首页分享在RSA算法密钥产生过程中，设P=43,Q=17,取密钥D=593，求公钥

在RSA算法密钥产生过程中，设P=43,Q=17,取密钥D=593，求公钥

来源：萌宠菠菠乐园时间：2024-12-14 10:20

　　公钥为17。
　　#include <stdio.h>
　　#include <math.h>
　　#include <stdlib.h>
　　//判断公钥e是否为素数，1成立，0不成立
　　int prime(int e);
　　//判断公钥e与(p-1)*(q-1)的最大公约数是否为1，1成立，0不成立
　　int gcd(int e,int pq);
　　//判断e*d余(p-1)*(q-1)是否为1，1成立，0不成立
　　int mod(int e,int d,int pq);
　　#define SIZE 1024
　　void main()
　　{
　　int p;
　　int q;
　　int e;//公钥
　　int d;//密钥
　　int pq;//(p-1)*(q-1)
　　int* eArray=(int*)malloc(sizeof(int)*SIZE);
　　int i=0;
　　int size;
　　printf("请输入素数p和qn");
　　scanf("%d%d",&p,&q);
　　printf("请输入密钥dn");
　　scanf("%d",&d);
　　pq=(p-1)*(q-1);
　　printf("p=%dnq=%dnd=%d(p-1)*(q-1)=%dn",p,q,d,pq);
　　for(e=1;e<pq;e=e+2)
　　{
　　if(mod(e,d,pq)&&gcd(e,pq))
　　{
　　eArray[i]=e;
　　i++;
　　}
　　}
　　size=i;
　　printf("在0-%d可能的公钥数量为 %d n",pq,size);
　　printf("公钥为:");
　　for(i=0;i<size;i++)
　　{
　　if(i%5==0)
　　printf("n");
　　printf("%d ",eArray[i]);
　　}
　　printf("n");
　　free(eArray);
　　}
　　int mod(int e,int d,int pq)
　　{
　　int ed=e*d;
　　if(ed%pq==1)
　　return 1;
　　return 0;
　　}
　　int gcd(int e,int pq)
　　{
　　if(prime(e)&&pq%e!=0)
　　return 1;
　　return 0;
　　}
　　int prime(int e)
　　{
　　for(int i=2;i<=int(sqrt(e)+1);i++)
　　{
　　if(e%i==0&&e!=2)
　　return 0;
　　}
　　return 1;
　　}