葱一根 - one sat on Nostr: 量子计算如何打破当今的密码学？ ...

量子计算如何打破当今的密码学？
本章涵盖了量子计算如何能够打破传统公钥加密的大多数形式。我们从讨论密码学基础知识开始，特别关注当今大多数公钥加密方案如何提供保护。然后，你将建立在第2章的基础上，学习量子计算机如何打破这种保护，以及什么密码学是或不太容易受到量子破解的影响。
密码学基础
密码学是保护和验证授权方之间的人员、数据、交易和其他对象的科学、研究和实践。它是通过使用加密、完整性检查和算法实现来完成的。密码学允许在授权的、指定的各方（或代表他们的软件或设备）之间随时维护数据、通信和参与者的机密性和完整性。本节将介绍数字加密、身份验证和完整性散列的基础知识。
附注：本章通篇都将使用“主体”一词。它是用来指任何身份，可以绑定到一个加密动作。主体可以是用户组、计算机、设备、服务、守护程序、公司、发布者或任何其他标识对象。
加密
加密是受试者保守秘密的一种常用方法。单个主体可能希望对自己保密，或者该秘密可能在选定的一组人或设备之间共享。秘密可以是任何类型的内容、参与方的身份以及任何涉及的事务和对象。
各种形式的加密已经使用了数千年，从口头密码和编码的文字开始。一个常见的例子是简单替换密码，其中字母表的字母和数字被重新排列，以创建一个编码的消息，只有预期的当事人理解。在其最简单的应用中，使用替换密码的各方可以同意将未加密消息的每个字符在字母表中向前移动一个字母，以编码和加密消息。因此， FROG 一词将成为 GSPH （ F +）1 个转发字母的位置= G ， R + 1 = S ， O +1= P ，和 G + 1 为 H ）。所有涉及授权接收者将需要被告知，所产生的编码的消息可以通过颠倒的过程解码（即， G - 1 = F ， S - 1 ＝ R ， P - 1 ＋ O ，和 H － 1 ＝ G ）。有关图形示例，请参见图3.1。
[插图]
图3.1一种简单的替换密码
原始的、未编码的消息称为明文消息。被编码的消息被称为加密消息，或密文。将明文文本消息转换为加密形式的过程称为加密。将加密消息还原为原始明文消息形式的过程称为解密。用于加密或解密消息的文档化过程和步骤通常称为密码或密码算法。
注意：在计算机世界中，消息可以是任何类型的数字内容，包括文本、电子邮件、聊天消息、数据、声音、图片和视频。
每个密码本质上都是前面简单替换示例中介绍的基本加密组件的更复杂的实现。总有一个明文消息是使用密码算法进行编码和解码的。在前面的简单替换方法中，密码算法在数学上表示为+ X 或- X （即+或- x ，或+- X ），其中 X 是字母表中为加密或解密而向前或向后移动的位置数。
+或-是（简单的）密码算法。X是密钥。在今天的世界中，密码算法是使用从相当简单到复杂的数学方程表示的。一些密码算法是由使用传统数学运算（如加、减、乘、除）的数学方程组成的。其他人使用三角学、微积分和其他更高级的数学运算。在任何情况下，如果提供了可靠的算法和密钥，密码算法都允许以可预测的方式对明文文本消息进行加密和解密。
随着无线和无线电通信的出现，模拟传输波本身被编码，以防止意外窃听。当计算机开始普遍使用时，数字加密被用来保护敏感的数字通信。正如第二章“量子计算机简介”所述，传统的二进制计算机使用位（0和1的二进制数字）。所有数字数据和对象在经典计算机上都以0和1的形式存储。当加密是必要的，这些位被重新安排在一个预定的，算法的方式，以提供加密晦涩。
注：密码的另一个术语是密码原语。
加密密钥
如前所述，在我们的简单替换示例中，密码算法表示为+- X ，其中X是向前或向后移动的位置数。X是密钥，它是用于使用密码算法加密消息的比特数。稍微复杂一些简单替换示例可能是使用键１２。在这种情况下，FROG这个词变成了RDAS(F+12=R，R+12=D，O+12=A，G+12=S)。密码是一样的，但密钥变了。如果密码很强，并且密钥足够长，它可以是非平凡的。（这是一种非常非常困难的加密语言……或者“您可能一辈子都做不到”），以防未经授权的一方在不知道密钥的情况下解密受保护的消息。
附注：有了好的密码学，使用强而可靠的密码，每个人都可以知道密码算法的细节。密码学的强度来自于算法转换过程的强度和足够长的密钥。密钥必须对未经授权的人保密，但密码不能。大多数观察者通常认为，要求密码也要保密的加密解决方案是可疑的，而且可能是脆弱的。
在所有其他条件相同的情况下，密钥的保护随着其长度的增加而增加。随着密钥长度的增加，未经授权的一方将受保护的加密消息转换回明文状态变得更加困难，即使他们知道密码算法也是如此。在我们简单的替换例子中，即使是一个孩子也很容易理解如何计算和加减一个额外的（+- 1 ）。对信息进行编码和解码的字母位置，甚至可以加上或减去 12 个（+- 12 ）变化的位置。但是如果我们的密钥突然变成了+- 1 , 234 ， 567 ， 980 ，改变了字母表中的位置，那么这个答案对于普通人来说就更难计算了（尽管不是不可能）。
在传统的计算机世界中，数字加密密钥只是一长串看似随机生成的1和0。数字密钥看起来有点像101010101101000101010101100111001010101。根据密码算法将数字密钥应用于明文消息，产生加密消息。如果操作正确，密钥和加密的消息看起来就像是一组随机的不可预知的比特。
今天，数字加密密钥的大小通常从128位到4,096位不等，但在不太常见的情况下，它们可以更小或更大。特定长度的位是否被认为是安全的，取决于许多因素，包括所涉及的密码算法，所有可能的关键位位置（称为密钥空间）可以被猜测的速度，以及任何可以用来减少暴力猜测方法的“技巧”。较难“破解”的强密码算法可以使用较小的密钥位长度，而相反，较弱的算法通常需要较长的密钥长度来获得相同的保护时间。使用相同算法的新密钥的位长度往往会随着时间的推移而增长，以补偿更大的计算能力和其他破解因素。密码攻击只会随着时间的推移而变得更强，这会削弱密钥长度所提供的保护能力。
通过在任何计算机或设备上打开数字证书，您可以很容易地找到和查看密码密钥示例。图3.2显示了从数字证书中提取的2048位密钥。
[插图]
图3.2：来自数字证书的2048位密码密钥
注意：在大多数计算机和设备上，几乎所有的数字加密密钥都被转换为十六进制表示（例如，基数为16的编号系统），而不是它们的底层比特（即1和0）。
您可以访问www.keylength.com/查看常用加密算法的推荐最小密钥长度。加密算法通常分为两种主要类型:对称和非对称。

