說明：本文使用的數(shù)據(jù)來自網(wǎng)絡(luò)，重復(fù)的太多了，也不知道哪篇是原創(chuàng).

算法原理介紹

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：明文

stepdecriptionequationnote

1	Find the prime pairs	P 、Q	-
2	Calculate the common module	N = P * Q	-
3	euler function	φ(N) = (P-1)(Q-1)	-
4	Calculate the public key - E	1 < E < φ(N)	E must be an integer E and φ(N) are prime numbers
5	Calculate the private key - D	E * D % φ(N) = 1	-
6	encryption	C ＝ ME mod N	C：ciphertext ,M：plaintext
7	decryption	M ＝CD mod N	C：ciphertext ,M：plaintext

算法舉例

• 隨機(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都算出來了，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，所以無需推導(dǎo).

---

相關(guān)推薦：
?????????[crypto]-01-對(duì)稱加解密AES原理概念詳解
?????????[crypto]-02-非對(duì)稱加解密RSA原理概念詳解
?????????[crypto]-03-數(shù)字摘要HASH原理概念詳解
?????????[crypto]-04-國產(chǎn)密碼算法（國密算法sm2/sm3/sm4）介紹
?????????[crypto]-05-轉(zhuǎn)載:PKCS #1 RSA Encryption Version 1.5介紹
?????????[crypto]-05.1-PKCS PKCS#1 PKCS#7 PKCS#11的介紹
?????????[crypto]-06-CA證書介紹和使用方法


?????????[crypto]-30-The Armv8 Cryptographic Extension在linux中的應(yīng)用
?????????[crypto]-31-crypto engion的學(xué)習(xí)和總結(jié)


?????????[crypto]-50-base64_encode和base64_decode的C語言實(shí)現(xiàn)
?????????[crypto]-51-RSA私鑰pem轉(zhuǎn)換成der, 在將der解析出n e d p q dp dq qp
?????????[crypto]-52-python3中rsa(簽名驗(yàn)簽加密解密)aes(ecb cbc ctr)hmac的使用,以及unittest測(cè)試用
?????????[crypto]-53-openssl命令行的使用（aes/rsa簽名校驗(yàn)/rsa加密解密/hmac）


?????????[crypto]-90-crypto的一些術(shù)語和思考

總結(jié)

以上是生活随笔為你收集整理的[crypto]-02-非对称加解密RSA原理概念详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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