#include <stdio.h>
int candp(int a,int b,int c)
{	
	int r=1;
	b=b+1;
	while(b!=1)
	{
		r=r*a;
		r=r%c;
		b--;
	}
	printf("%d\n",r);
	return r;
}
void main()
{
	int p,q,e,d,m,n,t,c,r;
	char s;
	printf("please input the p,q: ");
	scanf("%d%d",&p,&q);
	n=p*q;
	printf("the n is %3d\n",n);
	t=(p-1)*(q-1);
	printf("the t is %3d\n",t);
	printf("please input the e: ");
	scanf("%d",&e);
	if(e<1||e>t)
	{
		 printf("e is error,please input again: ");
		 scanf("%d",&e);
	}
	d=1;
	while(((e*d)%t)!=1)  
		d++;
	printf("then caculate out that the d is %d\n",d);
	printf("the cipher please input 1\n");
	printf("the plain please input 2\n");
	scanf("%d",&r);
	switch(r)
	{
		case 1: printf("input the m: "); /*输入要加密的明文数字*/
				scanf("%d",&m);
				c=candp(m,e,n);
				printf("the cipher is %d\n",c);break;
		case 2: printf("input the c: "); /*输入要解密的密文数字*/
				scanf("%d",&c);
				m=candp(c,d,n);
				printf("the cipher is %d\n",m);break;
	}
	getch();
}

# include <iostream.h>
# include <string.h>
# include <fstream.h>
# include <math.h>
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# define ul unsigned long
ul isPrime(ul n)
{
 ul b=1;
 for(ul i=2;i<n;i++)
  if(n%i==0) { b=0; break; }
 return b;
}
ul Power(ul x,ul y)
{
 ul ans=1;
 if(x==1) return x;
 for(ul i=1;i<=y;i++)
   ans*=x;
 return(ans);
}
char * ToBin(int x)
{
char *ans=new char[20];
int i=0;
 while(x>=1)
 {
  if(x%2==1) ans[i]='1'; else ans[i]='0';
  x/=2; i++;
 }
 if(x==1) ans[i]='1',i++;
 ans[i]='\0';
 strrev(ans);
 return(ans);
}
	ul Crypt(int x,int key,int n) // (x^y)%z //Method 2
	{
	 char *B=new char[20];
	 B=ToBin(key);
	 ul ans=1;int c=1;
	 for(int i=0;i<strlen(B);i++)
	 {
	   c=2*c;
	   ans=(ans*ans)%n;
	   if(B[i]=='1')
	   {
	    c=c+1;
	    ans=(ans*x)%n;
	   }
	 }
	 return(ans);
	}
void Fun1(int,int,int);
int Bin2Num(char *s)
{
 int ans=0; int i,j;
 for(j=0,i=7;i>=0;j++,i--)
  {
    if(s[i]=='1') ans+=Power(2,j);
  }
  return ans;
}
char * Num2Bin(int n)
{
 char *s=new char[20];
 int i=0;
 for(i=0;i<8;i++) s[i]='0';
 while(n>1)
 {
  if(n%2==1) s[i]='1';
  else s[i]='0';
  n/=2; i++;
 }
 if(n%2==1) s[i]='1'; else s[i]='0';
 s[8]='\0';
 strrev(s);
 return s;
}

