跳转到内容
← 返回计算理论
计算理论当代约 23 分钟阅读

Bellare–Rogaway 1994：RSA 前面那两轮掩码为什么被叫优选

Optimal Asymmetric Encryption

OAEPBellare–RogawayEUROCRYPT 1994RSA随机预言机

1994 年 5 月 9 日至 12 日，欧洲密码学年会（EUROCRYPT）在意大利佩鲁贾举行。国际商业机器公司托马斯·J·沃森研究中心的米希尔·贝拉雷（Mihir Bellare）与加州大学戴维斯分校的菲利普·罗加韦（Phillip Rogaway）发表《Optimal Asymmetric Encryption》。会议录次年由斯普林格收入《Advances in Cryptology — EUROCRYPT '94》，计算机科学讲义（LNCS）第 950 卷，页码 92 至 111。DOI 为 10.1007/BFb0053428。主编是阿尔弗雷多·德桑蒂斯（Alfredo De Santis）。印刷 ISBN 为 3-540-60176-7。斯普林格条目把贝拉雷署在 IBM、罗加韦署在戴维斯；不把后年全文上的圣地亚哥通信地址焊进这一章。本页的对象是这份已印行的佩鲁贾会议章：在任意 $k$ 比特陷门置换前面，加两轮由随机预言机 $G$ 与 $H$ 驱动的费斯托掩码，使明文以接近 $k$ 的长度被编成一条恰好 $k$ 比特的串，再被置换一次。课堂所称最优非对称加密填充（OAEP），封面钉在佩鲁贾这一章上。它不是人物评传，也不是把模幂焊进产品的说明书。

会期是一九九四年五月，讲义落到纸面上是一九九五年。同一条 DOI、同一组页码，不是两次发现。作者个人页上偶见另一组分页，斯普林格章页码仍是 92 至 111。一九九五年十一月那份带副标题《How to Encrypt with RSA》的全文，是会议章的论证扩写，通信地址已改到加州大学圣地亚哥分校，不是第二份封面，也不是期刊。

它不是 1993 年 11 月 3 日至 5 日弗吉尼亚费尔法克斯第一届 ACM 计算机与通信安全会议（CCS）页码 62 至 73 的贝拉雷与罗加韦《Random Oracles are Practical》。那一篇 DOI 为 10.1145/168588.168596，对象是随机预言机方法论：先在理想哈希里写协议，再把询问换成具体哈希。本页假定那一套装置已经在那儿，再把它焊到陷门置换前面。同一对作者、隔年两篇、两种对象。方法论不是填充。

它不是RSA 公钥密码算法页上的教科书模幂 me mod nm^e \bmod n。那一档是确定性的、对乘法同态敞开的公开函数。本页把随机种子送进两轮掩码，再对整串做一次置换。把封面听成又一次「用 RSA 加密消息」，会把填充与燃料焊成一次装配。它也不是后年同作者的概率签名方案（PSS）：那是签名垫，不是加密垫。它更不是 OAEP+。加号方案出现在 2001 年维克多·肖普（Victor Shoup）重审原文证明的那一篇里，不是佩鲁贾页码 92 至 111。

它不是 1998 年罗纳德·克拉默与维克多·肖普那份不必再挂非交互零知识、在判定性迪菲–赫尔曼假说下可具体写出的方案。那十三页走的是标准模型与离散对数族，不调用随机预言机。本页走的是理想哈希与陷门置换，RSA 是主展览。两套装置不要焊成一次「可证明的公钥加密」。它不是 2001 年肖普《OAEP Reconsidered》，也不是同年藤崎英一郎、冈本龙明、大卫·普安特舍瓦尔与雅克·斯特恩补全 RSA-OAEP 选择密文证明的那一篇。那两章是后年邻居，不是第二份封面。

