之前分享过三种常用MD5、SHA2和AES加密算法(点这里)实现源码，前三者分别属于哈希加密和对称加密，而另一种很常用的非对称加密RSA算法实现这次分享出来。RSA算法的原理和用途大家可以网上自行搜索。虽然其算法原理很简单，但是由于其密钥长度很长(一般至少1024位)，所以实际在其相互运算以及大质数查找会牵扯很多算法理论，因此我这里代码实现中数学运算是直接基于GMP(The GNUMultiple PrecisionArithmetic Library)，我将其linux64位下编译好的动静态库都已上传，如果环境相同可以不用安装直接使用。另外针对RSA算法内的大质数p和q以及公钥e和私钥d等也是有要求的(参考这里)，这块我是参考JDK内RSA算法的实现。
下面开始准备工作，首先是大质数的选取，由于大质数判断是相当困难，所以当前对于大质数的选取都是概率选取，先看下JDK内实现(我查看的代码版本是jdk-10.0.1)
BigInteger.java内762-769行，其中SMALL_PRIME_THRESHOLD为常量95 ，DEFAULT_PRIME_CERTAINTY为常量100，rnd入参是一个随机数，所以是按95位为分界对应两个不同方法，我这里只考虑长密钥所以直接看大的
public static BigInteger probablePrime(intbitLength, Random rnd) {if (bitLength < 2)throw new ArithmeticException("bitLength < 2");return (bitLength < SMALL_PRIME_THRESHOLD ?smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
}
BigInteger.java内822-841行，certainty就是之前传入的常量100，而其结果是调用BitSieve类中的retrieve方法获取，为了简单些我这就跳过这个函数代码了，里面大体是循环调用BigInteger类内primeToCertainty方法。
private static BigInteger largePrime(int bitLength, intcertainty, Random rnd) {
BigInteger p;
p= new BigInteger(bitLength, rnd).setBit(bitLength-1);
p.mag[p.mag.length-1] &= 0xfffffffe;//Use a sieve length likely to contain the next prime number
int searchLen =getPrimeSearchLen(bitLength);
BitSieve searchSieve= newBitSieve(p, searchLen);
BigInteger candidate=searchSieve.retrieve(p, certainty, rnd);while ((candidate == null) || (candidate.bitLength() !=bitLength)) {
p= p.add(BigInteger.valueOf(2*searchLen));if (p.bitLength() !=bitLength)
p= new BigInteger(bitLength, rnd).setBit(bitLength-1);
p.mag[p.mag.length-1] &= 0xfffffffe;
searchSieve= newBitSieve(p, searchLen);
candidate=searchSieve.retrieve(p, certainty, rnd);
}returncandidate;
}
BigInteger.java内934-962行，可以看到最后调用MillerRabin和LucasLehmer算法，前者中rounds为迭代轮数，而这个算法检测一轮为质数实际为不为质数的概率为1/4(参考这里)，后者也是一个伪素数检测算法，感兴趣可以参考这里，所以可以看出JDK中RSA算法获取的是概率质数，其概率跟其位数相关。
boolean primeToCertainty(intcertainty, Random random) {int rounds = 0;int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;//The relationship between the certainty and the number of rounds//we perform is given in the draft standard ANSI X9.80, "PRIME//NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
int sizeInBits = this.bitLength();if (sizeInBits < 100) {
rounds= 50;
rounds= n < rounds ?n : rounds;returnpassesMillerRabin(rounds, random);
}if (sizeInBits < 256) {
rounds= 27;
}else if (sizeInBits < 512) {
rounds= 15;
}else if (sizeInBits < 768) {
rounds= 8;
}else if (sizeInBits < 1024) {
rounds= 4;
}else{
rounds= 2;
}
rounds= n < rounds ?n : rounds;return passesMillerRabin(rounds, random) &&passesLucasLehmer();
}
通过查询GMP库中对应函数，其文档有两个相关函数int mpz_probab_prime_p (const mpz t n, int reps)和void mpz_nextprime (mpz t rop, const mpz t op)前者是概率判断n(入参)是否为质数，其概率值为4的reps(入参)次方，后者是直接给出一个大于op(入参)的概率质数rop(出参)。所以前者就是对应JDK中的primeToCertainty方法，后者对应probablePrime方法，为了简单我这里使用mpz_nextprime函数直接获取，这个函数没有给出是质数的概率，文档也没有说明只是说结果是合数的概率很小(原文：“This function uses a probabilistic algorithm to identify primes. For practical purposes it’s adequate, the chance of a composite passing will be extremely small.”)。我查了下源码，这个概率可能是4的-25次方(最后调用了25轮MillerRabin算法)
有了获取大质数的获取方法剩下的难点就是查询GMP文档学习英语了..JDK内的RSA加密解密是基于CRT的，我不太清楚这块原理所以将这部分去掉了，代码封装了字符串加解密(每次加密数据大小不可超过密钥大小)，下面展示下在我机子上的运行结果(2048bit密钥):
