RSA整理

RSA

百越杯math

题目,给了n1,n,和密文flag,公钥e。

from libnum import *
from Crypto.Util.number import *
from gmpy2 import next_prime
from flag import flag
flag = s2n(flag)
a = getRandomRange(pow(10,499),pow(10,500))
b = getRandomRange(pow(10,499),pow(10,500))
p = a*pow(10,500)+b
q = b*pow(10,500)+a
print p*q
e = 65537
c = getRandomInteger(100)
p = next_prime(p+c)
q = next_prime(q+c)
n = p*q
print n
flag = pow(flag,e,n)
print flag

可以通过n1,求p1,q1。

其中先求从n1中分解出a*b

n1=a*b*pow(10,1000)+a*a*pow(10,500)+b*b*pow(10,500)+a*b

n1一共有2000位,前500位和后500位拼接可以得到a*b,考虑到进位有三种可能,都测试一下,最后得到a,b。从而求出p1,q1

n=37290153165969298170747767487987767106604956327590459309623310884436645867385405226836923826439760402232182199047042298740970941114757402758035338227352981884345194304183079410512904720516197002459598643659802383718137698974557870280366585586392385470235597777672593360788744398375690898546971801388821194234775373952698134335885991694714949974679482564600815766377388895037809222168800554222619940240853717965637149897765149770956991503459995786889995461520332980787566967767243445754450380553166156028030513979079301998632175402072502016282327825403961392784400687386536170117841528456263456021394359662685873080287765689757030352392386374307257266677811647633925457228036341541693812765785784057781251815707260401922647083928541835257244409503393940374048782722357915189148582407507806733352268172024029303953342827905707727300151171157623562387977156106983516547443642151573456682745626175061369310982040554116369983687552560719792717887667637107087090897681039368534492698712183905213300675019880169669159964289135274268951386122314246699412166656323475268623240778461031327966634628420986855022944785421496251349486099392411145566566437986155875600117002222032846697544656901210849382567936904958595228620017066673190455548617917273881089052468844830306632804733848750820391807100094948772492402636422551350516389981409116121666282434777976293668265700614707939438561465158100805697922866599682141928964956895065357677209698826476508887966210560085802544989199042295263908880764987497015388183619829914488242002252489035055312547747792033076017959711401664024465093007341377103124755426567781873434171576297409356302054965976819782564966567852321032108507478998871390301458143582617644492262165902951270805160376459476885522275531457938661136508391452032625051782015102833218959697470722331233350397631435041061401412630047713991858871735035714326218833998760244965866341087147750123869855038366992182962371334384526411144813368418246803652025254206189223834187719880012103660703380187226220860

ab=3729015316596929817074776748798776710660495632759045930962331088443664586738540522683692382643976040223218219904704229874097094111475740275803533822735298188434519430418307941051290472051619700245959864365980238371813769897455787028036658558639238547023559777767259336078874439837569089854697180138882119423477537395269813433588599169471494997467948256460081576637738889503780922216880055422261994024085371796563714989776514977095699150345999578688999546152033298078756696776724344575445038055316615519829914488242002252489035055312547747792033076017959711401664024465093007341377103124755426567781873434171576297409356302054965976819782564966567852321032108507478998871390301458143582617644492262165902951270805160376459476885522275531457938661136508391452032625051782015102833218959697470722331233350397631435041061401412630047713991858871735035714326218833998760244965866341087147750123869855038366992182962371334384526411144813368418246803652025254206189223834187719880012103660703380187226220860


a2b2=n-(pow(10,1000)+1)*ab #a**2+b**2
# print a2b2
t=a2b2/pow(10,500)
# print t #len:1001

t1=t+2*ab #(a+b)**2
print "(a+b)**2:",t1 #(a+b)**2 len:1001
t2=t1-4*ab #(a-b)**2
print "(a-b)**2:",t2 #(a-b)**2 len:1001

tt1=iroot(t1,2)[0]
print "(a+b):",tt1 #(a+b)
tt2=iroot(t2,2)[0] 
print "(a-b):",tt2 #(a-b)

b=(tt1-tt2)/2
a=tt1-b
print "b:",b
print "a:",a
p = a*pow(10,500)+b
q = b*pow(10,500)+a

c是一个20位的数,通过二分法爆破,最后用p1,q1,c得到p,q

