[SEE CTF] Crypto-OpenEndendRSA

OpenEndendRSA

BabyRC4와 같이 코드로 풀면 될 것 같다.

 

 

from Crypto.Util.number import *
from gmpy2 import iroot # this helps with super accurate square root calculations!

flag = b'????????????????????????'
m = bytes_to_long(flag)
e = 0x10001
pp = bytes_to_long(b'????????????????')
s = 1
assert isPrime(pp) #소수 판별

while not isPrime(s):
    p = getPrime(512) #키 생성
    s = p**2 + pp**2 

assert iroot(s-pp**2,2) == (p, True)  # quick demo on how to use iroot()
assert s%2 == 1                       # duh, s is a prime number after all!

q = getPrime(512)
n = p*q
c = pow(m,e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f's = {s}')

"""
n = 102273879596517810990377282423472726027460443064683939304011542123196710774901060989067270532492298567093229128321692329740628450490799826352111218401958040398966213264648582167008910307308861267119229380385416523073063233676439205431787341959762456158735901628476769492808819670332459690695414384805355960329
e = 65537
c = 51295852362773645802164495088356504014656085673555383524516532497310520206771348899894261255951572784181072534252355368923583221684536838148556235818725495078521334113983852688551123368250626610738927980373728679163439512668552165205712876265795806444660262239275273091657848381708848495732343517789776957423
s = 128507372710876266809116441521071993373501360950301439928940005102517141449185048274058750442578112761334152960722557830781512085114879670147631965370048855192288440768620271468214898335819263102540763641617908275932788291551543955368740728922769245855304034817063220790250913667769787523374734049532482184053
"""

n, e, c, s를 활용해서 해결하면 될 것 같다..

 

 

우선 gmpy2 툴을 설치해준다.

pip install gmpy2

우선 s는 소수인 것을 알고 있다. s는 소수이기 때문에 홀수가 된다. (짝수인 경우 2로 나누어지기 때문에 소수가 될 수 없음.)

p와 pp는 소수이고, p**2 + pp**2 = s

p는 512비트 소수(getPrime(512))이므로 p는 홀수여야 한다.

따라서 p**2는 홀수이다.

 

s는 홀수이므로 s - p**2는 짝수여야 한다.

홀수(p**2) + 홀수(pp**2) = 짝수(s)는 홀수(p**2) + 짝수(pp**2) = 홀수(s)이므로 pp**2는 짝수여야 한다.

pp**2는 짝수인 것은 pp가 짝수라는 것을 의미한다.

하지만 pp는 소수이다. 짝수인 소수는 '2'가 유일하기 때문에 pp는 2가 된다.

 

 

이 다음 p를 찾을 수 있고 RSA 암호 해독은 간단하다.

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot

n = 102273879596517810990377282423472726027460443064683939304011542123196710774901060989067270532492298567093229128321692329740628450490799826352111218401958040398966213264648582167008910307308861267119229380385416523073063233676439205431787341959762456158735901628476769492808819670332459690695414384805355960329
e = 65537
c = 51295852362773645802164495088356504014656085673555383524516532497310520206771348899894261255951572784181072534252355368923583221684536838148556235818725495078521334113983852688551123368250626610738927980373728679163439512668552165205712876265795806444660262239275273091657848381708848495732343517789776957423
s = 128507372710876266809116441521071993373501360950301439928940005102517141449185048274058750442578112761334152960722557830781512085114879670147631965370048855192288440768620271468214898335819263102540763641617908275932788291551543955368740728922769245855304034817063220790250913667769787523374734049532482184053

p = iroot(s-4, 2)[0]
assert n % p == 0
q = n//p
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

SEE{0dd_3vEN:deadbeef}

 

 

SEE{0dd_3vEN:deadbeef}