문제파일을 받아보니 아래와 같은 파이썬 코드가 있었는데
from math import lcm
from Crypto.Util.number import*
with open('flag.txt', 'rb') as f:
flag = bytes_to_long(f.read().strip())
oops = getPrime(20) #e
p1 = getPrime(512)
p2 = getPrime(512)
haha = (p1-1)*(p2-1) #phi
crazy_number = pow(oops, -1, haha) #d
discord_mod = p1 * p2 #n
hehe_secret = pow(flag, crazy_number, discord_mod) #c
print('admin =', discord_mod)
print('hehe_secret =', hehe_secret)
print('crazy number =', crazy_number)주석처리를 하면 이렇게 된다 이때 oops는 e가 되는데 getprime(20)이면 e값이 20자리 소수로 너무 큰 값이된다
그래서 이때 wienr attack 을 사용하게 되면 flag 값이 나온다
'''
Created on Dec 22, 2011
@author: pablocelayes
'''
def egcd(a,b):
'''
Extended Euclidean Algorithm
returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
'''
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return u, v, a
def gcd(a,b):
'''
2.8 times faster than egcd(a,b)[2]
'''
a,b=(b,a) if a<b else (a,b)
while b:
a,b=b,a%b
return a
def modInverse(e,n):
'''
d such that de = 1 (mod n)
e must be coprime to n
this is assumed to be true
'''
return egcd(e,n)[0]%n
def totient(p,q):
'''
Calculates the totient of pq
'''
return (p-1)*(q-1)
def bitlength(x):
'''
Calculates the bitlength of x
'''
assert x >= 0
n = 0
while x > 0:
n = n+1
x = x>>1
return n
def isqrt(n):
'''
Calculates the integer square root
for arbitrary large nonnegative integers
'''
if n < 0:
raise ValueError('square root not defined for negative numbers')
if n == 0:
return 0
a, b = divmod(bitlength(n), 2)
x = 2**(a+b)
while True:
y = (x + n//x)//2
if y >= x:
return x
x = y
def is_perfect_square(n):
'''
If n is a perfect square it returns sqrt(n),
otherwise returns -1
'''
h = n & 0xF; #last hexadecimal "digit"
if h > 9:
return -1 # return immediately in 6 cases out of 16.
# Take advantage of Boolean short-circuit evaluation
if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ):
# take square root if you must
t = isqrt(n)
if t*t == n:
return t
else:
return -1
return -1
'''
Created on Dec 14, 2011
@author: pablocelayes
'''
# Types
CFListT = list[int] # CF coefficients
CVListT = list[tuple[int, int]] # Convergents at each coefficient level
def rational_to_contfrac(x: int, y: int) -> tuple[CFListT, CVListT]:
"""
Converts a rational x/y fraction into
a list of partial coefficients [a0, ..., an], and
a list of convergents at each coefficient level [(n0, d0), (n1, d1), ...]
The algorithm of computing the convergents from left to right is available
in Section 9.1 of https://r-knott.surrey.ac.uk/Fibonacci/cfINTRO.html#CFtofract
Args:
x (int): numerator of the given rational number
y (int): denominator of the given rational number
Returns:
tuple[CFListT, CVListT]: a tuple of coefficients and convergents at each
coefficient level
"""
a = x // y
cflist = [a]
cvlist = [(a, 1)]
ppn, ppd = 1, 0 # pre-pre numerator and denominator of convergent
pn, pd = a, 1 # pre numerator and denominator of convergent
while a * y != x:
x, y = y, x - a * y
a = x // y
cflist.append(a)
cn, cd = a * pn + ppn, a * pd + ppd
cvlist.append((cn, cd))
ppn, ppd = pn, pd
pn, pd = cn, cd
return cflist, cvlist
def hack_RSA(e,n):
'''
Finds d knowing (e,n)
applying the Wiener continued fraction attack
'''
_, convergents = rational_to_contfrac(e, n)
for (k,d) in convergents:
#check if d is actually the key
if k!=0 and (e*d-1)%k == 0:
phi = (e*d-1)//k
s = n - phi + 1
# check if the equation x^2 - s*x + n = 0
# has integer roots
discr = s*s - 4*n
if(discr>=0):
t = is_perfect_square(discr)
if t!=-1 and (s+t)%2==0:
print("Hacked!")
return d
########### 풀이 #########
from math import lcm
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes
# with open('flag.txt', 'rb') as f:
# flag = bytes_to_long(f.read().strip())
# oops = getPrime(20)
# p1 = getPrime(512)
# p2 = getPrime(512)
# phi = (p1-1)*(p2-1)
# crazy_number = pow(oops, -1, phi)
# n = p1 * p2
# hehe_secret = pow(flag, crazy_number, n)
# # pow = flag ** cn % n
# print('admin =', n)
# print('hehe_secret =', hehe_secret)
# print('crazy number =', crazy_number)
admin_n = 115527789319991047725489235818351464993028412126352156293595566838475726455437233607597045733180526729630017323042204168151655259688176759042620103271351321127634573342826484117943690874998234854277777879701926505719709998116539185109829000375668558097546635835117245793477957255328281531908482325475746699343
ct = 10313360406806945962061388121732889879091144213622952631652830033549291457030908324247366447011281314834409468891636010186191788524395655522444948812334378330639344393086914411546459948482739784715070573110933928620269265241132766601148217497662982624793148613258672770168115838494270549212058890534015048102
cn_e = 13961211722558497461053729553295150730315735881906397707707726108341912436868560366671282172656669633051752478713856363392549457910240506816698590171533093796488195641999706024628359906449130009380765013072711649857727561073714362762834741590645780746758372687127351218867865135874062716318840013648817769047
d = hack_RSA(cn_e, admin_n)
# using lcm
print(f'{d = }')
flag = pow(ct, d, admin_n)
print(f'{flag = }')
print(f'{long_to_bytes(flag) = }')https://github.com/pablocelayes/rsa-wiener-attack/blob/master/RSAwienerHacker.py
rsa-wiener-attack/RSAwienerHacker.py at master · pablocelayes/rsa-wiener-attack
A Python implementation of the Wiener attack on RSA public-key encryption scheme. - pablocelayes/rsa-wiener-attack
github.com
위 코드를 참고하여 flag 값을 도출했다
tjctf{congrats_on_rsa_e_djfkel2349!}
'Cryptography' 카테고리의 다른 글
| RSA CRT Attack 중국인 나머지 정리 (2) | 2024.05.08 |
|---|---|
| [python] .pem 파일에서 e,n 얻기 (0) | 2024.03.27 |
| [Cryptohack] Diffie-Hellman Starter 1 write up (0) | 2024.03.04 |
| RSA 낮은 지수 공격 cyling Attack code (0) | 2024.03.03 |
| BraekerCTF Write up - Thus spoke machine (0) | 2024.02.29 |
