题目摘要

赛题名称: RSA 加密体制破译

赛题描述

RSA密码算法是使用最为广泛的公钥密码体制。该体制简单且易于实现,只需要选择5个参数即可(两个素数𝑝𝑝𝑞𝑞、模数𝑁=𝑝𝑞𝑁=𝑝𝑞、加密指数𝑒𝑒和解密指数𝑑𝑑。设𝑚为待加密消息RSA体制破译相当于已知𝑚𝑒𝑚^𝑒 modmod 𝑁𝑁能否还原𝑚的数论问题。目前模数规模为1024比特的RSA算法一般情况下是安全的,但是如果参数选取不当,同样存在被破译的可能。

有人制作了一个RSA加解密软件采用的RSA体制的参数特点描述见密码背景部分)。已知该软件发送某个明文的所有参数和加密过程的全部数据(加密案例文件详见附件3-1。Alice使用该软件发送了一个通关密语,且所有加密数据已经被截获,请问能否仅从加密数据恢复该通关密语及RSA体制参数?如能请给出原文和参数,如不能请给出已恢复部分并说明剩余部分不能恢复的理由?

加密过程

  1. 原始明文
1
This is a test of my RSA system.

Frame0

1
A5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100019726C82FED1E6CD58DE825528AE5634653C9921CAE02AFF7325F20D6E7085B7C8E3DC78D7518A78A8BC7D07E2E837083324579510851827794AE3D1FB9BAB360B1413A8F171A83804CEA73DFBC1248139BB27EB7D5BAD724AD8B08F51888B90562AF950725ACDD698F817AE62746CEA09479A191A6552B0116830355C68D0F61

Frame1

1
A5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD90000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001789018FDB800AD59A54D27A77F280515BB3BFAB1CD75CB0A255A116D4A44849459FD887FF091F87C0B3E6305F019700E4E4CB3646D1DF276DFB87C4F64245F77377508EC6A796236F8ABB125023D3F4B898F55E3342D0A852193AF890990EA82F12FC85917BF132F2A58C449648D6E934B24E80307AB092DB18110D77BBA0F8E

Frame2

1
BA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B5119530000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001534810A0D1B2F6FB257DC3BBDA30AA76157B89038E52D05EE1E5DB06C2D79FAE84892950EF5FD8ADC4F241C3741AD7C97002902C8CA4D96574F28EDCEF3BEF15303335FA8D250102B4EE77E3B405E30F6B81E92403A8881285B65F29668E05B9CD6AC44FC1CD193CF4A5811A2649BE0EDEFBA91FA7143266286C5EC6EE8077D6

Frame3

1
BA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B51195300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100018805A937DABF25FE760F9F398C7D9D5955EF7468FEC89119F8DD69874FB009AB2C424BD6A8E85401C4CD130B48D0490586DFBD81C8154EDCEFC3AFC4F80338432197EB059AB54CF109B231416FB65E2F9BE4F01D455E25486D8E155A5874E8A910E8C65F73ACD953D316B35A148D5AC5834D86F66AD415EBA38AD3908B32780A

2.过程及参数

RSA 密码算法描述如下,包含体制参数选取和加解密过程。

1)RSA 体制参数选取

​ Step1.每个使用者,任意选择两个大素数𝑝𝑝𝑞𝑞,并求出其乘积𝑁=𝑝𝑞𝑁=𝑝𝑞

​ Step2.令𝜑(𝑁)=(𝑝−1)(𝑞−1)选择整数𝑒𝑒,使得GCD(𝑒,𝜑(𝑁))=1,并求出𝑒𝑒模 𝜑(𝑁)的逆元𝑑𝑑,即𝑒𝑑≡1 mod (𝜑(𝑁))

​ Step3.将数对(𝑒,𝑁)(𝑒,𝑁)公布为公钥,𝑑𝑑保存为私钥。

2)加解密过程

​ Bob欲传递明文𝑚给 Alice,则Bob首先由公开途径找出 Alice 的公钥 (𝑒,𝑁)(𝑒,𝑁),Bob 计算加密的信息𝑐𝑐为:𝑐𝑚𝑒𝑐 ≡ 𝑚^𝑒 modmod 𝑁𝑁

​ Bob 将密文𝑐𝑐传送给 Alice。 随后 Alice 利用自己的私钥𝑑𝑑解密:
𝑐e(𝑚𝑒)𝑑𝑚𝑒𝑑𝑚 mod 𝑁𝑐^e ≡ (𝑚^𝑒)^𝑑 ≡ 𝑚^{𝑒𝑑}≡ 𝑚\space mod\space 𝑁

Alice 使用的 RSA 密码体制有以下事项需要说明:

​ 1)模数𝑁=𝑝𝑞规模为1024比特,其中𝑝,𝑞为素数;

​ 2)素数𝑝由某一随机数发生器生成;

​ 3)素数𝑞可以随机选择,也可以由2)中的随机数发生器产生;

​ 4)可以对文本加密,每次加密最多8个明文字符

​ 5)明文超过8个字符时,对明文分片,每个分片不超过8个字符

​ 6)分片==明文填充为512比特消息后再进行加密,填充规则为高位添加64比特标志位,随后加上32比特通信序号==,再添加若干个0,最后64比特为明文分片字符对应的ASCII码(**注:填充方式参见加密案例,但注意每次通信的标志位可能变化)

​ 7)分片加密后发送一个加密帧数据,帧数据文件名称为FrameXX,其中XX表示接收序号,该序号不一定等于通信序号;

​ 8)帧数据的数据格式如下,其中数据都是16进制表示,结构如下==1024bit模数N | 1024bit加密指数e | 1024bit密文== me mod Nm^e\space mod \space N

​ 9)由于Alice初次使用该软件,可能会重复发送某一明文分片。

符号说明: n 模数、p 素数、q素数、e加密指数、d 解密指数、m 明文分片、c 密文分片、“0X”十六进制数据表示

明文: "This is a test of my RSA system."将其分割为4个8字符长度消息(注意:空格也是一个字符)

