【科学技术(11)】
恢复被粉碎的文件
伍加，2011年12月10日，周六
拿一面镜子，在地上摔碎，然后再把玻璃碎片对接起来使得“破镜重圆”，这件事有多难？
“那得看镜子被摔成了几片，”你会问，“如果只摔成两、三片，这件事很容易。”
如果把镜子摔碎变成成千上万的玻璃碎渣，要想使它再破镜重圆就没那么容易了；正如中文里的又一句成语所说：覆水难收，一去不返。当然，“破镜重圆”这个成语在中文里有特殊的引申含义，用来比喻夫妻失散或离婚后重新团聚；本文中的“破镜重圆”只是指它的字面意思，没有其它引申意义。
从科学研究和技术应用的角度，“破镜重圆”具有重要的现实意义。比如在证据学和鉴识学中，收集证据和恢复证据都很重要。当犯罪嫌疑毁灭了证据文件后，如何恢复这些被粉碎的文件？在电子数字通信中，被传输的数据会因为各种各样的原因在传输过程中部分丢失，如何进行纠错恢复？在军事上，攻破敌方指挥机关之后，会发现许多机密文件已经被粉碎机处理过了，如何恢复这些被粉碎的文件？在计算机鉴识学中，恢复被删除、被粉碎过的电子文件也是一项重要课题。正是因为“破镜重圆”的重要科学和军事意义，美国国防部高级研究计划局（DARPA，Defence Advanced Research Projects Agency）最近组织了一项“破镜重圆”的公开大奖赛【1】，共有 9000 个小组参赛。
从 10 月 28 日开始，经过 33 天的时间，来自于旧金山的一个三人小组解决了全部五个问题，赢得了五万美元的奖金。这个获胜团队里的三名队员都是电脑程序设计师，队长 Otavio Good 是一位编程高手，擅长开发电子游戏。他们的方法是使用一个计算机视觉算法把碎纸片上的字形进行自动拼接，再由人来做最后的验证。用这种计算机辅助工具，他们把粉碎成一万多片的碎纸条完整无误地拼接了起来。
在这次竞赛中，DARPA 共提出了五个被粉碎的文件。这五个难题（Puzzle）一个比一个更复杂、更困难，第一个难题有 224 个碎片，第二个难题有 373 个碎片，第三个难题有 1115 个碎片，第四个难题有 2340 个碎片，第五个难题有 6068 个碎片。最初，有些专家认为根本就不可能有系统的解决方法，更不用说在这么短的时间之内就拿出答案。DARPA 虽然是个军事科研部门，他们也想通过公开竞赛来吸收民间智慧。事实证明，第一个难题在一周之内就被攻破；前三个难题在 23 天之内被解决；全部五个难题在 33 天里被全部解决。下面列出前三个难题及它们的答案：
Puzzle 1: 
Puzzle 2：   
Puzzle 3：   
最近驻德黑兰的英国大使馆受到伊朗民众的攻击，这使人们想到 1979 年美国大使馆被伊朗人占领的旧事。当时，尽管美国使馆的工作人员把机密文件用碎纸机粉碎了，但是他们没有来得及把粉碎后的碎片烧掉。据说伊朗人缴获了那些碎纸片后，花费了大量的人力恢复出了机密原文。那是成千上万名编制波斯地毯的能工巧匠们的成就，他们用灵巧的双手，耗费多年的时间才获得成功。而今天使用计算机辅助工具，采用电脑视觉算法，三个人花 33 天就解决了五个十分复杂的“破镜重圆”难题。
通常，人们对于机密文件的处理就是简单地用碎纸机将它粉碎了之，就连军事部门和安全部门也是这么做的。这项“破镜重圆”公开大赛的结果告诉我们，简单粉碎文件是不能保密的。对于高度敏感的资料，必须有更可靠的毁密方法。
参考文献：
【1】DARPA，Shredder Challenge， http://www.shredderchallenge.com/ ， October 27, 2011 -- December 2, 2011。
【2】DARPA，”DARPA’s Shredder Challenge Solved, http://www.darpa.mil/NewsEvents/Releases/2011/12/02_.aspx, December 2, 2011.
【3】 DARPA Shredder Challenge, Puzzle Solutions, http://www.shredderchallenge.com/puzzlefiles/Puzzle%20Solutions.pdf, December 7, 2011.
伍加，2011年12月10日，周六
http://blog.creaders.net/invictus/
|
