部分1：基礎題型

Jarvis OJ - Basic - easyRSA

題目給出了e和n以及密文c，題目要求明文m，解題思路是根據n求出p和q，然後根據e，p，q求出d，再根據c，d，n求出明文m。

如何求p和q呢，這裡涉及到素數的分解，linux下一般可直接執行命令 factor去分解它， factor 322831561921859 ，但是factor能分解的數的長度不是特別大。當n有點大的時候可以命令列下使用這個命令（推薦） factordb 322831561921859 （需要安裝python模組，pip install factordb-pycli），如果n再大點，就直接去這個網站線上分解n：

http：//

factordb。com/

，般可直接如果n大的不行，就算了吧，肯定不是分解n去解題，一定有別的方法。

首先求p和q（解出的p和q順序無所謂）

解題指令碼：

#！/usr/bin/python

#coding：utf-8

#@Author：醉清風

import libnum

from Crypto。Util。number import long_to_bytes

c = 0xdc2eeeb2782c

n = 322831561921859

e = 23

q = 13574881

p = 23781539

d = libnum。invmod（e， （p - 1） *（q - 1））

m = pow（c， d， n）

print “m的值為：”

print long_to_bytes（m）

關於long_to_bytes與bytes_to_long百度一下就知道了，關於如何記住pow裡面的變數順序，我記得好像有個cdn加速來，靠諧音就記住了，有興趣的可以瞭解一下CDN（內容分發網路） 關於求d，也就是模逆運算，下面的數學基礎中會講。

Jarvis OJ - Crypto- MediumRSA

不容易啊，終於從Basic到了Crypto了，現在的題目才開始慢慢變得像話了。

題目給出2個檔案，如下圖所示：

其中flag。enc是密文，pubkey。pem是公鑰，很明顯正常的話是必須要有私鑰才可以解開密文，但是這裡加密的強度不高，所以可以直接解開，下面咱們一起來乾點壞事O（∩_∩）O哈！（關於什麼公鑰，私鑰之類的基礎知識建議看一下對稱加密和非對稱加密的基礎知識，百度/google一下就行）

現在我們只知道密文c，其他的都不知道，怎麼辦呢，這裡我們要讀取公鑰檔案pubkey。pem （使用命令openssl提取私鑰資訊）

公鑰檔名

首先把n由16進位制轉為10進位制，接著分解n得到p和q。

現在有了n，p，q，e，c，所以可以根據p，q求phi，再根據phi和e求d，接著根據c，d，n即可求出明文m。

詳細的openssl使用可以參考連結：

解題指令碼：openssl常用命令，簽名、非對稱加解密 - kk Blog —— 通用基礎解題指令碼：

#！/usr/bin/python

#coding：utf-8

#@Author：醉清風

import libnum

from Crypto。Util。number import long_to_bytes

n = 87924348264132406875276140514499937145050893665602592992418171647042491658461

p = 275127860351348928173285174381581152299

q = 319576316814478949870590164193048041239

e = 65537

phi = （p-1）*（q-1）

d = libnum。invmod（e，phi）

with open（‘。/flag。enc’） as f：

c = f。read（）。encode（‘hex’）

c = int（c，16）

m = pow（c，d，n）

print long_to_bytes（m）

或者

#！/usr/bin/python

#coding：utf-8

#@Author：醉清風

import gmpy2

from Crypto。Util。number import long_to_bytes

n = 87924348264132406875276140514499937145050893665602592992418171647042491658461

p = 275127860351348928173285174381581152299

q = 319576316814478949870590164193048041239

e = 65537

phi = （p-1）*（q-1）

d = gmpy2。invert（e，phi）

with open（‘。/flag。enc’） as f：

c = f。read（）。encode（‘hex’）

c = int（c，16）

m = pow（c，d，n）

print long_to_bytes（m）

關於檔案形式的密文c，一般都是16進位制形式讀取，接著再轉為整型用於計算。上面的讀取程式碼有點冗餘了，後面的題目會有更簡潔的讀取方式。

gmpy2和libnum的效果都是一樣的，接下來題目就按照我愛用的gmpy2介紹吧。

存貨0——babyRSA

真的忘了題目是哪個比賽的題，就叫存貨吧

題目：

p+q ：

0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea

（p+1）（q+1）：

0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740

e ：

0xe6b1bee47bd63f615c7d0a43c529d219

d：

0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5

enc_flag：

0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