c1=223544898878048947880330262959
c2=253544898878048947880330262959
def fun(c1,c2):
    c = (c1+c2)/2
        p=7724533844747394899349412339828776507222531964570563673657731510573489841606241899431933799753548435100266998960524464930676080336780106550530528156652698098697939066388001862335776045810162308820460444103489118460484370360374490252853308767775503254680817659918620827189505621697773686635428578989940339364335258812085155863395156211658749886912345720117817903261544675017614190883555615406264212068632733125247667940798492107549869436238502679059874386631718816248039209963903483751137734845937488448274956023820422762712035969893644873130710756898125766905141097162634971719675541937272502083073371337486398745408176446378960949530179254458951059359334312627484778865569189174918141307780733163571737089532375061096755773211249431675122668604315339846808046876666178988233969079030213364891617388431952560954924381712484465088395641644984415182477503907081799371321500277312785408279987356973984610573989890126043071505051543960194615504894391665369281429295377569609839082507454042128770271891415
    q=4827495602382042276271203596989364487313071075689812576690514109716263497171967554193727250208307337133748639874540817644637896094953017925445895105935933431262748477886556918917491814130778073316357173708953237506109675577321124943167512266860431533984680804687666617898823396907903021336489161738843195256095492438171248446508839564164498441518247750390708179937132150027731278540827998735697398461057398989012604307150505154396019461550489439166536928142929537756960983908250745404212877027189141577245338447473948993494123398287765072225319645705636736577315105734898416062418994319337997535484351002669989605244649306760803367801065505305281566526980986979390663880018623357760458101623088204604441034891184604843703603744902528533087677755032546808176599186208271895056216977736866354285789899403393643352588120851558633951562116587498869123457201178179032615446750176141908835556154062642120686327331252476679407984921075498694362385026790598743866317188162480392099639034837511377348459374884
    p = next_prime(p+c)
    q = next_prime(q+c)

    n2=p*q
    if n2>n:
        print "c1:",c1
        print "c2:",c
        fun(c1,c)
    elif n2<n:
        print "c1:",c
        print "c2:",c2
        fun(c,c2)
    elif n2==n:
        print "p:",p
        print "q:",q
        exit(0)
    else:
        print "error"
        exit(0)
fun(c1,c2)

最后解密得到flag

c=37184996108096167233025618263505757153157343097156888579791591678112798126919291822117280574121886798076450090988956975942694991748710209332101082905159257360206646364269758967180975253962825625943696420172327932961625085719678913462057142665457670366149034781204452807008455874986258694889544297820868505385801547530471600056912582928858038944066247597538813265625994454536879142936629149425871030836276097612443965190900147217177268273320302968487288289500066066413057425060274495415705347775452378126322700828792271046010263910271491830733016822853700053524052302275780619672110356657862368196424416287062999248715568046365255257809392739368556770263662626707604374137827085932252100188620626033333675559976574305831148764403296339508944436482748296238651395448197460974036742794395872850277918173344274773788864080695651830624419146757315446431269176300228703998177892985982388577831521216077129479998846266657008240203501406588349129137285647942569321607846013589344817050392650458477423460119297842938591617558953789224928692831245011187614395138305116091095517452781922364575105441246935183151829079785593965595659385764661764536534314109799011221376335166825363745468702289956019189691732841787948543771767552418889945812912952844388135828118570454948482278617042826378637743128777368607901501702388930246381982139634661483616105908175895785968677045741141086145187314146524800384426347813569795767829229399693985449649456073846347751123890326703399205472967773736717062282465272801543616851680865089979007872017576434756441977097817456958807489726277542047228572876003573562220328683701400744899648300227399574965938796721337143228465728576794734241148236493866791812420360737798058399689694043617192496134725512211166304050577572889549976404923415229865890151512800020112421854251196729060158218415862519607464231622361159436715876677889457900668694738243191441657050304632774189736769141333132873006921328644347784442609254582911864794147017850676177776316795316841373510481580805823659839
N=p*q
phin = (p - 1) * (q - 1)
e = 65537
d = invert(e, phin)
print "d",d#137443939677632407697822373106774146170757453506013404320961
flag = powmod(c, d, N)
print hex(flag)[2:].decode('hex')

unctf babyrsa

#!/usr/bin/env python2
# -*- coding:utf8 -*-
from Crypto.Util.number import *

