密码学 - 加密和签名算法整理

加密和签名算法整理

对比

RSA加密

目的：保护数据的机密性，确保只有拥有相应私钥的人能够解密数据。

过程：

1. 加密：

   • 使用接收方的公钥 $ e $ 对消息 $ m $ 进行加密。
   • 加密公式：$ c \equiv m^e \pmod{n} $
   • 这里，$ c $ 是密文，$ m $ 是明文，$ n $ 是两个大素数的乘积（$ n = p \times q $），$ e $ 是公钥。

2. 解密：

   • 使用接收方的私钥 $ d $ 对密文 $ c $ 进行解密。
   • 解密公式：$ m \equiv c^d \pmod{n} $
   • 这里，$ m $ 是解密后的明文，$ c $ 是密文，$ d $ 是私钥。

应用：

• 安全的消息传输，例如电子邮件加密、文件加密等。

RSA签名

目的：验证消息的真实性和完整性，确保消息来自合法发送者且未被篡改。

过程：

1. 签名：

   • 使用发送方的私钥 $ d $ 对消息的哈希值 $ h(m) $ 进行签名。
   • 签名公式：$ s \equiv h(m)^d \pmod{n} $
   • 这里，$ s $ 是签名，$ h(m) $ 是消息 $ m $ 的哈希值，$ d $ 是私钥。

2. 验证：

   • 使用发送方的公钥 $ e $ 对签名 $ s $ 进行验证。
   • 验证公式：$ h(m) \equiv s^e \pmod{n} $
   • 这里，$ h(m) $ 是从消息中计算出的哈希值，$ s $ 是签名，$ e $ 是公钥。

应用：

• 数字签名、身份认证、电子合同等需要验证数据来源和完整性的场景。

总结

1. 目的：

   • RSA加密：保护数据的机密性，防止未经授权的人访问数据。
   • RSA签名：验证消息的真实性和完整性，确保消息的来源可靠且未被篡改。

2. 操作过程：

   • RSA加密：
     • 加密：使用接收方的公钥 $ e $ 加密消息。
     • 解密：使用接收方的私钥 $ d $ 解密消息。
   • RSA签名：
     • 签名：使用发送方的私钥 $ d $ 签名消息的哈希值。
     • 验证：使用发送方的公钥 $ e $ 验证签名。

3. 安全性：

   • RSA加密：安全性依赖于公钥加密算法的强度和私钥的保密性。
   • RSA签名：安全性依赖于数字签名算法的强度和私钥的保密性。

4. 应用场景：

   • RSA加密：用于确保数据在传输过程中的机密性。
   • RSA签名：用于确保数据的来源可信且未被篡改。

公式

RSA

加密：

• 明文 $ M $
• 公钥 $ (e, n) $
• 密文 $ C $
  $ C \equiv M^e \mod n $

解密：

• 密文 $ C $
• 私钥 $ (d, n) $
• 明文 $ M $
  $ M \equiv C^d \mod n $

签名：

• 消息 $ M $
• 私钥 $ (d, n) $
• 签名 $ S $
  $ S \equiv M^d \mod n $

验签：

• 签名 $ S $
• 公钥 $ (e, n) $
• 消息 $ M $
  $ M \equiv S^e \mod n $

ElGamal

加密：

• 明文 $ M $
• 公钥 $ (p, g, y) $
  • 素数 $ p $
  • 生成元 $ g $
  • 公钥 $ y = g^x \mod p $，其中 $ x $ 是私钥
• 随机数 $ k $
• 密文 $ (C_1, C_2) $
  $ C_1 \equiv g^k \mod p $
  $ C_2 \equiv y^k \cdot M \mod p $

解密：

• 密文 $ (C_1, C_2) $
• 私钥 $ x $
• 明文 $ M $
  $ M \equiv C_2 \cdot (C_1)^{-x} \mod p $

签名：

• 消息 $ m $
• 私钥 $ x $
• 公钥 $ y = g^x \mod p $
• 随机数 $ k $
• 签名 $ (r, s) $
  $ r \equiv g^k \mod p $
  $ s \equiv (H(m) - xr) \cdot k^{-1} \mod (p-1) $