1
2
3
4
5
This is8字符对应的ASCII为		54	68	69	73	20	69	73	20	将其视为64比特整数为==>	0X5468697320697320
a test o 该8字符对应的ASCII为 61 20 74 65 73 74 20 6F 将其视为64比特整数为==> 0X612074657374206F
f my RSA 该8字符对应的ASCII为 66 20 6D 79 20 52 53 41 将其视为64比特整数为==> 0X66206D7920525341
system. 该8字符对应的ASCII为 20 73 79 73 74 65 6D 2E 将其视为64比特整数为==> 0X2073797374656D2E

选择前缀为0xFFFFFFFFFFFFFFFF,再添加通信序号和若干个0,最终填充后的4条消息依次为

1
2
3
4
5
0xFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005468697320697320
0xFFFFFFFFFFFFFFFF000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000612074657374206F
0xFFFFFFFFFFFFFFFF00000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000066206D7920525341
0xFFFFFFFFFFFFFFFF0000000300000000000000000000000000000000000000000000000000000000000000000000000000000000000000002073797374656D2E

第0个明文分片参数及加密结果

1
2
3
4
5
6
7
8
p= 0XC60C5F1B997ED8A5E340023F33D2E269CFB423A3CF66B46D3F686747403A92B1265CB12B9A4E0135B890254F31A2C3F96A0427B39A36DEFDEEB85C57A80A9641
q= 0XD684DA331AB6157DA338B6D7B08AB4C1B72C29BB7F9EF445466056DFDBF29809C4D4A2435986A40DE688AFE7CC5A5C519F7C63CB486E44D523B0E1EF21C22199
n= 0XA5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD9
e= 0X10001
d= 0X4C5340AAECBB1BB5BE74F09F9D9D45BF4583ECF38334D75FF44834A4809CEC4D57071C9374DC1EC3BF574634B0D30DC7EF1D04E0131EAA2F5C4B8364D6A95676C23F9DADAAB4523A6F5B22EC5904650BF558B3FDF39E3B13EA4771FB1D297DA03C8E1E82F4759B31A9492C56E4D1C690A66ECEC430849A17C027D1A7480F1E01
m= 0XFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005468697320697320
c= 0X9726C82FED1E6CD58DE825528AE5634653C9921CAE02AFF7325F20D6E7085B7C8E3DC78D7518A78A8BC7D07E2E837083324579510851827794AE3D1FB9BAB360B1413A8F171A83804CEA73DFBC1248139BB27EB7D5BAD724AD8B08F51888B90562AF950725ACDD698F817AE62746CEA09479A191A6552B0116830355C68D0F61

第1个明文分片参数及加密结果

1
2
3
4
5
6
7
8
p= 0XC60C5F1B997ED8A5E340023F33D2E269CFB423A3CF66B46D3F686747403A92B1265CB12B9A4E0135B890254F31A2C3F96A0427B39A36DEFDEEB85C57A80A9641
q= 0XD684DA331AB6157DA338B6D7B08AB4C1B72C29BB7F9EF445466056DFDBF29809C4D4A2435986A40DE688AFE7CC5A5C519F7C63CB486E44D523B0E1EF21C22199
n= 0XA5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD9
e= 0X10001
d= 0X4C5340AAECBB1BB5BE74F09F9D9D45BF4583ECF38334D75FF44834A4809CEC4D57071C9374DC1EC3BF574634B0D30DC7EF1D04E0131EAA2F5C4B8364D6A95676C23F9DADAAB4523A6F5B22EC5904650BF558B3FDF39E3B13EA4771FB1D297DA03C8E1E82F4759B31A9492C56E4D1C690A66ECEC430849A17C027D1A7480F1E01
m= 0XFFFFFFFFFFFFFFFF000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000612074657374206F
c= 0X789018FDB800AD59A54D27A77F280515BB3BFAB1CD75CB0A255A116D4A44849459FD887FF091F87C0B3E6305F019700E4E4CB3646D1DF276DFB87C4F64245F77377508EC6A796236F8ABB125023D3F4B898F55E3342D0A852193AF890990EA82F12FC85917BF132F2A58C449648D6E934B24E80307AB092DB18110D77BBA0F8E

第2个明文分片参数及加密结果

1
2
3
4
5
6
7
8
p= 0XD502B3D96C648A9393966CDD37188D37576AA221290C861B347ED7A57640993F7ED2D16992B42AA3CA66936D3268DE47EB3A61B1495C982BF54EC0350B907C4F3CA272F9ED04EEB355367DFDA1B89357130A25411DAC4E3B8A1EECC594E0435F0E7298897B54D6C334062C8D8508AC67CEDAECD1A5FCA84BF2EE5D
q= 0XE00258CB6F
n= 0XBA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B511953
e= 0X10001
d= 0X524EB244F1CE59966C273B91AC40B620CFB55BA2030E871F01147E11844888B6224C5D4DE14551DFDB93C984DAD94A4359643B247ED6CC7DE774A15440D525E26FE9CF4328DBEF2AAA8E402922596F1C23B8F117C018870777434C93B68F1028295DFA6E69FA8E00FFC4EFEF747C348EDBC99C529B7C3B649813647FF90A8261
m= 0XFFFFFFFFFFFFFFFF00000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000066206D7920525341
c= 0X534810A0D1B2F6FB257DC3BBDA30AA76157B89038E52D05EE1E5DB06C2D79FAE84892950EF5FD8ADC4F241C3741AD7C97002902C8CA4D96574F28EDCEF3BEF15303335FA8D250102B4EE77E3B405E30F6B81E92403A8881285B65F29668E05B9CD6AC44FC1CD193CF4A5811A2649BE0EDEFBA91FA7143266286C5EC6EE8077D6

第3个明文分片参数及加密结果

