RSAの仕組み


p=997,q=991,e=983
'A'=64 --> 851605

encrypt
64^983%988027=851605

d=(x*996*990+1)/983
x=54
d=54167

decrypt
851605^54167%988027=64

#include
#include
#include
#define N 100
int gcd(int n,int m){
int a,r;
if(n>m){a=m;m=n;n=a;}
r=m%n;while(r!=0){m=n;n=r;r=m%n;}return(n);
}
int euclid(int x,int y){
int q,x1,y1,a,b,a1,b1,xx;
x1=x;y1=y;a=0;b=1;a1=1;b1=0;
while(y1!=0){
q=x1/y1;
xx=x1;x1=y1;y1=xx%y1;
xx=a1;a1=a;a=xx-a*q;
xx=b1;b1=b;b=xx-b*q;
}
if(b1<0)b1+=x;
return(b1);
}
int mulmod(int a,int n,int m){
int mu;
a=a%m;if(a<0)a+=m;
mu=0;
while(n>=1){
if((n%2)==1)mu=(a+mu)%m;
a=(a*2)%m;n/=2; }
return(mu); }
int powermod(int a,int n,int m){
int pw;
a=a%m;if(a<0)a+=m;
pw=1;
while(n>=1){
if((n%2)==1)pw=mulmod(a,pw,m);
a=mulmod(a,a,m);n/=2; }
return(pw); }

int main(int ac,char *av[]){
int a[N*N];
int i,j;
int p,q,e,n,x,y,d;
FILE *fp;
char buf[256];
char cmd;
int l,s;
if(ac>1){
printf("p=");scanf("%d",&p);
printf("q=");scanf("%d",&q);
printf("e=");scanf("%d",&e);
n=p*q; x=p-1; y=q-1;
if(gcd(x*y,e)!=1){printf("change e\n");exit(1);}
d=euclid(x*y,e);
printf("public key e=%d n=%d \n",e,n);
printf("secret key d=%d n=%d \n",d,n);
fp=fopen(av[1],"r");
if(fp==NULL){printf("notfound %s\n",av[1]);exit(1);}
while(fgets(buf,256,fp)!=NULL){
l=strlen(buf);
for(i=0;i

ブログ気持玉

クリックして気持ちを伝えよう!

ログインしてクリックすれば、自分のブログへのリンクが付きます。

→ログインへ

なるほど(納得、参考になった、ヘー)
驚いた
面白い
ナイス
ガッツ(がんばれ!)
かわいい

気持玉数 : 1

ナイス

この記事へのコメント

この記事へのトラックバック