rsaclass.cpp

robocup源代码2001年清华机器人源代码

/*
    Copyright (C) 2001  Tsinghuaeolus

    Authors : ChenJiang, YaoJinyi, CaiYunpeng, Lishi

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

	If you make any changes or have any comments we would appreciate a 
	message to [e-mail].
*/

#include "stdafx.h"
#include "RSAClass.h"
#include <math.h>

RSAEncrypt::RSAEncrypt(){
	L=2399798950592707,N=2399798845658776,ONE=1;
}


RSAEncrypt::RSAEncrypt(unsigned _int64 m, unsigned _int64 n){
	setkey(m, n);    
}

void RSAEncrypt::setkey(unsigned _int64 m, unsigned _int64 n){
	L = m * n;
	if (n != 1)
		N=(m - 1) * (n - 1);
	else
		N = m - 1;
}

unsigned _int64 RSAEncrypt::Exponent(unsigned _int64 m, unsigned _int64 e){
	unsigned _int64 result,exp;
	if (m==0) return 0;
	int length = int(log(double(_int64 (e)))/log(2)+1),i;
	for(i=0,exp=m%L,result=1;i<length;i++){
		if ((e&ONE<<i)!=0) 
			result=Model_mutiple(result,exp);
	    	exp=Model_mutiple(exp,exp);
	}
    return result;
}

unsigned _int64 RSAEncrypt::Model_mutiple(unsigned _int64 m, unsigned _int64 n){
	unsigned _int64 num[3],r;
	r = 18446744073709551615%L + 1;
	mutiple(m%L,n%L,&num[0]);
	num[0]=num[0]%L;num[1]=num[1]%L;num[2]=num[1];
	while(num[0]!=0){
		mutiple(num[0],r,&num[0]);
		num[1]=num[1]%L;
		if (18446744073709551615-num[1]<num[2]) num[0]++;
		num[1]=(num[1]+num[2])%L;
		num[2]=num[1];
	}
	return num[1]%L;
}

void RSAEncrypt::mutiple(unsigned _int64 m, unsigned _int64 n, unsigned _int64* num){
	unsigned _int64 high[2],low[2],temp;
	num[0]=0,num[1]=0;
	high[0]=m>>32,high[1]=n>>32;
	temp=4294967295,low[0]=m&temp,low[1]=n&temp;
	num[1]+=low[0]*low[1];
	temp=low[0]*high[1];
	if (18446744073709551615-num[1]<(temp<<32)) num[0]++;
	num[1]+=temp<<32,num[0]+=temp>>32;
	temp=low[1]*high[0];
	if (18446744073709551615-num[1]<(temp<<32)) num[0]++;
	num[1]+=temp<<32,num[0]+=temp>>32;
	num[0]+=high[0]*high[1];
}

_int64 RSAEncrypt::GenerateKey(unsigned _int64 m){
	if (m>N) return -1;
	else
	   return ZZXC(m,N);
}

//solve for d, dm mod n =1,-1 represent no solution
_int64 RSAEncrypt::ZZXC(_int64 m, _int64 n) {
	_int64 a[2],b[2],bigger,smaller,quotient,temp;
	bigger=m>n?m:n;
	smaller=m+n-bigger;
	if (smaller==1) return 1;
	a[0]=1,b[0]=0;
	a[1]=0,b[1]=1;
	do{
		quotient=_int64(bigger/smaller);
		temp=a[1];
		a[1]=a[0]-quotient*a[1];
		a[0]=temp;
		temp=b[1];
		b[1]=b[0]-quotient*b[1];
		b[0]=temp;
		temp=smaller;
		smaller=bigger%smaller;
		bigger=temp;
	}
	while((smaller!=1)&&(smaller!=0));
	if (smaller==0) return -1;
	if (m>n){	
		a[1]=a[1]%n;
		if (a[1]<0) a[1]=n+a[1];
		return a[1];
	}
	else {
		b[1]=b[1]%n;
		if (b[1]<0) b[1]=n+b[1];	
		return b[1];
	}
}