rsa算法介绍

但是否等同于大数分解一直未能得到理论上的证明，

因为没有证明破解< /p>

RSA

就一

定

需要作大数分解。假设存在 一种无须分解大数的算法，那它肯定可以修改成为大数分解

算法。

目前，

RSA

的一些变种算法已被证明等价于大数分解。不管怎样，分解

n

是最显然的攻

击方法。

现在，人们已能分解

140

多个十进制位的大素数。因此，模数

n

必须选大一些，因具体

适用情况而定。

由于进行的都是大数计算，使得

RSA

最快的情况也比

DES

慢上

100

倍，无论是软件还

是硬件实现。

速度一直是

RSA

的缺陷。一般来说只用于少量数据加密。

*/

public struct RSA_PARAM

{

public UInt64 p, q;

//

两个素数，不参与加密解密运算

public UInt64 f;

//f=(p -1)*(q-1)

，不参与加密解密运算

public UInt64 n, e;

//

公匙，

n=p*q

，

g cd(e,f)=1

public UInt64 d;

//

私匙，

e*d=1 (mod f)

，

gcd(n,d)=1

public UInt64 s;

//

块长，满足

2^s<=n

的最大的

s

，即

log 2(n)

};

//

小素数表

#region Prime Table

readonly static long[] g_PrimeTable =

{

3,

5,

7,

11,

13,

17,

19,

23,

29,

31,

37,

41,

43,

47,

53,

59,

61,

67,

71,

73,

79,

83,

89,

97

};

#endregion

readonly long g_PrimeCount = g_;

const UInt64 multiplier =

const UInt64 adder = 42234541;

//

随机数类

public class RandNumber

{

/* */

private UInt64 randSeed;/* */

public RandNumber() : this(0) { }

public RandNumber(UInt64 s)

{

if (0 == s)//(!s)

{

randSeed = (UInt64)new Random().Next();//time(NULL);

}

else

{

randSeed = s;

}

}

/* */

public UInt64 Random(UInt64 n)

{

randSeed = multiplier * randSeed + adder;

return randSeed % n;

}

}

static RandNumber g_Rnd = new RandNumber();

/*

模乘运算，返回值

x=a*b mod n */

UInt64 MulMod(UInt64 a, UInt64 b, UInt64 n)

{

return a * b % n;

}

/*

模幂运算，返回值

x=base^pow mod n */

UInt64 PowMod(UInt64 bas, UInt64 pow, UInt64 n)

{

UInt64 a = bas, b = pow, c = 1;

while (b != 0)

// (b)

{

while (1 != (b & 1))

// !(b&1)

{

b >>= 1;

//a=a * a % n;

//

< br>函数看起来可以处理

64

位的整数，但由于

这里

a*a

在

a>=2^3 2

时已经造成了溢出，因此实际处理范围没有

64

位

a = MulMod(a, a, n);

} b--;

//c=a * c % n;

//

这里也会溢出，若把

64

位整数拆为两个

32

位整

数不知是否可以解决这个问题。

c = MulMod(a, c, n);

} return c;

}

/*

Rabin-Mi ller

素数测试，通过测试返回

1

， 否则返回

0

。

n

是待测素数。

注意：通过测试并 不一定就是素数，非素数通过测试的概率是

1/4

*/

long RabinMillerKnl(UInt64 n)

{

UInt64 b, m, j, v, i;

m = n - 1;

j = 0;

//0

、先计算 出

m

、

j

，使 得

n-1=m*2^j

，其中

m

是正奇数，

j

是非负整数

while (1 != (m & 1))

// (!(m & 1))

{

++j;

m >>= 1;

}

//1

、随机取一个

b

，

2<=b

b = 2 + g_(n - 3);

//2

、计算

v=b^m mod n

v = PowMod(b, m, n);

//3

、如果

v==1

，通过测试

if (v == 1)

{

return 1;

}

//4

、令

i=1

i = 1;

//5

、如果

v=n-1

，通过测试

while (v != n - 1)

{

//6

、如果

i==l

，非素数，结束

if (i == j)

{

return 0;

}

//7

、

v=v^2 mod n

，

i=i+1

v = PowMod(v, 2, n);

++i;

//8

、循环到

5

} return 1;

}

/*

Rabin-Miller

< br>素数测试，循环调用核心

loop

次

全部通过返 回

1

，否则返回

0

*/

long RabinMiller(UInt64 n, long loop)

{

//

先用小素数筛选一次，提高效率

for (long i = 0; i < g_PrimeCount; i++)

{

if ((n % unchecked((ulong)g_PrimeTable[i])) == 0)

{

return 0;

}

}

//

循环调用

Rabin-Mille r

测试

loop

次，使得非素数通过测 试的概率降为

(1/4)^loop

for (long i = 0; i < loop; i++)

{

if (0 == RabinMillerKnl(n)) //(! ...)

{

return 0;

}

} return 1;

}

/*

随机生成一个

bits