安全算法

RSA 算法原理&JAVA 实现

Posted by Charlie on 2019-05-21

数学原理简述

RSA算法基于大整数因式分解的难题。

给定两个素数p、q 很容易相乘得到n，而对n进行因式分解却相对困难。

加密算法具体过程：

  1. 随机选择两个质数p、q

  2. 计算p、q的乘积n，将n转为二进制，n的位数即为密钥的位数，假如n为1024位，则密钥为1024位

    其实不是完全标准的1024位，计算机也是随机选择一个近似1024位的大整数

    （从实验来看，每次产生的确实都是1024位，所以此处说法需论证）

  3. 计算n的欧拉函数φ(n)

    欧拉函数 φ(n) ：求小于等于n的数中，有多少个数与n互质

  4. 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质：实际应用中常常选择：65537，hex为：0x10001

  5. 计算e对于φ(n)的模反元素d

    指有一个整数d，可以使得e*d被φ(n)除的余数为1

  6. 将n和e封装成公钥（n,e），n和d封装成私钥（n,d）

  7. 加密时，即计算出下式中的c，其中m即为需要加密的内容

    1. c = m^e % n :m的e次方除以n的余数为c

      若使用私钥加密，则公式为 c = m^d % n

    2. 如果m>n，由于c = m^e % n，c为密文，m为明文，e和n组成公钥，显然当m>n时，m与m-n得出的密文一样，无法解密，运算就会出错。

      这里怎么理解，没有搞懂

  8. 解密时，通过下面等式，反解出c即可解密

    1. m = c^d % n : 明文m等于c的d次方除以n的余数

      若使用公钥解密，则公式为：m = c^e % n

由上述过程可知：

  1. 公钥的组成：（n，e）

  2. 私钥的组成：（n，d）

    n 我们称为模数，e、d称为指数

  3. RSA算法支持的加密长度与密钥长度相关，假如1024位，加密长度为1024位，即128字节

加签算法具体过程:

以 Sha1WithRsa 为例

加签

  1. 对原文内容 s 做 sha1 摘要，得到message
  2. 对 message 使用 RSA privateKey 加密，得到密文 encrypted

验签

  1. 对原文内容 s 做 sha1 摘要，得到 message
  2. 对 encrypted 使用 RSA publicKey 解密，得到明文 message1
  3. 将 message 与 message1 比对，相同即验签成功

问题

JAVA具体实现

生成密钥对

1
2
3
4
5
6
7
8
9
/**
 * 生成发送方密钥对
*/
public static KeyPair initKey() throws NoSuchAlgorithmException{
  KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");//密钥对生成器
  keyPairGenerator.initialize(KEY_SIZE);//指定密钥长度
  KeyPair keyPair = keyPairGenerator.generateKeyPair();//生成密钥对
  return keyPair;
}

获取公钥

1
2
3
4
5
6
7
8
9
10
11
/**
     * 获取公钥的模数(16进制)+指数(16进制)
     * @param keyPair
     * @return
     */
public static String getHexModulusPublicKey(KeyPair keyPair){
  RSAPublicKey pub = (RSAPublicKey)keyPair.getPublic();
  String modulus = pub.getModulus().toString(16).toUpperCase();
  String exponent = pub.getPublicExponent().toString(16).toUpperCase();
  return modulus + "-" + exponent;
}

获取私钥

1
2
3
4
5
6
7
8
9
10
11
/**
     * 获取私钥的模数(16进制)+指数(16进制)
     * @param keyPair
     * @return
     */
public static String getHexModulusPrivateKey(KeyPair keyPair){
  RSAPrivateKey pri = (RSAPrivateKey)keyPair.getPrivate();
  String modulus = pri.getModulus().toString(16).toUpperCase();
  String exponent = pri.getPrivateExponent().toString(16).toUpperCase();
  return modulus + "-" + exponent;
}

还原公钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
     * 从模数+指数中还原公钥
     * @param modulusAndExponent
     * @return
     * @throws NoSuchAlgorithmException
     * @throws InvalidKeySpecException
     */
public static PublicKey toPublicKeyFromModulus(String modulusAndExponent)
  throws NoSuchAlgorithmException, InvalidKeySpecException {
  String[] ss = modulusAndExponent.split("-");
  BigInteger modulus = new BigInteger(ss[0],16);
  BigInteger publicExponent = new BigInteger(ss[1],16);
  RSAPublicKeySpec keySpec = new RSAPublicKeySpec(modulus,publicExponent);
  KeyFactory keyFactory = KeyFactory.getInstance("RSA");
  PublicKey publicKey = keyFactory.generatePublic(keySpec);
  return publicKey;
}

还原私钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
     * 从模数+指数中还原私钥
     * @param modulusAndExponent
     * @return
     * @throws NoSuchAlgorithmException
     * @throws InvalidKeySpecException
     */
public static PrivateKey toPrivateKeyFromModules(String modulusAndExponent)
  throws NoSuchAlgorithmException, InvalidKeySpecException {
  String[] ss = modulusAndExponent.split("-");
  BigInteger modulus = new BigInteger(ss[0],16);
  BigInteger privateExponent = new BigInteger(ss[1],16);
  RSAPrivateKeySpec keySpec = new RSAPrivateKeySpec(modulus,privateExponent);
  KeyFactory keyFactory = KeyFactory.getInstance("RSA");
  PrivateKey privateKey = keyFactory.generatePrivate(keySpec);
  return privateKey;
}

参考资料

https://www.jianshu.com/p/288b3f3e91a5

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

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

https://blog.csdn.net/taoxin52/article/details/53782470

https://blog.csdn.net/lvxiangan/article/details/45487943




FEATURED TAGS
安全算法