基于Java实现的RSA原理

  • Post author:
  • Post category:java




(1)RSA原理

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


RSA算法生成步骤如下:

1.寻找两个不相同的质数

随意选择两个大的质数p和q,p不等于q,计算N=p

q;

质数:除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1该数本身两个正因数]的数)。比如2,3,5,7这些都是质数,9就不是了,因为3

3=9了。

2.根据欧拉函数获取r

r =φ(N)=φ§φ(q)=(p-1)(q-1)。

欧拉函数的定义:φ(n)是小于或等于n的正整数中与n互质的数的数目。

互质的定义:如果两个或两个以上的整数的最大公约数是1,则称它们为互质。例如:φ(8) =4,因为1,3,5,7均和8互质。

推导欧拉函数:

(1)如果n=1,φ(1)=1;(小于等于1的正整数中唯一和1互质的数就是1本身);

(2)如果n为质数,φ(n)=n-1;因为质数和每一个比它小的数字都互质。比如5,比它小的正整数1,2,3,4都和他互质;

(3) 如果n是a的k次幂,则φ(n)=φ(a

k)=a

k-a

(k-1)=(a-1)a

(k-1);

(4) 若m,n互质,则φ(mn)=φ(m)φ(n)

证明:设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理(,A

*B

和C可建立双射一一对应)的关系。(或者也可以从初等代数角度给出欧拉函数积性的简单证明) 因此的φ(n)值使用算术基本定理便知。

3. 选择一个小于r并与r互质的整数e,求得e关于r的模反元素,命名为d(ed = 1(mod r)模反元素存在,当且仅当e与r互质),e我们通常取65537。

模反元素:如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

比如3和5互质,3关于5的模反元素就可能是2,因为3

2-1=5可以被5整除。所以很明显模反元素不止一个,2加减5的整数倍都是3关于5的模反元素{…-3, 2,7,12…} 放在公式里就是3

2 = 1 (mod 5)。

上面所提到的欧拉函数用处实际上在于欧拉定理:如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:

a^φ(n) = 1(mod n)

由此可得:a的φ(n – 1)次方肯定是a关于n的模反元素。欧拉定理就可以用来证明模反元素必然存在。由模反元素的定义和欧拉定理我们知道,a的φ(n)次方减去1,可以被n整除。比如,3和5互质,而5的欧拉函数φ(5)等于4,所以3的4次方(81)减去1,可以被5整除(80/5=16)。

小费马定理:

假设正整数a与质数p互质,因为质数p的φ§等于p-1,则欧拉定理可以写成

a^(p-1) = 1 (mod p)

这其实是欧拉定理的一个特例。

4. 销毁p和q

此时我们的(N , e)是公钥,(N, d)为私钥,A会把公钥(N, e)传给B,然后将(N, d)自己藏起来。一对公钥和私钥就产生了。

(2)利用现有开发工具实现RSA的求解,并对常见信息进行加解密。

实现代码:

package internetsafe;

import java.security.InvalidKeyException;
//import java.security.Key;
import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.NoSuchAlgorithmException;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.InvalidKeySpecException;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Base64;
import java.util.HashMap;
import java.util.Map;

import javax.crypto.BadPaddingException;
import javax.crypto.Cipher;
import javax.crypto.IllegalBlockSizeException;
import javax.crypto.NoSuchPaddingException;

public class RSA {
  public static final String KEY_ALGORITHM = "RSA";
  /** 貌似默认是RSA/NONE/PKCS1Padding,未验证 */
  public static final String CIPHER_ALGORITHM = "RSA/ECB/PKCS1Padding";
  public static final String PUBLIC_KEY = "publicKey";
  public static final String PRIVATE_KEY = "privateKey";

  /** RSA密钥长度必须是64的倍数,在512~65536之间。默认是1024 */
  public static final int KEY_SIZE = 2048;

  public static final String PLAIN_TEXT = "123456789";

