求解一个简单的RSA题目

创建: 2023-09-29 17:11
https://scz.617.cn/python/202309291711.txt

在看雪上看到这篇，应该是某个CTF题，已知条件用Python代码给出来，求flag。

https://bbs.kanxue.com/thread-279050.htm

原题如下

from Crypto.Util.number import *
import gmpy2
from jx2023 import flag, N, E

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e1 = 65537
m = bytes_to_long(flag)
flagenc = pow(m, e1, n)
print("n is %d"%n)
print("flagenc is %d"%flagenc)

e2 = getPrime(122)
d2 = gmpy2.invert(e2,(p-1)*(q-1))

c1 = pow(e2, 17, n)
print("c1 is %d"%c1)
c2 = pow(d2, E, N)
print("N is %d"%N)
print("E is %d"%E)
print("c2 is %d"%c2)

# n is 8783117353228609820060025773720048836109116296720444291318682193328216575376903671782151675801584925066872219021319381163804239505579013818679255656402117567158378369967703317919205364480806143209934093723468591544792794708122025724968669241594029740047941933910596214170603520800531302474255823072859735679699558933009869241259760910402379740926512037606096020308081609477145816657118917642443176163860564823645522254412566891344745856141731910712040298787696382973824645074768059896153817964229975814742137600918515702471008251376697190058997187350022140633621955761877009643524289144711721902192261617574896449017

# flagenc is 1832021020586052459314800741399454951500982061634041208695770794636942946870944684781204845687614819955481692885982545657535952608100558061853098768890990198808258902800083671402999197944855469054517686346352932015639347886120547093778527571008483890754044661117042113616196224634409728684137167049242919543742476300792865668127981523314258326046469003175979484948578219765126696355000799390683333335678236115175267218556919253045561467791607635318317825080003594243366362225620291777807071774013296604063473075790067769213249767073197915283384750139985842145668772180552896467043807903712438253502782564391233381742

# c1 is 7501185876834032332235110133210399479682524972321262801050956129090974843598848916000280794969942298848478394986779571489577405391165372124215072990382219817624500948789393550575823082225944683449240150364401487955484843961943987266467050723988657081468393104862383181698999645914573683498375228946881234015678337769955671069215094086232377038727627179660862997067062391991524231807127953937881102711759932207432989764529075450526104070640765094626829603546052250863300827172150912585791552174463067989228539713261075253602907390439036055716154404417991482262846355144755622306307102084492476950657455416297047328320

# N is 29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767755161686549607991960624754677443327266743771304424298446433734879681913848286620429175461870451099771965936783237191184798864363652633155779478727580408625494617809961465590055999661472563150275608218351797354628429061984878432442357241449134341597647749840966740944318445550768334070331490455379767889443973947

# E is 3527492693

# c2 is 11237333233288323887902003767693284822911839921763421974808265907264411495367936669799604082222415065052099486867383635886650443299459413288200494593477575168578514325691333043832168789236017314435940348619410775859032696755081680003338452277759483862961120696587307757666691557048088894021864124052243936836752825473836552342254367444581003605318145868368417247224184184040226260236268012375524575700053732026218766291274077482132408824236096242385408780811520890742688121731805867574680433796282417791570436991022839930635640379142355212121030479526679958801911687722402447690578345774902440346290388183936888977900

网友「hypersine」评论回复

这个应该还是很好办的

N是一个不安全的大合数，可以用yafu快速分解得到P、Q，因此可以算出E对应的D，从而解密c2得到d2。题目中N的两个因数P、Q靠得太近了，两者之差未超过10000(实际是2214)，所以很容易分解。

c1 = pow(e2, 17, n)，但e2是一个122位的质数，因此e2^17应该有122 * 17 = 2074位，太接近于n的2048位。这里可以暴力破解，因为c1 = pow(e2, 17, n)，所以存在k使得e2^17 == k * n + c1，这个k范围不大，不超过2^(2074 - 2048 + 1) = 2^27，自己写个程序穷举k就好，穷举到k * n + c1是一个完全17次方数就行，然后开17次方得到e2。