对称密码

如果密码算法使用相同的密钥对消息进行加密和解密，则称为对称密码。例如，在前面的简单替换示例中，用于加密明文消息的密钥（例如，1、2或1,234，567，980）与用于将加密消息加密或解密回其原始形式的密钥相同。
在同等条件下，对称密码比非对称密码（本章后面将介绍）更强、更快、更容易验证，并且它们需要更小的密钥长度。从密码学的观点来看，好的对称密码更容易被证明是强而可靠的。它们的数学没那么复杂。它们需要较少的假设和猜测。它们更难攻击。因此，对称密码完成了世界上大部分的数据加密。
自20世纪70年代以来，世界上使用了许多不同的对称密码标准，包括数据加密标准（DES）、三重DES（3DES）、国际数据加密算法（IDEA）和Rivest Cipher 5（RC5）。所有这些较旧的对称密码在今天看来被认为是弱的和不好的。
自2001年以来，最流行的对称密码被称为高级加密标准（AES）。根据需要，国家标准和技术研究所（www.nist.gov）定期举行公开竞赛，选择新的加密密码标准，以取代老化和削弱的密码算法。在aes竞赛中，超过12个不同的团队向nist提交了他们的对称密码，以作为新的国家对称密码标准。在一个相当开放和慎重的过程中，NIST选择了一种名为Rijndael的密码，并将其重命名为高级加密标准。目前，AES使用128位、192位和256位长度的密钥大小，它的强度在多年的密码审查和攻击下一直保持得很好。
附注：只为单个主体所知并由单个主体使用，且不与其他任何人故意共享的密钥称为私有密钥或秘密密钥。有意在多个主体之间共享的密钥称为共享密钥。任何人都可以知道并使用的密钥称为公钥。创建仅用于临时使用的密钥称为会话密钥。

对称密码的弱点

这并不是说对称密码没有它们的弱点和缺点。是的。常见的对称密码弱点包括缺乏认证能力和密钥交换缩放问题。
由于使用相同的密钥对消息进行加密和解密，因此访问该密钥的任何一方都可以对消息进行加密和解密，并且可能假装是具有相同密钥的任何其他相关方。从纯密码学的角度来看，如果有人指控其他参与方之一加密了某些东西，因为每个人都共享相同的对称密钥，被指控方不能（再次从密码学的角度来看）否认指控。这就是所谓的不可抵赖性。在密码学领域，这不是一个令人向往的特质。
这也意味着，由于同样的原因，对称密钥本身在大多数身份验证场景中更难使用，特别是在需要数据完整性或主题身份验证的情况下。例如，假设Fred、Wilma和Dino共享相同的加密密钥。Fred可以加密一些数据并将其发送给Wilma，但声称它来自或最初由Dinumber创建和加密，因为每个人都共享相同的密钥，从纯密码学的角度来看，Dino无法证明谁真正发送或加密了它。Fred甚至可以把Wilma发送的加密信息解密，恶意修改，再加密，然后发送给Dino，声称是Wilma发送的。Dino没有办法说清楚消息来自谁，也没有办法得知原始消息在解密之前是否被篡改。
第二个大问题是，随着共享参与者数量的增长，对称密码就不容易使用了。在一个小组中，比如两个或三个人，安全地交换共享对称密钥相对容易，尽管如此，所有参与方都需要确保共享密钥准确、安全地传达给所有参与者。任何两个人都很难准确地读、写或说256位密钥。就像我们很多人都很难将16位数的信用卡号码传达给另一个人。
假设你有一个共享对称密钥的场景，有一千个参与者。一个或多个参与者必须找到一种方法，将商定的密钥安全地传输给所有其他授权方。会怎么做：写信、打电话、发电子邮件等？如果使用书面形式，如何将书面形式安全地发送给其他当事人？邮件系统和它的工作人员可以信任吗？是否可以保证只有预期的收件人在另一端打开邮寄的邮件？如果使用呼叫，电话系统的可信度如何？有没有可能有人在偷听？可能吧。如果接收方不在，发送方该怎么办？他们会把密钥留在语音信箱吗如果接收者真的听到了密钥的内容，他们能准确地转录出来吗？如果使用电子邮件，电子邮件系统以及发送者和接收者之间的所有中转点的可信度如何？在任何电子邮件系统中，都有一个或多个电子邮件管理员可以读取其他人的电子邮件。在任何情况下，无论如何通信，你能想象一千个不同的人试图安全和准确地共享一个256位对称密钥，而不犯一个错误吗？所以，安全地交换共享的对称密钥的难度，随着参与者的数量呈指数级增长。
现在假设这一千个参与者中的一些人想要额外的、更小的组，他们为每个子组使用不同的共享密钥。他们将负责跟踪哪些人和团体使用了哪些密钥。更进一步，假设每个参与的用户都需要在各方之间保证加密，而其他人或各方都无法看到。这将要求这一千个参与者中的每一个都有一个单独的共享密钥，用于其他参与者的每一个可能的联合。每个希望向所有其他用户发送机密消息的用户将需要使用999个不同的对称密钥来发送消息，并跟踪哪些密钥属于哪些联合。这将需要499,500个（1,000个参与者×999个其他参与者/2）对称密钥。
显然，这将是一项繁重的工作，特别是如果参与者被要求定期更改密钥，以确保持续的、强有力的隐私，防止正在进行的攻击。几个世纪以来，哲学家和密码学家一直在寻找一种更好的方法来安全地交换私有信息和/或对称密钥（后者被称为密钥交换）。

