Cramer-Shoup 加密算法：IND-CCA2 安全性的里程碑

算法原理 · 2026-09-08

概述

Cramer-Shoup 加密方案是由密码学家 Ronald Cramer 和 Victor Shoup 于 1998 年提出的首个被严格证明满足 IND-CCA2（非自适应选择密文攻击下不可区分）安全性的通用公钥加密方案。在此之前，标准的 ElGamal 加密方案仅能证明 IND-CPA 安全性（抵御选择明文攻击），无法抵抗更强大的选择密文攻击。

Cramer-Shoup 的设计直接推动了公钥加密方案的安全标准升级，其核心思想——引入双重哈希校验和代数结构——成为后来许多安全加密方案（如 RSA-OAEP、ECIES）的设计蓝本。

数学构造

参数设置

设 $G$ 为一个素数阶 $q$ 的循环群，生成元为 $g_1, g_2$。安全性基于决策性 Diffie-Hellman (DDH) 假设。

私钥：$(x_1, x_2, y_1, y_2, z_1, z_2) \in \mathbb{Z}_q^6$

公钥：

CODE

h_1 = g_1^{x_1} · g_2^{x_2}
h_2 = g_1^{y_1} · g_2^{y_2}
h_3 = g_1^{z_1} · g_2^{z_2}

其中 $c_1 = (g_1^{r}, g_2^{r})$ 是加密时的随机值，$r \xleftarrow{R} \mathbb{Z}_q$。

加密算法

给定消息 $m \in G$ 和公钥，加密过程如下：

选取随机 $r \xleftarrow{R} \mathbb{Z}_q$
计算 $c_1 = (g_1^r, g_2^r)$
计算 $u = H(c_1)$，其中 $H$ 是抗碰撞哈希函数，输出 $\mathbb{Z}_q$ 中的元素
计算 $e = h_1^r · h_2^{u·x_1} · h_3^{u·z_1} · m$
计算 $f = h_1^r · h_2^{u·y_1} · h_3^{u·z_2}$
输出密文 $C = (c_1, e, f)$

注意：这里的 $e$ 和 $f$ 是两个校验值，用于验证密文的完整性。

解密算法

给定密文 $C = (c_1, e, f)$ 和私钥 $(x_1, x_2, y_1, y_2, z_1, z_2)$：

验证 $c_1 = (g_1^r, g_2^r)$ 是否一致
计算 $u = H(c_1)$
验证 $e \cdot f^{-1} \stackrel{?}{=} g_1^{r·x_1} · g_2^{r·y_1}$
若验证通过，计算 $m = e · (c_1[1]^{x_1} · c_1[2]^{x_2})^{-1}$
否则返回 $\perp$（无效密文）

安全证明

IND-CCA2 安全性

Cramer-Shoup 方案的关键突破在于其 IND-CCA2 安全性证明。这意味着即使攻击者拥有解密oracle（可以询问任意密文的解密结果），也无法区分两个不同明文的加密。

证明思路：

归约到 DDH 假设：假设存在一个能攻破 Cramer-Shoup IND-CCA2 安全性的攻击者 $\mathcal{A}$，则可以构造一个解 DDH 问题的算法 $\mathcal{B}$。

双重校验机制：密文包含两个校验值 $e$ 和 $f$，任何对密文的篡改都会导致校验失败。

哈希函数的作用：抗碰撞哈希函数 $H$ 将密文第一部分映射为 $\mathbb{Z}_q$ 中的元素，作为二次校验的输入。

与 ElGamal 的对比

特性	ElGamal	Cramer-Shoup
安全性模型	IND-CPA	IND-CCA2
密文长度	2 个群元素	3 个群元素
计算复杂度	低	中等
抗选择密文攻击	否	是

关键区别：Cramer-Shoup 通过额外的校验值 $e$ 和 $f$，使得任何对密文的修改都能被检测到，从而抵御选择密文攻击。

工程实现

参数选择建议

在实际部署中，建议使用以下参数：

群 $G$：素数阶 $q \approx 2^{256}$ 的循环群
生成元：选择固定的 $g_1, g_2$
哈希函数：使用 SHA-256 或更强的抗碰撞哈希

Python 实现示例

PYTHON

import hashlib
import random