void KeyEnc(int,int);
void KeyDec(int,int);
void main()
{
 clrscr();
 randomize();
  /* K E Y   G E N E R A T I O N */
 ul p,q,n,n1,e,d;
 Beg:    // Reading 2 random prime-numbers from 20 to 50
 p=2+rand()%200;
 q=2+rand()%200;
//p=17;q=11;
 if(p==q||!isPrime(p)||!isPrime(q)) goto Beg;
 n = p * q;
n1 = (p-1) * (q-1);
int x=n1+1;
 for(e=2;e<=x/2;e++)
 {
  if(x%e==0) break;
 }
  d=x/e;
 if(p==1||q==1||e==1||d==1||e==d||
 q==e||q==d||p==e||p==d) goto Beg;
// if(e>30||d>30) goto Beg;
		 ul P1=18,P2,Cypher;
B1:
 Cypher=Crypt(P1,e,n);  //Encrypting using public-key  'e'
// if(Cypher>160||Cypher<d*2||Cypher==P1) goto Beg;
 P2=Crypt(Cypher,d,n);//Decrypting using private key 'd'

 cout<<"p  	      = "<<p<<endl;
 cout<<"q             = "<<q<<endl;
 cout<<"n =(p*q)      = "<<n<<endl;
 cout<<"n1=(p-1)*(q-1)= "<<n1<<endl;
 cout<<"e	      = "<<e<<endl;
 cout<<"d	      = "<<d<<endl<<endl;
 cout<<"Public Key  : { "<<e<<","<<n<<" }"<<endl;
 cout<<"Private Key : { "<<d<<","<<n<<" }"<<endl;
cout<<"PlainText Before Encryption is : "<<P1<<endl;
cout<<"Cypher is : "<<Cypher<<endl;
cout<<"PlainText After Decryption is : "<<P2<<endl;
getch(); randomize(); clrscr();goto Beg;
// KeyEnc(e,n);
// KeyDec(d,n);
 getch();
}
void KeyEnc(int e,int n)
{
  ifstream fin("key.txt");
 ofstream fout("keyEnc.txt");
 char str[10]; int i,X,Y,j;
 //while(!fin.eof())
 for(j=0;j<8;j++)
 {
  for(i=0;i<8&&!fin.eof();i++) { fin.get(str[i]); cout<<str[i]; }
  str[8]='\0';
    cout<<str<<",";
  X=Bin2Num(str);
  Y=Crypt(X,e,n);
  cout<<X<<","<<Y<<endl;
  fout<<Y<<endl;
  getch();
 }
 fin.close(); fout.close();
}
void KeyDec(int d,int n)
{
 ifstream fin("keyEnc.txt");
 ofstream fout("keyDec.txt");
 char ch; int i,X,Y;
 char *str=new char[20];
 cout<<"Decrypt...\n";
 int Ch;
 while(!fin.eof())
 {
   fin>>Ch; if(fin.eof()) return;
   cout<<Ch;
   Y=Crypt(Ch,d,n);
   cout<<","<<Y;
   str=Num2Bin((int)Y);
   cout<<","<<str<<endl;
   fout<<str;
   getch();
 }
 fin.close(); fout.close();
}
void Fun1(int e,int d,int n)
{
 char str[30];
 cout<<"Enter some Text : ";
 gets(str);
 ofstream fout("d:\\cyfer.txt",ios::binary);
 int M,C; char ch;
 for(int i=0;i<strlen(str);i++)
 {
   C=Crypt(str[i],e,n);
   fout.put(C);
 } fout.close();
 ifstream fin("d:\\cyfer.txt");
 while(!fin.eof())
 {
    fin.get(ch);
    ch=Crypt(ch,d,n);
    cout<<ch;
 }
 fin.close();
}

# include <iostream.h>
# include <string.h>
# include <fstream.h>
# include <math.h>
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# define ul unsigned long
ul isPrime(ul n)
{
 ul b=1;
 for(ul i=2;i<n;i++)
  if(n%i==0) { b=0; break; }
 return b;
}
ul Power(ul x,ul y)
{
 ul ans=1;
 if(x==1) return x;
 for(ul i=1;i<=y;i++)
   ans*=x;
 return(ans);
}
char * ToBin(int x)
{
char *ans=new char[20];
int i=0;
 while(x>=1)
 {
  if(x%2==1) ans[i]='1'; else ans[i]='0';
  x/=2; i++;
 }
 if(x==1) ans[i]='1',i++;
 ans[i]='\0';
 strrev(ans);
 return(ans);
}
	ul Crypt(int x,int key,int n) // (x^y)%z //Method 2
	{
	 char *B=new char[20];
	 B=ToBin(key);
	 ul ans=1;
	 int c=1;
	 for(ul i=0;i<strlen(B);i++)
	 {
	   c=2*c;
	   ans=(ans*ans)%n;
	   if(B[i]=='1')
	   {
	    c=c+1;
	    ans=(ans*x)%n;
	   }
	 }
	 return(ans);
	}
void main()
{
 clrscr();
 randomize();
  /* K E Y   G E N E R A T I O N */
 ul p,q,n,n1,e,d;
 Beg:    // Reading 2 random prime-numbers from 20 to 50
 p=2+rand()%200;
 q=2+rand()%200;
 if(p==q||!isPrime(p)||!isPrime(q)) goto Beg;
 n = p * q;
n1 = (p-1) * (q-1);
ul x=n1+1;
 for(e=2;e<=x/2;e++)
 {
  if(x%e==0) break;
 }
  d=x/e;
 if(p==1||q==1||e==1||d==1||e==d||
 q==e||q==d||p==e||p==d) goto Beg;
		 ul P1=31,P2,Cypher;
B1:
 Cypher=Crypt(P1,e,n);  //Encrypting using public-key  'e'
 P2=Crypt(Cypher,d,n);//Decrypting using private key 'd'

 cout<<"p  	      = "<<p<<endl;
 cout<<"q             = "<<q<<endl;
 cout<<"n =(p*q)      = "<<n<<endl;
 cout<<"n1=(p-1)*(q-1)= "<<n1<<endl;
 cout<<"e	      = "<<e<<endl;
 cout<<"d	      = "<<d<<endl<<endl;
 cout<<"Public Key  : { "<<e<<","<<n<<" }"<<endl;
 cout<<"Private Key : { "<<d<<","<<n<<" }"<<endl;
cout<<"PlainText Before Encryption is : "<<P1<<endl;
cout<<"Cypher is : "<<Cypher<<endl;
cout<<"PlainText After Decryption is : "<<P2<<endl;
getch(); randomize(); clrscr();goto Beg;
 getch();
}

