[ASISctf] DLP

암독 과제해보고 암호문제 푸니까 재밋는것 같기도..

알고리즘은 이렇다.

def encrypt(nbit, msg):

    msg = bytes_to_long(msg)

    p = getPrime(nbit)

    q = getPrime(nbit)

    n = p*q

    s = getPrime(4)

    enc = pow(n+1, msg, n**(s+1))

    return n, enc

주어지는건 enc와 n 이고 msg를 알아내야한다.

식은 이렇다

enc=(n+1)^msg(modn^(s+1))

여기서 재밌는건 s+1>2이면 다음이 성립한다는 것!

enc=(n+1)^msg=msg*n+1(mod n^2)=mn+1(mod n^2)

이고

(enc-1)/n(mod n^2)=m이라는 식이 완성되었다.

이제 계산한다.

>>> gmpy2.div((enc-1)%(n**2),n)

mpz(3111713836765922319510495043104426235462341566734455114627991655609961822874033923703388182594027279760482968199249300393055526546602287243645)

>>> hex(3111713836765922319510495043104426235462341566734455114627991655609961822874033923703388182594027279760482968199249300393055526546602287243645)[2:-1].decode('hex')

'ASIS{Congratz_You_are_Discrete_Logarithm_Problem_Solver!!!}'

>>>