它不是 1984 年 4 月《计算机与系统科学杂志》第 28 卷第 2 期页码 270 至 299 的戈德瓦塞尔–米卡利概率加密，DOI 为 10.1016/0022-0000(84)90070-9。那三十页把语义安全写成多项式不可区分，第一次实现按比特膨胀。本页要同一句语义安全，却把膨胀压到密文仍长 $k$。它不是 1988 年卢比–拉科夫那十四页：三轮才挡住正向询问，四轮才挡住连逆向一起问的观察者。本页只用两轮，因为外层已经是陷门置换。它不是密码学基础总览，也不是加密基础总览。总览已经把填充收成一格；本页只抽出佩鲁贾这一枚钉子。

破除误解：优选是膨胀上的算术，不是广告词，更不是一份攻击手册

会期年与讲义年叠在同一条链上。佩鲁贾开会是一九九四年五月，斯普林格把讲义年印成一九九五年。封面仍是这一章，不是圣地亚哥通信地址的全文，更不是一份从未存在过的同名期刊。把年份听成发现次数，会把一次会议章收成两枚钉子。

随机预言机方法论已经先印过了。一九九三年那十二页论证：先在公开随机函数里写协议，再把询问换成具体哈希，可以得到更紧的方案。佩鲁贾章把 $G$ 与 $H$ 取成这种理想函数，并建议从安全哈希算法的压缩函数派生。理想化是证明装置，不是已经造好的哈希产品。把本页听成方法论的重印，会把「怎样用理想哈希」收成「哈希被发明了一次」。

「optimal」在原文里有算术含义。启发式的简单嵌入已经能做到：编码一次、置换一次、密文恰好 $k$ 比特、明文长度靠近 $k$。戈德瓦塞尔–米卡利按比特各做一次置换，密文相对明文拉长到模数那么多倍。若可证明方案必须付两次置换，或把密文写成 $n+k$，实务会继续用启发式。原文把「比特最优」写成：能被 f(rx)f(r_x) 装下的字符串 $x$，长度几乎就是 $k$。种子占去 k0k_0 比特，明文知晓那一档再留下 k1k_1 比特冗余，剩下的 n=k−k0−k1n=k-k_0-k_1 才是载荷。优选回答的是膨胀，不是把方案吹成已经最优的产品。

明文知晓被写成一种定义上的声称：多项式对手不该能交出合法密文，却「不知道」对应明文。原文说，在理想哈希模型里，这一句蕴含不可延展与选择密文那一档。选择密文是对手类的标签：见到挑战之后仍可对解码手续拥有访问权，只是不能把挑战自己送回去。本页停在口径，不把访问权展开成询问日程，也不把核验写成对部署系统的检测步骤。把一九九四年听成已经在标准模型里做完克拉默–肖普那件事，会把随机预言机收成数论假说。

种子、两轮费斯托，以及作用在整串上的陷门置换

装置从「简单嵌入」开始。发送方握有一枚 $k$ 比特到 $k$ 比特的陷门置换 $f$，接收方握有逆映射。实务里明文长度 $n$ 只比 $k$ 短一截。启发式的做法是：把 $x$ 概率地嵌进一条 $k$ 比特串 rxr_x，再输出 f(rx)f(r_x)。裸嵌入 rx=xr_x=x 不够。置换在泛用输入上难求逆，并不等于 $f(x)$ 已经藏住 $x$ 的所有可计算性质。姚期智 1982 年已经把陷门与计算不可区分写成共用装置；戈德瓦塞尔与米卡利把「藏住任何可计算函数」收成语义安全。本页要在简单嵌入的形状上同时满足这两句，并且不把密文拉长到 $k$ 以外。

基本方案把种子写成短的那一侧。取 k0k_0，使观察者的运行时间远小于 2k02^{k_0} 步。明文长度定为 n=k−k0n=k-k_0。$G$ 把 k0k_0 比特种子扩成 $n$ 比特掩码，形状接近后来标准里的掩码生成函数；$H$ 把 $n$ 比特压回 k0k_0 比特。抽一枚均匀的种子 $s$（原文记作 $r$）。第一轮：$G(s)$ 按位掩住明文。第二轮：对掩住之后的那一段求 $H$，再用 $H$ 的输出掩住种子。两轮之后仍是一条 $k$ 比特串。陷门置换作用在这条整串上，不是作用在裸明文上。这是两轮费斯托：左右半不对等，短的一侧是种子，长的一侧是载荷。