现在知道d2、e2那就能分解n了，自己写个程序分解n得到p、q，最后解密flagenc。

他这个回复写得非常清楚，我第一次听说yafu，照着他说的做了一遍，挺有意思。后文假设对RSA算法门儿清，不做科普，直接演示具体实现。

yafu在这里:

https://sourceforge.net/projects/yafu/

1) 用yafu分解N

yafu-x64.exe factor(…)

N   = 29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767755161686549607991960624754677443327266743771304424298446433734879681913848286620429175461870451099771965936783237191184798864363652633155779478727580408625494617809961465590055999661472563150275608218351797354628429061984878432442357241449134341597647749840966740944318445550768334070331490455379767889443973947
P   = 173078108398797693665135881829236075381385640386270681597614075449385160047192826549689858183180936639070064309925929218966667262650552855318783567546131862440848767306600252044834602371191453881522882233745590790067041490962165388372445595736465527512700919336312857203007896777270237470242797091626699715021
Q   = 173078108398797693665135881829236075381385640386270681597614075449385160047192826549689858183180936639070064309925929218966667262650552855318783567546131862440848767306600252044834602371191453881522882233745590790067041490962165388372445595736465527512700919336312857203007896777270237470242797091626699712807

2) 已知PHIN、E求D

PHIN
    = ( P - 1 ) * ( Q - 1 )
    = 29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767754815530332810396573294482913784855115981000023651757083238506728783143528192234776076082154084737898687796654617339326360931029127332050068841160445316361769736112426852389551909992267820767367845172587329863446848927901896508111580496557942868666592724439128068318604039534974779529856549969785584636044546120
E   = 3527492693
D   = pow( E, -1, PHIN )
    = 11714295081028872095829649166462229534600990710051935510446747726812850082248692172993712813876838631530131841002864405509809020642090830057480563098086105449080792559844536414801734203530804966201381422491474684930923968884279519098355698332242744379775874767776071264516751080436520394348871721340176066921420286921422058287034111670045372227822407191894590900146761623610897328261136348388566000514394645573157244495497931592466836405935725526366908335327195113887202308698472178807611689040253147826886972580034858628911446318134969278899776543868656799330072299690972211680722019638416076131152808496762522693477

3) 已知N、D、c2求d2

c2  = 11237333233288323887902003767693284822911839921763421974808265907264411495367936669799604082222415065052099486867383635886650443299459413288200494593477575168578514325691333043832168789236017314435940348619410775859032696755081680003338452277759483862961120696587307757666691557048088894021864124052243936836752825473836552342254367444581003605318145868368417247224184184040226260236268012375524575700053732026218766291274077482132408824236096242385408780811520890742688121731805867574680433796282417791570436991022839930635640379142355212121030479526679958801911687722402447690578345774902440346290388183936888977900
c2  = pow( d2, E, N )
d2  = pow( c2, D, N )
    = 1465609176542763075940181962864772219331485015754212502937973493443861834882896923514247538047873222749277952886635121836117307545036562427772437806854340361074148192771473277727294143006055601401312427467541596180527496770619498342429377442434816909227051361516850883374420088718381665893195779978368015188860126495766884766922749307806795261008469763388207146667293445107027754446987485763318465318384962761520682566768934401101857441607051135056991848789269185392218296823177075051007900064049736104615073193811802036090426977600680928083396357891022205464091444388907654190936465902019121558566966912994707102641

4) 已知n、c1求e2

c1  = pow( e2, 17, n )
e2  = getPrime( 122 )

#
# pip3 install gmpy2
#
import gmpy2

c1  = 7501185876834032332235110133210399479682524972321262801050956129090974843598848916000280794969942298848478394986779571489577405391165372124215072990382219817624500948789393550575823082225944683449240150364401487955484843961943987266467050723988657081468393104862383181698999645914573683498375228946881234015678337769955671069215094086232377038727627179660862997067062391991524231807127953937881102711759932207432989764529075450526104070640765094626829603546052250863300827172150912585791552174463067989228539713261075253602907390439036055716154404417991482262846355144755622306307102084492476950657455416297047328320
n   = 8783117353228609820060025773720048836109116296720444291318682193328216575376903671782151675801584925066872219021319381163804239505579013818679255656402117567158378369967703317919205364480806143209934093723468591544792794708122025724968669241594029740047941933910596214170603520800531302474255823072859735679699558933009869241259760910402379740926512037606096020308081609477145816657118917642443176163860564823645522254412566891344745856141731910712040298787696382973824645074768059896153817964229975814742137600918515702471008251376697190058997187350022140633621955761877009643524289144711721902192261617574896449017

