Java RSA 算法基本实现

xiaoxiao2021-02-28  31

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。

关于RSA算法的历史和原理,推荐去看下面阮一峰的这两篇文章:

http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

RSA基本过程:

    (1)选取两个大素数p、q:这里我是用Java BigInteger自带的probablePrime()素数生成函数得到的

    (2)根据选取的p、q计算出n和φ(n)

    (3)从1—φ(n)之间选取一个随机整数e(e要与φ(n)互质),

    (4)计算e对于φ(n)的模反元素d(关于模反元素可以去看上面那两篇文章)

  这样,我们就得到了公钥(n,e)和私钥(n,d),把公钥公开,这样别人把要发给你的消息用你的公钥加密,加密后的消息只能用你的私钥才能解密得到明文信息,只要你的密匙长度足够长,理论上是不可能被别人破解的

下面贴上简单实现RSA加密解密的代码:

package com.eridani.rsa; import java.io.UnsupportedEncodingException; import java.math.BigInteger; import java.net.URLDecoder; import java.net.URLEncoder; import java.security.SecureRandom; import java.util.Random; public class a { public static void main(String[] args) throws UnsupportedEncodingException { // 随机生成两个2048位比特大质数 Random random = new SecureRandom(); BigInteger p = BigInteger.probablePrime(2048, random); BigInteger q = BigInteger.probablePrime(2048, random); BigInteger[][] key = getKey(p, q); // 获取公钥和私钥 String string = "陈独秀同学,请你坐下!"; string = URLEncoder.encode(string ,"utf-8"); byte[] bs = string.getBytes(); BigInteger m = new BigInteger(bs); // 要加密的数据 BigInteger c = exmode(m, key[0][1], key[0][0]); // 加密 BigInteger d = exmode(c, key[1][1], key[1][0]); // 解密 byte[] b = d.toByteArray(); String string2 = new String(b); string2 = URLDecoder.decode(string2, "utf-8"); String mm = m.toString(), cc = c.toString(), dd = d.toString(), pp = p.toString(), qq = q.toString(); System.out.println("加密前为:" + URLDecoder.decode(string, "utf-8")); System.out.println("加密前mm=:" + mm); System.out.println("加密后为:" + cc); System.out.println("解密后d=:" + dd); System.out.println("解密后为:" + string2); } public static BigInteger[][] getKey(BigInteger p, BigInteger q) { // 生成公钥和私钥的方法 BigInteger n = p.multiply(q); BigInteger x, y; BigInteger fn = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE)); BigInteger e = new BigInteger("65537"); // 一般选取e=65537 BigInteger a = e; BigInteger b = fn; BigInteger result[] = gcd(a, b); while ((result[0].compareTo(BigInteger.ZERO)) == -1) { result[0] = result[0].add(fn); // 求出的d必须要大于0 } BigInteger d = result[0]; BigInteger[][] key = new BigInteger[2][2]; key[0][0] = n; key[0][1] = e; // 获得公钥 key[1][0] = n; key[1][1] = d; // 获得私钥 return key; } private static BigInteger[] gcd(BigInteger a, BigInteger b) { // 拓展欧几里得算法求出d if (b.equals(BigInteger.ZERO)) { BigInteger[] result = new BigInteger[3]; result[0] = BigInteger.ONE; result[1] = BigInteger.ZERO; result[2] = a; return result; } else { BigInteger[] result = new BigInteger[3]; result = gcd(b, a.mod(b)); BigInteger x = result[0]; result[0] = result[1]; result[1] = x.subtract((a.divide(b)).multiply(result[1])); return result; } } public static BigInteger exmode(BigInteger m, BigInteger ex, BigInteger n) { // 加密解密求法 return m.modPow(ex, n); } }
转载请注明原文地址: https://www.6miu.com/read-1950030.html

最新回复(0)