密钥交换算法中讲到的密钥都是一般指对称加密算法的密钥（注意区别：非对称算法自己本身的密钥），因为对于对称算法的特性来说，采取”一次一密”的话才比较安全。

1.      RSA，可以用做密钥传输算法，即使用对端的RSA公钥对密钥进行加密，对端使用自己的私钥对其进行解密，就可以获取密钥。

基本原理：与rsa相关的参数字母有p,q,e,d,n，这个大家在看关文档的时候总会看到这些东东，他们是干什么的呢，都代表什么意思呢？主要由p,q,e三个东东构成，

1)      p,q均为大素数。

2)      e可以为任何数但e与(p-1)(q-1)一定要互素。

3)      产生p,q,e后n就自然出来了，因为n=p*q，

4)      另一个d是由e,p,q计算出来的，公式: d * e = 1 modulo（p - 1）*（q - 1)，这个公式看起来是不是有些头疼？其实很简单就是d*e除以(p-1)*(q-1)=1

5)      公钥就为n和e组成，私钥就是d了(注：e和d是可以互换的，但是只能公开一个，公开哪个，哪个就被称用作公钥)

6)      加密方法：C=(p ^ e) mod n

           解密方法：P=(c ^ d) mod n

举个简单的例子：

1)      取p=3,q=11, n=q*p=33。

2)      (q-1)*(p-1)=20,取e=7，则d=3，因为3*7 mod 20 =1.

3)      原文2，使用公钥算密文C=(2^7) mod 33 = 29

                   解密P=(29^3)mod33=2

证明公式:

<定理>

若 p, q 是相异质数, rm == 1 mod (p-1)(q-1),

a 是任意一个正整数, b == a^m mod pq, c == b^r mod pq,

则 c == a mod pq

证明的过程, 会用到费马小定理, 叙述如下:

m 是任一质数, n 是任一整数, 则 n^m == n mod m

(换另一句话说, 如果 n 和 m 互质, 则 n^(m-1) == 1 mod m)

运用一些基本的群论的知识, 就可以很容易地证出费马小定理的........

 

<证明>

因为 rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整数

因为在 modulo 中是 preserve 乘法的

(x == y mod z and u == v mod z => xu == yv mod z),

所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq

 

1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时,

则 a^(p-1) == 1 mod p (费马小定理) => a^(k(p-1)(q-1)) == 1 mod p

a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q

所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1

即 a^(k(p-1)(q-1)) == 1 mod pq

=> c == a^(k(p-1)(q-1)+1) == a mod pq

 

2. 如果 a 是 p 的倍数, 但不是 q 的倍数时,

则 a^(q-1) == 1 mod q (费马小定理)

=> a^(k(p-1)(q-1)) == 1 mod q

=> c == a^(k(p-1)(q-1)+1) == a mod q

=> q | c - a

因 p | a

=> c == a^(k(p-1)(q-1)+1) == 0 mod p

=> p | c - a

所以, pq | c - a => c == a mod pq

 

3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上

 

4. 如果 a 同时是 p 和 q 的倍数时,

则 pq | a

=> c == a^(k(p-1)(q-1)+1) == 0 mod pq

=> pq | c - a

=> c == a mod pq

Q.E.D.

 

这个定理说明 a 经过编码为 b 再经过解码为 c 时, a == c mod n (n = pq)....

但我们在做编码解码时, 限制 0 <= a < n, 0 <= c < n,

所以这就是说 a 等於 c, 所以这个过程确实能做到编码解码的功能....

安全性分析：

        由于公钥中n是公开的，RSA的安全性依赖于大数分解，所以就是需要n一定要大，目前最常 见的攻击方法就是分解n是最显然的攻击方法。另一个需要注意的是：原文数据一定不能比n大。由于为了防止被攻击，明文一般会进行至少有8个填充字节，这里不介绍填充算法。