在Python中，可以使用`cryptography`库来实现非对称加密算法和哈希函数进行数字签名。`cryptography`是一个由Python Cryptography Authority（PyCA）维护的开源项目，旨在提供现代密码学的基础工具和算法 [^1]。 以下是一个详细的示例代码及解释： ```python from cryptography.hazmat.backends import default_backend from cryptography.hazmat.primitives.asymmetric import rsa, padding from cryptography.hazmat.primitives import hashes from cryptography.hazmat.primitives.serialization import load_pem_private_key, load_pem_public_key from cryptography.hazmat.primitives.serialization import PrivateFormat, Encoding, NoEncryption # 生成私钥 private_key = rsa.generate_private_key( public_exponent=65537, key_size=2048, backend=default_backend() ) # 从私钥中提取公钥 public_key = private_key.public_key() # 待签名的消息 message = b"Hello, World!" # 对消息进行签名 signature = private_key.sign( message, padding.PSS( mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH ), hashes.SHA256() ) # 验证签名 try: public_key.verify( signature, message, padding.PSS( mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH ), hashes.SHA256() ) print("签名验证成功") except Exception: print("签名验证失败") # 私钥的序列化和反序列化 private_pem = private_key.private_bytes( encoding=Encoding.PEM, format=PrivateFormat.PKCS8, encryption_algorithm=NoEncryption() ) loaded_private_key = load_pem_private_key(private_pem, password=None, backend=default_backend()) # 公钥的序列化和反序列化 public_pem = public_key.public_bytes( encoding=Encoding.PEM, format=serialization.PublicFormat.SubjectPublicKeyInfo ) loaded_public_key = load_pem_public_key(public_pem, backend=default_backend()) ``` ### 代码解释： 1. **生成密钥对**：使用`rsa.generate_private_key`函数生成一个2048位的RSA私钥，然后从私钥中提取公钥。 2. **签名过程**：使用私钥对消息进行签名，采用PSS填充方案和SHA256哈希函数。 3. **验证过程**：使用公钥验证签名，如果验证成功则输出“签名验证成功”，否则输出“签名验证失败”。 4. **密钥的序列化和反序列化**：将私钥和公钥序列化为PEM格式的字节串，然后再反序列化回来，以便在不同的环境中使用。 ### 复杂度分析： - **时间复杂度**：签名和验证的时间复杂度主要取决于RSA算法的复杂度，通常为$O(k^3)$，其中$k$是密钥的位数。 - **空间复杂度**：主要取决于密钥的大小和签名的长度，通常为$O(k)$。