明文知晓那一档只多一截约定冗余。再取参数 k1k_1，令 n=k−k0−k1n=k-k_0-k_1。$G$ 扩到 n+k1n+k_1 比特，$H$ 从 n+k1n+k_1 比特压回 k0k_0。明文先与 k1k_1 比特的固定填充拼在一起，再走同一对掩码。合法对象被定义成：陷门还原整串、解开两轮掩码之后，那一截填充仍在约定位置。对不上则该对象不在合法密文集合里，手续拒绝，不把载荷交出去。拒绝是集合的边界，不是一份把畸形串送进解码器的日程。本页不讨论如何选取模数、如何实例化哈希、如何去询问一台已部署的解码器。

两轮不是卢比–拉科夫意义上的「已经像随机置换」。一九八八年那十四页证明：三轮才挡住正向询问，四轮才挡住连逆向一起问的观察者。OAEP 的外层是陷门置换，$G$ 与 $H$ 在证明里是随机函数。安全性不来自两轮费斯托自己像随机置换，而来自理想掩码把嵌入随机化、置换再把整串推到难求逆的一侧。把两轮听成可以替换数据加密标准，会把填充定理收成分组密码规格。

燃料被点名为任意陷门置换。RSA 与模平方都是原文点名的候选。$G$ 与 $H$ 相对一次模幂可以忽略，所以复杂度只按 $f$ 与 f−1f^{-1} 的调用次数来写：编码一次，还原一次，密文仍长 $k$。RSA 是主展览，不是唯一合法的 $f$。把封面听成「RSA 的产品补丁」，会把任意陷门置换上的条件句收成一次模幂工程。

理想哈希是证明模型，不是标准模型。佩鲁贾章跟随前一年的方法论：证明时把 $G$、$H$ 当成随机函数；落到具体方案时再从密码学哈希派生。它没有声称某一种具体哈希已经是随机预言机。它也把「精确安全」写成实务能读的数字：观察者跑时间 $t$，对 $G$ 问 qgenq_{\mathrm{gen}} 次、对 $H$ 问 qhashq_{\mathrm{hash}} 次，若仍能以优势 ε\varepsilon 分开密文总体，则存在把同一优势翻译成求逆 $f$ 的归约。原文举例 $k=512$，是为了让参数对具体模数有意义，不是一份选取密钥长度的编制手续。

它证明了什么，没有覆盖什么

它证明了：在随机预言机模型里，任意 $k$ 比特陷门置换前面加上这一对掩码，可以得到简单嵌入型的公钥加密，编码一次、还原一次、密文仍长 $k$，载荷长度靠近 $k$。基本方案在 $G$、$H$ 为理想函数时达到语义安全。明文知晓那一档把固定填充写进合法对象的定义，并在同一模型里声称由此得到不可延展与选择密文口径。优选是膨胀上的主张：不必为了可证明而把密文拉长到 $n+k$ 或按比特各做一次置换。这句话不是操作单。

它没有证明某一种具体陷门置换难求逆，也没有证明分解困难，更没有裁决 $P$ 对 $NP$。二十页是条件句：若这种置换在那儿，并且 $G$、$H$ 可当成随机函数，相应口径就会跟着在那儿。随机预言机方法论是一九九三年费尔法克斯的封面。午餐时间、自适应时间窗与不可延展作为相关性，分别是纳奥尔–扬、拉科夫–西蒙、多列夫–德沃克–纳奥尔的封面。它没有在标准模型、判定性迪菲–赫尔曼上交出克拉默–肖普那一套群元素加核验。

