8

我的理解是，如今许多公钥密码算法都依赖于大素数来组成密钥，而难以分解两个素数的乘积使得加密难以破解。我的理解也是，分解如此大的数字如此困难的原因之一是，所使用的数字的绝对大小意味着没有 CPU 可以有效地处理这些数字，因为我们的微型 32 位和 64 位 CPU 无法匹配对于 1024、2048 甚至 4096 位数。必须使用专门的 Big Integer 数学库来处理这些数字，而这些库本身就很慢，因为 CPU 一次只能保存（和处理）小块（如 32 位或 64 位）。

所以...

为什么你不能构建一个具有 2048 位寄存器和巨大算术电路的高度专业化的定制芯片，就像我们从 8 位到 16 位到 32 位到 64 位 CPU 一样，只是构建一个更大的芯片？该芯片不需要传统 CPU 上的大部分电路，毕竟它不需要处理虚拟内存、多线程或 I/O 等事情。它甚至不需要是支持存储指令的通用处理器。只是对巨大数字执行必要的算术计算的最低限度。

我对 IC 设计了解不多，但我确实记得学习过逻辑门的工作原理，如何构建半加器、全加器，然后将一堆加法器连接在一起进行多位运算。只是放大。很多。

现在，我相当肯定有一个很好的理由（或 17 个）以上方法行不通（否则许多比我聪明的人中的一个已经这样做了），但我很想知道为什么它行不通。

（注意：这个问题可能需要重新处理，因为我什至不确定这个问题是否有意义）

4

6 回答 6

3

@cube 说了什么，以及一个巨大的算术逻辑单元需要更多时间来稳定逻辑信号，并包括数字设计中的其他复杂性。数字逻辑设计包括您在软件中认为理所当然的东西，即通过组合逻辑的信号需要一小段但非零的时间来传播和稳定。需要仔细设计 32x32 乘法器。1024x1024 乘法器不仅会占用芯片中的大量物理资源，而且还比 32x32 乘法器慢（尽管计算执行 1024x1024 乘法所需的所有部分乘积可能比 32x32 乘法器快）。此外，瓶颈不仅在于乘数：您还有内存路径。你'

几乎可以肯定，让一堆“传统”的 32 位或 64 位系统并行工作会更好：您可以在没有硬件设计复杂性的情况下获得加速。

编辑：如果有人有 ACM 访问权限（我没有），也许看看这篇论文，看看它说了什么。

于 2009-07-30T14:20:06.730 回答
3

这是因为这种加速只会在 O(n) 中，但因数分解的复杂性类似于 O(2^n)（相对于位数）。因此，如果您制作了这个超级处理器并将数字因式分解的速度提高了 1000 倍，我只需将数字增大 10 位，我们就会重新开始。

于 2009-07-30T12:39:14.600 回答
2

我无法评论与您描述的方法完全相同的方法的可行性，但人们使用 FPGA 经常做类似的事情：

于 2009-07-30T16:34:30.953 回答
2

如上所述，主要问题只是您必须通过多少种可能性来分解一个数字。话虽如此，确实存在专门的计算机来做这种事情。

这种密码学的真正进步是对数分解算法的改进。目前，已知最快的通用算法是通用数域筛。

从历史上看，我们似乎能够每十年对两倍大的数字进行分解。部分原因是更快的硬件，部分原因只是更好地理解数学以及如何执行因式分解。

于 2009-07-30T13:16:52.793 回答
2

Shamir & Tromer提出了一种类似的方法，使用一种网格计算： 将加法器与 TWIRL 进行比较的电路图

本文讨论了一种用于筛选步骤的定制硬件实现的新设计，该设计将 [相对于 TWINKLE 的筛选成本] 降低到约 1000 万美元。这款名为 TWIRL 的新设备可以看作是 TWINKLE 设备的扩展。然而，与 TWINKLE 不同的是，它没有光电元件，因此可以使用标准 VLSI 技术在硅片上制造。基本思想是使用输入的单个副本来并行解决许多子问题。由于输入存储占主导地位，如果并行化开销保持较低，则基本上可以免费获得加速。实际上，主要挑战在于有效地实现这种并行性，同时允许输入的紧凑存储。解决这个问题涉及到无数的考虑，

于 2016-05-03T17:59:27.710 回答
0

为什么不尝试构建一个超级量子计算机并在其上运行Shor 的算法呢？

“......如果要构建具有足够数量的量子比特的量子计算机，Shor 的算法可用于破解公钥加密方案，例如广泛使用的 RSA 方案。RSA 基于这样的假设，即分解大数是计算上不可行。据我们所知，这个假设对于经典（非量子）计算机是有效的；没有已知的经典算法可以将多项式时间分解。但是，Shor 的算法表明分解在量子计算机上是有效的，因此足够大的量子计算机可以破解 RSA。……” ——维基百科

于 2012-09-25T08:14:05.183 回答