题目摘要
赛题名称： RSA 加密体制破译
赛题描述
RSA密码算法是使用最为广泛的公钥密码体制。该体制简单且易于实现，只需要选择5个参数即可（两个素数$𝑝$和$𝑞$、模数$𝑁=𝑝𝑞$、加密指数$𝑒$和解密指数$𝑑$。设𝑚为待加密消息RSA体制破译相当于已知$𝑚^𝑒$ $mod$ $𝑁$能否还原𝑚的数论问题。目前模数规模为1024比特的RSA算法一般情况下是安全的，但是如果参数选取不当，同样存在被破译的可能。有人制作了一个RSA加解密软件采用的RSA体制的参数特点描述见密码背景部分）。
已知该软件发送某个明文的所有参数和加密过程的全部数据（加密案例文件详见附件3-1。Alice使用该软件发送了一个通关密语，且所有加密数据已经被截获，请问能否仅从加密数据恢复该通关密语及RSA体制参数？如能请给出原文和参数，如不能请给出已恢复部分并说明剩余部分不能恢复的理由？
加密过程
- 原始明文
This is a test of my RSA system.
Frame0
A5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100019726C82FED1E6CD58DE825528AE5634653C9921CAE02AFF7325F20D6E7085B7C8E3DC78D7518A78A8BC7D07E2E837083324579510851827794AE3D1FB9BAB360B1413A8F171A83804CEA73DFBC1248139BB27EB7D5BAD724AD8B08F51888B90562AF950725ACDD698F817AE62746CEA09479A191A6552B0116830355C68D0F61
Frame1
A5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD90000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001789018FDB800AD59A54D27A77F280515BB3BFAB1CD75CB0A255A116D4A44849459FD887FF091F87C0B3E6305F019700E4E4CB3646D1DF276DFB87C4F64245F77377508EC6A796236F8ABB125023D3F4B898F55E3342D0A852193AF890990EA82F12FC85917BF132F2A58C449648D6E934B24E80307AB092DB18110D77BBA0F8E
Frame2
BA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B5119530000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001534810A0D1B2F6FB257DC3BBDA30AA76157B89038E52D05EE1E5DB06C2D79FAE84892950EF5FD8ADC4F241C3741AD7C97002902C8CA4D96574F28EDCEF3BEF15303335FA8D250102B4EE77E3B405E30F6B81E92403A8881285B65F29668E05B9CD6AC44FC1CD193CF4A5811A2649BE0EDEFBA91FA7143266286C5EC6EE8077D6
Frame3
BA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B51195300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100018805A937DABF25FE760F9F398C7D9D5955EF7468FEC89119F8DD69874FB009AB2C424BD6A8E85401C4CD130B48D0490586DFBD81C8154EDCEFC3AFC4F80338432197EB059AB54CF109B231416FB65E2F9BE4F01D455E25486D8E155A5874E8A910E8C65F73ACD953D316B35A148D5AC5834D86F66AD415EBA38AD3908B32780A
2.过程及参数
RSA 密码算法描述如下，包含体制参数选取和加解密过程。
1）RSA 体制参数选取
Step1.每个使用者，任意选择两个大素数$𝑝$和$𝑞$，并求出其乘积$𝑁=𝑝𝑞$。
Step2.令$𝜑(𝑁)=(𝑝−1)(𝑞−1)$选择整数$𝑒$，使得$GCD(𝑒,𝜑(𝑁))=1$，并求出$𝑒$模 $𝜑(𝑁)$的逆元$𝑑$，即$𝑒𝑑≡1 mod (𝜑(𝑁))$
Step3.将数对$(𝑒,𝑁)$公布为公钥，$𝑑$保存为私钥。
2）加解密过程
Bob欲传递明文𝑚给 Alice，则Bob首先由公开途径找出 Alice 的公钥 $(𝑒,𝑁)$，Bob 计算加密的信息$𝑐$为:$𝑐 ≡ 𝑚^𝑒$ $mod$ $𝑁$。
Bob 将密文$𝑐$传送给 Alice。 随后 Alice 利用自己的私钥$𝑑$解密： $𝑐^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密文== $m^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字符长度消息(注意：空格也是一个字符)
This is 该8字符对应的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条消息依次为
0xFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005468697320697320
0xFFFFFFFFFFFFFFFF000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000612074657374206F
0xFFFFFFFFFFFFFFFF00000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000066206D7920525341
0xFFFFFFFFFFFFFFFF0000000300000000000000000000000000000000000000000000000000000000000000000000000000000000000000002073797374656D2E
第0个明文分片参数及加密结果
p= 0XC60C5F1B997ED8A5E340023F33D2E269CFB423A3CF66B46D3F686747403A92B1265CB12B9A4E0135B890254F31A2C3F96A0427B39A36DEFDEEB85C57A80A9641
q= 0XD684DA331AB6157DA338B6D7B08AB4C1B72C29BB7F9EF445466056DFDBF29809C4D4A2435986A40DE688AFE7CC5A5C519F7C63CB486E44D523B0E1EF21C22199
n= 0XA5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD9
e= 0X10001
d= 0X4C5340AAECBB1BB5BE74F09F9D9D45BF4583ECF38334D75FF44834A4809CEC4D57071C9374DC1EC3BF574634B0D30DC7EF1D04E0131EAA2F5C4B8364D6A95676C23F9DADAAB4523A6F5B22EC5904650BF558B3FDF39E3B13EA4771FB1D297DA03C8E1E82F4759B31A9492C56E4D1C690A66ECEC430849A17C027D1A7480F1E01
m= 0XFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005468697320697320
c= 0X9726C82FED1E6CD58DE825528AE5634653C9921CAE02AFF7325F20D6E7085B7C8E3DC78D7518A78A8BC7D07E2E837083324579510851827794AE3D1FB9BAB360B1413A8F171A83804CEA73DFBC1248139BB27EB7D5BAD724AD8B08F51888B90562AF950725ACDD698F817AE62746CEA09479A191A6552B0116830355C68D0F61
第1个明文分片参数及加密结果
p= 0XC60C5F1B997ED8A5E340023F33D2E269CFB423A3CF66B46D3F686747403A92B1265CB12B9A4E0135B890254F31A2C3F96A0427B39A36DEFDEEB85C57A80A9641
q= 0XD684DA331AB6157DA338B6D7B08AB4C1B72C29BB7F9EF445466056DFDBF29809C4D4A2435986A40DE688AFE7CC5A5C519F7C63CB486E44D523B0E1EF21C22199
n= 0XA5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD9
e= 0X10001
d= 0X4C5340AAECBB1BB5BE74F09F9D9D45BF4583ECF38334D75FF44834A4809CEC4D57071C9374DC1EC3BF574634B0D30DC7EF1D04E0131EAA2F5C4B8364D6A95676C23F9DADAAB4523A6F5B22EC5904650BF558B3FDF39E3B13EA4771FB1D297DA03C8E1E82F4759B31A9492C56E4D1C690A66ECEC430849A17C027D1A7480F1E01
m= 0XFFFFFFFFFFFFFFFF000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000612074657374206F
c= 0X789018FDB800AD59A54D27A77F280515BB3BFAB1CD75CB0A255A116D4A44849459FD887FF091F87C0B3E6305F019700E4E4CB3646D1DF276DFB87C4F64245F77377508EC6A796236F8ABB125023D3F4B898F55E3342D0A852193AF890990EA82F12FC85917BF132F2A58C449648D6E934B24E80307AB092DB18110D77BBA0F8E
第2个明文分片参数及加密结果
p= 0XD502B3D96C648A9393966CDD37188D37576AA221290C861B347ED7A57640993F7ED2D16992B42AA3CA66936D3268DE47EB3A61B1495C982BF54EC0350B907C4F3CA272F9ED04EEB355367DFDA1B89357130A25411DAC4E3B8A1EECC594E0435F0E7298897B54D6C334062C8D8508AC67CEDAECD1A5FCA84BF2EE5D
q= 0XE00258CB6F
n= 0XBA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B511953
e= 0X10001
d= 0X524EB244F1CE59966C273B91AC40B620CFB55BA2030E871F01147E11844888B6224C5D4DE14551DFDB93C984DAD94A4359643B247ED6CC7DE774A15440D525E26FE9CF4328DBEF2AAA8E402922596F1C23B8F117C018870777434C93B68F1028295DFA6E69FA8E00FFC4EFEF747C348EDBC99C529B7C3B649813647FF90A8261
m= 0XFFFFFFFFFFFFFFFF00000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000066206D7920525341
c= 0X534810A0D1B2F6FB257DC3BBDA30AA76157B89038E52D05EE1E5DB06C2D79FAE84892950EF5FD8ADC4F241C3741AD7C97002902C8CA4D96574F28EDCEF3BEF15303335FA8D250102B4EE77E3B405E30F6B81E92403A8881285B65F29668E05B9CD6AC44FC1CD193CF4A5811A2649BE0EDEFBA91FA7143266286C5EC6EE8077D6
第3个明文分片参数及加密结果
p= 0XD502B3D96C648A9393966CDD37188D37576AA221290C861B347ED7A57640993F7ED2D16992B42AA3CA66936D3268DE47EB3A61B1495C982BF54EC0350B907C4F3CA272F9ED04EEB355367DFDA1B89357130A25411DAC4E3B8A1EECC594E0435F0E7298897B54D6C334062C8D8508AC67CEDAECD1A5FCA84BF2EE5D
q= 0XE00258CB6F
n= 0XBA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B511953
e= 0X10001
d= 0X524EB244F1CE59966C273B91AC40B620CFB55BA2030E871F01147E11844888B6224C5D4DE14551DFDB93C984DAD94A4359643B247ED6CC7DE774A15440D525E26FE9CF4328DBEF2AAA8E402922596F1C23B8F117C018870777434C93B68F1028295DFA6E69FA8E00FFC4EFEF747C348EDBC99C529B7C3B649813647FF90A8261
m= 0XFFFFFFFFFFFFFFFF0000000300000000000000000000000000000000000000000000000000000000000000000000000000000000000000002073797374656D2E
c= 0X8805A937DABF25FE760F9F398C7D9D5955EF7468FEC89119F8DD69874FB009AB2C424BD6A8E85401C4CD130B48D0490586DFBD81C8154EDCEFC3AFC4F80338432197EB059AB54CF109B231416FB65E2F9BE4F01D455E25486D8E155A5874E8A910E8C65F73ACD953D316B35A148D5AC5834D86F66AD415EBA38AD3908B32780A
密文结构解析
提取传送帧的信息
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
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
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
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的公因子则可以因数碰撞
#遍历所有模数,找到模数相同的加密密文 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，寻找低加密指数及对应的加密对，可以用低指数广播攻击
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],还因为可能存在重复发包
设两个用户的公钥分别为 $e_1$ 和 $e_2$ ，且两者互质。明文消息为 $m$ ，密文分别为: $$ \begin{aligned} &c_1=m^{e_1} \bmod n \ &c_2=m^{e_2} \bmod n \end{aligned} $$ 当攻击者截获 $c_1$ 和 $c_2$ 后，就可以恢复出明文。用扩展欧几里得算法求出 $r e_1+s e_2=1 \bmod n$ 的两个整数 $r$ 和 $s$ ，由此可得: $$ \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} $$
#公共模数攻击
#扩展欧几里得算法
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采用该种攻击方法
因数碰撞法指的是, 如果参数选取不当, $p$ 或者 $q$ 在多个RSA加密中出现多次，那么生成不同的 $\mathrm{n}$ 可能会有相同的因子，我们假设 $\mathrm{p}$相同,$\mathrm{q}$不同，那么在
$$
\left{\begin{array}{l}
n_1=p * q_1 \
n_2=p * q_2
\end{array}\right.
$$
很容易知道
$$
\operatorname{gcd}\left(n_1, n_2\right)=p
$$
这样很快就能将他们各自的私钥求解出来了。
代码过于简单, 直接gcd两个因数就行, 结果不为1就说明有相同因数。
#公因数碰撞攻击
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采用该种攻击方法
低加密指数广播攻击适合于$\mathrm{n}$很大,$e$很小的情况, 其适用的情况是如$\mathrm{n}$下的，当一条消息$m$发送给不同的接收者时，每个接收者的 $n$ 都不同，但是加密公钥都是相同的，我们假设公钥为3那么就有 $$ \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. $$ 由中国剩余定理知道,我们是可以将 $m^3$ 算出来的，那么对其开立方就将明文给求出来了。
#中国剩余定理
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 是干了这么一件事: 今有一个 $e$ 阶的多项式 $f$, 那么可以:
-
在模 $n$ 意义下，快速求出 $n^{1 / e}$ 以内的根
-
给定 $\beta$ ，快速求出模某个 $b$ 意义下较小的根，其中 $b \geq n^\beta$ ，是 $n$ 的因数。
Pollard p-1分解法
Frame2、Frame6、Frame19均采用该种攻击方法
Pollard p-1分解法是一种用于分解大质数的算法，它是Pollard rho算法的一种变体。它的基本思想是利用费马小定理来找到大质数的一个小因子。
如果 $p$ 与 $q$ 都不超过 $10^{20}$ 次方, 若其中一个 $(p-1)$ 或 $(q-1)$ 的因子都很小的时候（适用于p-1或q-1能够被小素数整除的情况,在这里为了方便说明我们假设为 $(p-1))$ ,可以如下操作: 选取一个整数 $k$, 使其满足 $(p-1) \mid k!$，由费马小定理知道, $a$ 与 $p$ 互素 的时候有 $$ a^{p-1}=1 \bmod p $$ 所以 $a^{k !}=1 \bmod p \quad, \quad$即 $\mathrm{p} \mid\left(a^{k !}-1\right)$ 。 那么对于 $\mathrm{n}$ 与 $\left(a^{k !}-1\right)$ 必有公因数为 $\mathrm{p}$, 这样就可以把 $\mathrm{n}$ 分解出来了。 但是对于 $k$ 的选取还是有要求的，太小了 $(p-1) \mid k !$不会成立，太大了花费时间会很多。
- 首先选取一个合适的整数a和一个正整数B；
- 选择一个整数k，使得k满足2<=k<=B；
- 计算$a^k ~ mod ~ n$，然后将其与n计算最大公因数，记为d；
- 如果d是n的因子，则输出d；否则，将d作为下一次迭代的起点，重复执行第3步和第4步，直到找到一个因子或者达到最大迭代次数为止。
在实际使用中，可以选择多个不同的a值和不同的B值，然后分别运行p-1分解法，取所有得到的因子的最大公因数作为最终的结果。
需要注意的是，p-1分解法的效率取决于选取的参数a和B的大小。如果a过小或B过大，算法可能无法找到因子；如果a过大或B过小，算法可能会陷入循环而无法得到结果。因此，在实际应用中需要进行合理的参数选择。
Get $\mathrm{n}$, an odd integer to be factored.
Let $\mathrm{a}=2$ and $\mathrm{i}=2$.
Compute $a=a^i \bmod n$.
Compute $\mathrm{d}=\operatorname{gcd}(\mathrm{a}-1, \mathrm{n})$.
If $1<\mathrm{d}<\mathrm{n}$, then output $\mathrm{d}$ as a factor of $\mathrm{n}$.
If $\mathrm{d}=1$, then $\mathrm{i}=\mathrm{i}+1$, and go to step 3.
#Pollard's p-1算法
def pollard_p_1(n):
b=2**20
a=2
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.’
费马分解法
如果 $p$ 和 $q$ 相差不大的话我们可以通过费马分解把 $p$ 和 $q$ 求出来, 原理如 下 $$ \mathrm{n}=\mathrm{p} * \mathrm{q}=\frac{1}{4}(p+q)^2-\frac{1}{4}(p-q)^2 $$ 由于 $\mathrm{p}$ 与 $\mathrm{q}$ 相差不大, 所以 $\mathrm{p}-\mathrm{q}$ 相对于 $\mathrm{n}$ 和 $(p+q)^2$ 来说可以忽略不计, 所以有～ $$ 2 \sqrt{\mathrm{n}} \approx \mathrm{p}+\mathrm{q} $$ 也就是说通过不断尝试就可以把 $\mathrm{p}$ 和 $\mathrm{q}$ 给计算出来了
p、q比较接近时，可以使用这种攻击方法
# 费马分解
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 | \xb8\xbc\xa2S)s\xcd\xd2 | |
| Frame8 | t is a f | 低指数广播攻击 |
| Frame9 | ||
| Frame10 | will get | 费马分解法 |
| Frame11 | \xb8\xbc\xa2S)s\xcd\xd2 | |
| Frame12 | t is a f | 低指数广播攻击 |
| Frame13 | ||
| Frame14 | ||
| Frame15 | \xb8\xbc\xa2S)s\xcd\xd2 | |
| 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.“
参考链接
-
[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
-
[Twenty Years of Attacks on the RSA Cryptosystem] https://www.ams.org/notices/199902/boneh.pdf
-
[On using Pollard’s p-1 Algorithm to Factor RPrime RSA Modulus] https://www.scitepress.org/Papers/2018/100836/100836.pdf
完整代码
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=['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):
Frame_name='Frame'+str(i)
if Frame_name in sloved:
print(Frame_name+':')
print(sloved[Frame_name])
else:
print(Frame_name+':Not sloved')