非对称加密算法

# 简介

非对称加密算法的加密与解密使用不同的密钥，即公钥和私钥。通常来说，发送方使用公钥加密数据后发送，接受方使用私钥解密数据得到明文

# DH

DH（Diffie-Hellman 密钥交换）算法用于安全的发放收发双方约定的密钥

DH算法是第一个密钥协商算法，仅用于密钥分配，不能用于加解密消息

# 消息传递流程

• 收发双方构建本地密钥。构建密钥时，使用本方的私钥及对方的公钥构建本地密钥
• 发送方使用本地密钥加密消息发送
• 接受方使用本地密钥对收到的消息解密

# API 使用流程

• 通过调用生成甲方密钥对
• 通过甲方公钥生成乙方密钥对
• 构建甲方本地密钥：通过甲方私钥与乙方公钥构建
• 构建乙方本地密钥：通过乙方私钥与甲方公钥构建
• 甲方加密
• 乙方解密

# 代码

• Java API

  // 初始化甲方密钥 - 直接构建
  public static Map<String, Object> initKey() throws Exception {
      // 1.实例化DH算法的密钥对生成器
      KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("DH");
      keyPairGenerator.initialize(512);  // 初始化生成器 - 密钥长度需64的整数倍，默认1024
  
      // 2.生成密钥对
      KeyPair keyPair = keyPairGenerator.generateKeyPair();
      DHPublicKey publicKey = (DHPublicKey) keyPair.getPublic();  // 甲方公钥
      DHPrivateKey privateKey = (DHPrivateKey) keyPair.getPrivate(); // 甲方私钥
      
      // 3.hash表存储密钥并返回
      Map<String, Object> KeyMap = new HashMap<String, Object>(2);
      keyMap.put("DHPublicKey", publicKey);
      keyMap.put("DHPrivateKey", privateKey);
      return keyMap;
  }
  
  // 初始化乙方密钥 - 根据甲方公钥构建自己的密钥对
  public static Map<String, Object> initKey(byte[] publicKey) throws Exception {
      // 1.根据传入的公钥转换成可生成本地密钥对的公钥
      X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(publickey);  // 公钥转换材料。X509为数字证书文档，根据RFC 5280编码
      KeyFactory keyFactory = KeyFactory.getInstance("DH");  // 实例化
      PublicKey pubKey = keyFactory.generatePublic(x509KeySpec);  // 产生转换后的公钥
          
      // 2.根据转化后的公钥构建密钥对
      DHParameterSpec dhParamSpec = ((DHPublicKey) pubKey).getParams();
      // 密钥对生成器
      KeyPairGenerator KeyPairGenerator = KeyPairGenerator.getInstance(keyFactory.getAlgorithm())
      // 生成密钥对
      KeyPair keyPair = keyPairGenerator.generateKeyPair();
      DHPublicKey publicKey = (DHPublicKey) keyPair.getPublic();  // 已方公钥
      DHPrivateKey privateKey = (DHPrivateKey) keyPair.getPrivate(); // 已方私钥
      
      // 3.hash表存储密钥对并返回
      Map<String, Object> KeyMap = new HashMap<String, Object>(2);
      keyMap.put("DHPublicKey", publicKey);
      keyMap.put("DHPrivateKey", privateKey);
      return keyMap;
  }
  
  // 构建本地密钥 - 本方的私钥及对方的公钥
  public static byte[] getSecretKey(byte[] publicKey, byte[] privateKey) throws Exception { 
      // 公钥转换为可用公钥
      X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(publickey);  // 公钥转换材料。X509为数字证书文档，根据RFC 5280编码
      KeyFactory keyFactory = KeyFactory.getInstance("DH");  // 实例化
      PublicKey pubKey = keyFactory.generatePublic(x509KeySpec);  // 产生转换后的公钥
          
      // 私钥转换为可用私钥
      PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(privateKey);
      PrivateKey priKey = KeyFactory.generatory.generatePrivate(pkcs8KeySpec);
          
      // 构建本地密钥
      KeyAgreement keyAgree = KeyAgreement.getInstance(keyFactory.getAlgorithm());
      keyAgree.init(priKey);
      KeyAgree.doPhase(pubKey, true);
      // 生成本地密钥
      SecretKey secretKey = keyAgree.generateSecret("AES");
      return secretKey.getEncoded();
  }
  
  // 加密 - 消息加解密使用AES进行，DH只在密钥交换中使用
  public static byte[] encrypt(byte[] data, byte[] key) throws Exception {
      // 转换成可用本地密钥
      SecretKey secretKey = new SecretKeySpec(key, "AES");
      // 加密
      Cipher cipher = Cipher.getInstance(secretKey.getAlgorithm());
      cipher,init(Cipher.ENCRYPT_MODE, secretKey);
      return cipher.doFinal(data);
  }
  
  // 解密 - 消息加解密使用AES进行，DH只在密钥交换中使用
  public static byte[] decrypt(byte[] data, byte[] key) throws Exception {
      // 转换成可用本地密钥
      SecretKey secretKey = new SecretKeySpec(key, "AES");
      // 解密
      Cipher cipher = Cipher.getInstance(secretKey.getAlgorithm());
      cipher,init(Cipher.DECRYPT_MODE, secretKey);
      return cipher.doFinal(data);
  }
  

