当前位置：文江博客话题详情

encryption cryptography quantum-computing

量子计算和加密破解

发布于 2024-08-31 00:05:01 字数 149 浏览 6 评论 0 原文

我不久前读到，量子计算机可以在很短的时间内（我相信只有几分钟）破解当今使用的大多数类型的哈希和加密。怎么可能呢？我尝试阅读有关它的文章，但我迷失在量子位可以是 1、0 或其他上。有人能解释一下这与用简单的英语破解此类算法有什么关系，而不需要所有花哨的数学吗？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

极度宠爱 2024-09-07 00:05:01

序言：量子计算机是一种奇怪的野兽，我们还没有将其驯服到有用的地步。支持它们的理论是抽象的和数学的，因此任何关于它们如何比经典计算机更高效的讨论都将不可避免地冗长且复杂。您至少需要本科生对线性代数和量子力学的了解才能理解细节，但我会尽力表达我有限的理解！

量子计算的基本前提是量子叠加。这个想法是，正如你所说，量子系统（例如量子位，或qubit，普通位的量子类似物）不仅可以存在于0 和 1 状态（称为系统的计算基础状态），但也可以是两者的任意组合（以便每个状态都有一个振幅 > 与之相关）。当系统被某人观察时，量子位的状态崩溃到其基本状态之一（您可能听说过薛定谔的猫思想实验，与此相关）。

因此，n 个量子位的寄存器拥有自己的 2^n 基本状态（这些是您可以观察寄存器的状态）存在；想象一个经典的 n 位整数）。由于寄存器可以同时存在于所有这些状态的叠加中，因此可以对所有2^n寄存器状态应用计算，而不仅仅是其中之一。这称为量子并行性。

由于量子计算机的这一特性，它们看起来像是一颗灵丹妙药，可以比经典计算机以指数级速度更快地解决任何问题。但事情并没有那么简单：问题是，一旦你观察到计算结果，它就会崩溃（正如我上面提到的）只是其中一个计算的结果 - 并且你会丢失所有其他计算的结果。

量子计算/算法领域就是试图通过操纵量子现象来解决这个问题，以比经典计算机更少的操作来提取信息。事实证明，设计一种比任何可能的经典算法更快的“量子算法”是非常困难的。

你问的例子是量子密码分析的例子。人们认为量子计算机可能能够“破解”某些加密算法：特别是 RSA 算法，该算法依赖于找到非常大的整数的质因数的难度。实现这一点的算法称为 Shor 算法，它可以用多项式时间分解整数复杂。相比之下，该问题的最佳经典算法具有（几乎）指数时间复杂度，并且该问题因此被认为是“棘手”。

如果您想更深入地了解这一点，请阅读几本有关线性代数和量子力学的书籍并感到舒适。如果你想要一些澄清，我会看看我能做什么！

旁白：为了更好地理解量子叠加的概念，请从概率的角度思考。想象一下，您抛掷一枚硬币，然后将其接在手上，并遮盖起来，这样您就看不到它了。 作为一个非常微妙的类比，硬币可以被认为是正面和反面“状态”的叠加：每个状态的概率为 0.5（并且，自然地，因为有两种状态，这些概率加起来为 1)。当你把手拿开并直接观察硬币时，它会崩溃为正面状态或反面状态，因此这种状态的概率变为 1，而另一种状态的概率变为 0。我想，有一种思考方式：是一组在观察之前保持平衡的尺度，此时，随着我们对系统的了解增加，并且一个状态成为“真实”状态，它会向一侧倾斜。

当然，我们并不认为硬币是一个量子系统：出于所有实际目的，硬币具有确定的状态，即使我们看不到它。然而，对于真正的量子系统（例如被困在盒子里的单个粒子），我们可以不要这样想。根据量子力学的传统解释，粒子基本上没有明确的位置，但同时存在于所有可能的位置。只有在观察时，它的位置才会在空间中受到限制（尽管程度有限；参见不确定性原理)，甚至这也是纯粹随机的，仅由概率决定。

顺便说一句，量子系统并不限于只有两个可观察的状态（那些有的被称为两个级系统）。有些有很大但有限的数量，有些有可数无限的数量（例如“盒子里的粒子” 或谐波振荡器），有些甚至有不可数的无限数量（例如作为自由粒子的位置，不受单个点的限制在太空中）。

