我意识到这不是一个“是或否”的问题,我很抱歉提出一些可以被视为讨论话题的问题,但我不得不问。

我目前正在做EPQ在CS中(特别是QC将如何更改密码术)。我正在尝试收集涉及的主题,到目前为止,我已经写下了-

效果-


国家安全,经典加密方法(RSA ,DSA,AES-256)。包括Shor的算法。
通信
在线服务,例如BitCoin。

我们将如何应对(不确定如何更好地表达这一点)-


基于格的
多变量
哈希基于签名的签名
基于代码的加密技术

您是否还建议我包括(以及上述)其他内容,或者您​​认为我不应该包含的其他内容? ?

老实说,上面的列表是一个粗略的草稿,它的主要部分是初稿...所以不要当作福音。

最好的问候,

Cameron。

评论

在“后量子密码学”中搜索有用的材料。此外,恕我直言,“量子计算会赶上经典,何时?”是最有趣的主题。

这当然是一个非常有趣的主题。您会怎么想?主要涵盖历史,我认为这些进步将在哪里结束或完全消失?另外,您不认为有关量子计算的第一个主题更加关注吗?

如果我知道如何有意义地探索“量子计算会赶上Classic,什么时候赶上?”,我会那样做!确实,这似乎比您要解决的问题更加困难,而且重点更少。但也更加扎实。

与质量控制最接近的事情之一似乎是这个

这份调查报告是关于此主题的很好的阅读。

#1 楼

实际上,当前的对称密码术和散列被认为对量子计算是相当安全的。量子计算机比最著名的经典算法更快地解决了一些问题,但是最著名的针对AES的量子攻击实际上是“尝试所有密钥”。在量子计算机中,解决一般搜索问题(例如“查找给出合理消息的AES密钥”)所花费的时间比传统计算机要慢。这将有效地将n位密钥转换为n / 2位密钥。幸运的是,这将使AES-256拥有有效的128位密钥来对抗量子攻击者,而量子攻击者仍然认为难以破解。类似的考虑也适用于哈希。您希望增加密钥长度等,但是您可以合理地做到这一点。

主要问题实际上是非对称密码学。与对称加密和哈希不同,非对称算法具有极高的数学结构-它们基于单个难题的难度。在量子计算机上可以非常迅速地解决用于此的两个主要问题。如果您试图增加密钥长度以使其花费较长时间,那么经典计算机上的合法用户使用长密钥将花费不可行的长时间。然而,这是历史上的意外:没有理由不必须用量子计算机轻易地破解不对称加密,只是最常用的密码碰巧容易被一个破解。其他人可能不是;后量子密码学是一个活跃的研究领域,人们正在研究依赖于量子计算机无法有效解决的问题的算法。

评论


$ \ begingroup $
您声称非对称加密特别容易受到攻击;这不是意味着对称密钥协商/交换由于使用非对称密码技术而容易发生吗?看起来,如果您未使用PSK,则很容易受到攻击。
$ \ endgroup $
–克莱·弗里曼
2014年12月30日在8:58

$ \ begingroup $
@ClayFreeman正确。实际上,非对称加密的主要用途是为对称加密加密密钥。但是,人们正在研究不对称算法来抵抗量子计算机,而其他加密的常见应用(例如磁盘加密)也确实使用了PSK。
$ \ endgroup $
–cpast
2014年12月30日在9:01

$ \ begingroup $
@ClayFreeman问题实际上并不是非对称加密对量子计算机的固有弱点。但是,最流行和广泛使用的非对称方案对量子攻击(例如,RSA)较弱。有许多已知的非对称加密方案被认为对量子计算机并不弱。特别是,基于LWE问题的基于格的加密方案在理论密码学界引起了很多关注。
$ \ endgroup $
– Guut Boy
2014年12月30日12:24

$ \ begingroup $
我听说它说量子计算机本身将能够进行更安全的加密,这种加密实际上具有理论上证明的抗破解能力,而不是依赖于P不等于NP的假设(我相信,这与您在第二段中提到的硬数学问题有关?)。我还听说过,这种加密形式不可能被秘密篡改,因为每次尝试读取或修改它都会留下痕迹吗?不幸的是,我不记得这些要求的来源。
$ \ endgroup $
– KRyan
17 Mar 6 '17 at 20:49

