NEKO

RSA例题

2018/02/09

windows下openssl链接:
https://pan.baidu.com/s/1nvstpB7 密码:00l0

最基础的RSA

jarvis mediumRSA
链接:https://pan.baidu.com/s/1bAa1yu 密码:7281

利用openssl工具

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.PublicKey import RSA

def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y

pub=RSA.importKey(open("C:\\Users\\kuraraneko\\Desktop\\pubkey.pem").read())
n=pub.n #n
e=pub.e #e
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239 #p,q用工具或网站http://factordb.com/求出
print(egcd(e,(p-1)*(q-1)))#求d
d=10866948760844599168252082612378495977388271279679231539839049698621994994673

private=RSA.construct((n,e,d)).exportKey().decode()#生成密钥

with open('private.pem','w') as f:#生成密钥文件
f.write(private)

上述代码用于生成密钥文件
将生成的密钥文件和密文文件放到openssl的bin文件夹内
运行openssl.exe
rsautl -decrypt -in flag.enc -inkey private.pem -out flag.dec
生成flag.dec.

直接用脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.PublicKey import RSA
import codecs
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y

pub=RSA.importKey(open("C:\\Users\\kuraraneko\\Desktop\\pubkey.pem").read())
n=pub.n #n
e=pub.e #e
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239 #p,q用工具或网站http://factordb.com/
print(egcd(e,(p-1)*(q-1)))#求d
d=10866948760844599168252082612378495977388271279679231539839049698621994994673

c=int(codecs.encode(open('C:\\Users\\kuraraneko\\Desktop\\flag.enc','rb').read(),'hex_codec'),16)#将密文还原成16进制

m=hex(pow(c,d,n))[2:]#明文的16进制

if(len(m)%2==1):#16进制解密要求密文不能为奇数,在头部填0即可
m='0'+m

print(codecs.decode(m,'hex_codec'))#输出明文

(但输出结果前面一堆乱七八糟的东西没搞清是什么)

Rabin,e=2

Jarvis hardRSA
链接:https://pan.baidu.com/s/1bpbcTmn 密码:07c3
此题为Rabin加密算法http://blog.sina.com.cn/s/blog_64370f500100lhqz.html,用中国剩余定理求解。
求出e为2,发现和φ(n)不互素,判断是Rabin加密(雾,此处猜测)
由c≡m2mod n⇒mp≡√cmod p和mq≡√cmod q.根据c是模p的充分必要条件c(p-1)/2≡1 mod p⇒mp≡c(p+1)/4mod p 和mq≡c(q+1)/4mod q.下面应用中国剩余定理求解
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.PublicKey import RSA
import gmpy2
import codecs
#16进制解密
def run(m):
m=hex(m)[2:]
if len(m)%2==1:
m='0'+m
print(codecs.decode(m,'hex_codec'))

pub=RSA.importKey(open("C:\\Users\\kuraraneko\\Desktop\\pubkey.pem").read())
n=pub.n
e=pub.e
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
c=int(codecs.encode(open('C:\\Users\\kuraraneko\\Desktop\\flag.enc','rb').read(),'hex_codec'),16)

#下面是中国剩余定理求出4个解,其中必有一解为明文
M1=q
M2=p
M_1=gmpy2.invert(M1,M2)#M1的逆
M_2=gmpy2.invert(M2,M1)#M2的逆

