c语⾔字符串⾮对称加密,RSA算法C语⾔实现（⽀持任意位密
钥）
之前分享过三种常⽤MD5、SHA2和AES加密算法(点这⾥)实现源码，前三者分别属于哈希加密和对称加密，⽽另⼀种很常⽤的⾮对称加密RSA算法实现这次分享出来。RSA算法的原理和⽤途⼤家可以⽹上⾃⾏搜索。虽然其算法原理很简单，但是由于其密钥长度很长(⼀般⾄少1024位)，所以实际在其相互运算以及⼤质数查会牵扯很多算法理论，因此我这⾥代码实现中数学运算是直接基于GMP(The
GNU Multiple Precision Arithmetic 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 ieve(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);
ieve(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) {java源代码加密
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密钥):
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论