1、什么是RSA？

RSA是一種公鑰密碼算法，它的名字由三位開發(fā)者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母組成的。 RSA被用于公鑰密碼和數(shù)字簽名。 1983年，RSA公司為RSA算法在美國(guó)取得了專利，但現(xiàn)在該專利已經(jīng)過期。

2、算法原理介紹

step說明描述備注

1	找出質(zhì)數(shù)	P 、Q	-
2	計(jì)算公共模數(shù)	N = P * Q	-
3	歐拉函數(shù)	φ(N) = (P-1)(Q-1)	-
4	計(jì)算公鑰E	1 < E < φ(N)	E的取值必須是整數(shù) E 和 φ(N) 必須是互質(zhì)數(shù)
5	計(jì)算私鑰D	E * D % φ(N) = 1	-
6	加密	C ＝ ME mod N	C：密文 M：明文
7	解密	M ＝CD mod N	C：密文 M：明文

3、算法舉例

• 隨機(jī)選擇兩個(gè)不相等的質(zhì)數(shù) : p=61、q=53
• 計(jì)算 n = p × q = 61×53 = 3233
• 計(jì)算n的歐拉函數(shù) : φ(n) = (p-1)(q-1) = 3120
• 隨機(jī)選擇一個(gè)整數(shù)e，條件是1< e < φ(n)，且e與φ(n) 互質(zhì), 我們選擇一個(gè) e=17
• 計(jì)算e對(duì)于φ(n)的模反元素d ： d*e%φ(n)=1

支持 n e d都算出來(lái)了，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）

公鑰能否推導(dǎo)出私鑰，也就是n和e的情況下，推導(dǎo)出d

• （1）ed%φ(n)=1, 推導(dǎo)d, 需要知道e和φ(n)
• （2）φ(n)=(p-1)(q-1)。計(jì)算φ(n), 需要知道p和q
• （3）n=pq。只有將n因數(shù)分解，才能算出p和q.

私鑰能否推導(dǎo)出公鑰，也就是n和d的情況下，推導(dǎo)出e

• （1）ed%φ(n)=1, 推導(dǎo)e, 需要知道d和φ(n)
• （2）φ(n)=(p-1)(q-1)。計(jì)算φ(n), 需要知道p和q
• （3）n=pq。只有將n因數(shù)分解，才能算出p和q.

對(duì)于3233您可以進(jìn)行因數(shù)分解（3233=61×53），那么對(duì)于下面一個(gè)這樣很大的數(shù)字呢？

12301866845301177551304949
　　58384962720772853569595334
　　79219732245215172640050726
　　36575187452021997864693899
　　56474942774063845925192557
　　32630345373154826850791702
　　61221429134616704292143116
　　02221240479274737794080665
　　351419597459856902143413

它等價(jià)于：

33478071698956898786044169
　　84821269081770479498371376
　　85689124313889828837938780
　　02287614711652531743087737
　　814467999489
　　　　×
　　36746043666799590428244633
　　79962795263227915816434308
　　76426760322838157396665112
　　79233373417143396810270092
　　798736308917

公鑰(e,n)對(duì)明文m進(jìn)行加密 ： c = m^e % n
私鑰(d,n)對(duì)密文c進(jìn)行解密 ： m = c^d % n

其中e和d是對(duì)等的，一樣的地位，可以互換的. 所以，公鑰推出私鑰比較困難，那么私鑰推出公鑰也是比較困難.
另外，在密碼學(xué)中，我們一般不說通過公鑰并不是完全不能推算出私鑰， 而是表述為：通過公鑰推算私鑰在計(jì)算上是困難的。

那么為什么我們?cè)谄綍r(shí)使用時(shí)，感覺的是公鑰不能推導(dǎo)私鑰，但私鑰可以推導(dǎo)公鑰呢？
因?yàn)樵赑EM或DER的編碼格式中，公鑰包含了N和E，私鑰包含了N E D P Q等信息，也就是私鑰已經(jīng)包含了公鑰，故私鑰是能推出公鑰的。
另外在通常使用中，e一般就等于65535，所以無(wú)需推導(dǎo).

4、RSA的用法

公鑰加密、私鑰解密
私鑰簽名、公鑰驗(yàn)簽

總結(jié)

以上是生活随笔為你收集整理的05-密码学基础-RSA的介绍的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。