1
2
3
4
5
6
7
8
p= 0XD502B3D96C648A9393966CDD37188D37576AA221290C861B347ED7A57640993F7ED2D16992B42AA3CA66936D3268DE47EB3A61B1495C982BF54EC0350B907C4F3CA272F9ED04EEB355367DFDA1B89357130A25411DAC4E3B8A1EECC594E0435F0E7298897B54D6C334062C8D8508AC67CEDAECD1A5FCA84BF2EE5D
q= 0XE00258CB6F
n= 0XBA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B511953
e= 0X10001
d= 0X524EB244F1CE59966C273B91AC40B620CFB55BA2030E871F01147E11844888B6224C5D4DE14551DFDB93C984DAD94A4359643B247ED6CC7DE774A15440D525E26FE9CF4328DBEF2AAA8E402922596F1C23B8F117C018870777434C93B68F1028295DFA6E69FA8E00FFC4EFEF747C348EDBC99C529B7C3B649813647FF90A8261
m= 0XFFFFFFFFFFFFFFFF0000000300000000000000000000000000000000000000000000000000000000000000000000000000000000000000002073797374656D2E
c= 0X8805A937DABF25FE760F9F398C7D9D5955EF7468FEC89119F8DD69874FB009AB2C424BD6A8E85401C4CD130B48D0490586DFBD81C8154EDCEFC3AFC4F80338432197EB059AB54CF109B231416FB65E2F9BE4F01D455E25486D8E155A5874E8A910E8C65F73ACD953D316B35A148D5AC5834D86F66AD415EBA38AD3908B32780A

密文结构解析

