我正在实现RSA算法，用于加密和解密，如下所示:
http://www.di-mgt.com.au/rsa_alg.html
但是无法理解 key 生成中随机质数生成部分。
因此，我将两个质数作为用户的输入。我也难以生成e。所以我把它设为常数(e = 17)
某些质数输入在Linux下的gcc中可正常工作(即正确地编码和解码)，而在Windows下的devcpp中则不能。 (例如53,61)
这是 key 生成代码:
/* Generates private and public keys and saves into two separate files */
void keygen()
{
int p,q,phi,d,e,n,s;
printf("\n Enter two prime numbers: ");
scanf("%d%d",&p,&q);
n = p*q;
phi=(p-1)*(q-1);
e=17;
// selec d such that d*e = 1+ k*phi for some integer k.
d = 0;
do
{
d++;
s = (d*e)%phi;
}while(s!=1);
printf("\n public key: { e=%d n=%d }",e,n);
printf("\n private key: { d=%d n=%d }\n",d,n);
}
在质数和e代中需要帮助和建议。
最佳答案
所以您已经知道e * d必须等于1 mod phi(n)
由于您知道phi(n)，因此可以使用扩展的欧几里得算法(EEA)计算元组(e，d):
为e选择一个整数(通常是一个小整数；这将是公共(public)指数，使用较小的指数加密会更快)，它小于phi(n)且大于2(？...我认为)
当您有e的候选者时，计算e和phi(n)的最大公约数(gcd)...应该为1 ...如果不是，请为e选择一个新的候选者并重复(因为将没有模数相反，换句话说，对于此e和phi(n)不存在私有(private)指数d
在知道gcd(e，phi(n))== 1之后，您可以使用EEA计算d(或者作为一种捷径，直接计算EEA，因为它还会提供GCD ...如果不是1，请选择一个新的e的值)
EEA(快速而肮脏的用于计算模逆):
想象一个有3列的表格:
假设这些列被命名为:b，q和t
因此该表的行将如下所示:
b0，q0，t0
b1，q1，t1
...
(等等)
前2行将被初始填充。
对于所有其他行，可以将一条适用于前两行的规则应用于最终两行的值
前两行是:
phi(n)，NO_VALUE，0
e，楼板(phi(n)/e)，1
创建下一行的命令规则是:(其中[]是用于选择该行的索引运算符)
b [i] = b [i-2] mod b [i-1]
q [i] = b [i-1]/b [i](整数除法，无分数...)
t [i] = t [i-2]-(q [i-1] * t [i-1])
您可以在b [i]变为0或1时中止该方案...最后一行实际上不需要q ...
因此，如果b [i]为0，则b [i-1]不能为1，因为如果计算b [i-1]为1，则应该中止。
如果您达到b [i] == 0，则b [i-1]是您的gcd ...因为它不是1，所以您需要为e输入一个新值
如果b [i] == 1，则您的gcd为1，并且存在一个逆...，即t [i](如果t为负，则添加phi(n))
具有真实值的示例:
假设phi(n)是120
假设我们选择23作为e的候选者
我们的表如下所示:
b q t
120 – 0
23 5 1
5 4 -5
3 1 21
2 1 -26
1 2 47
最后计算的b为1，因此=> gcd(23,120)== 1(证明:倒数存在)
最后计算的t为47 => 23 * 47 mod 120 == 1(t为倒数)