# RSA

RSA算法由三位学者提出，以三位学者首字母命名，基于因数分解，可用与加密与数字签名。

相对于DES算法，RSA算法效率低，速度慢

# 消息传递流程

• 发送方构建密钥对，公布公钥至消息接受方
• 发送方使用私钥加密数据，将加密内容发送至接受方
• 接受方通过公钥解密，得到消息内容。即“私钥加密，公钥解密”
• 消息的互相发送，即接受方需要向发送方发送消息
  • 如果保持之前情况，则采用“公钥加密，私钥解密”（容易被窃听）
  • 接受方同样生成密钥对，并告知发送方自己的公钥，以保证“私钥加密，公钥解密”
  • 即：私钥加密的数据需要公钥解密，公钥加密的数据需要私钥解密

# 工作模式与密钥长度

密钥长度支持512-65536，必须是64的整数倍

• ECB：密钥长度1024
• None：密钥长度2024

# 涉及到数学内容

• 互质：若N个整数的最大公因数为1，则这N个数互质
  • 判断1：两个质数一定互质
  • 判断2：一个质数与另一个不是它倍数的数一定互质
  • 判断3：两个相邻的数一定互质
  • 判断4：两个相邻的奇数一定互质
  • 判断5：较大的数为质数时，两数互质
  • 判断6：较小的数为质数，较大的数不是其倍数，两数互质（与判断2类似）
  • 判断7：2与任何奇数互质
  • 判断8：1与任何数互质
  • 判断9：通过 辗转相除法
• 欧拉函数：小于等于指定数字 n 的正整数中，与 n 互质的数的个数。例如：n=8，则与 n 互质的数为1、3、5、7，最终结果为4，记为 。质数的欧拉函数为自身减1，即 (为质数)
  • 若 ，其中p与q为质数，则有
• 同余：若 a 与 b 对 m 求模的值相等，则a与b关于模m同余，记为 。例如
  • ，则
• 模反元素：若 a 与 n 互质，则存在 b ，使 可以被n整除（ 除以 n 的余数为1, ），则b为a的模反元素 - 参考百度百科 模反元素open in new window
  • 根据定义可知 （k为任意常数），求解出 x 得到一组模反元素
  • 例如：3 与 11 互质，4 为 3 的模反元素 ， 可以被11整除。-18，-7，15，26等也为3的模反元素（除以11等于0），即 都为模反元素。
  • 此时记为 ，或记为
  • 模逆元的存在，在模数n下的除法可以用和对应模逆元的乘法来达成，此概念和实数除法的概念相同 - 参考wiki百科 模反元素open in new window
• 欧拉定理：若 m 与 n 互质，则
  • 引申： 。根据模反元素定义 就是 m 在模 n 时的模反元素

# 实现流程

寻找一对数字a，b，使得对a求幂还是对b求幂，对n取余后值为对方的逆运算。即 ，

