結(jié)論：
加密和解密使用同樣規(guī)則（簡(jiǎn)稱"密鑰"）锚国，這被稱為"對(duì)稱加密算法"
RSA是一種非對(duì)稱加密的算法赋荆，為什么會(huì)有這個(gè)澡罚，先說(shuō)對(duì)成加密，對(duì)稱就是同一個(gè)密鑰加密解密闰围，不安全元旬，
SSL是基于非對(duì)稱加密的原理榴徐，在這之上還進(jìn)行了對(duì)稱加密的數(shù)據(jù)傳輸
對(duì)成加密的話：
（1）甲方選擇某一種加密規(guī)則守问，對(duì)信息進(jìn)行加密；
（2）乙方使用同一種規(guī)則坑资，對(duì)信息進(jìn)行解密耗帕。
因?yàn)榧用芤?guī)則是相同的，所以最好是一份數(shù)據(jù)袱贮，或者一個(gè)客戶一個(gè)密鑰仿便，每個(gè)人密鑰不能不能隨便公開(kāi)
非對(duì)稱加密的話：
? ? ? ?（1）乙方生成兩把密鑰（公鑰和私鑰）。公鑰是公開(kāi)的攒巍，任何人都可以獲得嗽仪，私鑰則是保密的。
∑饫颉（2）甲方獲取乙方的公鑰闻坚，然后用它對(duì)信息加密。
【ばⅰ（3）乙方得到加密后的信息窿凤，用私鑰解密。
雖然大家都是用的同一個(gè)公鑰加密的西潘，但是只有有密鑰才解得開(kāi)卷玉，隨便你的公鑰怎么傳播
互質(zhì)關(guān)系
如果兩個(gè)正整數(shù)哨颂，除了1以外喷市，沒(méi)有其他公因子，我們就稱這兩個(gè)數(shù)是互質(zhì)關(guān)系（coprime）威恼。比如品姓，15和32沒(méi)有公因子，所以它們是互質(zhì)關(guān)系箫措。這說(shuō)明腹备，不是質(zhì)數(shù)也可以構(gòu)成互質(zhì)關(guān)系。
關(guān)于互質(zhì)關(guān)系斤蔓，不難得到以下結(jié)論：
1. 任意兩個(gè)質(zhì)數(shù)構(gòu)成互質(zhì)關(guān)系植酥，比如13和61。
2. 一個(gè)數(shù)是質(zhì)數(shù)弦牡，另一個(gè)數(shù)只要不是前者的倍數(shù)友驮，兩者就構(gòu)成互質(zhì)關(guān)系，比如3和10驾锰。
3. 如果兩個(gè)數(shù)之中卸留，較大的那個(gè)數(shù)是質(zhì)數(shù)，則兩者構(gòu)成互質(zhì)關(guān)系椭豫，比如97和57耻瑟。
4. 1和任意一個(gè)自然數(shù)是都是互質(zhì)關(guān)系旨指，比如1和99。
5. p是大于1的整數(shù)喳整，則p和p-1構(gòu)成互質(zhì)關(guān)系谆构，比如57和56。
6. p是大于1的奇數(shù)框都，則p和p-2構(gòu)成互質(zhì)關(guān)系低淡，比如17和15。
歐拉函數(shù)
請(qǐng)思考以下問(wèn)題：
任意給定正整數(shù)n瞬项，請(qǐng)問(wèn)在小于等于n的正整數(shù)之中蔗蹋，有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系？（比如囱淋，在1到8之中猪杭，有多少個(gè)數(shù)與8構(gòu)成互質(zhì)關(guān)系？）
計(jì)算這個(gè)值的方法就叫做歐拉函數(shù)妥衣，以φ(n)表示皂吮。在1到8之中，與8形成互質(zhì)關(guān)系的是1税手、3蜂筹、5、7芦倒，所以 φ(n) = 4艺挪，
我有個(gè)蠢的辦法先說(shuō)說(shuō)，互質(zhì)的本質(zhì)是兵扬，兩個(gè)數(shù)的所有公因子麻裳，出了1沒(méi)有交集，所以我們可以先求8的所有公因子（1-8除個(gè)遍器钟，余數(shù)為零的就是他的公因子）津坑，然后剩下的1-8，循環(huán)一遍傲霸，把他們的所有公因子也求出來(lái)疆瑰，對(duì)比兩者的公因子除了1以外還有沒(méi)有交集，沒(méi)有的話昙啄，說(shuō)明兩者互質(zhì)穆役。
或者就是按照文章里的1-6條規(guī)則L一一算一遍
歐拉定理
歐拉函數(shù)的用處，在于歐拉定理跟衅。"歐拉定理"指的是：
如果兩個(gè)正整數(shù)a和n互質(zhì)孵睬，則n的歐拉函數(shù) φ(n) 可以讓下面的等式成立：
也就是說(shuō)，a的φ(n)次方被n除的余數(shù)為1伶跷￡粒或者說(shuō)秘狞，a的φ(n)次方減去1，可以被n整除蹈集。比如烁试，3和7互質(zhì)，而7的歐拉函數(shù)φ(7)等于6拢肆，所以3的6次方（729）減去1减响，可以被7整除（728/7=104）。這他嗎是有點(diǎn)神奇的郭怪，好想看看推導(dǎo)過(guò)程
（3（φ(7)） - 1）= 7*104
歐拉定理的證明比較復(fù)雜支示，這里就省略了。我們只要記住它的結(jié)論就行了鄙才。
歐拉定理可以大大簡(jiǎn)化某些運(yùn)算颂鸿。比如，7和10互質(zhì)攒庵，根據(jù)歐拉定理嘴纺，
已知 φ(10) 等于4，所以馬上得到7的4倍數(shù)次方的個(gè)位數(shù)肯定是1浓冒。
因此栽渴，7的任意次方的個(gè)位數(shù)（例如7的222次方），心算就可以算出來(lái)
模反元素
還剩下最后一個(gè)概念：
如果兩個(gè)正整數(shù)a和n互質(zhì)稳懒，那么一定可以找到整數(shù)b闲擦，使得 ab-1 被n整除，或者說(shuō)ab被n除的余數(shù)是1僚祷。
這時(shí)佛致，b就叫做a的"模反元素"贮缕。
比如辙谜，3和11互質(zhì)，那么3的模反元素就是4感昼，因?yàn)?(3 × 4)-1 可以被11整除装哆。顯然，模反元素不止一個(gè)定嗓， 4加減11的整數(shù)倍都是3的模反元素 {...,-18,-7,4,15,26,...}蜕琴，即如果b是a的模反元素，則 b+kn 都是a的模反元素
3 * 5 - 1 = 7 * 2?
5就是3的模反元素
密鑰生成的步驟
第一步宵溅，隨機(jī)選擇兩個(gè)不相等的質(zhì)數(shù)p和q凌简。互質(zhì)
愛(ài)麗絲選擇了61和53恃逻。（實(shí)際應(yīng)用中雏搂，這兩個(gè)質(zhì)數(shù)越大藕施，就越難破解。）
第二步凸郑，計(jì)算p和q的乘積n裳食。
愛(ài)麗絲就把61和53相乘。
n = 61×53 = 3233
n的長(zhǎng)度就是密鑰長(zhǎng)度芙沥。3233寫成二進(jìn)制是110010100001诲祸，一共有12位，所以這個(gè)密鑰就是12位而昨。實(shí)際應(yīng)用中救氯，RSA密鑰一般是1024位，重要場(chǎng)合則為2048位歌憨。
第三步径密，計(jì)算n的歐拉函數(shù)φ(n)。
根據(jù)公式：
φ(n) = (p-1)(q-1)
愛(ài)麗絲算出φ(3233)等于60×52躺孝，即3120享扔。
第四步，隨機(jī)選擇一個(gè)整數(shù)e植袍，條件是1< e < φ(n)惧眠，且e與φ(n) 互質(zhì)。
愛(ài)麗絲就在1到3120之間于个，隨機(jī)選擇了17氛魁。（實(shí)際應(yīng)用中，常常選擇65537厅篓。）
第五步秀存，計(jì)算e對(duì)于φ(n)的模反元素d。
所謂"模反元素"就是指有一個(gè)整數(shù)d羽氮，可以使得ed被φ(n)除的余數(shù)為1或链。
ed ≡ 1 (mod φ(n))
這個(gè)式子等價(jià)于
ed - 1 = kφ(n)
于是，找到模反元素d档押，實(shí)質(zhì)上就是對(duì)下面這個(gè)二元一次方程求解澳盐。
ex + φ(n)y = 1
已知 e=17, φ(n)=3120，
17x + 3120y = 1
這個(gè)方程可以用"擴(kuò)展歐幾里得算法"求解令宿，此處省略具體過(guò)程叼耙。總之粒没，愛(ài)麗絲算出一組整數(shù)解為 (x,y)=(2753,-15)筛婉，即 d=2753。
至此所有計(jì)算完成癞松。
第六步爽撒，將n和e封裝成公鑰冕碟，n和d封裝成私鑰。
在愛(ài)麗絲的例子中匆浙，n=3233安寺，e=17，d=2753首尼，所以公鑰就是 (3233,17)挑庶，私鑰就是（3233, 2753）。
實(shí)際應(yīng)用中软能，公鑰和私鑰的數(shù)據(jù)都采用ASN.1格式表達(dá)（實(shí)例）迎捺。
七、RSA算法的可靠性
回顧上面的密鑰生成步驟查排，一共出現(xiàn)六個(gè)數(shù)字：
p
q
n
φ(n)
e
d
這六個(gè)數(shù)字之中凳枝，公鑰用到了兩個(gè)（n和e），其余四個(gè)數(shù)字都是不公開(kāi)的跋核。其中最關(guān)鍵的是d岖瑰，因?yàn)閚和d組成了私鑰，一旦d泄漏砂代，就等于私鑰泄漏蹋订。
那么，有無(wú)可能在已知n和e的情況下刻伊，推導(dǎo)出d露戒？
（1）ed≡1 (mod φ(n))捶箱。只有知道e和φ(n)智什，才能算出d。
《∈骸（2）φ(n)=(p-1)(q-1)荠锭。只有知道p和q，才能算出φ(n)悦屏。
〗诼佟（3）n=pq。只有將n因數(shù)分解础爬，才能算出p和q。
結(jié)論：如果n可以被因數(shù)分解吼鳞，d就可以算出看蚜，也就意味著私鑰被破解
加密和解密
有了公鑰和密鑰，就能進(jìn)行加密和解密了赔桌。
（1）加密要用公鑰 (n,e)
假設(shè)鮑勃要向愛(ài)麗絲發(fā)送加密信息m供炎，他就要用愛(ài)麗絲的公鑰 (n,e) 對(duì)m進(jìn)行加密渴逻。這里需要注意，m必須是整數(shù)（字符串可以取ascii值或unicode值）音诫，且m必須小于n惨奕。
所謂"加密"，就是算出下式的c：
me?≡ c (mod n)
愛(ài)麗絲的公鑰是 (3233, 17)竭钝，鮑勃的m假設(shè)是65梨撞，那么可以算出下面的等式：
6517?≡ 2790 (mod 3233)
于是，c等于2790香罐，鮑勃就把2790發(fā)給了愛(ài)麗絲卧波。
（2）解密要用私鑰(n,d)
愛(ài)麗絲拿到鮑勃發(fā)來(lái)的2790以后，就用自己的私鑰(3233, 2753) 進(jìn)行解密庇茫「哿唬可以證明，下面的等式一定成立：
cd?≡ m (mod n)
也就是說(shuō)旦签，c的d次方除以n的余數(shù)為m〔槠海現(xiàn)在，c等于2790宁炫，私鑰是(3233, 2753)咪惠，那么，愛(ài)麗絲算出
27902753?≡ 65 (mod 3233)
因此淋淀，愛(ài)麗絲知道了鮑勃加密前的原文就是65遥昧。
至此，"加密--解密"的整個(gè)過(guò)程全部完成
原文1:http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
原文2:http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
