RSA算法密钥生成

Question

我目前正在努力与RSA encryption algorythm。

我的问题是位于public/private密钥生成，这里是我的步骤：

1. -Generate 2 prime numbers p, q with p > q and nbBits(p) == nbBits(q) 
      using the miller-rabin algorythm this was done succesfully 
2. -compute n = p*q 
3. -compute fi(n) = (p-1)*(q-1) 

来了麻烦：我需要找到一个整数e与q < e < fi(n)。这个整数需要某种素数。

我的问题是：e是否必须是原始的（不能被任何数字除以它自己或1）或原始的WITH fi(n) (gcd(e, fi(n)) = 1)或两者？

我真的有一些问题搞清楚了这一点（我的源代码中明确指出需要对欧几里德algorythm（GCD），但因为英语不是我的母语，我有一些麻烦与数学英语）

可能是一个愚蠢的问题，但我找不到明确的解释（至少对我来说足够清楚）。

感谢您的阅读，甚至更多的回答。

Answer 1

加密指数e需要与phi(n)互斥，即gcd(e,phi(n)) = 1。 这个条件是必要的，否则，你将无法构造（通过Euclid的扩展算法）指数d（解密指数），使得e*d = 1 mod phi(n)。