# include <iostream.h>
# include <string.h>
# include <fstream.h>
# include <math.h>
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# define ul unsigned long
ul isPrime(ul n)
{
 ul b=1;
 for(ul i=2;i<n;i++)
  if(n%i==0) { b=0; break; }
 return b;
}
ul Power(ul x,ul y)
{
 ul ans=1;
 if(x==1) return x;
 for(ul i=1;i<=y;i++)
   ans*=x;
 return(ans);
}
char * ToBin(int x)
{
char *ans=new char[20];
int i=0;
 while(x>=1)
 {
  if(x%2==1) ans[i]='1'; else ans[i]='0';
  x/=2; i++;
 }
 if(x==1) ans[i]='1',i++;
 ans[i]='\0';
 strrev(ans);
 return(ans);
}
	ul Crypt(int x,int key,int n) // (x^y)%z //Method 2
	{
	 char *B=new char[20];
	 B=ToBin(key);
	 ul ans=1;int c=1;
	 for(int i=0;i<strlen(B);i++)
	 {
	   c=2*c;
	   ans=(ans*ans)%n;
	   if(B[i]=='1')
	   {
	    c=c+1;
	    ans=(ans*x)%n;
	   }
	 }
	 return(ans);
	}
void Fun1(int,int,int);
int Bin2Num(char *s)
{
 int ans=0; int i,j;
 for(j=0,i=7;i>=0;j++,i--)
  {
    if(s[i]=='1') ans+=Power(2,j);
  }
  return ans;
}
char * Num2Bin(int n)
{
 char *s=new char[20];
 int i;
 for(i=0;i<8;i++) s[i]='0';
 i=0;
 while(n>1)
 {
  if(n%2==1) s[i]='1';
  else s[i]='0';
  n/=2; i++;
 }
 if(n%2==1) s[i]='1'; else s[i]='0';
 s[8]='\0';
 strrev(s);
 return s;
}

void KeyEnc(int,int);
void KeyDec(int,int);
void main()
{
 clrscr();
 randomize();
  /* K E Y   G E N E R A T I O N */
 ul p,q,n,n1,e,d;
 Beg:    // Reading 2 random prime-numbers from 20 to 50
 p=2+rand()%150;
 q=2+rand()%150;
 if(p==q||!isPrime(p)||!isPrime(q)) goto Beg;
 n = p * q;
n1 = (p-1) * (q-1);
int x=n1+1;
 for(e=2;e<=x/2;e++)
 {
  if(x%e==0) break;
 }
  d=x/e;
 if(p==1||q==1||e==1||d==1||e==d||
 q==e||q==d||p==e||p==d) goto Beg;
		 ul P1=18,P2,Cypher;
B1:
 Cypher=Crypt(P1,e,n);  //Encrypting using public-key  'e'
 P2=Crypt(Cypher,d,n);//Decrypting using private key 'd'

 cout<<"p  	      = "<<p<<endl;
 cout<<"q             = "<<q<<endl;
 cout<<"n =(p*q)      = "<<n<<endl;
 cout<<"n1=(p-1)*(q-1)= "<<n1<<endl;
 cout<<"e	      = "<<e<<endl;
 cout<<"d	      = "<<d<<endl<<endl;
 cout<<"Public Key  : { "<<e<<","<<n<<" }"<<endl;
 cout<<"Private Key : { "<<d<<","<<n<<" }"<<endl;
cout<<"PlainText Before Encryption is : "<<P1<<endl;
cout<<"Cypher is : "<<Cypher<<endl;
cout<<"PlainText After Decryption is : "<<P2<<endl;
cout<<"\n\n\nEncrypting Key...";
cout<<"\nEncrypting Key ...";
 KeyEnc(e,n);
cout<<"\nDecrypting Key...";
 KeyDec(d,n);
cout<<"\nFinish [key.txt]";
 getch();
}
void KeyEnc(int e,int n)
{
  ifstream fin("d:\\key.txt");
 ofstream fout("d:\\keyEnc.txt");
 char str[10]; ul i,X,Y,j;
 for(j=0;j<8;j++)
 {
  for(i=0;i<8&&!fin.eof();i++) { fin.get(str[i]); }
  str[8]='\0';
//    cout<<str<<",";
  X=Bin2Num(str);
  Y=Crypt(X,e,n);
//  cout<<X<<","<<Y<<endl;
  fout<<Y<<endl;
  getch();
 }
 fin.close(); fout.close();
}
void KeyDec(int d,int n)
{
 ifstream fin("d:\\keyEnc.txt");
 ofstream fout("d:\\keyDec.txt");
 char ch; ul i,X,Y;
 char *str=new char[20];
 int Ch;
 while(!fin.eof())
 {
   fin>>Ch; if(fin.eof()) return;
   cout<<Ch;
   Y=Crypt(Ch,d,n);
//   cout<<","<<Y;
   str=Num2Bin(Y);
//   cout<<","<<str<<endl;
   fout<<str;
   getch();
 }
 fin.close(); fout.close();
}