非对称密码

加密的圣杯是找到一种方法，允许两个或两个以上的当事人通过不受信任的（甚至是故意恶意的）通信信道交换对称密钥，而不必事先建立一个私人通信方法来为每个参与者交换对称密钥。在20世纪70年代中期，几个不同的各方，在彼此不知情的情况下，在几年内开发出了几乎相同的解决方案。

整数分解工作负载工作量

所有的解决方案都使用了一个多项式数学问题（例如， A × B = C ），因为难以在内部解决各个组成部分（即因子）的问题，所以需要解决其工作量的问题，以进行保护。这道数学题需要很难分解，以至于万一有人得知了C（A×B的结果），没有人能轻易算出A或B。多项式工作负载工作量（也称为整数分解问题），是当今大多数公钥加密背后的核心保护。
附注：工作量的努力类似于整数分解，但在不同的，但相关类型的非对称密码，包括离散对数问题和椭圆曲线离散对数问题使用。它们使用不同类型的很难解决的数学，但它们采用的方法根本不同。
今天，最流行的非对称密码解决方案使用两个大素数（A和B），当它们相乘（或算法应用）时，会得到一个更大的结果（例如C）。在第二章中，素数是大于1的整数，它只能被自己和1整除（2、3、5、7、11、13、17、19、23等）。任何其它组合都得到余数或分数。质数对于传统的二进制计算机来说是很难按需创建和验证的。如果A和B的值是非常大的质数，即使有人知道C，他们也很难将结果分解回其基本的质数成分（即A和B）。
为了更好的解释，我们从一个简单的例子开始。让我们使用一个常见的密码学数学方程，它代表整数因式分解保护方法: p * q = n ，其中 p 和 q 是素数， n 是得到的数学结果，并且是密钥对的公钥（马上解释）如果p和q足够大，如果只给定n，p和q就很难计算出来。
对于我们最简单的例子，让我们假设 n = 15 。哪两个质数相乘得结果是15？这很容易算出来，特别是因为15以下的质数只有2、3、5、7、11和13。任何人都不会花太长时间来计算出 p 或 q 一定是 3 或 5 ，因为 3 × 5 = 15 ，没有其他素数的组合相乘等于 15 。
现在，让我们为这个问题增加一点复杂性。假设 n = 187 。哪两个质数相乘会得到187？现在，将187乘以两个相乘的质数所需的脑力在增长。普通人仍然可以弄清楚这个问题，但要做到这一点就不那么容易了。答案是 p 或 q 为 17 或 11 ，因为 17 × 11 = 187 。
但假设n=84773093，p和q是什么？现在我们说的是真正的脑力劳动。你必须算出84773093以下的所有质数，然后用不同的组合将它们相乘，看看哪一个结果是84773093。大多数人类无法迅速做到这一点。这是可以做到的，只是没有电脑不能很快完成。如果你感兴趣，答案是 p 或 q = 9539 或 8887 。计算机仍然可以非常快速地完成这一项。
但现在假设n等于4096位表示的数字。这个数字太大了，大多数计算器都显示不出来。它们将出错或显示一个无穷大符号。4096位数字是由1234位十进制数字表示的数字。它可以表示为24096—1可能的数字。用蛮力去猜测这么大的一个数字是不可能的任务，更不用说实际上算出两个超级巨大的素数相乘在一起会构成这个数字的结果。
当密码学家试图解释需要多少次暴力破解才能猜出正确的两个素数来生成一个4096位的数字时，他们开始创造滑稽可笑的比较，因为这是唯一可能向普通人传达因式分解超级巨大素数有多么困难的方法。一个4096位数的所有可能性都超过了已知宇宙中的所有原子。从整体上看，在这句话的结尾，有超过1.25亿个原子。另一个比较是，如果你有100万的东西，比如说硬币，代表宇宙中的每一颗恒星，在我们宇宙的10万亿个星系中，每一个星系都有1000亿颗恒星，你的硬币也只够代表一个4096位数的百分之一，更不用说算出用来创造4096位数的两个更大的质数了。
一些天真的观察家认为，新的数字这么大，我们所需要的是更多的计算能力，也许地球上所有的计算能力都能做到这一点？他们错了。不仅整个世界现在和永远都没有足够的经典计算机、处理能力、内存和存储空间，而且如果他们想要尝试的话，也没有足够的能量来驱动这些项目-至少使用传统的经典二进制计算机不行。因此，分解大型素数方程所需的工作量（和时间），这种方法提供了保护。
注意：提供全数字密码保护是因为很难用蛮力从所有可能的组合中猜出密钥，也很难将某种数学公式分解回其原始组成部分。各种各样的密码创造者提出了一个数学问题，如果你没有它的某个部分，是不容易弄清楚的。你可能知道 A + B = C ，但即使你知道 A 和 C ，你也不容易算出 B 。求解未知值的困难是赋予密码保护能力的原因。

公私密钥对

这种使用大素数的非对称加密方法，每个参与方生成（或被给予）一个密钥对，其中这对密钥中的两个密钥是彼此相关的。有一个密钥是私有的，不与其他任何人共享（私钥）。另一个密钥可以分发给整个世界（称为公钥）。一个密钥加密的任何东西，另一个可以解密，反之亦然。这对非对称加密的概念和它能做的一切都非常重要，所以如果你想理解非对称加密，你必须理解这两点。因为一个密钥用于加密，而另一个密钥用于解密，所以这种类型的密码称为非对称密码。
即使密钥对的两个密钥都可用于加密发送给对方的消息，反之亦然，谁拥有私钥和公钥分类的性质也很重要。请记住，私钥不会与其他任何人共享。正因为如此，如果有人想向另一个人发送机密消息，他们必须使用那个人的公钥来加密消息。这将保持消息的机密性，直到接收者使用他们的相关私钥解密它。由于没有其他人拥有接收者的私钥，因此没有其他人可以解密该消息。
注意：使用非对称加密，我们必须使用接收方的公钥来加密发送给他们的消息。
使用非对称加密，每个参与方需要自己的私有-公共密钥对，但每个人只有一个密钥对来安全地相互通信。一个非对称系统不需要499,500个不同的对称密钥来安全地相互通信，而只需要1,000个私有-公共密钥对（或总共2,000个密钥）。

