基于Java实现的RSA原理

（1）RSA原理

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

RSA算法生成步骤如下：

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

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

质数：除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1该数本身两个正因数]的数）。比如2，3，5，7这些都是质数，9就不是了，因为33=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)=φ(ak)=ak-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，因为32-1=5可以被5整除。所以很明显模反元素不止一个，2加减5的整数倍都是3关于5的模反元素{…-3, 2,7,12…} 放在公式里就是32 = 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;

  }
}

基于Java实现的RSA原理

继续阅读

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

Bugku-WEB-web33

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method