验签：

• 消息 $ m $
• 签名 $ (r, s) $
• 公钥 $ y $
• $ g $
• 验证方程
  $ g^{H(m)} \equiv y^r \cdot r^s \mod p $

DSA（数字签名算法）

签名：

• 消息 $ m $
• 私钥 $ x $
• 公钥 $ y = g^x \mod p $
• 随机数 $ k $
• 哈希值 $ H(m) $
• 参数 $ p, q, g $
• 签名 $ (r, s) $
  $ r \equiv (g^k \mod p) \mod q $
  $ s \equiv (H(m) + xr) \cdot k^{-1} \mod q $

验签：

• 消息 $ m $
• 签名 $ (r, s) $
• 公钥 $ y $
• 参数 $ p, q, g $
• 哈希值 $ H(m) $
• 验证过程
  $ w \equiv s^{-1} \mod q $
  $ u_1 \equiv H(m) \cdot w \mod q $
  $ u_2 \equiv r \cdot w \mod q $
  $ v \equiv ((g^{u_1} \cdot y^{u_2}) \mod p) \mod q $
  签名有效当且仅当 $ v = r $

详细解释

RSA

1. 加密：

   • 使用接收者的公钥 $ (e, n) $ 对明文 $ M $ 进行加密，计算密文 $ C $。
   • $ C \equiv M^e \mod n $

2. 解密：

   • 使用接收者的私钥 $ (d, n) $ 对密文 $ C $ 进行解密，恢复出明文 $ M $。
   • $ M \equiv C^d \mod n $

3. 签名：

   • 使用发送者的私钥 $ (d, n) $ 对消息 $ M $ 进行签名，计算签名值 $ S $。
   • $ S \equiv M^d \mod n $

4. 验签：

   • 使用发送者的公钥 $ (e, n) $ 对签名 $ S $ 进行验证，检查是否恢复出原消息 $ M $。
   • $ M \equiv S^e \mod n $

ElGamal

1. 加密：

   • 使用接收者的公钥 $ (p, g, y) $ 和随机数 $ k $ 对明文 $ M $ 进行加密，计算密文 $ (C_1, C_2) $。
   • $ C_1 \equiv g^k \mod p $
   • $ C_2 \equiv y^k \cdot M \mod p $

2. 解密：

   • 使用接收者的私钥 $ x $ 对密文 $ (C_1, C_2) $ 进行解密，恢复出明文 $ M $。
   • $ M \equiv C_2 \cdot (C_1)^{-x} \mod p $

3. 签名：

   • 使用发送者的私钥 $ x $、随机数 $ k $ 和消息 $ m $ 进行签名，计算签名值 $ (r, s) $。
   • $ r \equiv g^k \mod p $
   • $ s \equiv (H(m) - xr) \cdot k^{-1} \mod (p-1) $

4. 验签：

   • 使用发送者的公钥 $ y $、生成元 $ g $ 和消息 $ m $ 进行验证，检查签名 $ (r, s) $ 的有效性。
   • $ g^{H(m)} \equiv y^r \cdot r^s \mod p $

DSA

1. 签名：

   • 使用发送者的私钥 $ x $、随机数 $ k $ 和消息 $ m $ 进行签名，计算签名值 $ (r, s) $。
   • $ r \equiv (g^k \mod p) \mod q $
   • $ s \equiv (H(m) + xr) \cdot k^{-1} \mod q $

2. 验签：

   • 使用发送者的公钥 $ y $、生成元 $ g $、参数 $ p, q $ 和消息 $ m $ 进行验证，检查签名 $ (r, s) $ 的有效性。
   • 计算 $ w \equiv s^{-1} \mod q $
   • 计算 $ u_1 \equiv H(m) \cdot w \mod q $
   • 计算 $ u_2 \equiv r \cdot w \mod q $
   • 计算 $ v \equiv ((g^{u_1} \cdot y^{u_2}) \mod p) \mod q $
   • 签名有效当且仅当 $ v = r $