RSA算法原理及实现(Java)-白红宇

RSA算法原理及实现(Java)

阅读量：3899 次

发布时间：2019-05-23

本文共 6090 字，大约阅读时间需要 20 分钟。

基本介绍

RSA加密算法是一种非对称加密算法。这就意味着通过这个算法，你即将获得一对密钥，分别是公钥和私钥。你可以将公钥公布出去，别人利用你的公钥加密后的内容，只能使用你的私钥来解开，即可保证你和别人通信的安全性，这就是这个加密算法的意义所在。

算法步骤

参考来自:

$(1) 选择 p 、 q 两个超级大的质数，都是 1024 位。$

$(2) 令 n = p * q 。取 φ (n) = (p - 1) * (q - 1) 。计算与 n 互质的整数的个数。$

$3)取 e ∈ \{1 < e < φ(n)\} ，( n , e )作为公钥对$

1<e<φ(n)}，(n,e)作为公钥对

正 式 环 境 中 取 65537, 依 据 来 源 于 H T T P 证 书 。

$\quad mod \quad φ(n) = 1，计算d，( n , d ) 作为私钥对。$

计 算 d 可 以 利 用 扩 展 欧 几 里 的 算 法 进 行 计 算 ， 非 常 简 单 。

$e\quad mod\quad n ，明文 = 密文 ^ d\quad mod \quad n。$

算法难点

如何储存大数，动态语言一般不存在这个问题。不过在Java中就需要借助BigInteger,其他静态语言可能需要借助第三方库才能存储。

如何计算一个超大整数的超大整数次幂，然后取超大整数模，这个文字有点绕，大概就是这个样子: $超大数^{超大数} \quad mod \quad 超大数$ ,这个问题呢就需要使用到了。

如何产生两个随机1024位大质数？这个问题在Java直接利用如下方法即可:

public static BigInteger[] getRandomPQ() {
           BigInteger p = BigInteger.probablePrime(numLength, new Random());        while (!p.isProbablePrime(accuracy)) {
               p = BigInteger.probablePrime(numLength, new Random());        }        BigInteger q = BigInteger.probablePrime(numLength, new Random());        while (!q.isProbablePrime(accuracy)) {
               q = BigInteger.probablePrime(numLength, new Random());        }        return new BigInteger[]{
   p, q};    }

不仅可以产生指定长度的大数，还可以控制其为素数的准确率，即: $1-(2^{-accuracy})$ ,accuracy越大为素数的准确率就越高。

Java代码实现

import java.math.BigInteger;import java.util.Random;public class RSA {
       private final static int numLength = 1024;//素数长度    private final static int accuracy = 100;//素数的准确率为1-(2^(-accuracy))    //获取最大公约数    private BigInteger getGCD(BigInteger a, BigInteger b) {
           if (b.byteValue() == 0) return a;        return getGCD(b, a.mod(b));    }    //扩展欧几里得方法,计算 ax + by = 1中的x与y的整数解（a与b互质）    private static BigInteger[] extGCD(BigInteger a, BigInteger b) {
           if (b.signum() == 0) {
               return new BigInteger[]{
   a, new BigInteger("1"), new BigInteger("0")};        } else {
               BigInteger[] bigIntegers = extGCD(b, a.mod(b));            BigInteger y = bigIntegers[1].subtract(a.divide(b).multiply(bigIntegers[2]));            return new BigInteger[]{
   bigIntegers[0], bigIntegers[2], y};        }    }    //超大整数超大次幂然后对超大的整数取模，利用蒙哥马利乘模算法,    //(base ^ exp) mod n    //依据(a * b) mod n=(a % n)*(b % n) mod n    private static BigInteger expMode(BigInteger base, BigInteger exp, BigInteger mod) {
           BigInteger res = BigInteger.ONE;        //拷贝一份防止修改原引用        BigInteger tempBase = new BigInteger(base.toString());        //从左到右实现简答        /*            D=1            WHILE E>=0        　　  IF E%2=0        　　      C=C*C % N        　　  E=E/2        　　ELSE        　　  D=D*C % N        　　  E=E-1        　　RETURN D        */        for (int i = 0; i < exp.bitLength(); i++) {
               if (exp.testBit(i)) {
   //判断对应二进制位是否为1                res = (res.multiply(tempBase)).mod(mod);            }            tempBase = tempBase.multiply(tempBase).mod(mod);        }        return res;    }    //产生公钥与私钥    public static SecretKey generateKey(BigInteger p, BigInteger q) {
           //令n = p * q。取 φ(n) = (p-1) * (q-1)。        BigInteger n = p.multiply(q);        //计算与n互质的整数个数 欧拉函数        BigInteger fy = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));        //取 e ∈ [1 < e < φ(n) ] ，( n , e )作为公钥对，这里取65537        BigInteger e = new BigInteger("65537");        //计算ed与fy的模反元素d。令 ed mod φ(n)  = 1，计算d，然后将( n , d ) 作为私钥对        BigInteger[] bigIntegers = extGCD(e, fy);        //计算出的x不能是负数，如果是负数，则进行x=x+fy。使x为正数，但是x
   
    << j;                }            }        }        return new String(bytes);    }    //产生两个随机1024位大质数    public static BigInteger[] getRandomPQ() {
           BigInteger p = BigInteger.probablePrime(numLength, new Random());        while (!p.isProbablePrime(accuracy)) {
               p = BigInteger.probablePrime(numLength, new Random());        }        BigInteger q = BigInteger.probablePrime(numLength, new Random());        while (!q.isProbablePrime(accuracy)) {
               q = BigInteger.probablePrime(numLength, new Random());        }        return new BigInteger[]{
   p, q};    }    //密匙对    static class SecretKey {
           BigInteger n, e, d;        public SecretKey(BigInteger n, BigInteger e, BigInteger d) {
               this.n = n;            this.e = e;            this.d = d;        }        public PublicKey getPublicKey() {
               return new PublicKey(n, e);        }        public PrivateKey getPrivateKey() {
               return new PrivateKey(n, d);        }        //密钥        static class PrivateKey {
               public BigInteger n, d;            public PrivateKey(BigInteger n, BigInteger d) {
                   this.n = n;                this.d = d;            }        }        //公钥        static class PublicKey {
               public BigInteger n, e;            public PublicKey(BigInteger n, BigInteger e) {
                   this.n = n;                this.e = e;            }        }    }    public static void main(String[] args) {
           SecretKey secretKey = RSA.generateKey();        //明文内容不要超过1024位,超过后需要分段加密        String text = "Hello world";        String chipper = RSA.encrypt(text, secretKey.getPublicKey());        System.out.println("加密后:\n" +                //密文长度可能会随着随机密钥的改变而改变，最长不超过2048位                "密文二进制长度:" + new BigInteger(chipper).bitLength()                + "\n"                + chipper);        String origin = RSA.decrypt(chipper, secretKey.getPrivateKey());        System.out.println("解密后:\n" + origin);    }}

转载地址：http://cqfen.baihongyu.com/

你可能感兴趣的文章