关于为 RSA 算法导出私钥的困惑

Question

从这里开始是将在本文中使用的变量，因为我看到一些名称具有不同的含义：

• p & q：2 个质数，其中 q > p
• n = p*q
• Φ(n) Euler's Totient (of n)
• e：指数，必须大于1且必须是Φ(n)的互质，最好大
• k：使 d（见下文）和 interger
的一些值
• d: 私钥由(k*Φ(n) + 1) / e
计算

辅助功能：

• gcd(a,b) 返回a和b之间的最大公分母，b必须大于a

  def gcd(a,b): #greatest common denomonater
      while b % a != 0:
          temp = a
          a = b % a
          b = temp
      return a
  

• lcm(a,b) 返回 a 和 b 之间的最小公倍数。

  def lcm(a,b):
      out = abs(a*b)
      return out/gcd(a,b)
  

现在对于大多数这些值，通过输入或生成 p & q，计算值非常简单。

Φ(n) 可以通过欧拉的 Totient 的简单实现来计算。这是我在 python 中做的：

   ```
def Phi(n):
    count = 0
    for i in range(n-1):
        if i != 0:
            if gcd(i,n) == 1:
                count += 1
    return count + 1
   ``` 

我已经看到 Φ(n) = lcm(p-1,q-1) 但根据我的经验，这似乎不是真的

E 计算

```
while(exponent < phi): # e must be greater than one phi while being a co-prime of phi
        if(gcd(e,phi) == 1):
            break
        else:
            e+=1
```

d 通过代入等式 d = (k*Φ(n) + 1) / e

来计算

这是我第一个困惑是如何计算的。我发现这个线程在谈论它RSA 中的 k 是什么？。结合我发现的其他文章，我明白扩展欧几里德算法应该用于此任务。 在此，a 和 m 将被替换为什么。我对 p 和 q 继续使用常数值，所以我想出了一个可行的 k 值，但在规模上这是不可行的

继续加密和解密： 使用 p = 53 和 q = 59 我得到 3x3127 的公钥，其中 e = 3 和 3127 = n。我还得到了 2x2011 的私钥，其中 k = 2（我知道在密钥中包含这个没有任何实用价值）和 d = 2011。看看我是如何编码的 here.

现在（令人惊讶的是）这适用于我的加密和解密功能

```
def encrypt(message,public):
    key = public.split("x")
    e = int(key[0])
    n = int(key[1])
    out = pow(message,e)
    
    return(out % n)
def decrypt(message,private,public):
    key = private.split("x")
    k = int(key[0])
    d = int(key[1])
    publicKey = public.split("x")
    e = int(publicKey[0])
    n = int(publicKey[1])
    return(pow(message,int(d),n))
```

更准确地说，它在大约 50% 的时间内有效。以下是我注意到的一些导致问题的模式 这里供参考是我如何测试这个

```
x = encrypt(53,public)
print(x)
x = decrypt(x,private,public)
print(x)
```

如果值大于 n 或数字，这不起作用< 0. The latter can be avoided but the first problem seems to be an issue especially when simpler numbers are used. I think the issue comes in the encryption process as the output for encryption of a value over n is 0

总结一下：在 RSA 加密中，k 值是如何计算的，为什么消息的数值不能超过 n