1.2 RSA 乘法同态：一次计划外的发现

1.2 RSA 乘法同态：一次计划外的发现

本节摘要：RSA 在一九七八年问世时瞄准的是机密性与签名，它的乘法同态性是结构的副产物：两个密文的乘积恰等于两个明文乘积的密文。本节回到历史现场讲清这条性质如何被"顺手发现"，用可复算的小素数算例把它跑通，再解释为什么确定性加密与填充标准让这份天赋沉睡了三十年，最后把 ElGamal 与 RSA 放进部分同态的分类框架。

历史现场：一份没被领取的礼物

一九七八年，Rivest、Shamir、Adleman 发表公钥密码体制的同一年，Rivest 的名字还出现在另一篇少有人注意的短文里——与 Adleman、Dertouzos 合写的"数据银行与隐私同态"。两篇论文一个造锁，一个许愿。有趣的是，造锁那篇的成果里恰好埋着许愿那篇要的东西：RSA 的加密函数是模幂运算，而幂运算对底数的乘法天然守恒——两个密文相乘，等于对应明文相乘后再加密。这个性质在当时被当作"有趣但危险的好奇心"：教科书式的 RSA 因此是确定性的，同一明文永远加密成同一密文，连语义安全的门槛都没过，更别提拿去做密文运算了。

真正的历史脉络要分两支看。一支是实践派：电子投票、可验证加密等协议研究里，学者们确实频繁调用 RSA 与 ElGamal 的乘法同态性质——比如选票的"加密后相乘"被用来聚合签名与证明。另一支是理论派：他们盯着"乘法有了，加法没有"的残局，寻找能同时装下两种运算的结构。这条支线在一九九九年由 Paillier 暂时推进了一步（下一节的主角），然后陷入长达十年的沉寂。粗略地说，从构想的提出到全同态的破冰，中间隔了一代密码学家的整个职业生涯。

性质本身：两行推导与一个可复算的算例

RSA 的加密只有一个操作：把明文做成底数，做模幂。设公钥模数为两素数之积，加密指数公开，则密文等于明文的该次幂对模数取余。两个密文相乘再取模，等于两个明文之积的同一次幂取模——指数律直接给出结论，推导不过两行。更深一层看：RSA 密文空间是一个乘法群，加密是群上的指数映射，同态性不过是群结构守恒的自然结果。结构在，运算就在；这正是上一节"结构决定能力"的第一次实战。

下面是可以手算复验的完整算例，采用经典教学参数：取素数六十一与五十三，模数为三千二百三十三，公开指数十七，私钥指数二千七百五十三。我们加密明文七与十一，然后分别在密文域和明文域做乘法对照。

# RSA 乘法同态：经典教学参数的完整算例（可逐行复算）
# 模数 n = 61 x 53 = 3233，公钥指数 e = 17，私钥指数 d = 2753

def modpow(base, exp, mod):
    result, base = 1, base % mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

n, e, d = 3233, 17, 2753

E7  = modpow(7,  e, n)   # 加密明文 7   -> 2369
E11 = modpow(11, e, n)   # 加密明文 11  -> 3061
E77 = modpow(77, e, n)   # 加密明文 77（对照组）

prod = E7 * E11 % n      # 密文域：只做一次乘法
print("E(7)  =", E7)
print("E(11) =", E11)
print("密文之积 =", prod)        # 3123
print("E(77)    =", E77)        # 3123，两者相等
print("解密验证 =", modpow(prod, d, n))  # 77

# 乘法可以无限串联：密文立方 = 明文立方的密文
cube = E7 * E7 * E7 % n
print("E(7)^3 密文立方 =", cube)          # 1257
print("E(343)         =", modpow(343, e, n))  # 1257
​

三组数字全部对上：密文之积解密回七十七，密文立方解密回三百四十三。运行这段代码不需要任何密码库，一个 Python 解释器就够。这就是"乘法同态无限次"的实感——它不消耗任何预算，因为模幂结构不会因为多乘几次而"变脏"。记住这个干净得反常的细节：等到下一节噪声登场、再到第二章乘法开始付出代价时，你会怀念这个时代。

为什么这份天赋没能直接商用

看历史要看约束。RSA 乘法同态离实用差着三道坎，每一道都值得展开。

第一道是确定性。教科书 RSA 对同一明文永远给出同一密文，攻击者只需把候选明文逐一加密比对即可破解——这就是选择明文攻击下的完全失败。语义安全要求引入随机性，而一九九零年代出现的填充标准（概率性的 OAEP 等）在换取安全的同时，把乘法结构搅碎了：填充后密文之间不再保持任何整洁的代数关系。安全与同态在此第一次正面冲突，这个冲突将贯穿全册——直到格密码方案把随机性做成"误差项"，两者才在新的结构里共存。

第二道是运算方向锁死。指数结构只守恒乘法：想在密文上算加法，你面临的是"乘法群上做加法"的困难问题（离散对数），恰好是密码学家刻意选用的最硬的骨头之一。想要加法同态，得换地基，这就是 Paillier 的出场逻辑。

