6

我正在研究 WEP,作为其中的一部分,我正在玩弄 RC4 算法。我正在尝试确定是否可以编写逆向表(尽管很大……我没有空间,也不打算写一个)。为此,我决定检查前 10 个字节中有多少匹配输出。这将帮助我确定逆向表的工作情况。

当然,64 位 RC4 加密有 2^64 个可能的密钥,所以这意味着进行 ~ 2^128 次比较。另外,每次比较必须生成 10 个字节,大约是 265 个循环。(256 用于 RC4 初始化,10 用于字节本身)。

言归正传:

在拥有大约 100 个核心的超级计算机上,是否有可能在 20 天内执行大约 2^135 次计算?

(在我开始之前,20 天是限制。我最终可能只有 8 个,或者我可能最终得到 400+,但我猜是 100 个核心。)

如果这意味着什么,我的程序是用 Java 编写的。http://pastie.org/2118864

4

5 回答 5

4

在一个理想的世界里,它是:

2 135 次操作 ÷ 20 天 ÷ 24 小时/天 ÷ 60 分钟/小时 ÷ 60 秒/分钟 ÷ 100 个核心 =每个核心每秒10 32次操作(Hz/核心),假设我的数学没有关闭。

您需要 10个 32 Hz 内核,每个时钟执行一次计算。通常,它需要多个。那……至少可以说,目前还不是很容易达到。如果幸运的话,您使用超级计算机所能达到的最佳效果可能在 ~10 GHz = 10 10 Hz/核心的一般区域左右。

(这都忽略了阿姆达尔定律......)

于 2011-06-25T02:02:16.653 回答
4

有趣的问题,很难正确回答。大多数时候,可扩展性是“试一试”的事情之一。

需要注意的一件事是,由于其他因素,您将获得多核系统的线性扩展

假设您的程序可以n每秒比较密钥。因此,理想的(即线性)100 核系统将100n每秒计算密钥。要比较所有密钥(最坏的情况,现实情况是一半)需要(2^135/100n)/86400几天时间。

如果n是 1000,则需要 5041220250680569829087031221211 天,这比一些对宇宙年龄的估计长约 10 亿倍。

所以我要说...不 :) 密码算法是为这些类型的攻击而设计的。此外,Java 将是编写此类应用程序时选择的最后一种语言:p

于 2011-06-25T02:07:01.600 回答
3

这些数字有些虚构。他们主要是为了说明问题。数学过于乐观,以使其更容易。

  1. 单个核心每秒可以处理 40 亿 (2 32 ) 次操作(这是非常乐观的数字)

  2. 并且因为每天有 86400 秒(向上舍入 2 17

  3. 和 20 天(向上取整 2 5

  4. 和 100 个内核(向上舍入 2 7

然后... 2 32 * 2 17 * 2 5 * 2 7 == 2 (32 + 17 + 5 + 7) == 2 61计算...所以:

不是机会。甚至没有远程关闭。剩余的计算量是如此惊人,我什至无法理解它到底是什么。对不起 :-)

(根据上述数字,需要 2 79天......)

于 2011-06-25T02:04:17.760 回答
3

人们没有意识到一个数字有多大。

2^135 大约是 4e40,好吧,43556142965880123323311949751266331066368。

假设您有一台能够执行 1 exaflop 的计算机,比我们今天拥有的任何计算机都快得多。因此,如果它能够在每个浮点运算中进行其中一种计算,那么它可以在一秒钟内完成 10^18 次。这仍然让您需要 4e22 秒。每年大约有 31536000 秒,所以你的小企业仍然需要 1e15 年以上。

好吧,取决于你和谁交谈,宇宙的历史在 6000 年到 130 亿年之间。

Java 与否,答案是否定的。(天网在吗?)

于 2011-06-25T02:11:01.527 回答
1

宇宙中至少有 2^240 个原子,因此即使每天进行一次计算,您甚至不需要其中的一半来计算它。话又说回来,比尔盖茨不是说过“谁会需要宇宙中超过一半的原子?”

于 2011-06-25T02:10:51.353 回答