提取传送帧的信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n=[]#模数集合
e=[]#公钥指数集合
c=[]#密文集合
m={}#明文集合
# Path: code\main.py
sloved=[]#已解密的密文集合
filename=['RSA\data\Frame'+str(i) for i in range(0,21)]#文件名集合
# print(filename)
for i in range(0,21):
f=open(filename[i],'r')
data=f.read()
#str->hex->int
n.append(int(data[:256],16))
e.append(int(data[256:512],16))
c.append(int(data[512:],16))
#输出e的值
for i in range(0,21):
print('e['+str(i)+']='+str(e[i]))
#输出n的值
for i in range(0,21):
print('n['+str(i)+']='+str(n[i]))
#输出c的
for i in range(0,21):
print('c['+str(i)+']='+str(c[i]))

Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
e[0]=46786465362686334917265996843779843233606992585424976481745055335468678697948774988450305612127967926533923268260412557000125153569622340353246096040604284883505587337829322949633637609180797447754513992039018904786537115087888005528547900640339270052628915440787357271345416818313808448127098885767015748889
e[1]=65537
e[2]=65537
e[3]=5
e[4]=152206992575706893484835984472544529509325440944131662631741403414037956695665533186650071476146389737020554215956181827422540843366433981607643940546405002217220286072880967331118344806315756304650248634546597784597963886656422706197757265316981889118026978865295597135470735576032282694348773714479076093197
e[5]=65537
e[6]=65537
e[7]=3
e[8]=5
e[9]=65537
e[10]=65537
e[11]=3
e[12]=5
e[13]=65537
e[14]=65537
e[15]=3
e[16]=5
e[17]=65537
e[18]=65537
e[19]=65537
e[20]=5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n[0]=90058705186558569935261948496132914380077312570281980020033760044382510933070450931241348678652103772768114420567119848142360867111065753301402088676701668212035175754850951897103338079978959810673297215370534716084813732883918187890434411552463739669878295417744080700424913250020348487161014643951785502867
n[1]=92921790800705826977497755832938592891062287903332844896046168726101016067456726822505517352409138948392871113192427210529297191908638888388136391240683157994654207338463678065440899870434887094216772312358731142317774259942199808535233769089985063860828267808621928898445383706310204223006136919334252875849
n[2]=90252653600964453524559669296618135272911289775949194922543520872164147768650421038176330053599968601135821750672685664360786595430028684419411893316074286312793730822963564220564616708573764764386830123818197183233443472506106828919670406785228124876225200632055727680225997407097843708009916059133498338129
n[3]=92270627783020341903769877272635163757611737252302329401876135487358785338853904185572496782685853218459404423868889360808646192858060332110830962463986164014331540336037718684606223893506327126112739408023014900003600028654929488487584130630596342720833061628867179840913592694993869009133576053124769728363
n[4]=90058705186558569935261948496132914380077312570281980020033760044382510933070450931241348678652103772768114420567119848142360867111065753301402088676701668212035175754850951897103338079978959810673297215370534716084813732883918187890434411552463739669878295417744080700424913250020348487161014643951785502867
n[5]=99193711547257063160816850544214924340574358752670644615293764532335872088470223740970673347993652626497557387222167784182876395436088845281840169701654629849214222297784511349059698963212947299142320497759258889425182705042123217476724761095690092179821753840224757786599021225709340258545979566824267620959
n[6]=146839643970016464813197409569004275595828791825722617066607993001682901023784267554815946189374651530288894322286859792246413142980277245909181062525398546369553995023529451396820549308690493928593324007689135648753323161394735120908960458860801743476353228970081369439513197105039143930008573928693059198131
n[7]=155266493936043103849855199987896813716831986416707080645036022909153373110367007140301635144950634879983289720164117794783088845393686109145443728632527874768524615377182297125716276153800765906014206797548230661764274997562670900115383324605843933035314110752560290540848152237316752573471110899212429555149
n[8]=102900163930497791064402577447949741195464555746599233552338455905339363524435647082637326033518083289523250670463907211548409422234391456982344516192210687545692054217151133151915216123275005464229534891629568864361154658107093228352829098251468904800809585061088484485542019575848774643260318502441084765867
n[9]=97767951046154372321400443371234495476461828137251939025051233003462769415459435471728054384852461870179980010660162922547425212869925648424741526671585598167502856111641944825179295197098826911226483155821197251989297102189187139234080795582529077092266799813985026581245196104843272305656744384140745492897
n[10]=93836514358344173762895084384953633159699750987954044414830106276642828025218933012478990865656107605541657809389659063108620208004740646099662700112782252200834393363574089818787717951026690934986964275526538236750596344542450864284576226592039259070002692883820960186403938410354082341916474419847211138467
n[11]=112306066601652819062206435724795595603085908011001671184332227488970057128128821831260649058569739569103298091727188365019228385820143813415009397359257831092635374404034997011441653286642458431865026213129412677064308342580757248577955071384972714557250468686599901682728173096745710849318629959223270431039
n[12]=90267480939368160749458049207367083180407266027531212674879245323647502822038591438536367206422215464489854541063867946215243190345476874546091188408120551902573113507876754578290674792643018845798263156849027209440979746485414654160320058352559498237296080490768064578067282805498131582552189186085941328701
n[13]=94390533992358895550704225180484604016029781604622607833044135524814562613596803297695605669157378162035217814540004231075201420796787547733762265959320018107419058832819010681344133011777479722382525797938558181629835768471461434560813554411133962651212455645589624432040989600687436833459731886703583047283
n[14]=120008876536855131221255979370745233738591934188224528487535120483456214085493237482915446419599357910343450285858995374277365393767669569942204888383426461862651659865189178784473131914234181752055950431093341514138390898892413182538823693941124637301582389014479754627419560568004831093116617428970538503551
n[15]=147733349387696521015664992396355145811249793103958464053225389476050097503928022819269482555955365534137156079172704297584033078453033637103720972881068435459202133846880715879894340131656691631756162323422868846616160423755883726450486845175227682329583615739797782025647376042249605775433971714513081755709
n[16]=90673177193017332602781813187879442725562909473411994052511479411887936365983777106776080722300002656952655125041151156684340743907349108729774157616323863062525593382279143395837261053976652138764279456528493914961780300269591722101449703932139132398288208673556967030162666354552157189525415838326249712949
n[17]=111178307033150739104608647474199786251516913698936331430121060587893564405482896814045419370401816305592149685291034839621072343496556225594365571727260237484885924615887468053644519779081871778996851601207571981072261232384577126377714005550318990486619636734701266032569413421915520143377137845245405768733
n[18]=93394639108667212482180458616036741615058981058942739509025631675767304945732437421192075466824789572910657586684470553691049259504106442090140927782673066834126848556317079995332229262871079799089771973100731889841015960713908117908583988637159206246729697336281050046919985463146705713899703248595045701819
n[19]=94154993593274109828418786834159728190797445711539243887409583756844882924221269576486611543668906670821879426307992404721925623741478677756083992902711765865503466687919799394258306574702184666207180530598057989884729154273423032471322027993848437082723045300784582836897839491321003685598931080456249945287
n[20]=90916739755838083837461026375700330885001446224187511395518230504776419813625940046511904838818660297497622072999229706061698225191645268591198600955240116302461331913178712722096591257619538927050886521512453691902946234986556913039431677697816965623861908091178749411071673467596883926097177996147858865293
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
c[0]=48641173720475702278690317652676924796340996697567087705119344461991930773386153198223372579328462635803653561516674380209276666328375805315553713680858906705068657158073776194628700821011001144559278784795978097710145192236347629751116534400207288736776545247409895672030976932673010818369814246455196991083
c[1]=1626661141529320283833484152716550848856697186049377493478368799832043379420727509223318694347625977694500761460048670101820769656612419734057871562023463159698522348510157125720014700549254630959391701883372400982386084212421115166791728704867253734354874934210987301137512341070190760227227749365878233484
c[2]=39632263504870478574861695051251850807454294787974709214866410237055871793939895562441267574482198916367858789237648434983815369123479208726344716594227785308836601932181727610859898951190206345056426253251079929822424252271957269630987623886812686545521745791771387808772030614435314730783528512800343192265
c[3]=83421434286602546493364204139182949897795123160498680670964040331447569764445309937195566103281638928183742488663157138572020817924561990979723444797045375101801354862472761507421896454904818874439231990567738173059815647539737800523632262742398190575822391771655932895657208471832891505814792263361394479317
c[4]=19560634556305755550927540610989537766715902244072312818350844104485773927537226443429404190213856361759564153804627450805880512600339869169513348929194643809859468549718922965997647689203029517135396008631050292544022651948009392475583045438153697076529266662217519588521116539517972522591294232192817502376
c[5]=26054677793581772924866273737009673285775062802734786532404396138990264566536537921648515854012553861999940229349708989519156563830916553754762208466745321226835312974971739761769324569315525872096987367001543758380071859429619580182411498650200401467760546057912183435480924905200466941116258838789328064564
c[6]=47190775807472506173587993082023759909601357229808667044044468676457696140445235738005020994278091230440755033222450219378047807646817722376918364211727971804312327204294555178996480944188624972632371674822397258127227029990196956900925820980263353418653201918881814896866168764140848945600419602253279143149
c[7]=124929943232081828105808318993257526364596580021564021377503915670544445679836588765369503919311404328043203272693851622132258819278328852726005776082575583793735570095307898828254568015886630010269615546857335790791577865565021730890364239443651479580968112031521485174068731577348690810906553798608040451024
c[8]=25585088950095290712328215701309273521406235982885781641137768116285362079062975527364909549362511146004390419156826709543326814581466248280564194951706937822088902607754944405407698735824315900942915322054614437632116732271787823814807624841386886185122143173564380877370643120953803688563589496390425159539
c[9]=14375950543873882011796759348848479283522955796749853113492047625299699702886303193822347995567175524401038661237990847185236138967814088030767785916645492142741397786256445305366822277551514353423864240674522264407918605662008550545442780563568811883349771003546081844527788515420708612431091464410712019656
c[10]=78852785408127338210375705302361611580033298047358566712385067002412358292419274287993295604646693755514055710305938805847184012173449160624823261013152092151242661538772012880714981492275731658527465442787266554947828301571586721387286510359738598116104180351027973922256460236377354127082438812404967605644
c[11]=108387832390337770947361518376552702503741092284778824448943971792044922720461955035726863109418657218498659460663504872870862538725835055240750735576735249122665348803252691221869146679004017916359067454693701495389784159620341860394035373599823801288442604273046729873467936004227013186659110262247417571857
c[12]=44374979291120575503988741531987454898919254880086464254904878064332010355432423956182135846738023874326776872139229379943321321362822522900479438294291206287205647145759972233097276253408812699557305314344220807356024994977399840843758750494467535572805794732065369887057841293267499209427585419962565568495
c[13]=41663689952657185984513733558388033289292857758748468070934326941659317694408873831451567385012905508903797893149006067280788298408959017459890579859784072677410890657854942639040056924596925599973762214900728648657052474974405878868755028761443878403349272421153452240103741921751653022646614028009138548572
c[14]=35133765260146855599194761500993159592311136378033858818728078464540389548474611501950689942825550399101504201020687961256642455745888410410524955937773951578993882275525944145131794970001708655718844507774877602125183877782393564092461821246419013099835940432551540513624090850765797735157630551978900512155
c[15]=52253817590056116368273294519761274350847193477090280916373828903718796358618956145225746496960677477661151583828604021049936963779103440560630451125137344639503705880024677345063113240530798352727432768980751992926293801206779839157443722614687126711272753610923903360818026083573711899014859313677159790039
c[16]=24086371701602948122317790211004032014326487279907486724991846810668564197542368948703436295770758262739732290677177527297040556666434577730354732397784651220918412407485171180732327730242552955646750279842251200227937257322414662213662054605527282812231172173474061845763736546747711105935349033514358348526
c[17]=1395222187334055833498435136007269572138525113145744882969531037442244086277594803865217301719947066153176244638660864035949705664670633245110847416168796640199238733478540080417312141011028469385167826450855601412915611725028631975605932279023918771764204031806414734015476034106891049334159757621016327648
c[18]=49047978458885807127192385282227726754593888749388775377492411121925201201621099927332087316607446894372751446254341808051569111053293066232980434901592875347200122022210780536817524813076908750647137301610117592355818408280291766068780616226847056325075159440352473034526412778650516438709293396458312728764
c[19]=52958695992371180409414011678115981405835026800648278393085136639708219930134280877954018305615378579281651249142230848262822421713895227069561145945972448893229231020632492517869034217943260664130647322694583182800800838539691542175229797652856708373533581250607375664993806654537737027000328299623032632769
c[20]=23204039098754030513954332212496652705175644349879686639449689791620605370809827884267260830136516742466455588549253481016504796674014871020503543639681251834114159250986728840380777774144853925216884802529230212783759821262799845229436535491711201551797166082529740271577684082458494926929260818927584104158