/*
 * rsatest.c
 */

#include <stdio.h>
#include <stdlib.h>
#include "mrsa.h"

void
main(int i, char **v) {
	NN m,c,d;
	rsa_key key;
	char s[NSIZE*4+2];

	if(i==4) {
		hn(c,v[1]);
		hn(d,v[2]);
		hn(m,v[3]);
		em(c,d,m);
		nh(s,c); puts(s);
		exit(EXIT_SUCCESS);
	}

	if(i!=3) {
		puts("Usage: mtest [hex_pseed] [hex_qseed]");
		exit(EXIT_FAILURE);
	}

	hn(key.p,v[1]);
	hn(key.q,v[2]);

	puts("Generating key...");
	if(!rsa_gen(&key)) {
		puts("Failed, try other seed values.");
		exit(EXIT_FAILURE);
	}
	puts("Done, key components: pq,e,d,p,q,dp,dq,qp");		
	printf("bits = %u\n",key.b);
	nh(s,key.pq); puts(s);
	nh(s,key.e); puts(s);
	nh(s,key.d); puts(s); 
	nh(s,key.p); puts(s);
	nh(s,key.q); puts(s);
	nh(s,key.dp); puts(s);
	nh(s,key.dq); puts(s);
	nh(s,key.qp); puts(s);
	puts("testing, msg,cip,dec1,dec2");
	cl(m);
	randomize(m, key.b-2);
	nh(s,m); puts(s);
	cp(c,m); rsa_enc(c,&key);
	nh(s,c); puts(s);
	cp(d,c); em(d,key.d,key.pq); /* slow way */
	nh(s,d); puts(s);
	cp(d,c); rsa_dec(d,&key); /* faster way */
	nh(s,d); puts(s);
	exit(EXIT_SUCCESS);
}

/*
 * mrsa.c -- portable multiprecision math and RSA library
 * 1993 Risto Paasivirta, paasivir@jyu.fi
 * Public Domain, no warranty. 
 */

#define MRSA_C 1

#include "mrsa.h"

/*
 * math library stuff
 */

/*
 * sign = ts(N a) -- test signed, returns 1, 0 or -1 
 */

PRIVATE int
ts(N a)
{
	ULONG i = NSIZE;
	if (a[NSIZE - 1] & SIGN_BIT)
		return -1;
	while (i--)
		if (*a++)
			return 1;
	return 0;
}

/*
 * carry = ng(N a) -- negate, returns carry
 */

PRIVATE ULONG
ng(N a)
{
	ULONG c = 0, i = NSIZE;
	while (i--) {
		c = 0 - *a - c;
		*a++ = c;
		c = (c >> UNIT_BITS) & 1;
	} return c;
}

/*
 * cl(N a) -- clear value, a = 0
 */

PRIVATE void
cl(N a)
{
	ULONG i = 0;
	while (i++ < NSIZE)
		*a++ = 0;
}

/*
 * cp(N a, N b) -- copy, a = b
 */

PRIVATE void
cp(N a, N b)
{
	ULONG i = NSIZE;
	while (i--)
		*a++ = *b++;
}

/*
 * flag = cu(a, b) -- compare unsigned, returns <0 if a<b, 0 if a==b, >0 if a>b
 */
 
PRIVATE int
cu(N a, N b)
{
	ULONG i = NSIZE;
	a += NSIZE;
	b += NSIZE;
	while (i--)
		if (*--a - *--b)
			return (int) *a - (int) *b;
	return 0;
}

