RSA 공격법: 약간의 평문을 알고, p/q값이 비슷할 때(Fermat Factorization attack)

from Crypto.Util.number import *
import gmpy2

p = getPrime(1024)
q = gmpy2.next_prime(p)
e = 65537
N = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.powmod(e, -1, phi)
flag = open("flag").read()

msg = ["Hello Happy RSA!", "Life like Pwn", flag]

def enc(m):
    tmp = bytes_to_long(m)
    ct = gmpy2.powmod(tmp, e, N)
    ct = long_to_bytes(ct)
    return ct.encode("hex")

print(enc(msg[0]))
print(enc(msg[1]))
print(enc(msg[2]))

c1 = 0x35e769b1f3955afc915696e1da02c449f6aa8f04ab476beacf80cc3e1dd040d76d6b576b6ec30a028ae72d42ebad4aa34ebe37a843bc83bd6e58b1d7348579a9014738e2cecf220fdb0a4992c20987c86bcfb42124d43f145d1cff94ff6d3e48e956c57ac612b8f856b46162c39bec9bbc51719bca49dec523a6dedccf4a7e008193c76c5eb5931de7b3ebf59c5e92e5bdab9e320a68bd9375813c189720ca9111c5d81526b2987cbcdbd2455f4ebcb0152eb39ae91e43ae05bbfe38d3237772f15f3417d6fa67187bbe2e913e53cb8a4a1ddf004588a7fe761437bf8b7568d0528f6494ab2835d94b633f866b7acfe1c343cbcf9033aec2eb359f6fc2ef9d34

c2 = 0x57f55e39c5a9a489fe02787690402fb3a3476e768fc11a9e95aa47e95306891badc6bea82f64348bd022f450b6327265b4f959a102a3f6ed8853cb1792b67ef3c1ec1c5424f02be279fa208ffbf86b9d9e4f129a0713863ff5bf883b81a4c2d3031a83b4bf5407176375c38fda17f71144655da0edbe6cd0b19324d39fa180adb8eb06d1a37d61c774385564f0ca73d72cac132c2616151cde7f7968ed21943b9edce743d32f9849d98948e6ae0faac3f4be95ed3324bafac8dc50a48edd051508fedd1076648f133689c3bbe59bc1c34cb7bee6042dd371d45e8c8b2afa63a5e38bf9185ac7ffc1837a7f6310b6b522b360416aae28a69d9d89d5ecc8dbdb2c

c = 0x0fa42a0459083b8f57c013744300196a1ff03ef3357c35f9732b180b50cebba0ab9449fe22a25da055115e625713178b4ebd28ac8d6d717ece2911a3de9a14ce470590b009f873a7aad041d9982738451622fd53f7c664b247e3148dc74bb70e9a861c916bb7a9e95a803de781b146509824df999e0be533dbaa42bb286979635b7fac8ef93f3d82556e942ac65c02bc220a6954832c7412a34819de9179e05b5edb34fd8f698569fc6b2c72317a20eb9ecd8c9f0f8348610dd433c9a2faf44e56c666c7904b6d275ff3f8a330de09484da1cd498922036d96b9a7d33290038ab76bc48f4ac1feb9a99dcc4f415d2d71180b84a51bdfe94c37c77916e2b02fc6

 

문제로 주어지는 py파일과 txt파일

주목할 것은 평문 2개와 그에 대응하는 암호문 2개를 알고 있다는 점이다

 

q값을 만들 때 next_prime함수를 사용했는데, gmpy2 모듈의 next_prime 함수를 이용할 경우 p, q값이 거의 차이 나지 않는다

이런 경우에는 n값만 주어져도 p, q값을 구할 수 있게 된다

n, e값만 있으면 gmpy2의 isqrt와 t_divmod를 이용해서 문제를 풀 수 있다

 

그런데 지금 주어진 값을 보면 n, e값이 없다

이는 RSA 암호문의 식을 살짝 바꿔서 생각할 수 있다

 

RSA 암호문 c는 이렇게 만들어진다

