###### tags: `writeups`

# Writeup for RSA in 2019西湖决赛

## 0x00 Observation

这是一道标准的RSA加密，给出了`n, e, d`

用`Winhex`打开`output`文件提取数据


## 0x01 Analysis
`flag`是对`p+q`的`md5`加密值，所以需要根据`n, e, d`将`n`质因数分解成`p`和`q`。

关于如何在给定的`e`和`d`的情况下分解`n`，有一篇 [paper](http://www.ams.org/notices/199902/boneh.pdf) 提供了一个通法。


## 0x02 Decryption
根据paper所给出的方法，写出解密脚本：

# python2
from md5 import md5

def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309
e = 65537
d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453

k = e * d - 1
x = pow(2, k / 4, n)
assert x != 1

p = gcd(x - 1, n)
q = n/p

print "p: %d\nq: %d" % (p, q)
print "Flag: flag{%s}" % md5(str(p + q)).hexdigest()
# p: 134388416661738455437155072073325006890713121761597606147089758733385481112565493304597414841403553334452751594251761452974840757858360219741735123120957682353146947112071576479841838875008748813717254467137424822946053401492632307085887983816096569782409349352398269269865393361999329194582827715646840442991
# q: 121681461613856685891389697655082707982324934394003375745821514797619569583750841725694490585739982440237839675155146102668334623474524757328414864963814738071946391260695792366762521733527504377788503669628114869921159658618293030663730923781347146576731525405173348568491361155907470541865888995846800200299
# Flag: flag{e7ddad281ff7dfc99eb3379e0efd46f8}

## 0x03 Another solution
事实上，只需要求出`p+q`即可，也就是说不必单独地算出`p, q`。

一方面，由于`φ(n) = (p-1)(q-1) = pq - (p+q) + 1`，其中`pq=n`已知，所以只要算出`φ(n)`即可求得`p+q`。

另一方面，根据RSA的定义，有`ed = kφ(n) + 1`。现在`e, d`都已经给出，因而可以算出`kφ(n) = ed - 1` ；其中`k`是一个倍数，可以看出k的大小与e差不多，因此只要对`kφ(n)`质因数分解，遍历`k`的所有可能，就可以得出`φ(n)`。

通过[factordb.com](http://factordb.com/index.php?query=619975326238334242368958597123431397321696562598847237022837931599422896760672261337075922446419144388114565878486630608+795773759034002466744540702920876929104199960132389007171759582002764376358852199767600296991275608656880855328406633746+452154920439135530012220763400989200237576432259418251227673279321827658075721199628006034684913034623245373006845076468+718237388124825301338471741006439692037719534256618958449667738791738159898043898185419198805714424017915679921668677960+930177703687930455411027800434983508809554681582866712385929888987740571994181085546494962075837368611684515439393666021+043721588123067801260)网站对算出来的`kφ(n)`质因数分解：


解密：

# python3
import itertools
import hashlib

n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309
e = 65537
d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453

def GetMultiple(l):
    ans = 1
    for i in l:
        ans*=i
    return ans


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
    

kphi = e*d - 1
factor = [3,3,5,7,11,31,1223,12503,40499] # φ(n)中必有因数4
kk = []
for i in range(1,len(factor)):
    c = list(itertools.combinations(factor, i))
    for kkk in c:
        m = GetMultiple(kkk)
        if 1000 < m < 1000000: # 根据e，d，n的大小预估k的范围
            kk.append(m) # all possible k

for k in kk:
    phi = kphi//k
    x = n+1-phi
    y = n
    if(is_perfect_square(x**2-4*y)!=-1): # verification
        print("k: %d" % k)
        print("p+q: %d" % x)
        print("Flag: flag{" + hashlib.md5(str(x).encode()).hexdigest()+"}")
# k: 37913
# p+q: 256069878275595141328544769728407714873038056155600981892911273531005050696316335030291905427143535774690591269406907555643175381332884977070149988084772420425093338372767368846604360608536253191505758136765539692867213060110925337749618907597443716359140874757571617838356754517906799736448716711493640643290
# Flag: flag{e7ddad281ff7dfc99eb3379e0efd46f8}

## 0x04 Reference
[1] [https://stackoverflow.com/questions/5747013/how-to-factor-rsa-modulus-given-the-public-and-private-exponent](https://stackoverflow.com/questions/5747013/how-to-factor-rsa-modulus-given-the-public-and-private-exponent)
[2] [http://www.ams.org/notices/199902/boneh.pdf](http://www.ams.org/notices/199902/boneh.pdf)
[3] [https://www.di-mgt.com.au/rsa_factorize_n.html](https://www.di-mgt.com.au/rsa_factorize_n.html)