/*
 * carry = ad(N a, N b) -- add, a += b
 */

PRIVATE ULONG
ad(N a, N b)
{
	ULONG c = 0, i = NSIZE;
	while (i--) {
		c = *b++ + *a + c;
		*a++ = c;
		c >>= UNIT_BITS;
	} 
	return c;
}

/*
 * carry = sb(N a, N b) -- substract, a -= b
 */

PRIVATE ULONG
sb(N a, N b)
{
	ULONG c = 0, i = NSIZE;
	while (i--) {
		c = *a - *b++ - c;
		*a++ = c;
		c = (c >> UNIT_BITS) & 1;
	}
	return c;
}

/*
 * carry = sr(N a) -- shift right, a >>= 1
 */

PRIVATE ULONG
sr(N a)
{
	ULONG c = 0, i = NSIZE;
	a += NSIZE;
	while (i--) {
		c |= *--a;
		*a = c >> 1;
		c = (c & 1) << UNIT_BITS;
	}
	return c;
}

/*
 * carry = sl(N a) -- shift left, a <<= 1
 */

PRIVATE ULONG
sl(N a)
{
	ULONG c = 0, i = NSIZE;
	while (i--) {
		c |= (ULONG) * a << 1;
		*a++ = c;
		c = (c >> UNIT_BITS) & 1;
	}
	return c;
}

/*
 * dm(N a, N b, N c) -- divide-modulo unsigned, a = a / b, c = a % b
 */

PRIVATE void
dm(N a, N b, N c)
{
	ULONG i = NSIZE * UNIT_BITS;
	cl(c);
	while (i--) {
		sl(c);
		*c |= sl(a);
		if (sb(c, b)) {
			ad(c, b);
		} else {
			*a |= 1;
		}
	}
}

/*
 * remainder = di(N a, int n) -- divide by integer
 */

PRIVATE ULONG
di(N a, ULONG t)
{
	ULONG c = 0, i = NSIZE;
	while (i--) {
		c = (c << UNIT_BITS) | a[i];
		a[i] = c / t;
		c = c % t;
	} 
	return c;
}

/*
 * mu(N a, N b) -- multiply unsigned, a *= b
 */

PRIVATE void
mu(N a, N b)
{
	ULONG i = NSIZE * UNIT_BITS;
	NN c;
	cl(c);
	while (i--) {
		sl(c);
		if (sl(a))
			ad(c, b);
	}
	cp(a, c);
}

/*
 * mm(N a, N b, N m) -- modular multiply, a = a * b mod m 
 */

PRIVATE void
mm(N a, N b, N m)
{
	ULONG i = NSIZE * UNIT_BITS;
	NN c;
	cl(c);
	while (i--) {
		sl(c);
		if (sb(c, m))
			ad(c, m);
		if (sl(a))
			ad(c, b);
		if (sb(c, m))
			ad(c, m);
	}
	cp(a, c);
}

/*
 * pmm(N a, N b, N m, ULONG p) -- internal modmul w/precision for modexp
 */

#ifndef AMIGA

static void
pmm(N aa, N b, N m, ULONG p)
{
	ULONG k, c, j = UNIT_BITS, i;
	NN v;
	N a;
	i = p;
	cl(v);
	a = aa + p;
	while (!*--a
	       && i)
		i--;
	if (i) {
		while (!(*a & (1 << j)) && j)
			j--;
		cp(v, b);
	} while (i--) {
		while (j--) {
			for (k = 0, c = 0; k < p; k++) {
				c |= (ULONG) v[k] << 1;
				v
					[k] = c;
				c >>= UNIT_BITS;
			} for (k = 0, c = 0; k < p; k++) {
				c = v[k] - m[k] - c;
				v[k] = c;
				c = (c >> UNIT_BITS) & 1;
			} if (c)
				for (k = 0, c = 0; k < p; k++) {
					c = v[k] + m[k] + c;
					v[k] = c;
					c >>= UNIT_BITS;
			} if (*a & (1 << j)) {
				for (k = 0, c = 0; k < p; k++) {
					c = v[k] + b[k] + c;
					v[k] = c;
					c >>= UNIT_BITS;
				} for (k = 0, c = 0; k < p; k++) {
					c = v[k] - m[k] - c;
					v[k] = c;
					c = (c >> UNIT_BITS) & 1;
				} if (c)
					for (k = 0, c = 0; k < p; k++) {
						c = v[k] + m[k] + c;
						v[k] = c;
						c >>= UNIT_BITS;
					}
			}
		}
		a--;
		j = UNIT_BITS;
	}
	cp(aa, v);
}

