了解概念
相關(guān)資料https://www.kancloud.cn/kancloud/rsa_algorithm/48493
P : 大質(zhì)數(shù)
Q : 大質(zhì)數(shù)
N(Modulus) : N=P*Q
C : 密文
M : 明文
C＝ME mod N（加密過(guò)程）
M＝CD mod N（解密過(guò)程）
公鑰(E , N) 私鑰(D , N) 密鑰對(duì)(E , D , N)
同余定理
給定一個(gè)正整數(shù)m，如果兩個(gè)整數(shù)a和b滿足（a-b）能夠被m整除，即（a-b）/m得到一個(gè)整數(shù)，那么就稱整數(shù)a與b對(duì)模m同余，記作a≡b(mod m)。
性質(zhì)： 1 反身性 a≡a (mod m)
2 對(duì)稱性 若a≡b(mod m)，則b≡a (mod m)
3 傳遞性 若a≡b (mod m)，b≡c (mod m)，則a≡c (mod m)
4 同余式相加 若a≡b (mod m)，c≡d(mod m)，則a+-c≡b+-d (mod m)
5 同余式相乘 若a≡b (mod m)，c≡d(mod m)，則ac≡bd (mod m)
歐拉函數(shù)
φ(pq)= φ(p) φ(q)=(p-1)(q-1)
歐拉定理
如果兩個(gè)正整數(shù)a和n互質(zhì)，則n的歐拉函數(shù) φ(n) 可以讓下面的等式成立：
aφ(n)≡1 (mod n)即1=aφ(n) mod n
- 費(fèi)馬小定理
假設(shè)正整數(shù)a與質(zhì)數(shù)p互質(zhì)，因?yàn)橘|(zhì)數(shù)p的φ(p)等于p-1，則歐拉定理可以寫成
ap-1≡1 (mod p)
模反元素
如果兩個(gè)正整數(shù)a和n互質(zhì)，那么一定可以找到整數(shù)b，使得 ab-1 被n整除，或者說(shuō)ab被n除的余數(shù)是1。
ab≡1 (mod n)
- 證明
aφ(n)=a × aφ(n)-1≡1 (mod n)
b = aφ(n)-1即可證明存在
密匙生成過(guò)程
- 隨機(jī)選擇兩個(gè)不相等的質(zhì)數(shù)p和q。
- 計(jì)算p和q的乘積n。
- 根據(jù)公式：φ(n) = (p-1)(q-1) 計(jì)算n的歐拉函數(shù)φ(n)
- 隨機(jī)選擇一個(gè)整數(shù)e，條件是1到φ(n)
- 計(jì)算e對(duì)于φ(n)的模反元素d。公式 ed ≡ 1 (mod φ(n))
- ed - 1= kφ(n) e,φ(n)已知 對(duì)k進(jìn)行操作使d為整數(shù)可利用擴(kuò)展歐幾里得算法
- 將n和e封裝成公鑰，n和d封裝成私鑰
如何從C＝ME mod N 推導(dǎo) M＝CD mod N
C＝ME mod N => C = ME - kN
假設(shè) M＝CD mod N成立
帶入可得(ME - kN)D mod N =M => MED mod N =M
由于ED ≡ 1 (mod φ(N)) 所以ED = hφ(N)+1
Mhφ(N)+1 mod N =M
- 當(dāng) M 與 N 互質(zhì)時(shí)根據(jù)歐拉定理，此時(shí) Mφ(N) ≡ 1 (mod N)
則Mhφ(N) × M ≡ 1 (mod N)成立 - 當(dāng) M 與 N 不互質(zhì)
此時(shí)，由于n等于質(zhì)數(shù)p和q的乘積，所以m必然等于kp或kq。以 m = kp為例，考慮到這時(shí)k與q必然互質(zhì)，則根據(jù)歐拉定理，下面的式子成立：
(kp)q-1≡ 1 (mod q) =>(kp)(q-1)h(p-1) × kp ≡ kp (mod q)=>(kp)ed≡ kp (mod q)
(kp)ed=kp +tq (t可整除p) => (kp)ed=kp +xpq => med≡m (mod n) 證畢
后綴名
- .enc 代表 C
- .dec 代表 M
- .pem代表 密鑰
知道C N E解密
- 思路
N 分解為 P Q
h(p-1)(q-1)+1=ed 解得 d
M＝CDmod N - 操作
openssl rsa -pubin -text -modulus -in warmup -in 【public.pem】
可以解出 E 和 N
#python
print(0xN)
轉(zhuǎn)化為十進(jìn)制N
利用 yafu
factorr(N)
解出 p q
python rsatool.py -o 【private.pem】 -e 【65537】 -p 【123】-q 【123】
得到私鑰private.pem
openssl rsautl -decrypt -in 【flag.enc】 -inkey 【private.pem】
私鑰解密
