找到两个素数p,q后把它们相乘，就是三元组(e,d,n)中的n了，也就是n = q * p;接着计算n的欧拉函数φ(n),我们知道φ(n)的含义是小于n中与n互质的数的个数，并且对于n = q * p, 它的欧拉函数的值就是(p - 1) * (q - 1),所以接下来e的选取就是1到(p - 1) * (q - 1)中和(p - 1) * (q - 1)互质的数中的任何一个，而e随便选了，d也就定下来了，是e在mod φ(n)下的逆元，换句话说，e * d mod φ(n) = 1,利用扩展欧几里德算法，我们可以很容易的求出d，这样我们就轻松的把e , d , n求了出来。

简单的证明一下这样选取的(e,d,n)对于任何m,满足(m^e)^d mod n = m吧：

因为 e * d mod φ(n) = 1

即存在整数c使得e * d = φ(n) * c + 1

那么MOD n

那么由欧拉定理很快就能得到右边的这坨等于1

即MOD n

QED

在上文中我们知道，我们要在1～φ(n)中随便找个和φ(n)互素的数，如果这个数选的不当，那么这个rsa的安全性很有可能没你想象的那么安全，wiener发现了，如果d非常小的时候，在小于n^(1/4)/3时，wiener攻击能够奏效！

在说wiener's attack之前，先介绍下连分数，对于任意一个数都能展开成连分数，

如果你尝试做一遍你会发现，在你对一个分数展开成连分数的时候，事实上就是在对分子分母不断做辗转相除法，因此你很快得出一个结论：对于任意有理数(两个整数的比)的连分数永远是有限的。这很简单，对于两个数辗转相除，最终会停在两个数的最大公约数上，对于无理数也能连分数展开，例如π，e，无理数连分数展开是无限的。

对于连分数，我们观察每一个分母，它后面加的那一项都小于1,所以相比ai是一个非常小的数，如果我们把第i个分母后面的分数全部略去，我们称这个分数为这个连分数第i个渐进分数，显然i越大离x越接近，并且由于约去了分母前n-1个渐进分数都是小于x的。比如祖冲之发现圆周率的疏率和密率22 / 7与355 / 113 就是π连分数展开的两个渐进分数。

介绍完连分数，我们回来看RSA，首先N = pq; φ(n) = pq - (p + q) + 1 = N - (p + q) + 1

可以发现由于p,q非常大，pq是远大于p+q的，因此φ(n)约等于N

上面我们知道e d对于φ(n)互为逆元，因此我们可以列出式子:ed-1=k*φ(n)

这个式子非常重要我们将它变个型，两边同除以d*φ(n)可以得到：

由于φ(n)约等于N，上式我们可以写成

显然d*φ(n)是一个很大的数，因此可以说e/N 略大于k/d

为啥要这么写呢，因为e和N是我们是知道的，公钥中给我们的，所以我们计算出e/N后，比它略小的k/d怎么出来呢，计算e/N的连分数展开，依次算出这个分数每一个渐进分数，由于e/N 略大于k/d，wiener证明了，该攻击能精确的覆盖k/d

我们来举个例子，现在有一个rsa, e = 42667, N = 64741,我们来求。第一步，我们把分数e/N连分数展开，以此求出每一个渐进分数：0，1, 1/2, 2/3 ....

我们用1/2举例子，现在我们说，k/d=1/2非常可能成立，假设它成立，我们把k=1,d=2代入上面的ed-1=k*φ(n)中（为何原来比值相等的可以直接把分子分母分别带进去？想一想为什么），显然e,d,k都有了，φ(n)也就有了，我们知道φ(n)有啥用呢？我们知道 φ(n) = pq - (p + q) + 1 = N - (p + q) + 1，N = pq作为公钥我们是知道的，所以知道了φ(n)  我们只要算出N- φ(n)+1就是(p +  q)的值，现在知道了pq,和p+q的值很简单就能求出p,q。