#endif

/*
 * em(N a, N b, N m) -- modular exponentation, a = a^b mod n
 */

PRIVATE void
em(N a, N e, N m)
{
	ULONG i = NSIZE, j = UNIT_BITS, p = NSIZE;
	NN c;
	N mp;
	cl(c);
	*c = 1;
	e += NSIZE;
	while (!*--e && i)
		i--;
	if (i) {
		while (!(*e & (1 << j)))
			j--;
		cp(c, a);
	}
	mp = m + NSIZE;
	while (!*--mp && p)
		p--;
	if (*mp & SIGN_BIT && p < NSIZE)
		p++;
	while (i--) {
		while (j--) {
			pmm(c, c, m, p);
			if (*e & (1 << j))
				pmm(c, a, m, p);
		}
		e--;
		j = UNIT_BITS;
	}
	cp(a, c);
}

/*
 * gd(N a, N b) -- a = greatest common divisor(a,b)
 */

PRIVATE void
gd(N a, N bb)
{
	NN r, b;
	cp(b, bb);
	while (ts(b)) {
		dm(a, b, r);
		cp(a, b);
		cp(b, r);
	}
}

/*
 * iv(N a, N b) -- multiplicative inverse, a = a^{-1} mod b 
 */

PRIVATE void
iv(N a, N b)
{
	NN c, d, e, f, g, y;
	cp(c, b);
	cl(e);
	cl(f);
	*f = 1;
	while (ts(a)) {
		cp(y, c);
		dm(y, a, d);
		if (f[NSIZE - 1] & SIGN_BIT) {
			ng(f);
			mu(y, f);
			ng(f);
			ng(y);
		} else
			mu(y, f);
		cp(g, e);
		sb(g, y);
		cp(c, a);
		cp(a, d);
		cp(e, f);
		cp(f, g);
	}
	if (e[NSIZE - 1] & SIGN_BIT)
		ad(e, b);
	cp(a, e);
}

/*
 * nh(char *a, N b) -- convert value to a hex string (use for debugging)
 */

PRIVATE void
nh(char *a, N b)
{
	char *d = "0123456789abcdef";
	NN c;
	ULONG i = NSIZE * sizeof(UWORD) * 2; /* 2 digits/byte! */
	cp(c, b);
	a += NSIZE * sizeof(UWORD) * 2;
	*a = 0;
	while (i--) {
		*--a = d[*c & 15];
		sr(c);
		sr(c);
		sr(c);
		sr(c);
	}
}

/*
 * hn(N a, char *b) -- lower-case hex string to value (use for constants)
 */

PRIVATE void
hn(N a, char *b)
{
	cl(a);
	while (*b) {
		sl(a);
		sl(a);
		sl(a);
		sl(a);
		*a += *b < 'a' ? *b - '0' : *b - ('a' - 10);
		b++;
	}
}

/*
 * integer = ri() -- generate weak pseudorandom integer (range 0-65535)
 */

PRIVATE ULONG
ri(void)
{
	static ULONG s = 27182;
	s = (s * 31421 + 6927) & 0xffff;
	return s;
}

/*
 * prime generation and RSA stuff
 */

/*
 * randomize(N n, ULONG bits) -- pseudorandomize n, limit to value to
 * range 2^bits to 2^(bits+1)-1. This function eors n with weak random
 * generator, n should be initialized with at least bits-bit strong random
 * value before call.
 * (XXX check portablility when converting to >16-bit UWORD machine)
 */

void
randomize(N a, ULONG b)
{
	ULONG i;
	NN c;
	N d = c;
	cp(c,a);
	cl(a);
	if(b>UNIT_BITS*NSIZE-2) {
		i = NSIZE-1;
		b = UNIT_BITS-2;
	} else {
		i = b / UNIT_BITS;
		b = b % UNIT_BITS;
	}
	while (i--)
		*a++ = *d++ ^ ri();
	*a = ((*d ^ ri()) & ((1 << b) - 1)) | (1 << b);
}

/*
 * const sp[PRIMES], PRIMES -- table of small primes, number of primes in table
 */

static unsigned char sp[PRIMES] = {
  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
 59, 61, 67, 71, 73, 79, 83, 89, 97,101,103,107,109,113,127,131,
137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,
227,229,233,239,241,251
};

/*
 * divisor = sieve_prime(N n) -- try to find divisor of n by sieving
 * with small integers returns divisor or 0 if no divisor found.
 */

ULONG
sieve_prime(N n)
{
	ULONG i;
	NN a;
	for(i=0;i<PRIMES;i++) {
		cp(a,n);
		if(!di(a,sp[i]))
			return ((ULONG)sp[i]);
	}
	return (0);
}