題目給出了p+q，（p+1）（q+1），e，d，c 當時做這題的時候就蒙了，n在哪？ p，q呢？ 我是誰？ 我在哪？ 仔細想了一會，拿本子列了一下等式關係，呀，出來了。

思路：

（p+1）（q+1）=p*q+p+q+1=n+（p+q）+1=題目已給出值（設為y）

所以n=y-（p+q+1）

設x=p+q+1

所以n=y-x

phi=（p-1）（q-1）

=p*q-p-q+1

=p*q-（p+q）+1

=n-x+2

d = gmpy2。invert（e，phi）

m = pow（c，d，n）

解題指令碼：

#！/usr/bin/python

#coding：utf-8

#@Author：醉清風

import gmpy2

from Crypto。Util。number import long_to_bytes

x = 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea + 1

y = 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740

c = 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

e = 0xe6b1bee47bd63f615c7d0a43c529d219

n = y-x

phi = n-x+2

d =gmpy2。invert（e，phi）

m = pow（c，d，n）

print long_to_bytes（m）

其實這個題也不是很難哈，就是什麼替換一下什麼的的數學小遊戲罷了。真正難的在最後面。

感謝評論區的大佬 @Tiger 1218 給了它個名分。該題目取自GUET-CTF 2019中的BabyRSA。

部分2：數學基礎

這部分是我從別人那裡搬來的，然後做了一點點的修改，我覺得吧，還是應該看點這部分數學原理的。畢竟越往深了學，用到的數學知識就越多。話說數學好的人是真的優秀，作為學習網路工程的人，在我眼裡，偉大的夏農是通訊方面的大佬，沒想到的是他個職業的數學家，和密碼學專家，業餘無聊搞一搞通訊，太狠了。

如果實在看不懂可以跳過這部分，進入下個標題的學習。不要看都沒看就跳過哈。哪怕稍微看點再看下一篇也行。

參考連結：

RSA應用流程

上面講的公鑰和私鑰產生多半是大白話的，下面是偏數學上的介紹，也很好理解啦：

選取兩個較大的互不相等的質數p和q，計算n = p * q 。

計算phi = (p-1) * (q-1) 。

選取任意e，使得e滿足 1<e<phi 且 gcd(e , phi) == 1 。

計算e關於n的模逆元d， 即d滿足(e * d)% n ==1 。

加解密：c = (m ^ e) % n ， m = (c ^ d) % n 。其中m為明文，c為密文，(n,e)為公鑰對，d為私鑰，要求 0 <= m < n 。

理解模逆運算

如果(a*b)%c==1 ，那麼a和b互為對方模c的模逆元/數論倒數，也寫作mod_inv 。

關於最大公約數有一個基本事實：給予兩整數a、c，必存在整數x、y使得ax + cy = gcd(a,c) ，基於這個事實，當a,c互素即gcd(a,c)==1 時，有ax+cy=1 ，那麼就有(a*x)%c==1 ，所以x就是a 對c的模逆元。因此，a對c存在模逆元b的充要條件是gcd(a,c)==1 。顯然對於每一組a,c ，存在一族滿足條件的x，在求模逆元時我們取得是最小正整數解x mod n 。

上述的基本事實很容易理解，因為a和c的最大公約數是gcd(a,b)，所以a和c都可表示為gcd(a,b)的整數倍，那麼a和b的任意整係數的線性組合ax+by也必定能表示成gcd(a,c)的整數倍，他們當中最小的正整數就應該是gcd(a,c)。實際上最大公約數有一個定義就是：a和b的最大公約數g是a和b的線性和中的最小正整數 。

求模逆元主要基於擴充套件歐幾里得演算法，貼一個Python實現：

#！/usr/bin/python

#coding：utf-8

#47模30的逆為23

def egcd （ a ， b ）：

if （b == 0）：

return 1， 0， a

else：

x ， y ， q = egcd（ b ， a % b ） # q = GCD（a， b） = GCD（b， a%b）

x ， y = y， （ x - （a // b） * y ）

return x， y， q

def mod_inv（a，b）：

#return egcd（a，b）［0］%b #求a模b得逆元

print egcd（a，b）［0］%b

def main（）：

a = 47

b = 30

mod_inv（a，b）

if __name__==“__main__”：

main（）

或者(推薦)

#！/usr/bin/python

#coding：utf-8

#@Author：醉清風

#求47模30的逆為23

import gmpy2

print gmpy2。invert（47，30）

熟悉吧，前面求d的時候用的就是這個。

模意義下的運演算法則

(a + b) % n ≡ (a % n + b % n) % n

