这在小型超级计算机上实用吗？
我正在研究 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
I'm investigating WEP and as part of that, I'm toying with the RC4 algorithm. I'm trying to decide if an inverse table is feasible to write (although large... I don't have the space and I don't intend to write one). For that, I've decided to check how many matching outputs there are in the first 10 bytes. That will help me decide how well an inverse table would work.
Of course, a 64 bit RC4 encryption has 2^64 possible keys, so that would mean making ~ 2^128 comparisons. Plus, 10 bytes have to be generated for each comparison, which is approximately 265 loops. (256 for RC4 initialization, 10 for the bytes themselves).
Down to business:
On a supercomputer with around 100 cores , would it be possible to perform around 2^135 calculations in 20 days?
(20 days is the limit until I am kicked off. I could end up with only 8, or I could end up with 400+, but I'm guessing 100 cores.)
If it means anything, my program is written in Java. http://pastie.org/2118864
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
有趣的问题，很难正确回答。可扩展性是大多数时候“尝试看看”的事情之一。
需要注意的一件事是，由于其他因素，您将获得低于线性的缩放与多核系统。
假设您的程序每秒可以比较 n 个键。因此，理想的（即线性）100 核系统每秒将计算
100n个密钥。要比较所有密钥（最坏的情况，实际情况是一半）需要(2^135/100n)/86400天。如果 n 为 1000，则需要 5041220250680569829087031221211 天，这比某些宇宙年龄估计值长约 10 万倍。
所以我要说...不:) 密码算法是为此类攻击而设计的。另外，在编写此类应用程序时，Java 将是最后选择的语言 :p
Interesting question, and very hard to answer properly. Scalability is one of those "try it and see" things most of the time.
One thing to note is that because of other factors, you're going to get less-than-linear scaling with multi-core systems.
Let's say your program can compare
nkeys per second. So an ideal (i.e. linear) 100-core system will compute100nkeys per second. To compare all keys (a worst-case scenario, realistic would be half of that) would take(2^135/100n)/86400days.If
nis 1000, it would take 5041220250680569829087031221211 days, which is about 100 thousand million times longer than some estimates of the age of the universe are.So I'm going to say... no :) Cryptography algorithms are designed for these kinds of attacks. Also, Java would be the last language to choose when writing such an application :p
在理想世界中，大约是：
2135次操作 ÷ 20 天 ÷ 24 小时/天 ÷ 60 分钟/小时 ÷ 60 秒/分钟 ÷ 100 个核心 = 假设我的数学没有出错，每个核心每秒 1032 次操作（Hz/核心）。
您需要 1032 Hz 内核，每个时钟执行一次计算。通常情况下，需要多个。至少可以说，目前还不太容易实现。如果幸运的话，超级计算机所能达到的最佳性能可能约为大约 10 GHz = 1010 Hz/核心。
（这一切都忽略了阿姆达尔定律...）
In an ideal world, it's around:
2135 operations ÷ 20 days ÷ 24 hours/day ÷ 60 min/hour ÷ 60 sec/min ÷ 100 cores = 1032 operations per second per core (Hz/core), assuming my math isn't off.
You'd need 1032 Hz cores, which do a single calculation per clock. Normally, it'd need multiple. That's... not very reachable at the moment, to say the least. The best you'd reach with a supercomputer is probably around the general area of ~10 GHz = 1010 Hz/core, if you're lucky.
(And this is all ignoring Amdahl's law...)
人们没有意识到一个数字有多大。
2^135 大约是 4e40，好吧，43556142965880123323311949751266331066368。
假设你有一台能够执行 1 exaflop 的计算机，比我们今天拥有的任何计算机都要快得多。因此，如果它能够在每个浮点运算中执行其中一个计算，那么它可以在一秒钟内执行 10^18 个计算。这仍然需要 4e22 秒。每年大约有 31536000 秒，所以你的小企业仍然需要 1 到 15 年以上。
好吧，宇宙的年龄介于 6000 岁到 130 亿年左右，这取决于你与谁交谈。
无论是否使用 Java，答案是否定的。 （天网来了吗？）
People don't realize how big a number can be.
2^135 is roughly 4e40, ok, 43556142965880123323311949751266331066368.
Suppose you have a computer capable of performing 1 exaflop, vastly faster than anything we have today. So if it was capable of one of these computations in EVERY floating point operation, then it could do 10^18 of them in a second. This still leaves you needing 4e22 seconds. There are roughly 31536000 seconds per year, so your little enterprise will still take more than 1e15 years.
Ok, depending on who you talk to, the universe is somewhere between 6000 years old, and 13 billion years or so.
Java or not, the answer is no. (Is Skynet here yet?)
这些数字有些虚构。他们大多是为了表达一个观点。为了让事情变得更容易，数学过于乐观了。
单个核心每秒可以处理 40 亿次 (232) 操作（这是一个非常乐观的数字）
和 20 天（向上舍入到 25）
和 100 个核心（向上舍入到 27）
然后... 232 * 217 * 25 * 27< /sup> == 2(32 + 17 + 5 + 7) == 261 计算...所以：
没有机会。甚至远距离都不近。剩余的计算量是如此惊人我什至无法理解它到底是什么。抱歉:-)
（根据上述数字，需要 279 天...）
These numbers are somewhat fictions. They are mostly to make a point. The math is grossly over-optimistic to make it easier.
A single core can process 4 billion (232) operations a second (this is hugely grossly optimistic figure)
and since there are 86400 seconds (round up to 217) a day
and 20 days (round up to 25)
and 100 cores (round up to 27)
then... 232 * 217 * 25 * 27 == 2(32 + 17 + 5 + 7) == 261 calculations ... so:
Not a chance. Not even remotely close. The amount of calculations remaining is so staggering I can't even fathom what it really is. Sorry :-)
(With the above figures it would take 279 days...)
宇宙中至少有 2^240 个原子，因此即使每天计算一次，您甚至不需要一半的原子来计算它。话又说回来，比尔·盖茨不是曾经说过“谁会需要宇宙中一半以上的原子呢？”
There are at least 2^240 atoms in the universe, so you wouldn't even need half of them to compute it even at one computation per day. Then again, didn't Bill Gates once say "who would ever need more than half the atoms in the universe?"