Preamble: Quantum computers are strange beasts that we really haven't yet tamed to the point of usefulness. The theory that underpins them is abstract and mathematical, so any discussion of how they can be more efficient than classical computers will inevitably be long and involved. You'll need at least an undergraduate understanding of linear algebra and quantum mechanics to understand the details, but I'll try to convey my limited understanding!

The basic premise of quantum computation is quantum superposition. The idea is that a quantum system (such as a quantum bit, or qubit, the quantum analogue of a normal bit) can, as you say, exist not only in the 0 and 1 states (called the computational basis states of the system), but also in any combination of the two (so that each has an amplitude associated with it). When the system is observed by someone, the qubit's state collapses into one of its basis states (you may have heard of the Schrödinger's cat thought experiment, which is related to this).

Because of this, a register of n qubits has 2^n basis states of its own (these are the states that you could observe the register being in; imagine a classical n-bit integer). Since the register can exist in a superposition of all these states at once, it is possible to apply a computation to all 2^n register states rather than just one of them. This is called quantum parallelism.

Because of this property of quantum computers, it may seem like they're a silver bullet that can solve any problem exponentially faster than a classical computer. But it's not that simple: the problem is that once you observe the result of your computation, it collapses (as I mentioned above) into the result of just one of the computations – and you lose all of the others.

The field of quantum computation/algorithms is all about trying to work around this problem by manipulating quantum phenomena to extract information in fewer operations than would be possible on a classical computer. It turns out that it's very difficult to contrive a "quantum algorithm" that is faster than any possible classical counterpart.

The example you ask about is that of quantum cryptanalysis. It's thought that quantum computers might be able to "break" certain encryption algorithms: specifically, the RSA algorithm, which relies on the difficulty of finding the prime factors of very large integers. The algorithm which allows for this is called Shor's algorithm, which can factor integers with polynomial time complexity. By contrast the best classical algorithm for the problem has (almost) exponential time complexity, and the problem is hence considered "intractable".

If you want a deeper understanding of this, get a few books on linear algebra and quantum mechanics and get comfortable. If you want some clarification, I'll see what I can do!

Aside: to better understand the idea of quantum superposition, think in terms of probabilities. Imagine you flip a coin and catch it on your hand, covered so that you can't see it. As a very tenuous analogy, the coin can be thought of as being in a superposition of the heads and tails "states": each one has a probability of 0.5 (and, naturally, since there are two states, these probabilities add up to 1). When you take your hand away and observe the coin directly, it collapses into either the heads state or the tails state, and so the probability of this state becomes 1, while the other becomes 0. One way to think about it, I suppose, is a set of scales that is balanced until observation, at which point it tips to one side as our knowledge of the system increases and one state becomes the "real" state.

Of course, we don't think of the coin as a quantum system: for all practical purposes, the coin has a definite state, even if we can't see it. For genuine quantum systems, however (such as an individual particle trapped in a box), we can't think about it in this way. Under the conventional interpretation of quantum mechanics, the particle fundamentally has no definite position, but exists in all possible positions at once. Only upon observation is its position constrained in space (though only to a limited degree; cf. uncertainty principle), and even this is purely random and determined only by probability.

By the way, quantum systems are not restricted to having just two observable states (those that do are called two-level systems). Some have a large but finite number, some have a countably infinite number (such as a "particle in a box" or a harmonic oscillator), and some even have an uncountably infinite number (such as a free particle's position, which isn't constrained to individual points in space).

回复收藏 0 原文

对风讲故事 2024-09-07 00:05:01

在这一点上它是高度理论化的。量子比特可能提供破解加密的能力，但显然还没有到那个地步。

在量子层面上，支配行为的法则与宏观层面上的不同。

要回答您的问题，您首先需要了解加密的工作原理。

从根本上讲，加密是将两个极大的素数相乘的结果。这个超大的结果可以被1、它本身和这两个素数整除。

破解加密的一种方法是通过进行素数分解来暴力猜测两个素数。

这种攻击很慢，并且可以通过选择越来越大的素数来阻止。您听说过 40 位、56 位、128 位的密钥大小，现在有 256,512 位及以上。这些大小与数字的大小相对应。

