题目摘要
赛题名称: RSA 加密体制破译
赛题描述
RSA密码算法是使用最为广泛的公钥密码体制。该体制简单且易于实现,只需要选择5个参数即可(两个素数𝑝 𝑝 p 和𝑞 𝑞 q 、模数𝑁 = 𝑝 𝑞 𝑁=𝑝𝑞 N = pq 、加密指数𝑒 𝑒 e 和解密指数𝑑 𝑑 d 。设𝑚为待加密消息RSA体制破译相当于已知𝑚 𝑒 𝑚^𝑒 m e m o d mod m o d 𝑁 𝑁 N 能否还原𝑚的数论问题。目前模数规模为1024比特的RSA算法一般情况下是安全的,但是如果参数选取不当,同样存在被破译的可能。
有人制作了一个RSA加解密软件采用的RSA体制的参数特点描述见密码背景部分)。已知该软件发送某个明文的所有参数和加密过程的全部数据(加密案例文件详见附件3-1。Alice使用该软件发送了一个通关密语,且所有加密数据已经被截获,请问能否仅从加密数据恢复该通关密语及RSA体制参数?如能请给出原文和参数,如不能请给出已恢复部分并说明剩余部分不能恢复的理由?
加密过程
原始明文
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.每个使用者,任意选择两个大素数𝑝 𝑝 p 和𝑞 𝑞 q ,并求出其乘积𝑁 = 𝑝 𝑞 𝑁=𝑝𝑞 N = pq 。
Step2.令𝜑(𝑁)=(𝑝−1)(𝑞−1)选择整数𝑒 𝑒 e ,使得GCD(𝑒,𝜑(𝑁))=1,并求出𝑒 𝑒 e 模 𝜑(𝑁)的逆元𝑑 𝑑 d ,即𝑒𝑑≡1 mod (𝜑(𝑁))
Step3.将数对( 𝑒 , 𝑁 ) (𝑒,𝑁) ( e , N ) 公布为公钥,𝑑 𝑑 d 保存为私钥。
2)加解密过程
Bob欲传递明文𝑚给 Alice,则Bob首先由公开途径找出 Alice 的公钥 ( 𝑒 , 𝑁 ) (𝑒,𝑁) ( e , N ) ,Bob 计算加密的信息𝑐 𝑐 c 为:𝑐 ≡ 𝑚 𝑒 𝑐 ≡ 𝑚^𝑒 c ≡ m e m o d mod m o d 𝑁 𝑁 N 。
Bob 将密文𝑐 𝑐 c 传送给 Alice。 随后 Alice 利用自己的私钥𝑑 𝑑 d 解密:
𝑐 e ≡ ( 𝑚 𝑒 ) 𝑑 ≡ 𝑚 𝑒 𝑑 ≡ 𝑚 m o d 𝑁 𝑐^e ≡ (𝑚^𝑒)^𝑑 ≡ 𝑚^{𝑒𝑑}≡ 𝑚\space mod\space 𝑁 c e ≡ ( m e ) d ≡ m e d ≡ m m o d N
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 m o d N m^e\space mod \space N m e m o d 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 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条消息依次为
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={} sloved=[] filename=['RSA\data\Frame' +str (i) for i in range (0 ,21 )] for i in range (0 ,21 ): f=open (filename[i],'r' ) data=f.read() n.append(int (data[:256 ],16 )) e.append(int (data[256 :512 ],16 )) c.append(int (data[512 :],16 )) for i in range (0 ,21 ): print ('e[' +str (i)+']=' +str (e[i])) for i in range (0 ,21 ): print ('n[' +str (i)+']=' +str (n[i])) 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)+']' ) 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' ) 结果
遍历所有加密指数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],还因为可能存在重复发包
设两个用户的公钥分别为 e 1 e_1 e 1 和 e 2 e_2 e 2 ,且两者互质。明文消息为 m m m ,密文分别为:
c 1 = m e 1 m o d n c 2 = m e 2 m o d n \begin{aligned}
&c_1=m^{e_1} \bmod n \\
&c_2=m^{e_2} \bmod n
\end{aligned}
c 1 = m e 1 mod n c 2 = m e 2 mod n
当攻击者截获 c 1 c_1 c 1 和 c 2 c_2 c 2 后,就可以恢复出明文。用扩展欧几里得算法求出 r e 1 + s e 2 = 1 m o d n r e_1+s e_2=1 \bmod n r e 1 + s e 2 = 1 mod n 的两个整数 r r r 和 s s s ,由此可得:
c 1 r c 2 s ≡ m r e 1 m s e 2 m o d n ≡ m ( r e 1 + s e 2 ) m o d n ≡ m m o d n \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}
c 1 r c 2 s ≡ m r e 1 m s e 2 mod n ≡ m ( r e 1 + s e 2 ) mod n ≡ m mod 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 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 m=hex (m)[2 :] m=binascii.unhexlify(m)[-8 :] 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 p p 或者 q q q 在多个RSA加密中出现多次,那么生成不同的 n \mathrm{n} n 可能会有相同的因子,我们假设 p \mathrm{p} p 相同,q \mathrm{q} q 不同,那么在
{ n 1 = p ∗ q 1 n 2 = p ∗ q 2 \left\{\begin{array}{l}
n_1=p * q_1 \\
n_2=p * q_2
\end{array}\right.
{ n 1 = p ∗ q 1 n 2 = p ∗ q 2
很容易知道
gcd ( n 1 , n 2 ) = p \operatorname{gcd}\left(n_1, n_2\right)=p
gcd ( n 1 , n 2 ) = 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 :] m18=hex (m18)[2 :] m1=binascii.unhexlify(m1)[-8 :] m18=binascii.unhexlify(m18)[-8 :] sloved['Frame1' ]=m1 sloved['Frame18' ]=m18
‘Frame1’: b’. Imagin’, ‘Frame18’: b’m A to B’
低指数广播攻击
Frame3、Frame8、Frame12、Frame16、Frame20采用该种攻击方法
低加密指数广播攻击适合于n \mathrm{n} n 很大,e e e 很小的情况, 其适用的情况是如n \mathrm{n} n 下的,当一条消息m m m 发送给不同的接收者时,每个接收者的 n n n 都不同,但是加密公钥都是相同的,我们假设公钥为3那么就有
{ C 1 = m 3 m o d n 1 C 2 = m 3 m o d n 2 C 3 = m 3 m o d 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.
⎩ ⎨ ⎧ C 1 = m 3 mod n 1 C 2 = m 3 mod n 2 C 3 = m 3 mod n 3
由中国剩余定理知道,我们是可以将 m 3 m^3 m 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=1 for a,n in backup: N*=n Ni=[] for a,n in backup: Ni.append(N//n) Ni_inverse=[] for i in range (0 ,len (Ni)): Ni_inverse.append(gmpy2.invert(Ni[i],backup[i][1 ])) x=0 for i in range (0 ,len (Ni)): x+=backup[i][0 ]*Ni[i]*Ni_inverse[i] x=x%N return x,N 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 :] m=binascii.unhexlify(m)[-8 :] sloved['Frame7' ]=m sloved['Frame11' ]=m sloved['Frame15' ]=m 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 :] m=binascii.unhexlify(m)[-8 :] 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 e e 阶的多项式 f f f , 那么可以:
Pollard p-1分解法
Frame2、Frame6、Frame19均采用该种攻击方法
如果 p p p 与 q q q 都不超过 1 0 20 10^{20} 1 0 20 次方, 若其中一个 ( p − 1 ) (p-1) ( p − 1 ) 或 ( q − 1 ) (q-1) ( q − 1 ) 的因子都很小的时候(适用于p-1或q-1能够被小素数整除的情况,在这里为了方便说明我们假设为 ( p − 1 ) ) (p-1)) ( p − 1 )) ,可以如下操作:
选取一个整数 k k k , 使其满足 ( p − 1 ) ∣ k ! (p-1) \mid k! ( p − 1 ) ∣ k ! ,由费马小定理知道, a a a 与 p p p 互素 的时候有
a p − 1 = 1 m o d p a^{p-1}=1 \bmod p
a p − 1 = 1 mod p
所以 a k ! = 1 m o d p , a^{k !}=1 \bmod p \quad, \quad a k ! = 1 mod p , 即 p ∣ ( a k ! − 1 ) \mathrm{p} \mid\left(a^{k !}-1\right) p ∣ ( a k ! − 1 ) 。 那么对于 n \mathrm{n} n 与 ( a k ! − 1 ) \left(a^{k !}-1\right) ( a k ! − 1 ) 必有公因数为 p \mathrm{p} p , 这样就可以把 n \mathrm{n} n 分解出来了。 但是对于 k k k 的选取还是有要求的,太小了 ( p − 1 ) ∣ k ! (p-1) \mid k ! ( p − 1 ) ∣ k ! 不会成立,太大了花费时间会很多。
Pollard p-1 Factoring Algorithm ( n , B ) (\mathrm{n}, \mathrm{B}) ( n , B ) :
a ← 2 B ! ( m o d n ) a \leftarrow 2^{B !}(\bmod n) a ← 2 B ! ( mod n )
d ← gcd ( a − 1 , n ) d \leftarrow \operatorname{gcd}(a-1, n) d ← gcd ( a − 1 , n )
if 1 < d < n 1<d<n 1 < d < n then return d d d 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 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 :] m=binascii.unhexlify(m)[-8 :] sloved['Frame' +str (i)]=m
‘Frame2’: b’ That is’, ‘Frame6’: b’ "Logic ‘, ‘Frame19’: b’instein.’
费马分解法
如果 p p p 和 q q q 相差不大的话我们可以通过费马分解把 p p p 和 q q q 求出来, 原理如 下
n = p ∗ q = 1 4 ( p + q ) 2 − 1 4 ( p − q ) 2 \mathrm{n}=\mathrm{p} * \mathrm{q}=\frac{1}{4}(p+q)^2-\frac{1}{4}(p-q)^2
n = p ∗ q = 4 1 ( p + q ) 2 − 4 1 ( p − q ) 2
由于 p \mathrm{p} p 与 q \mathrm{q} q 相差不大, 所以 p − q \mathrm{p}-\mathrm{q} p − q 相对于 n \mathrm{n} n 和 ( p + q ) 2 (p+q)^2 ( p + q ) 2 来说可以忽略不计, 所以有~
2 n ≈ p + q 2 \sqrt{\mathrm{n}} \approx \mathrm{p}+\mathrm{q}
2 n ≈ p + q
也就是说通过不断尝试就可以把 p \mathrm{p} p 和 q \mathrm{q} 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 :] m=binascii.unhexlify(m)[-8 :] sloved['Frame' +str (i)]=m
经检验,Frame10可以采用该种攻击方法
‘Frame10’: b’will get’
综上
整理一下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
[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 binasciiimport gmpy2import mathn=[] e=[] c=[] m={zip (['Frame' +str (i) for i in range (0 ,21 )],'' )} sloved={} filename=['RSA\data\Frame' +str (i) for i in range (0 ,21 )] for i in range (0 ,21 ): f=open (filename[i],'r' ) data=f.read() n.append(int (data[:256 ],16 )) e.append(int (data[256 :512 ],16 )) c.append(int (data[512 :],16 )) 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)+']' ) 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 m=hex (m)[2 :] m=binascii.unhexlify(m)[-8 :] 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 :] m18=hex (m18)[2 :] m1=binascii.unhexlify(m1)[-8 :] m18=binascii.unhexlify(m18)[-8 :] sloved['Frame1' ]=m1 sloved['Frame18' ]=m18 def chinese_remainder_theorem (backup ): N=1 for a,n in backup: N*=n Ni=[] for a,n in backup: Ni.append(N//n) Ni_inverse=[] for i in range (0 ,len (Ni)): Ni_inverse.append(gmpy2.invert(Ni[i],backup[i][1 ])) x=0 for i in range (0 ,len (Ni)): x+=backup[i][0 ]*Ni[i]*Ni_inverse[i] x=x%N return x,N 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 :] m=binascii.unhexlify(m)[-8 :] sloved['Frame7' ]=m sloved['Frame11' ]=m sloved['Frame15' ]=m 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 :] m=binascii.unhexlify(m)[-8 :] 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 :] m=binascii.unhexlify(m)[-8 :] sloved['Frame' +str (i)]=m 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 :] m=binascii.unhexlify(m)[-8 :] 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_data(n) print (sloved) for i in range (1 ,21 ): if sloved['Frame' +str (i)]: print (sloved['Frame' +str (i)])