密码学第二次实验报告：RSA算法
实验题目
RSA算法
实验目的
了解公钥算法基本原理和RSA算法的原理。了解RSA算法在数据加密和数字签名中的应用。了解RSA算法中大和数分解的困难性，从而理解单向函数的
内涵。
实验要求
- 编程实现素数的选择判断
- 编程实现模逆算法。
- 编程实现快速模指运算。
- 编程实现RSA算法。
- 编程实现利用RSA进行数据加解密。
- 实现利用RSA对较大数据进行加解密（选作）
- 实现简单的GUI界面
实验原理与理论基础
RSA算法：
简介
RSA算法的单向函数基于质因数分解问题。
质因数分解问题指数论中的一个简单事实：计算两个素数的乘积很简单，但要把这个乘积重新分解为两个素数却很难。
步骤
RSA算法由三部分构成：密钥生成算法，加密算法，解密算法
1. 密钥生成算法
随机生成两个素数 p,q
计算 n=pq
计算欧拉函数 φ(n)=(p−1)(q−1)φ(n)=(p−1)(q−1)
选取一较小的与φ(n)φ(n)互质的正整数e。那么(n, e)为密钥对中的公钥
计算e在模φ(n)φ(n)下的数论倒数d，d≡e−1modφ(n)d≡e−1modφ(n)，那么(n, d)为密钥对中的私钥
2. 加密算法
计算
C=fe(M)=Memodn
C=fe(M)=Memodn
其中M为明文，(n, e)为公钥，C为密文
3. 解密算法
计算
M=fd(C)=Cdmodn
M=fd(C)=Cdmodn
其中C为密文，(n, d)为私钥，M为明文
根据加密、解密过程中n、e、d三数扮演的角色，我们把n称为公共模数，把e称为公共指数，把d称为私有指数。
数学基础：
同余
两个整数a、b，如果他们除以正整数m的余数相等，那a和b同余。用公式来表示就是：
amodm=bmodm⇔a≡bmodm
数论倒数
普通算术运算中，如果ab=1ab=1，那么我们说a和b互为倒数。类似地，在同余式中，如果ab≡1modmab≡1modm ，我们说在模m下，a和b互为数论倒数，或者说乘法逆元。有时候也记作a≡b−1modma≡b−1modm或者b≡a−1modm
欧拉函数
欧拉函数φ(n)φ(n)，也就是对于正整数n，小于或等于n且与n互质的正整数的个数。比如φ(6)φ(6)，不超过6并且跟6互质的有1和5两个数，则φ(6)=2φ(6)=2。
特别地，对于任意素数p，所有小于p的正整数都跟它互质，所以φ(p)=p−1φ(p)=p−1。
另外，如果p和q均为素数，那么对于整数n=pqn=pq，有φ(n)=φ(p)φ(q)=(p−1)(q−1)φ(n)=φ(p)φ(q)=(p−1)(q−1)
欧拉定理
如果a和m都是整数，并且互质，那么有：
···
aφ(m)≡1modm
···
费马小定理
如果a为整数，p为素数，且a与p互质（也就是p不能整除a），那么：
ap−1≡1modp
中国剩余定理
中国剩余定理常用于一元线性同余方程组的求解，在这里我们介绍它的一个推论。
如果 p, q 互质，n = p * q，则对任意整数 x 和 a
···
{x≡amodpx≡amodq⇔x≡amodn
···
实验过程和结果测试
素数测试
1. 平方根测试：如果n是素数，则 1 模 n 的平方根是 +1 和 -1
如果n是合数，则 1 模n 的平方根除了 +1 和 -1外，还可能有其他值。
-
输入123，可以看到123没有通过平方根测试
image.png
image.png
-
输入13，可以看到13通过平方根测试
image.png
2.费马测试：
如果n是素数，则a^n = a mod n
如果n是合数，则a^n = a mod n 以一定概率成立
比如561是合数，但它可以通过费马测试，有许多这样的数存在，所以要配合其他素数判定规则
注意，不能使用a^(n-1) = 1 mod n 来判断，因为 a 不一定与n 互素
-
输入123，测试次数为123的一半，可以看到123费马测试不通过
image.png
-
输入17，通过费马测试
image.png
3. miller素数测试
-
输入123
-
输入17
image.png
RSA算法的加密与解密
-
输入p，q，可算出n和n的欧拉函数t
image.png
-
输入e，判断e是否与t互素，如果不互素重新输入，如果互素，则计算得出d
image.png
image.png
-
输入1，进行加密
image.png
-
输入2，进行解密
- 输入0，退出
实验分析与反思
- 平方根测试：一开始不知道怎么做，后来仔细想了一下，按老师密码学例子那里的原理一步一步写，因为负数和整数是一样的，所以负数部分没有，因此计算出结果为1的有几个，如果超过一个就判断为合数，否则为素数。
- 费马测试：一开始想着说要随机生成a，那就得随机生成不同的a，在这里卡了一段时间，后来写出来了，就让他随机生成后的a和之前的比较，如果一样就舍弃，否则加入数组。然后这里测试的次数用的是输入的n的一半，一开始想着固定100次，但是如果输入的n太小，就会做很多无用功，所以选择了n的一半。
- miller测试：一开始想自己写，但实在写不出来了，所以后来网上找了代码，并看懂。
- rsa算法：本来自己把需要的函数都写好了，打算输入明文然后程序自动生成p和q，还有e和d，但是写了很久一直有错误，后来因为时间原因只能放弃了，采用手动输入p，q，e的方法，就很简单了，一下子就写好了。
