常用非对称加密算法的Python实现及详解

非对称加密算法（Asymmetric Encryption）使用公钥加密、私钥解密，解决了对称加密的密钥分发问题。本文将详细介绍 RSA、ECC、ElGamal、DSA、ECDSA、Ed25519 等非对称加密算法的原理，并提供Python实现代码及安全性分析。

1. 非对称加密概述

1.1 非对称加密的基本原理

• 公钥（Public Key）：用于加密或验证签名，可公开。
• 私钥（Private Key）：用于解密或生成签名，必须保密。
• 核心操作：
  • 加密：C = E(PubKey, P)
  • 解密：P = D(PrivKey, C)
  • 签名：Sig = Sign(PrivKey, M)
  • 验证：Verify(PubKey, M, Sig)

1.2 非对称加密的分类

1.3 非对称加密的应用

• TLS/SSL（如RSA、ECDSA）
• 数字签名（如DSA、Ed25519）
• 加密货币（如比特币使用ECDSA）
• SSH认证（如RSA、Ed25519）

2. RSA（Rivest-Shamir-Adleman）

2.1 算法原理

• 密钥生成：
  1. 选择两个大素数 p 和 q。
  2. 计算 n = p * q 和 φ(n) = (p-1)(q-1)。
  3. 选择 e 使得 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。
  4. 计算 d 使得 d * e ≡ 1 mod φ(n)。
• 公钥：(e, n)
• 私钥：(d, n)

2.2 Python实现

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import binascii

# 生成RSA密钥对
key = RSA.generate(2048)
private_key = key.export_key()
public_key = key.publickey().export_key()

print("私钥:", private_key.decode())
print("公钥:", public_key.decode())

# 加密
message = b"Hello, RSA!"
cipher = PKCS1_OAEP.new(RSA.import_key(public_key))
encrypted = cipher.encrypt(message)
print("RSA加密:", binascii.hexlify(encrypted))

# 解密
cipher = PKCS1_OAEP.new(RSA.import_key(private_key))
decrypted = cipher.decrypt(encrypted)
print("RSA解密:", decrypted.decode())

输出示例：

私钥: -----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAr3...
-----END RSA PRIVATE KEY-----
公钥: -----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG...
-----END PUBLIC KEY-----
RSA加密: b'4a3b2c1d0e9f8a7b6c5d4e3f2a1b0c9d...'
RSA解密: Hello, RSA!

2.3 安全性分析

• 推荐密钥长度：≥2048位（3072位更安全）
• 攻击方式：
  • 大数分解（量子计算机威胁）
  • 旁路攻击（如时序攻击）

3. ECC（Elliptic Curve Cryptography）

3.1 算法原理

• 基于椭圆曲线离散对数问题（ECDLP）
• 曲线方程：y² = x³ + ax + b
• 优势：
  • 更短的密钥（256位ECC ≈ 3072位RSA）
  • 更快的计算速度

3.2 Python实现（ECDH密钥交换）

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import serialization

# 生成ECC密钥对
private_key = ec.generate_private_key(ec.SECP256R1())
public_key = private_key.public_key()

# 序列化密钥
private_pem = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.PKCS8,
    encryption_algorithm=serialization.NoEncryption()
)
public_pem = public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo
)

print("私钥:", private_pem.decode())
print("公钥:", public_pem.decode())

输出示例：

私钥: -----BEGIN PRIVATE KEY-----
MIGHAgEAMBMGByqGSM49AgEGCCqGSM49AwEHBG0wawIBAQQgK2X7sQ...
-----END PRIVATE KEY-----
公钥: -----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEkE9cX7QZ...
-----END PUBLIC KEY-----

3.3 安全性分析

• 推荐曲线：NIST P-256（secp256r1）、Curve25519
• 量子威胁：需迁移到后量子密码（如格密码）

4. ElGamal加密

4.1 算法原理

• 基于离散对数问题
• 密钥生成：
  1. 选择大素数 p 和生成元 g。
  2. 选择私钥 x，计算公钥 y = g^x mod p。

4.2 Python实现

from Crypto.PublicKey import ElGamal
from Crypto import Random
import binascii

# 生成ElGamal密钥对
key = ElGamal.generate(2048, Random.new().read)
public_key = key.publickey()
private_key = key

# 加密
message = b"Hello, ElGamal!"
k = Random.new().read(16)
c1, c2 = public_key.encrypt(message, k)
print("ElGamal加密:", (binascii.hexlify(c1), binascii.hexlify(c2)))

# 解密
decrypted = private_key.decrypt((c1, c2))
print("ElGamal解密:", decrypted.decode())

4.3 安全性分析

• 主要用于混合加密（如PGP）
• 已被ECC替代

5. DSA（Digital Signature Algorithm）

5.1 算法原理

• 基于离散对数
• 仅用于签名（不可加密）

5.2 Python实现

from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256

# 生成DSA密钥对
key = DSA.generate(2048)
private_key = key
public_key = key.publickey()

# 签名
message = b"Hello, DSA!"
hash_obj = SHA256.new(message)
signer = DSS.new(private_key, 'fips-186-3')
signature = signer.sign(hash_obj)
print("DSA签名:", binascii.hexlify(signature))

# 验证
verifier = DSS.new(public_key, 'fips-186-3')
try:
    verifier.verify(hash_obj, signature)
    print("DSA验证成功!")
except ValueError:
    print("DSA验证失败!")

5.3 安全性分析

• 已被ECDSA替代

6. ECDSA（Elliptic Curve DSA）

6.1 Python实现

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import utils

private_key = ec.generate_private_key(ec.SECP256R1())
public_key = private_key.public_key()

# 签名
message = b"Hello, ECDSA!"
signature = private_key.sign(
    message,
    ec.ECDSA(hashes.SHA256())
)

# 验证
try:
    public_key.verify(
        signature,
        message,
        ec.ECDSA(hashes.SHA256())
    )
    print("ECDSA验证成功!")
except:
    print("ECDSA验证失败!")

6.2 安全性分析

• 比特币、TLS 1.3常用

7. Ed25519（EdDSA）

7.1 Python实现

from cryptography.hazmat.primitives.asymmetric import ed25519

private_key = ed25519.Ed25519PrivateKey.generate()
public_key = private_key.public_key()

# 签名
message = b"Hello, Ed25519!"
signature = private_key.sign(message)

# 验证
try:
    public_key.verify(signature, message)
    print("Ed25519验证成功!")
except:
    print("Ed25519验证失败!")

7.2 安全性分析

• SSH、加密货币首选

8. 总结

推荐选择：

• 加密：RSA（兼容性）、ECC（性能）
• 签名：Ed25519（最快最安全）

9. 完整代码库

本文代码基于：

• PyCryptodome（RSA/DSA/ElGamal）
• cryptography（ECC/ECDSA/Ed25519）

安装：

pip install pycryptodome cryptography