?? rsa.cpp
字號:
vlong operator <<( const vlong& x, DWORD n ) // multiply by 2**n
{
vlong result = x;
while (n)
{
n -= 1;
result += result;
}
return result;
}
vlong abs( const vlong & x )
{
vlong result = x;
result.negative = 0;
return result;
}
long product ( const vlong &X, const vlong &Y )
{
return X.value->product( *Y.value );
}
vlong pow2( DWORD n )
{
vlong result;
result.setbit(n);
return result;
}
vlong gcd( const vlong &X, const vlong &Y )
{
vlong x=X, y=Y;
while (1)
{
if ( y == 0 ) return x;
x = x % y;
if ( x == 0 ) return y;
y = y % x;
}
}
vlong modinv( const vlong &a, const vlong &m ) // modular inverse
// returns i in range 1..m-1 such that i*a = 1 mod m
// a must be in range 1..m-1
{
vlong j=1,i=0,b=m,c=a,x,y;
while ( c != 0 )
{
x = b / c;
y = b - x*c;
b = c;
c = y;
y = j;
j = i - j*x;
i = y;
}
if ( i < 0 )
i += m;
return i;
}
class monty // class for montgomery modular exponentiation
{
vlong m,n1;
vlong T,k; // work registers
DWORD N; // bits for R
void mul( vlong &x, const vlong &y );
public:
vlong R,R1;
vlong exp( const vlong &x, const vlong &e );
vlong monty_exp( const vlong &x, const vlong &e );
monty( const vlong &M );
};
monty::monty( const vlong &M )
{
m = M;
N = 0; R = 1;
while ( R < M )
{
R += R;
N += 1;
}
R1 = modinv( R-m, m );
n1 = R - modinv( m, R );
}
void monty::mul( vlong &x, const vlong &y )
{
// T = x*y;
T.value->fast_mul( *x.value, *y.value, N*2 );
// k = ( T * n1 ) % R;
k.value->fast_mul( *T.value, *n1.value, N );
// x = ( T + k*m ) / R;
x.value->fast_mul( *k.value, *m.value, N*2 );
x += T;
x.value->shr( N );
if (x>=m) x -= m;
}
vlong monty::monty_exp( const vlong &x, const vlong &e )
{
vlong result = R-m, t = x; // don't convert input
t.docopy(); // careful not to modify input
DWORD bits = e.value->bits();
DWORD i = 0;
while (1)
{
if ( e.value->bit(i) )
mul( result, t);
i += 1;
if ( i == bits ) break;
mul( t, t );
}
return result; // don't convert output
}
vlong monty::exp( const vlong &x, const vlong &e )
{
return ( monty_exp( (x*R)%m, e ) * R1 ) % m;
}
//// 求 x的e次冪，再對m求模
vlong modexp( const vlong & x, const vlong & e, const vlong & m )
{
monty me(m);
return me.exp( x,e );
}
vlong monty_exp( const vlong & x, const vlong & e, const vlong & m )
{
monty me(m);
return me.monty_exp( x,e );
}
vlong monty_exp( const vlong & x, const vlong & d, const vlong & m, const vlong &p, const vlong &q )
{
monty me(m);
vlong x1 = ( x * me.R1 ) % m; // Transform input
vlong u = modinv( p, q );
vlong dp = d % (p-1);
vlong dq = d % (q-1);
// Apply chinese remainder theorem
vlong a = modexp( x1 % p, dp, p );
vlong b = modexp( x1 % q, dq, q );
if ( b < a ) b += q;
vlong result = a + p * ( ((b-a)*u) % q );
// Transform result
return ( result * me.R ) % m;
}
static vlong half(const vlong &a, vlong p)
{
if (a.bit(0))
return (a+p)/2;
return a/2;
}
vlong lucas ( vlong P, vlong Z, vlong k, vlong p ) // P^2 - 4Z != 0
{
vlong D = P*P - 4*Z, U = 1, V = P, U1,V1;
DWORD i=k.bits()-1;
while (i)
{
i -= 1;
U1 = U*V; V1 = V*V + D*U*U; U = U1%p; V = half(V1%p,p);
if ( k.bit(i) )
{
U1 = P*U+V; V1 = P*V+D*U; U = half(U1%p,p); V = half(V1%p,p);
}
}
return V;
}
vlong sqrt( vlong g, vlong p )
{
vlong result;
if (p%4==3)
result = modexp( g, p/4+1, p );
else if (p%8==5)
{
vlong gamma = modexp( 2*g, p/8, p);
vlong i = 2*g*gamma*gamma - 1;
result = g*gamma*i;
}
else
{
vlong Z = g;
vlong P = 1;
while (1)
{
vlong D = (P*P-4*g)%p; if (D<0) D += p;
if ( D==0 )
{
result = half(P,p);
break;
}
if ( modexp( D, (p-1)/2, p ) != 1 )
{
result = half( lucas( P, Z, (p+1)/2, p ), p );
break;
}
P += 1; // Is this ok (efficient?)
}
}
result = result % p;
if ( result < 0 ) result += p;
return result;
}
/***************"vlong.cpp"********************/
/***************"rsa.cpp"********************/
//#include "rsa.h"
static vlong from_str( const char * s )
{
vlong x = 0;
while (*s)
{
x = x * 256 + (unsigned char)*s;
s += 1;
}
return x;
}
public_key::public_key()
{
/*在這里必須初始化requires為1，否則無法進行加解密
在Debug版中它初始化就不會為0，而在Release版中它初始化為0
這就會出現只有Release版才會出的錯*/
requires = true;
}
void private_key::create()
{
char prand[2][LEVEL * 4/*必須不小于LEVEL*2 */], tc;
DWORD i, j;
DWORD validate[LEVEL]; //驗證m的最高位是否為0
prime_factory pf;
vlong tmp;
start: //條件不成立，重新再生成p和q
srand((unsigned)time(NULL));
for(i = 0; i < 2; i++)
{
for(j = 0; j < (LEVEL * 2); j++)
{
tc = (char)(0x41+rand()%0xAF);
prand[i][j] = tc;
}
prand[i][j]=0;
}
// Choose primes
p = pf.find_prime( from_str(prand[0]) );//計算生成兩個大奇數 p, q
q = pf.find_prime( from_str(prand[1]) );
if ( p > q )
{
tmp = p;
p = q;
q = tmp;
}
// Calculate public key
m = p * q; //當m的最高位是非0時，要加密的大整數最高位是0，就滿足加密的條件了
m.store(validate, LEVEL);
//如果這個m不能滿足條件，就重新生成p和q，直到條件成立，其實這也不能完全解決問題還是要有requires
if(validate[LEVEL - 1] == 0x00000000) goto start;
e = 65537; //如果這個固定的e不能滿足條件，就重新生成p和q，直到條件成立
if( gcd(p-1,e) != 1 || gcd(q-1,e) != 1 ) goto start;
/*while ( gcd(p-1,e) != 1 || gcd(q-1,e) != 1 )
{
e += 2;
}*/
}
vlong public_key::encrypt( const vlong& plain )
{
if(plain >= m)
{
requires = false;
//::MessageBox(NULL,"加密的數必須小于m","public_key::encrypt",MB_ICONSTOP);
}
if(!requires)
{ //只有出錯一次就永遠不能進行加密，只有再把requires=true
return m;
}
return modexp( plain, e, m );
}
vlong private_key::decrypt( const vlong& cipher )
{
if(cipher >= m)
{
requires = false;
//::MessageBox(NULL, "加密的數必須小于m", "private_key::decrypt", MB_ICONSTOP);
}
if(!requires)
{ //只有出錯一次就永遠不能進行加密，只有再把requires=true
// ::MessageBox(NULL,"我錯了","private_key::decrypt",MB_ICONSTOP);
return m;
}
// Calculate values for performing decryption
// These could be cached, but the calculation is quite fast
vlong d = modinv( e, (p-1)*(q-1) );
vlong u = modinv( p, q );
vlong dp = d % (p-1);
vlong dq = d % (q-1);
// Apply chinese remainder theorem
vlong a = modexp( cipher % p, dp, p );
vlong b = modexp( cipher % q, dq, q );
if ( b < a ) b += q;
return a + p * ( ((b-a)*u) % q );
}
void public_key::PK_to_vlong(PK pk)
{
m.load(pk.m, LEVEL);
e = 65537; //一個固定的e
}
void private_key::SK_to_vlong(SK sk)
{
p.load(sk.p, LEVEL / 2);
q.load(sk.q, LEVEL / 2);
m = p * q;
e = 65537; //一個固定的e
}
void public_key::vlong_to_PK(PK &pk)
{
//把公開密鑰轉換成可用格式
m.store(pk.m, LEVEL);
}
void private_key::vlong_to_SK(SK &sk)
{
//把私人密鑰轉換成可用格式
p.store(sk.p, LEVEL / 2);
q.store(sk.q, LEVEL / 2);
}
int public_key::get_requires()
{
return requires;
}
void public_key::set_requires(int req)
{
requires = req;
}
void public_key::encrypt(MessageDollop &dollop)
{
vlong m, c;
c.load( (DWORD *)&dollop, LEVEL);
m = encrypt(c);
m.store( (DWORD *)&dollop, LEVEL);
}
void private_key::decrypt(MessageDollop &dollop)
{
vlong m, c;
m.load( (DWORD *)&dollop, LEVEL/*必須是dollop的長度，否則會出錯*/);
c = decrypt(m);
c.store( (DWORD *)&dollop, LEVEL);
}
void public_key::encrypt(MessagePackage &package)
{
MessageDollop dollop;
int quotient, remainder, i;
quotient = (package.n * 2) / sizeof(MessageDollop);
remainder = (package.n * 2) % sizeof(MessageDollop);
quotient = remainder?++quotient:quotient;
for(i = 0;i < quotient;i++)
{ //把消息包分成若干塊
::MoveMemory(
&dollop, //目標
package.data + i * sizeof(MessageDollop),//源內容
sizeof(MessageDollop));
//用公鑰加密消息快
encrypt(dollop); //dollop.nil[0]必須為零，之前應該設置好了，如果已被解密就不用
//把處理的消息保存到原來的消息包中
::MoveMemory(
package.data + i * sizeof(MessageDollop),//目標
&dollop, //源內容
sizeof(MessageDollop));
}
}
void private_key::decrypt(MessagePackage &package)
{
MessageDollop dollop;
int quotient, remainder, i;
quotient = (package.n * 2) / sizeof(MessageDollop);
remainder = (package.n * 2) % sizeof(MessageDollop);
quotient = remainder?++quotient:quotient;
for(i = 0;i < quotient;i++)
{ //把消息包分成若干塊
::MoveMemory(
&dollop, //目標
package.data + i * sizeof(MessageDollop),//源內容
sizeof(MessageDollop));
//用私鑰解密消息快
decrypt(dollop);//dollop.nil[0]必須為零，之前應該設置好了，如果已被加密就不用
//把處理的消息保存到原來的消息包中
::MoveMemory(
package.data + i * sizeof(MessageDollop), //目標
&dollop, //源內容
sizeof(MessageDollop));
}
}
/***************"rsa.cpp"********************/
/***************"prime.cpp"********************/
//#include "prime.h"
long is_probable_prime( const vlong &p )
{
// Test based on Fermats theorem a**(p-1) = 1 mod p for prime p
// For 1000 bit numbers this can take quite a while
const rep = 4;
const DWORD any[rep] = { 2,3,5,7 /*,11,13,17,19,23,29,31,37..*/ };
for ( DWORD i=0; i<rep; i+=1 )
{
if ( modexp( any[i], p-1, p ) != 1 )
return 0;
}
return 1;
}
prime_factory::prime_factory( DWORD MP )
{
np = 0;
// Initialise pl
char * b = new char[MP+1]; // one extra to stop search
for (DWORD i=0;i<=MP;i+=1) b[i] = 1;
DWORD p = 2;
while (1)
{
// skip composites
while ( b[p] == 0 ) p += 1;
if ( p == MP ) break;
np += 1;
// cross off multiples
DWORD c = p*2;
while ( c < MP )
{
b[c] = 0;
c += p;
}
p += 1;
}
pl = new DWORD[np];
np = 0;
for (p=2;p<MP;p+=1)
{
if ( b[p] )
{
pl[np] = p;
np += 1;
}
}
delete [] b;
}
prime_factory::~prime_factory()
{
delete [] pl;
}
vlong prime_factory::find_prime( vlong & start )
{
DWORD SS = 1000; // should be enough unless we are unlucky
char * b = new char[SS]; // bitset of candidate primes
DWORD tested = 0;
while (1)
{
DWORD i;
for (i=0;i<SS;i+=1)
b[i] = 1;
for (i=0;i<np;i+=1)
{
DWORD p = pl[i];
DWORD r = to_unsigned(start % p); // not as fast as it should be - could do with special routine
if (r) r = p - r;
// cross off multiples of p
while ( r < SS )
{
b[r] = 0;
r += p;
}
}
// now test candidates
for (i=0;i<SS;i+=1)
{
if ( b[i] )
{
tested += 1;
if ( is_probable_prime(start) )
{
delete [] b;
return start;
}
}
start += 1;
}
}
}
long prime_factory::make_prime( vlong & r, vlong &k, const vlong & min_p )
// Divide out small factors or r
{
k = 1;
for (DWORD i=0;i<np;i+=1)
{
DWORD p = pl[i];
// maybe pre-computing product of several primes
// and then GCD(r,p) would be faster ?
while ( r % p == 0 )
{
if ( r == p )
return 1; // can only happen if min_p is small
r = r / p;
k = k * p;
if ( r < min_p )
return 0;
}
}
return is_probable_prime( r );
}
/***************"prime.cpp"********************/
/*********試驗************
private_key pv_key;
public_key pl_key;
vlong m, c;
pv_key.create(); //計算生成兩個大奇數公鑰和私鑰：p,q,e,m
//傳遞公鑰，本來已經用CA分配好的了
pl_key.char_to_vlong(pv_key.key);
//要加密的數字標識的數據
DWORD a[8];
a[0] = 1234567890;
a[7] = 3666667777;
c.load(a, 8);
m = pv_key.decrypt(c); //先用私鑰進行加密
c = pl_key.encrypt(m); //再用公鑰進行解密
//可以用在數字簽名中
****************************/
/*******對數據進行加密*******
private_key pv_key;
public_key pl_key;
vlong m//*明文大整數*, c//*密文大整數*;
pv_key.create(); //計算生成兩個大奇數公鑰和私鑰：p,q,e,m
//傳遞公鑰
pl_key.char_to_vlong(pv_key.key);
char *s = new char[VL + 3];
char *q = new char[VL * 4];
//加密數據
pl_key.encrypt(s, VL + 3, q);
pv_key.decrypt(q, VL + 3, s);
*******************************/
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -