基礎(chǔ)知識點(diǎn)
分解質(zhì)因數(shù)難題
取兩個(gè)很大的素?cái)?shù)P1第煮、P2
假設(shè)都是長度都在150位左右
求積N = P1 * P2
N長度300多位
若只知道N，倒推計(jì)算P1放仗、P2是非常復(fù)雜的
同余
符號：≡
兩個(gè)整數(shù)a润绎、b，若它們除以整數(shù)m所得的余數(shù)相等诞挨，則稱a與b對于模m同余或a同余于b模m莉撇。
記作：a≡b (mod m)
例如 26≡2(mod 12)
a與b對m取模的結(jié)果一樣，相減后自然能整除m
歐拉函數(shù)（Phi函數(shù)）φ(N)
定義： 1~ N 中與 N 互質(zhì)的數(shù)的個(gè)數(shù)叫歐拉函數(shù)
對于任何質(zhì)數(shù)P
φ(P) = P - 1
因?yàn)橘|(zhì)數(shù)跟比它小的數(shù)都沒有公約數(shù)
如果a惶傻，b互質(zhì)，有φ(a*b)= φ(a) * φ(b)
例：φ(7 * 11) = φ(7) * φ(11) = 6 * 10 = 60
對應(yīng)【分解質(zhì)因數(shù)難題】
φ(N) = φ(P1) * φ(P2)
歐拉定理
對任意兩個(gè)正整數(shù) a, n银室，如果兩者互質(zhì)涂佃，那么 a^φ(n)≡1(mod n)励翼。
時(shí)鐘算術(shù)
例：
明文m = 3
取模（Modulus）N = 17
指數(shù)（Exponent） E，公開的
計(jì)算余數(shù)(Remainder) c = m ^ E mod N
| 指數(shù)Exponent | 余數(shù)Remainder(m ^ E mod N) |
|---|---|
| 1 | 3 |
| 2 | 9 |
| 3 | 10 |
| 4 | 13 |
| 5 | 5 |
| 6 | 15 |
| 7 | 11 |
| 8 | 16 |
| ... | ... |
結(jié)論：
若只知道一組E辜荠、c汽抚、N，則很難反推出m
解密過程：
c ^ d mod N = m
已知：m ^ E mod N = c
得 (m ^ E) ^ d mod N = m
即 m ^ (E * d) mod N = m
E為加密侨拦，公開的殊橙，公鑰
d為解密，私鑰
因此需要一個(gè)方法構(gòu)建一對密鑰E和d
E會(huì)公開狱从，而d要很難被計(jì)算出來
實(shí)踐
生成一對密鑰
生成兩個(gè)同位數(shù)的素?cái)?shù)
P1 = 53
P2 = 59
N = P1 * P2 = 3127
φ(N) = (P1 - 1) * (P2 - 1) = 52 * 58 = 3016
選公鑰e（條件如下）
- 必須是質(zhì)數(shù)
- 1 < 公鑰 < φ(N)
- 和φ(N)沒有公約數(shù)
在此選擇了e = 3
計(jì)算私鑰d（條件如下）
- (d * e) % φ(N) = 1
即 d = (k * φ(N) + 1) / e
原因：
根據(jù)【歐拉定理】
n是非常大的兩個(gè)素?cái)?shù)相乘
自然滿足
m ^ φ(n) ≡ 1 (mod n)
變換（兩邊都自乘k次）
m ^ (k * φ(n)) ≡ (1^k) (mod n)
即
m ^ (k * φ(n)) ≡ 1 (mod n)
再變換（兩邊同乘以m）
m ^ (k * φ(n)) * m ≡ (1 * m) (mod n)
即
m ^ (k * φ(n) + 1) ≡ m (mod n)
可得 e * d = k * φ(n) + 1
經(jīng)計(jì)算k=2時(shí)有解
d = (2 * φ(N) + 1) / e = (2 * 3016 + 1) / 3 = 2011
公鑰(e,N)分發(fā)
私鑰(d,N)自己保留
加密
明文m = hi 填充法轉(zhuǎn)化為
m = 89
計(jì)算密文c = m ^ e mod N
= 89 ^ 3 mod 3016
= 1394
解密
c ^ d mod N
= 1394 ^ 2011 mod 3127
= 89
= m（明文）
注：私鑰加密的密文膨蛮，用公鑰也能解密