c= 평문^e mod N

 

이 식은 모듈러 합동의 특성을 이용해 살짝 바꾸면 이렇게 된다

N | 평문^e - c

즉 평문^e - c는 n의 배수이다

 

위에 경우에도 이렇게 식이 나오고

c1 = p1^e mod N , c2 = p2^e mod N

 

각각 이렇게 나타낼 수 있다

N | p1^e - c1
N | p2^e - c2 

 

 

두 식이 나왔으니 최대공약수를 구해서 n을 구한다

N = gcd(p1^e - c1, p2^e - c2)

 

여기까지 n값을 구했고, 지금 p, q값이 큰 차이가 없기 때문에 Fermat Factorization attack을 쓸 수 있다

e값은 65537로 두고 여기 defenit.kr/2019/09/24/Crypto/%E3%84%B4%20Research/RSA_for_CTF/ 코드를 참고했다

 

from gmpy2 import *

c1 = 0x35e769b1f3955afc915696e1da02c449f6aa8f04ab476beacf80cc3e1dd040d76d6b576b6ec30a028ae72d42ebad4aa34ebe37a843bc83bd6e58b1d7348579a9014738e2cecf220fdb0a4992c20987c86bcfb42124d43f145d1cff94ff6d3e48e956c57ac612b8f856b46162c39bec9bbc51719bca49dec523a6dedccf4a7e008193c76c5eb5931de7b3ebf59c5e92e5bdab9e320a68bd9375813c189720ca9111c5d81526b2987cbcdbd2455f4ebcb0152eb39ae91e43ae05bbfe38d3237772f15f3417d6fa67187bbe2e913e53cb8a4a1ddf004588a7fe761437bf8b7568d0528f6494ab2835d94b633f866b7acfe1c343cbcf9033aec2eb359f6fc2ef9d34
c2 = 0x57f55e39c5a9a489fe02787690402fb3a3476e768fc11a9e95aa47e95306891badc6bea82f64348bd022f450b6327265b4f959a102a3f6ed8853cb1792b67ef3c1ec1c5424f02be279fa208ffbf86b9d9e4f129a0713863ff5bf883b81a4c2d3031a83b4bf5407176375c38fda17f71144655da0edbe6cd0b19324d39fa180adb8eb06d1a37d61c774385564f0ca73d72cac132c2616151cde7f7968ed21943b9edce743d32f9849d98948e6ae0faac3f4be95ed3324bafac8dc50a48edd051508fedd1076648f133689c3bbe59bc1c34cb7bee6042dd371d45e8c8b2afa63a5e38bf9185ac7ffc1837a7f6310b6b522b360416aae28a69d9d89d5ecc8dbdb2c
e = 65537
c = 0x0fa42a0459083b8f57c013744300196a1ff03ef3357c35f9732b180b50cebba0ab9449fe22a25da055115e625713178b4ebd28ac8d6d717ece2911a3de9a14ce470590b009f873a7aad041d9982738451622fd53f7c664b247e3148dc74bb70e9a861c916bb7a9e95a803de781b146509824df999e0be533dbaa42bb286979635b7fac8ef93f3d82556e942ac65c02bc220a6954832c7412a34819de9179e05b5edb34fd8f698569fc6b2c72317a20eb9ecd8c9f0f8348610dd433c9a2faf44e56c666c7904b6d275ff3f8a330de09484da1cd498922036d96b9a7d33290038ab76bc48f4ac1feb9a99dcc4f415d2d71180b84a51bdfe94c37c77916e2b02fc6

p1 = int("Hello Happy RSA!".encode("hex"), 16)
p2 = int("Life like Pwn".encode("hex"), 16)

n1 = pow(p1, e) - c1
n2 = pow(p2, e) - c2

n = gcd(n1, n2)

p = isqrt(n)

while True:
    q, r = t_divmod(n, p)
    if r == 0:
        break
    p += 1
    
phi = (p-1) * (q-1)
d = invert(e, phi)

print ('%x' % pow(c, d, n)).decode("hex")