密码学：RSA加密算法详解
概述
? 本文旨在說明RSA加密算法的原理及實現(xiàn)，而其相關的數(shù)學部分的證明則不是本文內(nèi)容。
版權說明
著作權歸作者所有。
商業(yè)轉載請聯(lián)系作者獲得授權，非商業(yè)轉載請注明出處。
作者：Q-WHai
發(fā)表日期： 2016年2月29日
本文鏈接：http://blog.csdn.net/lemon_tree12138/article/details/50696926
來源：CSDN
更多內(nèi)容：分類 ? 數(shù)據(jù)加密與信息安全
RSA簡介
??1977年，三位數(shù)學家Rivest、Shamir 和 Adleman 設計了一種算法，可以實現(xiàn)非對稱加密。這種算法用他們?nèi)齻€人的名字命名，叫做RSA算法。從那時直到現(xiàn)在，RSA算法一直是最廣為使用的"非對稱加密算法"。毫不夸張地說，只要有計算機網(wǎng)絡的地方，就有RSA算法。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?-- 摘自網(wǎng)絡
數(shù)學背景
? 此部分旨在補充本文的完整性。如果說你已經(jīng)了解，或是不想了解此部分內(nèi)容。那么可以直接跳過此部分的閱讀。
? 雖說只是補充說明（只能是補充的原因是因為博主的數(shù)學也是比較差的-_-!!!），但是此部分的內(nèi)容卻是相當重要的。博主還是希望可以重新閱讀一下此部分。
1.互質
? 從小學開始，我們就了解了什么是質數(shù)。互質是針對多個數(shù)字而言的，如果兩個正整數(shù)，除了1以外，沒有其他公因子，那么就稱這兩個數(shù)是互質關系（注意，這里并沒有說這兩個數(shù)一定是質數(shù)或有一個為質數(shù)。比如15跟4就是互質關系）。以下有一些關于質數(shù)與互質的性質：
- 質數(shù)只能被1和它自身整除
- 任意兩個質數(shù)都是互質關系
- 如果兩個數(shù)之中，較大的那個數(shù)是質數(shù)，則兩者構成互質關系
- 如果兩個數(shù)之中，較小的那個數(shù)是質數(shù)，且較大數(shù)不為較小數(shù)的整數(shù)倍，則兩者構成互質關系
- 1和任意一個自然數(shù)是都是互質關系
- p是大于1的整數(shù)，則p和p-1構成互質關系
- p是大于1的奇數(shù)，則p和p-2構成互質關系
2.歐拉函數(shù)
??歐拉函數(shù)是求小于x并且和x互質的數(shù)的個數(shù)。其通式為：φ(x) = x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)。
? 其中p1, p2……pn為x的所有質因數(shù)，x是不為0的整數(shù)。看到這里是不是有一些頭疼，太理論的東西的確不夠具象。我們且不去理會后面公式計算與論證，因為已經(jīng)超出本文的范圍了。就前一句來說說吧，歐拉函數(shù)是求小于x并且和x互質的數(shù)的個數(shù)。這里我可以列舉一個例子：
? 令x = 16，那么x的所有質因數(shù)為：φ(16) = 16 * (1 - 1/2) = 8
? 我們也可以枚舉出所有比16小，且與16互質的數(shù)：1, 3, 5, 7, 9, 11, 13, 15
? 現(xiàn)在也給出部分歐拉函數(shù)的性質：
- 若n是素數(shù)p的k次冪，，因為除了p的倍數(shù)外，其他數(shù)都跟n互質
- 歐拉函數(shù)是積性函數(shù)——若m,n互質，
- 當n為奇數(shù)時，
- p是素數(shù)，，φ(p)稱為p的歐拉值
? 歐拉函數(shù)更多參考請見這里的鏈接。
3.模反元素
定義：如果兩個正整數(shù)a和n互質，那么一定可以找到整數(shù)b，使得 ab-1 被n整除，或者說ab被n除的余數(shù)是1。
關于模反元素的求解，使用的是樸素的解法。如果讀者想要更進一步了解的話，請自行搜索其他解法（比如：輾轉相除法、歐幾里德算法）。
RSA原理
? 在RSA原理之前，我想還是有必要了解一下非對稱加密算法的加密跟解密過程。下面就是一幅非稱加密算法的流程圖。
??
? 在此可以看到，非對稱加密是通過兩個密鑰（公鑰-私鑰）來實現(xiàn)對數(shù)據(jù)的加密和解密的。公鑰用于加密，私鑰用于解密。對于非對稱的加密和解密為什么可以使用不同的密鑰來進行，這些都是數(shù)學上的問題了。不同的非對稱加密算法也會應用到不同的數(shù)學知識。上面也對RSA中使用的數(shù)學問題做了一個小小的介紹。現(xiàn)在就來看看RSA算法是怎么來對數(shù)據(jù)進行加密的吧，如下是一幅RSA加密算法流程及加密過程圖。
??
RSA應用
1. 實例模型
? 就以上圖中的Bob和Alice來舉例吧。
? 現(xiàn)在Alice通過密鑰生成器生成了一對密鑰（公鑰-私鑰）。只把公鑰對外公開了。并說，你有什么要跟我說的，就用模冪運算和公鑰加密后發(fā)給我吧。
? 此時，Bob已經(jīng)獲得了Alice發(fā)布的公鑰。使用模冪運算對明文進行了加密，就把加密后的密文發(fā)送給了Alice。
? Alice獲得Bob發(fā)來的密文并沒有使用公鑰對密文進行解密，并獲得了明文。因為解密過程需要使用的密鑰是私鑰。
2. RSA算法實現(xiàn)
? 下面的代碼只是根據(jù)RSA算法的定義，使用Java開發(fā)語言實現(xiàn)。且這里只是展示了一些關鍵步驟，完整過程可以參見下面的源碼下載文檔。
public class RSA { /*** 獲得(公/私)密鑰*/public final Map<String, RSAKey> getCipherKeys() {...int[] primes = getRandomPrimes(2);int modulus = modulus(primes[0], primes[1]);int euler = euler(primes[0], primes[1]);int e = cipherExponent(euler);int inverse = inverse(euler, e);publicKey.setExponent(e);publicKey.setModulus(modulus);privateKey.setExponent(inverse);privateKey.setModulus(modulus);...}/*** 加密*/public int encode(int plaintext, RSAPublicKey key) {return modularPower2(plaintext, key.getExponent(), key.getModulus());}/*** 解密*/public int decode(int chipertext, RSAPrivateKey key) {return modularPower2(chipertext, key.getExponent(), key.getModulus());}// 隨機生成count個素數(shù)private final int[] getRandomPrimes(int count) {...try {primeLabels = FileReadUtils.readLines("./data/prime_table");} catch (IOException e) {e.printStackTrace();}for (int i = 0; i < primes.length; i++) {primes[i] = Integer.parseInt(primeLabels.get(indexs.get(i)));}return primes;}// 計算公共模數(shù)private final int modulus(int p, int q) {return p * q;}// 計算歐拉數(shù)private final int euler(int p, int q) {return (p - 1) * (q - 1);}// 計算加密指數(shù)private final int cipherExponent(int euler) {Random random = new Random();int e = 7;do {e = random.nextInt(euler - 1);} while (!isCoprime(e, euler) || e <= 1);return e;}// 判斷兩個數(shù)互素private final boolean isCoprime(int number1, int number2) {int sqrt = (int) Math.sqrt(Math.max(number1, number2));for (int i = 2; i <= sqrt; i++) {if (number1 % i == 0 && number2 % 2 == 0) {return false;}}return true;}// 計算“模的逆元”// (d * e) ≡ 1 mod eulerprivate final int inverse(int euler, int e) {...while (flag) {q = m[2] / n[2];for (int i = 0; i < 3; i++) {temp[i] = m[i] - q * n[i];m[i] = n[i];n[i] = temp[i];}if (n[2] == 1) {if (n[1] < 0) {n[1] = n[1] + euler;}return n[1];}if (n[2] == 0) {flag = false;}}return 0;}// 模冪運算private final int modularPower(int base, int e, int modular) {int result = 1;do {if (isOdd(e)) {result = (result * (base % modular)) % modular;e -= 1;} else {base = (base * base) % modular;e /= 2;}} while (e > 0);result %= modular;return result;} }
RSA算法判別
RSA算法優(yōu)點
RSA算法缺點
Ref
源碼下載
http://download.csdn.net/detail/u013761665/9439852
總結
以上是生活随笔為你收集整理的密码学：RSA加密算法详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Python代码优化及技巧笔记（一）
- 下一篇： 排序算法系列：快速排序算法