《信息安全数学基础》大作业
一、 构建 RSA 密码系统
（1） 说明如何随机生成大素数（约为$2^{200}$）
计算机可以很简单的生成随机数，位数并不存在限制，但如果需要生成随机素数的话，可以生成一系列的随机数，再对随机数进行素数测试，从而得到随机素数，下面主要讨论素数测试的一般方法及部分的代码实现。
1. 埃拉斯托特尼筛法
尝试从2到 $ \sqrt{N} $的整数是否整除N，确定性判断N是否为素数
/**
* 埃拉斯托特尼筛法：
* 测试从2到根号N的数能不能被N整除的确定性素数测试
* 建议N小于999999999999999999时使用
*
* @param n
* @author: distiny
* @date: 2021/5/27
* @return: boolean
*/
public static boolean violentIfPrime(BigInteger n) {
//A constant holding the maximum value a long can have, 2^63-1.
if (n.compareTo(new BigInteger(String.valueOf(MAX_VALUE))) >= 0)
System.out.println("正在使用埃拉斯托特尼筛法进行素数测试，待测数值超过0x7fffffffffffffffL,本方法可能会出现不可知错误");
if (n.compareTo(sxjc1.VALUE_1) == 0) {
return false;
} else if (n.compareTo(sxjc1.VALUE_2) == 0 || (n.compareTo(new BigInteger("3")) == 0)) {
return true;
} else {
long n0 = n.longValue();
long p = (long) Math.sqrt(n0);
for (long i = 2; i <= p; i++) {
if (n0 % i == 0) {
System.out.println(n + "可以被" + i + "整除");
return false;
}
}
return true;
}
}
2. Fermat素数检验
给定奇整数n≥3和安全参数t
- 随机选取整数b，(b,n) = 1, 2 ≤ b ≤ n-2
- 计算r = b^n-1^(mod n)
- 如果r ≠ 1，则 n 是合数。
- 上述过程重复t次
/**
* 费马素数测试
*
* @param n
* @param t
* @author: distiny
* @date: 2021/5/27
* @return: boolean
*/
public static boolean fermat(BigInteger n, int t){
if (t < 1) {
System.out.println("安全参数t应是正整数");
}
if ((n == null) || (n.compareTo(sxjc1.VALUE_1) <= 0)) {
return false;
}
if (n.compareTo(sxjc1.VALUE_2)==0 || (n.compareTo(new BigInteger("3")) == 0)) {
return true;
} else {
if ((n.mod(sxjc1.VALUE_2)).compareTo(sxjc1.VALUE_0) == 0) {
return false;
}
}
BigInteger b;
for (int i = 0; i < t; i++) {
do {
b = new BigInteger(n.bitLength(), new Random());
b = b.mod(n);
} while ((b.compareTo(sxjc1.VALUE_2) < 0) || (b.compareTo(n.subtract(sxjc1.VALUE_2)) > 0));
if (sxjc1.greatestCommonDivisor(b, n).compareTo(sxjc1.VALUE_1) > 0) {
return false;
} else {
if ((b.modPow(n.subtract(sxjc1.VALUE_1),n)).compareTo(sxjc1.VALUE_1)==0) {
continue;
} else {
return false;
}
}
}
return true;
}
3. Miller-Rabin素数检验
给定奇整数n≥3和安全参数k。
写n-1 = 2^s^t ，其中t为奇整数。
-
(1) 随机选取整数 b, 2 ≤ b ≤ n - 2.
-
(2) 计算$r_0 \equiv b^t(mod n)$.
-
(3)
- a. 如果r~0~ = 1或r~0~ = n- 1,则通过检验,可能为素数.回到(1). 继续选取另一个随机整数b, 2 ≤ b ≤ n -2;
- b. 否则,有r~0~ ≠ 1以及r~0~ ≠ n -1,计算$r_1 \equiv r_0^2(mod n)$.
-
(4)
- a. 如果r~1~ = n - 1，则通过检验,可能为素数,回到(1)．继续选取另一个随机整数b, 2 ≤ b ≤ n - 2.
- b. 否则,有r~1~ ≠ n -1，计算$r_2 \equiv r_1^2(mod n)$.
-
如此继续下去，
-
(s+2)
a. 如果r~s-1~-1= n - 1,则通过检验,可能为素数,回到(1). 继续选取另一个随机整数b, 2 ≤ b ≤ n -2;
b. 否则,有r~s-1~ ≠ n - 1, n为合数.
# 伪代码[from] https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Input #1: n > 3, an odd integer to be tested for primality Input #2: k, the number of rounds of testing to perform Output: “composite” if n is found to be composite, “probably prime” otherwise write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1) WitnessLoop: repeat k times: pick a random integer a in the range [2, n − 2] x ← ad mod n if x = 1 or x = n − 1 then continue WitnessLoop repeat r − 1 times: x ← x2 mod n if x = n − 1 then continue WitnessLoop return “composite” return “probably prime”/** * BigInteger中自带的MillerRabin算法 * * @param iterations * @param rnd * @return: boolean */ private boolean passesMillerRabin(int iterations, Random rnd) { // Find a and m such that m is odd and this == 1 + 2**a * m BigInteger thisMinusOne = this.subtract(ONE); BigInteger m = thisMinusOne; int a = m.getLowestSetBit(); m = m.shiftRight(a); // Do the tests if (rnd == null) { rnd = ThreadLocalRandom.current(); } for (int i=0; i < iterations; i++) { // Generate a uniform random on (1, this) BigInteger b; do { b = new BigInteger(this.bitLength(), rnd); } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0); int j = 0; BigInteger z = b.modPow(m, this); while (!((j == 0 && z.equals(ONE)) || z.equals(thisMinusOne))) { if (j > 0 && z.equals(ONE) || ++j == a) return false; z = z.modPow(TWO, this); } } return true; }
（2） 说明如何运用中国剩余定理简化计算
RSA算法中，对于$c^d$操作由于$d$值往往较大，故计算难度较高，可以使用中国剩余定理适当降低计算量。
下面几部分会被预计算并存入私钥：
- $p, q$
- $d_P = d (mod\space p - 1)$
- $d_Q = d (mod\space q - 1)$
- $q_{inv} = q^{−1}\space (mod\space p)$
这样最后的私钥就是$(p, q, d, d_P, d_Q, q_{inv} )$
解密步骤如下：
$m_1 = c^{dP} (mod\space p)$
$m_2 = c^{dQ}(mod\space q)$
$h = q_{inv}(m_1 - m_2) (mod\space p)$
- 当m~1~<m~2~时，有些实现会这样计算$ h=q_{inv}(m_1+\frac qpp)-m_2$
$m = m_2 + hq\space (mod\space p*q)$
通过中国剩余定理，即使必须计算两次模幂运算，这也比通过幂平方计算更有效。 原因是这两次模幂运算都使用较小的指数和较小的模量。
/**
* 利用中国剩余定理计算
* 给出同余组方程如：x与b1模m1同余
* x与b2模m2同余
* 其中m1,m2互素
* 可求得x =
* 其中运用了贝祖等式函数
* @param b1
* @param b2
* @param m1
* @param m2
* @author: distiny
* @date: 2021/5/27
* @return: java.math.BigInteger
*/
public static BigInteger CRTfor2(BigInteger b1, BigInteger b2, BigInteger m1, BigInteger m2){
if(greatestCommonDivisor(m1,m2).compareTo(sxjc1.VALUE_1)!=0)
{
System.out.println("请保证m1和m2互素");
return null;
}
m=m1.multiply(m2);
BigInteger M1s = BezoutCalForS(m2,m1);
BigInteger M2s = BezoutCalForS(m1,m2);
x = (M1s.multiply(m2).multiply(b1)).add(M2s.multiply(m1).multiply(b2));
return x;
}
/**
* 返回计算贝祖等式后又s变为正之后的值（中国剩余定理中会用到）
*
* @author: distiny
* @date: 2021/5/27
* @return: java.math.BigInteger
*/
public static BigInteger BezoutCalForS(BigInteger a, BigInteger b) {
BigInteger c = greatestCommonDivisor(a, b);//先对a，b同除以最大公因数
valueOfc = c;
a = a.divide(c);
b = b.divide(c);
if ((a.compareTo(sxjc1.VALUE_0) <= 0) || (b.compareTo(sxjc1.VALUE_0) <= 0)) {
System.out.println("请输入正整数！");
return null;
}
/**
* s, t, q, r : 辅助数组
*/
LinkedList<BigInteger> s = new LinkedList<>();
LinkedList<BigInteger> t = new LinkedList<>();
LinkedList<BigInteger> q = new LinkedList<>();
LinkedList<BigInteger> r = new LinkedList<>();
//给j,s,t,q,r赋初值
r.add(0, a);
r.add(1, b);
s.add(0, sxjc1.VALUE_1);
s.add(1, sxjc1.VALUE_0);
t.add(0, sxjc1.VALUE_0);
t.add(1, sxjc1.VALUE_1);
q.add(null);
q.add(null);//只是为了填充链表，使得其可以在最后add（保持编号的一致性）
q.add(2, r.get(0).divide(r.get(1)));
r.add(2, ((r.get(0)).subtract((q.get(2).multiply(r.get(1))))));
int j = 1;//辅助数组的指针
while (r.get(j + 1).compareTo(sxjc1.VALUE_0) != 0) {
j++;
s.add(j, ((s.get(j - 2)).subtract((q.get(j).multiply(s.get(j - 1))))));
t.add(j, ((t.get(j - 2)).subtract((q.get(j).multiply(t.get(j - 1))))));
q.add(j + 1, r.get(j - 1).divide(r.get(j)));
r.add(j + 1, ((r.get(j - 1)).subtract((q.get(j + 1).multiply(r.get(j))))));
}
BigInteger tmp = s.get(j);
if (tmp.compareTo(BigInteger.ZERO) <= 0) {
tmp = tmp.add(b);
}
return tmp;
}
（3） 加密/解密（对如下文字）
This course combines the theory and engineering practice of information security and cryptography with a rigorous mathematical language on information security and cryptography involved in the mathematical theory gives a detailed reasoning and explanation, including some specific examples for students and engaged in information Security workers to lay a solid theoretical foundation to help keep up with information security and the latest advances in cryptography, and to improve the ability to innovate and make innovative work.
代码：
//具体代码 (包括部分工具类函数的实现即其他部分内容）已上传至https://github.com/distiny-cool/mathOfIS
/**
* 构造函数，生成RSA的对象，得到密钥
*
* @param plainText 输入需要加密的明文，暂时不能加密中文
* @author: distiny
* @date: 2021/5/28
* @return:
*/
public RSA(String plainText) {
p = getBigPrime();
//System.out.println("生成随机密钥p="+p);
do q = getBigPrime();
while (q.compareTo(p) == 0);
//System.out.println("生成随机密钥q="+q);
n = p.multiply(q);
//System.out.println("生成公钥n="+n);
EulerN = (p.subtract(sxjc1.VALUE_1).multiply(q.subtract(sxjc1.VALUE_1)));
//System.out.println("公钥n的欧拉函数值="+EulerN);
do e = getBigPrime(8, 100);//默认确定度100
while (sxjc1.greatestCommonDivisor(e, EulerN).compareTo(sxjc1.VALUE_1) != 0);
//System.out.println("生成公钥e="+e);
d = sxjc1.BezoutCalForS(e, EulerN);
//System.out.println("生成私钥d="+d);
dP = d.mod(p.subtract(sxjc1.VALUE_1));
dQ = d.mod(q.subtract(sxjc1.VALUE_1));
qinv = q.modInverse(p);
PlainText = stringToAscii(plainText);
//System.out.println("明文"+PlainText);
PlainTextList = PlainText.split(",");
}
/**
* 对于对象中的明文进行加密（目前使用时并不应该通过外部对象直接调用,但是暂时先这样吧）
*
* @author: distiny
* @date: 2021/5/29
* @return: java.lang.String
*/
public String RSAEncrypt() {
CipherTextList = new String[PlainTextList.length];
BigInteger x;
for (int i = 0; i < PlainTextList.length; i++) {
x = RSAEncrypt(PlainTextList[i]);
CipherTextList[i] = x.toString();
}
StringBuffer sbu = new StringBuffer();
for (int i = 0; i < PlainTextList.length; i++) {
x = new BigInteger(CipherTextList[i]).mod(BigInteger.valueOf(DEFAULT_MOD_VALUE)).add(BigInteger.valueOf(32));
sbu.append((char) Integer.parseInt(x.toString()));
}
CipherText = sbu.toString();
System.out.println("密文：" + CipherText);
return CipherText;
}
/**
* 对于对象中的密文进行解密（目前使用时并不应该通过外部对象直接调用,但是暂时先这样吧）
*
* @author: distiny
* @date: 2021/5/29
* @return: java.lang.String
*/
public String RSADecrypt() {
BigInteger x;
for (int i = 0; i < CipherTextList.length; i++) {
x = RSADecryptByCRT(CipherTextList[i]);
PlainTextList[i] = x.toString();
}
String plantext2 = "";
for (int i = 0; i < PlainTextList.length; i++)
plantext2 = plantext2 + (char) Integer.parseInt(PlainTextList[i]);
System.out.println("解密后的明文为：" + plantext2);
return plantext2;
}
/**
* 用RSA加密单个数字
*
* @param PlainM
* @author: distiny
* @date: 2021/5/29
* @return: java.math.BigInteger
*/
public static BigInteger RSAEncrypt(String PlainM) {
BigInteger m = new BigInteger(PlainM);
//System.out.println("明文m=" + m);
BigInteger c = m.modPow(e, n);
//System.out.println("密文c=" + c);
return c;
}
/**
* RSA解密单个大数字
*
* @param PlainC
* @author: distiny
* @date: 2021/5/29
* @return: java.math.BigInteger
*/
public static BigInteger RSADecrypt(String PlainC) {
BigInteger c = new BigInteger(String.valueOf(PlainC));
//System.out.println("密文c=" + c);
BigInteger m = c.modPow(d, n);
//System.out.println("明文m=" + m);
return m;
}
/**
* 使用中国剩余定理优化RSA解密单个数字
*
* @param PlainC
* @author: distiny
* @date: 2021/5/29
* @return: java.math.BigInteger
*/
public static BigInteger RSADecryptByCRT(String PlainC) {
BigInteger c = new BigInteger(String.valueOf(PlainC));
//System.out.println("密文c=" + c);
BigInteger m1 = c.modPow(dP, p);
BigInteger m2 = c.modPow(dQ, q);
BigInteger h = qinv.multiply(m1.subtract(m2)).mod(p);
BigInteger m = m2.add(h.multiply(q).mod(p.multiply(q)));
//System.out.println("明文m=" + m);
return m;
}
public void show() {
System.out.println("生成的私钥p：" + p);
System.out.println(" q：" + q);
System.out.println(" d：" + d);
System.out.println(" dQ：" + dQ);
System.out.println(" dP：" + dP);
System.out.println(" qinv：" + qinv);
System.out.println("生成的公钥e：" + e);
System.out.println(" n：" + n);
}
执行效果如下：
请输入你要加密的一段内容（按回车键结束）：
This course combines the theory and engineering practice of information security and cryptography with a rigorous mathematical language on information security and cryptography involved in the mathematical theory gives a detailed reasoning and explanation, including some specific examples for students and engaged in information Security workers to lay a solid theoretical foundation to help keep up with information security and the latest advances in cryptography, and to improve the ability to innovate and make innovative work.
输入的数据为：This course combines the theory and engineering practice of information security and cryptography with a rigorous mathematical language on information security and cryptography involved in the mathematical theory gives a detailed reasoning and explanation, including some specific examples for students and engaged in information Security workers to lay a solid theoretical foundation to help keep up with information security and the latest advances in cryptography, and to improve the ability to innovate and make innovative work.
密文：0v)1JGi/-1VJGih~)vV1JevVJevVi-<JivZJVvt)vVV-)vtJZ-iGe)GVJiaJ)vai-hie)ivJ1VG/-)e<JivZJG-<Zeit-iZv<JI)evJiJ-)ti-i/1JhievVhie)Gi{J{ivt/itVJivJ)vai-hie)ivJ1VG/-)e<JivZJG-<Zeit-iZv<J)v*i{*VZJ)vJevVJhievVhie)Gi{JevVi-<Jt)*V1JiJZVei){VZJ-Vi1iv)vtJivZJV[Z{ivie)iv2J)vG{/Z)vtJ1ihVJ1ZVG)a)GJV[ihZ{V1Jai-J1e/ZVve1JivZJVvtitVZJ)vJ)vai-hie)ivJ9VG/-)e<JIi-2V-1JeiJ{i<JiJ1i{)ZJevVi-Ve)Gi{Jai/vZie)ivJeiJvV{ZJ2VVZJ/ZJI)evJ)vai-hie)ivJ1VG/-)e<JivZJevVJ{ieV1eJiZ*ivGV1J)vJG-<Zeit-iZv<2JivZJeiJ)hZ-i*VJevVJi~){)e<JeiJ)vvi*ieVJivZJhi2VJ)vvi*ie)*VJIi-2/
解密后的明文为：This course combines the theory and engineering practice of information security and cryptography with a rigorous mathematical language on information security and cryptography involved in the mathematical theory gives a detailed reasoning and explanation, including some specific examples for students and engaged in information Security workers to lay a solid theoretical foundation to help keep up with information security and the latest advances in cryptography, and to improve the ability to innovate and make innovative work.
生成的私钥p：11347570364539804153139825862423929775563028823414138992542757961030720411139827999777355083645855382743434720007411589953113536616448517330990382188207719
q：8720914217463155306977252297014625998987315051204190318691615523123753269604256956990896753014492506833035919721859986097808278691883910527545969759849531
d：69396019608533637946796138649174046276316765560369886059942666820550046300157121296161881329096252099202644684286420724047320550372423260532595008911798685251787184620850361312483698908223210748487688439880268436101802888773605259349615012557783408154351574520050034241865938619708065514672550553395945766221
dQ：2279741060996592466139281720796354514258094805916448091608181651273014340187004930665670105559805095147225157437664643668721666214060939266536913256724151
dP：3295974794679611164812397553401141428586771857423193898248933847602283936845593194956078240063111521958673985064393407870198952544196664784934965780807221
qinv：2211122856061831955767878715771858541960204824531657411174927729874322015768314625894891952475917320609613631495235037559039862007479512185077779066312583
生成的公钥e：241
n：98961187725778738137147156298526302678061186390823328641693388779600953599632344570266351481137258910697262537946907659736119838105053288688493474247002878918666306817308200213578582141998341357358862275199989891773096557991070492624940306869740810437822886880888594669739904219742194658085164355100012729789
二、 讨论RSA密码系统的安全性
假设偷听者Eve获得了Alice的公钥N和e以及Bob的加密消息c，但她无法直接获得Alice的密钥d 。要获得d ，最简单的方法是将N分解为p和q，这样她可以得到同余方程$de\equiv 1(mod(p-1)(q-1))$并解出d，然后带入解密公式 解出 ，然后代入解密公式 $ c^{d} = n(mod\space N)$导出n（破密）。但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在。
至今为止也没有人能够证明对N进行因数分解是唯一的从c导出n的方法，直到今天也还没有找到比它更简单的方法。（至少没有公开的方法。） 因此今天一般认为只要N足够大，那么黑客就没有办法了。假如N的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的 N。一个由Shamir 和Tromer在2003年从理论上构建的硬件TWIRL，使人们开始质疑1024位长的N的安全性，目前推荐N的长度至少为2048位。1994年彼得·秀尔（Peter Shor）证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰RSA和相关的派生算法。（即依赖于分解大整数困难性的加密算法） 假如有人能够找到一种有效的分解大整数的算法的话，或者假如量子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。
三、 构建Diffie-Hellman 密钥协商系统
一、概述
Diffie-Hellman密钥协商算法主要解决秘钥配送问题，本身并非用来加密用的；该算法其背后有对应数学理论做支撑，简单来讲就是构造一个复杂的计算难题，使得对该问题的求解在现实的时间内无法快速有效的求解（computationally infeasible ）。
DH密钥协商算法在1976年在Whitfield Diffie和Martin Hellman两人合著的论文New Directions in Cryptography（Section Ⅲ PUBLIC KEY CRYPTOGRAPHY）中被作为一种公开秘钥分发系统(public key distribution system)被提出来。原文的叙述过程比较简单，但基本阐述了算法的原理以及其可行性。
在该论文中实际上提出了一些在当时很有创新性的思想。原论文重点讨论两个话题：
（1）在公网通道上如何进行安全的秘钥分派。
（2）认证（可以细分为消息认证和用户认证）。
为了解决第一个问题，原文提出两种方法：公钥加密系统(public key cryptosystem)和秘钥分发系统(public key distribution system)。对于公钥加密系统，原文只是勾画了一种比较抽象的公钥加密系统的概念模型，重点是加解密采用不同的秘钥，并总结了该系统应该满足的一些特性，相当于是一种思想实验，并没有给出具体的算法实现途径，但这在当时应该来说已经足够吸引人。后来RSA三人组（Ron Rivest、Adi Shamir 和 Leonard Adleman）受此启发，经过许多轮失败的尝试后，于第二年在论文*A Method for Obtaining Digital Signatures and Public-Key Cryptosystems*中提出了切实可行且很具体的公钥加密算法–RSA公钥加密算法。而对于秘钥分发系统，就是本文的DH秘钥协商算法。
为了解决第二个问题，原文通过单向函数（one-way function）来解决，这就是单向认证的问题。另外作者还讨论了这些密码学问题之间的关联性以及如何相互转化。比如一个安全的密码系统（可以防御明文攻击）可以用来生成一个的单向函数、公钥加密系统可以用来作为单向认证、陷门密码系统可以用来生成一个公钥加密系统。数学难题的计算复杂度被当成一种保障密码学安全问题的有效工具被利用起来，这一重要思想贯穿现代密码学的许多加密算法。
二、算法流程及原理
假设Alice需要与Bob协商一个秘钥，需要进行如下步骤
1）首先Alice与Bob共享一个素数pp以及该素数p的本原根g（geneator），当然这里有2⩽g⩽p−1。这两个数是可以不经过加密地由一方发送到另一方，至于谁发送给并不重要，其结果只要保证双方都得知p和g即可。
2）然后Alice产生一个私有的随机数A，满足1⩽A⩽p−1，然后计算$g^Amod \space p=Y_a$，将结果$Y_a$通过公网发送给Bob；与此同时，Bob也产生一个私有的随机数B，满足1⩽B⩽p−1，计算$g^Bmod \space p=Y_b$，将结果$Yb$通过公网发送给Alice。
3）此时Alice知道的信息有p,g,A,Y~a~，其中数字A是Alice私有的，只有她自己知道，别人不可能知道，其他三个信息都是别人有可能知道的；Bob知道的信息p,g,B,Y~b~，其中数字BB是Bob私有的，只有他自己知道，别人不可能知道，其他都是别人有可能知道的。
到目前为止，Alice和Bob之间的秘钥协商结束。
Alice通过计算$K_a=(Y_b)Amodp$得到秘钥$K_a$，同理，Bob通过计算$K_b=(Y_a)^Bmodp$得到秘钥Kb，此时可以证明，必然满足Ka=Kb。因此双方经过协商后得到了相同的秘钥，达成秘钥协商的目的。
三、加解密
1）假设Alice和Bob共享的p和g分别是p=17,g=3，显然这里g=3是p=17的一个本原根，实际上3,5,6,7,10,11,12,14都是17的本原根。
2）然后Alice选定一个私有数字，假设$A=15$，计算$Y_a=3^{15}mod 17=14348907mod17=6$，将6发送给Bob；同时Bob也选定一个私有的数字，假设$B=13$，计$Y_a=3^{13}mod17=1594323mod17=12$，将12发送给Alice。
3）Alice计算秘钥$K_a=12^{15}mod17=2147483647mod17=8$，Bob计算秘钥$Kb=6^{13}mod17=2147483647mod17=8$。双方经过协商后，8最终成为双方的协商的秘钥。
