【Crypto】 題目鏈接 【RSA演算法解密】
?審題分析?
首先拿到一個壓縮包，解壓得到檔案enc.txt， 先不用去管其他，第一眼enc馬上聯想到 RSA解密，接著往下看
[{"c": 7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042, "e": 10, "n": 25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c": 21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461, "e": 10, "n": 23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c": 6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983, "e": 10, "n": 18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c": 4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052, "e": 10, "n": 23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c": 22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672, "e": 10, "n": 31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c": 17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087, "e": 10, "n": 22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c": 1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639, "e": 10, "n": 25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c": 15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352, "e": 10, "n": 32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c": 8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797, "e": 10, "n": 52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c": 13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247, "e": 10, "n": 30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}]
給出 十組RSA（enc）加密資訊，且十組的e都相同，這里涉及到三個引數：
e / c ：c要滿足 ： e * c = 1 (mod(p-1) * (q-1))
n : n = p * q（p和q是兩個不同的大素數）
{ e , n } 為公開密鑰 { c , n } 為私有密鑰
詳情可參考 阮一峰RSA演算法
?低加密指數廣播攻擊?
推一波大佬的總結： 詳情戳這里
低加密指數廣播攻擊
介紹：
如果選取的加密指數較低，并且使用了相同的加密指數給一個接受者的群發送相同的資訊，那么可以進行廣播攻擊得到明文，即，選取了相同的加密指數e（這里取e=3），對相同的明文m進行了加密并進行了訊息的傳遞，那么有：
$ c_1equiv m^e$ $mod$ $n_1$
$ c_2equiv m^e$ $mod$ $n_2$
$ c_3equiv m^e$ $mod$ $n_3$
對上述等式運用中國剩余定理，在e=3時，可以得到：
$ c_xequiv m^3$ $mod$ $n_1n_2n_3$
通過對$ c_x $進行三次開方可以求得明文，
識別：
這個識別起來比較簡單，一般來說都是給了三組加密的引數和明密文，其中題目很明確地能告訴你這三組的明文都是一樣的，并且e都取了一個較小的數字，
?環境準備?
-
python2.x -- python3.x環境準備 -
libnum
-
gmpy2（重頭戲）
python2.x -- python3.x 環境準備
第一個相信大家都已經準備好了，
安裝 libunm
如何下載 libunm庫 只需打開 cmd 視窗，執行該命令即可：
pip install libnum -i https://pypi.mirrors.ustc.edu.cn/simple/
-i 后面接的是鏡像源，加速下載， 可以換源 自取，
阿里云 http://mirrors.aliyun.com/pypi/simple/
中國科技大學 https://pypi.mirrors.ustc.edu.cn/simple/
豆瓣(douban) http://pypi.douban.com/simple/
清華大學 https://pypi.tuna.tsinghua.edu.cn/simple/
中國科學技術大學 http://pypi.mirrors.ustc.edu.cn/simple/
若是下載失敗或者在pycharm里運行還是顯示沒有該模塊，則我們可以采取直接法，直接在pycharm里下載該庫，
先打開pycharm -> settings -> Project Interpreter -> "+" -> 輸入 libnum ->下載 -> 完成，
這里提一句： 點擊下方紅框按鈕，進行添加鏡像，下載速度會更快哦~鏡像源在上面已經給出，可自取！
若出現 不信任報錯，手動修改 http 為 https 即可！
順帶一提：在做RSA解題時經常會碰到 import crypto 如題【攻防世界】 cr3-what-is-this-encryption
import libnum
from Crypto.Util.number import long_to_bytes
安裝pycryptodome
缺少crypto模塊怎么辦？
法一： pip 安裝
法二： pycharm 里直接安裝 crypto ，發現找不到？！ 實際上應安裝
pycrypto即可，(法一法二均與上述libnum模塊安裝一致)
法三：pycharm里面直接安裝
pycryptodome模塊（PS：像博主這種倒霉蛋pycrypto又沒安成功，只好曲線救國）
這樣就萬事大吉啦~~
Windows下 -- gmpy2安裝
最后一項 下載 gmpy2庫 這可真是太折騰了， 博主親測：
-
第一種：與上述裝 libnum庫 一樣，直接 pip 或者 pycharm 里安裝 ， （反正倒霉蛋我是不行的）
-
第二種：利用pip 安裝 .whl 輪子檔案 成功上岸！！
首先，確定自己的python 版本 ，可直接 用
python -version查看，下面，來這個 寶藏之地 找到
GMPY板塊， 根據自己的python版本來進行相應的下載，比如說，博主的python環境是 python3.8 ，并且，電腦是64版本，那就下載相對應的
gmpy2?2.0.8?cp38?cp38?win_amd64.whl的檔案 即可，
安裝后，進入你安裝的python環境的目錄，打開
Script檔案夾，將剛下載好的.whl檔案拖進去，然后在此處打開 cmd視窗 ，或者是 Powershell ， 執行以下命令 ： 注意！！.whl檔案名一定要復制完整！！
C:\Program Files\Python38\Scripts> pip install gmpy2?2.0.8?cp38?cp38?win_amd64.whl這樣就安裝成功啦！！
Kali Linux下安裝 RsaCtfTools
RsaCtfTools 也是解Rsa題目的必備神器， 如何安裝，大家可以康康大佬的這篇 kail下安裝RsaCtfTool
(博主親測安裝很順利)
但是！！ 在安裝mpfr時 ，記得將命令換成這條哦！不然會404
wget https://www.mpfr.org/mpfr-current/mpfr-4.1.0.tar.bz2在執行
pip install -r requirements.txt時，記得 先回傳 RsaCtfTool目錄中哦cd ../ cd ../友情提醒一下 RsaCtfTool.py 是 python3 噠
python2 pip 安裝 ：
apt-get install python-pippython3 pip3 安裝 ：
apt-get install python3-pip
python -V查看當前版本~
Successful!!!
?解題腳本?
萬事俱備，只欠東風~接下來可以解題了，利用 中國剩余定理 來進行撰寫解密腳本 借鑒網上大佬腳本：這里
python3.x 腳本
import libnum
import gmpy2
dic =[{"c":7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042, "e": 10, "n":25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c":21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461, "e": 10, "n":23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c":6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983, "e": 10, "n":18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c":4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052, "e": 10, "n":23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c":22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672, "e": 10, "n":31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c":17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087, "e": 10, "n":22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c":1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639, "e": 10, "n":25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c":15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352, "e": 10, "n":32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c":8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797, "e": 10, "n":52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c":13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247, "e": 10, "n":30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}]
n = []
C = []
for i in dic:
n.append(i["n"])
C.append(i["c"])
N = 1
for i in n:
N *= i
Ni = []
for i in n:
Ni.append(N // i)
T = []
for i in range(10):
T.append(int(gmpy2.invert(Ni[i], n[i])))
X = 0
for i in range(10):
X += C[i] * Ni[i] * T[i]
m10 = X % N
m = gmpy2.iroot(m10, 10)
print (libnum.n2s(m[0]))
python2.x 腳本
import libnum
import gmpy2
dic =[{"c":7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042, "e": 10, "n":25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c":21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461, "e": 10, "n":23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c":6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983, "e": 10, "n":18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c":4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052, "e": 10, "n":23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c":22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672, "e": 10, "n":31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c":17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087, "e": 10, "n":22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c":1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639, "e": 10, "n":25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c":15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352, "e": 10, "n":32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c":8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797, "e": 10, "n":52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c":13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247, "e": 10, "n":30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}]
n = []
C = []
for i in dic:
n.append(i["n"])
C.append(i["c"])
N = 1
for i in n:
N *= i
Ni = []
for i in n:
Ni.append(N / i)
T = []
for i in xrange(10):
T.append(long(gmpy2.invert(Ni[i], n[i])))
X = 0
for i in xrange(10):
X += C[i] * Ni[i] * T[i]
m10 = X % N
m = gmpy2.iroot(m10, 10)
print libnum.n2s(m[0])
- python2.x和python3.x環境腳本存在三個不同
Ni.append(N / i)在Python3中，N / i回傳的是float型別，float最大值為1.7976931348623157e+308因此會報錯OverflowError: integer division result too large for a float所以要將它繞過，用//代替/，這樣回傳的是Integer，T.append(long(gmpy2.invert(Ni[i], n[i])))在Python3中，不存在long()函式，直接改為int()就可
綜上！！得到flag啦~~
flag{wo0_th3_tr4in_i5_leav1ng_g3t_on_it}
?結語?
關于以上鏈接參考【侵權刪】
第一次寫博客，多多擔待！若有錯誤之處還請多多指正~!
【轉載請放鏈接】 https://www.cnblogs.com/Jlay/p/RSA_Environment.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71771.html
標籤：其他
上一篇：對三次握手和四次揮手簡單理解
下一篇：簡單快速搭建釣魚wifi