老师给的题目,我止血药满足基本要求就行了!!
相信这好似一道经典的题目了吧,高手们一定都做过!!
有存留的程序代码给小妹一个!!
谢谢啊!老师的基本要求如下:
题目: RSA 公开密钥加密系统
在公开密钥加密系统中, 每个当事方均有一对密钥(e,d). 其中 e是公开密钥而d 是私有密钥. 公开密钥 e 是要公开的. 而私有密钥只有当事人自己知道. 假设当事双方 Alice 和 Bob 的密钥对分别为 (eA, dA) 和 (eB, dB). 如果 Alice 欲给 Bob 发送明文 m, Alice 用 Bob 的公开密钥 eB 将明文m 加密为 c = E(m, eB), 然后将密文 c 发送个Bob. 收到密文后, Bob 用自己的私有密钥 dB 将密文解密, 还原明文: m = D(c, dB).
对公开密钥加密系统的基本要求是, 用公开密钥e 加密的密文, 只有用与之对应的私有密钥 d 才能正确解密, 并且从公开密钥e 推算出私有密钥 d 是非常困难的.
基本要求
1.选择适当的基底以及适当的数据结构, 实现长整数运算类. 并且定义适当的运算符或者函数实现长整数的四则运算, 求余运算, 赋值运算或者交换(swap)运算.
2.实现ab mod n 的计算. 其中0 <= a, b < n. a, b, n 均为长整数.
3.实现欧几里德算法以及扩展的欧几里德算法.
4.选择或者实现一个加快的伪随机数算法. 使用Rabin_Miller 素性测试算法. 实现工业素数的产生算法.
5.实现生成RSA1024 密钥对函数::
void generate_rsa1024_key_pair(RSA_key& e, RSA_key& d);
6.实现RSA1024 加解密算法:
bool RSA1024(char result[1024/8], char const source[1024/8], RSA_key const& key);
较高要求
1.对公钥e 为 3, 257, 216 + 1, 给出特别实现的加密算法.
2.已知 n = pq 中的p和q, 利用中国剩余定理, 给出解密算法的快速实现.
3.实现
short remainder(Math_int const& a, short b),
它返回 a 除以 b 的余数. 求出[3, 216] 之间的所有素数. 从而可以快速判别一个长整数 a 是否包含这些素因子.
4.实现
Math_int remainder(Math_int const& a, Math_int const& b);
它返回a 除以 b 的余数 r, 使得 r 满足: -b/2 <= r < b/2. 利用这个函数实现欧几里德算法和扩展的欧几里德算法. 将这个结构和普通的欧几里德算法与扩展的欧几里德算法进行比较,
5.实现二进制欧几里德算法与扩展欧几里德算法, 并将结果与普通的欧几里德算法进行比较. 二进制欧几里德算法的递归描述为:
gcd(a, b) = 2 gcd(a/2, b/2); 如果a, b 均为偶数.
gcd(a, b) = gcd(a, b/2); 如果a 为奇数, b 为偶数;
gcd(a, b) = gcd(a/2, b); 如果a为偶数, b为奇数.:
gcd(a, b) = gcd(a-b, b); 如果 a, b 均为奇数.
6.利用公式
xy = (x12n + x0)(y12n + y0) = x1y122n +[(x0+x1)(y0+y1) – x1y1 - x0y0]2n + x0y0
给出长整数乘法的快速算法. 注意, 当 n 为16时, 就可以直接使用计算机本身的乘法运算计算. 分析这个算法的复杂度.
7.查阅资料, 实现求 a mod n 的Barrett 算法. 其中 a < n2.
8.用下面的牛顿迭代法可以求奇数a 的逆元 b = a-1 mod W, 其中 W = 2k
xn+1 = xn(2-axn)
如果适当选取初始值x0. 上面的迭代很快就收敛到a 的模 W 的逆元. 容易证明 如果 xn ≡1 mod 2k, 则, xn+1 ≡1 mod 22k. 用这里介绍的方法求a-1 mod 21024 . 其中 a 为奇数. 初始值x0 可以选取a. 其满足x0 ≡1 mod 8. 选择更好的x0, 使得x0 ≡1 mod 16.
联系方式:703970869@qq.com 谢谢昂!!!!