RSA加密算法是最常用的非對稱加密算法溢谤，CFCA在證書服務(wù)中離不了它。但是有不少新來的同事對它不太了解，恰好看到一本書中作者用實例對它進行了簡化而生動的描述尽爆，使得高深的數(shù)學(xué)理論能夠被容易地理解抬伺。我們經(jīng)過整理和改寫特別推薦給大家閱讀螟够，希望能夠?qū)r間緊張但是又想了解它的同事有所幫助。
RSA是第一個比較完善的公開密鑰算法，它既能用于加密妓笙，也能用于數(shù)字簽名若河。RSA以它的三個發(fā)明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名，這個算法經(jīng)受住了多年深入的密碼分析寞宫，雖然密碼分析者既不能證明也不能否定RSA的安全性萧福，但這恰恰說明該算法有一定的可信性，目前它已經(jīng)成為最流行的公開密鑰算法辈赋。
RSA的安全基于大數(shù)分解的難度鲫忍。其公鑰和私鑰是一對大素數(shù)（100到200位十進制數(shù)或更大）的函數(shù)。從一個公鑰和密文恢復(fù)出明文的難度炭庙，等價于分解兩個大素數(shù)之積（這是公認(rèn)的數(shù)學(xué)難題）饲窿。
RSA的公鑰、私鑰的組成焕蹄，以及加密逾雄、解密的公式可見于下表：
在沒有正式講解RSA加密算法以前，讓我們先復(fù)習(xí)一下數(shù)學(xué)上的幾個基本概念腻脏，它們在后面的介紹中要用到：
一鸦泳、 什么是“素數(shù)”？
素數(shù)是這樣的整數(shù)永品，它除了能表示為它自己和1的乘積以外做鹰，不能表示為任何其它兩個整數(shù)的乘積。例如鼎姐，15＝3＊5钾麸，所以15不是素數(shù)；又如炕桨，12＝6＊2＝4＊3饭尝，所以12也不是素數(shù)。另一方面献宫，13除了等于13＊1以外钥平，不能表示為其它任何兩個整數(shù)的乘積，所以13是一個素數(shù)姊途。素數(shù)也稱為“質(zhì)數(shù)”涉瘾。
二、什么是“互質(zhì)數(shù)”（或“互素數(shù)”）捷兰？
小學(xué)數(shù)學(xué)教材對互質(zhì)數(shù)是這樣定義的：“公約數(shù)只有1的兩個數(shù)立叛，叫做互質(zhì)數(shù)〖叛常”這里所說的“兩個數(shù)”是指自然數(shù)囚巴。
判別方法主要有以下幾種（不限于此）：
（1）兩個質(zhì)數(shù)一定是互質(zhì)數(shù)。例如，2與7彤叉、13與19庶柿。
（2）一個質(zhì)數(shù)如果不能整除另一個合數(shù)，這兩個數(shù)為互質(zhì)數(shù)秽浇。例如浮庐，3與10登舞、5與 26夷陋。
（3）1不是質(zhì)數(shù)也不是合數(shù)，它和任何一個自然數(shù)在一起都是互質(zhì)數(shù)酥夭。如1和9908斑举。
（4）相鄰的兩個自然數(shù)是互質(zhì)數(shù)搅轿。如 15與 16。
（5）相鄰的兩個奇數(shù)是互質(zhì)數(shù)富玷。如 49與 51璧坟。
（6）大數(shù)是質(zhì)數(shù)的兩個數(shù)是互質(zhì)數(shù)。如97與88赎懦。
（7）小數(shù)是質(zhì)數(shù)雀鹃，大數(shù)不是小數(shù)的倍數(shù)的兩個數(shù)是互質(zhì)數(shù)。如 7和 16励两。
（8）兩個數(shù)都是合數(shù)（二數(shù)差又較大）黎茎，小數(shù)所有的質(zhì)因數(shù)，都不是大數(shù)的約數(shù)当悔，這兩個數(shù)是互質(zhì)數(shù)傅瞻。如357與715，357=3×7×17盲憎，而3俭正、7和17都不是715的約數(shù)，這兩個數(shù)為互質(zhì)數(shù)焙畔。等等。
三串远、什么是模指數(shù)運算宏多？
指數(shù)運算誰都懂，不必說了澡罚，先說說模運算伸但。模運算是整數(shù)運算，有一個整數(shù)m留搔，以n為模做模運算更胖，即m mod n。怎樣做呢？讓m去被n整除却妨，只取所得的余數(shù)作為結(jié)果饵逐，就叫做模運算。例如彪标，10 mod 3=1倍权；26 mod 6=2；28 mod 2 =0等等捞烟。
模指數(shù)運算就是先做指數(shù)運算薄声，取其結(jié)果再做模運算。如
好题画，現(xiàn)在開始正式講解RSA加密算法默辨。
算法描述：
（1）選擇一對不同的、足夠大的素數(shù)p苍息，q缩幸。
（2）計算n=pq。
（3）計算f(n)=(p-1)(q-1)档叔，同時對p, q嚴(yán)加保密桌粉，不讓任何人知道。
（4）找一個與f(n)互質(zhì)的數(shù)e衙四，且1
（5）計算d铃肯，使得de≡1 mod f(n)。這個公式也可以表達為d ≡e-1 mod f(n)
這里要解釋一下传蹈，≡是數(shù)論中表示同余的符號押逼。公式中，≡符號的左邊必須和符號右邊同余惦界，也就是兩邊模運算結(jié)果相同挑格。顯而易見，不管f(n)取什么值沾歪，符號右邊1 mod f(n)的結(jié)果都等于1漂彤；符號的左邊d與e的乘積做模運算后的結(jié)果也必須等于1。這就需要計算出d的值灾搏，讓這個同余等式能夠成立挫望。
（6）公鑰KU=(e,n)，私鑰KR=(d,n)狂窑。
（7）加密時媳板，先將明文變換成0至n-1的一個整數(shù)M。若明文較長泉哈，可先分割成適當(dāng)?shù)慕M蛉幸，然后再進行交換破讨。設(shè)密文為C，則加密過程為：
（8）解密過程為：
實例描述：
在這篇科普小文章里奕纫，不可能對RSA算法的正確性作嚴(yán)格的數(shù)學(xué)證明提陶，但我們可以通過一個簡單的例子來理解RSA的工作原理。為了便于計算若锁。在以下實例中只選取小數(shù)值的素數(shù)p,q,以及e搁骑，假設(shè)用戶A需要將明文“key”通過RSA加密后傳遞給用戶B，過程如下：
（1）設(shè)計公私密鑰(e,n)和(d,n)又固。
令p=3仲器，q=11，得出n=p×q=3×11=33仰冠；f(n)=(p-1)(q-1)=2×10=20乏冀；取e=3，（3與20互質(zhì)）則e×d≡1 mod f(n)洋只，即3×d≡1 mod 20辆沦。
d怎樣取值呢？可以用試算的辦法來尋找识虚。試算結(jié)果見下表：
通過試算我們找到肢扯，當(dāng)d=7時，e×d≡1 mod f(n)同余等式成立担锤。因此蔚晨，可令d=7。從而我們可以設(shè)計出一對公私密鑰肛循，加密密鑰（公鑰）為：KU =(e,n)=(3,33)铭腕，解密密鑰（私鑰）為：KR =(d,n)=(7,33)。
（2）英文數(shù)字化多糠。
將明文信息數(shù)字化累舷，并將每塊兩個數(shù)字分組。假定明文英文字母編碼表為按字母順序排列數(shù)值夹孔，即：
則得到分組后的key的明文信息為：11被盈，05，25搭伤。
（3）明文加密
用戶加密密鑰(3,33) 將數(shù)字化明文分組信息加密成密文害捕。由C≡Me(mod n)得：
因此，得到相應(yīng)的密文信息為：11闷畸，31，16吞滞。
（4）密文解密佑菩。
用戶B收到密文盾沫，若將其解密，只需要計算
殿漠，即：
用戶B得到明文信息為：11赴精，05，25绞幌。根據(jù)上面的編碼表將其轉(zhuǎn)換為英文蕾哟，我們又得到了恢復(fù)后的原文“key”。
你看莲蜘，它的原理就可以這么簡單地解釋谭确！
當(dāng)然，實際運用要比這復(fù)雜得多票渠，由于RSA算法的公鑰私鑰的長度（模長度）要到1024位甚至2048位才能保證安全逐哈，因此，p问顷、q昂秃、e的選取、公鑰私鑰的生成杜窄，加密解密模指數(shù)運算都有一定的計算程序肠骆，需要仰仗計算機高速完成。
最后簡單談?wù)凴SA的安全性
首先塞耕，我們來探討為什么RSA密碼難于破解蚀腿？
在RSA密碼應(yīng)用中，公鑰KU是被公開的荷科，即e和n的數(shù)值可以被第三方竊聽者得到唯咬。破解RSA密碼的問題就是從已知的e和n的數(shù)值（n等于pq），想法求出d的數(shù)值畏浆，這樣就可以得到私鑰來破解密文胆胰。從上文中的公式：d ≡e-1 (mod((p-1)(q-1)))或de≡1 (mod((p-1)(q-1))) 我們可以看出。密碼破解的實質(zhì)問題是：從Pq的數(shù)值刻获，去求出(p-1)和(q-1)蜀涨。換句話說，只要求出p和q的值蝎毡，我們就能求出d的值而得到私鑰厚柳。
當(dāng)p和q是一個大素數(shù)的時候，從它們的積pq去分解因子p和q沐兵，這是一個公認(rèn)的數(shù)學(xué)難題别垮。比如當(dāng)pq大到1024位時，迄今為止還沒有人能夠利用任何計算工具去完成分解因子的任務(wù)扎谎。因此碳想，RSA從提出到現(xiàn)在已近二十年烧董，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受胧奔，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一逊移。
然而，雖然RSA的安全性依賴于大數(shù)的因子分解龙填，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價胳泉。即RSA的重大缺陷是無法從理論上把握它的保密性能如何。
此外岩遗，RSA的缺點還有：A)產(chǎn)生密鑰很麻煩扇商，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密喘先。B)分組長度太大钳吟，為保證安全性，n 至少也要 600 bits 以上窘拯，使運算代價很高红且，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級涤姊；且隨著大數(shù)分解技術(shù)的發(fā)展暇番，這個長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化思喊。因此壁酬，使用RSA只能加密少量數(shù)據(jù)，大量的數(shù)據(jù)加密還要靠對稱密碼算法恨课。