(a - b) % n ≡ (a % n - b % n) % n

(a * b) % n ≡ (a % n * b % n) % n

(a ^ b) % n ≡ ((a % n) ^ b) % n //冪運算

若 a ≡ b(mod n) ,則

1.對於任意正整數c,有a^c ≡ b^c(mod n)

2.對於任意整數c,有ac ≡ bc(mod n),a+c ≡ b+c(mod n),

3.若 c ≡ d(mod n),則a-c ≡ b-d(mod n),a+c ≡ b+d(mod n),ac ≡ bd(mod n)

如果ac≡bc (mod m)，且c和m互質，則a≡b (mod m）。

[理解：當且僅當c和m互質,c^-1存在,等式左右可同乘模逆。]

除法規則：

在模n意義下，a/b不再僅僅代表這兩個數相除，而是指 a+k1*n 和 b+k2*n這兩個組數中任意兩個相除，使商為整數

因此也就可以理解，除以一個數等價於乘以它的逆

a/b ≡ c(mod n) <=> a ≡ c*(b^-1) (mod n)，其中b模n的逆記作b的負一次方。

費馬小定理:

a是整數,p是質數,則a^p==a(mod p),如果a不是p的倍數,還有a^(p-1) ≡ 1(mod p)

歐幾里得演算法

歐幾里得演算法是求最大公約數的演算法, 也就是中學學的 輾轉相除法 。記 gcd(a,b) 為a和b的最大公約數。

歐幾里得演算法的基本原理是gcd(a,b)==gcd(b,a%b),(b!=0) 和 gcd(a,0)==a 。

# 遞迴版

def gcd（a， b）：

return a if not b else gcd（b， a % b）

# 迭代版

def gcd2（a， b）：

while b：

a， b = b， a % b

return a

擴充套件歐幾里得演算法

擴充套件歐幾里得演算法基於歐幾里得演算法，能夠求出使得 ax+by=gcd(a,b) 的一組x,y。

對照下圖和以下遞迴版實現容易理解。

python實現如下：

# 遞迴版

def ext_euclid （ a ， b ）：

# ref：https：//zh。wikipedia。org/wiki/擴充套件歐幾里得演算法

if （b == 0）：

return 1， 0， a

else：

x1 ， y1 ， q = ext_euclid（ b ， a % b ） # q = GCD（a， b） = GCD（b， a%b）

x ， y = y1， （ x1 - （a // b） * y1 ）

return x， y， q

# 迭代版

def egcd（a， b）：

# ref：https：//blog。csdn。net/wyf12138/article/details/60476773

if b == 0：

return （1， 0， a）

x， y = 0， 1

s1， s2 = 1， 0

r， q = a % b， a / b

while r：

m， n = x， y

x = s1 - x * q

y = s2 - y * q

s1， s2 = m， n

a， b = b， r

r， q = a % b， a / b

return （x， y， b）

中國剩餘定理

python實現如下：

def CRT（mi， ai）：

# mi，ai分別表示模數和取模後的值，都為列表結構

# Chinese Remainder Theorem

# lcm=lambda x ， y：x*y/gcd（x，y）

# mul=lambda x ， y：x*y

# assert（reduce（mul，mi）==reduce（lcm，mi））

# 以上可用於保證mi兩兩互質

assert （isinstance（mi， list） and isinstance（ai， list））

M = reduce（lambda x， y： x * y， mi）

ai_ti_Mi = ［a * （M / m） * gmpy2。invert（M / m， m） for （m， a） in zip（mi， ai）］

return reduce（lambda x， y： x + y， ai_ti_Mi） % M

以上程式將mi當作兩兩互質處理，實際上有時會遇到其他情況，這時就需要逐一兩兩合併方程組。我（不是我）參照下圖實現了一個互質與不互質兩種情況下都能工作良好的中國剩餘定理（解同餘方程組）的Python程式。

def GCRT（mi， ai）：

# mi，ai分別表示模數和取模後的值，都為列表結構

assert （isinstance（mi， list） and isinstance（ai， list））

curm， cura = mi［0］， ai［0］

for （m， a） in zip（mi［1：］， ai［1：］）：

d = gmpy2。gcd（curm， m）

c = a - cura

assert （c % d == 0） #不成立則不存在解

K = c / d * gmpy2。invert（curm / d， m / d）

cura += curm * K

curm = curm * m / d

cura %= curm

return （cura % curm， curm） #（解，最小公倍數）

好了，如果都看到這裡了的話，說明你的資質還是挺高的，給你點個贊。