flag='XXXXXXXXXX'
e=0x10001 #65537
n=3464115689260819392935656139231271022088014497600959975252672820761470484618617542699739764705620767566046150296286140279466041905437740736319886548924058066340624280173573039937440574809212831672936265975209972857747738693288788052694888593629820783280181774594890101819911390468376042288685444703477639361249422054925155575158181408046447773183467474182159096249846479461475003039637685547191529769071424947165685996675043741359728960138725130116665515880652680244470002603320184043266997163009799067135481330853926800023087208636366543210276325733789567957712475079676808820490428973148590780103404729397985019089646026534758042652163974037179260930147000267787012874887703048185189387666199961350969478997330352491403611551096779887936063702892671572230523920277869824082318417366635732798078805070773662305098133013800559413976855639167085996705265872418286939474978058429877355305699191892248323534097124680592084808397263288943661630283254265898940430505371463275516870915261799702701453110383723660477322192658118815861974573497885759332587457883589126213868868281682733732394640188383458580555618181208722172011645063817887462511925363883111475043389367021569982583145912277082528397480756465818166640691294267829613428532584923122279261412957652411789780285394451850006055483598427256129336822790446219260722224551892755568723667049099823707012236618539013908897459508493477299241358343681962043777720375898238069411747593247677719659288861028038609681592049271388766040068274682329498410270047730060645409396168652996740411436504098243588534151795927613112273405281530700440843961363083171583053608594479571127638861391879160062136043924515492933057094406001740725150570943724333872057035272515676895138632004436149126542560186729495087753846670118167613304943153665660470977150177815354160112481310498255965933157902965011317272734556307544837058247794721427834401390455487872367113056168812990496943458920406382650794656884209032284257748450399719067686010156664485086500184078244358783696803659745365860507822269113477617988541658390715640119076036723560146145256418191555730429
m=bytes_to_long(flag)
c=pow(m,e,n)
# print(c)
assert c==1348180992713820685594359831085361247035354818267759694375727771380213764105201303900290589048476671838784929302557807429509301123621642066527762448168417430350203900517746161928291953862336621873868684964993481406952303460424386080800907869577832154132021624995347121475139439850224598911049824567475034545196149320206620924509546294914370633958171840525667753751028800452370972967842349036965813468093121305475860652163573748880159896028384459277781803606279654121781761535513864212749202340439422384362197321739535686506006254445152569135807838677803047115947240251817017395748631234023225248868640103807357800695487118067385969130665294711887439861169737031598274672286881054564295019370600398079829687943670066246766386800967129670975899437309257181151390273864539453238400821713398980792443187238155205199387468000884390778225928491109565539772444103430764411852162036780535068932010631521096301305200494731040799554079996593223419379540630567412342494359961515157700054387356888773321804429041668331430841954949061238002355270616266853430676140296078177898764114420743905073496118755793091902224563802923183897542996809393707165837427396760691616506592877656939455806776333105152244073459704842848097376929745632888315642056267589901527329593161439752243318158600747713335265681764274061086952626629147275106502354039293870614872849851780761537660716667003562253735923584765118319171207551032289722689929226947535724389015974764265109970513715649126340709399701638880824570967389428525179746112494690443526404899052482884526335312491500994658519105204100875596292743155076199283666094556235485722975240358390560161706163569618302627055238860096406627340558428533728688904747040262153892623865784320600845613247625784683300197845026108394831724602330903266980995146046956218083954561639114586880305451066793209385702886944430548686040360906088479432852330611586273784509957389880104225534635731572089138568407411433675077699382999593384336070450058824669351046095205147266720901917218217564113964074957585348227506587531149811564371155522575778721899999227020238022970334707476977210019

猜测n是由若干个小素数的乘积而来,于是利用Pollard’s ρ algorithm分解这个n

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

def mapx(x):
    x=(x*x+1)%n
    return x

def pollard_rho(x1,x2):
    while 1:
        x1 = mapx(x1)
        x2 = mapx(mapx(x2))
        p = gcd(a - i, n)
        if p != 1:
            return p
n=...

while (n!=1):
    p = pollard_rho(2,2)
    print p
    n = n / p

但其实有前面6个740160703366837大概已经是够了,740160703366837的6次方大概有90位,而如果flag是md5值得话,长度是32+6。由76位十六进制表示,最大由92位十进制表示(显然是不可能的,这个时候已经不是可打印字符了)所以90位作为n应该已经是够了。(再不济就再等一会儿,多出来几个就好了)

exp

from Crypto.Util.number import *
from gmpy2 import *