• 公私钥产生
  • 取余对象：任意两质数 p 与 q （加密中会使用较大质数），且 ，得到 。例如，取 p = 3，q = 11， (二进制为100001，6位二进制，即6位加密，实际中会常用1024位)
  • 公钥范围：计算n的互质个数
  • 选公钥：选择小于 的整数 e , ，且需要互质（取模反的条件）。这里取 e = 7。其中，取 e = 19 时，后续生成的公私钥相同
  • 算私钥：求 e 模 的模反元素，命名为d（模反元素定义，需要 e 与 互质）。这里取 k = 1 时, d 的值，3
  • (n, e) 为公钥，（n，d）为私钥。本例中公钥 (33, 7) ，私钥 (33, 3)
  • 如果需要猜测私钥，需要知道公钥范围。而需要两个质数因子p和q，即对n进行质因数分解
• 加密
  • 将待加密文本进行编码，得到字节码。例如：加密数字 3
  • 待加密数字 m 必须小于 n（本例中必须小于33），使用事先约定好的方法将待加密文本转换成数组（每两位16进制组成一个数字，举例中直接用ascii码数组）。数组中数字依次使用 得到密文c。 可用 ，得到 ，密文9
• 解密
  • 根据流程目标，与加密同理
  • 计算, 明文为3

# 原理

• 明确流程

  • 明文 m 使用公钥 e 经过 加密得到密文 c
  • 密文 c 使用私钥 d 经过 解密得到明文 m′
  • 将加密公式代入解密公式可知，只需 证明 即可证明该算法

• 根据公私钥生成过程可知，e 与 d 是模 的模反元素，即存在整数 k ，使得

• 将 式(1) 代入 得到 式(2)

• 将 m 与 n 代入欧拉定理（欧拉定理要求 m 与 n 互质，实际计算中明文 m 与模数 n 不互质也能正常输出），得到 式(3)

• 将 式(3) 两边同乘 m 得到

• 将 式(2) 代入 式(4) 得到 待证明式，即证明完成

# 代码

• Python实现。代码出自GPT：使用python编写rsa算法的实现流程

  import random
  from math import gcd  # 用于计算最大公约数
  from sympy import mod_inverse  # 计算模反元素
  
  def is_prime(n):
      """检查一个数是否为素数"""
      if n <= 1:
          return False
      for i in range(2, int(n ** 0.5) + 1):
          if n % i == 0:
              return False
      return True
  
  def generate_prime(bits=8):
      """生成一个指定位数的素数"""
      while True:
          num = random.getrandbits(bits)
          if is_prime(num):
              return num
  
  def generate_keys(bits=8):
      """生成 RSA 密钥对"""
      # 生成两个大素数 p 和 q
      p = generate_prime(bits)
      q = generate_prime(bits)
      # 计算 n 和 φ(n)
      n = p * q
      phi_n = (p - 1) * (q - 1)
  
      # 选择公钥指数 e (通常选择 65537)
      e = 65537  # 公钥指数
      d = mod_inverse(e, phi_n)  # 私钥指数 - 求模反元素
      
      return (e, n), (d, n)
  
  def encrypt(message, public_key):
      """加密"""
      e, n = public_key
      encrypted_message = [pow(ord(char), e, n) for char in message]
      return encrypted_message
  
  def decrypt(encrypted_message, private_key):
      """解密"""
      d, n = private_key
      decrypted_message = ''.join([chr(pow(char, d, n)) for char in encrypted_message])
      return decrypted_message
  
  # 测试 RSA 加密解密
  public_key, private_key = generate_keys(bits=8)
  message = "Hello RSA"
  print("原始消息:", message)
  
  # 加密
  encrypted_message = encrypt(message, public_key)
  print("加密后的消息:", encrypted_message)
  
  # 解密
  decrypted_message = decrypt(encrypted_message, private_key)
  print("解密后的消息:", decrypted_message)
  

• 代码中的公钥指数补充：关于公钥指数e常用65537，可以加快加密过程

  • 65537 是一个费马素数（Fermat prime），形式为 ，k = 4时，。费马素数的二进制较为特殊，如65537的二进制为10000000000000001，在计算乘法和模运算可以通过快速指数算法（如 快速幂算法）进行优化，从而显著提高计算效率
  • 快速幂算法：将较大的幂运算拆成多个较小的幂运算的乘积，循环查看指定位数是否为1后进行连乘，详细内容可查看快速幂open in new window。以对65537求幂为例

    def binpow(a, b):
        res = 1
        while b > 0:
            if b & 1:
                res = res * a
            a = a * a
            b >>= 1
        return res