暴力算法（简单来说）可能看起来像

for(int i = 3; i < int64.max; i++)
{
  if( key / i is integral)
  {
    //we have a prime factor
  }
}

这样，所以你想暴力尝试素数；对于一台计算机来说，这将需要一段时间。因此，您可以尝试将一堆计算机组合在一起以分而治之。这可行，但对于非常大的密钥大小仍然很慢。

量子位解决这个问题的方式是它们同时为 0 和 1。假设你有 3 个量子位（请注意，这不是一件小事）。

使用 3 qbits，您的程序可以同时具有 0-7 的值

（000,001,010,011等）

，同时包含素数 3,5,7。

所以使用上面的简单算法，你可以只除一次，而不是每次将 i 加 1，然后检查

0,1,2,3,4,5,6,7

同时出现。

当然，量子比特还没有达到那个程度。该领域仍有大量工作要做；但这应该让您知道如果我们可以使用量子进行编程，我们将如何破解加密。

It's highly theoretical at this point. Quantum Bits might offer the capability to break encryption, but clearly it's not at that point yet.

At the Quantum Level, the laws that govern behavior are different than in the macro level.

To answer your question, you first need to understand how encryption works.

At a basic level, encryption is the result of multiplying two extremely large prime numbers together. This super large result is divisible by 1, itself, and these two prime numbers.

One way to break encryption is to brute force guess the two prime numbers, by doing prime number factorization.

This attack is slow, and is thwarted by picking larger and larger prime numbers. YOu hear of key sizes of 40bits,56bits,128bits and now 256,512bits and beyond. Those sizes correspond to the size of the number.

The brute force algorithm (in simplified terms) might look like

for(int i = 3; i < int64.max; i++)
{
  if( key / i is integral)
  {
    //we have a prime factor
  }
}

So you want to brute force try prime numbers; well that is going to take awhile with a single computer. So you might try grouping a bunch of computers together to divide and conquer. That works, but is still slow for very large keysizes.

How a quantum bit address this is that they are both 0 and 1 at the same time. So say you have 3 quantum bits (no small feat mind you).

With 3 qbits, your program can have the values of 0-7 simulatanously

(000,001,010,011 etc)

, which includes prime numbers 3,5,7 at the same time.

so using the simple algorithm above, instead of increasing i by 1 each time, you can just divide once, and check

0,1,2,3,4,5,6,7

all at the same time.

Of course quantum bits aren't to that point yet; there is still lots of work to be done in the field; but this should give you an idea that if we could program using quanta, how we might go about cracking encryption.

回复收藏 0 原文

寂寞笑我太脆弱 2024-09-07 00:05:01

维基百科文章很好地解释了这一点。

简而言之，如果你有 N 位，你的量子计算机可以同时处于 2^N 种状态。从概念上讲，类似于使用传统位进行 2^N 个 CPU 的处理（尽管不完全相同）。

回复收藏 0 原文

梦巷 2024-09-07 00:05:01

量子计算机可以实现Shor算法，该算法可以快速执行素因数分解。加密系统建立在这样的假设之上：在经典计算机上无法在合理的时间内分解大素数。

回复收藏 0 原文

ㄖ落Θ余辉 2024-09-07 00:05:01

几乎我们所有的公钥加密（例如 RSA）都完全基于数学，依赖于分解的难度或离散对数。使用量子计算机可以有效地破解这两个问题（尽管即使在获得计算机科学学士学位之后和数学，并且上了几门量子力学课程，我仍然不明白算法）。

但是，散列算法（例如 SHA2）和对称密钥加密（例如 AES） 主要基于扩散和混乱，仍然安全。

回复收藏 0 原文

送你一个梦 2024-09-07 00:05:01

用最基本的术语来说，普通的非量子计算机通过使用布尔逻辑对位（开或关的状态）进行操作来工作。您可以非常快速地处理很多很多位，并且可以解决一类可计算问题中的任何问题。

然而，它们是“速度限制”，即所谓的计算复杂性。通俗地说，这意味着对于给定的算法，您知道运行算法所需的时间（以及运行算法所需的内存空间）有一个最小界限。例如，O(n^2) 的算法意味着对于 n 的数据大小，需要 n^2 时间来运行。

