RSA

R RSA算法基于很难找出一个两个大质数的分解因数这个原理。 这个算法为非对称加密算法，使用公钥和私钥。 公钥可以开放，任何人都可以用公钥加密信息，而只有私钥的拥有者才能解开这些信息。 从理论上讲，可以根据公钥算出私钥，但实际上几乎不可能，因此RSA算法成为了数据加密的流行算法。

密钥产生

它的安全是因为产生两个大质数非常苦难。而且，作为p和q的两个大质数至少钥在100位以上。

1) 获得两个大质数，p和q
为了方便演示，底下使用了两个相对较小的数字，虽然这是不安全的。 为了得到随机的质数，我们首先使用一个随即的数字，然后逐步求得一个质数，开始：

p = 7
q = 19

2) Let n = pq

n = 7 * 19
= 133

3) Let m = (p - 1)(q - 1)

m = (7 - 1)(19 - 1)
= 6 * 18
= 108

4) 找到一个小的数字e, e 与 m 互质
e 与 m互质,意味着这个大数字可以被e和m分解，（下文的gcd意思是‘最大公约数’）他们的最大公约数是1， means that the largest number that can exactly divide both e and m (their greatest common divisor, or gcd) is 1. 欧几里德算法就是为了找到两个数字的最大公约数， 具体的细节这里就不再演示。

e = 2 => gcd(e, 108) = 2 (no)
e = 3 => gcd(e, 108) = 3 (no)
e = 4 => gcd(e, 108) = 4 (no)
e = 5 => gcd(e, 108) = 1 (yes!)

5) 找到一个数字 d, 使 d * e % m = 1
找到d所付出的代价跟找到符合 d * e = 1 + n * m 中当n是任意数的代价是一样的。 也可以这么去描述这个关系 d = ( 1 + n * m ) / e。现在，通过n找到e：

n = 0 => d = 1 / 5 (no)
n = 1 => d = 109 / 5 (no)
n = 2 => d = 217 / 5 (no)
n = 3 => d = 325 / 5
= 65 (yes!)

如果处理一个大的数字，我们必须使用一个叫做欧几里德的算法。

公钥

n = 133
e = 5

私钥)

n = 133
d = 65

通讯

加密
要加密的信息必须比p和q中的较小者小，基于这个原因，我们不知道p和q，因此，习惯上p和q作为公钥。 This can be somewhat below their true value and so isn't a major security concern. 底下这个例子来说明： For this example, lets use the message "6".

C = Pe % n
= 65 % 133
= 7776 % 133
= 62

解密
跟加密非常相似，但这个过程分为了若干步

P = Cd % n
= 6265 % 133
= 62 * 6264 % 133
= 62 * (622)32 % 133
= 62 * 384432 % 133
= 62 * (3844 % 133)32 % 133
= 62 * 12032 % 133

We now repeat the sequence of operations that reduced 6265 to 12032 to reduce the exponent down to 1.

= 62 * 3616 % 133
= 62 * 998 % 133
= 62 * 924 % 133
= 62 * 852 % 133
= 62 * 43 % 133
= 2666 % 133
= 6

现在，明文跟原来的匹配，因此，算法正确。