后年证明缝必须写在封面之后，不能写进封面。2001 年圣芭芭拉国际密码学年会讲义第 2139 卷里，肖普《OAEP Reconsidered》指出：把一般陷门置换的单向性黑盒翻译成 OAEP 的自适应选择密文口径，原文论证有缝，而且缝不能按原设想补上；同一篇给出 OAEP+，不是佩鲁贾对象。紧随其后的藤崎–冈本–普安特舍瓦尔–斯特恩一章证明：在随机预言机模型里，RSA-OAEP 的自适应口径可以收到部分域单向性上；对 RSA，这一档与标准 RSA 假设等价，归约并不紧。两章是后年邻居，不是第二份封面。PKCS 后来把 OAEP 收进公钥密码学标准，那是标准化，不是佩鲁贾页码。

密文膨胀等于种子加冗余，不再等于模数那么多倍；代价是理想哈希。对照属于计算复杂性地图与密码学基础总览。

跨域连接

  • 贝拉雷–罗加韦一九九三年论文：费尔法克斯那十二页把随机预言机写成「先在理想函数里证明、再换成具体哈希」的方法论。本页把 $G$ 与 $H$ 取成那一类理想函数，焊在陷门置换前面。没有方法论，填充的证明模型没有名字；没有本页，方法论还停在范式，没有这一枚简单嵌入。把两篇听成一次印刷，会把装置与用例焊成一句。
  • RSA 公钥密码：算法页管模幂、密钥与后来的填充产品。本页给出的是任意陷门置换前面的两轮掩码定义，RSA 只是主展览。教科书 me mod nm^e \bmod n 是确定性燃料，不是佩鲁贾对象。把封面听成又一份模幂说明书，会把编码与置换收成一次装配。
  • 戈德瓦塞尔–米卡利一九八四年概率加密：那三十页把语义安全写成多项式不可区分，按比特膨胀。本页要同一句安全口径，却把密文钉在 $k$ 比特上。没有语义安全，优选没有要压的那一截代价；没有本页，第一次实现仍按比特付钱。把 1994 年听成又一篇二次剩余加密，会把膨胀定理收成一次谓词抽样。
  • 卢比–拉科夫一九八八年论文：三轮费斯托才挡住正向询问，四轮才挡住连逆向一起问的观察者。本页的两轮不是那条置换定理的特例。外层已经是陷门置换，$G$ 与 $H$ 在证明里是随机函数。把两轮听成已经像随机置换，会把填充收成一次分组密码规格。
  • 克拉默–肖普一九九八年论文：圣芭芭拉那十三页在判定性迪菲–赫尔曼上交出不必再挂非交互零知识的自适应装置，不走随机预言机。本页走理想哈希与 RSA 燃料。把两篇听成同一种「可证明公钥」，会把标准模型与随机预言机焊成一次页码。
  • 拉科夫–西蒙一九九一年论文：那十二页把自适应时间窗写成存在性条件句，撑住窗口的是可抽取的非交互知识证明。本页用明文知晓加理想哈希去声称同一档口径，装置却是掩码而不是证明系统。时间窗是前邻，不是本页新发明的对手类。
  • 多列夫–德沃克–纳奥尔一九九一年论文：那十一页问密文被改写之后明文关系会不会泄漏。原文把明文知晓说成在理想哈希里蕴含不可延展。相关性定义是前邻；两轮掩码是本页的嵌入形状。把两篇听成同一封面，会把关系谓词与费斯托焊成一次印刷。
  • 纳奥尔–扬一九九〇年论文：那十一页把选择密文写成午餐时间，合法密文后面吊着同文语言上的非交互零知识。本页不调用那一套传证，时间窗也不是午餐时间这一档。把填充听成又一份双密文加证明，会把存在性条件句收成一次简单嵌入。
  • 姚期智一九八二年陷门函数论文：芝加哥那十二页把陷门与计算不可区分写成共用装置。本页把陷门置换当成已经在那儿的燃料，再问简单嵌入能不能既随机又几乎不膨胀。
  • 密码学基础：总览需要语义安全、选择密文、不可延展，也需要随机预言机与标准模型两档证明宇宙。本页提供 1994 年把膨胀压到接近 $k$ 的那一次。它没有把模数写成步骤。
  • 加密基础：基础页把「先填充再模幂」写成产品地图上的一格。本页提供的是两轮掩码的定义，以及「优选」在膨胀上的原意。把封面听成已经写好的 PKCS 条款，会把一次条件句收成一次标准对照。