/*
 * flag = prob_prime(N n) -- test if 2^(n-1) mod n == 1. Returns 0 if
 * test failed, !0 if success. Large n which passes this test is a
 * probable prime. This test does not work well with small value of n. 
 * Because this test is slow, you should first try sieving n.
 */

int
prob_prime(N m)
{
	ULONG i = NSIZE, j = UNIT_BITS, p = NSIZE;
	NN c, ee;
	N mp, e = ee + NSIZE;
	cl(c);
	*c = 1;
	cp(ee, m);
	sb(ee, c);
	while (!*--e && i)
		i--;
	if (i) {
		while (!(*e & (1 << j)))
			j--;
		*c = 2;
	}
	mp = m + NSIZE;
	while (!*--mp && p)
		p--;
	if (*mp & SIGN_BIT && p < NSIZE)
		p++;
	while (i--) {
		while (j--) {
			pmm(c, c, m, p);
			if (*e & (1 << j)) {
				sl(c);
				if(sb(c, m)) ad(c, m);
			}
		}
		e--;
		j = UNIT_BITS;
	}
	cl(ee);
	*ee = 1;
	return (!cu(c,ee));
}

#ifndef THINK_SILENTLY

/*
 * tw() -- indicate working when checking/generating primes
 */

#include <stdio.h>		/* only for tw() */

static void
tw(void)
{
	static ULONG j = 0;
	putchar("/-\\|"[j & 3]);
	j++;
	putchar('\b');
	fflush(stdout);
}

#endif /* THINK_SILENTLY */

/*
 * next_prime(N a) -- find next probable prime >= a
 */

void
next_prime(N a)
{
	NN b;
	*a |= 1;
	cl(b); *b = 2;
	for (;;) {
#ifndef THINK_SILENTLY
		tw();
#endif /* THINK_SILENTLY */
		if (!sieve_prime(a)) {
			if (prob_prime(a))
				return;
		}
		ad(a, b);
	}
}

/*
 * bits rsa_gen(rsa_key *key) -- generate a RSA key from key->p and key->q
 * Initialize key->p and key->q either with primes or strong random
 * integers of apporopriate size. Returns number of bits in modulus key->pq
 * or 0 if key generation failed.
 */

ULONG
rsa_gen(rsa_key *k)
{
	NN p1, q1, pq1, f, g, t;
	next_prime(k->p);
	next_prime(k->q);
	if (cu(k->p, k->q) < 0) {
		cp(t, k->p);
		cp(k->p, k->q);
		cp(k->q, t);
	}
	hn(t, "1");
	cp(p1, k->p);
	sb(p1, t);
	cp(q1, k->q);
	sb(q1, t);
	cp(g, p1);
	gd(g, q1);
	hn(t, "ff");
	if (cu(t, g) < 0)
		return 0;
	cp(k->pq, k->p);
	mu(k->pq, k->q);
	cp(pq1, p1);
	mu(pq1, q1);
	cp(f, pq1);
	dm(f, g, t);
	hn(k->e, "3");
	hn(k->qp, "1");
	cp(t, pq1);
	gd(t, k->e);
	if (cu(t, k->qp)) {
		hn(k->e, "10001");
		cp(t, pq1);
		gd(t, k->e);
		if (cu(t, k->qp))
			return 0;
	}
	cp(k->d, k->e);
	iv(k->d, f);
	cp(t, k->d);
	dm(t, p1, k->dp);
	cp(t, k->d);
	dm(t, q1, k->dq);
	cp(k->qp, k->q);
	iv(k->qp, k->p);
	cp(t, k->pq);
	for(k->b = 0; ts(t); sr(t), k->b++)
		; /* VOID */
	return (k->b);
}

/*
 * rsa_dec(N m, rsa_key *key) -- low level rsa decryption. Result undefined
 * (ie. wrong) if key is not private rsa key.
 */

void
rsa_dec(N m, rsa_key * k)
{
	NN mp, mq, t;
	cp(t, m);
	dm(t, k->p, mp);
	cp(t, m);
	dm(t, k->q,
	   mq);
	em(mp, k->dp, k->p);
	em(mq, k->dq, k->q);
	if (sb(mp, mq))
		ad(mp, k->p);
	mm(mp, k->qp,
	   k->p);
	mu(mp, k->q);
	ad(mp, mq);
	cp(m, mp);
}

/*
 * rsa_enc(N m, rsa_key *k) -- low level rsa encryption
 */

void
rsa_enc(N m, rsa_key * k)
{
	em(m, k->e, k->pq);
}