数字签名  

非对称密码系统的用户也可以使用他们的密钥对，对内容进行身份验证和数字签名。数字签名是提供签名内容仍与签名时相同的证据的行为。要对内容签名，用户需要使用私钥“加密”内容（或一个散列结果，稍后介绍）。尽管我们并不真的称这个过程为“加密”，因为任何拥有相关公钥的人（理论上可以是整个世界）都可以解密和读取它。如果全世界的人都能看到，就不能认为是机密或加密的。
相反，我们称之为数字签名。由私钥签名的任何内容只能通过使用相关的公钥来显示。如果内容可以被相关公钥验证（“解密”），那么它一定是由相关私钥签名的，因为相关公钥唯一可以“解密”的是由相关私钥签名的东西。类似的过程可用于验证密码操作中涉及的用户身份，本章后面将介绍其中的一些操作。常用的数字签名密码有：数字签名算法（DSA）和椭圆曲线DSA（ECDSA）。
如果需要这两种保护，则可以对消息进行加密和签名。如果Fred需要向Wilma发送一个经过签名和加密的消息，那么他使用自己的私钥对消息进行签名，然后使用Wilma的公钥对其进行加密。
注：数字签名和验证比前面描述的要复杂一些。我们稍后会讲到。
由于每一方都有自己唯一的密钥对，并且只有该密钥对才能对彼此之间的消息进行加密和解密，因此非对称加密还允许对主体和消息进行身份验证。每个相关的密钥对可以绑定到一个特定的主体。这允许否认。

密钥交换

