RSA 3

문제

RSA - 3 100

I was finally able to capture the modulos and ciphertext that my friend uses to send the flag to everyone. Please hack it, and tell me what he is sending.

Note: Different flag format.

rsa3.txt

풀이

같은 메시지를 다른 public key 로 계속 보낸다면 의심하라 e가 작은지 확인해 볼것

알려주지 않았다. 높은 확률로 Hastad s Broadcast Attack이다.

CRT를 이용하여 숫자가 변하지 않을 때까지 숫자를 키운다.

p = 1
while len(ns) != 0:
    c1 = crt(c, cs[1], n, ns[1])
    p += 1
    n *= ns[1]
    ns = ns[1:]
    cs = cs[1:]
    if c == c1:
        break
    c = c1

몇 제곱을 했는지 모르기 때문에 e의 값을 BF를 해본다.

상위 비트 부터 게싱하여 c값보다 작은지 확인하고, 마지막 비트까지 게싱하였다면 같은지 확인한다.

for j in range(p - 5, p+10000):
    m = 0
    for i in range(length/(j - 3), -1, -1):
        m97 = pow((m+(2^i)),j)
        if m97 <= c:
            m = m + (2^i)
    m97 = pow(m,j)
    if m97 == c:
        print hex(m).decode("hex")
        break

전체 소스 (sage)

solve.sage

hackcon{h4st4d_n0t_s0_f4st3d_8r04dc457_8u7_m3554g3_15_10ng_cuz_p0w3r_15_5m4113r_th4n_u5u41}