051210-rsa.cpp

利用密码学中重要算法RSA

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>

long gcd(long n,int u);
int sushu(int n);
int mod_invese(int e, long n);
int mod_power(int a, int k, long n);
int encrypt(int m, int e, long n);
void dncrypt(int c, int d, long n);
//主函数
//控制RSA公私密钥对的产生等
void main()
{
	int n, i = 0;
	long num;
    int s[2];
	long fi;
    int e, d;//密钥空间
	int j;
	char m;//明文空间
	int c;//密文空间
	srand(time(NULL));
	do{
		n = rand();
		num = n * n;
		n = num % 256;   //产生一个256以内的随机数
		if(n % 2 == 0)
			n = n - 1;     //若是偶数则减1成为奇数

		if(sushu(n))       //如是是素数则作为p或q
		{
			printf("p%d是%d\n", i, n);
			s[i] = n;
			i++;
		}
		                        
		if(i == 2)                  //p,q都产生后，得到其乘积n,并判断n是否越界
		{
			num = (long) s[0] * s[1];
			if(num < 0)                //如果n越界，则重新产生p,q
			{
				printf("错误的数据!!数据过大!!\n\n");
				i = 0;
				continue;
			}
			printf("n的值是：%ld\n", num);   //没有越界则输出n，进行下一步程序
		}
	}while(i < 2);

	fi = (s[0] - 1) * (s[1] - 1);                   //得到
	printf("fi的值是：%ld\n", fi);
	do
	{
		n = rand();
		j = (int) (n * n) % fi;    //产生一个大于1小于fi 的随机数e
		if(gcd(fi, j) == 1)    //判断其是否与fi互素
		{
			e = j;              //互素则作为公钥e
			printf("e的值是：%d\n", e);
			break;
		}
	}while(1);

	d = mod_invese(e, fi);      //得到私钥
	printf("d是:%d\n", d);

		
	printf("输入要加密的明文字符\n");  //使用RSA对一个字符进行加密
	do{
		scanf("%c", &m);      //输入要加密的字符
		getchar();            //接收上句的enter键
		
		if(m == 10)           //若直接按enter则输入退出加密
			break;
		c = encrypt(m, e, num);
		dncrypt(c, d, num);
		printf("输入要加密的明文字符\n");
	}while(1);
}

//求最大公因数的函数，用的是Euclid算法
//该函数用于判断一个随机选取的数e（公钥）是还与fi是互素的
//当它们的最大公因子为1时是互素
long gcd(long n,int u)
{
	long n1;
	long n2,q,r;
	n1 = n;
	n2 = u;
	do{
		q = (int )n1 / n2;
		r = (int) n1 - q * n2;
		if(r == 0)
			return n2;
		else
		{
			n1 = n2;
			n2 = r;
		}
	}while(1);
}

//判断一个数是否素数的函数
//用的是穷举的方法，即用小于n的所有数去除n,当没有数能整除n时为素数
int sushu(int n)
{
	int i;
	for(i = 2; i < n; i++)
	{
		if(n % i == 0)
		{
			return(0);
		}
	}
	return 1;
}

//求模逆的函数
//用到了扩展的Euclid算法的修改算法
int mod_invese(int e, long n)
{
	long n1;
	int n2, q, r;
    int b1 = 0, b2 = 1;
	int t;
	n1 = n;
	n2 = e;
	do{
		q = (int) n1 / n2;
		r = n1 - n2 * q;
		n1 = n2;
		n2 = r;
		t = b2;
		b2 = b1 - q * b2;
		b1 = t;
	}while(r != 1);

	if(b2 < 0)
		b2 = b2 + n;
	return b2;

}
//模幂算法，用于求a^e(mod n)
int mod_power(int a, int k, long n)
{
	int x, y, c = 1;
	x = a;
	y = k;
	if(y == 0)
		return c;
	do
	{
		if(y % 2 != 0)
		{
			y = y - 1;
			c = (c * x) % n;
			if(y == 0)
				return c;
		}
		else
		{
			y = y / 2;
			x = (x * x) % n;
		}
	}while(1);
}
//RSA体制的加密／签名
int encrypt(int m, int e, long n)
{
	int c;
	c = mod_power(m, e, n);
	printf("密文是：%ld\n", c);
	return c;


}
void dncrypt(int c, int d, long n)
{
	int m;
	m = mod_power(c, d, n);
	printf("解密结果是：%c\n", m);
}