加密：RSA算法
我正在实现加密和解密的RSA算法，如下所示：
http://www.di-mgt.com.au/rsa_alg.html
但无法理解密钥生成中的随机素数生成部分。 所以我将两个素数作为用户的输入。 我也很难产生e。 所以我让它保持不变（e = 17）
一些素数输入在linux下的gcc中正常工作（即正确编码和解码），但在windows下的devcpp中没有。 （例如53,61）
这是密钥生成代码：
/* 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=%dn=%d }",e,n); printf("\n private key: { d=%dn=%d }\n",d,n); } 需要素数和e代的帮助和建议。
所以你已经知道e * d需要与1 mod phi（n）一致
因为你知道phi（n）一个元组（e，d）可以用扩展的欧几里得算法（EEA）计算：
为e选择一个整数（通常是一个小整数;这将是公共指数，对于较小的指数加密会更快），小于phi（n）且大于2（？…我认为）
当你有e的候选者时，计算e和phi（n）的最大公约数（gcd）……应该是1 ……如果没有，选择e的新候选者并重复（因为没有模块化逆，换句话说，这个e和phi（n）不存在私有指数d）
在您知道gcd（e，phi（n））== 1之后，您可以使用EEA计算d（或作为快捷方式，直接计算EEA，因为它也将提供GCD …如果不是1，请选择新的e）的价值
EEA（计算模块逆的快速和脏）：
想象一个有3列的表：
让我们说这些列被命名为：b，q和t
所以该表的行看起来像：
b0，q0，t0
b1，q1，t1
…
（等等）
最初的2行将首先填充。 对于所有其他行，有一个itterative规则可以应用于前两行，这将导致下一行的值
前两行是：
phi（n），NO_VALUE，0
e，floor（phi（n）/ e），1
创建下一行的itterative规则是:(其中[]是用于选择行的索引运算符）
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的候选者
我们的表格如下：
bqt 120 – 0 23 5 1 5 4 -5 3 1 21 2 1 -26 1 2 47
最后计算的b是1所以=> gcd（23,120）== 1（certificate：逆存在）
最后计算的t是47 => 23 * 47 mod 120 == 1（t是反的）
我没有答案，但如果使用两个不同的编译器编译的相同代码给出不同的答案，我会猜测某些类型具有不同的大小，或者您隐含地依赖于某处的未定义行为。
你应该做的第一件事是，给定相同的素数对，检查你生成的所有常量在两个实现中是否相同。 如果没有，您的密钥对生成算法就会出错。
接下来要确保两个系统上的加密输入数据完全相同。 特别注意你如何处理行尾字符。 请记住，在Windows上，行末是\r\n ，在Linux上它是\n 。 如果将"r"作为模式参数提供给fopen()大多数Windows库实现将把\r\n转换为\n因为文件被读入。 您的实施可能会有所不同。
最后，无论问题是什么， 决不会使用gets()如果你甚至想要再次使用它，你应该用冰锥去除大脑的额叶。
按照链接页面末尾的实际注释，您将得到类似于此类素材的一代：
unsigned int get_prime(int e) { while (true) { unsigned int suspect = 1 + (unsigned int)(65535.0 * rand() / (RAND_MAX + 1.0)); suspect &= 0x0000FFFF; // make sure only the lower 16bit are set suspect |= 0xC001; // set the two highest and the lowest bit while (!test_prime(suspect)) { suspect += 2; } if (suspect < 65536 && gcd(e, suspect - 1) == 1) return suspect; } }
test_prime应该是Miller-Rabin测试的一个实现。 上述function做出了某些假设，并有一些缺点：
-
int是32位 - RAND_MAX大于65536
-
rand()通常不是一个好的随机数生成器，用于严重加密 - 生成的素数是16位，因此显然不足以进行严格的加密
不要在任何生产代码中使用它。
根据文章，似乎可以选择固定。
Dear Friend just follow this algorithm Key generation 1) Pick two large prime numbers p and q, p != q; 2) Calculate n = p × q; 3) Calculate ø (n) = (p − 1)(q − 1); 4) Pick e, so that gcd(e, ø (n)) = 1, 1 < e < ø (n); 5) Calculate d, so that d · e mod ø (n) = 1, ie, d is the multiplicative inverse of e in mod ø (n); 6) Get public key as KU = {e, n}; 7) Get private key as KR = {d, n}. Encryption For plaintext block P < n, its ciphertext C = P^e (mod n). Decryption For ciphertext block C, its plaintext is P = C^d (mod n). Code: #include #include #include #include #include long int p,q,n,t,flag,e[100],d[100],temp[100],j,m[100],en[100],i; char msg[100]; int prime(long int); void ce(); long int cd(long int); void encrypt(); void decrypt(); void main() { clrscr(); printf("\nENTER FIRST PRIME NUMBER\n"); scanf("%d",&p); flag=prime(p); if(flag==0) { printf("\nWRONG INPUT\n"); getch(); exit(1); } printf("\nENTER ANOTHER PRIME NUMBER\n"); scanf("%d",&q); flag=prime(q); if(flag==0||p==q) { printf("\nWRONG INPUT\n"); getch(); exit(1); } printf("\nENTER MESSAGE\n"); fflush(stdin); scanf("%s",msg); for(i=0;msg[i]!=NULL;i++) m[i]=msg[i]; n=p*q; t=(p-1)*(q-1); ce(); printf("\nPOSSIBLE VALUES OF e AND d ARE\n"); for(i=0;i0) { d[k]=flag; k++; } if(k==99) break; } } } long int cd(long int x) { long int k=1; while(1) { k=k+t; if(k%x==0) return(k/x); } } void encrypt() { long int pt,ct,key=e[0],k,len; i=0; len=strlen(msg); while(i!=len) { pt=m[i]; pt=pt-96; k=1; for(j=0;j