[Cryptohack] RSA (Factoring, Inferius Prime)

Factoring

 

문제

지금까지 계수에 작은 소수의 제품을 사용해 왔지만, 작은 소수는 최신 방법을 사용하여 인수 분해할 수 있기 때문에 RSA에 그다지 좋지 않습니다. "작은 소수"란 무엇입니까? RSA 모듈리를 인수할 수 있는 팀에게 상금이 수여되는 RSA Factoring Challenge가 있었습니다. 이를 통해 대중은 다양한 키 크기가 얼마나 오랫동안 안전하게 유지될 수 있는지에 대한 통찰력을 얻을 수 있었습니다. 컴퓨터는 더 빨라지고 알고리즘은 더 좋아지기 때문에 암호학에서는 항상 주의를 기울이는 편이 신중합니다. 요즘에는 최소 1024비트 길이의 소수를 사용하는 것이 좋습니다. 이러한 1024비트 소수 두 개를 곱하면 2048비트의 계수가 됩니다. 2048비트 계수의 RSA를 RSA-2048이라고 합니다. 미래에 대비하려면 RSA-4096 또는 RSA-8192를 사용해야 한다는 의견도 있습니다. 그러나 여기에는 트레이드오프가 있습니다. 큰 소수를 생성하는 데 더 오랜 시간이 걸리고 모듈식 지수는 큰 계수로 예측할 수 있을 정도로 느립니다. 150비트 번호 5101437587355090255308200653196460532653147을 두 개의 구성 소수로 분해합니다. 둘 중에 작은 것을 골라주세요.

풀이

from sympy.ntheory import factorint

print(factorint(510143758735509025530880200653196460532653147))

 두개의 소수를 factorint를 통해 분리하였고

그중에 작은 걸 고르면 됬으니

플래그값은 19704762736204164635843이다.

Inferius Prime

문제

다음은 매우 강력한 RSA 구현입니다. 1600비트의 강력한 RSA이기 때문에 깨지지 않을 것입니다... 적어도 나는 그렇게 생각합니다!

풀이

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD

e = 3

# n will be 8 * (100 + 100) = 1600 bits strong which is pretty good
while True:
    p = getPrime(100)
    q = getPrime(100)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    if d != -1 and GCD(e, phi) == 1:
        break

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag

 

output.txt

이번에 준 코드를 보게 되면 플래그값인 평문값을 비밀키 e와 n값으로 mod계산을 하여 암호문을 만들고

n과 e, 암호문을 txt파일로 보여준다.

 

일단 RSA STARTER문제들을 볼때 먼저 비밀 키를 구하기 위해 n을 통해 두 소수를 구해야된다.

factorint를 사용하기엔 시간이 너무 오래걸림(http://factordb.com/)

p는 752708788837165590355094155871

q를 986369682585281993933185289261로하여

이를 비밀키로 만들어 flag값을 구해보았다.

from Crypto.Util.number import inverse
from Crypto.Util.number import long_to_bytes

e = 3
n = 742449129124467073921545687640895127535705902454369756401331
ct = 39207274348578481322317340648475596807303160111338236677373

p = 752708788837165590355094155871 
q = 986369682585281993933185289261 

phi = (p - 1) * (q - 1)
d = inverse(e, phi)




pt = pow(ct, d, n) 
pt_hex = hex(pt)
print( bytearray.fromhex(pt_hex[2:]).decode())

플래그값은 crypto{N33d_b1g_pR1m35}이다.