[Crypto] RRSSAA - K1rit0

xp0int Posted on Apr 29 2021

三层的RSA, 一层一层解出来就行了
# Level 1
参考[这里](https://4rch4ngel6320.wordpress.com/2018/12/10/inctf-quals-2018-multiprime-rsa-writeup/)
N有多因子的RSA,且这些因子都跟其中一个因子有关
这样就能得到这个因子跟N的关系, 从而得到该因子的一个近似
然后根据这近似来寻找这个因子, 找到了就可以得到其他因子了

# Level 2
2020祥云杯 RSAssss 一样的, 条件还更多了
直接费马分解再利用gcd得到四个因子

# Level 3
利用费马小定理可以知道, $m^{-7}C4 - 1 \ (mod \ n)  = kp$
求$gcd(kp,n)$可以得到p
因为s是2^10位, 简单爆破就能出来了
这样就能得到e了

## 脚本
```python
from Crypto.Util.number import *
from gmpy2 import gcd,invert as inverse_mod,next_prime,iroot
# LEVEL 3
R = 81225738828166640599054154023183465870678960906769673605358084529196871174429427936591822589995476552044227730868809310992934103731850597399114246762836121101348301079296663951503688072299542357013093324718850936925265954204973634470836187733828189312553819810470405246669124171178070485118436102895117354417
C4 = 22238585749689335043198360403653248049710943304594623939441271714322821476047298977043454290592085809700500599520080107736858423927071836758485527270617538166045213386679961664240306883126224169183649140929168343634245637578487850945986688768857954082116136864696582066988005306045105860368497626822666433678879698344619056273526837700698315346972423482713305543394110949178233504551465821354514535155389087138867576532139739270960823294873497825040963862751772914087741831403951901
C3 = 2385064917660948806957457681641614888669217960607006360543268900921017481245498563263991410918604891314384810533439253814523067168636768976220059028108900592323119524657903364697700329145453517769093265052715204625870232288203427545150983037310876534801548309890853026234248412421497939811385725642492104262954059677793538707604205179344884142656842895567795000647837461835179395742399372683460208271310884657279893532539121893558143029933794905470899127632780110459122203796256514
n3 = 24502730939655407292543436897382196297516664227273320602397906878696723372242877776550446563950867624819352853122033114711732125433588724779869985477495098802744344448915032607469954642257825855931872281908232331623829725043031800535739432133948607448362641204034546581444904408754892037110031202573463399201625812005615264689877537231974023870006792196961829162058446662172634212427186470724599941352830546043772969297733239518604749366684163813795999625784931375110137805143337329

R7inv = inverse_mod(R**7,n3)
C5 = (C4 * R7inv)%n3
p3 = gcd(C5-1,n3)
q3 = n3 // p3
phi = (p3-1)*(q3-1)

for i in range(2,2**11):
    s = i
    if(gcd(s,p3-1) == 1):
        sinv = inverse_mod(s,p3-1)
        e = 4*s*sinv+3
        if(gcd(phi,e) == 1):
            if pow(R,e,n3) == C4:
                break

d = inverse_mod(e,phi)
C2 = pow(C3,d,n3)

# LEVLE 2
# 利用fermat分解 得到一个因子ou
e = 65537
n2 = 8799438599707547810413590252769637047669730373282934937368515093438977181200080057948977998859737775815535703211966248578669447308370171323881776611030752648135480196879162497896464322936833458775227550623435000527614781055524145936353357662536280470664112516976033358499330391929435857811788923590666783090016628619936968367309955759172412259970189158362661969
os = 2966384769329081457959929210854946307725303451729041111756565081822209869706734847077404063837454548238096227843381458842322035116059935545789370388767999132347222281376931478665079
ou =2966384769329081457959929210854946307725303451729041111756565081822209869706734847077404651306368582818672174524720657329423156396400608586670887330204238883628829887762408566296707
o = gcd(ou,os)
s = os//o
u = ou//o
t = n2//(o*s*u)

phi = (o-1)*(s-1)*(u-1)*(t-1)
d = inverse_mod(e,phi)
C1 = pow(C2,d,n2)

# LEVEL 1
def primesgen(p):
    q = next_prime(21*p)
    r = next_prime(3*p*q)
    return p*q*r

def find_p(papprox, n):
    while True:
        n_approx = primesgen(papprox)
        if n != n_approx:
            papprox = papprox - 1
        else:
            return papprox

e = 65537
n1 = 7296833146437859657873621309783663953888975990236533231501856312811032923469834028894995888763882827280881148914714991084488173289859941577252999932599209531912854472326211936264815965582591809770319779712527572174152560819828597241583278731544411246154674514626001858732363262751244419415544407653873858309154132440262888841600498885105451586030156787
papprox = iroot(n1 // 1323, 4)[0]
p = find_p(papprox, n1)
q = next_prime(21 * p)
r = next_prime(3 * p * q)

phi = (q-1)*(p-1)*(r-1)
d = inverse_mod(e,phi)
msg = pow(C1,d,n1)
print(long_to_bytes(msg))
```

## flag值
flag{4c2fd4e6-44de-445f-8c34-1235464de2de}

打赏还是打残，这是个问题