RSA加密算法原理及RES签名算法简介(转载)
第一部分:RSA算法原理與加密解密
一、RSA加密過程簡述
A和B進行加密通信時,B首先要生成一對密鑰。一個是公鑰,給A,B自己持有私鑰。A使用B的公鑰加密要加密發送的內容,然后B在通過自己的私鑰解密內容。
?
二、RSA加密算法基礎
整個RSA加密算法的安全性基于大數不能分解質因數。
三、數學原理
(一)??互質關系:兩個數a和b沒有除1外的其他公約數,則a與b互質
1.????????任意兩個質數構成互質關系
2.????????兩個數中,如果大數為質數,則兩數必定互質
3.????????1和任意整數互質
4.????????當p>1時,p與p-1互質(相鄰兩數互質)
5.????????當p=2n+1(n>0且n為整數)時,p與p+2互質(相連的兩個奇數互質)
(二)??求歐拉函數:
定義:與正整數n互質且小于正整數n的正整數的個數。通常使用ψ(n)表示。
?
求取與正整數n互質的正整數的個數ψ(n),且ψ(n)滿足ψ(n)∈(2,n)
1.????????如果n=1,則ψ(n)=1
2.????????如果n是質數,則ψ(n)=n-1
3.????????如果n是質數p的次方,則:ψ(p^k)=p^k-p^(k-1) = p^k*(1-1/p)
4.????????若p1和p2互質,n=p1*p2,則ψ(n)= ψ(p1*p2)= ψ(p1) ψ(p2)
5.????????任意一個大于1的正整數都可以寫成一系列質數的積
6.????????根據定理5,推導歐拉定理:
因為
???????? n = (p1^k1)* (p2^k2)*……(pr^kr)?? (p1~pr都是質數)
所以
???????? ψ(n)= ψ((p1^k1)) ψ(p2^k2) ……ψ(pr^kr)?? 定理4
???????? ψ(n)= (p1^k1)*(1-1/p1) * (p2^k2)(1-1/p2)……(pr^kr)*(1-1/pr)?? 定理3
???????? ψ(n)= (p1^k1)* (p2^k2)*……(pr^kr) * (1-1/p1) (1-1/p2)…… (1-1/pr)
???????? ψ(n)=n (1-1/p1) (1-1/p2)…… (1-1/pr)??
(三)??歐拉定理:
正整數a與n互質,則下式恒成立
a^ψ(n) ≡1(mod n)
即:
???????? a的ψ(n)次冪除以n,余數恒為1
(四)??模反元素
如果兩個正整數a和n互質,則必定存在整數b使得a*b-1被n除余數為1
ab ≡1(mod n)
其中b被稱為a的模反元素
?
四、RSA算法詳解:假設A和B要通信
(一)??生成密鑰
1.????????公鑰
1)????????隨機生成兩個不相等的質數p和q(質數越大越安全)
2)????????計算n,n=p*q 則n的二進制位數就是密鑰的長度。
3)????????計算n的歐拉函數ψ(n)????????
因為
n=p*q
所以
ψ(n) =ψ(p)* ψ(q)??? 定理4
又p和q為質數
所以
ψ(p)=p-1????定理2
ψ(q)=q-1????定理2
所以
?????????????????? ψ(n) = (p-1)(q-1)
4)????????獲取隨機正整數e,e滿足? e∈(1, ψ(n))且e與ψ(n)互質(通常選擇65537)
將n和e封裝成公鑰
????????
2.????????私鑰
1)????????計算e對于ψ(n)的模反元素d
e*d=1(modψ(n));
設正整數k, e*d = kψ(n)+1;
?
則ed-kψ(n)=1
? d = (kψ(n)+1) / e;
對于不定方程ax+by=c,設gcd(a,b)=d,如果ax+by=c有解,則d|c----->也就是說如果ed-kψ(n)=1 有解,則gcd(d,-k)能夠整除1,而1顯然可以被任何整數整除,所以該二元一次方程必定有解(d,k)
?
?(歐幾里得定理和擴展歐幾里得定理計算二元一次方程)
2)????????將n和d封裝成私鑰
?
?
五、RSA算法可靠性論證
從上文可以統計出整個算法涉及到的量有6個,其中三個為由私鑰持有者生成,三個是私鑰持有者推導出來的
生成量:p,q,e
推導量:n, ψ(n),d
?
密鑰中只有公鑰被發布,所有人都可以獲取。而公鑰由n和e封裝起來,因此,如果要破解一份RSA加密過的密文,我們必須使用私鑰(私鑰由n和d封裝而成)
n可以從公鑰獲取。
?
(假設mc為明文,c為密文,則公鑰由n和e封裝則意味著求取密文的運算中,n,e和mc是已知數,只有c是未知數;私鑰由n和d封裝,同上,解密密文的運算中,n,d和c是已知的,只有mc是未知數。)
?
因此,破解私鑰的關鍵就是破解e對于ψ(n)的模反元素d。
???????? 其數學關系是:? e*d=1(modψ(n));
因此需需要先求出ψ(n),而求出ψ(n)需要知道ψ(p)和ψ(q)(因為ψ(n)= ψ(p* ψ(q))
?
而p和q只能通過分解n的質因數獲得。所以,整個RSA算法都基于n這個大數不能分解質因數這個基礎上。
????????
因此,只要n夠大,私鑰就不會被破解
?
?
六、加解密過程:假設明文是m,c是密文
(一)??加密:使用公鑰(n,e)
先將其換算成asc碼或者unicode等其他數值。且m必須小于n
則加密算法是
???????? m^e=c(mod n)
推出
???????? m^e / n = k ……c這里c就是密文,k我們不關心
(二)??解密:使用私鑰(n,d)
1.????????簡單的說解密就是通過下式求m。(一定可以求解出m)
c^d = m(mod n)
推出
c^d / n = k … … m??? m就是明文編碼,不關心k
?
查表得出明文
?
?
第二部分:RSA算法簽名與驗簽
?
假設A要想B發送消息,A會先計算出消息的消息摘要,然后使用自己的私鑰加密這段摘要加密,最后將加密后的消息摘要和消息一起發送給B,被加密的消息摘要就是“簽名”。
B收到消息后,也會使用和A相同的方法提取消息摘要,然后使用A的公鑰解密A發送的來簽名,并與自己計算出來的消息摘要進行比較。如果相同則說明消息是A發送給B的,同時,A也無法否認自己發送消息給B的事實。
其中,A用自己的私鑰給消息摘要加密成為“簽名”;B使用A的公鑰解密簽名文件的過程,就叫做“驗簽”。
?
數字簽名的作用是保證數據完整性,機密性和發送方角色的不可抵賴性
?
下面是對簽名和驗簽過程的簡要描述:
?
l? 簽名過程:
1.????????A計算消息m的消息摘要,記為 h(m)
2.????????A使用私鑰(n,d)對h(m)加密,生成簽名s ,s滿足:
s=(h(m))^d mod n;
由于A是用自己的私鑰對消息摘要加密,所以只用使用s的公鑰才能解密該消息摘要,這樣A就不可否認自己發送了該消息給B。
3.????????A發送消息和簽名(m,s)給B。
?
l? 驗簽過程:
1.????????B計算消息m的消息摘要,記為h(m);
2.????????B使用A的公鑰(n,e)解密s,得到
H(m) = s^e mod n;
3.????????B比較H(m)與h(m),相同則證明
?
第三部分:總結
?
下面簡單總結加密和解密的完整過程。
?
l ?簽名過程:
1.????????A提取消息m的消息摘要h(m),并使用自己的私鑰對摘要h(m)進行加密,生成簽名s
2.????????A將簽名s和消息m一起,使用B的公鑰進行加密,生成密文c,發送給B。
l ?驗證過程:
1.????????B接收到密文c,使用自己的私鑰解密c得到明文m和數字簽名s
2.????????B使用A的公鑰解密數字簽名s解密得到H(m).
3.????????B使用相同的方法提取消息m的消息摘要h(m)
4.????????B比較兩個消息摘要。相同則驗證成功;不同則驗證失敗。
?
下面是借鑒一個網友的Demo,加上我自己注釋后,打包的一個Demo。
?
EnAndDe.java
?
package com.joe.main;import java.io.*; import java.math.BigInteger; import java.util.ArrayList;/*** <p>* Company: 建工學院* </p>* * @author 04信息(1)程晟* @modify Joe* @Description Demo說明:* 1、按照加密解密和簽名驗簽的邏輯,編寫簡單的demo,不涉及java中繼承的RSA相關類和Sigesture簽名類* 2、只能對數字和字母進行加密, 不涉及編碼和解碼問題 。 3、不做數字簽名和驗證了,涉及到提取信息摘要。*/ public class EnAndDe {private long p = 0;private long q = 0;private long n = 0;private long t = 0; // 歐拉函數private long e = 0; // 公匙private long d = 0; // 密匙private String mc; // 明文private long c = 0; // 密文private long word = 0; // 解密后明文// 判斷是一個數 x 否為素數素數就是判斷在 (2,√x)范圍內有沒有除1外的因數,如果沒有則x數素數public boolean isPrime(long t) {long k = 0;k = (long) Math.sqrt((double) t);for (int i = 2; i <= k; i++) {if ((t % i) == 0) {return false;}}return true;}// 隨機產生大素數(1e6數量級,注意,太大了要超出范圍)public void bigprimeRandom() {do {p = (long) (Math.random() * 1000000);} while (!this.isPrime(p));do {q = (long) (Math.random() * 1000000);} while (p == q || !this.isPrime(q));}// 輸入PQpublic void inputPQ() throws Exception {this.bigprimeRandom();System.out.println("自動生成兩個大素數p,q分別為:" + this.p + " " + this.q);this.n = (long) p * q;this.t = (long) (p - 1) * (q - 1);System.out.println("這兩個素數的乘積為p*q:" + this.n);System.out.println("所得的t=(p-1)(q-1):" + this.t);}// 求最大公約數public long gcd(long a, long b) {long gcd;if (b == 0)gcd = a;elsegcd = gcd(b, a % b);return gcd;}// 生成公匙public void getPublic_key() throws Exception {do {this.e = (long) (Math.random() * 100000);// e滿足 e∈(1, ψ(n))且e與ψ(n)最大公約數為1,即 e與t互質} while ((this.e >= this.t) || (this.gcd(this.t, this.e) != 1));System.out.println("生成的公鑰為:" + "(" + this.n + "," + this.e + ")");}// 生成私鑰 e*d=1(modψ(n))==> d = (kψ(n)+1) / epublic void getPrivate_key() {long value = 1; // value 是e和d的乘積outer: for (long k = 1;; k++) {value = k * this.t + 1;if ((value % this.e == 0)) {this.d = value / this.e;break outer;}}System.out.println("產生的一個私鑰為:" + "(" + this.n + "," + this.d + ")");}// 輸入明文public void getText() throws Exception {System.out.println("請輸入明文:");BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));mc = stdin.readLine();}// 解密密文public void pascolum() throws Exception {this.getText();System.out.println("輸入明文為: " + this.mc);// 加密ArrayList cestr = new ArrayList();for (int i = 0; i < mc.length(); i++) {this.c = this.colum((long) mc.charAt(i), this.n, this.e);cestr.add(c);}System.out.println("加密后所得的密文為:" + cestr);// 解密StringBuffer destr = new StringBuffer();for (int j = 0; j < cestr.size(); j++) {this.word = this.colum(Long.parseLong(cestr.get(j).toString()),this.n, this.d);destr.append((char) word);}System.out.println("解密后所得的明文為:" + destr);}// 加密、解密計算public long colum(long mc, long n, long key) {BigInteger bigy = new BigInteger(String.valueOf(mc));BigInteger bign = new BigInteger(String.valueOf(n));BigInteger bigkey = new BigInteger(String.valueOf(key));return Long.parseLong(bigy.modPow(bigkey, bign).toString());// 備注1}public static void main(String[] args) {try {EnAndDe t = new EnAndDe();t.inputPQ();t.getPublic_key();t.getPrivate_key();t.pascolum();} catch (Exception e) {e.printStackTrace();}}}備注1:modPow(a,b)是java類BigInteger中的一個方法,返回結果是:調用該方法的對象的a次冪,模b的結果
轉載于:https://www.cnblogs.com/pang-blog/p/4092143.html
總結
以上是生活随笔為你收集整理的RSA加密算法原理及RES签名算法简介(转载)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 静态页中调用动态数据的三种办法
- 下一篇: 仔细学习CSS(二)