RoarCTF2019

这次roarCTF就简单看了看两道RSA的题目，感觉还是有新意的，现在特地记录一下

rsa

A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
p=next_prime(z*x*y)
q=next_prime(z)
A =                     2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n =  117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128

很明显，这里需要我们通过A和n的值来求出p,q的值，进而求出私钥d，最后进行解密。

我们先进行第一步，将x,y进行爆破：

#coding=utf-8

A = 2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
num = 0
#由于有指数2019，推测，x,y的值应该不会超过1000
for x in range(1,1000):
    for y in range(1,1000):
        if((x%y)!=0 and x!=0 and y!=0):
            num = (((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
            if(num == A):
                print("x:",x)
                print("y:",y)
#x = 2
#y = 83

得到x,y之后，我们可以利用n=p*q对z的取值进行爆破:

#coding=utf-8

import sympy
import math
n=117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
#m即是sqrt(n/166)的近似值
m=sympy.nextprime(842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458029)
c=86974685960185109994565885227776590430584975317324687072143606337834618757975096133503732246558545817823508491829181296701578862445122140544748432956862934052663959903364809344666885925501943806009045214347928716791730159539675944914294533623047609564608561054087106518420308176681346465904692545308790901579479104745664756811301111441543090132246542129700485721093162972711529510721321996972649182594310700996042178757282311887765329548031672904349916667094862779984235732091664623511790424370705655016549911752412395937963400908229932716593592702387850259325784109798223415344586624970470351548381110529919234353
p=0
q=0
#从m附近查找q或p
while(m>100):
    if(n%m==0):
        p=m
        q=n/p
        print("p=")
        print p
        print("q=")
        print q
        break
    m=sympy.nextprime(m)
#p
#c
#q
#139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183

然后就可以求出d:

# coding = utf-8
def computeD(fn, e):
    (x, y, r) = extendedGCD(fn, e)
    #y maybe < 0, so convert it
    if y < 0:
        return fn + y
    return y
 
def extendedGCD(a, b):
    #a*xi + b*yi = ri
    if b == 0:
        return (1, 0, a)
    #a*x1 + b*y1 = a
    x1 = 1
    y1 = 0
    #a*x2 + b*y2 = b
    x2 = 0
    y2 = 1
    while b != 0:
        q = a / b
        #ri = r(i-2) % r(i-1)
        r = a % b
        a = b
        b = r
        #xi = x(i-2) - q*x(i-1)
        x = x1 - q*x2
        x1 = x2
        x2 = x
        #yi = y(i-2) - q*y(i-1)
        y = y1 - q*y2
        y1 = y2
        y2 = y
    return(x1, y1, a)
 
p = 842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569
        q = 139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
e = 65537
 
n = p * q
fn = (p - 1) * (q - 1)
 
d = computeD(fn, e)
print("d:",d)
#8599589881775512182490339390302384847126810744233969198532121090013876515514061191844004921719994842305490870513682688025890863319222633068753414378485078624510630709922513396281417153363777832648184544232199294766471900485392788050293515601012127448268872412182805907996901141107293140818104160339368182321217372234809523842344722549604286239338414176997138752498663184064331483582259621245748238876057665171100280468834141443144340932719393320666917904802256624401993129580989389345716562456345455121702090606106185465724822179950100180548721991615891176882567105125169912160252167465495939533501038099782250065

然后就可以直接解密了：

#coding:utf-8
from Crypto.Util.number import long_to_bytes
    
n =117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127

d = 8599589881775512182490339390302384847126810744233969198532121090013876515514061191844004921719994842305490870513682688025890863319222633068753414378485078624510630709922513396281417153363777832648184544232199294766471900485392788050293515601012127448268872412182805907996901141107293140818104160339368182321217372234809523842344722549604286239338414176997138752498663184064331483582259621245748238876057665171100280468834141443144340932719393320666917904802256624401993129580989389345716562456345455121702090606106185465724822179950100180548721991615891176882567105125169912160252167465495939533501038099782250065

c = 41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128

m=pow(c,d,n)
#本来这里想使用libnum的一个库来着，但是可能因为某种玄虚原因不太行，所以以后字符串的转换还是使用pycrypto
print(long_to_bytes(m))
#RoarCTF{wm-l1l1ll1l1l1l111ll}

babyRSA

import sympy
import random

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

#p=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140651

q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
#q=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351043

r=myGetPrime()
#r = 237546113044253096281605033809113626736013565483812642295460095292363136024662398343531093674459197466191288877320101248913883958536348617639742373951502

n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=38620963949231568493951852806812359956058522979245676395704780066879051018892175913415575431734194586035432099562300809271498658506900105389975586615280808081596988894713047252672924018208747721253303054480800386069769084714127190055658807083226038640292692679215406182331245636616583141043207599068234065117886147748321058731290102675088056205224134057176167818706519201527516421824645801542347535393294450756726281744763656819345306146716190523210020241675468
#so,what is the flag?

以前没做过这种题目，现在遇到正好积累一下，关于三个合数的RSA

这里需要用到一个数学结论:

wilson定理，公式表达大概如下，此处p为素数

( p-1 )! = -1 mod p

应用：快速求阶乘

$$n<p: \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \\ n!*[ (n+1) * (n+2)···* (p-1) ] = -1\ mod\ (p) \qquad \qquad\qquad \\ 令p = n-x: \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad\qquad \qquad \qquad \qquad \qquad\\ n!*[ (p-x+1) * (p-x+2) * ···* (p-1) ] = (p-1)\ mod\ (p) \\ 那么：\qquad \qquad\qquad \qquad\qquad \qquad\qquad \qquad\qquad \qquad\qquad \qquad\qquad \qquad\quad \\ (n!)' = (p-x+1)*(p-x+2)*···*(p-2) \qquad \qquad\qquad \quad$$

解密脚本如下：

#coding=utf-8
from Crypto.Util.number import long_to_bytes
import gmpy2

def myGetPrime(A,B):
    ans=1
    for i in range(B+1,A-1):
        ans=(i*ans)%A
    s=gmpy2.invert(ans,A)
    return gmpy2.next_prime(s)

A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e=0x1001
p=myGetPrime(A1,B1)
q=myGetPrime(A2,B2)
r=n//(p*q)
phi=(r-1)*(q-1)*(p-1)
d=gmpy2.invert(e,phi)
enc=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
m=pow(enc,d,n)
print(long_to_bytes(m).decode())

RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}