a1=pow(c,(p+1)//4,p)
a2=pow(c,(q+1)//4,q)

x1=(a1*M1*M_1+a2*M2*M_2)%n
x2=(a1*M1*M_1-a2*M2*M_2)%n
x3=n-x1
x4=n-x2

run(x1)
run(x2)
run(x3)
run(x4)

两个有公因子的n

如果给了两个分解不出来的n,但他们两个有公因数,那么这个公因数就是q,就能求出p1和p2了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import codecs
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y
def gcd(a,b):
if b==0:
return a
else:
return gcd(b,a%b)
n1=18263905851567773440446838695766097054252159817375942220432646590577605535001102705343902666589196712209131000424743250389209817386462242094905266578654348699073317748484503797678183012090375022172700739930717847219593096973008967105897376613550069563133191469825170677181620033104899474861544205137427444083416158205978241738189319430709815369614381957092634679663073529915011800029514945250518582469896694087993939399022631417819581576165949892810231692555896017395242464371112868608767990194529216988324463096379599680586615395063392235579858007086701467453321499203151052012397135583838714605379937464734426058203
n2=16950818485762084795193828768953323876388698051219062552262211712110062204954209462306530235388240321343855913666709750794055992220667151032536667937762799073479211925880106492191394846770654371623007051501782616639485222511300384032213459590408774089539345780246233268007572472533774114330568959631749390932599046733958624832563792588926026242133422467392689761450865841250657088270966077177543599222351800102728976845282712937106806976091210265560260177661816495238213887970556095475226646345568545415814035277834069152282458515989066082948101449829801979628039212597995349260855092279108102204886522855975419755219
c1=16274856857661787783089247952446020386301296490309822420733326939579521159181274564159881569720941773424141684911497028248685883897404191432880449283023146073930043226457053587418510143359803678057561120305169670182063356905346792409675959838228170818653485027257264058185367161472527834396804757004371950225319647551718070122431050642186905590213972232201966833949845104276760241004644118590467546314025479853604227295841523010158969804175921406672115195772809154058842429049437301440993794765038365224477229612151404063782303298937771968709567577283974551173044172598459482531433545960749147311254443274915272200560
c2=9946468920119252596998213656931348575944985856629754429330209121534145245119561878513995066589817036899299533093751237144960328759208855732474853794711347203865156360078772132790431594811682581926722057546683437873159107885652842304739962490836998123152090675606004046425633751397173768982047965656687448847259753864171018963561303276197312504508548802813909914926514763930195218396740593919987596462341469781868335025782329081775818968846955110510048099746584203570892950955431181639182647914240604278151551608856971433512600491550082244566145491335738112881861092354219766862656988674738232228115996349755982641605
e1=1804229351
e2=17249876309

q=gcd(n1,n2)
p1=n1//q
p2=n2//q

d1=egcd(e1,(p1-1)*(q-1))[1]
d2=egcd(e2,(p2-1)*(q-1))[1]

while d1<0:
d1+=(p1-1)*(q-1)
while d2<0:
d2+=(p2-1)*(q-1)
m2=hex(pow(c2,d2,n2))[2:]
m1=hex(pow(c1,d1,n1))[2:]
if(len(m2)%2==1):
m2='0'+m2
if (len(m1) % 2 == 1):
m1 = '0' + m1
print(codecs.decode(m1,'hex_codec'))
print(codecs.decode(m2,'hex_codec'))

2个e,一个n的共模攻击

Jarvis veryhardRSA
链接:https://pan.baidu.com/s/1hsamKV6 密码:aiud

当n到达2048或4096位时,无法分解出p,q,此时需要其他解法。
由加密脚本知明文被分别用e1,e2加密成2份密文,且n相同,属于共模攻击。
e1,e2互素,则存在s1,s2使s1e1+s2e2=1
则可以将c1≡me1mod n和c2≡me2mod n转化为
m≡c1s1*c2s2mod n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import codecs
import gmpy2
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y

n=0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
c1=int(codecs.encode(open("C:\\Users\\kuraraneko\\Desktop\\flag.enc1",'rb').read(),'hex_codec'),16)
c2=int(codecs.encode(open("C:\\Users\\kuraraneko\\Desktop\\flag.enc2",'rb').read(),'hex_codec'),16)
e1=17
e2=65537
s1=egcd(e1,e2)[1]
s2=egcd(e1,e2)[2]
#此处判断s1和s2是否小于0,因为pow()函数里s1和s2不能为负,
if(s1<0):
s1=-s1
c1=gmpy2.invert(c1,n)#若s1为负,s1取正,c1取逆
if(s2<0):
s2=-s2
c2=gmpy2.invert(c2,n)
m=codecs.decode(hex(pow(c1,s1,n)*pow(c2,s2,n)%n)[2:],'hex_codec')
print(m)

e=3,低指数攻击

Jarvis Extremely hard RSA
发现e=3
属于低指数攻击
c≡m3 mod n
则m=(c+kn)1/3 mod n k=0,1,2….
需要用到gmpy库的一个函数root,python3貌似只支持gmpy2,但gmpy2里的root改了(应该有其他方法替代,我就不想探索了),只好用kali里的python2.7去跑脚本了(跑到k=118719488的时候跑出结果)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy

c=545666236924510340010249577709750283325731706774285241719627277546281629429734726717293022303311450772262647904537263500252284243393598944613964442974546950954108203106726282255676706429218187217515454665602130999856741523362906632677988245886500953095201122016935004088287862399317170828388632964668574391252399791901016522260191839164586088073933168096433230663402492577707149742261018318811473591856287943664733276898405984282679026758294364432874973387827086342720762945025346962005339728347282927842299962927871005260338747371451546554777112213044710533502191671159066680035742327279159127279685106716107705888068319962657817786581813767331740609788885735155741039564703781141646102609725965697004923161084032164730408824475517786576979990372940555488021025837456038491436690372760376483602299268887032528766383572923258228355911069631275397149328319966792315903921085816103476508992023873616148326626245855060470294978538631677232260545724075728912626994884533001056079733734460116442499311813113038763837974777469202302071221647473459505245546281400799833123812072606012604323510933244028733287443734697557314202167934768160824072400916728008549350662843995750077421616789178835625661267955774815287104291379928002318796086248

n=721059527572145959497866070657244746540818298735241721382435892767279354577831824618770455583435147844630635953460258329387406192598509097375098935299515255208445013180388186216473913754107215551156731413550416051385656895153798495423962750773689964815342291306243827028882267935999927349370340823239030087548468521168519725061290069094595524921012137038227208900579645041589141405674545883465785472925889948455146449614776287566375730215127615312001651111977914327170496695481547965108836595145998046638495232893568434202438172004892803105333017726958632541897741726563336871452837359564555756166187509015523771005760534037559648199915268764998183410394036820824721644946933656264441126738697663216138624571035323231711566263476403936148535644088575960271071967700560360448191493328793704136810376879662623765917690163480410089565377528947433177653458111431603202302962218312038109342064899388130688144810901340648989107010954279327738671710906115976561154622625847780945535284376248111949506936128229494332806622251145622565895781480383025403043645862516504771643210000415216199272423542871886181906457361118669629044165861299560814450960273479900717138570739601887771447529543568822851100841225147694940195217298482866496536787241
e=3
i=0
while 1:
if gmpy.root((c+i*n),e)[1]==1:
print "yes"
m=gmpy.root((c+i*n),e)[0]
print m
print i
break
i=i+1

结果转成字符串即可

n&e都很大

http://www.shiyanbar.com/ctf/730
当n和e都特别大时可以用github上的脚本:https://github.com/pablocelayes/rsa-wiener-attack
RSAwienerHacker.py可以求出d:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
'''
Created on Dec 14, 2011

@author: pablocelayes
'''

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
'''
Finds d knowing (e,n)
applying the Wiener continued fraction attack
'''
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)

for (k,d) in convergents:

#check if d is actually the key
if k!=0 and (e*d-1)%k == 0:
phi = (e*d-1)//k
s = n - phi + 1
# check if the equation x^2 - s*x + n = 0
# has integer roots
discr = s*s - 4*n
if(discr>=0):
t = Arithmetic.is_perfect_square(discr)
if t!=-1 and (s+t)%2==0:
print("Hacked!")
return d

# TEST functions

def test_hack_RSA():
print("Testing Wiener Attack")
times = 5

while(times>0):
e,n,d = RSAvulnerableKeyGenerator.generateKeys(1024)
print("(e,n) is (", e, ", ", n, ")")
print("d = ", d)

hacked_d = hack_RSA(e, n)

if d == hacked_d:
print("Hack WORKED!")
else:
print("Hack FAILED")

print("d = ", d, ", hacked_d = ", hacked_d)
print("-------------------------")
times -= 1

if __name__ == "__main__":
#test_is_perfect_square()
#print("-------------------------")
#test_hack_RSA()
d=hack_RSA(30749686305802061816334591167284030734478031427751495527922388099381921172620569310945418007467306454160014597828390709770861577479329793948103408489494025272834473555854835044153374978554414416305012267643957838998648651100705446875979573675767605387333733876537528353237076626094553367977134079292593746416875606876735717905892280664538346000950343671655257046364067221469807138232820446015769882472160551840052921930357988334306659120253114790638496480092361951536576427295789429197483597859657977832368912534761100269065509351345050758943674651053419982561094432258103614830448382949765459939698951824447818497599,109966163992903243770643456296093759130737510333736483352345488643432614201030629970207047930115652268531222079508230987041869779760776072105738457123387124961036111210544028669181361694095594938869077306417325203381820822917059651429857093388618818437282624857927551285811542685269229705594166370426152128895901914709902037365652575730201897361139518816164746228733410283595236405985958414491372301878718635708605256444921222945267625853091126691358833453283744166617463257821375566155675868452032401961727814314481343467702299949407935602389342183536222842556906657001984320973035314726867840698884052182976760066141)
print(d)

改下脚本,控制台下运行即可。
求出d后直接就能求明文了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.PublicKey import RSA

import codecs
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y

pub=RSA.importKey(open("C:\\Users\\kuraraneko\\Desktop\\warmup.pub").read())
n=pub.n #n
e=pub.e #e

d=4221909016509078129201801236879446760697885220928506696150646938237440992746683409881141451831939190609743447676525325543963362353923989076199470515758399
c=0x1e04304936215de8e21965cfca9c245b1a8f38339875d36779c0f123c475bc24d5eef50e7d9ff5830e80c62e8083ec55f27456c80b0ab26546b9aeb8af30e82b650690a2ed7ea407dcd094ab9c9d3d25a93b2140dcebae1814610302896e67f3ae37d108cd029fae6362ea7ac1168974c1a747ec9173799e1107e7a56d783660418ebdf6898d7037cea25867093216c2c702ef3eef71f694a6063f5f0f1179c8a2afe9898ae8dec5bb393cdffa3a52a297cd96d1ea602309ecf47cd009829b44ed3100cf6194510c53c25ca7435f60ce5f4f614cdd2c63756093b848a70aade002d6bc8f316c9e5503f32d39a56193d1d92b697b48f5aa43417631846824b5e86

m=hex(pow(c,d,n))[2:]#明文的16进制

if(len(m)%2==1):#16进制解密要求密文不能为奇数,在头部填0即可
m='0'+m

print(codecs.decode(m,'hex_codec'))#输出明文

e和ψ(n)不互素

attachments:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from secret import flag

modulus_list = [143786356117385195355522728814418684024129402954309769186869633376407480449846714776247533950484109173163811708549269029920405450237443197994941951104068001708682945191370596050916441792714228818475059839352105948003874426539429621408867171203559281132589926504992702401428910240117807627890055235377744541913L,
73988726804584255779346831019194873108586184186524793132656027600961771331094234332693404730437468912329694216269372797532334390363774803642809945268154324370355113538927414351037561899998734391507272602074924837440885467211134022878597523920836541794820777951492188067045604789153534513271406458984968338509L,
95666403279611361071535593067846981517930129087906362381453835849857496766736720885263927273295086034390557353492037703154353541274448884795437287235560639118986397838850340017834752502157881329960725771502503917735194236743345777337851076649842634506339513864285786698870866229339372558162315435127197444193L,
119235191922699211973494433973985286182951917872084464216722572875998345005104112625024274855529546680909781406076412741844254205002739352725207590519921992295941563460138887173402493503653397592300336588721082590464192875253265214253650991510709511154297580284525736720396804660126786258245028204861220690641L]

e = [114194L, 130478L, 122694L, 79874L]
message = bytes_to_long(flag)
ciphertext = [pow(message, e[i], modulus_list[i]) for i in range(4)]
ciphertext = [long_to_bytes(ciphertext[i]) for i in range(4)]
ciphertext = [ciphertext[i].encode("hex") for i in range(4)]

obj1 = open("ciphertext.txt",'w')
obj1.write(str(ciphertext))

还有ciphertext.txt.

先是找到有公因子的一对n。
找到后发现(e,ψ(n))=2

1
2
3
4
5
6
由  e*d=2 mod ψ(n)
=> e*(d/2) =1 mod ψ(n)

由 c^d = m mod n
=> c^(d/2) = m mod n
=> c^d = m^2 mod n

所以求出m^2 后开下平方就行了。
exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import gmpy2
from Crypto.Util.number import *
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y
def exploit():
modulus_list = [143786356117385195355522728814418684024129402954309769186869633376407480449846714776247533950484109173163811708549269029920405450237443197994941951104068001708682945191370596050916441792714228818475059839352105948003874426539429621408867171203559281132589926504992702401428910240117807627890055235377744541913L,
73988726804584255779346831019194873108586184186524793132656027600961771331094234332693404730437468912329694216269372797532334390363774803642809945268154324370355113538927414351037561899998734391507272602074924837440885467211134022878597523920836541794820777951492188067045604789153534513271406458984968338509L,
95666403279611361071535593067846981517930129087906362381453835849857496766736720885263927273295086034390557353492037703154353541274448884795437287235560639118986397838850340017834752502157881329960725771502503917735194236743345777337851076649842634506339513864285786698870866229339372558162315435127197444193L,
119235191922699211973494433973985286182951917872084464216722572875998345005104112625024274855529546680909781406076412741844254205002739352725207590519921992295941563460138887173402493503653397592300336588721082590464192875253265214253650991510709511154297580284525736720396804660126786258245028204861220690641L]
e = [114194L, 130478L, 122694L, 79874L]
c=['0c55bc89e3773d8e378121eced4f9300103a8696bc3f9a1542c5b1539442ca5de03a40ad564ab5c2e764b2f946058ec220abf20afc271896ff4ca1f4a2dd227405f221de51e097d6b9f270c4561cd25596e96efd7de1a0e65d37cbf6a73c62a7e323f48450b9dc75e3e738ec1c7e1ae9fc808da8c476e72aea9155125b815653', '67caf9720696b1d0d589f053bb00ebe42b7b26fed38acb4012d29ddc55cd53da8398f042f22987453bdfa2ee8fb35ff121f81e96137995a8ca4daa1fbd88af3fd29138853d5fe98f9b983f67d6fd2b7ff6650228479ca6cac1d49572d28f01a659892b0799ca8202031a1ab37656331470d3ea5f221cc948636c1027bb6dd10f', '65e1cffe93ebccd49a9d14c01b2583a5d5e3140bf38a768833aa494d2d879a2934dbc10a843ec834e9ade286824e68879cb09ac9bd67afd7318b74955e9aa66df5740e6dcc26ccc787f0b415bdc80c6468421c4d4ce615fa3d25350940c5004e9b480c86faebc31e809725a9a868c94e9f1eaac567b4672fe395a7b205775883', '23108bb7f35d12b69bbe5e649ff47fb802b68f22045c484805040a3f4f8669acde8b04daba71190154aef4be9a0eafdebe31b5f96e8b01b5085f502fc0e12a326cc4d867f5317ac12bf16607765d99708934c35c4b9404747f69988ea7d3f4d8022cdfd81ada3aedb22d110db4aa81038aa151c9a4dbb5651757dc092b70b84d']
for i in modulus_list:
for j in modulus_list:
if i!=j and gmpy2.gcd(i,j)!=1:
n1=i
n2=j
q1=q2=gmpy2.gcd(i,j)
p1=n1/q1
p2=n2/q2
e1=e[modulus_list.index(n1)]
e2=e[modulus_list.index(n2)]
c1=int(c[modulus_list.index(n1)],16)
c2=int(c[modulus_list.index(n2)],16)

return n1,n2,q1,q2,p1,p2,e1,e2,c1,c2
n1,n2,q1,q2,p1,p2,e1,e2,c1,c2=exploit()

d1=egcd(e1,(p1-1)*(q1-1))[1]

m=pow(c1,d1,n1)
m=gmpy2.iroot(m,2)[0]
print long_to_bytes(m)

非套路的rsa-1

bsides的一道题,不是很难但感觉挺很有新意的。
encrypted:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import gmpy2

p=getPrime(1024)
q=getPrime(1024)

N1=p*q
e=65537L

flag=open('flag.txt').read()
f1=bytes_to_long(flag[:len(flag)/2])
f2=bytes_to_long(flag[len(flag)/2:])

if p>q:
x=p%q
else:
x=q%p

r=gmpy2.next_prime(x+f1)
s=gmpy2.next_prime(r)

for i in range(50):
s=gmpy2.next_prime(s)

N2=r*s

enc_f1=pow(f2,e,N1)
enc_f2=pow(f1,e,N2)

pub_key = RSA.construct((int(N1), e))
pub_key2 = RSA.construct((int(N2), e))
open("publickey1.pem","w").write(pub_key.exportKey("PEM"))
open("publickey2.pem","w").write(pub_key2.exportKey("PEM"))

file1 = open("ciphertext1.txt", 'w')
file2 = open("ciphertext2.txt", 'w')
file1.write(str(enc_f1))
file2.write(str(enc_f2))

此外给了2个公钥文件和2个密文。
注意到:

1
2
3
4
5
6
s=gmpy2.next_prime(r)

for i in range(50):
s=gmpy2.next_prime(s)

N2=r*s

虽然经过了51次循环,但其实s和r之前的差还是很小的,这种情况用yafu解一下N2就出来了,可以得到明文f1。


1
r=gmpy2.next_prime(x+f1)

可以推出

1
x=r-f1-w

w属于可爆破范围。

注意到:

1
2
3
4
if p>q:
x=p%q
else:
x=q%p

假设p>q,因为p,q都是1024位,那么x=p%q等价于x=p-q.

现在得到方程组:

1
2
x=p-q
N1=p*q

x^2+4N1=(p+q)
得到

1
(x^2+4N1)^(1/2)=p+q

由于p+q一定为整数,那么就可以爆破出x,进而解出p和q了.
exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy2
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y

flag=''
pub1=RSA.importKey(open("./publickey1.pem").read())
pub2=RSA.importKey(open("./publickey2.pem").read())
n1=pub1.n
e1=pub1.e
n2=pub2.n
e2=pub2.e
c1=9487341811162828852624490333351729972267613161732702520360352607861401987201312103486995348470220908634467468849530123630733494221072022235462597033186714521759666140232970127208173677641698566801132239812856250932681591031073089224810061516865884354315145934044864851489540980292173024996801525629642199750983493941177227822694735281265429662933894875414018994886084399944107873262803718093774820641369618367718492818757774725477934957021552170853545114222052387655020014050439857140746072154265813708499993547896725495119277435663141247838718756489986282983071978632225188148268715713168868025674730763137176945862
c2=720336303815976435960535386565298253917301410143042455414749354278998354711417859713176558018723953167245949341553676677606186844692745131879730233112804103895056237414988941251562952580874379924021140152820592041519436003547905142989374910253868640294361777968506003000509649929691016350483107377073043489660346750211371485068306084103641837994518138152566374479300028404788777718238937329263008132850286656496357294026208591137553112829472346321602199854893500327419190240478598316514987190292957831904729491732321821010395230567921598353908303162037876529987366642090956212558413788635816629533331854265110439562
s = 34943163978391913490204654305109869295969157488468663432729901906249731064212045067569040629711809459931937454973699790926994065010763031849790674858604991174643121365163423162775788932612813130638817575733125991407600361279872314029744419625686687155697263385630614699236173841815497058736893083857633953613
r = 34943163978391913490204654305109869295969157488468663432729901906249731064212045067569040629711809459931937454973699790926994065010763031849790674858604991174643121365163423162775788932612813130638817575733125991407600361279872314029744419625686687155697263385630614699236173841815497058736893083857633916533
d2=gmpy2.invert(e2,(r-1)*(s-1))

m1=long_to_bytes(pow(c2,d2,n2))
flag+=m1

f1=bytes_to_long(m1)


for i in range(1000):
x = r - f1-i
sum=pow(x,2)+4*n1
if gmpy2.iroot(sum,2)[1]==True:
num1=gmpy2.iroot(sum,2)[0]
num2=r-f1-i
break
p1=(num1+num2)/2
q1=n1/p1

d1=gmpy2.invert(e1,(p1-1)*(q1-1))
m2=long_to_bytes(pow(c1,d1,n1))

flag+=m2
print flag

参考:
http://blog.csdn.net/veritas501/article/details/55257957
http://blog.sina.com.cn/s/blog_64370f500100lhqz.html

更多链接:
https://err0rzz.github.io/2017/11/14/CTF%E4%B8%ADRSA%E5%A5%97%E8%B7%AF/
https://github.com/0x01f/crypto_repo/blob/master/QWB_nextrsa/writeup.md

原文作者: n3k0

发表日期: February 9th 2018, 4:36:34

发出嘶吼: 没有魔夜2玩我要死了

CATALOG
  1. 1. 最基础的RSA
    1. 1.1. 利用openssl工具
    2. 1.2. 直接用脚本
  2. 2. Rabin,e=2
  3. 3. 两个有公因子的n
  4. 4. 2个e,一个n的共模攻击
  5. 5. e=3,低指数攻击
  6. 6. n&e都很大
  7. 7. e和ψ(n)不互素
  8. 8. 非套路的rsa-1