结果分析

  • 遍历所有的模数N,判断是否存在模数相同的加密片段,如果猜测可以用共模攻击

  • 遍历寻找任意两个模数N的公因子,如果得到不为1的公因子则可以因数碰撞

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #遍历所有模数,找到模数相同的加密密文
    for i in range(0,21):
    for j in range(i+1,21):
    if n[i]==n[j]:
    print('n['+str(i)+']=='+'n['+str(j)+']')

    #遍历寻找任意两个模数N的公因子,如果得到不为1的公因子则可以成功分解这两个模数
    for i in range(0,21):
    for j in range(i+1,21):
    if n[i]==n[j]:
    continue
    else:
    rem=math.gcd(n[i],n[j])
    if rem!=1:
    print('gcd(n['+str(i)+'],n['+str(j)+']>1')

    结果
    #n[0]==n[4]
    #gcd(n[1],n[18])>1
  • 遍历所有加密指数e,寻找低加密指数及对应的加密对,可以用低指数广播攻击

    1
    2
    3
    4
    5
    6
    e[0]=46786465362686334917265996843779843233606992585424976481745055335468678697948774988450305612127967926533923268260412557000125153569622340353246096040604284883505587337829322949633637609180797447754513992039018904786537115087888005528547900640339270052628915440787357271345416818313808448127098885767015748889
    e[1]=e[2]=e[5]=e[6]=e[9]=e[10]=e[13]=e[14]=e[17]=e[18]=e[19]=65537
    e[2]=65537
    e[3]=e[8]=e[12]=e[16]=e[20]=5
    e[4]=152206992575706893484835984472544529509325440944131662631741403414037956695665533186650071476146389737020554215956181827422540843366433981607643940546405002217220286072880967331118344806315756304650248634546597784597963886656422706197757265316981889118026978865295597135470735576032282694348773714479076093197
    e[7]=e[11]=e[15]=3

    对上述的公钥e进行分析,主要有以下几种,其中e比较小的有3和5,其中

    Frame7,Frame11,Frame15采用低加密指数e=3进行加密

    Frame3,Frame8,Frame12,Frame16和Frame20均采用低加密指数e=5进行加密

  • 采用费马分解尝试p,q差距比较小的帧和Pollard p-1分解进行尝试p,q差距比较大的帧

    Frame10可以用费马分解法破解

    Frame2,6,19可以用p-1分解法破解

  • Baidu or Google Hack

实例破解

公共模数攻击

n[0]==n[4],还因为可能存在重复发包

设两个用户的公钥分别为 e1e_1e2e_2 ,且两者互质。明文消息为 mm ,密文分别为:

c1=me1modnc2=me2modn\begin{aligned} &c_1=m^{e_1} \bmod n \\ &c_2=m^{e_2} \bmod n \end{aligned}

当攻击者截获 c1c_1c2c_2 后,就可以恢复出明文。用扩展欧几里得算法求出 re1+se2=1modnr e_1+s e_2=1 \bmod n 的两个整数 rrss ,由此可得:

c1rc2smre1mse2modnm(re1+se2)modnmmodn\begin{aligned} c_1^r c_2^s & \equiv m^{r e_1} m^{s e_2} \bmod n \\ & \equiv m^{\left(r e_1+s e_2\right)} \bmod n \\ & \equiv m \bmod n \end{aligned}

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
#公共模数攻击
#扩展欧几里得算法
def exgcd(a,b):
if b==0:
return 1,0,a
else:
x,y,r=exgcd(b,a%b)
x,y=y,(x-(a//b)*y)
return x,y,r
def same_mod_attack(n,e1,e2,c1,c2):
x,y,r=exgcd(e1,e2)
#求模逆元
if x<0:
x=-x;
c1=gmpy2.invert(c1,n)
elif y<0:
y=-y;
c2=gmpy2.invert(c2,n)
#求解明文
m=pow(c1,x,n)*pow(c2,y,n)%n
#将明文转换为hex
m=hex(m)[2:]#去掉0x
#将hex转换为str
m=binascii.unhexlify(m)[-8:]#hex->str
return m

if __name__ == '__main__':
#公共模数攻击
for i in range(0,21):
for j in range(i+1,21):
if n[i]==n[j]:
m2=same_mod_attack(n[i],e[i],e[j],c[i],c[j])
sloved['Frame'+str(i)]=m2
sloved['Frame'+str(j)]=m2
print(sloved)

{‘Frame0’: b’My secre’, ‘Frame4’: b’My secre’}

公因数碰撞攻击

Frame1、Frame18采用该种攻击方法

因数碰撞法指的是, 如果参数选取不当, pp 或者 qq 在多个RSA加密中出现多次,那么生成不同的 n\mathrm{n} 可能会有相同的因子,我们假设 p\mathrm{p}相同,q\mathrm{q}不同,那么在

{n1=pq1n2=pq2\left\{\begin{array}{l} n_1=p * q_1 \\ n_2=p * q_2 \end{array}\right.

很容易知道

gcd(n1,n2)=p\operatorname{gcd}\left(n_1, n_2\right)=p

这样很快就能将他们各自的私钥求解出来了。
代码过于简单, 直接gcd两个因数就行, 结果不为1就说明有相同因数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#公因数碰撞攻击
def same_factor_attack():
p_of_prime=gmpy2.gcd(n[1],n[18])
q1=n[1]//p_of_prime
q18=n[18]//p_of_prime
phi1=(p_of_prime-1)*(q1-1)#计算欧拉函数
phi18=(p_of_prime-1)*(q18-1)#计算欧拉函数
d1=gmpy2.invert(e[1],phi1)#计算私钥
d18=gmpy2.invert(e[18],phi18)#计算私钥
m1=pow(c[1],d1,n[1])#解密
m18=pow(c[18],d18,n[18])#解密
m1=hex(m1)[2:]#去掉0x
m18=hex(m18)[2:]#去掉0x
m1=binascii.unhexlify(m1)[-8:]#hex->str
m18=binascii.unhexlify(m18)[-8:]#hex->str
sloved['Frame1']=m1
sloved['Frame18']=m18

‘Frame1’: b’. Imagin’, ‘Frame18’: b’m A to B’

低指数广播攻击

Frame3、Frame8、Frame12、Frame16、Frame20采用该种攻击方法

低加密指数广播攻击适合于n\mathrm{n}很大,ee很小的情况, 其适用的情况是如n\mathrm{n}下的,当一条消息mm发送给不同的接收者时,每个接收者的 nn 都不同,但是加密公钥都是相同的,我们假设公钥为3那么就有

{C1=m3modn1C2=m3modn2C3=m3modn3\left\{\begin{array}{l} C_1=m^3 \bmod n_1 \\ C_2=m^3 \bmod n_2 \\ C_3=m^3 \bmod n_3 \end{array}\right.

由中国剩余定理知道,我们是可以将 m3m^3 算出来的,那么对其开立方就将明文给求出来了。

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
#中国剩余定理
def chinese_remainder_theorem(backup):
#计算N的乘积
N=1
for a,n in backup:
N*=n
#计算Ni
Ni=[]
for a,n in backup:
Ni.append(N//n)
#计算Ni的模逆元
Ni_inverse=[]
for i in range(0,len(Ni)):
Ni_inverse.append(gmpy2.invert(Ni[i],backup[i][1]))
#计算x
x=0
for i in range(0,len(Ni)):
x+=backup[i][0]*Ni[i]*Ni_inverse[i]
x=x%N
return x,N

#低指数3
def low_exponent_attack3():
frame_range=[7,11,15]
backup=[]
for i in frame_range:
backup.append([c[i],n[i]])
x,N=chinese_remainder_theorem(backup)
#开三次方根
m=gmpy2.iroot(x,3)[0]
m=hex(m)[2:]#去掉0x
m=binascii.unhexlify(m)[-8:]#hex->str
sloved['Frame7']=m
sloved['Frame11']=m
sloved['Frame15']=m
#低指数5
def low_exponent_attack5():
frame_range=[3,8,12,16,20]
backup=[]
for i in frame_range:
backup.append([c[i],n[i]])
x,N=chinese_remainder_theorem(backup)
#开五次方根
m=gmpy2.iroot(x,5)[0]
m=hex(m)[2:]#去掉0x
m=binascii.unhexlify(m)[-8:]#hex->str
sloved['Frame3']=m
sloved['Frame8']=m
sloved['Frame12']=m
sloved['Frame16']=m
sloved['Frame20']=m

‘Frame7’: b’\xb8\xbc\xa2S)s\xcd\xd2’, ‘Frame11’: b’\xb8\xbc\xa2S)s\xcd\xd2’, ‘Frame15’: b’\xb8\xbc\xa2S)s\xcd\xd2’, ‘Frame3’: b’t is a f’, ‘Frame8’: b’t is a f’, ‘Frame12’: b’t is a f’, ‘Frame16’: b’t is a f’, ‘Frame20’: b’t is a f’

可以看到Frame7,Frame11,Frame15采用低加密指数广播攻击出来是乱码,说明该种方法不正确

Frame3、Frame8、Frame12、Frame16、Frame20可以采用该种攻击方法

Coppersmith广播攻击

Coppersmith 是干了这么一件事: 今有一个 ee 阶的多项式 ff, 那么可以:

  • 在模 nn 意义下,快速求出 n1/en^{1 / e} 以内的根

  • 给定 β\beta ,快速求出模某个 bb 意义下较小的根,其中 bnβb \geq n^\beta ,是 nn 的因数。

Pollard p-1分解法

Frame2、Frame6、Frame19均采用该种攻击方法

如果 ppqq 都不超过 102010^{20} 次方, 若其中一个 (p1)(p-1)(q1)(q-1) 的因子都很小的时候(适用于p-1或q-1能够被小素数整除的情况,在这里为了方便说明我们假设为 (p1))(p-1)) ,可以如下操作:
选取一个整数 kk, 使其满足 (p1)k!(p-1) \mid k!,由费马小定理知道, aapp 互素 的时候有

ap1=1modpa^{p-1}=1 \bmod p

所以 ak!=1modp,a^{k !}=1 \bmod p \quad, \quadp(ak!1)\mathrm{p} \mid\left(a^{k !}-1\right) 。 那么对于 n\mathrm{n}(ak!1)\left(a^{k !}-1\right) 必有公因数为 p\mathrm{p}, 这样就可以把 n\mathrm{n} 分解出来了。 但是对于 kk 的选取还是有要求的,太小了 (p1)k!(p-1) \mid k !不会成立,太大了花费时间会很多。

Pollard p-1 Factoring Algorithm (n,B)(\mathrm{n}, \mathrm{B}) :
a2B!(modn)a \leftarrow 2^{B !}(\bmod n)
dgcd(a1,n)d \leftarrow \operatorname{gcd}(a-1, n)
if 1<d<n1<d<n then return dd else return failure

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
#Pollard's p-1算法
def pollard_p_1(n):
b=2**20
a=2
# while True:
# a=gmpy2.powmod(a,b,n)
# d=gmpy2.gcd(a-1,n)
# if d!=1 and d!=n:
# return d
# a+=1
for i in range(2,b+1):
a=gmpy2.powmod(a,i,n)
d=gmpy2.gcd(a-1,n)
if d!=1 and d!=n:
q=n//d
n=q*d
return d
def pollard_data(n):
frame_range=[2,6,19]
for i in frame_range:
temp_n=n[i]
temp_c=c[i]
temp_e=e[i]
p=pollard_p_1(temp_n)
q=temp_n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(temp_e,phi)
m=pow(temp_c,d,temp_n)
m=hex(m)[2:]#去掉0x
m=binascii.unhexlify(m)[-8:]#hex->str
sloved['Frame'+str(i)]=m

‘Frame2’: b’ That is’, ‘Frame6’: b’ "Logic ‘, ‘Frame19’: b’instein.’

费马分解法

如果 ppqq 相差不大的话我们可以通过费马分解把 ppqq 求出来, 原理如 下

n=pq=14(p+q)214(pq)2\mathrm{n}=\mathrm{p} * \mathrm{q}=\frac{1}{4}(p+q)^2-\frac{1}{4}(p-q)^2

由于 p\mathrm{p}q\mathrm{q} 相差不大, 所以 pq\mathrm{p}-\mathrm{q} 相对于 n\mathrm{n}(p+q)2(p+q)^2 来说可以忽略不计, 所以有~

2np+q2 \sqrt{\mathrm{n}} \approx \mathrm{p}+\mathrm{q}

也就是说通过不断尝试就可以把 p\mathrm{p}q\mathrm{q} 给计算出来了

p、q比较接近时,可以使用这种攻击方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 费马分解
def fermat_factorization(n):
a=gmpy2.iroot(n,2)[0]+1
max=200000
for i in range(0,max):
b2=a*a-n
b=gmpy2.iroot(b2,2)[0]
if gmpy2.is_square(b2):
p=a-b
q=a+b
return p,q
a+=1
def fermat_data():
frame_range=[10]
for i in frame_range:
p,q=fermat_factorization(n[i])
phi=(p-1)*(q-1)#计算欧拉函数
d=gmpy2.invert(e[i],phi)#计算私钥
m=pow(c[i],d,n[i])#解密
m=hex(m)[2:]#去掉0x
m=binascii.unhexlify(m)[-8:]#hex->str
sloved['Frame'+str(i)]=m

经检验,Frame10可以采用该种攻击方法

‘Frame10’: b’will get’

综上

帧号 value solution
Frame0 My secre 公共模数攻击
Frame1 . Imagin 公因数碰撞攻击
Frame2 That is Pollard rho-p-1分解法
Frame3 t is a f 低指数广播攻击
Frame4 My secre 公共模数攻击
Frame5
Frame6 "Logic Pollard rho-p-1分解法
Frame7 https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_coppersmith_attack/
Frame8 t is a f 低指数广播攻击
Frame9
Frame10 will get 费马分解法
Frame11
Frame12 t is a f 低指数广播攻击
Frame13
Frame14
Frame15 https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_coppersmith_attack/
Frame16 t is a f 低指数广播攻击
Frame17
Frame18 m A to B 公因数碰撞攻击
Frame19 instein. Pollard rho-p-1分解法
Frame20 t is a f 低指数广播攻击

整理一下My secret is a f__instein. That is "Logic will get__m A to B. Imagin__

根据搜索结果可以补全后面的saying的内容,根据语义也可以填充前面的内容

My secret is a famous saying of Albert Einstein. That is "Logic will get you from A to B. Imagination will take you everywhere.“

image-20221103131323423 image-20221103131433317

参考链接

[2016 全国高校密码数学挑战赛-赛题三] https://www.tr0y.wang/2017/10/31/RSA2016/

[现代密码学大作业] https://blog.csdn.net/m0_63571390/article/details/122375466?spm=1001.2014.3001.5501

[关于RSA的几种攻击手段] https://blog.csdn.net/pigeon_1/article/details/114371456

[Pollard’s rho算法] https://blog.csdn.net/qq_39972971/article/details/82346390

[分解因子算法——Pollard rho算法] https://blog.csdn.net/weixin_46395886/article/details/115073059

https://en.wikipedia.org/wiki/Pollard's_rho_algorithm

Coppersmith 相关攻击 - CTF Wiki (ctf-wiki.org)

Coppersmith 攻击 (ruanx.net)

Twenty Years of Attacks on the RSA Cryptosystem

完整代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
import binascii
import gmpy2
import math
n=[]#模数集合
e=[]#公钥指数集合
c=[]#密文集合
m={zip(['Frame'+str(i) for i in range(0,21)],'')}
# Path: code\main.py
sloved={}#已解密的密文集合
filename=['RSA\data\Frame'+str(i) for i in range(0,21)]#文件名集合
# print(filename)
for i in range(0,21):
f=open(filename[i],'r')
data=f.read()
#str->hex->int
n.append(int(data[:256],16))
e.append(int(data[256:512],16))
c.append(int(data[512:],16))
#输出e的值
# for i in range(0,21):
# print('e['+str(i)+']='+str(e[i]))
# #输出n的值
# for i in range(0,21):
# print('n['+str(i)+']='+str(n[i]))
# #输出c的
# for i in range(0,21):
# print('c['+str(i)+']='+str(c[i]))

#遍历所有模数,找到模数相同的加密密文
for i in range(0,21):
for j in range(i+1,21):
if n[i]==n[j]:
print('n['+str(i)+']=='+'n['+str(j)+']')

#遍历寻找任意两个模数N的公因子,如果得到不为1的公因子则可以成功分解这两个模数
for i in range(0,21):
for j in range(i+1,21):
if n[i]==n[j]:
continue
else:
rem=math.gcd(n[i],n[j])
if rem!=1:
print('gcd(n['+str(i)+'],n['+str(j)+'])='+str(rem))
#公共模数攻击
#扩展欧几里得算法
def exgcd(a,b):
if b==0:
return 1,0,a
else:
x,y,r=exgcd(b,a%b)
x,y=y,(x-(a//b)*y)
return x,y,r
def same_mod_attack(n,e1,e2,c1,c2):
x,y,r=exgcd(e1,e2)
#求模逆元
if x<0:
x=-x;
c1=gmpy2.invert(c1,n)
elif y<0:
y=-y;
c2=gmpy2.invert(c2,n)
#求解明文
m=pow(c1,x,n)*pow(c2,y,n)%n
#将明文转换为hex
m=hex(m)[2:]#去掉0x
#将hex转换为str
m=binascii.unhexlify(m)[-8:]#hex->str
return m
#公因数碰撞攻击
def same_factor_attack():
p_of_prime=gmpy2.gcd(n[1],n[18])
q1=n[1]//p_of_prime
q18=n[18]//p_of_prime
phi1=(p_of_prime-1)*(q1-1)#计算欧拉函数
phi18=(p_of_prime-1)*(q18-1)#计算欧拉函数
d1=gmpy2.invert(e[1],phi1)#计算私钥
d18=gmpy2.invert(e[18],phi18)#计算私钥
m1=pow(c[1],d1,n[1])#解密
m18=pow(c[18],d18,n[18])#解密
m1=hex(m1)[2:]#去掉0x
m18=hex(m18)[2:]#去掉0x
m1=binascii.unhexlify(m1)[-8:]#hex->str
m18=binascii.unhexlify(m18)[-8:]#hex->str
sloved['Frame1']=m1
sloved['Frame18']=m18
#中国剩余定理
def chinese_remainder_theorem(backup):
#计算N的乘积
N=1
for a,n in backup:
N*=n
#计算Ni
Ni=[]
for a,n in backup:
Ni.append(N//n)
#计算Ni的模逆元
Ni_inverse=[]
for i in range(0,len(Ni)):
Ni_inverse.append(gmpy2.invert(Ni[i],backup[i][1]))
#计算x
x=0
for i in range(0,len(Ni)):
x+=backup[i][0]*Ni[i]*Ni_inverse[i]
x=x%N
return x,N

#低指数3
def low_exponent_attack3():
frame_range=[7,11,15]
backup=[]
for i in frame_range:
backup.append([c[i],n[i]])
x,N=chinese_remainder_theorem(backup)
#开三次方根
m=gmpy2.iroot(x,3)[0]
m=hex(m)[2:]#去掉0x
m=binascii.unhexlify(m)[-8:]#hex->str
sloved['Frame7']=m
sloved['Frame11']=m
sloved['Frame15']=m
#低指数5
def low_exponent_attack5():
frame_range=[3,8,12,16,20]
backup=[]
for i in frame_range:
backup.append([c[i],n[i]])
x,N=chinese_remainder_theorem(backup)
#开五次方根
m=gmpy2.iroot(x,5)[0]
m=hex(m)[2:]#去掉0x
m=binascii.unhexlify(m)[-8:]#hex->str
sloved['Frame3']=m
sloved['Frame8']=m
sloved['Frame12']=m
sloved['Frame16']=m
sloved['Frame20']=m

# 费马分解
def fermat_factorization(n):
a=gmpy2.iroot(n,2)[0]+1
max=200000
for i in range(0,max):
b2=a*a-n
b=gmpy2.iroot(b2,2)[0]
if gmpy2.is_square(b2):
p=a-b
q=a+b
return p,q
a+=1
def fermat_data():
frame_range=[10]
for i in frame_range:
p,q=fermat_factorization(n[i])
phi=(p-1)*(q-1)#计算欧拉函数
d=gmpy2.invert(e[i],phi)#计算私钥
m=pow(c[i],d,n[i])#解密
m=hex(m)[2:]#去掉0x
m=binascii.unhexlify(m)[-8:]#hex->str
sloved['Frame'+str(i)]=m




#Pollard's p-1算法
def pollard_p_1(n):
b=2**20
a=2
# while True:
# a=gmpy2.powmod(a,b,n)
# d=gmpy2.gcd(a-1,n)
# if d!=1 and d!=n:
# return d
# a+=1
for i in range(2,b+1):
a=gmpy2.powmod(a,i,n)
d=gmpy2.gcd(a-1,n)
if d!=1 and d!=n:
q=n//d
n=q*d
return d
def pollard_data(n):
frame_range=[2,6,19]
for i in frame_range:
temp_n=n[i]
temp_c=c[i]
temp_e=e[i]
p=pollard_p_1(temp_n)
q=temp_n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(temp_e,phi)
m=pow(temp_c,d,temp_n)
m=hex(m)[2:]#去掉0x
m=binascii.unhexlify(m)[-8:]#hex->str
sloved['Frame'+str(i)]=m

if __name__ == '__main__':
#公共模数攻击
for i in range(0,21):
for j in range(i+1,21):
if n[i]==n[j]:
m2=same_mod_attack(n[i],e[i],e[j],c[i],c[j])
sloved['Frame'+str(i)]=m2
sloved['Frame'+str(j)]=m2
#公因数碰撞攻击
same_factor_attack()
print(sloved)
#低指数攻击
low_exponent_attack3()
low_exponent_attack5()
print(sloved)
#费马分解
fermat_data()
print(sloved)
#Pollard's p-1算法
pollard_data(n)

print(sloved)
#输出将地点按照帧数排序
for i in range(1,21):
if sloved['Frame'+str(i)]:
print(sloved['Frame'+str(i)])