$ \ begingroup $
这不是BB84 2轮密钥交换的直接结果吗?除非我有所遗漏,否则两轮密钥交换协议意味着存在INDCPA安全加密方案,并且BB84的安全性是信息论的。
$ \ endgroup $
– Geoffroy Couteau
17年5月11日在7:33

#2 楼

Grover的算法将允许在$ O(\ sqrt {N})$时间而不是通常的$ O(N)$时间中搜索具有N个条目的未排序数据库。

目前,对于AES-256,平均需要破解$ n / 2 $个猜测,即$ 2 ^ {255} $。但是,使用量子计算可以在$ 2 ^ {128} $的时间内完成,这要快得多。而且,对于AES-256而言,这只是蛮力,而凭借更聪明的攻击,它可以更快地被破解。

$ 2 ^ {128} $仍然足够慢。但是,AES-256具有比DES(最快的经典攻击:$ 2 ^ {39} –2 ^ {43} $,已经相当糟糕),3DES甚至较小的密钥空间AES-128等标准更大的密钥空间。由于质量控制,这些将被破坏或变得更接近破坏。

因此,我们可能会发现朝着更大的密钥空间标准(如AES-256)迈进了一步。无论如何,这正是摩尔定律(更好的计算机)已经迫使我们脱离DES的情况,所以也许QC并不是开创性的。您需要做的就是我们一直在做的事情,那就是在我们系统的性能和打破它所花费的时间之间找到适当的平衡,只是平衡会发生变化。

#3 楼

保理和RSA是我们知道的量子计算机应该能够有效解决的一些问题。也就是说,是的,RSA可能会被破坏。

但是,量子计算机并不一定会使所有现代密码学都过时。对于对称图元,例如AES,甚至都不知道量子计算机会产生很大的不同。因此,主要挑战在于公钥加密。在这一领域,我们已经知道了一些后量子密码学的候选人,这些候选人不是基于可以在量子计算机上有效解决的问题。

例如,基于晶格的加密是显示出很大希望的那些候选者之一。基于格的加密算法基于格点问题,而格点问题与诸如分解等问题根本不同,因此,在量子计算机上尚无法有效解决。最后,我检查了此类系统的主要问题是,基本的硬度假设并未像RSA那样经过良好的测试,因此很难准确确定哪些系统可以视为安全参数。

如果您对后量子密码学感兴趣,您可以阅读《后量子密码学》一书,该书处理许多不同的候选对象,例如基于格,哈希和代码的候选对象。这本书是2009年出版的,所以可能有点过时了,但是我认为材料仍然应该有意义。

#4 楼

总结:


对于“对称”密码,对于QC来说,使用256位密钥是可以的。注意AES-256并不意味着具有256位块的AES!它关于关键。 AES-256块大小的安全性不如AES-128位块(请参阅Wikipedia)
,因为“非对称”密码尚未准备好,所有当前密码都有其问题(有些存在安全性问题,有些存在实现问题)我们需要一些时间和精力来修复


评论


$ \ begingroup $
256位块的AES不存在。 AES是Rijndael的标准形式,具有128位块大小。
$ \ endgroup $
–马腾·博德威斯♦
2013年1月3日20:53

$ \ begingroup $
实际上,我不确定如果QC成为现实,则128位块是否足够,我不确定通用识别符是否受Grover算法影响,但可能需要牢记。也就是说,增加块和密钥的大小是一个简单的过程,而提出一种安全的非对称算法则不容易。
$ \ endgroup $
–托马斯
13年1月4日,下午5:35



$ \ begingroup $
@Thomas QC是现实,但是您是什么意思128位块对于QC不安全?我以为格罗弗是要更快地找到密钥2倍,该协议也生效了?
$ \ endgroup $
–mary
13年1月4日在8:35

$ \ begingroup $
@mary它们几乎不是实际的现实,我们不知道建造足够大的量子计算机在物理上是否可行。但无论如何,较小的块大小可让您将块密码的输出与随机流区分开,这是一个弱点-我怀疑Grover的算法也会加快这种类型的攻击,需要您相应地增加块大小也一样
$ \ endgroup $
–托马斯
13年1月4日在8:50



$ \ begingroup $
AES是Rijndael的一种变体,具有128位的固定块大小和128、192或256位的密钥大小。猜猜有人对命名感到困惑。 AES-256表示密钥的长度为256位,而不是块...在这种情况下,它仍由128位组成。
$ \ endgroup $
– e-sushi
13年7月30日在8:39