/*
 * len = n_to_b(unsigned char *buf, N a) -- convert a to bytes, most
 * significant byte first. Returns number of bytes written to buf. buf
 * should be large enough to hold sizeof(NN) bytes. (Note that number
 * is handled as unsigned, negative value converts to sizeof(NN) bytes.)
 * (XXX check portablility when converting to not-16/32 bit machine)
 */

ULONG
n_to_b(unsigned char *b, N a)
{
	ULONG i = NSIZE - 1, l = 1;
	a += NSIZE;
	while (!*--a && i)
		i--;
	if (*a > 255) {
		*b++ = *a >> 8;
		l++;
	}
	*b++ = *a;
	while (i--) {
		*b++ = *--a >> 8;
		*b++ = *a;
		l += 2;
	} 
	return (l);
}

/*
 * b_to_n(N a, unsigned char *buf,ULONG len) -- convert len bytes from
 * buf to value a. Conversion is unsigned, most significant byte first.
 * (XXX check portablility when converting to not-16/32 bit machine)
 */

void
b_to_n(N a, unsigned char *b, ULONG l)
{
	ULONG i;
	if (l > NSIZE * sizeof(UWORD))
		l = NSIZE * sizeof(UWORD);
	b += l;
	cl(a);
	i = l / 2;
	while (i--) {
		*a = *--b;
		*a++ |= (ULONG) *--b << 8;
	}
	if (l & 1)
		*a = *--b;
}

/*
 * mrsa.h -- Multiprecision math and  RSA public key crypt library
 * 1993 Risto Paasivirta, paasivir@jyu.fi
 * Public Domain, no warranty. Use as you wish.
 */

#ifndef	MRSA_H
#define MRSA_H 1
#ifndef NSIZE
/* #define NSIZE 32 for max 512 (actually 511) bit modulus */
#define NSIZE 16
#endif

/*
 * unsigned 16 and 32 -bit types (other sizes may need some porting)
 */

#ifndef	UWORD	
typedef unsigned short UWORD;
#endif
#ifndef	ULONG
typedef unsigned long ULONG;
#endif

typedef UWORD *N, NN[NSIZE];

typedef struct rsa_key {
	ULONG b;
	NN pq,e,d,p,q,dp,dq,qp;
} rsa_key;

#if !defined(RSA_ONLY) || defined(MRSA_C)

#define UNIT_BITS 16		/* unit bits */
#define SIGN_BIT (1<<15)	/* top bit of unit */
#define PRIMES 54		/* number of primes in prime table */

#ifdef	RSA_ONLY	/* define RSA_ONLY if math stuff not needed */
#define PRIVATE static
#else
#define PRIVATE
#endif


int	ts(N a);		/* test signed, returns -1, 0 or 1 */
ULONG	ng(N a);		/* negate, return carry*/
void	cl(N a);		/* clear */
void	cp(N a,N b);		/* copy, a = b */
int	cu(N a,N b);		/* compare unsigned, returns, -1 0 or 1 */
ULONG	ad(N a,N b);		/* add, a += b */
ULONG	sb(N a,N b);		/* substract, a -= b */
ULONG	sr(N a);		/* shift right, a >>= 1, return carry */
ULONG	sl(N a);		/* shift left, a <<= 1, return carry */
void	dm(N a,N b,N c);	/* div-mod unsigned, a /= b, c = a % b */
void	mu(N a,N b);		/* multiply unsigned, a *= b */
void	mm(N a,N b,N m);	/* modular multiply, a = a * b mod m */
void	em(N a,N e,N m);	/* modular exponentiation, a = a^e mod m */
void	gd(N a,N b);		/* greatst common divisor, a = ***(a,b) */
void	iv(N a,N b);		/* multiplicative inverse, a = a^{-1} mod p */
void	nh(char *a,N b);	/* convert number to hex string */
void	hn(N a,char *b);	/* convert lowercase hex string to number */
ULONG	ri();			/* weak pseudorandom integer */

#if	defined(AMIGA) && defined(MRSA_C)
__stdargs pmm(N aa, N b, N m, ULONG p); /* assembler modmul (SAS 6.2) */
#endif

#endif /* RSA_C */

void	randomize(N a, ULONG bits);
ULONG	sieve_prime(N);
int	prob_prime(N);
void	next_prime(N);
ULONG 	rsa_gen(rsa_key *);
void 	rsa_enc(N,rsa_key *);
void 	rsa_dec(N,rsa_key *);
ULONG 	n_to_b(unsigned char *,N);
void 	b_to_n(N,unsigned char *,ULONG);

#endif /* MRSA_H */