Probelm 59 - Project Euler

30分プログラム、その337。Problem 59 - Project Euler。

(訳者注: 文字コードの説明は適当です) 各文字はそれぞれ一意のコードに割り当てられている. よく使われる標準としてASCII (American Standard Code for Information Interchange) がある. ASCIIでは, 大文字A = 65, アスタリスク (*) = 42, 小文字k = 107というふうに割り当てられている.
モダンな暗号化の方法として, テキストファイルの各バイトをASCIIに変換し, 秘密鍵から計算された値とXORを取るという手法がある. XOR関数の良い点は, 暗号化に用いたのと同じ暗号化鍵でXORを取ると平文を復号できる点である. 65 XOR 42 = 107であり, 107 XOR 42 = 65である.
破られない暗号化のためには, 鍵は平文と同じ長さのランダムなバイト列でなければならない. ユーザーは暗号文と暗号化鍵を別々の場所に保存する必要がある. また, もし一方が失われると, 暗号文を復号することは不可能になる.
悲しいかな, この手法はほとんどのユーザーにとって非現実的である. そこで, 鍵の変わりにパスワードを用いる手法が用いられる. パスワードが平文より短ければ (よくあることだが), パスワードは鍵として繰り返し用いられる. この手法では, 安全性を保つために十分長いパスワードを用いる必要があるが, 記憶するためにはある程度短くないといけない.
この問題での課題は簡単になっている. 暗号化鍵は3文字の小文字である. cipher1.txtは暗号化されたASCIIのコードを含んでいる. また, 平文はよく用いられる英単語を含んでいる. この暗号文を復号し, 平文のASCIIでの値の和を求めよ.

暗号解読か。英単語だということが分っているので、暗号化された文字列の頻度表と英語の頻度表をみくられべて、適当なキーを想像する。そして、それを用いて復号してみて、意味のある言葉になっているかを調べるという、場当り的な方法で解いた。
ちなみに答えの「The Gospel of John」はヨハネの福音書のことらしいです。Johnはジョンじゃなくてヨハ(ネ)のことらしいです。

使い方

$ perl problem59.pl cipher1.txt
# 頻度表
First
------------------------------
71: 70
 2: 48
...

Second
------------------------------
79: 85
 7: 35
...

Third
------------------------------
68: 77
 1: 41
...

# 復号した文章
(The Gospel of John, chapter 1) 1 In the beginning ...

# 答え
107359

ソースコード

#! /usr/bin/perl
# -*- mode:perl; coding:utf-8 -*-
#
# problem59.pl -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/07/09 22:14:48
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

use strict;
use warnings;
use Data::Dumper;

# 頻度表の作成
sub hist(%){
    my (%hash) = @_;
    for(sort {$hash{$b} <=> $hash{$a}} keys %hash){
	printf "%2d: %d\n",$_,$hash{$_};
    }
}
my (%first,%second,%third);
my @xs = <>;
my @code = split ",",join('',@xs);

for(my $i=0; $i < @code ; $i += 3){
    $first{$code[$i]}    += 1;
    $second{$code[$i+1]} += 1 if($i+1 < @code);
    $third{$code[$i+2]}  += 1 if($i+2 < @code);
}
print "First\n","-"x30,"\n";
print hist(%first);

print "Second\n","-"x30,"\n";
print hist(%second);

print "Third\n","-"x30,"\n";
print hist(%third);

# decode
my $sum = 0;
for(my $i=0; $i < @code ; $i += 3){
    my $x = $code[$i]   ^ ord('g');
    my $y = $i+1 > $#code ? 0 : $code[$i+1] ^ ord('o');
    my $z = $i+2 > $#code ? 0 : $code[$i+2] ^ ord('d');
    print chr($x);
    print chr($y);
    print chr($z);
    $sum += $x+$y+$z;
}
print "\n";
print "$sum\n";

参考

• 過去の30分プログラム
• Problem 59 - PukiWiki