计算机 密码学 实验四_RSA公钥密码体制实验
- 格式：docx
- 大小：207.79 KB
- 文档页数：4
实验四：RSA公钥密码体制实验安全0901 王宇航 09283020
实验报告
1.实验步骤1：
2.实验步骤2、3、4：
（1）文字描述每个函数的实现原理
1-RSA计算
公钥和私钥的产生
假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。
她可以用以下
的方式来产生一个公钥和一个私钥：
随意选择两个大的质数p和q，p不等于q，计算N=pq。
根据欧拉函数，不大于N且与N互质的整数个数为(p-1)(q-1)
选择一个整数e与(p-1)(q-1)互质，并且e小于(p-1)(q-1)
用以下这个公式计算d：d× e ≡ 1 (mod (p-1)(q-1))
将p和q的记录销毁。
(N,e)是公钥，(N,d)是私钥。
(N,d)是秘密的。
Alice将她的公钥(N,e)传给Bob，而
将她的私钥(N,d)藏起来。
加密消息
假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。
他使用起先与
Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。
假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。
用下面这个公式他可以将n加密为c：
计算c并不复杂。
Bob算出c后就可以将它传递给Alice。
解密消息
Alice得到Bob的消息c后就可以利用她的密钥d来解码。
她可以用以下这个公式来将c转换为n：
得到n后，她可以将原来的信息m重新复原。
解码的原理是
以及ed≡ 1 (mod p-1)和ed≡ 1 (mod q-1)。
由费马小定理可证明（因为p和q 是质数）和
这说明（因为p和q是不同的质数，所以p和q互质）
签名消息
RSA也可以用来为一个消息署名。
假如甲想给乙传递一个署名的消息的话，那么她可以为她的消息计算一个散列值(Message digest)，然后用她的密钥(private key)加密这个散列值并将这个“署名”加在消息的后面。
这个消息只有用她的公钥才能被解密。
乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。
假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。
（2）函数说明(包括函数参数, 返回值及实现过程的说明)
2-扩展欧几里德算法
void ext_euclid(inta,int b)：
使用递归算法实现gcd(a,b)=gcd(b,a mod b)。
3-模幂运算
void modular_exponentitation(intx,intr,intp,int t)：
使用递归算法实现：
(1) a←x, b←r , c←1
(2)若b=0，则输出c, 结束．
(3)若b是正的偶数，则b←b/2，a ←a2 mod p, 转(3)
否则, 转(4).
(4) b←b-1, c ←a*c mod p ,转(2).
4-欧拉函数Ø(n)
函数的值：
通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为
x的所有质因数，x是不为0的整数。
φ(1)=1（唯一和1互质的数就是1本身）。
(注意：每种质因数只一个。
比如12=2*2*3
那么φ（12）=12*（1-1/2）*(1-1/3)=4)
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，
其他数都跟n互质。
（3）程序运行结果截图
3.写出实现过程中遇到的困难及解决办法：。