for k in range( 1, 2 ** 26 + 1 ) :
    candidate_e2    = gmpy2.iroot( c1 + k * n, 17 )
    if candidate_e2[1] :
        e2  = int( candidate_e2[0] )
        break

print( e2 )

e2  = 3114339948601620171033737415539895793

5) 已知d2、e2求phin

phin
    = ( p - 1 ) * ( q - 1 )
d2  = gmpy2.invert( e2, ( p - 1 ) * ( q - 1 ) )
    = gmpy2.invert( e2, phin )
    = 1465609176542763075940181962864772219331485015754212502937973493443861834882896923514247538047873222749277952886635121836117307545036562427772437806854340361074148192771473277727294143006055601401312427467541596180527496770619498342429377442434816909227051361516850883374420088718381665893195779978368015188860126495766884766922749307806795261008469763388207146667293445107027754446987485763318465318384962761520682566768934401101857441607051135056991848789269185392218296823177075051007900064049736104615073193811802036090426977600680928083396357891022205464091444388907654190936465902019121558566966912994707102641
phin
    = d2 * e2 - 1
    = 4564405207544251621160138521706538594591784054549538038692015318448340060945594510240871241985116895061629335549085777512188622521933821640819214402972309080980101472729575101642738824863473723503841109828134042994208926579706530001337866814284613148761778236517745008488863858493336754425945969109191308539573113018399570409432491059671276224719844411075725059282216645249950347005535736283487807684943380670169841615202868719656631327521626280108728698099730736885638610021004467364144372676841478360285710205019233880849492164726462754974464448072252673660705407944718572359537230563100649714802350999623686904206314914914672843032286408998095089312

此处我直接求phin，并不需要分解n，不需要知道p、q。

6) 已知phin、e1求d1

e1  = 65537
d1  = pow( e1, -1, phin )
    = 1337625561378990442589706889968960743514805446567258610725526743764878148382151886166381938043641837230170026375264986845584855641183773722226739579527384045795563252593866356442169184892928823925641581936297700989468188105800442730147780185775215223997416921899992532966677133012237754329687325979387647768604623474241758842845422025604567361520504932467466858241516286810054570160189196195441763193265217650354486443712502809553767509595806251976261400059560683775967394663524601373205316411056615856503156235372376000054859796996146355067207290380635135119512764773887497150270412899505791818705371825057181907658063143809622146623710160233416456129

7) 已知n、d1、flagenc求m

n   = 8783117353228609820060025773720048836109116296720444291318682193328216575376903671782151675801584925066872219021319381163804239505579013818679255656402117567158378369967703317919205364480806143209934093723468591544792794708122025724968669241594029740047941933910596214170603520800531302474255823072859735679699558933009869241259760910402379740926512037606096020308081609477145816657118917642443176163860564823645522254412566891344745856141731910712040298787696382973824645074768059896153817964229975814742137600918515702471008251376697190058997187350022140633621955761877009643524289144711721902192261617574896449017
flagenc
    = pow( m, e1, n )
    = 1832021020586052459314800741399454951500982061634041208695770794636942946870944684781204845687614819955481692885982545657535952608100558061853098768890990198808258902800083671402999197944855469054517686346352932015639347886120547093778527571008483890754044661117042113616196224634409728684137167049242919543742476300792865668127981523314258326046469003175979484948578219765126696355000799390683333335678236115175267218556919253045561467791607635318317825080003594243366362225620291777807071774013296604063473075790067769213249767073197915283384750139985842145668772180552896467043807903712438253502782564391233381742
