|
楼主 |
发表于 2006-3-13 18:27:50
|
显示全部楼层
翻译 M4 Project 页面:http://www.equn.com/m4/m4_project.html
M4 Message Breaking Project
M4 加密信息破解项目
Status:
状态:
The first message has been broken on February 20th, 2006. The signal in question is the second of the intercepts in Erskine's letter. You can read the raw server logs as well as an interpretation and translation.
第一条加密信息于2006年2月20日被成功破解。该信息是 Erskine 的信件中提到的截获信息中的第二条。您可以阅读原始的服务器日志来了解该信息被破解和破译的详细情况。
The second break has occurred on March 7th, 2006. The signal in question is the third of the intercepts in Erskine's letter. You can read the raw server logs as well as an interpretation and translation.
第二条加密信息于2006年3月7日被成功破解。该信息是 Erskine 的信件中提到的截获信息中的第三条。您可以阅读原始的服务器日志来了解该信息被破解和破译的详细情况。
About:
关于:
The M4 Project is an effort to break 3 original Enigma messages with the help of distributed computing. The signals were intercepted in the North Atlantic in 1942 and are believed to be unbroken. Ralph Erskine has presented the intercepts in a letter to the journal Cryptologia. The signals were presumably enciphered with the four rotor Enigma M4 - hence the name of the project.
M4 项目希望能够借助分布式计算的力量来破解三条加密信息。这三条信息是盟军于 1942 年在北大西洋截获的,这些信息曾被认为是无法破解的信息。Ralph Erskine 将这三条信息密文致函给《Cryptologia》杂志(美国杂志《密码术》)。这些信息是用四转子的 Enigma 机来加密的——项目的名称“M4”即来源于此——四转子之迷。
This project has officially started as of January 9th, 2006. You can help out by donating idle time of your computer to the project. If you want to participate, please follow the client install instructions for your operating system:
本项目正式开始于2006年1月9日。您可以通过捐献您的计算机的闲置处理时间来帮助本项目。如果您想参加本项目,您可以浏览下面给出的安装指南:
Unix Client Install
Win98 Client Install
Win2000 Client Install
WinXP Home Client Install
WinXP Pro Client Install
Software:
软件:
The software used in this project is Open Source, so that you can see what is going on on your computer. The client is a Python script that tries to connect to the server to get a workunit (range of keys). When successful, it launches the message breaking program (written in C) to work on the range. The most promising result of that effort is submitted back to the server, after which the client gets a new workunit.
本项目使用的软件是开放源代码的,因此您能方便的知道我们的软件在您的电脑里到底在做哪些事情。客户端程序使用 Python 脚本来与服务器进行连接,继而获得计算单元(一段加密信息)。当客户端成功下载计算单元后,将自动调用密文破解程序(用 C 语言编写)来对这段加密信息进行猜解。最为可能的猜解结果将被提交返回给服务器,然后客户端将自动获得一个新的计算单元,如此往复。
I have been running the client in the background on two Linux machines for almost two months, and I haven't experienced any stability problems whatsoever. The client runs at the lowest priority, which means that other programs you run on your machine will not be disturbed by it.
我们已经在两台 Linux 机器上将客户端设为后台运行程序连续运行了近两个月,客户端没有使这两台机器出现任何不稳定问题。客户端在最低优先级上运行,这意味着当您需要运行其他程序时,客户端将自动让出资源而丝毫不会影响您日常的工作。
The client-server setup has been tested on some challenge messages presented by Geoff Sullivan and Frode Weierud. Messages 1, 3, 5 and 6 have been broken. Here are the raw server logs of break 5.
客户端-服务端安装程序在针对多条加密信息的破解挑战中测试成功,测试人是 Geoff Sullivan 和 Frode Weierud。加密信息 1、3、5 和 6 已经被破解,这里是加密信息 5 破解返回的结果。
You can see that the server has been restarted due to a kernel upgrade. You can also see that the partial break has a lower score than the highest nonsense results. Here is a cleaned up version of break 5 with all parts of the key corrected.
您可以发现服务器在处理核心程序升级的过程中会出现重启现象。您也可能会发现局部破解结果的得分低于某些毫无意义的破解结果。这里是加密信息 5 的所有可能正确的部分密文。
Method:
方法:
The method in question is a ciphertext-only attack. This means that we don't need bits of guessed/known plaintext for a successful decryption.
解决问题的方法是对纯密码信息进行攻击。这意味着我们不需要猜解或在已知明码文本的某些比特位信息的情况下来对密文进行完美解密。
The most simple ciphertext-only attack would use brute force. You would take every possible key, decrypt the message, and determine the likelihood of the resulting candidate plaintext. The enigma key space is too large for this approach.
大多数简单的纯密文攻击方式都使用暴力破解。您可以尝试几乎所有可能的密钥来猜解密文信息,并且可以确定所有返回给服务器的结果中可能性最大的明文信息。Enigma 的密钥空间在这种情况下显得巨大无比。
The method used here is a mixture of brute force and a hill climbing algorithm:
这里使用的方法是一种结合了强力攻击(brute force,暴力破解)和梯度算法(hill climbing algorithm,爬山法)的混合方法:
The program iterates through all possible machine settings except the plugboard settings. This is a major shortcut since the plugboard settings form a huge portion of the key space. For each of these machine settings the program uses a hill climbing algorithm to find the optimal plugboard settings.
程序重复通过所有可能的机器装置,当然配线板装置除外。这是一条重要的捷径,通过设置线路连接板的步线来生成大量的密钥空间。对这些机器中的每一台都设置程序使用梯度算法(hill climbing algorithm,爬山法)来寻找最佳的线路连接板步线方式。
Hill climbing algorithms try to optimize an object, in this case the plugboard settings, by changing the object step by step. After each change the "goodness" or "fitness" of the new object has to be determined by a scoring function. Changes that lead to a "better" object are retained.
梯度算法逐步对对象(在此情况下为线路连接板设置)进行改变,以此来优化对象。每次做出改变后,新对象的“良好度”与“适切度”须由一个得分函数来决定。对它进行改变就可获得一个“更好的”对象。
Here the changes lie in constantly trying out new wirings of the Enigma plugboard. After each change the scoring function tests a new wiring by deciphering the message and trying to determine how closely the resulting plaintext matches the statistics of the natural language. The scoring function uses Sinkov Statistics.
这里要做的改变在于不断地实验 Enigma 线路连接板的接线方式。每做出一次改变,得分函数就通过译解信息来验证新的接线方式,并试图决定所得到的纯文本与自然语言的匹配程度。得分函数使用 Sinkov 统计数据。
Shortcuts:
捷径:
The messages date from 25th November 1942, which rules out UKW C-Thin and Greek wheel Gamma. See Heinz Ulbricht's PhD Thesis, p9 (in German). The search space can be reduced further by only testing keys where the middle ring is in the 'A' position. Another shortcut is described in the software's documentation.
这些加密信息是1942年11月25日被截获的,其加密手段遵从 UKW C-Thin 和 Greek wheel Gamma 规则。请阅读 Heinz Ulbricht's PhD Thesis 第 9 页(德语)。搜索空间(查找空间)可以更进一步的缩小到仅仅只需要在含有“A”的中间环节进行密钥测试就可以了。另外一条捷径在软件文档中有详细描述。
Runtime Estimates:
运行时间估计:
The key server hands out workunits of the size of 26^4 keys. With a ciphertext length of 180 letters, processing time is around 80min on a Celeron 1.2GHz.
密钥服务器发放给客户端的任务包含有 26^4 个待测密钥,其复杂程度等同于一段含有 180 个字母的加密电文,如果在 Celeron 1.2GHz 处理器上运行,大约需要 80 分钟。
The total search space consists of 7434 workunits. Based on the Celeron, 100 participants running the software 24/7 could walk through the search space in 4 days.
搜索空间(查找空间)总共包括 7434 个任务包。如果在 Celeron 处理器上运行,100 个参与者每天 24 小时不停的运行,大概只需要 4 天就可以完成。
Easy messages break on the first walk through the search space. Tougher ones require more. Based on my experience with messages of this length, there should be a good chance that 1-10 walks will yield a break.
简单的加密信息在一个小的搜索空间里也能很容易得到破解。高强度的加密信息则需要更大的搜索空间。基于我们对加密信息长度的认知经验,好的运气要胜过 1-10 次破解过程。
Mailing List:
邮件列表:
I have set up a mailing list for anything related to the project.
我们设立了一个邮件列表,希望能够方便大家交流一切与本项目有关的问题。
Acknowledgements:
致谢:
I was introduced to hill climbing algorithms by numerous usenet articles by Jim Gillogly. His Cryptologia paper "Ciphertext-Only Cryptanalysis of Enigma" is a great reference for anyone trying to solve classical ciphers using hill climbing or the Index of Coincidence.
我在文中对梯度算法的介绍文字来自 Jim Gillogly 发表在一些新闻组中的文章。他发表的密码术论文“Ciphertext-Only Cryptanalysis of Enigma”为那些试图破解一些经典密码的人们详细介绍了梯度算法(hill climbing,爬山法)和符合系数(Index of Coincidence,并发指数)算法的具体使用方法。
In their Cryptologia paper "Breaking German Army Ciphers" Geoff Sullivan and Frode Weierud show a very efficient way of rewiring the plugboard during the hill climb. My program received a considerable speed-up after incorporating their method. Several shortcuts that reduce the search space can be found in the paper.
在由 Geoff Sullivan 和 Frode Weierud 合作完成的密码术论文“Breaking German Army Ciphers”中给出了一种非常有效的方式在进行梯度算法处理过程中对线路连接板重新步线的方法。我们的程序在合并了他们的方法之后,处理速度的提升相当可观。此外,论文还介绍了几种可用于缩小搜索空间(查找空间)的捷径。
A special thanks goes to Geoff Sullivan for answering questions in sci.crypt, always revealing _exactly_ the right amount of information.
特别要感谢 Geoff Sullivan 在 sci.crypt 新闻组里无私地给我们答疑,Geoff Sullivan 对问题的解答富于启迪、严密而准确,给了我们很大的帮助。
Online References:
在线参考资料:
Enigma overview: http://en.wikipedia.org/wiki/Enigma_machine
Mathematics of Enigma: http://www.nsa.gov/publications/publi00004.cfm
PhD thesis by Heinz Ulbricht (in German): Die Chiffriermaschine Enigma - Trügerische Sicherheit
Paper by Jim Gillogly: Ciphertext-Only Cryptanalysis of Enigma
Paper by Ravi Ganesan and Alan T. Sherman: Statistical Techniques for Language Recognition
Paper by Geoff Sullivan: Cryptanalysis of Hagelin machine pin wheels
Paper by Geoff Sullivan and Frode Weierud: Breaking German Army Ciphers (Now online!)
Contact:
联系我们:
Stefan Krah <website @ bytereef.org> |
评分
-
查看全部评分
|