class CramerShoup:
    def __init__(self, p, g1, g2):
        self.p = p  # 素数
        self.g1 = g1  # 生成元
        self.g2 = g2  # 生成元
        self.q = p - 1  # 群阶
    
    def keygen(self):
        """密钥生成"""
        x1 = random.randint(1, self.q - 1)
        x2 = random.randint(1, self.q - 1)
        y1 = random.randint(1, self.q - 1)
        y2 = random.randint(1, self.q - 1)
        z1 = random.randint(1, self.q - 1)
        z2 = random.randint(1, self.q - 1)
        
        h1 = pow(self.g1, x1, self.p) * pow(self.g2, x2, self.p) % self.p
        h2 = pow(self.g1, y1, self.p) * pow(self.g2, y2, self.p) % self.p
        h3 = pow(self.g1, z1, self.p) * pow(self.g2, z2, self.p) % self.p
        
        public_key = (self.p, self.g1, self.g2, h1, h2, h3)
        private_key = (x1, x2, y1, y2, z1, z2)
        
        return public_key, private_key
    
    def hash_func(self, c1):
        """抗碰撞哈希函数"""
        return int(hashlib.sha256(str(c1).encode()).hexdigest(), 16) % self.q
    
    def encrypt(self, m, public_key):
        """加密"""
        p, g1, g2, h1, h2, h3 = public_key
        r = random.randint(1, self.q - 1)
        
        c1 = (pow(g1, r, self.p), pow(g2, r, self.p))
        u = self.hash_func(c1)
        
        e = pow(h1, r, self.p) * pow(h2, r * u, self.p) * pow(h3, r * u, self.p) * m % self.p
        f = pow(h1, r, self.p) * pow(h2, r * u, self.p) * pow(h3, r * u, self.p) % self.p
        
        return (c1, e, f)
    
    def decrypt(self, C, private_key):
        """解密"""
        c1, e, f = C
        x1, x2, y1, y2, z1, z2 = private_key
        p = self.p
        
        # 验证密文完整性（防止选择密文攻击）
        # Cramer-Shoup 解密需检查：e/f == h1^r * h2^(u*x1) * h3^(u*z1) mod p
        # 简化验证：直接检查 e * f^(-1) 是否为有效密文结构
        try:
            # 计算解密结果
            m = e * pow(f, -1, p) % p
            # 验证密文结构（简化版：检查 f 是否可逆）
            if f == 0 or m == 0:
                return None
        except (ZeroDivisionError, ValueError):
            return None
        
        return m

注意：上述代码为简化演示版本，实际部署需要使用完整的有限域算术和安全的随机数生成。

国密适配

与国密算法的对比

Cramer-Shoup 加密方案在设计思路上与国密 SM2 加密有相似之处：

特性	Cramer-Shoup	SM2 加密
安全性	IND-CCA2	IND-CCA2
数学基础	DDH 假设	ECDLP
密文结构	3 部分	C1C3C2
校验机制	哈希 + 二次校验	SM3 哈希

核心差异：SM2 加密采用椭圆曲线离散对数问题（ECDLP）作为安全基础，而 Cramer-Shoup 基于决策性 Diffie-Hellman（DDH）假设。两者都属于混合加密方案，即使用 ECC 协商临时密钥，再使用对称加密处理数据。

国密场景下的应用建议

在国密场景中，Cramer-Shoup 方案可以用于：

密钥封装机制（KEM）：作为 SM2 加密的替代方案，提供更高的安全性证明
安全协议设计：在需要 IND-CCA2 安全性的协议中（如 TLS、IPSec）作为底层加密方案
学术研究：作为理解 IND-CCA2 安全性的经典案例

注意：在实际部署中，应优先使用已经过广泛验证的国密标准（如 SM2），而非自行实现 Cramer-Shoup 方案。

已知漏洞与改进

原始方案的局限

密文长度：原始 Cramer-Shoup 方案产生 3 个群元素的密文，比 ElGamal 多 1 个
计算开销：加密和解密都需要多次群运算
参数选择：需要精心选择生成元和哈希函数

改进方案

Cramer-Shoup Lite：通过简化哈希函数调用，减少计算开销。

通用 Cramer-Shoup：将方案推广到任意安全级别，适用于不同的应用场景。

总结

Cramer-Shoup 加密方案是公钥密码学的里程碑式成果，首次严格证明了 IND-CCA2 安全性。其核心设计思想——双重校验、哈希函数引入——成为后续许多安全加密方案的基础。

虽然在实际部署中，SM2 等國密标准更为常用，但 Cramer-Shoup 的理论价值不容忽视。它为密码学家提供了一个清晰的安全框架，帮助理解如何在设计中抵御选择密文攻击。

对于密码学研究者和工程师来说，掌握 Cramer-Shoup 的设计原理，有助于深入理解现代公钥加密方案的安全标准，为设计更安全的密码系统奠定基础。

参考

Cramer, R., & Shoup, V. (1998). *Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack*. SIAM Journal on Computing, 33(1), 8-54.
Shoup, V. (2001). *A Proposal for an ISO Standard for Public Key Encryption*. ISO/IEC JTC 1/SC 27 Working Group 2.
ElGamal 加密方案
SM2 公钥加密算法深度解析

← 返回知识库