m   = pow( flagenc, d1, n )
    = 13040004482820175097649030762837021876498280967062558556361414290853656516097063334199255421

8) 已知m的long求bytes

m   = bytes_to_long( flag )

import Crypto.Util.number

m   = 13040004482820175097649030762837021876498280967062558556361414290853656516097063334199255421
Crypto.Util.number.long_to_bytes( m )

b'flag{616fa39c8781aa45031e15651228489a}'

9) 完整求解代码

import gmpy2
import Crypto.Util.number

N       = 29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767755161686549607991960624754677443327266743771304424298446433734879681913848286620429175461870451099771965936783237191184798864363652633155779478727580408625494617809961465590055999661472563150275608218351797354628429061984878432442357241449134341597647749840966740944318445550768334070331490455379767889443973947
#
# from yafu
#
P       = 173078108398797693665135881829236075381385640386270681597614075449385160047192826549689858183180936639070064309925929218966667262650552855318783567546131862440848767306600252044834602371191453881522882233745590790067041490962165388372445595736465527512700919336312857203007896777270237470242797091626699715021
Q       = 173078108398797693665135881829236075381385640386270681597614075449385160047192826549689858183180936639070064309925929218966667262650552855318783567546131862440848767306600252044834602371191453881522882233745590790067041490962165388372445595736465527512700919336312857203007896777270237470242797091626699712807
PHIN    = ( P - 1 ) * ( Q - 1 )
E       = 3527492693
D       = pow( E, -1, PHIN )
c2      = 11237333233288323887902003767693284822911839921763421974808265907264411495367936669799604082222415065052099486867383635886650443299459413288200494593477575168578514325691333043832168789236017314435940348619410775859032696755081680003338452277759483862961120696587307757666691557048088894021864124052243936836752825473836552342254367444581003605318145868368417247224184184040226260236268012375524575700053732026218766291274077482132408824236096242385408780811520890742688121731805867574680433796282417791570436991022839930635640379142355212121030479526679958801911687722402447690578345774902440346290388183936888977900
d2      = pow( c2, D, N )
c1      = 7501185876834032332235110133210399479682524972321262801050956129090974843598848916000280794969942298848478394986779571489577405391165372124215072990382219817624500948789393550575823082225944683449240150364401487955484843961943987266467050723988657081468393104862383181698999645914573683498375228946881234015678337769955671069215094086232377038727627179660862997067062391991524231807127953937881102711759932207432989764529075450526104070640765094626829603546052250863300827172150912585791552174463067989228539713261075253602907390439036055716154404417991482262846355144755622306307102084492476950657455416297047328320
n       = 8783117353228609820060025773720048836109116296720444291318682193328216575376903671782151675801584925066872219021319381163804239505579013818679255656402117567158378369967703317919205364480806143209934093723468591544792794708122025724968669241594029740047941933910596214170603520800531302474255823072859735679699558933009869241259760910402379740926512037606096020308081609477145816657118917642443176163860564823645522254412566891344745856141731910712040298787696382973824645074768059896153817964229975814742137600918515702471008251376697190058997187350022140633621955761877009643524289144711721902192261617574896449017

for k in range( 1, 2 ** 26 + 1 ) :
    candidate_e2    = gmpy2.iroot( c1 + k * n, 17 )
    if candidate_e2[1] :
        e2  = int( candidate_e2[0] )
        break

phin    = d2 * e2 - 1
e1      = 65537
d1      = pow( e1, -1, phin )
flagenc = 1832021020586052459314800741399454951500982061634041208695770794636942946870944684781204845687614819955481692885982545657535952608100558061853098768890990198808258902800083671402999197944855469054517686346352932015639347886120547093778527571008483890754044661117042113616196224634409728684137167049242919543742476300792865668127981523314258326046469003175979484948578219765126696355000799390683333335678236115175267218556919253045561467791607635318317825080003594243366362225620291777807071774013296604063473075790067769213249767073197915283384750139985842145668772180552896467043807903712438253502782564391233381742
m       = pow( flagenc, d1, n )
flag    = Crypto.Util.number.long_to_bytes( m )

print( flag )