几个简单密码学算法的实现
文章给出了密码学初学时可能会遇到的算法实现，包括求最大公约数（最小公倍数lcm(a,b)=ab/gcd(a,b)）、乘法逆元，快速模幂运算、Miller-Rabin素数判定等等。声明一下，只是实现了功能，保证了实践复杂度是我已知的最好的，但是并未做任何优化，仅供学习参考，计算速度跟专业的库相比应该有很大差距。
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/29 18:01
* @description: <br/>
* 我的工具类
*/
public class Main {
/**
* 将一个十进制的数字转化为指定进制，指定位数的数字符串（位数不够，前面补零）
* 如：
* - 将 33 转化为长度为 8 的二进制字符串
* - 则结果为： "00100001"
*
* @param number 带转换的十进制数字
* @param radix 将要转化为的进制数
* @param length 转化后字符串的长度
* @return 满足要求的字符串
*/
public static String toString(int number, int radix, int length) {
StringBuilder str = new StringBuilder();
for (int i = 0; i < length; i++) {
int bit = number % radix;
str.insert(0, bit);
number = number / radix;
}
return str.toString();
}
// 反转指定位置的字符串
public static String reverseStr(String str, int start, int end) {
char[] chars = str.toCharArray();
while (start < end) {
char temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;
start++;
end--;
}
return new String(chars);
}
// 反转指定位置的对象数组
public static <T> T[] reverseArray(T[] arr, int start, int end) {
while (start < end) {
T temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
return arr;
}
// 反转指定位置的字符串
public static int[] reverseInt(int[] arr, int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
return arr;
}
/**
* 大整数的大整数幂对一个大整数求幂的结果(Big Integer Power Modulus)
*
* @param base 底数
* @param exponent 指数
* @param n 模数
* @return base的exponent次幂模n
*/
public static BigInteger BigIntegerPM(BigInteger base, BigInteger exponent, BigInteger n) {
// 保证底数大于模数
if (base.compareTo(n) == -1) {
base = base.mod(n);
}
BigInteger res = solvePM(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) ) (这里的n指的是 exponent)
* 空间复杂度 T(n) = O( lon(n) ) (递归函数的空间开销)
*
* @param base 底数
* @param exponent 指数
* @param n 模数
* @return base的exponent次幂模n
*/
public static BigInteger solvePM(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 = solvePM(base, exponent.divide(two), n).pow(2);
return base.mod(n);
} else {
BigInteger two = new BigInteger("2");
base = solvePM(base, exponent.divide(two), n).pow(2)
.multiply(base);
return base.mod(n);
}
}
/**
* 欧几里得算法(辗转相除法)求两个数的最大公约数。（递归法）
* 注意，第一参数a 必须大于等于第二个参数b
*
* @param a：较大的参数
* @param b：较小的参数
*/
public static int gcdByRecursive(int a, int b) {
return b == 0 ? a : gcdByRecursive(b, a % b);
}
/**
* 欧几里得算法(辗转相除法)求两个数的最大公约数。（非递归法）
*
* @param a：参数
* @param b：参数
*/
public static int gcd(int a, int b) {
int r;
if (a < b) {
r = a;
a = b;
b = r;
}
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
/**
* 扩展的欧几里得算法求最大公约数
* 设 s0 = 1 ,s1 = 0 ; t0 = 0 , t1 = 1 ;
* 则:
* s(i+1) = s(i-1) - si * qi ; (i = 1,2,...,n)
* t(i+1) = t(i-1) - ti * qi ; (i = 1,2,...,n)
* 当 n>1 时，按照上述地推公式迭代求得 sn 和 tn
* sn 和 tn 满足 a * sn + b * tn = gcd(a,b)
* (这里 这里的 n 是用辗转相除法使得 a|b 是的辗转相除的次数。)
* 例如 a = 10,b = 0时,辗转相除0次,n = 0;
* * a = 20,b = 10时,辗转相除1次,n = 1;
* * a = 15,b = 10时，辗转相除2次,n = 2;
* 当 n = 0 时, s0 = 1,t0 = 0;
* 当 n = 1 时, s1 = 0,t1 = 1;
* 当 n > 1 时, sn,tn 由上述递推公式求得。
*
* @param a 第一个参数
* @param b 第二个参数
* @return 返回一个含有三个元素的Map，分别为 gcd(a,b)、s和t 其中s和t满足 as + bt = gcd(a,b)
*/
public static Map<String, Integer> gcdExtend(int a, int b) {
Map<String, Integer> res = new HashMap<>();
int r, r0 = a, r1 = b;
// 迭代求解 s和t 使得 as + bt = gcd(a,b) 时用到的变量
int s0 = 1, t0 = 0;
int s1 = 0, t1 = 1;
int s = 1, t = 0;
// 这么赋值是为了保证 s，t满足 as + bt = gcd(a,b)
if (a < b) {
r0 = b;
r1 = a;
s0 = 0;
t0 = 1;
s1 = 1;
t1 = 0;
}
// 以下两种特殊情况处理
if (r1 == 0) {
res.put("gcd", r0);
res.put("s", 1);
res.put("t", 0);
return res;
}
if (r0 % r1 == 0) {
res.put("gcd", r1);
res.put("s", 0);
res.put("t", 1);
return res;
}
// 迭代求解 s和t 使得 as + bt = gcd(a,b)
int qi = 0;
while (r0 % r1 != 0) {
qi = r0 / r1;
s = s0 - s1 * qi;
t = t0 - t1 * qi;
s0 = s1;
t0 = t1;
s1 = s;
t1 = t;
r = r0 % r1;
r0 = r1;
r1 = r;
}
// 找到相应的 s和t 后 , 返回结果
res.put("gcd", a * s + b * t);
res.put("s", s);
res.put("t", t);
return res;
}
/**
* 针对大整数的扩展的欧几里得算法
* 时间复杂度T(n) = O(log n)
*
* @param a 任意长度的整数
* @param b 任意长度的整数
* @return a 和 b 的最大公约数以及 s 和 t组成的map,其中 key = "gcd" 的 value 是 gcd(a,b)
*/
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;
}
/**
* 求 a 在 模n 下的乘法逆元（扩展的欧几里得算法）
*
* @param a 求a的乘法逆元
* @param n 模数
* @return 存在乘法逆元时，返回 a 在 模n 下的乘法逆元。否则返回 -1
*/
public static int getMultiplicativeInverse(int a, int n) {
Map<String, Integer> map = gcdExtend(a, n);
if (map.get("gcd") == 1) {
Integer s = map.get("s");
while (s < 0) {
s = s + n;
}
while (s >= n) {
s = s - n;
}
return s;
} else {
System.out.println("getMultiplicativeInverse()提示您: " + a + "在模" + n + "下没有乘法逆元！");
return -1;
}
}
/**
* 求 a 在 模n 下的乘法逆元（扩展的欧几里得算法）
* 这里 a 和 n 都是 BigInteger 类型的
*
* @param a 求a的乘法逆元
* @param n 模数
* @return 存在乘法逆元时，返回 a 在 模n 下的乘法逆元。否则返回 -1
*/
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");
}
}
/**
* 返回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;
}
/**
* 牛顿下降法判断大整数是不是完全平方数(具体方法可参考 https://www.jianshu.com/p/91a69f585352)
*
* @param F7 带判断大整数
* @return 如果是完全平方数，返回平方根，否则返回0
*/
public static boolean isSquare(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 true;
} else {
return false;
}
}
/**
* 牛顿下降法对大整数开根号
* 由于开根号结果不一定是整数，这里的结果使用的直接抹掉小数部分，效果即为 floor(根号F7)
*
* @param F7 待开放的整数
* @return 对F7开放后，结果的整数部分
*/
public static BigInteger sqrt(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(); // 求平方根的整数部分
return sqrt;
}
/**
* 产生一个范围在 [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;
}
/**
* 产生一个范围在 [start,end]之间的随机数
*
* @param start 随机数的最小值
* @param end 随机数的最大值
* @return 返回一个范围在[start, end]之间的随机大整数, 如果start<end ， 返回-1
*/
public static double random(double start, double end) {
if (start > end) {
return -1;
}
if (start == end) {
return end;
}
double res;
Random random = new Random();
return start + random.nextDouble() * (end - start);
}
/**
* 产生一个范围在 [start,end]之间的随机数
*
* @param start 随机数的最小值
* @param end 随机数的最大值
* @return 返回一个范围在[start, end]之间的随机整数, 如果start<end ， 返回-1
*/
public static int random(int start, int end) {
if (start > end) {
int temp = start;
start = end;
end = temp;
}
Random random = new Random();
return start + random.nextInt(end - start + 1);
}
/**
* 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小得多)
* <p>
* 时间复杂度： T(n) = O(log n)
*
* @param n 待判定数字
* @param k 迭代的轮数，迭代k次后，将合数判定为素数的概率为 1/4^k
* @return 是素数返回true, 是合数返回false。注意返回false一定是合数，返回true，有1/4^k 的概率是合数
*/
public static boolean isPrime_Miller_Rabin(BigInteger n, int k) {
if (n.compareTo(BigInteger.ONE) <= 0) {
return false;
}
// 特殊情况，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 (BigIntegerPM(a, m, n)
.compareTo(BigInteger.ONE) != 0) {
int r;
for (r = 0; r <= t - 1; r++) {
if (BigIntegerPM(a, two.pow(r)
.multiply(m), n)
.subtract(n)
.compareTo(new BigInteger("-1")) == 0) {
break;
}
}
if (r == t) {
return false;
}
}
}
return true;
}
// 获得Miller-Rabin素数检测的检测次数
private static int getTryTime(BigInteger n) {
//copy自jdk源码, n的bit数越多, 需要的Miller-Rabin检测次数就越少
int sizeInBits = n.bitLength();
int tryTime = 0;
if (sizeInBits < 100) {
tryTime = 50;
} else if (sizeInBits < 256) {
tryTime = 27;
} else if (sizeInBits < 512) {
tryTime = 15;
} else if (sizeInBits < 768) {
tryTime = 8;
} else if (sizeInBits < 1024) {
tryTime = 4;
} else {
tryTime = 2;
}
return tryTime;
}
/**
* 判断一个数是否是素数
* 当 num 较小时，使用查询素数表和查看num是不是小素数的倍数的方法对num进行素性判定
* 当 使用上述方法无法判断 num 的素性时，采用 Miller-Rabin进行k轮素性判定，其中k的值根据num的大小不同而动态求出。
*
* @param num 待判断的数
* @return 素数返回true，合数返回false
*/
public static boolean isPrime(BigInteger num) {
// # 创建小素数的列表,可以大幅加快速度
int[] small_primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
if (num.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) < 0) {
long n = num.longValue();
// # 如果是小素数,那么直接返回true
for (int i = 0; i < small_primes.length; i++) {
if (n == small_primes[i]) {
return true;
}
}
// #如果大数是这些小素数的倍数,那么就是合数,返回false
for (int i = 0; i < small_primes.length; i++) {
if (n % small_primes[i] == 0) {
return false;
}
}
}
// #如果这样没有分辨出来,就一定是大整数,那么就调用rabin算法
return isPrime_Miller_Rabin(num, getTryTime(num));
}
public static void main(String[] args) {
// System.out.println(toString(33,33,8));
// Integer[] arr = new Integer[5];
// for(int i = 0; i < 5; i++){
// arr[i] = i;
// }
// Integer[] res = reverseArray(arr,0,arr.length - 1);
// for(Integer re : res){
// System.out.println(re);
// }
// Integer a = 5;
// System.out.println(a);
// System.out.println(bitOfInt(1000));
// System.out.println(MyTools.getMultiplicativeInverse(7467,11200));
// System.out.println(MyTools.BigIntegerPM(new BigInteger("5859"),new BigInteger("3"),new BigInteger("11413")));
// for(int i = 0; i < 100; i++){
// System.out.print(random(BigInteger.TEN,BigInteger.TEN.pow(2)) + ",");
// }
// for(int i = 2; i < 300; i++){
// System.out.println(isPrime_Miller_Rabin(BigInteger.valueOf(i),10));
// }
System.out.println(99 % 13);
Random random = new Random();
int bitLength = 180;
BigInteger randomInteger = new BigInteger(bitLength, random);
BigInteger bigInteger = new BigInteger(randomInteger.toString());
boolean isPrime = bigInteger.isProbablePrime(100);
while (!isPrime) {
bigInteger = bigInteger.add(BigInteger.ONE);
isPrime = bigInteger.isProbablePrime(100);
}
System.out.println("生成的大素数：" + bigInteger);
}
}