Tjctf writeup - weird crypto

문제파일을 받아보니 아래와 같은 파이썬 코드가 있었는데 

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

위 코드를 참고하여 flag 값을 도출했다 

tjctf{congrats_on_rsa_e_djfkel2349!}