第三道是无人需要的尴尬。那个年代"外包计算"的市场还不存在，云还未兴起，密文上做乘法找不到买单的场景。技术史里"正确的发现出现在需求之前"是常态，同态加密是最极端的样本之一：从发现到起飞，中间隔了三十多年的生态位空缺。

ElGamal 与分类框架：把"部分同态"定义清楚

一九八五年的 ElGamal 把同样的乘法同态换了个结构实现：密文是二元组，第一分量随随机性变化，第二分量藏着明文与随机数的纠缠。两个 ElGamal 密文按分量相乘，得到的正是明文之积的加密——推导同样只有两行，但与教科书 RSA 不同，ElGamal 每次加密自带随机数，天然满足语义安全。这解释了为什么后来电子投票协议大量采用 ElGamal 而非裸 RSA：投票场景既要乘法聚合，又要防"同一选票加密结果相同"的比对攻击。

至此可以把"部分同态"这个分类钉牢。判断一个方案属于哪一档，只问两个问题：支持哪种运算？该运算可执行多少次？下面这张表把本节与下一节的主角放进统一框架：

注意表格里没有一个方案能同时进"乘法"和"加法"两列。这不是巧合：能无限做乘法的结构与能无限做加法的结构，在密文空间的代数设计上互相排斥——支持加法需要密文之积对应明文之和，支持乘法需要密文之积对应明文之积，同一个"密文相乘"动作无法兼任两种语义。破局需要更迂回的设计，那正是第二章的故事。

⚠️ 常见坑：不要在产品里直接使用教科书 RSA 的同态性。确定性加密会在真实数据（低熵、可枚举）面前瞬间失守；二零二零年代仍有系统因裸用模幂加密短数字口令被字典攻击打穿。教学算例与工程实践之间隔着填充、参数与实现审计三重门。

本节要点回顾

• 要点一：RSA 的同态性来自幂运算对底数乘法的守恒，是设计的副产物而非目标；ElGamal 用随机化版本实现了同等的乘法同态且语义安全
• 要点二：算例中密文之积解密回明文之积、密文立方解密回明文立方，乘法同态不消耗任何预算——这是与后文噪声模型的根本区别
• 要点三：填充标准（如 OAEP）修复语义安全的同时摧毁同态结构，安全与同态的第一次冲突以同态让步告终
• 要点四：部分同态分类看两个维度——运算种类与执行次数；RSA 与 ElGamal 填乘法列，Paillier 填加法列，无人能同时填两列
• 要点五：需求缺位让这份天赋沉睡三十余年，技术史意义在于说明"发现"与"可用"之间隔着结构与生态的双重距离

乘法同态在协议史上的三次出场

虽然没能长成通用计算工具，RSA 与 ElGamal 的乘法同态在协议史上留下了三次重要出场，值得记录——它们既是同态思想的早期实战，也解释了为什么"同态"这个词在二零零九年之前就已经是密码学家的常用词。第一次出场是可否认的选举协议研究：一九八零年代的电子投票方案用 ElGamal 加密选票，密文相乘聚合出总票数，零知识证明保证选票格式合法——这个"加密聚合加零知识合规证明"的组合结构，与今天第五章联邦学习的加密聚合、区块链场景的合规解密在骨架上完全同源，可以说当代应用是在新地基上重演旧结构。

第二次出场是盲签名与电子现金：利用模幂的代数性质，用户让签名者对"盲化过的消息"签名，签名者既完成了签名又不知道消息内容——电子现金的防双重支付体系建立在这块积木上。盲签名的"遮住内容完成操作"思想，与同态加密的"不见明文完成计算"是同一哲学的两种实现。第三次出场是门限解密：把解密能力拆成多份份额，若干份额协作才能解密一个 ElGamal 密文——门限密码学从这里发展成熟，第五章区块链的门限解密委员会直接继承了这个部件。

三次出场的共同点耐人寻味：乘法同态从未被当作"计算能力"使用，而是被当作"协议结构"使用——人们需要它的代数关系来组装协议，不需要它算出乘积。同态性作为计算能力的觉醒，要等第二章的破冰时刻。这段前史给读者的启示是：一个数学性质的价值，取决于你问它什么问题；问"它能组装什么协议"与问"它能执行什么计算"，会得到完全不同的技术史。

常见问题：能否把 RSA 改造成同时支持加法

历史上确有尝试，思路是把明文编码进指数的加法结构里（模指数的指数相加对应密文相乘），但这条路撞上离散对数——密文域里做"对应明文相加"的运算等价于求离散对数，恰好是方案刻意选用的困难问题。结构自锁：安全性与加法同态在同一根指数上互斥。这个失败的教训被后续设计吸收：想要双重运算，必须让加法与乘法住在密文空间的不同结构层里——这正是格方案"系数层放噪声、明文层放信息"分层设计的思想前身。失败尝试的价值在于它划定了不可能的边界，本册时间线一节会把这类"负结果"也计入演化史。