# flag='XXXXXXXXXX'
e=0x10001
n=3464115689260819392935656139231271022088014497600959975252672820761470484618617542699739764705620767566046150296286140279466041905437740736319886548924058066340624280173573039937440574809212831672936265975209972857747738693288788052694888593629820783280181774594890101819911390468376042288685444703477639361249422054925155575158181408046447773183467474182159096249846479461475003039637685547191529769071424947165685996675043741359728960138725130116665515880652680244470002603320184043266997163009799067135481330853926800023087208636366543210276325733789567957712475079676808820490428973148590780103404729397985019089646026534758042652163974037179260930147000267787012874887703048185189387666199961350969478997330352491403611551096779887936063702892671572230523920277869824082318417366635732798078805070773662305098133013800559413976855639167085996705265872418286939474978058429877355305699191892248323534097124680592084808397263288943661630283254265898940430505371463275516870915261799702701453110383723660477322192658118815861974573497885759332587457883589126213868868281682733732394640188383458580555618181208722172011645063817887462511925363883111475043389367021569982583145912277082528397480756465818166640691294267829613428532584923122279261412957652411789780285394451850006055483598427256129336822790446219260722224551892755568723667049099823707012236618539013908897459508493477299241358343681962043777720375898238069411747593247677719659288861028038609681592049271388766040068274682329498410270047730060645409396168652996740411436504098243588534151795927613112273405281530700440843961363083171583053608594479571127638861391879160062136043924515492933057094406001740725150570943724333872057035272515676895138632004436149126542560186729495087753846670118167613304943153665660470977150177815354160112481310498255965933157902965011317272734556307544837058247794721427834401390455487872367113056168812990496943458920406382650794656884209032284257748450399719067686010156664485086500184078244358783696803659745365860507822269113477617988541658390715640119076036723560146145256418191555730429
# m=bytes_to_long(flag)
# c=pow(m,e,n)
# print(c)
c =1348180992713820685594359831085361247035354818267759694375727771380213764105201303900290589048476671838784929302557807429509301123621642066527762448168417430350203900517746161928291953862336621873868684964993481406952303460424386080800907869577832154132021624995347121475139439850224598911049824567475034545196149320206620924509546294914370633958171840525667753751028800452370972967842349036965813468093121305475860652163573748880159896028384459277781803606279654121781761535513864212749202340439422384362197321739535686506006254445152569135807838677803047115947240251817017395748631234023225248868640103807357800695487118067385969130665294711887439861169737031598274672286881054564295019370600398079829687943670066246766386800967129670975899437309257181151390273864539453238400821713398980792443187238155205199387468000884390778225928491109565539772444103430764411852162036780535068932010631521096301305200494731040799554079996593223419379540630567412342494359961515157700054387356888773321804429041668331430841954949061238002355270616266853430676140296078177898764114420743905073496118755793091902224563802923183897542996809393707165837427396760691616506592877656939455806776333105152244073459704842848097376929745632888315642056267589901527329593161439752243318158600747713335265681764274061086952626629147275106502354039293870614872849851780761537660716667003562253735923584765118319171207551032289722689929226947535724389015974764265109970513715649126340709399701638880824570967389428525179746112494690443526404899052482884526335312491500994658519105204100875596292743155076199283666094556235485722975240358390560161706163569618302627055238860096406627340558428533728688904747040262153892623865784320600845613247625784683300197845026108394831724602330903266980995146046956218083954561639114586880305451066793209385702886944430548686040360906088479432852330611586273784509957389880104225534635731572089138568407411433675077699382999593384336070450058824669351046095205147266720901917218217564113964074957585348227506587531149811564371155522575778721899999227020238022970334707476977210019
def PollardRho_p_1(Q,N):
    a = i = 2
    while 1:
        a = pow(a, i, N)
        d = gcd(a - 1, N)
        if d != 1:
            return d
        i += 1
# print(PollardRho_p_1(1,n))
p = 1043705605371301
n1 = p**7
# print n1
phi = (p-1)*(p**6)
d = invert(e,phi)
# c = c % n1
print(hex(pow(c,d,n1))[2:].decode('hex'))
# flag{G0oDJ0b_S0_SimPle_ChaMd5}

这里相当于我们直接把原题的n给纂改了

首先可以证明 M=C^d^ mod N

首先,看到这里要求m<n,所以这里n_new大于m即可

其次,由于n_new | n,所以 c % n_new == pow(m ,e ,n_new)

推理如下

n = n_new * x
          c = m^e % n
        m^e = k*n + c
        m^e = k*n_new*x + c
m^e % n_new = c % n_new

所以只要新的N满足,m<N, m^e ≡ c (mod N),并且gcd(e,phi(N))=1,即可逆向求出m来。

https://xz.aliyun.com/t/6703#toc-1

http://www.hghhgghhg.top/2019/10/28/UNCTFWP/#simple-rsa


文章作者: hh
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 hh !
  目录