  public static void main(String[] args) {
      Map<String, byte[]> keyMap = generateKeyBytes();

      // 加密
      PublicKey publicKey = restorePublicKey(keyMap.get(PUBLIC_KEY));
      
      byte[] encodedText = RSAEncode(publicKey, PLAIN_TEXT.getBytes());
      System.out.println("RSA 加密密文: " + new String(Base64.getEncoder().encode(encodedText)));

      // 解密
      PrivateKey privateKey = restorePrivateKey(keyMap.get(PRIVATE_KEY));
      System.out.println("RSA 解密密文: "
              + RSADecode(privateKey, encodedText));
  }

  /**
   * 生成密钥对。注意这里是生成密钥对KeyPair,再由密钥对获取公私钥
   * 
   * @return
   */
  public static Map<String, byte[]> generateKeyBytes() {

      try {
          KeyPairGenerator keyPairGenerator = KeyPairGenerator
                  .getInstance(KEY_ALGORITHM);
          keyPairGenerator.initialize(KEY_SIZE);
          KeyPair keyPair = keyPairGenerator.generateKeyPair();
          RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic();
          RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate();

          Map<String, byte[]> keyMap = new HashMap<String, byte[]>();
          keyMap.put(PUBLIC_KEY, publicKey.getEncoded());
          keyMap.put(PRIVATE_KEY, privateKey.getEncoded());
          return keyMap;
      } catch (NoSuchAlgorithmException e) {
          // TODO Auto-generated catch block
          e.printStackTrace();
      }
      return null;
  }

  /**
   * 还原公钥,X509EncodedKeySpec 用于构建公钥的规范
   * 
   * @param keyBytes
   * @return
   */
  public static PublicKey restorePublicKey(byte[] keyBytes) {
      X509EncodedKeySpec x509EncodedKeySpec = new X509EncodedKeySpec(keyBytes);

      try {
          KeyFactory factory = KeyFactory.getInstance(KEY_ALGORITHM);
          PublicKey publicKey = factory.generatePublic(x509EncodedKeySpec);
          return publicKey;
      } catch (NoSuchAlgorithmException | InvalidKeySpecException e) {
          // TODO Auto-generated catch block
          e.printStackTrace();
      }
      return null;
  }

  /**
   * 还原私钥,PKCS8EncodedKeySpec 用于构建私钥的规范
   * 
   * @param keyBytes
   * @return
   */
  public static PrivateKey restorePrivateKey(byte[] keyBytes) {
      PKCS8EncodedKeySpec pkcs8EncodedKeySpec = new PKCS8EncodedKeySpec(
              keyBytes);
      try {
          KeyFactory factory = KeyFactory.getInstance(KEY_ALGORITHM);
          PrivateKey privateKey = factory
                  .generatePrivate(pkcs8EncodedKeySpec);
          return privateKey;
      } catch (NoSuchAlgorithmException | InvalidKeySpecException e) {
          // TODO Auto-generated catch block
          e.printStackTrace();
      }
      return null;
  }

  /**
   * 加密,三步走。
   * 
   * @param key
   * @param plainText
   * @return
   */
  public static byte[] RSAEncode(PublicKey key, byte[] plainText) {

      try {
          Cipher cipher = Cipher.getInstance(CIPHER_ALGORITHM);
          cipher.init(Cipher.ENCRYPT_MODE, key);
          return cipher.doFinal(plainText);
      } catch (NoSuchAlgorithmException | NoSuchPaddingException
              | InvalidKeyException | IllegalBlockSizeException
              | BadPaddingException e) {
          // TODO Auto-generated catch block
          e.printStackTrace();
      }
      return null;

  }

  /**
   * 解密,三步走。
   * 
   * @param key
   * @param encodedText
   * @return
   */
  public static String RSADecode(PrivateKey key, byte[] encodedText) {

      try {
          Cipher cipher = Cipher.getInstance(CIPHER_ALGORITHM);
          cipher.init(Cipher.DECRYPT_MODE, key);
          return new String(cipher.doFinal(encodedText));
      } catch (NoSuchAlgorithmException | NoSuchPaddingException
              | InvalidKeyException | IllegalBlockSizeException
              | BadPaddingException e) {
          // TODO Auto-generated catch block
          e.printStackTrace();
      }
      return null;

  }
}



版权声明:本文为weixin_44828537原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。