RSA
公钥加密思想的提出
从单表替换密码到多表替换密码,再到分组密码,密码系统的安全性不断提高,但随之而来的密钥分发问题却越来越突出。20世纪70年代,美国政府每天需要分发数吨计的密钥。虽然几乎所有人认为密钥分发的问题不可能解决,但这个问题还是被奇流般地解决了。这个方法被称为公钥密码,其发展是整个密码学发展历史上最伟大的一革命,也许可以说是唯一一次革命。
公钥密码学与以前的密码学完全不同。首先,公钥算法是基于数学函数而不是基于替换和置换,更重要的是,与只使用一个密钥的对称传统密码不同,公钥密码是非对称的它使用两个独立的密钥。我们将会看到,使用两个独立密钥在消息的保密性、密钥分配和认证领域有着重要意义。
1976年 Whitefield Diffie 和 Martin Hellman 提出了公开密钥(Public Key)密码的解密新思想”。虽然他们没能给出公钥加密的具体方案,但这个思想仍具有划时代的意义。与经典密码学相对应,业界将1976年定为现代密码学元年。也因此获得美国计算机协会 ACM 授予的2015年度“图灵奖”。
公钥密码体制简介
提到公钥密码体制，首先要介绍与之对应的对称密码体制，从而更好的了解公钥密码体制。
对称密码体制
1970年以前,密码学一直使用对称密钥,即消息发送者Alice用特定的密钥加密,接收者 Bob用同一个密钥解密(如密码锁)。对称密钥体制的缺点是:
- 它需要在 Alice和 Bob之间首先在传输密文之前使用一个安全信道交换密钥实际上,这可能很难达到。例如,假定 Alice 和 Bob的居住地相距很远,他们决定用 Emai或手机通信,在这种情况下,Alice和 Bob可能无法获得一个合理的安全信道。
- 如果 Alice 需要和多人进行通信(假如 Alice 是一家银行)时,需要和每个人交換不同的密钥,她必须管理所有这些密钥,为了建立密钥还需要发送成千上万的消息。 由此可见对称密钥体制已经无法满足实际应用的需求。在公钥密码体制中,任何使用者都可以取得其他使用者的加密密钥(即公开密钥),假设Alice欲通过此公开密钥密码系统加密消息给 Bob,她可以先取得 Bob的加密密钥,通过加密函数 $E_{Bob}$.将信息加密成密文传递给 Bob,Bob 在收到 Alice 传来的密文后,便可通过自己的解密密钥(私钥),用解密函数 $D_{Bob}$ 解密。
公钥密码体制
公钥密码体制是由几个部分组成的。首先,包括可能信息的集合M(可能的明文和密文),还包括密钥的集合K。对于每一个密钥k,有一个加密函数E和解密函数D.,通常,E和D,被假定从M映射到M,虽然可能出现一些变化,允许明文和密文来自不同的集合。这些部分必须满足下列要求:
- 对于每一个 $m\in M$ 和每一个 $k\in K,E_k(D_k(m))=m$ 和 $D_k(E_k(m))=m$;
- 对于每一个 m 和每一个 k , $E_k(m)$ 和 $D_k(m)$ 的值很容易计算出来:
- 对于几乎每一个 $k\in K$,如果某人仅仅知道函数 $E_k$,那么找到一个算法计算出 $D_k$,在计算上是不可行的;
- 已知 $k\in K$,很容易找到函数 $E_k$ 和 $D_k$。
要求(1)说明加密和解密互相抵消了;要求(2)是必需的,否则有效地加密和解密是不可能的。由于(4),一个用户能够从K中选择一个秘密的随机数 k 并得到函数$E_k$和$D_k$、要求(3)使该体制成为公钥密码体制。因为很难确定和$D_k$。所以公开 $E_k$ 而不危及系统的安全性是可能的。
公钥加密的第一个实现RSA
1977 年《科学美国人》报道了当时 MIT 的 Ronald Rivest、Adi Shamir 和 Leonar Adleman开创的一种“数百万年才能破解”的公开密钥密码系统(Public KeCryptosystem)。他们三人先申请了专利,命名为 RSA 公钥密码技术,在加州成立了 RSA 数据安全公司,并于 2002年共同获得“图灵奖”。如今 RSA密码系统已经成为使最广、安全性高的公开密钥密码系统。
预备知识
RSA算法需要用到数论中一些基础，比如 同余，模运算，欧拉定理等等。最基础的东西这里不做介绍，读者可以自信搜索相关资料学习。
算术基本定理
任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积 $N=p_1^{a_1}\cdot p_2^{a_2}\cdot … \cdot p_n^{a_n}$，这里 $P_1 < P2 < … < P_n$ 均为质数，指数 $a_i$ 是正整数。
证明： 我们知道，任何非零自然数可根据其是否能表示成两个不同于自身的自然数的乘积分成3类：质数、合数 和 1。下面是用反证法证明上述定理：
- 假设存在大于1的自然数不能写成质数的乘积，设这些数中最小的那个为n。
- 由于 n 大于 1 ，显然，n不能为质数，因为质数 p 可以写成质数乘积：p = p，这与假设不相符合。因此 n 只能是合数。
- 我们知道每个合数都可以分解成两个小于自身而大于1的自然数的积。设其中a和b都是介于1和n之间的自然数，因此，按照n的定义，a和b都可以写成质数的乘积。从而n也可以写成质数的乘积。由此产生矛盾。因此大于1的自然数必可写成质数的乘积。
Euler函数 & Euler定理
在数论中,对于正整数n,欧拉函数(n)是小于或等于m的整数中与 n 互质的所有数的个数。欧拉函数具有两个很重要的性质:
- 任何素数户的欧拉函数值 $φ(p)=p-1$
- 欧拉函数可乘,即 $φ(p\cdot q)=φ(p)\cdot φ(q)$
欧拉定理表述为：若正整数m和n互素,即 gcd(m,n)=1,则 $m^{φ(n)}=1 \pmod n$
因式分解困难问题
由上述算数基本定理可知，任何一个大于一的正整数都可以分解为素数的乘积。这在数字很小的时候很容易实现，但是当整数n非常大的时候，并没有好的办法能够将它分解为几个素数乘积的形式。当n的大小达到 2^2024 时，使用现在最先进的计算机对其进行分解也需要数百年甚至更久的时间，因此分解大整数的问题也被称为大数分解困难问题，这是RSA密码安全性的保证。
RSA的步骤
- Alice 选择秘密的两个互异大素数p和q,并计算 $n = p \cdot q$
- Alice 选择e满足 $gcd(e,(p-1)(q-1))=1$。
- Alice 计算 d 满足 $ed≡1 \pmod {(p-1)(q-1)}$
- Alice 将 $(n,e)$ 作为公钥,$(d,p,q)$ 作为私钥。
- Bob 加密 m 为 $c≡m^e \pmod n$,发送 c 给 Alice.
- Alice 解密 $m=c^d \pmod n$。
RSA解密算法的正确性证明
我们知道：$m ≡ c^d \pmod n = m^{ed} \pmod n ≡ m^{ed} \pmod n ≡ m^{kφ(n)+1} \pmod n$. 由 $ed ≡1 \pmod {φ(n)}$ 可知 $ed = kφ(n) + 1$ ,故只需要证明 $m ≡ m^{kφ(n)+1} \pmod n$
如果 m 和 n 互素，
- 由于 m < n，因此 $m \pmod n = m$ ,
- 由欧拉公式知 $m^{φ(n)} ≡ 1 \pmod n$ ,根据同余式的性可知，$m^{kφ(n)} ≡ 1 \pmod n$
- 综上所述，$c^d ≡ m^{ed} ≡ m^{kφ(n)+1} ≡ m \pmod n$
如果m和n不互素，
- 那么m 和 n 存在大于 1 的公因子，由于 n 只有两个因子 p 和 q，所以 m=ap 或 bq 。
- 不失一般性，我们设m=ap，由于 m < n ，因此 gcd(m,q)=1。因此，根据欧拉定理可得下面等式成立： $m^{φ(q)} ≡ 1 \pmod q$.
- 由同余的性质可得：$m^{kφ(q)} ≡ 1 \pmod q$ , 因此$(m^{kφ(q)} )^{φ(p)} ≡ 1 \pmod q$
- 也就是 $m^{kφ(n)} ≡ 1 \pmod q$, 因此可得 $m^{kφ(n)} = sq + 1$
- 两边同乘以 m 可得：$m^{kφ(n)+1} = sq \cdot ap + m = s\cdot a \cdot n + m$
- 综上所述： $m^{kφ(n)+1} \pmod n ≡ m \pmod n$
故无论m和n是否互素，都可以得到 $m^{kφ(n)+1} \pmod n ≡ m \pmod n$,RSA的正确性得证。
RSA的实现
文章给出了RSA加密算法的一个实现。未做任何优化，仅供学习参考，计算速度跟专业的库相比应该有很大差距。虽然密码学算法是安全的，但是工程实现中可能存在其他攻击，没有足够的信心，不要使用自己写的加密算法做加密。
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
/**
* @author miracle
* @date 2022/8/31 22:56
* @description: <br/>
* RSA公钥加密
*/
public class Main
{
// --------------------------------------------------- 工具函数 -------------------------------------------------------------------
/**
* 产生一个范围在 [start,end]之间的随机大整数
*
* @param start 随机数的最小值
* @param end 随机数的最大值
* @return 返回一个范围在[start,end]之间的随机大整数,如果start<end ， 返回null
*/
public static BigInteger random(BigInteger start,BigInteger end){
if(start.compareTo(end) > 0){
return null;
}
if(start.compareTo(end) == 0){
return end;
}
BigInteger a;
do{
a = new BigInteger((end.subtract(start)).bitLength(),new Random());
}
while(a.compareTo(end.subtract(start)) > 0);
a = a.add(start);
return a;
}
/**
* 返回int型数据的位数
*
* @param number 数据
* @return 数据的位数
*/
public static int bitOfInt(int number){
if(number < 0){
number = -number;
}
int[] sizeTable = {9,99,999,9999,99999,999999,9999999,99999999,999999999,Integer.MAX_VALUE};
int i = 0;
while(number > sizeTable[i++])
;
return i;
}
/**
* 针对大整数的扩展的欧几里得算法
*
* @param a 任意长度的整数
* @param b 任意长度的整数
* @return a 和 b 的最大公约数以及 s 和 t
*/
public static Map<String, BigInteger> gcdExtend(BigInteger a, BigInteger b) {
Map<String, BigInteger> res = new HashMap<>();
BigInteger r, r0 = a, r1 = b;
BigInteger s0 = BigInteger.ONE;
BigInteger t0 = BigInteger.ZERO;
BigInteger s1 = BigInteger.ZERO;
BigInteger t1 = BigInteger.ONE;
BigInteger s = BigInteger.ONE;
BigInteger t = BigInteger.ZERO;
// 如果 a < b; 交换 a,b ; 保证 a >= b
if (a.compareTo(b) == -1) {
r0 = b;
r1 = a;
s0 = BigInteger.ZERO;
t0 = BigInteger.ONE;
s1 = BigInteger.ONE;
t1 = BigInteger.ZERO;
}
// 以下两种特殊情况处理
if (r1 == BigInteger.ZERO) {
res.put("gcd", r0);
res.put("s", BigInteger.ONE);
res.put("t", BigInteger.ZERO);
return res;
}
if (a.mod(b) == BigInteger.ZERO) {
res.put("gcd", r1);
res.put("s", BigInteger.ZERO);
res.put("t", BigInteger.ONE);
return res;
}
// 迭代求解 s和t 使得 as + bt = gcd(a,b)
BigInteger qi = BigInteger.ZERO;
while (r0.mod(r1) != BigInteger.ZERO) {
qi = r0.divide(r1);
s = s0.subtract(s1.multiply(qi));
t = t0.subtract(t1.multiply(qi));
s0 = s1;
t0 = t1;
s1 = s;
t1 = t;
r = r0.mod(r1);
r0 = r1;
r1 = r;
}
// 找到相应的 s和t 后 , 返回结果
BigInteger as = a.multiply(s);
BigInteger bt = b.multiply(t);
res.put("gcd", as.add(bt));
res.put("s", s);
res.put("t", t);
return res;
}
public static BigInteger getMultiplicativeInverse(BigInteger a, BigInteger n) {
Map<String, BigInteger> map = gcdExtend(a, n);
if (map.get("gcd").compareTo(BigInteger.ONE) == 0) {
BigInteger s = map.get("s");
while (s.compareTo(BigInteger.ZERO) == -1) {
s = s.add(n);
}
while (s.compareTo(n) == 1) {
s = s.subtract(n);
}
return s;
} else {
System.out.println("getMultiplicativeInverse()提示您: " + a + "在模" + n + "下没有乘法逆元！");
return new BigInteger("-1");
}
}
/**
* 大整数的大整数幂对一个大整数求幂的结果
*
* @param base 底数
* @param exponent 指数
* @param n 模数
* @return base的exponent次幂模n
*/
public static BigInteger LargeIntegerPowerModulo(BigInteger base, BigInteger exponent, BigInteger n) {
// 保证底数大于模数
if (base.compareTo(n) == -1) {
base = base.mod(n);
}
BigInteger res = solve(base, exponent, n);
return res;
}
/**
* 1、数论中有如下结论
* (a + b) % p = (a % p + b % p) % p
* (a - b) % p = (a % p - b % p) % p
* (a * b) % p = (a % p * b % p) % p
* (a ^ b) % p = ((a % p) ^ b) % p
* (a ^ b) % p = ((a % p) ^ b) % p
* <p>
* 2、分治法求解
* (1) 若 exponent 为奇数： 令 exponent = 2k+1, k 为非负整数 , 则
* a^(2k+1) = (a^k)^2 *a ; a^(2k+1) % n = ((a^k % n)^2 % n * a % n) % n = [ (a^k % n)^2 * a ] % n
* (2) 若power 为偶数: 令 power = 2k, k为非负整数， 则
* a^(2k) = (a^k)^2 ; a^(2k) % n = (a^k % n)^2 % n
* (3) 若 power == 0: 返回 1。
* <p>
* 3、算法分析
* 时间复杂度 T(n) = O( log(n) )
* 空间复杂度 T(n) = O( lon(n) ) (递归函数的空间开销)
*
* @param base 底数
* @param exponent 指数
* @param n 模数
* @return base的exponent次幂模n
*/
public static BigInteger solve(BigInteger base, BigInteger exponent, BigInteger n) {
if (exponent == BigInteger.ZERO) {
return new BigInteger("1");
}
if (exponent.mod(new BigInteger("2")) == BigInteger.ZERO) {
BigInteger two = new BigInteger("2");
base = solve(base, exponent.divide(two), n).pow(2);
return base.mod(n);
} else {
BigInteger two = new BigInteger("2");
base = solve(base, exponent.divide(two), n).pow(2)
.multiply(base);
return base.mod(n);
}
}
// --------------------------------------------------- 加解密函数 -------------------------------------------------------------------
/**
* RSA加密函数
*
* @param m 待加密的明文消息
* @param e 加密使用的公钥
* @param n 加密使用的模数
* @return 返回加密后的消息，即密文
*/
private static BigInteger encryptCore(BigInteger m,BigInteger e,BigInteger n){
return LargeIntegerPowerModulo(m,e,n);
}
/**
* RSA解密函数
*
* @param c 密文
* @param p 私钥：选取的两个大素数之一
* @param q 私钥：选取的两个大素数之一
* @param e 公钥
* @return 将密文恢复后得到的明文
*/
private static BigInteger decryptCore(BigInteger c,BigInteger p,BigInteger q,BigInteger e){
BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
BigInteger d = getMultiplicativeInverse(e,m);
return LargeIntegerPowerModulo(c,d,p.multiply(q));
}
// --------------------------------------------------- RSA签名 -------------------------------------------------------------------
/**
* RSA签名函数
*
* @param name 待签名的消息
* @param p 选取的私钥中两个大素数之一
* @param q 选取的私钥中两个大素数之一
* @param d 私钥，是e在模n = pq 下的逆元
* @return 返回一个长度为2数组，第一个元素是待签名的消息，第二个元素是签名后的消息
*/
private static BigInteger[] sig(BigInteger name,BigInteger p,BigInteger q,BigInteger d){
BigInteger[] res = new BigInteger[2];
res[0] = name;
BigInteger n = p.multiply(q);
res[1] = LargeIntegerPowerModulo(name,d,n);
return res;
}
/**
* RSA签名验证函数
*
* @param sig 经RSA签名算法加密后的消息
* @param n 公开的模数n
* @param e 公钥的指数e
* @return 如果签名验证成功，返回true，否则返回false
*/
private static boolean ver(BigInteger[] sig,BigInteger n,BigInteger e){
BigInteger ver = LargeIntegerPowerModulo(sig[1],e,n);
return ver.compareTo(sig[0]) == 0;
}
// --------------------------------------------------- 加密解密函数 -------------------------------------------------------------------
/**
* 加密字符串（这里假设只发送英文和标点，此时转化为byte数组，最大为122）
* 可以将字符换转化为byte数组。将byte数组的数字划为三位数，不够三位的，首位补 9(这样可以恢复) ，将byte拼接为字符串，转化为BigInteger
* 并将其作为明文的底数，以公钥的指数e和模数n对其加密，将得到的BIgInteger转化为字符串作为密文。
* 注意：
* - 这里的字符串长度不能太长，否则将导致 m > n,导致错误，可将字符串转化的byte数组分成一个个长度较小的子数组分别加密，这里不在实现
*
* @param plaintext 明文字符串
* @param n 公钥：模数
* @param e 公钥：指数
* @return 加密后的字符串
*/
private static String encrypt(String plaintext,String n,String e){
byte[] bytes = plaintext.getBytes();
int[] ints = new int[bytes.length];
int i = 0;
for(i = 0; i < bytes.length; i++){
ints[i] = bytes[i];
}
StringBuilder builder = new StringBuilder();
// 目前只能小于 1024
BigInteger c = BigInteger.ZERO;
i = 0;
while(i < ints.length){
if(bitOfInt(ints[i]) == 2){
ints[i] += 900;
}
builder.append(ints[i++]);
}
// System.out.println("plain = " + builder.toString());
BigInteger m = new BigInteger(builder.toString());
c = encryptCore(m,new BigInteger(e),new BigInteger(n));
return c.toString();
}
/**
* RSA解密
*
* @param ciphertext 密文
* @param p 私钥 p
* @param q 私钥 q
* @param e 指数 e
* @return 解密后的明文字符串
*/
private static String decrypt(String ciphertext,String p,String q,String e){
StringBuilder res = new StringBuilder();
BigInteger cc = new BigInteger(ciphertext);
BigInteger pp = new BigInteger(p);
BigInteger qq = new BigInteger(q);
BigInteger ee = new BigInteger(e);
String plaintext = decryptCore(cc,pp,qq,ee).toString();
// System.out.println("plain = " + plaintext);
for(int i = 0; i < plaintext.length(); i = i + 3){
StringBuilder builder = new StringBuilder();
builder.append(plaintext.charAt(i));
builder.append(plaintext.charAt(i + 1));
builder.append(plaintext.charAt(i + 2));
int integer = new Integer(builder.toString());
if(integer / 100 == 9){
integer -= 900;
}
char temp = (char) integer;
res.append(temp);
}
return res.toString();
}
// --------------------------------------------------- 测试函数 -------------------------------------------------------------------
// 测试RSA的加密核心函数
private void testRSACore(){
System.out.println("---------------------- 测试RSA核心加密函数 ----------------------------");
BigInteger p = new BigInteger("885320963");
BigInteger q = new BigInteger("238855417");
BigInteger m = new BigInteger("30120");
BigInteger e = new BigInteger("9007");
System.out.println("待加密明文为：" + m);
BigInteger ciphertext = encryptCore(m,e,p.multiply(q));
System.out.println("RSA对m加密得： " + ciphertext);
BigInteger plaintext = decryptCore(ciphertext,p,q,e);
System.out.println("RSA对c解密得： " + plaintext);
}
// 测试RSA签名算法
private void testRASSignature(){
System.out.println("---------------------- 测试RSA签名算法 ----------------------------");
System.out.println("对19用私钥(p,q,d)=(7,17,77)进行签名");
BigInteger[] sig = sig(new BigInteger("19"),new BigInteger("7"),new BigInteger("17"),new BigInteger("77"));
System.out.println("签名后的结果为：(" + sig[0] + "," + sig[1] + ")");
System.out.println("对签名后的结果用公钥(n,e)=(119,5)进行验证");
boolean ver = ver(sig,new BigInteger("119"),new BigInteger("5"));
System.out.println("ver(66) == 19 的结果为 " + ver);
}
// 测试RSA加密字符串
private void testRSA(){
System.out.println("---------------------- 测试RSA算法加密字符串 ----------------------------");
BigInteger e = new BigInteger("9007");
BigInteger pp = new BigInteger("12026655772210679470465581609002525329245773732132014742758935511187863487919026457076252932048619706498126046597130520643092209728783224795661331197604583");
BigInteger qq = new BigInteger("8002511426596424351829267099531651390448054153452321185350746845306277585856673898048740413439442356860630765545600353049345324913056448174487017235828857");
String cipher = encrypt("I love cryptography!",pp.multiply(qq)
.toString(),e.toString());
System.out.println("cipher = " + cipher);
String plain = decrypt(cipher,pp.toString(),qq.toString(),e.toString());
System.out.println("plain = " + plain);
}
// --------------------------------------------------- 素性判定(RSA攻击) -------------------------------------------------------------------
/**
* 试除法素性判定
* 时间复杂度 T(n) = O(n^0.5)
*
* @param n 待判定整数
* @return 是素数返回true，否则返回false
*/
private static boolean isPrime(int n){
for(int i = 2; i <= Math.sqrt(n); i++){
if(n % i == 0){
return false;
}
}
return true;
}
/**
* 费马素性判定
* 时间复杂度： T(n) = O(log n)
*
* @param n 待判定数字
* @param k 迭代的轮数，迭代k次后，将合数判定为素数的概率为 1/2^k
* @return 是素数返回true,是合数返回false。注意返回false一定是合数，返回true，有1/2^k 的概率是合数
*/
private static boolean isPrime_Fermat(BigInteger n,int k){
// 特殊情况，n为2或3时，MyTools.random返回为null
if(n.compareTo(new BigInteger("2")) == 0 || n.compareTo(new BigInteger("3")) == 0){
return true;
}
// 费马素性判定法
BigInteger two = new BigInteger("2");
for(int i = 0; i < k; i++){
BigInteger a = random(two,n.subtract(two));
BigInteger temp = LargeIntegerPowerModulo(a,n.subtract(BigInteger.ONE),n);
if(temp.compareTo(BigInteger.ONE) != 0){
return false;
}
}
return true;
}
/**
* Miller-Rabin素性判定
* 算法思路
* 设n是一个奇数，n-1 = 2^t * m,其中m是一个奇数。要测试n是否为素数，
* ① 先随机选择一个介于 [2,n-2]区间内的整数a,如果a^m ≠ 1 且
* ② 对所有的满足 r ∈ [0,k-1] 的整数有，a^(2^r * m) ≠ -1 ， 则有n一定是合数。否则，n有很大可能是素数。
* (目前可以在数学上证明，Miller-Rabin将合数判定为素数的概率小于1/4，而事实上经验告诉我们，概率比1/4小得多)
*
* 时间复杂度： T(n) = O(log n)
*
* @param n 待判定数字
* @param k 迭代的轮数，迭代k次后，将合数判定为素数的概率为 1/4^k
* @return 是素数返回true,是合数返回false。注意返回false一定是合数，返回true，有1/4^k 的概率是合数
*/
private static boolean isPrime_Miller_Rabin(BigInteger n,int k){
// 特殊情况，n为2或3时，MyTools.random返回为null
if(n.compareTo(new BigInteger("2")) == 0 || n.compareTo(new BigInteger("3")) == 0){
return true;
}
// Miller-Rabin素性判定
BigInteger two = new BigInteger("2");
BigInteger m = n.subtract(BigInteger.ONE);
int t = 0;
while(m.mod(two) == BigInteger.ZERO){
m = m.divide(two);
t++;
}
for(int i = 0; i < k; i++){
BigInteger a = random(two,n.subtract(two));
if(LargeIntegerPowerModulo(a,m,n).compareTo(BigInteger.ONE) != 0){
int r;
for(r = 0; r <= t-1; r++){
if(LargeIntegerPowerModulo(a,two.pow(r).multiply(m),n).subtract(n).compareTo(new BigInteger("-1")) == 0){
break;
}
}
if(r == t){
return false;
}
}
}
return true;
}
// --------------------------------------------------- 因式分解(RSA攻击) -------------------------------------------------------------------
/**
* 牛顿下降法判断大整数是不是完全平方数
*
* @param F7 待判断大整数
* @return 如果是完全平方数，返回平方根，否则返回0
*/
public static BigInteger getSquare(BigInteger F7){
// 牛顿法求解平方根, 求解a的平方根
// x为a的平方根，x的初始值为1， 按x = (x+a/x)/2迭代， 误差为error，事实上，当error < 1时即可求出x平方根的整数部分
BigDecimal x = BigDecimal.ONE;
BigDecimal a = new BigDecimal(F7.toString());
BigDecimal eps = new BigDecimal("1");
final BigDecimal error = new BigDecimal("1E-10");
int scale = 100;
// 进入循环
while(eps.compareTo(error) > 0){ // eps > error是执行循环
x = x.add(a.divide(x,scale,BigDecimal.ROUND_HALF_UP))
.divide(new BigDecimal("2.0"),scale,BigDecimal.ROUND_HALF_UP);
eps = x.multiply(x)
.subtract(a)
.abs();
}
BigInteger sqrt = x.toBigInteger(); // 求平方根的整数部分
if(sqrt.pow(2)
.compareTo(F7) == 0){
return sqrt;
}
else{
return BigInteger.ZERO;
}
}
/**
* 费马因式分解算法（将两个素数的乘积分解为这两个素数）
* 时间复杂度：T(n) = O(|p-q|)
*
* @param n 待分解的整数
* @return 如果能分解，返回分解后的结果存储的map，如果无法分解，返回null
*/
private Map<String,BigInteger> Fermat(BigInteger n){
HashMap<String,BigInteger> res = new HashMap<>();
BigInteger i = BigInteger.ONE;
BigInteger two = new BigInteger("2");
while(i.compareTo(n.divide(two)) < 0){
BigInteger temp = n.add(i.pow(2));
BigInteger sqrt = getSquare(temp);
if(sqrt != BigInteger.ZERO){
res.put("p",sqrt.subtract(i));
res.put("q",sqrt.add(i));
return res;
}
i = i.add(BigInteger.ONE);
}
return null;
}
/**
* Pollard p-1因式分解法
* 对于RSA加密中的 n,要将n分解为 n = x*y （这里x,y为两个素数，不使用 n =p*q是为了方便叙述）
* <p>
* 前置知识
* 1、费马小定理：
* - 对于任意素数p和整数 a ∈ Zp,都有 a^p ≡ a(mod p) ( 也可写成 a^(p-1) ≡ 1(mod p) )
* 2、B-Smooth数
* - 如果一个整数的所有素因子的最大值为B，我们称这个整数为B-Smooth数
* - 例：30 = 2 * 3 * 5 , 因此 30 是一个 5-Smooth数。
* - 例：12 = 2 * 2 * 3 , 因此 12 是一个 3-Smooth数。
* -
* - 定理 1：
* - 如果 p-1 是 B-Smooth数,并且 p-1的素因子各不相同，则 (p-1) | B!
* - 证明：
* - 不妨设 p-1 = p1 * p2 * ... * pk , 其中 p1 < p2 < ... < pk
* - 则 B = pk , B! = 1 * 2 ... * pk , 显然 p1,p2,...,pk 都是 B!的因子
* - 所以 p-1 | B!
* - 定理 2：
* - 对于任意的素数p,有 p | ( a^t - 1 ) , 其中 t是 p-1的非零倍数 , 即 t = k*(p-1) , k 为非零整数
* - 证明：
* - 由费马小定理知：对于任意素数p和整数 a ∈ Zp,都有 a^(p-1) ≡ 1(mod p)
* - 由同余的性质可知： a^(k*(p-1))≡ 1(mod p) ,
* - 即 a^(k*(p-1)) - 1 ≡ 0 (mod p)
* - 即 p | a^(k*(p-1)) - 1
* - 即 p | a^t - 1
* -
* -
* 3、Pollard p-1 算法的思路
* - ① 由定理 2可知，只需要找到合适的t即相当于素数p 是 a^t-1 的一个因子。即 p | a^t-1 ,如果p恰好又是n的一个因子，即 p | n 。则 p是n的一个非平凡因子，
* - 即 p = x 或 p = y（因为n只有x,y两个非平凡因子）。不失一般性，设p = x。
* - 那么如何求出p呢？
* - ② 注意到 p | a^t-1 且 p | n ，说明 p是 a^t-1和 n 的公约数，而y同时又是 a^t - 1的因子的概率非常小，除非 y-1 也仅仅含有小的素数因子。
* - 因此有很大概率 gcd(a^t-1,n) = p 是n的一个非平凡因子。
* - ③ 还有一种可能是 gcd(a^t-1,n) = n ,这时 a^t ≡ 1(mod n),可用指数分解法分解。
* - 那么t应该如何选取呢？
* - ④ 由定理 1 可知：对于某个合适的B,B!是p-1的倍数，即可选择 t = B! ,由于不知道 B是多少，可以采用循环尝试不同的B。
* - 小技巧：
* - a^(B!)的计算可以使用如下巧妙的方法:
* - 令 b1 = a (mod n) , bj = b(j-1)^j(mod n) ; 则 bB = a^(B!)(mod n)
* <p>
* 4、算法的过程
* - ①选取一个大于1的整数a,为了简单不妨选择 a = 2
* - ②选取B = 2，求 d = gcd( a^(B!)-1,n),如果 1 < d < n ,则d是其中一个因子，执行完毕，返回d
* - ③如果 第②步的 d = 1,则将 B++后重复第②步。
* - (由于当n = x*y中，x-1和y-1都含有大素数因子时，算法效率很低，因此可设置一个B的最大值maxB，当 B > maxB时，结束循环，返回-1，)
* - ④如果 第②步的 d = n,则使用指数分解法分解n（代码实现中，默认没有这种情况）
* 5、时间复杂度和空间复杂度：
* - T(n) = O(maxB * log n) ， S(n) = O(1)
* 6、参考文献
* - https://blog.soreatu.com/posts/intended-solution-to-crypto-problems-in-nctf-2019/#childrsa213pt-38solvers
*
* @param n 待分解的合数
* @param maxB 最大循环的轮数，当达到该循环轮数后，如果还未分解成功，直接结束。显然，该值越大对于分解n越有帮助
* @return 返回分解后的结果 n = p*q ,p和q被封装在一个map中，key 分别为 "p" 和 "q"
*/
private Map<String,BigInteger> Pollard_p_1(BigInteger n,BigInteger maxB){
HashMap<String,BigInteger> map = new HashMap<>();
BigInteger B = new BigInteger("2");
BigInteger j = BigInteger.ONE;
BigInteger b = new BigInteger("2");//这里相当于给a赋值为2
while(B.compareTo(maxB) < 0){
b = LargeIntegerPowerModulo(b,j,n);
BigInteger d = gcdExtend(b.subtract(BigInteger.ONE),n)
.get("gcd");
if(d.compareTo(BigInteger.ONE) > 0 && d.compareTo(n) < 0){
map.put("p",d);
map.put("q",n.divide(d));
return map;
}
else if(d.compareTo(BigInteger.ONE) == 0){
B = B.add(BigInteger.ONE);
j = j.add(BigInteger.ONE);
}
else{
// 使用指数分解法，这里返回空map，表示分解失败
map.put("p",BigInteger.ZERO);
map.put("q",BigInteger.ZERO);
return map;
}
}
return map;
}
public static void main(String[] args){
Main rsa = new Main();
rsa.testRSACore();
rsa.testRSA();
rsa.testRASSignature();
// BigInteger p = new BigInteger("10337");
// BigInteger q = new BigInteger("100493");
// Map<String,BigInteger> fermat = rsa.Fermat(p.multiply(q));
// System.out.println(fermat);
// BigInteger pp = new BigInteger("21");
// BigInteger qq = new BigInteger("11");
// Map<String,BigInteger> pollard_p_1 = rsa.Pollard_p_1(p.multiply(q),new BigInteger("100"));
// System.out.println(pollard_p_1);
// for(int i = 2; i < 30; i++){
// System.out.print(i + " : " + isPrime_Fermat(new BigInteger("" + i),10) + ",");
// System.out.println(isPrime(i));
// }
// System.out.println("------------------------------------------------");
// for(int i = 2000; i < 2030; i++){
// System.out.print(i + " : " + isPrime_Miller_Rabin(new BigInteger("" + i),10) + ",");
// System.out.println(isPrime(i));
//
// }
}
}