0HAL编号：tel-018312700https://theses.hal.science/tel-018312700提交日期：2018年7月5日0HAL是一个多学科开放获取档案库，用于存储和传播科学研究文档，无论其是否已发表。这些文档可以来自法国或国外的教育和研究机构，也可以来自公共或私人研究中心。0HAL多学科开放获取档案库，旨在存储和传播法国或国外的教育和研究机构、公共或私人实验室发表或未发表的研究级科学文献。0公钥密码学和计算机攻击的进展0Rémi Géraud0引用此版本：0RémiGéraud。公钥密码学和计算机攻击的进展。密码学与安全[cs.CR]。巴黎科学与文学研究大学，2017年。英文。�NNT：2017PSLEE057�。�tel- 01831270�0博士论文0巴黎科学与文学研究大学0巴黎科学与文学研究大学0在巴黎高等师范学校准备0由Rémi Géraud支持02017年9月5日0由David Naccache指导0公钥密码学和计算机攻击的进展0巴黎中心数学科学学院第386号博士学位0计算机专业0评审委员会成员0M. David POINTCHEVAL，巴黎高等师范学校，考官0M. Bart P RENEEL，鲁汶大学，评委0M. Ron R IVEST，麻省理工学院，考官0M. Amit SAHAI，加利福尼亚大学洛杉矶分校，考官0M. Jacques STERN，巴黎高等师范学校，考官0M. Serge VAUDENAY，洛桑联邦理工学院，考官0M. Moti YUNG，哥伦比亚大学和Snapchat，评委，评审委员会主席0摘要。信息安全依赖于硬件、操作系统、算法和通信网络等多个抽象层的正确交互。然而，保护这些元素是有成本的；因此，许多设备没有得到充分的保护。本论文从安全和密码学的角度讨论了这些不同方面。我们描述了新的密码算法（如Naccache-Stern加密方案的改进），新的协议（包括零知识分布式身份验证算法），改进的算法（包括新的纠错码和高效的整数乘法算法），以及与信息安全和入侵相关的多个系统性贡献。此外，其中几个贡献还涉及现有构造和本论文中引入的构造的性能改进。0摘要。信息安全依赖于硬件、操作系统、算法和网络等多个抽象层的正确交互。然而，保护技术堆栈的每个组件都有成本；因此，许多设备没有得到保护或保护不足。本论文从安全和密码学的角度讨论了其中的几个方面。为此，我们引入了新的密码算法（如Naccache-Stern加密方案的扩展），新的协议（包括分布式零知识身份验证协议），改进的算法（包括新的纠错码和高效的整数乘法算法），以及与信息安全和网络入侵相关的几个贡献。此外，其中几个贡献还涉及现有和新引入的构造的性能。v0前言0这篇论文汇集了我在过去两年半中的一部分工作。它探讨了许多主题，从最概念性的到最具体的。我认为这反映了我对安全性的立场：它本身是一个不断变化的目标，横跨边界。它与其说是珠宝，不如说是建筑。无论读者的背景如何，他们都希望能够享受到这个选择的多样性。因此，这个文件不是一个逐渐增加难度的长篇专著，而是展现了研究的根茎性质——一个潜在的主题，与其他终身的迷恋相联系——从中发芽出意想不到的创意。我希望读者能分享这种兴奋和惊喜的感觉，以及对更多知识的渴望！这项工作关注的是优化性，即作为协议、硬件和算法设计的指导原则。具体来说，目标是从文档、计算机和网络中提取最大的价值。最小化对内存、计算、复杂性、可信第三方和组件的需求；最大化速度、安全性和效率；设计最佳的攻击、最紧凑的协议等。这种方法的动机很简单：只有当使用技术的风险与带来的好处相比微不足道时，技术才会被使用。在过去的十年里，有几个现象迫使我们重新评估风险估计。一方面，攻击者在破坏安全性方面的技能和坚持性越来越高，不仅针对高价值目标，还针对技术的广大用户。另一方面，消费趋势转向轻便、移动设备上，对此类设备的保护昂贵、笨重、难以操作，因此很少使用且功能有限。如果还有第三个方面，我们可以加上政府机构越来越常见和深入地侵犯人们的私人领域，有时几乎没有监督，原因往往只能留给猜测和傲慢，通过篡改标准、通信渠道、硬件和软件组件。这就是为什么我们需要更强大的保护措施，这些措施易于实施、解释和分析。这些保护措施不依赖于（可能被感染或不可靠的）可信方，能够抵抗网络拦截，并适应手机、手表或任何我们决定随身携带的类似物品。优化性也是一种超越攻击者的方式，通过在他们之前找到最佳攻击，并设计出对未知攻击具有鲁棒性的系统。本论文中所呈现的大部分内容都是作为单独的文章发表的；我们选择保留这种格式有两个原因：它紧凑，避免了需要在整个手稿上来回阅读；而且它已经经过同行评审。本文档中的一些材料并不来自已发表的文章，有些工作根本没有出现，比如我在2016年3月获得微软安全研究员奖的努力，以及我研究的大部分专利成果。0没有努力去实现页数的质数。01 仔细的读者会在这篇论文中发现至少8种语言的痕迹，还有至少9种编程语言的提及，甚至还有更多。2请参阅https://technet.microsoft.com/en-us/security/cc308575.aspx。⊃⊃×⋆∩▽⊗⊙≥⊃⊃⊐±÷ ⋆⋆∩△△▽▽⊗⊗⊙>+=ABC D EFG HIJKL M N O P Q RST U V W XYZ•?!± ∓ × ÷ ⋆†‡∩ ∪ ⊓ ⊔ ∨ ∧ △ ▽ ⊕ ⊖ ⊗ ⊘ ⊙ ̸= < > ≤ ≥ ⊂ ⊃ ⊏ ⊐0Γνώμων0vinam-šeš nam-dub3-sa i3 li-gin7 i-im-bal-bal-e-ne30致谢/Remerciements0我要非常感谢很多人：因此这些感谢将是众多的，而且是双语的。0首先，我要衷心感谢我的导师DavidNaccache。你在接受指导我的时候做了一个赌注，你知道迄今为止的旅程是多么曲折和不确定；我从未见过一个人如此深深地决心给予他人，具有无与伦比的幽默感和无限的胸怀。感谢你的信任和支持（在科学和非科学领域），感谢你的建议和为我打开的许多机会。感谢你的耐心，感谢我们一起熬夜吃寿司，你的鼓励，你的可用性，以及与我分享让人活400岁的秘密。我在科学、文化和人性方面都学到了很多，我希望能够回报你所给予的至少同样多。0我还要感谢评审委员会：David Pointcheval、Bart Preneel、Ron Rivest、Amit Sahai、Jacques Stern、SergeVaudenay和MotiYung，尽管你们的时间表非常忙碌，但还是愿意评估我的论文，这对我来说是一种荣幸；你们的工作和奉献精神是我的榜样。0科学工作从来都不是一个孤独的努力；我要感谢所有与我合作的合著者，无论是在科学领域还是其他领域：EhsanAerabi、Antoine Amarilli、A. Elhadi Amirouche、Arash Atashpendar、Feng Bao、Hadrien Barral、FabriceBenhamouda、Marc Beunardeau、Éric Brier、Romain Campigotto、Noémie Cartier、Jean-Michel Cioranesco、SimonCogliani、Aisling Connolly、Jean-Sébastien Coron、Nathanaël Courant、Alix Desforges、Frédérick Douzet、HoudaFerradi、Éric Freyssinet、Aude Géry、Florentin Guth、Kavé Salamatian、Mirko Koscina、Georges-Axel Jaloyan、PaulLenczner、Tancrède Lepoint、Kévin Limonier、Diana Maimuţ、David Mestel、Matthias Minihold、DavidNaccache、David Pointcheval、Rodrigo Portella do Canto、Tomas Rigaux、Jérémy Robine、A. W. “Bill”Roscoe、Răzvan Roşie、Martin Ru�el、Peter Y. A. Ryan、David Saulpic、Emil Simion、Assia Tria、DamienVergnaud、Jean Vuillemin、Guilin Wang、Amaury de Wargny、Hang Zhou、Lionel Zoubritzky。0巴黎高等师范学校是一个非常好的学习地方。我与（前）博士生、博士后和研究人员度过了很多美好的时光，特别是在会议期间。感谢Pooya、Georg、Hoeteck（在维也纳共进晚餐）；Fabrice、Florian、Geoffroy、Rafael、Pierrick（没有他们，保加利亚、奥地利和圣塔芭芭拉将不会是一样的）；Adrian、Alain、Pierre-Alain、Romain、Raphael、Răzvan；Céline、Michel、Damien和David，以及所有其他人对我的热情接待。我还要向安全小组的同事们致以问候，Marc、Jérémie、Simon、Aisling、Chanez、Petra、Thibaut、Mirko、Maxime、Marc、Diana、Roman、Houda、Rodrigo。0我还要感谢那些在科学之外与我共度冒险时光的人：Daniel J. Berstein、Geoffroy Couteau、CarlEllison、Becca Kreuter、Tanja Lange、Kristin Lauter、Christof Paar、Tom Roeder、Mike Rosulek和EranTromer（一起在舞台上表演）；Yuval Yarom（愿意与我一起爬上北极附近一座黑暗而荒凉的煤矿）；Eloi deCherisey、Benjamin Wesolowski和Sonia Bogos（其中一些人吃过鲸肉，给我启发性的讨论）；FabriceMouhartem和里昂的同事们（我们一起去河内等地游览）。0我想再次感谢Castex网络战略主席团队的合作和非常有益的讨论。感谢ANSSI邀请我展示我的一些工作。03 “They pour out brotherhood and friendship like best oil” /‘他们像最好的油一样倾泻出兄弟情谊和友谊’。来自公元前3千年的《冬季与夏季之争辩》[KB93，第481-483页]。0viiMerci à Hervé et Hélène, pour leur amitié, nos animés et imbibés dîners, et pour m’avoir hébergé dansles temps durs. Merci à Claire, David, Isabelle et Iain, Fabrice et Aurélie, Annie et Paul pour des momentschaleureux de Lyon à Sarlat à l’île de Ré ; Thank you, Mange tak, Tapadh leat Marjun and John, Vivianand Graham, and the extended Scottish and Faroese clan, for their welcoming me to Insch, Edinburghand Aberdeen! Je tiens évidemment à remercier toute ma famille, pour leur confiance, leur soutien, leursencouragements, sans sans cesse renouvelés durant toutes ces années ! C’est grâce à vous tous que j’ensuis ici aujourd’hui. And Claire, who has kept amazing me since La Montagne many years ago: you makeme the luckiest person ever to walk the Earth, and this victory is also yours!viii0在格勒内尔的他们的网站上。我要感谢邀请我参加关于后量子密码学的北约研讨会的组织者。我要感谢邀请我在吉隆坡发表演讲的Mycrypt2016会议的组织者。感谢2015年和2016年在波尔多大学举办的国防安全网络夏季学校的组织者，他们邀请我在一个如此多样的观众面前展示我的想法，特别是与Sebastien-Yves Laurent，Laurent Oudot和ElenaPoincet以及ThierryLafon的讨论。感谢法国文化频道给我一个机会（虽然很快！）来谈谈我的研究意义，感谢法国24频道多次给我机会在直播中表达我的观点：这样我就完成了所承诺的15分钟的荣耀。此外，还要感谢Wired的AndyGreenberg与我们讨论并报道我们在欺诈支付卡方面的工作。0我有幸在一些著名的机构教授了许多学生：0•在巴黎中央理工学院，CentraleSupélec（自2014年起）和巴黎高等师范学校（自2016年起），作为我的信息安全课程的一部分（我无法感谢Alexis Benoist给我机会将爱好变成一个完整的学期课程！）；0•在巴黎高等师范学校（2017年），我在密码学教程中分享了我对Boyd，Groth和Schnorr签名的解构和改进的热情；0• 在CentraleSupélec（2017年），我在高级代数课程中进行讲座和教程；0• 在巴黎第一大学-潘捷-索邦大学（2016年），我教授了高级编程课程，试图将数学金融和高性能计算结合起来；0• 在南锡大学（2015年），我教授了我的统计学入门课程。0我还要感谢我作为私人教师教授的学生们，他们学习数学，物理，计算机，哲学，文学和音乐。最后，感谢所有曾经向我请教过某些事情的人，从量子力学到减五度的和弦：每个人，以及大家一起，都使我成为一个更好的教育者，并在我心中保持了对教育的热情。0基础研究不一定是抽象的与现实脱节的；我很幸运地看到我的一些研究成果得以通过工业合作伙伴的敏锐洞察力转化为具体产品：华为技术有限公司，Tanker和我的现任雇主Ingenico集团。给我如此自由的机会是一个大胆的举动，我希望我的研究成果能够鼓励Ingenico（和其他公司）在工业研究的核心加强学术卓越。0我的同事们，经常是我的合著者，值得一个奖项，因为他们耐心地听我讲笑话，八卦，狂吃。还有一个奖项是为了他们的参与。Marc Beunardeau，David Naccache，Aisling Connolly，Hiba Koudoussi：谢谢，�������，go raibhmaith agat，sahit！我还要感谢ÉricBrier，我们进行数学讨论，通过电话经常讨论Gröbner基，李代数和交换图表，总是很愉快。还要感谢IngenicoLabs的所有同事们，为生动和充满活力的氛围；我还要向Ingenico的团队（在法国，意大利，比利时和荷兰）表示感谢，他们欢迎我并对我的工作表示兴趣。还要感谢我有幸指导的年轻实习生们，祝愿他们有着光明的职业生涯：Mounira Hadjoudj，Louis Hauseux，Marius Lombard-Platet，Pauline Séchet，Amaury deWargny。特别感谢我善意的校对者：Răzvan（mulţumesc！）和Claire。ContentsPreface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .vAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .viiIIntroduction11Preliminaries31.1A brief prelude. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31.2Secret-key cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.3Public-key cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.4Hard problems and parameters choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . .151.5Adversaries and security notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .322Results and contributions372.1Organisation of this thesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .372.2Personal bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38II Cryptographic Primitives and Protocols433Identification and authentication453.1Distributed zero-knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .473.2Zero knowledge with colliding commitments: Slow-motion zero-knowledge . . . . . . . . .553.3Non-uniform zero-knowledge: Thrifty zero-knowledge. . . . . . . . . . . . . . . . . . . .664Digital signatures and integrity734.1Universal witness signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .754.2Legally fair contract signing without keystones . . . . . . . . . . . . . . . . . . . . . . . . .984.4Attestations for RSA prime generation algorithms . . . . . . . . . . . . . . . . . . . . . . . 1275.1Exploring Naccache-Stern knapsack encryption. . . . . . . . . . . . . . . . . . . . . . . . 1415.3Public-key cryptosystems from signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1595.5Human public-key encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172III Hardware and software security1916Side channels: Attacks and countermeasures1936.1When organized crime applies academic results . . . . . . . . . . . . . . . . . . . . . . . . 1956.2The conjoined microprocessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2136.3Process table covert channels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223ix04.3 在Schnorr签名中重用nonce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11305 公钥加密 13905.2 混合基数Naccache-Stern加密 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15305.4 Mersenne低汉明比例假设的困难性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16605.6 语言的蜜蜂加密 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1797Exploitation2297.1ARMv8 shellcodes from ‘A’ to ‘Z’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2317.2Control-flow obfuscation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2487.3Where there is Power there is Resistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2597.4Optimal botnet attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275IV Algorithms2918New building blocks2938.1Community-serving proofs of work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2958.2Optimal batch signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3098.3Multilinear maps with polylog complexity. . . . . . . . . . . . . . . . . . . . . . . . . . . 3279Improving building blocks3559.1Backtracking-assisted multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3579.2A Micali-Shamir implementation note . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3639.3Double-speed Barrett moduli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3679.4Applying cryptographic techniques to error correction . . . . . . . . . . . . . . . . . . . . . 3779.5Regulating the pace of von Neumann correctors . . . . . . . . . . . . . . . . . . . . . . . . 38810 Mathematical results39710.1 A number-theoretic error-correcting code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39810.2 High-rank elliptic curves and applications to cryptography. . . . . . . . . . . . . . . . . . 40510.3 Improving Laguerre’s theorem on locating a polynomial’s roots . . . . . . . . . . . . . . . . 410V Appendices413AHistorical cryptography415A.1A French code from the late 19th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415BSource code423B.1Implementation of the Thrifty Fiat-Shamir identification protocol. . . . . . . . . . . . . . 423B.2Implementation of the backtracking-assisted multiplication algorithm . . . . . . . . . . . . 425B.3Implementation of the von Neumann regulator. . . . . . . . . . . . . . . . . . . . . . . . 427B.4Implementation of the polynomial Barrett reduction algorithm . . . . . . . . . . . . . . . . 428B.5Implementation of the Micali-Shamir protocol . . . . . . . . . . . . . . . . . . . . . . . . . 431Bibliography433xPart IIntroduction1Chapter 1PreliminariesContents1.1A brief prelude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31.2Secret-key cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.2.1At the origins of cryptology . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.2.2Block and stream ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61.2.3Hash functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71.3Public-key cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.3.1Key exchange protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .101.3.2Digital signature schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111.3.3Identification or proof protocols. . . . . . . . . . . . . . . . . . . . . . . . . .121.3.4Encryption schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131.4Hard problems and parameters choices . . . . . . . . . . . . . . . . . . . . . . . . . . .151.4.1Discrete logarithm algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . .151.4.3Additional attacks on RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . .261.4.5Other hard problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .271.5.1Security games. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32This chapter sets the context for the topics discussed in this thesis: the motivations of this work, choicesmade in terms of models and approaches.While it is not the subject of this thesis to recall the long and convoluted history of Cryptology1,2, itis important that our discussion starts with the pioneering work of Claude Shannon. Shannon gave in1948 the first precise and quantitative definition of information as information entropy3 — a conceptmeasuring uncertainty, originally borrowed from Physics: a message bringing unexpected news carriesmuch information, whereas a message that is completely predictable carries no information. In essence,for Shannon, Information measures the amount of surprise caused by receiving a given message.301.4.2 因式分解算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2001.4.4 量子算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2701.5 对手和安全概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3201.5.2 安全模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3501.1 简短的序言01 对于感兴趣的读者，强烈建议参考DavidKahn的专著[Kah67]，该书涵盖了该主题的大部分内容，直到20世纪60年代末，但不包括Enigma。该书的最新版本还讨论了一些后来的发现，如RSA。2 这个术语的英文来源于法语，由两部分组成：crypto-，来自古希腊形容词κρυπτός < PIE *kreh 2u-“隐藏”；以及后缀-logia，来自古希腊λογία，表示“我说，我收集”的抽象修饰词λέγω < PIE *le ´g-“我收集”。因此，密码学是对（隐藏的）研究的研究。3 Shannon还在同一篇文章[Sha48]中引入了“比特”一词，用来表示信息的单位。Measuring information enabled Shannon to prove, for the first time, the security of a cryptographicsystem: it suffices to show that an adversary learns no information when eavesdropping. The ability toprovide mathematical security guarantees is at the heart of modern cryptology and distinguishes its toolsand methods from earlier approaches. We recall this result in modern language in Section 1.5.Incidentally, Shannon had met during his training as a cryptographer a young British mathematiciannamed Alan Turing. Amongst the t
我的内容管理
展开