参考文献

  • Mihir Bellare & Phillip Rogaway, "Optimal Asymmetric Encryption", Advances in Cryptology — EUROCRYPT '94, LNCS 950, Springer, 1995, pp. 92–111. DOI: 10.1007/BFb0053428. ISBN: 3-540-60176-7. —— 本文对象。会议 1994 年 5 月 9 日至 12 日举行于意大利佩鲁贾。主编 Alfredo De Santis。
  • Mihir Bellare & Phillip Rogaway, "Optimal Asymmetric Encryption — How to Encrypt with RSA"（1995 年 11 月 19 日全文）。—— 会议章的论证扩写，不是本页封面。
  • Mihir Bellare & Phillip Rogaway, "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols", Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, 3–5 November 1993, pp. 62–73. DOI: 10.1145/168588.168596. —— 前邻：随机预言机方法论，不是填充。
  • Shafi Goldwasser & Silvio Micali, "Probabilistic Encryption", Journal of Computer and System Sciences 28(2), April 1984, pp. 270–299. DOI: 10.1016/0022-0000(84)90070-9. —— 语义安全的先行文本；按比特膨胀，不是本页的简单嵌入。
  • Michael Luby & Charles Rackoff, "How to Construct Pseudorandom Permutations from Pseudorandom Functions", SIAM Journal on Computing 17(2), April 1988, pp. 373–386. DOI: 10.1137/0217022. —— 费斯托轮数阈值的先行文本；三轮与四轮，不是本页的两轮掩码。
  • Andrew C. Yao, "Theory and Application of Trapdoor Functions", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 80–91. DOI: 10.1109/SFCS.1982.45. —— 陷门与不可区分语言的先行文本。
  • Moni Naor & Moti Yung, "Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks", Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, May 1990, pp. 427–437. DOI: 10.1145/100216.100273. —— 前邻：午餐时间加同文非交互零知识。
  • Charles Rackoff & Daniel R. Simon, "Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack", Advances in Cryptology — CRYPTO '91, LNCS 576, Springer, 1992, pp. 433–444. DOI: 10.1007/3-540-46766-1_35. —— 前邻：自适应存在性加知识证明。
  • Danny Dolev, Cynthia Dwork & Moni Naor, "Non-Malleable Cryptography", Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 542–552. DOI: 10.1145/103418.103474. —— 前邻：不可延展性作为相关性。
  • Ronald Cramer & Victor Shoup, "A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack", Advances in Cryptology — CRYPTO '98, LNCS 1462, Springer, 1998, pp. 13–25. DOI: 10.1007/BFb0055717. —— 后年邻居：标准模型、判定性迪菲–赫尔曼，不走随机预言机。
  • Victor Shoup, "OAEP Reconsidered", Advances in Cryptology — CRYPTO 2001, LNCS 2139, Springer, 2001, pp. 239–259. DOI: 10.1007/3-540-44647-8_15. —— 后年邻居：一般陷门置换上原文证明的缝，以及 OAEP+；不是本页封面。
  • Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval & Jacques Stern, "RSA-OAEP Is Secure under the RSA Assumption", Advances in Cryptology — CRYPTO 2001, LNCS 2139, Springer, 2001, pp. 260–274. DOI: 10.1007/3-540-44647-8_16. —— 后年邻居：随机预言机里 RSA-OAEP 选择密文证明的补全；不是本页封面。

延伸阅读

正文中引用本条 · 7