公钥加密的公式分类整理

RSA 公钥加密

  1. RSA 加密方案

    • 密钥生成:

      • 选择两个大素数 $ p $ 和 $ q $
      • 计算 $ n = pq $
      • 计算 $ \phi(n) = (p-1)(q-1) $
      • 选择一个整数 $ e $（满足 $ 1 < e < \phi(n) $ 且 $ \gcd(e, \phi(n)) = 1 $）
      • 计算私钥 $ d $（满足 $ ed \equiv 1 \pmod{\phi(n)} $）
      • 公钥为 $ (e, n) $，私钥为 $ (d, n) $

    • 加密:

      • 明文 $ m $
      • 密文 $ c = m^e \mod n $

    • 解密:

      • 密文 $ c $
      • 明文 $ m = c^d \mod n $

基于离散对数的公钥加密

  1. ElGamal 加密方案

    • 密钥生成:

      • 选定大素数 $ p $ 和生成元 $ g $
      • 选择私钥 $ x $（随机数），计算公钥 $ y = g^x \mod p $
      • 公钥为 $ (p, g, y) $，私钥为 $ x $

    • 加密:

      • 明文 $ m $
      • 选择随机数 $ k $（满足 $ 1 < k < p-1 $）
      • 计算 $ c_1 = g^k \mod p $
      • 计算 $ c_2 = m \cdot y^k \mod p $
      • 密文为 $ (c_1, c_2) $

    • 解密:

      • 密文 $ (c_1, c_2) $
      • 计算 $ s = c_1^x \mod p $
      • 计算明文 $ m = c_2 \cdot s^{-1} \mod p $

基于椭圆曲线离散对数的公钥加密

  1. 椭圆曲线 ElGamal 加密方案

    • 密钥生成:

      • 选定椭圆曲线 $ E $ 和基点 $ G $
      • 选择私钥 $ d $（随机数），计算公钥 $ Q = dG $
      • 公钥为 $ (E, G, Q) $，私钥为 $ d $

    • 加密:

      • 明文点 $ P_m $
      • 选择随机数 $ k $
      • 计算 $ C_1 = kG $
      • 计算 $ C_2 = P_m + kQ $
      • 密文为 $ (C_1, C_2) $

    • 解密:

      • 密文 $ (C_1, C_2) $
      • 计算 $ P_m = C_2 - dC_1 $

总结

  • RSA 公钥加密:

    • 基于大整数分解难题，公钥用于加密，私钥用于解密。

  • 基于离散对数的公钥加密:

    • ElGamal 加密方案基于离散对数问题，使用生成元和大素数进行加密和解密。

  • 基于椭圆曲线离散对数的公钥加密:

    • 椭圆曲线 ElGamal 加密方案，使用椭圆曲线上的点和基点进行加密和解密。提供更高的安全性和效率。