-
using System;
using c;
using
/*RSA
算法
1978
年就出现了这种算法,它是第一个既能用于数据加密也能用于数字签名的算
法。它易
于理解和操作,也很流行。算法的名字以发明者的名字命名:
< br>Ron Rivest, AdiShamir
和
Leonard Adleman
。
但
RSA
的安全性一直未能得到理论上的证明。
RSA
的安全性依赖于大数难于分解这一特点。公钥
和私钥都是两个大素数(大于
100
个十
进制位)
的函数。
据猜测,
从一个密
钥和密文推断出明文的难度等同于分解两个大素数的积。
密钥对的产生。选择两个大素数,
p
和
q
。计算:
n = p * q
然后随
机选择加密密钥
e
,要
求
e
和
( p - 1 ) * ( q - 1 )
互质。
最后,
利用
Euclid
算法计算解密密钥
d,
满足
e * d = 1 ( mod
( p - 1 ) * ( q - 1 ) )
其中
n
和
d
也要互质。数
e
和
n
是公钥
,
d
是私钥。两个素数
p
和
q
不
再需要,应该丢弃,
不要让任何人知道。加密信息
m
(二
进制表示)时,首先把
m
分成等
长数据
块
m1 ,m2,..., mi
,
块长
s
,
其
中
2^s <= n, s
尽可能的大。
对应的密文是:
ci =
mi^e
( mod n ) ( a )
解密时作如下计算:
mi = ci^d ( mod n )
( b )
RSA
可用于数字签名,方案是用
( a
)
式签名,
( b
)
式验证。具体操作时考虑到安全性和
m
信息量较大等因素,一般是先作
HASH
运算。
RSA
的安全性。
RSA
的安全性依赖于大
数分解,但是否等同于大
数分解一直未能得到理论上的证明,因为没有证明破解
RSA
就
一
定需要作大数分解。
假设存在一种无须分解大数的算法,
p>
那它肯定可以修改成为大数分解算
法。目前,
RSA
的一些变种算法已被证明等价于大数分解。不管怎样,分解
n
是最显然的
攻击方法。现在,人们已能分解
140
多个十进制位的大素数。因此,模数
n
必须选大一些,
因具体适用情况而定。
p>
由于进行的都是大数计算,使得
RSA
最快
的情况也比
DES
慢上
100
倍,无论是软件还是
硬件实现。速度一直是
RS
A
的缺陷。一般来说只用于少量数据加密。
*/
namespace
{
class IntRSA :
MyRSAInterface
{
/*
RSA
算法
1978
年就出现了这种
算法,它是第一个既能用于数据加密也能用于数字签名的算法。
它易于理解和操作,也很流
行。算法的名字以发明者的名字命名:
Ron Rivest,
AdiShamir
和
Leonard Adleman
。
但
RSA
的安全性一直未能得到理论上的证明。
RSA
p>
的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数(大于
< br>100
个
十进制位)的函数。据猜测,从一个密钥和密文推断出
明文的难度等同于分解两个大
素数的积。
密钥对的产生。选择两个大素数,
p
和
q
。计算:
n = p * q
然后随
机选择加密密钥
e
,
要求
e
和
( p - 1 ) * ( q
- 1 )
互质。最后,利用
Euclid
算法计算解密密钥
d,
满足
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中
n
和
d<
/p>
也要互质。数
e
和
n
是公钥,
d
是私钥。
两个素数
p>
p
和
q
不再需要,
应该丢弃,不要让任何人知道。加密信息
m
< br>(二进制表示)
时,
首先把
m
分成等长数据块
m1 ,m2,..., mi
,块长
s
,其中
2^s <= n, s
尽可能的大。对
应
的密文是:
ci = mi^e ( mod n ) .................(
a )
解密时作如下计算:
mi = ci^d ( mod n )
.................( b )
RSA
可用于数字签名,方案是用
( a )
式签名,
( b
)
式验证。具体操作时考虑到安全
性
和
m
信息量较大等因素,一般是先作
HA
SH
运算。
RSA
的安全性。
p>
RSA
的安全性依
赖于大数
分解,
但是否等同于大数分解一直未能得到理论上的证明,
因为没有证明破解<
/p>
RSA
就一
定
需要作大数分解。假设存在
一种无须分解大数的算法,那它肯定可以修改成为大数分解
算法。
目前,
RSA
的一些变种算法已被证明等价于大数分解。不管怎样,分解
n
是最显然的攻
击方法。
现在,人们已能分解
140
多个十进制位的大素数。因此,模数
n
必须选大一些,因具体
适用情况而定。
由于进行的都是大数计算,使得
RSA
最快的情况也比
DES
慢上
100
p>
倍,无论是软件还
是硬件实现。
速度一直是
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
、如果
p>
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
位
(
二进制位
)
的素数,最多
32
位
*/
UInt64
RandomPrime(char bits)
{
UInt64 bas;
do
{
bas =
(UInt32)1 << (bits - 1);
//
保证最高位是
1
bas += g_(bas);
//
再加上一个随机数
bas |= 1;
//
保证
最低位是
1
,即保证是奇数
}
while (0 == RabinMiller(bas, 30)); //
(!RabinMiller(bas, 30))
//
进行拉宾-米勒
测试
30
次
return bas;
//
全部通过认为是素数
}
/*
欧几里得法求最大公约数
*/
UInt64
EuclidGcd(UInt64 p, UInt64 q)
{
UInt64 a = p > q ? p : q;
UInt64 b = p < q ? p : q;
UInt64 t;
if (p == q)
{
return p;
//
两数相等,最大公约数就是本身
}
else
{
while (0 != b) //(b)
//
p>
辗转相除法,
gcd(a,b)=gcd(b,a-qb)
-
-
-
-
-
-
-
-
-
上一篇:管道英文缩写
下一篇:物品库存管理课程设计报告