學(xué)一點(diǎn)有趣的數(shù)論知識
在探究RSA算法的原理之前疮胖，我們先來學(xué)習(xí)一點(diǎn)有趣的數(shù)論知識（數(shù)學(xué)分支之一粒没，主要研究整數(shù)的性質(zhì)）肆糕。你會發(fā)現(xiàn)一些簡單的數(shù)學(xué)知識竟然背后有如此神奇的魔力判沟。
質(zhì)數(shù)
說起質(zhì)數(shù)，想必大家不陌生了恶导，一個(gè)大于1的整數(shù)除了其本身和1之外浆竭，不存在因數(shù)則被稱為質(zhì)數(shù)或者是素?cái)?shù)。比如2惨寿、3邦泄、5、7等裂垦。在小學(xué)課堂里顺囊，我們可能只是記住了這個(gè)概念，但是這里我談下自己的一些思考幫助大家理解蕉拢，質(zhì)數(shù)就好比是構(gòu)成數(shù)字的基本元素特碳，想想看，氫分子僅由兩個(gè)氫原子（組成一個(gè)氫分子）構(gòu)成晕换，那么一個(gè)非質(zhì)數(shù)的6=3*2 即表示為6是由兩個(gè)“3”元素或3個(gè)“2”元素構(gòu)成午乓。其中“3”或者“2”是不可以繼續(xù)拆分的元素（3，2都是質(zhì)數(shù)）闸准。所以對一個(gè)非質(zhì)數(shù)進(jìn)行因式分解過程就好比對一個(gè)物體進(jìn)行深入解剖益愈，拆分至不可拆分的元素為止。這樣看來夷家，數(shù)學(xué)家們提出這些數(shù)學(xué)概念蒸其，其實(shí)也是一種對數(shù)字世界的認(rèn)識和思考的概括敏释，和我們?nèi)粘Ｉ罾斫庵苓吺挛锓绞揭彩窍嗨频摹?/p>
互質(zhì)關(guān)系
知道了質(zhì)數(shù)，我們再看看互質(zhì)關(guān)系枣接，那么什么是互質(zhì)呢颂暇？就是說兩個(gè)數(shù)沒有相同的因數(shù)稱為互質(zhì)關(guān)系。我們對6進(jìn)行因數(shù)分解但惶，拆分到質(zhì)數(shù)的乘積即6＝3* 2而 35=5*7,這兩者沒有相同的因數(shù)則稱6與35互質(zhì)耳鸯，就好像氫氣分子只是由氫原子構(gòu)成，而氧氣分子只是由氧原子構(gòu)成膀曾，這二者這間沒有相同的原子就是一種互質(zhì)的體現(xiàn)县爬。
所以互質(zhì)只是一個(gè)數(shù)和數(shù)之間有沒有相同的因數(shù)關(guān)系的體現(xiàn)(公約數(shù)也稱公因數(shù))，和兩者是不是質(zhì)數(shù)是沒有關(guān)系的添谊。當(dāng)然質(zhì)數(shù)之間必然是互質(zhì)關(guān)系财喳，因?yàn)樗鼈兌际菢?gòu)成數(shù)字的不同元素。數(shù)學(xué)上來表示a,b互質(zhì)一般用gcd(a,b)=1來表示斩狱。即a和b的最大公約數(shù)是1.
歐拉的思考之歐拉定理與歐拉函數(shù)
質(zhì)數(shù)和互質(zhì)的關(guān)系是不是很容易理解耳高？但是大數(shù)學(xué)家歐拉先生可絕不僅僅停步于此，數(shù)學(xué)家嘛總愛問一下抽象概括性的問題所踊，希望找尋規(guī)律比如
任意給定正整數(shù)n泌枪，請問在小于等于n的正整數(shù)之中，有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系秕岛？（比如碌燕，在1到10之中，有多少個(gè)數(shù)與10構(gòu)成互質(zhì)關(guān)系继薛？）
如果能找到規(guī)律修壕，無論數(shù)字如何千變?nèi)f化10位數(shù)還是100000位數(shù)，我們都能根據(jù)準(zhǔn)則輕易計(jì)算數(shù)互質(zhì)關(guān)系的數(shù)量遏考。你發(fā)現(xiàn)了沒有慈鸠，數(shù)字也是一片世界，真是一花一世界一葉一如來罢┟蟆林束！好了回歸正傳，對于這個(gè)問題歐拉先生給出了他的答案稽亏。他是這樣作答的：
首先呢上述問題可以簡化為一個(gè)函數(shù)來描述即：\Phi(n)
這也是數(shù)學(xué)家老毛病在他們看來任何問題就是對函數(shù)的求解。既然這個(gè)函數(shù)由歐拉提出來的缕题，那么我們就稱他為歐拉函數(shù).還好這個(gè)函數(shù)簡單只有一個(gè)變量截歉，即給定的正整數(shù)n。接下來就要分析這個(gè)n
歐拉函數(shù)
n=1的情況
n＝1的時(shí)候這個(gè)問題極其簡單：
\Phi(n)＝1
因?yàn)?與任何數(shù)包含他自身都構(gòu)成互質(zhì)關(guān)系烟零。1本身也是質(zhì)數(shù)且不作為其他數(shù)的因數(shù)瘪松，因?yàn)槿魏螖?shù)乘以1都是其本身
n是質(zhì)數(shù)的情況
大家想想看n是質(zhì)數(shù)咸作，其自身就不存在因數(shù)了，而那些與他非互質(zhì)關(guān)系(存在公約數(shù))的數(shù)進(jìn)行因式分解后一定都會有一個(gè)因數(shù)與n相等宵睦。比如n＝3為一個(gè)質(zhì)數(shù)记罚，那么6＝3*2與3是非互質(zhì)關(guān)系，因?yàn)榇嬖诠s數(shù)3壳嚎。所以我們發(fā)現(xiàn)與n非互質(zhì)關(guān)系的數(shù)都是n的倍數(shù)即(kn)桐智，因?yàn)閗n>=n所以與n互質(zhì)的數(shù)都小于n即
\Phi(n)＝n-1
n不是質(zhì)數(shù)的情況
還記得我們前面提到的質(zhì)數(shù)嗎，他可是構(gòu)成數(shù)字的元素呀烟馅，所以如果n不是質(zhì)數(shù)说庭，那么他一定可以被因式分解拆分成多個(gè)質(zhì)數(shù)的乘積。比如24=6*4=3*8=2*2*2*3 比如6=2*3郑趁，這些質(zhì)數(shù)因數(shù)相互乘積也可以形成如下情況：
n演變?yōu)閮蓚€(gè)互質(zhì)的數(shù)的乘積
我們把相同質(zhì)數(shù)因數(shù)進(jìn)行相乘刊驴，很容易將一個(gè)非質(zhì)數(shù)分解為兩個(gè)互質(zhì)關(guān)系的數(shù)的乘積，比如24=6*4=2*2*2*3＝3*8
從簡單的情況來考慮寡润，即n被拆分為兩個(gè)互質(zhì)關(guān)系的數(shù)的乘積：
即
n=p*q
p與q互質(zhì)捆憎，那么根據(jù)剩余定理:
\Phi \left( pq\right) =\Phi(p)*\Phi(q)
至于如何證明呢？說實(shí)話我也不清楚梭纹。在我理解看來躲惰，與24互質(zhì)的數(shù)都有這樣一個(gè)特點(diǎn)：他進(jìn)行因式分解后其因數(shù)不包含有3與2（因?yàn)?=2*2*2）。所以與3互質(zhì)的數(shù)定義為集合A栗柒，且個(gè)數(shù)為
\Phi \left( 3\right)
與8互質(zhì)的數(shù)定義為集合B礁扮，且個(gè)數(shù)為
\Phi \left( 8\right)
這AB兩組的數(shù)字可以在組與組間兩兩進(jìn)行組合乘積，構(gòu)成與24互質(zhì)的數(shù)瞬沦。所以兩組數(shù)字個(gè)數(shù)相乘就可以知道乘積的組合個(gè)數(shù)太伊，也就知道與24互質(zhì)的個(gè)數(shù)了。這樣的證明并不嚴(yán)謹(jǐn)?shù)们铱梢韵扔涀 ?br>
另外還需要記住歐拉函數(shù)是一個(gè)積性函數(shù),也就是n如果為多個(gè)互質(zhì)的數(shù)構(gòu)成即(n=a*b*c*d.... )逛钻，那么
\Phi \left( n\right)=\Phi \left( a\right) *\Phi \left( b\right)....
n演變?yōu)橘|(zhì)數(shù)的多次方
也就是n為某一個(gè)質(zhì)數(shù)的倍數(shù)僚焦，比如27=3*3*3=3^3 27就是3的倍數(shù)。那么小于27且存在非互質(zhì)關(guān)系的數(shù)一定都是3的倍數(shù)也就是：1*3曙痘、2*3,3*3...9*3 共計(jì)9個(gè)芳悲， 所以3^3 - 9 ＝3^3 - 3^2 .所以歸納一下也就是說如果p是質(zhì)數(shù)，求與p^n 互質(zhì)的數(shù)的個(gè)數(shù)边坤，只要將如下的數(shù)
(1*p)名扛、(2*p)、(3*p)茧痒、....(p^n-1 *p) 進(jìn)行剔除肮韧，剩余的都將與p^n （切記p是質(zhì)數(shù)）互質(zhì)所以我們得出：
\Phi \left( p^{k}\right)=p^{k}-p^{k-1}＝p^{k}(1-\dfrac {1}{p} )
當(dāng)k＝1的時(shí)候即
\Phi \left( p\right)=p-1
又回到了之前n為質(zhì)數(shù)的情況下的表達(dá)式。這里我們也看到數(shù)學(xué)追求簡潔和普適性的思想，再繁雜的規(guī)律都可以變成一個(gè)簡潔抽象的表達(dá)式弄企。
n演變?yōu)槎鄠€(gè)不同質(zhì)數(shù)的積
比如24=6*4=3*8=2*2*2*3超燃，因?yàn)橘|(zhì)數(shù)之間就是互質(zhì)關(guān)系而且質(zhì)數(shù)的多次方也是互質(zhì)關(guān)系所以
我們把24演變一下：24=2^3 * 3即把相同的質(zhì)數(shù)進(jìn)行合并為質(zhì)數(shù)的多次方。這樣2^3 與3是互質(zhì)關(guān)系(質(zhì)數(shù)的多次方之間也都是互質(zhì)關(guān)系)拘领，于是當(dāng)我們求與24互質(zhì)的數(shù)的個(gè)數(shù)時(shí)候意乓，就可以套用之前公式即：
\Phi \left(24\right)=\Phi \left( 2^{3}*3\right)=\Phi \left(2^3\right)*\Phi \left(3\right)=(2^{3}-2^{3-1})(3-1) =8
再進(jìn)一步歸納因?yàn)閜1、 p2...pm等都是質(zhì)數(shù)且
n = p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}
則由于歐拉函數(shù)是積性函數(shù)约素，那么：
\Phi \left(n\right)=\Phi \left( p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}\right) =\Phi \left( p_{1}^{k_{1}}\right)* \Phi \left( p_{2}^{k_{2}}\right)*...\Phi \left( p_{m}^{k_{m}}\right)
由上一小節(jié)n為質(zhì)數(shù)的多次方的結(jié)論
\Phi \left( p^{k}\right)=p^{k}-p^{k-1}＝p^{k}(1-\dfrac {1}{p} )
可以得出：
\Phi \left( p_{1}^{k_{1}}\right)* \Phi \left( p_{2}^{k_{2}}\right)*...\Phi \left( p_{m}^{k_{m}}\right)=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{m}^{k_{m}}*(1-\dfrac {1}{p_{1}} )*(1-\dfrac {1}{p_{2}})...(1-\dfrac {1}{p_{m}} )
則
\Phi \left(n\right)=n*(1-\dfrac {1}{p_{1}} )*(1-\dfrac {1}{p_{2}})...(1-\dfrac {1}{p_{m}})
此時(shí)我們?nèi)匀挥?jì)算24互質(zhì)個(gè)數(shù)則
\Phi \left(24\right)=\Phi \left( 2^{3}*3\right)=\Phi \left(2^3\right)*\Phi \left(3\right)=24*(1-\dfrac {1}{2})(1-\dfrac {1}{3})＝8
歐拉函數(shù)的總結(jié)
上面說的那么多其實(shí)歸結(jié)起來就是這樣一個(gè)道理：當(dāng)我們?nèi)デ笮∮谀硞€(gè)數(shù)范圍內(nèi)與其互質(zhì)的數(shù)的個(gè)數(shù)時(shí)候届良，無非就是把n分為質(zhì)數(shù)還是非質(zhì)數(shù)。
對于質(zhì)數(shù)：
\Phi \left(n\right)=n-1對于非質(zhì)數(shù)：
我們都可以將非質(zhì)數(shù)進(jìn)行因式分解形成多個(gè)質(zhì)數(shù)的乘積业汰，我們把相同的因數(shù)進(jìn)行歸并伙窃，即將2*2*3*5=2^2 *3*5），使得n的乘積因子都為互質(zhì)關(guān)系样漆，這樣就可以套用如下公式
\Phi \left(n\right)=n*(1-\dfrac {1}{p_{1}} )*(1-\dfrac {1}{p_{2}})...(1-\dfrac {1}{p_{m}})
歐拉定理
知道了歐拉函數(shù)为障，接下來我們再理解一個(gè)同余概念，簡單來說也就是25除以3的余數(shù)為1放祟，而1除以2的余數(shù)為1鳍怨，則我們稱25與1對于模3同余數(shù)，用人話來說就是25和1 除以2得到的余數(shù)都一樣跪妥。求余數(shù)的過程在數(shù)學(xué)里的黑話叫取模鞋喇。所以才有上面那么拗口的說法。但是不要緊眉撵，數(shù)學(xué)喜歡簡單不啰嗦侦香，于是搞出了如下的表達(dá)式來表達(dá)上述說法：
25\equiv 1\left( mod\ 3\right)
也就是說
25 \% 3 = 1\%3=1
注意到了嗎？上述表達(dá)式也可以這樣表述纽疟，即25除以3得到的余數(shù)為1.圍繞著同余這個(gè)概念罐韩，歐拉大師結(jié)合他的歐拉函數(shù)活脫脫就搞出了個(gè)歐拉定理，我們來看看他有什么發(fā)現(xiàn)污朽？
如果兩個(gè)正整數(shù)a與n互質(zhì)散吵，則通過n的歐拉函數(shù)可以得出
a^{\Phi \left(n\right)}\equiv 1\left( mod\ n\right)
如果n為質(zhì)數(shù)則n的φ(n)（小于p的整數(shù)范圍內(nèi)與p互質(zhì)關(guān)系的個(gè)數(shù)）等于n-1，則歐拉定理可以寫成：
a^{n-1}\equiv 1\left( mod\ n\right)
而這樣一個(gè)同余表達(dá)式又叫做費(fèi)爾馬小定理
另外根據(jù)取模運(yùn)算的規(guī)則：
a^蟆肆\%p = ((a \% p)^矾睦) \% p
我們還可以得出
（a^{\Phi \left(n\right)})^{k}\equiv 1\left( mod\ n\right)
因?yàn)?br>
(a^{\Phi \left(n\right)})^{k} \% n=（a^{\Phi \left(n\right)}\%n)^{k}\%n=1^k\%n =1
我們舉個(gè)例子：比如
{\Phi \left(10\right)}＝{\Phi \left(2*5\right)}={\Phi \left(2\right)}*{\Phi \left(5\right)}=(2-1)*(5-1)=4
所以根據(jù)歐拉定理：因?yàn)?與10互質(zhì)所以
9^{\Phi \left(10\right)}=9^4\equiv 1\left( mod\ 10\right)
于是(9^4 )^k 除以10都余1。
模反元素
如果a與n互質(zhì)炎功，則必然能夠找到一個(gè)數(shù)使得
ab\equiv 1\left( mod\ n\right)
則b稱為a的模反元素枚冗，我們可以通過歐拉定理來給予證明
a^{\Phi \left(n\right)}=1\left( mod\ n\right)
a^{\Phi \left(n\right)}= a*a^{\Phi \left(n\right)-1}\equiv 1\left( mod\ n\right)
模反元素的概念對后續(xù)在已知道公鑰情況下，計(jì)算合適的私鑰是有很重要的意義的蛇损。
掌握了這些數(shù)學(xué)知識官紫，你可能覺得這些東西似乎很孤立肛宋，看不到任何作用和價(jià)值州藕，不過接下來我們來看看RSA是怎么運(yùn)作的束世，你就會發(fā)現(xiàn)這些看似毫無作用的東西是如何產(chǎn)生價(jià)值的。
RSA究竟如何運(yùn)作床玻？
RSA 實(shí)現(xiàn)方式：
- 找出兩個(gè)很大的且不相等的質(zhì)數(shù)P和Q
- 求出他們的乘積n=p*q
- 才有歐拉函數(shù)計(jì)算小于n范圍內(nèi)與n互質(zhì)的個(gè)數(shù)毁涉。這一結(jié)果我們姑且定義為為m，因?yàn)閜與q互質(zhì)所以
m={\Phi \left(n\right)} = {\Phi \left(p*q\right)}=(p-1)*(q-1) - 在1<e<M選取一個(gè)整數(shù)e锈死，要求e與m互質(zhì)贫堰。
- 尋找一個(gè)整數(shù)d，使得
E*D \equiv 1(mod\ M)
這也就是我們前面提及的模反元素的知識待牵，因?yàn)閑與m互質(zhì)其屏，則必然能夠找到d使得上述表達(dá)式成立。 - 到此為止缨该，我們完成了公私秘鑰對的創(chuàng)建工作偎行，即(e,n)是公鑰，(d,n)是私鑰贰拿。更準(zhǔn)確的來說n被稱為模數(shù)蛤袒，e稱為公開指數(shù)，而d稱為私密指數(shù)膨更。
- 此時(shí)我們有一串明文信息x妙真，則我們使用公鑰E加密即x^E mod n =y,y為加密后的數(shù)據(jù)
- 當(dāng)我們拿到y(tǒng)通過私鑰d執(zhí)行Y^d mod n = x即可解密。
從加解密的表達(dá)式可以看出在荚守，數(shù)學(xué)原理上公鑰和私鑰其實(shí)并沒有什么差異珍德。你可以用公鑰加密、私鑰解密矗漾，也可以用私鑰加密锈候，公鑰進(jìn)行解密。但是對于密碼學(xué)來說缩功，對公鑰和私鑰會有不同的要求晴及。
另外需要注意的是這里明文數(shù)值不能大于等于N，否則解密的結(jié)果并不會等于明文嫡锌。
RSA有效性證明
因?yàn)榧用艿墓綖椋?br>
x^e mod n = y
而解密公式為
y^d mod n = x
從上面表達(dá)式可以看出在數(shù)學(xué)原理上公鑰和私鑰其實(shí)并沒有什么差異虑稼。你可以用公鑰加密、私鑰解密势木，也可以用私鑰加密蛛倦，公鑰進(jìn)行解密。
所以根據(jù)：
y=x^e - kn
且因?yàn)閅^D mod N = x 所以
y^D \equiv x (mod\ n)
所以確定能否加解密的過程本質(zhì)就是證明：
（x^e - kn)^d \equiv x (mod\ n)（1.1）
而根據(jù)二項(xiàng)式定理
[圖片上傳失敗...(image-ca75c7-1530364603810)]
（x^e - kn)^d 展開后演變?yōu)?br>
x^ed-m_{1}x^{e(d-1)}kn+m_{2}x^{e(d-2)}(kn)^2...m_{n}(kn)^eeibbw7
你會發(fā)現(xiàn)二項(xiàng)式展開后啦桌，唯有x^ed 沒有包含n溯壶，因此結(jié)合模運(yùn)算加法運(yùn)算規(guī)則(a + b) % p = (a % p + b % p) % p 及皂，要想證明1.1的表達(dá)式，則必然證明：
x^{ed} \equiv x (mod\ n)
由于
ed \equiv 1 (mod\ {\Phi \left(n\right)})
所以
ed=h{\Phi \left(n\right)})+1
則從證明
x^{ed} \equiv x (mod\ n) 演變?yōu)樽C明
x^{h{\Phi \left(n\right)}}*x\equiv x (mod\ n)
如果x與n 互質(zhì)則根據(jù)歐拉定理
x^{{\Phi \left(n\right)}}\equiv 1 (mod\ n)
基于在歐拉定理中提及的且改，根據(jù)取模運(yùn)算規(guī)則可以得出
x^{h{\Phi \left(n\right)}}\equiv 1 (mod\ n)
仍然是基于取模運(yùn)算乘法規(guī)則验烧，我們又可以得出
x^{h{\Phi \left(n\right)}}x\equiv x (mod\ n)
這樣原式得到證明。
那么如果x與n不互質(zhì)的情況下又跛，因?yàn)閚=p*q且p和q都是質(zhì)數(shù)碍拆，所以n的因數(shù)只有p和q了，因?yàn)閤與n不互質(zhì)慨蓝，那么我們可以認(rèn)為：
x=k_{1}p 0 < u< q
或者
x=k_{2}q 0 < k
請注意k值的取值范圍感混，這里要牢記一點(diǎn)明文值必須大于0且小于n值。
這里我們先姑且定義
x=kq
0 < k< p
那么因?yàn)閜與q都是質(zhì)數(shù)礼烈，根據(jù)k<p 我們可以認(rèn)為k與p是互質(zhì)的弧满，而p本身就是質(zhì)數(shù)，所以根據(jù)費(fèi)爾馬小定理（n
為質(zhì)數(shù)此熬，a與n互質(zhì)庭呜，如果有所遺忘可以回到前面查看相關(guān)說明。）
a^{n-1}\equiv 1\left( mod\ n\right)
那么
(kq)^{p-1}\equiv 1\left( mod\ p\right)
根據(jù)費(fèi)爾馬定理我們推得出來的表達(dá)式
a^{\Phi \left(n\right)}\equiv 1\left( mod\ n\right)
得出
((kq)^{p-1})^{h*(q-1)}\equiv 1\left( mod\ p\right)
也就是
(kq)^{h*(q-1)(p-1)}\equiv 1\left( mod\ p\right)
根據(jù)取模運(yùn)算的運(yùn)算定義：
給定一個(gè)正整數(shù)p摹迷，任意一個(gè)整數(shù)n疟赊，一定存在等式 ：
n = kp + r ；
其中 k峡碉、r 是整數(shù)近哟，且 0 ≤ r < p，則稱 k 為 n 除以 p 的商鲫寄，r 為 n 除以 p 的余數(shù)吉执。
得出
(kq)^{h*(q-1)(p-1)} = 1+u*p
這里的u為任意整數(shù)，這時(shí)候兩邊都乘以kq
(kq)^{h*(q-1)(p-1)}*kq = 1+u*k*q*p
因?yàn)閚=pq x=kq那么
(x)^{\Phi \left(n\right)+1} = x+u*k*n
還是根據(jù)之前取模運(yùn)算定義得出
(x)^{h\Phi \left(n\right)+1}\equiv x\left( mod\ n\right)
即原式得到了證明地来。
RSA的安全性理論
之所以RSA是安全的戳玫，很大程度取決于n值是否足夠大以至于在已知公鑰e和模數(shù)n的情況下仍然難以找出d。根據(jù)之前的談及的密鑰對計(jì)算方式：
E*D \equiv 1(mod\ M)
要想算出D就必須計(jì)算出M 而M = (p-1)(q-1) 未斑，n=p*q則要算出M就需要知道p和q咕宿，即從一個(gè)龐大的數(shù)中分離出兩個(gè)也很大的質(zhì)數(shù)。大數(shù)的素因數(shù)分解被認(rèn)為是一個(gè)困難的問題蜡秽，即使是現(xiàn)代的計(jì)算機(jī)也非常難于處理府阀，所以許多加密系統(tǒng)的原理都是建基于此。
目前最安全的做法是選擇使用rsa-2048芽突，隨著2009年12月12日试浙，編號為RSA-768（768 bits, 232 digits）數(shù)也被成功分解。這一事件威脅了現(xiàn)通行的1024-bit密鑰的安全性寞蚌。這里的2048表示的是模數(shù)N
的二進(jìn)制位為2048位田巴。而一般公鑰世面上普遍選擇65535钠糊，這是安全性和計(jì)算速度之間的綜合考慮下選擇出來的一個(gè)比較妥當(dāng)?shù)臄?shù)值。因?yàn)榧咏饷芎瘮?shù)都是在做大數(shù)的指數(shù)運(yùn)算壹哺，所以在工程方面會盡量考慮公鑰加解密的執(zhí)行速度抄伍，畢竟公鑰是被外部使用的。
此外還記得前面提到rsa加密的明文數(shù)值大小不能大于N斗躏，或者其位數(shù)不能超過N的位數(shù)的限制逝慧。一旦超過密文解密后和原文數(shù)據(jù)不相匹配，這時(shí)候就需要采用分段加密技術(shù)啄糙。而另一方面明文的值也不能為0或1，-1因?yàn)檫@樣導(dǎo)致密文也是0云稚，1或者-1隧饼。另外也有一個(gè)問題即如果用私鑰解密一段非法數(shù)據(jù)，那么得到是解密失敗還是一個(gè)毫無意義的解密內(nèi)容呢静陈？這時(shí)候需要采用 rsa padding技術(shù)燕雁。對這個(gè)概念理解可以參考淺談RSA Padding這篇文章。
總結(jié)
通過學(xué)習(xí)一些簡單的數(shù)論知識即質(zhì)數(shù)鲸拥、歐拉函數(shù)拐格、模反元素等概念后，我們也了解RSA算法大致過程刑赶，總的來說公私密鑰對需要計(jì)算如下幾個(gè)數(shù)據(jù)：
- 很大的質(zhì)數(shù) p
- 很大的質(zhì)數(shù) q
- 兩個(gè)質(zhì)數(shù)乘積：n = p*q
- 小于n范圍內(nèi)捏浊，與n互質(zhì)的數(shù)個(gè)數(shù)：φ(n)
- 0~φ(n) 中的某個(gè)與φ(n)互質(zhì)的數(shù)E
- E的模反元素D
RSA的安全性不僅僅建立于大數(shù)質(zhì)因數(shù)分解困難這一理論基礎(chǔ)上，在工程上如何對上述這些數(shù)值的選取也是很大的學(xué)問撞叨。通過對rsa學(xué)習(xí)讓我對工程和理論之間的關(guān)系理解上更進(jìn)一步金踪。理論確定了方向的可行性，而工程實(shí)踐則要確保在有限資源下牵敷，理論結(jié)果是可以應(yīng)用起來解決特定規(guī)模的問題胡岔。而在加密算法領(lǐng)域，一旦工程實(shí)踐出現(xiàn)偏差枷餐，往往就容易產(chǎn)生安全漏洞靶瘸，盡管算法理論證明是安全的。比如rsa中p q值的選擇等毛肋。這里我羅列幾個(gè)工程問題有興趣的童鞋可以再進(jìn)一步做探索：
如何確定一個(gè)數(shù)是質(zhì)數(shù)怨咪？RSA周邊——大素?cái)?shù)是怎樣生成的？
如何選取安全的p q值村生，可以參考RSA 生成公私鑰時(shí)質(zhì)數(shù)是怎么選的惊暴？
如何快速找到模反元素即D
另外，加密解密公式是需要做大數(shù)值的指數(shù)計(jì)算趁桃，所以如何快速進(jìn)行指數(shù)計(jì)算呢辽话？