然而，当我们有 qbit（量子位）时，当您对可以具有“中间”值的 qbit 进行操作时，这种情况就被排除在外了。具有非常高计算复杂度的算法（例如分解大量数字，这是破解许多加密算法的关键）可以以低得多的计算复杂度来完成。这就是量子计算能够比普通计算机更快几个数量级地破解加密流的原因。

回复收藏 0 原文

待＂谢繁草 2024-09-07 00:05:01

首先，量子计算还刚刚走出理论阶段。大量的研究正在进行，并且有一些实验性的量子电池和电路，但“量子计算机”尚不存在。

其次，阅读维基百科文章：http://en.wikipedia.org/wiki/Quantum_computer

特别是，“一般来说，具有 n 个量子位的量子计算机可以同时处于最多 2^n 种不同状态的任意叠加（相比之下，普通计算机在任何时候只能处于这 2^n 种状态之一））”

密码学之所以安全，是因为使用了非常长的数字加密密钥，需要非常非常长的时间才能将其分解为质数，而且密钥足够长，可以通过暴力破解来尝试所有可能的方法。键值也需要很长时间才能完成。

由于量子计算（理论上）可以表示少量量子位单元中的许多状态，并同时对所有这些状态进行操作，因此似乎有可能使用量子计算来执行强力尝试所有可能的操作在很短的时间内获得键值对。

如果这样的事情成为可能，那么这可能就是我们所知的密码学的终结。

回复收藏 0 原文

我做我的改变 2024-09-07 00:05:01

量子计算机等都是谎言。我不相信这些科幻杂志。
事实上，RSA系统是基于两个素数及其乘法。
p1,p2 是大素数 p1xp2=N 模。
RSA系统是
像那样
选择一个素数..也许小它的 E 公钥
(p1-1)*(p2-1)=R
找到一个 D 数，使得 E*D=1 mod(R)
我们公开共享 (E,N) 数据作为公钥
我们将 (D,N) 安全地保存为私有。

要解决这个 Rsa 系统破解问题，需要找到 N 的质因数。
*宇宙的质量接近 10^53 kg*
电子质量为 9.10938291 × 10^-31 千克
如果我们将宇宙划分为电子，我们可以产生 10^84 个电子。
电子的速度比光慢。它的移动频率可以是10^26
如果有人从所有宇宙质量中产生电子大小平行的 rsa 素因子发现者。
所有宇宙每秒可以处理 (10^84)*(10^26)= 10^110 个数字。

rsa 具有无限位的替代素数。可能是 4096 位
4096 位 rsa 有 10^600 个可能的素数可以进行暴力破解。
所以你的宇宙质量量子求解器需要在 10^500 年期间进行测试。

RSA vs 宇宙质量量子计算机
1 - 0

也许量子计算机可以破解64/128位密码。因为 128 位密码有 10^39 个可能的暴力破解节点。

回复收藏 0 原文

过期以后 2024-09-07 00:05:01

该电路是了解量子位并行如何工作的良好开端。 2 量子位输入位于左侧。顶部量子位是 x，底部量子位是 y。 y 量子位在输入处为 0，就像普通位一样。另一方面，x 量子位在输入处叠加。 y (+) f(x) 这里代表模 2 加法，即 1+1=0、0+1=1+0=1。但有趣的是，由于 x 量子位处于叠加状态，f(x) 同时是 f(0) 和 f(1)，我们可以同时对所有状态的 f 函数进行评估，而无需使用任何（耗时）循环。有了足够的量子位，我们就可以将其分支为无限复杂的电路。

回复收藏 0 原文

丶情人眼里出诗心の 2024-09-07 00:05:01

在我看来更奇怪。是格罗弗算法。作为输入，我们得到一个未排序的整数数组，其中 arraylength = n。找到该数组最小值的算法的预期运行时间是多少？传统上，我们至少要检查数组中的每个 1..n 元素，从而得出 n 的预期运行时间。对于量子计算机来说并非如此，在量子计算机上我们可以在最大根（n）的预期运行时间内解决这个问题，这意味着我们甚至不必检查每个元素来找到有保证的解决方案......