前言
前几天的一个比赛，让我这个没怎么学过密码学，平时都只是套套脚本的人很受打击，决意好好研究一下RSA.希望在往后的比赛里，也能通过密码学拿拿分，顺便拓展一下知识面，以后吹牛有的吹….
计算公钥和私钥
RSA中的公钥和私钥需要结合在一起工作。公钥用来对数据块加密，之后 ，只有对应的私钥才能用来解密。生成密钥时，需要遵循几个步骤以确保公钥和私钥的这种关系能够正常工作。这些步骤也确保没有实际方法能够从一个密钥推出另一个。
开始前，首先要选择两个大的素数，记为p和q。根据当今求解大数因子的技术水平，这两个数应该至少有200位，这们在实践中才可以认为是安全的。
然后，开始计算n:
n = pq
接下来，选择一个小的奇数e，它将成为公钥的一部分。选择e最需要考虑的重点是它与(p-1)(q-1)不能有相同的因子。换句话说，e与(p-1)(q-1)是互为素数关系的。比如，如果p=11而q=19，那么n=11 X 19=209。这里选择e=17，因为(p-1)(q-1)=10 X 18 =180，而17和180没有相同的因子。通常选择3、17、65、537作为e的值。使用这些值不会对RSA的安全性造成影响，因为解密数据还需要用到私钥。
一旦为e选择了一个值，接下来开始计算相对应的值d，d将成为私钥的一部分。d的值就是计算e的倒数对(p-1)(q-1)的取模结果，公式如下：
d = e-1 mod (p-1)(q-1)
这里d和e是模乘法逆元的关系。
思考一下这个问题：当d为多少时可以满足ed mod (p-1)(q-1) = 1 ?比如在等式 17d mod 180 = 1中，d的一个可能值是53。其他的可能值是233、413、593等。在实践中，可以利用欧几里德算法来计算模乘法逆元。这里就不再展开。
现在有了e和d的值，将(e,n)作为公钥P，将(d,n)作为私钥S并保持其不可见。表示为：
P = (e,n) , S = (d,n)
加密方使用P来加密数据，解密方使用S来解密。为了防止就算有人知道了P也无法推算出S，必须保证p和q的值绝对不能暴露。
P和S结合在一起提供的安全性来自于一个事实，那就是乘法是一种很好的单向函数。
欧拉函数记为φ(n)，定义所有小于n的正整数里和n互素的整数的个数。
只有当两个整数的唯一公因子为1时，才说这两个整数是互素的。例如，φ（8）=4，因为一共只用4个比8小的整数是互素的，它们是1，3，5，7。
欧拉方程有两个性质对RSA算法来说是特别重要的。
第一，当n是素数时，φ（n）=n-1。这是由于n的唯一因子是1和n，因此，n与之前的所有n-1个正整数都是互素的。
另一个有趣的性质是对于任意小于n且与n互素的正整数a，都有aφ(n) mod n = 1。例如，14 mod 8 = 1, 34 mod 8 = 1, 54 mod 8 = 1, 74 mod 8 = 1。对上述方程两边都乘以a，得到：
(a)(aφ(n) mod n)=a，或者aφ(n)+1 mod n = a
因此，可以得到15 mod 8 = 1, 35 mod 8 = 3, 55 mod 8 = 5, 75 mod 8 = 7。
调整之后得到的等式非常强大。因为对于某些等式c = me mod n，该等于可以让我们找出一个d的值，使得cd mod n = m。
这就是RSA算法中允许加密数据，之后再解密回原文的恒等式。可以按照如下方式表示：
cd mod n = (me)d mod n = med mod n = mφ(n)+1 mod n = m mod n
欧拉函数和指数间的关系保证了加密的任意数据都能够唯一地解密回来。为了找出d的值，解方程d = e-1 φ(n) +1。不巧的是，对于方程d = e-1φ(n)+1不一定总是有整数解。为了解决这种问题，转而计算
d mod φ(n)的值。换句话说，d = (e-1 φ(n) + 1) mod φ(n)，可以简化为：
d = e-1 mod φ(n)
我们可以得到这样的简化形式，因为(φ(n)+1) mod φ(n) = (φ(n)+1) - φ(n) = 1。可以用任意的正整数替代φ(n)来证明等式成立。注意这个方程式同之前计算密钥的过程中得出d的推导式之间的相似之处。这提供了一种通过e和n来计算d的方法。当然了，e和n是公开的，对于攻击者来说是事先可知的，因此就有人问，这难道不是给了攻击者相同的机会来计算出私钥吗？讨论到这里，是时候来探讨一下RSA算法安全性保障的由来了。
RSA算法的安全性保障来自一个重要的事实，那就是欧拉函数是乘法性质的。这意味着如果p和q是互素的，那么有φ(pq)=φ(p)φ(q)。因此，如果有两个素数p和q，且n=p*q，则φ(n)=(p-1)(q-1)，而且最重要的是：
d = e-1 mod (p-1)(q-1)
因此，尽管攻击者可能知道了e和n的值，为了计算出d必须知道φ(n)，而这又必须同时得到p和q的值才能办到。由于p和q是不可知的，因此攻击者只能计算n的因子，只要给出的p和q的值足够大，这就是一个相当耗费时间的过程。