/* rep06.c 
gcc rep06.c -o rep06 -lm
*/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int gcd(int a, int b)
{
  return b==0 ? abs(a): gcd(b,a%b);
}

int euclid(int a, int b, int *x, int *y)
{
	int q,r,d0,x0,y0;
	if(b==0){
		if(a>=0){
			*x=1;
			*y=0;
			return(a);
		}
		else{
			*x=-1;
			*y=0;
			return(-a);
		}
	}
	else{
		q=a/b;
		r=a-q*b;
		d0=euclid(b,r,&x0,&y0);
		*x=y0;
		*y=x0-q*y0;
		return(d0);
	}
}

int mod(int a, int m)
{
	int b=a%m;
	return b<0 ?  b+m: b;
}

int modadd(int a, int b, int m)
{
	return mod(a+b,m);
}

int modsub(int a, int b, int m)
{
	return mod(a-b,m);
}

int modmul(int a, int b, int m)
{
	return mod(a*b,m);
}

int modinv(int a, int m)
{
	int d,x,y;
	d=euclid(a,m,&x,&y);
	if(d!=1){
		printf("法と互いに素ではありません\n");
		exit(1);
	}
	else return mod(x,m);
}

int moddiv(int a, int b, int m)
{
	return modmul(a,modinv(b,m),m);
}

int primeq(int n)
/* n が素数のとき 1、そうでないとき 0 を返す */
{
	int i,m;
	if(n<2) return 0;
	if(n<=3) return 1;
	if(n%2==0) return 0;
	m=(int)sqrt(n);
	for(i=3;i<=m;i+=2) if(n%i==0) return 0;
	return 1;
}

int powermod(int a0, int e0, int m)
{
	int e=e0,a=a0,b,x;
	if(e<0){
		a=modinv(a,m);
		e=-e;
	}
	x=1;
	b=a;
	while(e>0){
		if(e%2) x=modmul(x,b,m);
		b=modmul(b,b,m);
		e/=2;
	}
	return x;
}

int encrypt(int x, int e, int n)
/* RSA暗号の公開鍵 e,n を用いて平文 x を暗号文に変換する */
{
	return powermod(x,e,n);
}

int decrypt(int y, int d, int n)
/* RSA暗号の公開鍵 n と秘密鍵 d を用いて暗号文 y を復号する */
{
	return powermod(y,d,n);
}

main()
{
	int p,q,n,m,e,d,x,y,z,i;

	srand(time(NULL));  /* 乱数の初期化 */

	/* 素数 p の生成 */
	p=rand()%100+100;
	while(!primeq(p)) p++;  
  
	/* p と異なる素数 q の生成 */
	q=rand()%100+100;
	while(!primeq(q) || q==p) q++;  
  
	/* n の生成 */
	n=p*q;
  
	/* m の生成 */
	m=(p-1)*(q-1);
  
	/* 暗号化指数 e の生成 */
	e=rand()%m;
	while(gcd(e,m)!=1) e=rand()%m;  
  
	/* 復号化指数 d の生成 */
	d=modinv(e,m);  
  
	/* 鍵の表示 */
	printf("\n公開鍵 :\n");
	printf("n = %5d\n",n);
	printf("e = %5d\n",e);
	printf("\n秘密鍵 :\n");
	printf("p = %5d\n",p);
	printf("q = %5d\n",q);
	printf("m = %5d\n",m);
  	printf("d = %5d\n",d);

	/* 暗号化・復号化テスト */ 
	printf("\n暗号化・復号化テスト\n");
	for(i=1;i<=5;i++){
		x=rand()%n;
		y=encrypt(x,e,n);
		z=decrypt(y,d,n);
		printf("\n");
		printf("   平文   %5d\n",x);
		printf("-> 暗号文 %5d\n",y);
		printf("-> 復号文 %5d\n",z);
	}
}