1982年公钥密码学还很年轻RSA问世不过五年DH密钥交换刚刚解决了密钥分发难题。就在这一年的STOC会议上Shafi Goldwasser和Silvio Micali提交了一篇后来被引用到烂的论文题目里带着一股游戏感“Probabilistic Encryption How to Play Mental Poker Keeping Secret All Partial Information”。这篇论文一针见血地指出了当时所有公钥加密方案的共性漏洞它们是确定性的。同一个公钥下加密同一个明文两次得到的密文完全一样。这有什么问题问题大了——如果你知道某人的某个秘密只可能是两个值你甚至不需要解密直接把密文穷举比对就能知道是哪一个。Goldwasser-Micali公钥加密系统以下简称GM就是为回应这个问题而生的。它是历史上第一个被严格证明满足语义安全的公钥加密方案核心思想是概率加密把每一个明文比特放进一个庞大的密文集合究竟落在哪一个点由随机数决定。它依靠的数学难题是二次剩余问题Quadratic Residuosity证明结构极其干净——如果能攻破GM就必然能判定一个合数n下的平方剩余性。这篇文章适合三类人。第一正在学现代密码学刚开始接触语义安全、可证明安全这些概念的学生第二已经用过RSA-OAEP、ElGamal这些方案想追根溯源看“随机化加密”这个设计思路从哪里来的人第三纯粹出于好奇心想搞明白一篇1982年的论文为什么到今天还在被讨论的读者。我会把数学原理、加解密细节、安全证明的主线以及它效率上的致命短板一次讲透。1. 为什么确定性加密注定无法满足现代安全要求1.1 语义安全到底在要求什么香农在1949年提出了完善保密性密文不能泄露关于明文的任何信息。这个定义非常强但代价也很明显密钥必须和明文等长而且一个密钥只能使用一次这在实际系统中难以落地。后来公钥密码学出现以后人们一度把安全目标放宽为“攻击者无法恢复出完整明文”觉得只要密文不是一眼能看懂就算安全。Goldwasser和Micali在1982年把这个标准又拉高了。他们认为即使攻击者无法恢复明文也仍然可能从中得到某些信息比如明文是否是一份特定合同的某个关键字段、是一个大额转账还是小额转账、是“yes”还是“no”。语义安全要求的是从密文中得不到任何关于明文的计算上可解的信息哪怕攻击者事先已经掌握了明文的先验分布和某种关联信息密文也不能再给他增加一丁点有效信息。这个定义在之后被等价地改写成我们熟悉的不可区分性实验也就是IND-CPA安全攻击者提交两个等长明文挑战者随机加密其中一个攻击者猜是哪一个。如果任何高效攻击者的猜测优势都可忽略就称方案是语义安全的。请注意这个定义比“单向性”强得多。单向性只保证“很难从密文反推明文”但一个方案完全可以做到单向却无法做到语义安全比如教科书RSA。1.2 同一个公钥下加密两次不能暴露同一个明文确定性加密的致命问题在于公钥是公开的任何人都可以重放加密。假设方案是确定性的攻击者手里拿到挑战密文c*Enc(pk, m_b)他自己就能在本地把候选明文m0和m1分别加密一遍然后和c*比较一比就能猜出b。攻击者甚至不需要费任何心思去解数论问题。所以问题本质出在“可重放性”上。公钥公开意味着加密过程本身是所有人都能执行的如果加密没有随机化成分攻击者总能通过“重新计算并比对”的方式把密文和明文之间的映射关系给试出来。哪怕你给RSA加上一个固定填充只要填充规则是确定的攻击者依然可以照着重放一遍。因此一个想要达到语义安全的公钥加密方案加密过程必须掺入足够大的随机数让攻击者无法通过穷举随机空间来比对。这其实就是“概率加密”这个思想出现的历史动机。它并不是为了花哨而是为了堵上“公开可重放”这个结构性的大洞。1.3 概率加密的基本想法给密文注入随机性GM的方案思路听上去很简单每个明文比特不要只对应一个合法密文而是对应一大簇合法密文。具体说加密比特0时随机选一个r计算cr² mod n加密比特1时同样随机选一个r计算cy·r² mod n。这里的n是一个大合数y是一个精心挑选的“伪平方剩余”。这样同一个明文比特加密一百次会得到一百个不同的密文。攻击者即使知道候选明文也无法通过重放加密来比对因为对方用的随机数他不知道。更重要的是0对应的密文集合所有模n二次剩余和1对应的密文集合所有伪平方剩余在计算上是不可区分的除非攻击者能解决二次剩余问题。这个设计不是GM随便拍脑袋想的它背后有一个很深刻的权衡概率加密的代价是密文膨胀收益是语义安全第一次变得可证明。整个方案的要害并不在加解密本身而在如何构造出“公开可分辩但计算上不可分辩”的那一组密文分布。2. 先解决数学地基二次剩余、雅可比符号与伪平方剩余2.1 二次剩余与欧拉准则设p为一个奇素数。如果存在整数x使得x²≡a (mod p)并且p不整除a我们就说a是模p的二次剩余否则就是非剩余。这个定义可以很直观地理解为a在模p的意义下是有“平方根”的。判定一个小素数模下的一个数是不是二次剩余最优雅的工具是欧拉准则。对奇素数p和任意ap不整除a计算a^{(p-1)/2} mod p结果只可能是1或p-1。如果结果是1a就是二次剩余如果结果是p-1也就是数学写法里的-1a就是非剩余。这个准则实现起来非常简单本质上就是一次模幂运算所以它成了GM解密时最基本的判定工具。模一个素数p的乘法群是个循环群群里一半元素是二次剩余一半不是。二次剩余这个概念看起来基础却是后续很多密码学方案的地基GM、Blum-Goldwasser、Paillier等方案都长在它的变体上。2.2 雅可比符号公开可计算但不是完整的判定当模数变成合数npq时问题就微妙了。我们把Legendre符号扩展成Jacobi符号定义为(a/n)(a/p)(a/q)其中(a/p)和(a/q)分别是模p、模q下的Legendre符号。Jacobi符号有一个非常友好的性质就算你不知道p和q的分解也能通过数学算法直接计算(a/n)。可问题在于Jacobi符号只能告诉你“符号值”不能告诉你一个数是不是真正的二次剩余。设npq。一个数a如果同时是模p和模q的二次剩余那么(a/n)1并且它确实是模n的二次剩余。但还有另一类数它在模p和模q下都不是二次剩余此时(a/p)(a/q)-1乘起来Jacobi符号仍然是1。这类数被称为“伪平方剩余”。于是整个Jacobi符号为1的集合就被分成了两类一类是真二次剩余一类是伪平方剩余。根据p和q的分解可以轻松区分这两类但如果没有分解区分它们就是著名的二次剩余问题。GM方案的精髓就在这里构造一个公钥公开一个确定是伪平方剩余的元素y然后让0和1分别对应“真二次剩余”和“伪平方剩余”两类分布。没有n的分解没人能区分你给的密文究竟是哪一种。2.3 怎么找到那个关键的y密钥生成阶段我们需要找一个y使得(y/p)(y/q)-1。这等价于要y同时在模p和模q下是非二次剩余。实际操作中直接随机猜随机生成一个2到n-1之间的整数y用欧拉准则分别对p和q做判定如果满足两个都是非剩余就接受它。随机猜的成功率是多少因为模p下一半是二次剩余模q下一半也是二次剩余所以一个随机数同时成为两个模数下非剩余的概率是1/4。这意味着平均尝试四次就能找到一个合格的y效率没有任何压力。这段逻辑也很适合写进密钥生成函数里用一个while循环就能完成。2.4 三个容易绕晕的数学细节细节一Legendre符号的返回值可能是0当a能被p整除时。在GM里所有操作数都是在模n的乘法群中随机数r要避开n的倍数所以实际使用中很少碰到0但做边界判断时别忽略它。细节二Jacobi符号为1绝不意味着这个数在模n下有平方根。只有同时满足(a/p)1且(a/q)1的数才真的有平方根而Jacobi符号为1只说明(a/p)和(a/q)同号可能是(1,1)也可能是(-1,-1)。细节三欧拉准则不能直接用于合数模。a^{(n-1)/2} mod n的结果即使等于1也不能说明a是模n的二次剩余。想判定一个数在合数模下是不是二次剩余必须把它拆到p和q上分别用Legendre符号。GM的解密过程之所以需要私钥本质上就是因为这个拆解需要知道p和q。3. GM加解密全流程拆解逐比特编码与判定3.1 密钥生成密钥生成要做三件事选两个大素数p和q通常要求长度接近避免被特殊分解算法攻破计算npq再选一个满足(y/p)(y/q)-1的伪平方剩余y。公钥是(n, y)私钥是(p, q)。n的位数直接决定安全强度工程上如果硬要用GMn至少要2048位。用示意代码描述密钥生成逻辑就是def gm_keygen(bits2048): p random_prime(bits // 2) q random_prime(bits // 2) n p * q while True: y random.randrange(2, n - 1) if legendre(y, p) p - 1 and legendre(y, q) q - 1: return (n, y), (p, q)这里legendre函数可以预先定义成def legendre(a, p): return pow(a, (p - 1) // 2, p) # 返回1表示二次剩余返回p-1表示非剩余整个过程完全是概率性的多跑几次同一个p、q会得到不同的y但任意一个合格的y都不影响后续加解密的正确性。3.2 加密0和1分别怎么处理加密函数的输入是公钥pk(n, y)和一个明文比特bit再引入一个随机数r。加密逻辑只有两行若bit0密文c r² mod n若bit1密文c y·r² mod n。这里r必须是从1到n-1之间随机选取的整数且要和n互素。在实际的密码库中通常直接用密码学安全随机数源生成一个大整数再对n取模并检查gcd(r, n)1如果不为1就重新生成。也可以用r直接取模n后拒绝n的倍数。值得注意的是加密同一比特时r绝不能复用。一旦某个r被用了两次两个密文之间的比例关系就会泄露r²的信息攻击者可能直接通过y判断结构。这个点在后文的具体复现建议里还会再提到。3.3 解密利用欧拉准则还原比特解密者收到密文c后要用私钥p、q计算两个Legendre符号(c mod p)和(c mod q)。如果两者都等于1说明c在模n下是真正的二次剩余明文就是0否则只要其中一个等于-1明文就是1。为什么这么做是对的因为加密0时cr²它在模p和模q下显然都是平方两个Legendre符号都是1。加密1时cy·r²而y在这两个模数下都是非二次剩余所以(c/p)和(c/q)都是-1至少一个不是1解密函数直接输出1。整个过程不需要任何复杂的求逆或离散对数运算只有两次模幂。在代码里可以这样写def gm_dec(sk, n, c): p, q sk cp legendre(c % p, p) cq legendre(c % q, q) return 0 if cp 1 and cq 1 else 1核心直觉非常干净私钥就是“判定二次剩余的工具”公钥只是给了一个“无法区分两类数”的公开描述。合法接收者用私钥可以直接看穿密文属于哪一类而没有私钥的外部攻击者面对同一个问题却束手无策。3.4 一个可手算验证的完整小例子为了把上面的流程落到实处我用手算一个极小的例子。取p19q23于是n437。选y10检验一下模19的二次剩余集合是{1,4,9,16,6,17,11,7,5}10不在其中模23的二次剩余集合是{1,2,3,4,6,8,9,12,13,16,18}10也不在其中。所以(y/p)-1(y/q)-1y是一个合格的伪平方剩余。加密比特0随机取r5计算c₁5² mod 437 25。解密时(25 mod 19)66在模19的二次剩余集合里Legendres符号为1(25 mod 23)22在模23的二次剩余集合里也为1。两个都是1输出0正确。加密比特1同样取r5计算c₂10×25 mod 437 250。解密时(250 mod 19)33不在模19的二次剩余集合里Legendres符号为-1所以直接输出1正确。注意c₁25和c₂250的Jacobi符号都是1。如果只看(n,y)和这两个密文你没有任何办法在不分解437的前提下区分它们它们都是“某个r²”或“某个y r²”的样子。但知道p19、q23后一个取模运算就真相大白。这就是整个GM方案最精华的“陷门结构”。4. 安全性论证的主线破译GM等价于解QR问题4.1 安全定义从直觉到IND-CPA实验要理解GM的安全论证先要把“安全性”这个词换成可操作的语言。密码学界通用的做法是定义一个攻击游戏也叫不可区分性实验。游戏流程如下挑战者运行密钥生成算法得到公钥和私钥然后把公钥交给攻击者。攻击者可以任意调用加密函数这是公钥系统天然允许的。攻击者选定两个长度相同的候选明文m₀和m₁提交给挑战者。挑战者随机选一个b∈{0,1}计算c*Enc(pk, m_b)返回给攻击者。攻击者输出猜测b。如果攻击者猜对的概率严格大于1/2且优势不可忽略我们就说这个方案在这个实验下不安全反之如果任何高效攻击者的优势都是可忽略的方案就是语义安全的。GM的明文空间是单个比特所以m₀和m₁就是0和1。挑战者实际上是在问攻击者“我给你一个密文你能看出来它是由r²构成的还是由y·r²构成的吗”这个判断能力正好对应二次剩余问题的判定能力。4.2 归约构造把区分器转成QR解算器假设存在一个攻击者A能以不可忽略的优势ε区分GM密文到底是明文0还是明文1。我们现在构造一个算法B它试图解决二次剩余问题B收到了一个随机挑战z其中z是模n的雅可比符号为1的元素并且以50%概率是真二次剩余50%概率是伪平方剩余。B的任务是判断z属于哪一类。B的做法很直接先把公钥(n,y)交给A。当A提交两个候选明文后B不需要真的运行加密算法直接把收到的挑战z作为挑战密文c*返回给A。这里的关键观察是如果z是真二次剩余那么它的分布和Enc(0)的分布完全一致都是随机二次剩余如果z是伪平方剩余那么它的分布和Enc(1)的分布完全一致。因此A的猜测结果可以直接被B采用如果A输出“明文0”B就输出“z是二次剩余”如果A输出“明文1”B就输出“z是伪平方剩余”。这样一来A如果真的有不可忽略的区分优势B就获得了同样不可忽略的QR问题求解优势。由于我们相信二次剩余问题在当前所有的已知算法下都是困难的于是反推出A不存在。这就是一个标准的“归约证明”也是可证明安全里最常见的思路把方案安全性化归到某个公认的数学难题上。4.3 为什么这个证明是开创性的在GM之前公钥加密方案的安全性论证基本停留在“目前没人能破解”的经验层面或者只证明某种弱性质比如单向性。GM首次建立了一个完整链条从“密文不可区分”这个强安全目标到“二次剩余难题”这个清晰数论假设中间没有任何模糊地带。更重要的是GM的证明结构天生就是概率性的。随机数r的存在不是锦上添花而是归约能够成立的必要条件。正是因为加密引入了随机性挑战者才能把一个陌生的QR挑战z合法地伪装成一次正常加密从而把攻击者的能力“搬运”到数论问题上。这种“模拟器”式的证明范式后来成为整个现代密码学教科书的基础。5. 性能硬伤密文膨胀率与现实中几乎不用的原因5.1 一个比特要付出2048位密文GM最致命的问题是密文膨胀。一个比特的明文加密后是一个1到n-1之间的整数而n至少要2048位才安全。也就是说每加密1比特明文密文占2048比特膨胀率是2048倍。如果加密一个128位的AES密钥密文长度是128×2048等于262144位约32KB加密一个256位的会话密钥更是直接到64KB。这个数字在实际网络环境下完全不可接受。普通TLS握手里传送一个expired证书都没这么夸张。GM的证明虽然优雅但它的结构决定了每个明文比特都需要“消耗”一次模n运算和一次n长度的密文表示。因为它把一个比特的安全性就建立在了一次QR判定的难度上整个密文空间至少和n一样大无法压缩。可以说它是用巨大的通信开销换取了最干净的语义安全证明。5.2 和后续概率加密方案的对比GM之后出现的几个方案都在尝试改善它的膨胀率用不同的思路保留“随机化”这一核心。方案安全假设密文膨胀定位Goldwasser-MicaliQR难题约2048倍理论先驱OT与承诺等场景Blum-GoldwasserQR难题接近1倍改进GM伪随机密钥流ElGamalDDH/CDH难题2倍群上的概率加密通用性广Paillier复合剩余类难题2倍加法同态加密隐私计算常用RSA-OAEPRSA难题约1倍现代TLS/加密标准从表格能看出Blum-Goldwasser是把QR思想从“逐比特判定”升级成“伪随机序列生成”把膨胀率一下子压了下来ElGamal和Paillier则是在不同代数结构里找到自己的“随机化陷门判定”组合。但无论是哪一个核心骨架都带着GM的影子公钥决定了一个难分辩的分布私钥提供了一种可以穿透该分布的陷门能力。5.3 它真正留在工程里的位置OT、比特承诺那GM现在是不是就只活在教科书里也不是。在安全的“不经意传输”Oblivious TransferOT协议里GM反而有一个很适合它的角落。OT协议的基本场景是发送方有两个消息接收方想且只能取得其中一个但发送方不能知道接收方选择了哪一个。一种简单实现是用GM做四选一的一步发送方生成两个随机值对应的GM密文分别对应比特0和比特1接收方根据自己的选择比特解密其中一个。由于密文的概率特性接收方无法用另一把私钥判断另一个密文发送方也看不到接收方实际选择的是哪个。GM逐比特、独立生成密文的特点让这种协议在原型实现里显得非常自然。另一个用途是比特承诺承诺方把一个比特加密后交给验证方验证方当时看不到比特但承诺方事后可以打开承诺并证明自己没有作弊。GM天然适合这个场景因为同一个比特可以生成无数个随机密文打开时只需要披露r即可。一旦r被披露验证方就能确认当时密文确实是某个固定比特的加密。当然在这些场景中GM依然会碰到性能问题所以它更多出现在理论协议原型、课堂作业和研究者验证新思路的样例里。6. 从GM到现代密码学概率加密的遗产6.1 Blum-Goldwasser第一轮效率修复Blum和Goldwasser在1984年发表了基于QR难题的高效公钥加密方案思路和GM一脉相承但不逐比特生成独立密文。他们用私钥p、q作为某种伪随机数发生器的种子生成一段足够长的伪随机密钥流再用这个密钥流去掩盖消息。解密时知道p、q的人能重新推导出这个密钥流从而还原明文。这个方案把GM的密文膨胀率从2048倍直接压到了接近1倍同时仍然保持在QR假设下可证明安全。Blum-Goldwasser让研究者们看到了一个重要的可能性概率加密的思想不必总是以“一位一密文”的笨重方式落地它可以借助伪随机生成器变得实用。这个设计思路后来对流密码和伪随机数的理论也产生了深远影响。6.2 OAEP、Paillier与现代密码学的随机化1994年Bellare和Rogaway把概率加密的思想推广到了RSA之上提出了OAEP填充算法。RSA本身是确定性的直接加密相同消息永远得到相同密文无法达到语义安全。OAEP通过随机化消息填充使每次加密同一个消息都能得到不同的密文并在随机预言机模型下证明了RSA-OAEP的IND-CCA安全性。今天TLS 1.3里的RSA加密、以及很多标准库中的RSA加密实现使用的都是OAEP填充。换句话说GM提出的“随机化密文”思想最终变成了主流公钥加密的标准动作。Paillier在1999年则把这种思想带到了完全不同的代数结构上它公开一个复合数n加密时同样给消息乘上一个随机r⁽ᵗ⁾之类的元素让密文随机化同时利用“不知道因子分解就无法区分第n次剩余”的假设。Paillier实现了加法同态成为现代隐私计算和联邦学习加密聚合里的常见工具。回头看GM几乎给“随机化陷门判定”这套密码学打法打了个样后续所有方案都在这个骨架上更换不同的代数结构。6.3 复现GM时容易踩的坑与经验我自己动手实现GM的时候踩过或观察过几个很典型的坑在这里集中说一下。第一随机数r的来源和复用问题。r必须来自密码学安全随机数源比如操作系统提供的随机接口不能使用普通线性同余伪随机数。更重要的是r绝不能复用。如果两个密文用了同一个r那么c₀/y和c₁/y内部就存在明显的比例关系攻击者有可能通过比值判定密文结构。密钥交换协议里一旦出现随机数复用整个安全性立刻土崩瓦解。第二y的选择节点。我见过有人把y写死成某个固定常量公开到文档里说“反正公开也没关系”。从正确性上确实没问题但要达到标准安全定义y通常应当由密钥生成算法随机生成不能由使用者事先指定。写死某个y虽然不会直接破坏正确性但会让方案的部署模式偏离教科书假设一旦这个y关联到了某些已知结构的伪平方剩余攻击者可能找到捷径。第三明文的编码顺序。GM明文空间是{0,1}没法直接加密一块长数据必须先拆分位。拆分后每个比特独立随机生成r生成r的成本、密文长度都会线性叠加。所以GM的正确使用姿势不是加密长消息而是加密一个短随机串比如加密对称密钥的某个关键参数或者用在OT这类只有少数比特交互的协议里。第四解密阶段的符号计算。判断二次剩余时必须用欧拉准则算模幂不要尝试用扩展欧几里得算法去“解方程”也不要用随机抽验的方式猜结果。欧拉准则对素数模是确定性判定只要模数是素数结果就一定是可靠的。第五如果想真正理解GM的安全证明强烈建议跟着Katz-Lindell《Introduction to Modern Cryptography》第十章把归约步骤亲手写一遍。只读不动笔很容易产生“好像懂了”的错觉真正动手重推一遍才能看到那个模拟器构造里的精妙之处。我第一次完整读GM那篇论文是在研究生讨论班上读完最大的震撼不在于方案本身而在于它展示了“证明”这件事在密码学里可以如此彻底你想攻破这个加密系统最终等价于解决一个古老的数论问题。后来我去实现Blum-Goldwasser和Paillier发现所有复杂度都建立在“随机化密文陷门判定”这个骨架上。如果你也想真正理解现代公钥加密为什么长成今天这样从GM开始是一条特别值得走的路。