pollard.cpp

RSA加密解密BMP图象,并用pollord算法对其进行分析,能够成功加密图象

#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<windows.h> 

/*
  函数作用：十进制数转换成二进制数
  参数：十进制数
  返回值：转换以后得到的二进制数组
*/

int *ten_to_two(int m)
{
	int *array;
	int i, k;
	array = new int[1024];

	i = 0;
	k = m;
	while(k != 0)
	{
		array[i] = (k % 2);
		k = k / 2;
		i++;
	}
	array[i] = 2;
	return array;
}

/*
  函数作用：快速指数算法
  参数：二进制数组，底数，模n
  返回值：计算的得到的结果
*/

int pow(int *array, int a, int n)
{
	int d = 1;
	int i = 0, k;
	while(array[i] != 2)
		i++;
	k = i;
	for(i = k - 1;i >= 0;i--)
	{
		d = (d * d) % n;
		if(array[i] == 1)
			d = (d * a) % n;
	}
	return d;
}

/*
  函数作用：计算两个数的除1以外的公约数
  参数：要计算公约数的两个数
  返回值：返回他们的非1公约数，如果没有则返回-1
*/


int gcd(int a, int n)
{
	int i;
	if(n % a == 0)
		return a;
	else
	{
		i = 1;
		while(1)
		{
			i++;
			if((a % i == 0) && (n % i == 0))
				return i;
			else if(i >= a)
				return -1;
		}
	}
}

/*
  函数作用：pollard p-1算法分解模n
  参数：模n
  返回值：n的一个因子
*/

int pollard_p_1(int n)
{
	int a = 2, b = 2, d = -1, j, m, *array;
	while((d == -1) && b < ((int)sqrt((double)n)))
	{
		for(j = 2;j <= b;j++)
		{
			array = ten_to_two(j);
			m = pow(array, a, n);
			a = (a * m) % n;
		}
		d = gcd(a - 1, n);
		b++;
	}
	return d;
	

}


/*
 函数作用：pollard row算法分解n 
  参数：模n
  返回值：n的一个因子
*/

int pollard_row(int n)
{
	int x1, x2, p;
	x1 = 1;
	x2 = (x1 * x1 + 1) % n;
	p = gcd(x2 - x1, n);
	while(p == -1 || p == 1)
	{
		x1 = x2;
		x2 = (x2 * x2 + 1) % n;
		x2 = (x2 * x2 + 1) % n;
		if((x2 - x1) > 0)
			p = gcd(x2 - x1, n);
		else if((x2 - x1) < 0)
			p = gcd(x1 - x2, n);
	}
	return p;
}


void main()
{
	double time1, time2;
	
	int n[5], d, p, q, i, flag, j;
	cout<<"请选择破解方法:1是pollard-p-1算法，2是pollard—row算法!"<<endl;
	n[0] = 187;
	n[1] = 899;
	n[2] = 3953;
	n[3] = 13843;
	n[4] = 59989;


	
	cin>>flag;
	
	if(flag == 2)
	{
		for(j = 0;j < 5;j++)
		{
			time1 = GetTickCount();
			for(i = 0;i < 99;i++)
				d = pollard_row(n[j]);
			time2 = GetTickCount();
			time2 = time2 - time1;
			time2 = (time2 / 100);
			cout<<"time = "<<time2;
			cout<<endl;
			p = d;
			q = n[j] / p;
			cout<<"n = "<<n[j]<<endl;
			cout<<"p: "<<p<<endl;
			cout<<"q: "<<q<<endl;
		}
	}
	else
	{
		for(j = 0;j < 5;j++)
		{
			time1 = GetTickCount();
			for(i = 0;i < 99;i++)
				d = pollard_p_1(n[j]);
			time2 = GetTickCount();
			time2 = time2 - time1;
			time2 = (time2 / 100);
			cout<<"time = "<<time2;
			cout<<endl;
			p = d;
			q = n[j] / p;
			cout<<"n = "<<n[j]<<endl;
			cout<<"p: "<<p<<endl;
			cout<<"q: "<<q<<endl;
		}
	}

}