因为对称密钥在较小的密钥大小下更安全，所以它们被用于进行世界上大部分的消息加密，而非对称密码通常仅用于在双方之间安全地传输共享的对称密钥。非对称加密允许在不可信网络之间进行对称密钥交换，而无需事先建立安全、可信的通道。密钥交换过程的一个非常基本的总结，看起来与下面类似：
客户端和服务器端相互连接。
服务器向客户端发送其非对称密钥对中的服务器公钥。
客户端使用服务器的公钥将客户端新生成的“会话”对称密钥加密回服务器。
服务器和客户端现在都使用共享的会话对称密钥来相互发送加密内容。
在现实世界中，使用非对称密钥交换在客户端和服务器之间安全地传输一个共享的对称密钥要多一些步骤和复杂性（后面会介绍），但这是目前对非对称密钥交换基本步骤的一个很好的总结。
常见的非对称加密类型包括Rivest、Shamir、Adleman（RSA）、Diffie-Hellman（DH）、椭圆曲线加密（ECC）和ElGamal。RSA无疑是使用最普遍的非对称加密密码，可能占所有非对称密码使用的95%。虽然所有的非对称密码都用于执行密钥交换，但是Diffie-Hellman，也被称为Diffie-Hellman-Merkle，通常与仅用于密钥交换的实现相关联，使用较少的椭圆曲线Diffie Hellman(ECDH)也是如此。今天，RSA和DH密钥的大小通常在2048到4096位之间，并且它们的长度大约每7到10年就会增加一倍，以抵御不断发展的加密攻击。
注意：RSA安全公司，RSA密码背后的公司，过去一直提供现金奖励，，给破解越来越大的RSA密钥大小的密码学家。到目前为止，使用因式分解公开破解的最大RSA密钥是768位(https://eprint.iacr.org/2010/006.pdf),2010年完成。它涉及到一个232位的数字，很大，但并不像今天通常推荐的2048位或4096位密钥那么大。尽管如此，甚至在768位的密钥破解之前，RSA就停止提供比赛，没有任何解释。许多观察家认为即将到来的量子计算机的实现是一个主要因素（请原谅这个双关语）。

密钥信任和公钥基础设施

为了让非对称密码系统工作，与它们通信的人必须信任每个人的公钥是有效的，并且属于他们认为它属于的人。在早期的非对称密码通信中，一个人向另一个人发送他们已经知道的公钥就足够了，接收者会相信发送给他们的人是正确的，有效的，拥有正确的，有效的，相关的私钥的人。
但随着非对称信道中人数的增加，并非每个参与者都可能认识并信任其他所有参与者。获得对不认识的人的公钥信任的一种方法，是让您已经信任的人为另一个人作担保。例如，假设威尔玛想不对称地与迪诺沟通，但不知道或提前信任迪诺。但她知道弗雷德认识并信任迪诺，他可以为迪诺和迪诺的有效公钥做担保。Fred可以用自己的私钥签署Dino的公钥，然后Wilma可以使用Fred的公钥验证私钥。这就是所谓的对等信任（或网络信任）。这是非常流行的相当好的隐私（PGP）加密程序的工作原理。但是，对等信任系统并不像参与者数量规模那样有效，特别是在全球不对称系统中，大多数参与者彼此不认识。

公钥基础设施

公钥基础设施（PerkinElmer）是一个常用的加密框架和协议家族，用于在计算机世界中提供无关各方之间的身份信任。关于PerkinElmer是什么以及为什么需要它，您可能读到或听到过许多不同的描述，但就其基本要求而言，PerkinElmer主要用于验证加密事务中涉及的主体身份及其非对称密钥。如果没有这个要求，您就不需要PerkinElmer。
公钥基础设施向经过验证的主体颁发“数字证书”，这些证书是受密码保护的文件，证明主体身份及其相关的非对称密钥对的有效性。在实践中，主题（或代表它们的东西）生成一个非对称密钥对供主题使用。主体向PerkinElmer提交公钥（记住我们不共享私钥）。然后，PerkinElmer的证书颁发机构服务应该验证提交公钥的主体的身份。
PerkinElmer要求主体提供的身份证明级别决定了保证(或信任)的水平。珀金埃尔默（PerkinElmer）可以证明。如果证明级别非常低（比如只有一个有效的电子邮件地址），则认为所颁发的数字证书具有低保证。如果身份所有权和证据的级别很高，例如要求主体亲自到场，并将其出生证和国民身份证的有效副本交给另一个人工验证者进行验证，则可认为这种保证很高。
在任何情况下，PerkinElmer的主要工作都是验证提交公钥的主体的身份。如果验证了主体的身份，PerkinElmer将添加一些附加信息(如有效期日期、主题名称[S]、证书序列号以及验证局的名称和标识符)，并使用PerkinElmer的私钥对主体的公钥(和其他信息)进行签名。这将创建一个数字证书。图3.3显示了一个突出公钥字段的数字证书的部分示例。理论上，任何信任PerkinElmer（颁发特定数字证书的实体）的实体都将信任由PerkinElmer创建并由主题提供的任何数字证书。提供数字证书的主体实际上是在说，“我就是我所说的那个人，并且您信任的人验证了我的身份。”
[插图]
图3.3数字证书的详细信息
PerkinElmer可以比作美国的机动车辆管理局（DMV）。车管所执照持有人必须向车管所充分证明自己的身份，才能拿到驾驶执照。在驾驶员的身份被成功验证（确保）后，DMV将拍摄主体的照片，添加其他信息，并发出DMV许可证，与州徽一起密封（有点像现实世界的数字证书）。如果司机被执法部门阻止或去购买需要年龄验证的东西，他们往往会被要求出示他们的DMV许可证。官员和销售人员相信DMV许可证是准确的，因此将依靠在他们的核查过程中印在许可证上的信息。
互联网的大部分工作都有珀金埃尔默参与。每次您使用安全超文本传输协议（HTTPS）连接到网站时，该网站都有一个由受信任的PerkinElmer签署和颁发的HTTPS/TLS数字证书。您可能不信任PerkinElmer，但您的操作系统或相关软件确实信任PerkinElmer。当您通过浏览器使用HTTPS协议连接到网站时，网站会向您（或您的浏览器）发送其数字证书的副本。由PerkinElmer签名的数字证书证明了网站的名称（通常通过URL）、网站的公钥和其他相关的重要信息。一旦验证成功，您的浏览器将生成一个全新的共享会话对称密钥，然后安全地将其发送给网站（使用网站的公钥）。然后服务器和客户端都可以开始使用对称密钥通信安全地进行通信（见图3.4所示）。
[插图]
图3.4：Web服务器和客户端使用HTTPS和数字证书进行相互通信
在PerkinElmer使用的另一个流行示例中，当您从流行的供应商下载新软件时，该软件将附带一个数字证书，以验证谁签署了该软件（或相关的完整性散列在后面更详细地介绍），它允许下载器（或更实际地通常是代表他们的浏览器）验证软件自签名者签署软件或散列以来没有更改。软件在签名者和接收者之间的位置、是否通过可信或不可信的通道、涉及多少中间人或签名发生在多长时间以前（在合理范围内）都不重要。如果经过验证，数字证书和随附的验证散列告诉用户，他们可以依赖软件，因为它是签署的那一刻，是从它说谁签署了它。

非对称密码弱点

非对称密码允许在不受信任的信道上进行加密和密钥交换，并可用于进行身份验证。尽管量子计算机最近带来了迫在眉睫的威胁，但非对称密码已经相当好地经受住了几十年的密码攻击。但它们还是有问题。
最大的缺点是，非对称密码天生就比对称密码在数学上更复杂，而在计算机安全领域，复杂性往往是安全的敌人。大多数非对称密码使用两个密码学上相关的密钥，它们之间仅用一个被认为难以分解的数学方程来分隔。与对称密码相比，有一个增加的机会，有人会发现如何“快捷化数学”，并更快地因子基本的数学方程或素数。而现实表明这是真的（稍后将对此进行详细介绍）。在所有其他条件相同的情况下，非对称密钥通常比对称密钥长（但并非总是如此），并且随着时间的推移，非对称密钥的大小增加得更快、更多，以补偿密码攻击的进展。

完整性哈希

另一个重要的加密功能是完整性散列。散列算法（也称为散列函数或简称散列）用于为唯一的内容输入创建唯一的输出结果。它们使用“单向”加密函数，为检查的独特内容创建/输出一组独特的代表性字符或比特（称为散列、散列结果、数字签名或消息摘要）。散列函数创建散列内容的加密“数字指纹”。哈希函数可用于对内容、主题和其他加密对象的完整性进行加密签名和验证。
当完整性散列结果（通常简称为散列或消息摘要）与特定的加密主体身份（例如，用户、设备或服务）进行加密绑定时，它被称为数字签名。经验证的数字签名允许经签名的内容的接收者确信经签名的内容自经认证的签名者签名该内容以来未被改变。
安全、可信的散列函数有四个重要特性：
对于每个唯一的输入，必须生成一个唯一的输出结果。这种类型的保护被称为防碰撞。
每次对相同的输入进行散列处理时，都应该得到相同的散列输出。
任何两个不同的输入都不应该导致相同的散列输出。这种类型的保护被称为第二预像电阻。
如果给定了散列输出，任何人都应该很容易得到原始内容输入。这种类型的保护被正式称为预像电阻。
一个好的散列具有所有这些属性，即使在持续攻击下也能保留这些保护性散列功能。抗碰撞性与第二预像电阻相关且相似，但它们并不相同。两者都擅长并不能保证抗预像，因为它们是不相关的属性。如果散列容易受到这些属性中的任何一个属性的影响，它就被认为是弱的，不应该再使用。
散列算法通常会产生固定长度的散列结果，而与输入无关。常见的散列长度范围从128位到256位。多年来，已经有许多不同的被普遍接受的散列标准，包括消息摘要5（MD5）、Windows LANManager（LM）、Windows NT（NT）和安全散列算法-1(SHA-1). 所有这些以前的标准，除了NT，都被认为是薄弱和不完整的。
今天，最流行的散列算法是安全散列算法—2（SHA-2或SHA2）虽然在2015年NIST建议使用SHA-2的后继者安全散列算法-3（SHA-3或SHA3），因为随着时间的推移，SHA-2会因为加密攻击的改进而减弱。到目前为止，大多数人仍在使用SHA-2。SHA-2有许多不同的输出大小，包括224、384、256和512位。
表3.1显示了使用常见示例散列的单词“frog”的一些散列输出。
表3.1：单词“frog”的散列输出示例
散列弱点和非对称密码一样，散列算法也被认为有点神秘。他们似乎完成了他们想要做的工作，但没有人完全确信任何特定的散列算法都能满足上述四项要求，或者如果他们现在这样做了，要多久才会有人发现错误。以前的哈希标准在使用时也被认为是安全和强大的，直到随着时间的推移被各种密码攻击所削弱。密码学家发现哈希算法是最困难的密码函数，在准确地证明或反驳方面都是最难的。

密码使用

对称密码、非对称密码和完整性散列函数的主要加密函数，为计算机世界提供了广泛的服务，并延伸到现实世界。没有它们，大部分的互联网和现实世界，将是不可能的。常见的加密用途包括以下几种：
加密
证明
数字签名
HTTPS/TLS
加密货币
智能卡，虚拟智能卡
磁盘加密
网络加密
电子邮件加密
虚拟专用网
无线安全
代码和文档签名
隐写术
匿名
标记化
数据模糊/擦除
密码学保护世界上的网络、计算机、车辆、政府、货币和数字身份，并帮助验证和保护所有数字内容。一个没有好的、可靠的密码学的世界看起来更接近19世纪60年代，而不是20世纪60年代。对数字密码术的难以置信的依赖，就是为什么任何可以轻易地、突然地破解它的东西都会在全世界引起震动的原因。量子计算是当今最流行的数字密码学面临的最大威胁。
你可能想知道，任何一台计算机怎么能打破今天的密码学，特别是当我早些时候写到，在已知的宇宙中，甚至没有足够的能量来完成破解。好吧，那是在我们只有经典的二进制计算机的时候，并且仅仅依靠蛮力猜测来完成攻击。新的量子算法和真正的量子计算机的发明改变了这一切。

量子计算机如何破解密码

量子计算机由于其固有的量子特性(如叠加和纠缠)与量子算法相结合，能够突破传统密码学的许多形式，并利用这些特性简化了数学运算。量子计算机如何破解当今密码学的多种形式，是本节的重点。接下来将描述传统密码学量子计算机能破解和不能轻易破解的东西。

切割时间

有一句很流行的话，在这个世界上我们唯一找不回来的就是时间。这并不总是正确的，特别是在量子世界。我们喜欢和使用计算机的部分原因是它们能够非常快地完成某件事。然而，有许多潜在的解决方案，即使是最快的计算机也无法解决的问题。如前所述，许多加密数学问题都是如此。一台计算机，甚至是一个由数百万台非常快的计算机组成的网络，无法解决一些今天已知的数学问题，这就是今天依赖的密码学的保护能力。
这并不是说人类不去尝试。防御者和攻击者都试图提出问题和解决方案，试图缩短或延长做某事的正常时间。这些解决方案和问题按照它们对特定(最坏情况)解决方案与正常时间尺度的增减程度进行分类。
如果我们增加额外的资源来解决一个问题，例如更多的内存，更快的CPU，更多的硬盘空间，甚至更多的计算机，如果增加的结果没有更快的解决方案，我们称之为常数时间的解决方案。例如，如果一个人一天要做100个小部件，我们加了一个人，他一天还是只做100个小部件两者加在一起，额外的资源导致了一个恒定的时间解决方案。如果你想更快地解决问题，恒定时间的解决方案对你没有帮助，反而会适得其反。如果你试图防御一个攻击者，如果他们只有恒定时间攻击，这是一个好处。
如果增加资源可以加快解决方案的速度，对攻击者有利，对防御者不利。如果添加资源导致每个添加的个体生成相同数量的小部件，则称为线性时间（或直接时间）。例如，一个人做10个小部件，两个人做20个小部件，三个人做30个小部件（每个人只做10个小部件，但他们一起做更多的小部件）。
如果添加每一个额外的资源会使之前每个资源收集的速度增加一倍，这被称为指数时间。例如，一个人每天制作100个小部件，2个人做200个小部件，3个人做400个小部件，4个人做800个小部件等等。这就是二进制计算机(即2n)本质上的工作方式。每增加一位，就会使前一位的力量加倍(S)。任何资源的添加，无论是计算机资源或算法，能够比指数时间更快地完成解决方案，都被认为是对使用指数时间或更短时间进行防御的问题的威胁。
数学家和密码学家创造的问题和解决方案需要比指数时间多得多的工作量。时间尺度解被称为多项式、平方根、二次和阶乘，它们都是指数时间的巨大改进，被称为超指数时间尺度解。任何提供这些类型的时间解决方案改进的资源都是对依靠指数时间防御来保护自己的事物的威胁。特别是，任何超过指数时间的加密攻击都是对依赖指数时间保护的加密解决方案的威胁。量子比特和量子算法经常给出超显问题和解决方案。如果你读到一个密码问题或解决方案只在指数时间或更短的时间内工作，通常没有人关心。但是如果你读到一个在超指数时间尺度上工作的解决方案，特别是最快的方法之一，如阶乘，密码学世界的每个人都关心。这意味着增加每一个额外的资源比“正常的”、指数时间尺度的问题和解决方案带来了巨大的好处。
有关时间解决方案的详细信息，请参阅https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/和https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time.

量子算法

量子算法是依赖于量子理论和特性的一系列（数学）步骤，如果在量子设备上遵循这些步骤，将给出特定的结果。几十年来，量子计算机所能做的很多事情都只在理论论文中描述过。有了实际的、可工作的量子计算机和设备来进行试验，理论量子力学的世界就进入了现实世界。
有了一台工作中的量子计算机，科学家们可以用一个特定的量子算法解决一个问题，应用这个算法，并观察结果。大多数量子算法被认为是革命性的，因为它们在速度上比传统计算机快，或者它们可以回答曾经被认为无法解决的问题。最终，今天的许多密码学可以被量子特性、计算机和算法的组合所破解。
有几十种著名的量子算法。你可以在这里看到一个相当包容的主要列表：https://en.wikipedia.org/wiki/Quantum_algorithm或https://quantumalgorithmzoo.org/.许多人证明，至少在理论上，量子计算机能比经典计算机做得更好。其他的超越了理论，可以应用于解决实际问题，使用量子计算机的速度远远快于传统计算机。对于量子计算和量子密码学的前景来说，少数算法已经变得足够重要，以至于它们每天都在在线量子和密码圈中被讨论数千次。以下是三个最重要的量子算法，它们与打破今天的传统密码学有关。

格罗弗算法

在Shor的算法（简短地讨论）之后，Lov Grover的算法可能是讨论最多和最受喜爱的量子算法。Grover的算法从本质上证明了，用量子计算机发现任何非结构化/无序搜索（或数学）问题的答案都比传统的经典二进制计算机快得多。Grover 说，不需要像经典计算机那样，线性地一次计算所有可能的 N 个解，而是可以用 log （ N ）+ 1 量子比特的量子计算机在 N 的平方根上计算。Grover的算法提供了二次工作负载加速。
假设一个数学答案（或搜索）可以是 1 , 000 ， 000 个可能答案中的任意一个（即 N = 1000000 ）。在最坏的情况下，一台传统的计算机可能需要完成1,000,000个操作才能找到答案。Grover 的算法证明了量子计算机，用 7 个量子位（ log （ 1000000 ）+ 1 个量子比特），可以在相同运算次数的平方根中找到相同的答案，或者最多 1000 次运算。平方根解决方案实际上将指数问题的工作负载减半（记住，指数每增加一位数，前一个基数就会增加一倍）。
Grover的算法可以帮助破解对称（以及程度小得多的非对称）加密密钥，并在量子计算机上解决某些类型的加密散列函数，其速度远远快于经典计算机。专家建议，对称密钥和散列的大小增加一倍，以保持其在后量子世界的相对保护。

傅里叶变换

约瑟夫·傅立叶于1830年去世，他创造了一系列物理学的见解，今天被称为傅立叶级数。傅里叶变换算法获取一个波（或波函数），并将其转换为它的组成部分，就像遵循食谱可以帮助某人分解并重新创建相同的膳食。
注：感谢https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/食谱寓言。
傅立叶变换分析一个波，并打破了波的峰值，值，振幅（即角度），频率和偏移的离散值。它本质上允许任何波函数被分解和重构为它的频率分量的总和。它是一种通过波粒二象性谱连接和转换量子粒子的方法。
有了食谱寓言，想象你有一个美味的蔬菜汤。波浪将是完成的汤。傅立叶变换可以让任何人按照相同的汤配方（例如，1杯鸡汤，2杯切碎的胡萝卜，1杯切碎的洋葱等，在300华氏度下煮一个小时）来制作完全相同的汤，反之亦然。许多其他的量子解决方案和算法，如肖尔的算法（稍后解释），依赖于基于量子的傅立叶变换为自己的成功。傅立叶允许计算从量子的基于粒子的特性转移到基于波的特性，然后再回到各自有更大好处的地方。

肖尔算法

数学家Peter Shor可能是现代与量子计算和破解传统非对称密码学相关的最知名的人物。这是因为在1994年，他发表了一个算法（在他的论文《量子计算的算法：离散对数和因式分解》），本质上为量子计算机提供了一种快速分解非常大的素数方程的方法。https://pdfs.semanticscholar.org/6902/cb196ec032852ff31cc178ca822a5f67b2f2.pdf).肖尔的算法提供了至少一个指数的改善，并可能多项式时间的改善，为因式分解大素数。使用有足够稳定量子位的量子计算机，Shor的算法可以在几秒到几分钟内分解非常大的素数方程。他的算法过去是，现在仍然是革命性的。在它发表后，甚至在有一个实际的应用程序来测试理论之前，计算机世界立即理解了它的含义：量子计算机可以而且很可能最终会变得比经典计算机更强大。密码专家们马上就知道，今天大多数传统的公钥密码都是可以祝酒被破解的！这是这本书得以出版的关键原因。从那时起，加密世界的每个人都在担心量子计算机开始破解传统非对称加密的那一天。
Shor的算法不涉及所有涉及的数学问题(它并不特别复杂--只是很多)，它允许量子计算机更快地对素数进行因子分解，方法是使用一个方程，对其中一个素数进行纯粹的随机猜测，然后将它转化为一个更近的猜测，然后快速地找到实际的素数。Shor的算法使用了两个涉及素数的数学关系，与传统的蛮力方法相比，它大大减少了所需的猜测数。仍然需要大量的猜测，但当利用叠加的量子性质进行这些猜测时，它们几乎可以在量子门计算机上立即生成。在所有这些猜测中是正确的两个素数。所有的猜测都被认为是Shor算法的“第1阶段”或“第一部分”。
注意，  你将很难找到一个更好的解释Shor算法的所有基本数学和方程比这个视频：www.youtube.com/watch？v=lvTqbM5Dq4q。
在第二阶段，彼得·肖尔也想出了如何快速确定许多创建的猜测中哪些是正确的两个素数。虽然这是用数学方法来做的，但用视觉寓言来解释要容易得多（见图3.5所示）。每个素数猜测被转换成正弦波（使用傅立叶变换）。然后将每个猜测的正弦波加到其他可能的猜测的正弦波上。两个正确的答案创建了最高峰和最低谷的组合正弦波。所有其他不正确的猜测的组合正弦波相互干扰更大，导致更小的波峰和波谷，因此总的组合正弦波更小。最后，要找到正确的两个非常大的质数，量子计算机所要做的就是找到最高的正弦波。肖尔算法的最后一步很像我们任何人都能在一组照片中快速识别出最高的人。这样做需要的时间超过几秒钟，但在时间上，可以衡量分钟（理论上）。与经典计算机可能需要数十亿年才能算出这两个正确的数字相比，量子计算机的可用性要高得多。
[插图]
图3.5在求解一个易于理解的小素数方程时，右边的两个素数产生最高的正弦波峰值

超越肖尔算法

其他算法被吹嘘为比Shor算法更快，包括GEECM(https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization#量子_Version_(GEECM))和这一新宣布的进展，https://www.technologyreview.com/s/613596/how-a-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/.这意味着Shor的算法本质上是一个大素数方程分解速度的“地板”，很可能比Shor的预测更快和/或用更少的量子位数来解决它们。
此外，绝热计算机，这是量子退火计算机的一个子类（在第2章中介绍），使用绝热计算和相关的绝热定理因子大素数。事实上，截至2019年，绝热计算机已经比使用肖尔算法的通用量子计算机分解了更大的素数方程。但大多数观察家认为，随着通用量子计算机的不断改进，它们连同肖尔的算法，将远远超过绝热计算机迄今所取得的早期进展。有点像乌龟和兔子的两难选择。无论如何，许多不同类型的量子计算机和算法正在取得大量的计算进展，而这些进展中的很大一部分都指向了破解不同类型密码的能力。
因此，量子计算机如何可能打破今天的许多传统加密的问题是由两个接近现实的答案。首先，总的来说，量子计算机很可能在未来一两年内取得量子霸权，并将能够执行经典计算机无法轻易做到的事情。依靠传统计算机相对“慢”来进行秘密保护的密码算法将不那么强大。
第二，任何依赖于大素数分解（或离散对数问题或椭圆曲线离散对数问题）的密码将被打破，当量子计算机达到足够的稳定的量子比特，以执行更有效的量子因式分解算法对今天的相关密码。简而言之，量子计算机的速度更快，它们的量子特性使用量子算法可以“简化数学运算”，这在只有经典计算机的世界里提供了如此多的保护。

量子能打破的和不能打破的

量子计算机和量子属性不能神奇地破解每一个已知的密码。他们只能破解依赖于特定功能的密码，这些功能易受量子特性和量子算法的保护。本节将讨论量子计算机的密码是什么，哪些不太可能破解。

量子计算能打破什么

如前所述，量子计算机可以破解任何密码算法，其安全性依赖于整数分解问题，离散对数问题，椭圆曲线离散对数问题，或任何其他密切相关的数学问题。至少，这意味着以下密码和常见应用程序（使用这些密码）可能在不久的将来被破解:
里维斯特，沙米尔，阿德曼 （RSA）
Diffie-Hellman（密钥交换）
数字签名算法，又称有限域密码
椭圆曲线密码（又称椭圆曲线数字签名算法）
埃尔加马尔
PerkinElmer（包括数字证书、数字签名）
HTTPS/TLS
大多数VPN
硬件安全模块（HSM）
智能卡
大多数无线网络安全
加密货币
大多数依赖数字证书的双因素身份验证(例如，FIDO[快速身份在线】密钥、Google安全密钥）
经典随机数发生器
仅仅包括HTTPS/TLS，就意味着互联网的大部分加密都将被破解。添加Perkin Elmer相关的加密，意味着大多数与业务相关的加密将被破坏。并不是所有的传统密码都被打破了，但在每次使用的基础上，它包括了世界上的大部分地区。
注:不用说，这个关于什么密码可以被破解的假设适用于所有这些应用程序，因为它们是今天普遍应用的，如果它们使用（或可以移植到）抗量子密码，它们可能不容易被破解。

量子计算无法打破的

了解量子计算机可能破解的是一个令人印象深刻的密码和应用列表。但并不是今天所有的密码学都容易受到量子计算机的影响（至少就我们目前所知）。不受量子计算机和算法影响的密码学被称为量子抵抗（quantum resistant）、量子安全（quantum-safe）或后量子（post-quantum）。大多数密码学家可以互换使用这三个术语。
下面的密码被称为量子抗性:
当与"安全"密钥大小一起使用时，对称密码，如AES（以及仅依赖于对称密码的应用程序和协议，如Kerberos和GSM手机使用的网络交换子系统）
较新的完整性散列，如SHA-2、SHA-3等。与“安全”哈希大小一起使用时
SHAKE，一种流密码
量子密钥分配（QKD），例如BB84、BBM、B92、COW、DPS、E91和ARG04
SNOW 3G，一种基于字的同步流密码
超奇异同构Diffie-Hellman密钥交换
基于格的密码
基于多变量的密码学
基于代码的密码学
零知识证明密码学的几种形式
基于量子的随机数生成器（在第7章中讨论）
基于量子的密码
在接下来的章节中，我们将再次介绍许多抗量子密码。
所有的量子抵抗密码学和应用程序目前都被认为是量子抵抗的，但如果有令人惊讶的新进展，未来可能会变得容易受到量子计算或新算法的影响。可以说，有很多量子安全的密码和机制来保护我们的未来，但即使是这些也有风险。本书的第2部分“为量子突破做准备”讨论了这些量子安全的密码和实现。
附注：没有什么是不能破解的。即使是量子安全的密码，即使世界上最杰出的量子科学家告诉你。你会读到和听到量子密码和其他加密设备和功能是“不可破解的”。虽然这在理论层面上可能是正确的，但现实世界中的情况有点不同。人类还没有能力做出不可破解的东西，即使是从一个“不可破解”的理论或属性开始。量子世界并没有改变这一点，尽管量子特性可能会使黑客更难做黑客。