小儿科加密算法XOR的解密原理

perloicq

已知用XOR加密的字符串十进制表达如下：
69 90 84 18 64 71 88 81 90 18 83 64 94 69 95 18
87 93 73 18 91 71 92 66 66 18 94 68 84 64 17 70
89 87 17 94 80 72 72 18 85 93 86
原文和密匙都只有字母数字和空格。
求密匙和原文。

Perl解法如下：
[PHP]#!/usr/bin/perl

use strict;

# 已知xor过的数据，十进制数列
my @crypt_dec = qw(
69 90 84 18 64 71 88 81 90 18 83 64 94 69 95 18
87 93 73 18 91 71 92 66 66 18 94 68 84 64 17 70
89 87 17 94 80 72 72 18 85 93 86
);

# 转化为字符串
my $crypt = join('', map {chr} @crypt_dec);

# 16进制打印
print unpack("H*", $crypt), "\n";

# 未加密原文只包括如下字符
my @char_set = (' ', 0..9, 'a'..'z', 'A'..'Z');

# xor_table函数，打印以上字符间的XOR，用于建立find_key_length的退出条件
# 现在不用了
#my $xor_table = xor_table(@char_set);

# 找出密匙长度,$xor值用来人工查错
my ($key_len, $xor) = find_key_length($crypt);
print "Key length = ", $key_len, "\n";
print "Xor = ", unpack("H*", $xor), "\n";

my $key = find_key($crypt, $key_len);
print "Key = $key\n";
print "lain = ", decrypt($crypt, $key), "\n";

sub xor_table {
    my $table = {};   # 联想列表存结果
    for (my $i = 0; $i < @_; $i++) {
        for (my $j = $i+1; $j < @_; $j++) {  # 注意@_变量
            my $xor = "$_[$i]"^"$_[$j]";
            if (defined $table->{$xor}) {
                push @{$table->{$xor}}, $_[$i].$_[$j];
            } else {
                $table->{$xor} = [$_[$i].$_[$j]];
            }
        }
    }
    return $table;
}

sub find_key_length {
    my ($crypt) = @_;  # 加密字符串是唯一的参数变量
    my $crypt_len = length($crypt);  # 长度
    # 密匙长度从1往上试
    for (my $key_len = 1; $key_len < $crypt_len; $key_len++) {
        # 把加密的字符串往右循环推移$key_len位
        my $crypt_shift = substr($crypt, $key_len).substr($crypt, 0, $key_len);
        # 计算XOR
        my $xor = $crypt ^ $crypt_shift;
        # 如果XOR结果只包括0x01到0x7f间的字节，大功告成(道理见xor_table函数)
        return ($key_len, $xor) if $xor !~ /[^\x01-\x7f]/;
    }
    return;
}

sub find_key {
    my ($crypt, $key_len) = @_;
    my $crypt_len = length($crypt);
    my @key;
    for (my $i = 0; $i < $key_len; $i++) {
        my @c_i = ();
        $key[$i] = undef;
K_LOOP: foreach my $k (@char_set) {
            for (my $j = $i; $j < $crypt_len; $j+=$key_len) {
                my $c = substr($crypt, $j, 1);
                next K_LOOP unless char_found("$k" ^ "$c", @char_set);
            }
            $key[$i] = $k;
        }
    }
    join("", @key);
}

sub char_found {
    my ($char, @c_list) = @_;
    foreach my $c (@c_list) {
        $c eq $char && return 1;
    }
    return 0;
}

sub decrypt {
    my ($crypt, $key) = @_;
    my $crypt_len = length($crypt);
    my $key_len = length($key);
    my $plain = "";
    for (my $i = 0; $i < $crypt_len; $i+=$key_len) {
        my $block = substr($crypt, $i, $key_len);
        $plain .= "$block" ^ substr($key, 0, length($block));
    }
    $plain;
}

[/PHP]

perloicq

上面的算法有致命错误，表看。

perloicq

先来一个半暴力的解法，下面的xor表列出数字空格和小写字母间的xor值：

0x01: 01 23 45 67 89 bc de fg hi jk lm no pq rs tu vw xy
0x02: 02 13 46 57 ac df eg hj ik ln mo pr qs tv uw xz
0x03: 03 12 47 56 ab dg ef hk ij lo mn ps qr tw uv yz
0x04: 04 15 26 37 ae bf cg hl im jn ko pt qu rv sw
0x05: 05 14 27 36 ad bg cf hm il jo kn pu qt rw sv
0x06: 06 17 24 35 ag bd ce hn io jl km pv qw rt su
0x07: 07 16 25 34 af be cd ho in jm kl pw qv ru st
0x08: 08 19 ai bj ck dl em fn go px qy rz
0x09: 09 18 ah bk cj dm el fo gn py qx sz
0x0a: 28 39 ak bh ci dn eo fl gm pz rx sy
0x0b: 29 38 aj bi ch do en fm gl qz ry sx
0x0c: 48 59 am bn co dh ei fj gk tx uy vz
0x0d: 49 58 al bo cn di eh fk gj ty ux wz
0x0e: 68 79 ao bl cm dj ek fh gi tz vx wy
0x0f: 69 78 an bm cl dk ej fi gh uz vy wx
0x10:  0 aq br cs dt eu fv gw hx iy jz
0x11:  1 ap bs cr du et fw gv hy ix kz
0x12:  2 as bp cq dv ew ft gu hz jx ky
0x13:  3 ar bq cp dw ev fu gt iz jy kx
0x14:  4 au bv cw dp eq fr gs lx my nz
0x15:  5 at bw cv dq ep fs gr ly mx oz
0x16:  6 aw bt cu dr es fp gq lz nx oy
0x17:  7 av bu ct ds er fq gp mz ny ox
0x18:  8 ay bz hp iq jr ks lt mu nv ow
0x19:  9 ax cz hq ip js kr lu mt nw ov
0x1a: bx cy hr is jp kq lv mw nt ou
0x1b: az by cx hs ir jq kp lw mv nu ot
0x1c: dx ey fz ht iu jv kw lp mq nr os
0x1d: dy ex gz hu it jw kv lq mp ns or
0x1e: dz fx gy hv iw jt ku lr ms np oq
0x1f: ez fy gx hw iv ju kt ls mr nq op
0x40: 0p 1q 2r 3s 4t 5u 6v 7w 8x 9y
0x41:  a 0q 1p 2s 3r 4u 5t 6w 7v 8y 9x
0x42:  b 0r 1s 2p 3q 4v 5w 6t 7u 8z
0x43:  c 0s 1r 2q 3p 4w 5v 6u 7t 9z
0x44:  d 0t 1u 2v 3w 4p 5q 6r 7s
0x45:  e 0u 1t 2w 3v 4q 5p 6s 7r
0x46:  f 0v 1w 2t 3u 4r 5s 6p 7q
0x47:  g 0w 1v 2u 3t 4s 5r 6q 7p
0x48:  h 0x 1y 2z 8p 9q
0x49:  i 0y 1x 3z 8q 9p
0x4a:  j 0z 2x 3y 8r 9s
0x4b:  k 1z 2y 3x 8s 9r
0x4c:  l 4x 5y 6z 8t 9u
0x4d:  m 4y 5x 7z 8u 9t
0x4e:  n 4z 6x 7y 8v 9w
0x4f:  o 5z 6y 7x 8w 9v
0x50:  p 1a 2b 3c 4d 5e 6f 7g 8h 9i
0x51:  q 0a 2c 3b 4e 5d 6g 7f 8i 9h
0x52:  r 0b 1c 3a 4f 5g 6d 7e 8j 9k
0x53:  s 0c 1b 2a 4g 5f 6e 7d 8k 9j
0x54:  t 0d 1e 2f 3g 5a 6b 7c 8l 9m
0x55:  u 0e 1d 2g 3f 4a 6c 7b 8m 9l
0x56:  v 0f 1g 2d 3e 4b 5c 7a 8n 9o
0x57:  w 0g 1f 2e 3d 4c 5b 6a 8o 9n
0x58:  x 0h 1i 2j 3k 4l 5m 6n 7o 9a
0x59:  y 0i 1h 2k 3j 4m 5l 6o 7n 8a
0x5a:  z 0j 1k 2h 3i 4n 5o 6l 7m 8b 9c
0x5b: 0k 1j 2i 3h 4o 5n 6m 7l 8c 9b
0x5c: 0l 1m 2n 3o 4h 5i 6j 7k 8d 9e
0x5d: 0m 1l 2o 3n 4i 5h 6k 7j 8e 9d
0x5e: 0n 1o 2l 3m 4j 5k 6h 7i 8f 9g
0x5f: 0o 1n 2m 3l 4k 5j 6i 7h 8g 9f

然后直接分析加密字符串：
[PHP]sub analyze_crypt {
    my ($crypt) = @_;
    my $crypt_len = length($crypt);
    for (my $key_len = 1; $key_len <= 23; $key_len++) {
        print "Try key_len = $key_len:\n";
        for (my $i = 0; $i < $key_len; $i++) {
            print "i = $i\n";
            for (my $j = $i; $j < $crypt_len; $j += $key_len) {
                print join(" ", sort @{$XOR_TABLE->{substr($crypt, $j, 1)}}), "\
n";
            }
        }
        print '='x40, "\n";
    }
}
[/PHP]
所得结果用肉眼很容易就能辨别出key长度。写成程序可能还要花点时间。且听下回分解。

perloicq

正解在此：
[PHP]
#!/usr/bin/perl

use strict;

# 明文只包括如下字符
my @char_set = (' ', 0..9, 'a'..'z'); #, 'A'..'Z');

# xor_table函数，打印以上字符间的XOR
my $XOR_TABLE = xor_table(@char_set);

#foreach my $c (sort keys(%$XOR_TABLE)) {
#    print "0x", unpack("H*", $c), ": ", $XOR_TABLE->{$c}, "\n";
#}

my $plain = "the quick brown fox jumps over the lazy dog";
for my $key (qw(qwe)) {
    my $crypt = xor_crypt($plain, $key);
    #my $p = xor_crypt($crypt, $key);
    #print "Key = $key plain2='$p'\n";
    print "Crypt = 0x", unpack("H*", $crypt), "\n";
    crack_xor($crypt);
}

exit;

sub xor_table {
    my $table = {};   # 联想列表存结果
    for (my $i = 0; $i < @_; $i++) {
        for (my $j = $i + 1; $j < @_; $j++) {  # 参数变量在此
            my $xor = "$_[$i]" ^ "$_[$j]";
            if (exists $table->{$xor}) {
                $table->{$xor} .= $_[$i].$_[$j];
            } else {
                $table->{$xor} = $_[$i].$_[$j];
            }
        }
    }
    return $table;
}

sub crack_xor {
    my ($crypt) = @_;
    my $crypt_len = length($crypt);
GUESS: for (my $key_len = 1; $key_len <= 23; $key_len++) {
        print "Try key_len = $key_len ...";
        my $count = 0;
        my @key_candidates = ();
        for (my $i = 0; $i < $key_len; $i++) {
            $key_candidates[$i] = "";
            my $tested = {};
            my $c_i = substr($crypt, $i, 1);
            my $xor_i = $XOR_TABLE->{$c_i};
            if ($c_i eq "\0") {
                $xor_i = join('', @char_set);
            }
            #print "c[i=$i]=0x", unpack("H*", $c_i), ": $xor_i\n";
      CHAR: foreach my $char (split("", $xor_i)) {
                next if exists $tested->{$char} and $tested->{$char} == 0;
                for (my $j = $i+$key_len; $j < $crypt_len; $j += $key_len) {
                    my $c_j = substr($crypt, $j, 1);
                    if ($c_j eq "\0") {
                        $tested->{$char} = 1;
                        next;
                    }
                    my $xor_j = $XOR_TABLE->{$c_j};
                    #print "c[j=$j]=0x",unpack("H*", $c_j), ": $xor_j <$char> ";
                    if ($xor_j =~ /$char/) {
                        #print "found\n";
                        $tested->{$char} = 1;
                    } else {
                        #print "not found\n";
                        $tested->{$char} = 0;
                        next CHAR;
                    }
                }
            }
            #print "candidate [";
            foreach my $char (keys %$tested) {
                if ($tested->{$char} == 1) {
                    $key_candidates[$i] .= $char;
                    #print "$char";
                }
            }
            #print "]\n";
            if (length $key_candidates[$i]) {
                $count++;
            } else {
                print "failed at i = $i.\n";
                next GUESS;
            }
        }
        if ($count == $key_len) {
            #print "bingo.\nKey candidates: ";
            #for (my $i = 0; $i < $key_len; $i++) {
            #    print "<$key_candidates[$i]>";
            #}
            print "bingo.\n";
            my $total = 1;
            use integer;
            foreach (@key_candidates) { $total *= length };
            for (my $i = 0; $i < $total; $i++) {
                my $key = "";
                foreach my $str (@key_candidates) {
                    $key .= substr($str, ($i % length($str)), 1);
                }
                my $plain = xor_crypt($crypt, $key);
                next if $plain =~ /[^\d a-z]/;
                print "'$key'->'$plain'\n";
            }
        }
    }
}

sub xor_crypt {
    my ($crypt, $key) = @_;
    my $crypt_len = length($crypt);
    my $key_len = length($key);
    my $plain = "";
    for (my $i = 0; $i < $crypt_len; $i+=$key_len) {
        my $block = substr($crypt, $i, $key_len);
        $plain .= "$block" ^ substr($key, 0, length($block));
    }
    $plain;
}

[/PHP]

perloicq

结果不是唯一，只有肉眼才能分辨：

Crypt = 0x051f0051061018140e5115171e000b51110a09570f041a1502570a07121751030d145709100d1c51130a16
Try key_len = 1 ...failed at i = 0.
Try key_len = 2 ...failed at i = 0.
Try key_len = 3 ...bingo.
'qwd'->'thd qticj bsowo fnx kumqs nves tie mazx dng'
'qwe'->'the quick brown fox jumps over the lazy dog'
'qwf'->'thf qvich bqowm flx iumss lveq tke oazz dlg'
'qwx'->'thx qhicv boows frx wumms rveo tue qazd drg'
'qwy'->'thy qiicw bnowr fsx vumls sven tte paze dsg'
'qwz'->'thz qjict bmowq fpx uumos pvem twe sazf dpg'
Try key_len = 4 ...failed at i = 2.
Try key_len = 5 ...bingo.
'arlda'->'dml5gqjxj0terdj0cfm6nvvqc6xkvv0qap6hbax0rxz'
'bsnec'->'gln4erkzk2wdpeh3bdl4mwtpa5yiwt3pcq4kccy2qyx'
'crlfd'->'fml7bsjxh5verfo2cfo3lvvsf4xkts2qar3jbaz5pxz'
'dsnde'->'aln5ctkzj4qdpdn5bdm2kwtqg3yivr5pcp2mccx4wyx'
'frleg'->'cml4avjxk6serel7cfl0ivvpe1xkwp7qaq0obay6uxz'
'gsnfa'->'bln7gwkzh0rdpfj6bdo6hwtsc0yitv6pcr6nccz0tyx'
'arldc'->'dml5eqjxj2terdh0cfm4nvvqa6xkvt0qap4hbax2rxz'
'bsned'->'gln4brkzk5wdpeo3bdl3mwtpf5yiws3pcq3kccy5qyx'
'crlfe'->'fml7csjxh4verfn2cfo2lvvsg4xktr2qar2jbaz4pxz'
'dsndg'->'aln5atkzj6qdpdl5bdm0kwtqe3yivp5pcp0mccx6wyx'
'frlea'->'cml4gvjxk0serej7cfl6ivvpc1xkwv7qaq6obay0uxz'
'gsnfc'->'bln7ewkzh2rdpfh6bdo4hwtsa0yitt6pcr4nccz2tyx'
'arldd'->'dml5bqjxj5terdo0cfm3nvvqf6xkvs0qap3hbax5rxz'
'bsnee'->'gln4crkzk4wdpen3bdl2mwtpg5yiwr3pcq2kccy4qyx'
'crlfg'->'fml7asjxh6verfl2cfo0lvvse4xktp2qar0jbaz6pxz'
...................................

perloicq

NND 这么个小儿科的东西居然花了我这么多时间。
首先异或后的字符串16进制如下：

23 47 33 08 15 45 1d 0a 50 47 3a 19 50 2a 1c 05 1f 5d 72 4e 40 55 41 66 12 4a 72 30 11 17 00 15
50 64 33 10 1c 6f 38 19 1c 4a 72 4d 46 49 52 5e 40 03 61 76 7a 31 1a 05 03 13 3b 0f 50 11 1a 09
50 04 26 14 50 04 1c 02 05 52 3e 5c 23 11 13 18 15 13 3d 1a 50 11 1a 09 50 63 37 0e 1c 45 3d 02
19 5c 3c 5c 03 15 17 09 13 5b 7e 5c 07 0d 17 1e 15 5a 3c 5c 39 45 06 09 1c 5f 72 05 1f 10 52 04
1f 44 72 2c 15 17 1e 4c 19 40 72 18 1f 0c 1c 0b 5e 13 02 19 02 09 52 05 03 13 36 13 19 0b 15 4c
16 5a 3c 19 5c 45 06 04 11 5d 39 5c 09 0a 07 42 50 7d 3d 0b 50 11 1a 0d 04 13 26 14 11 11 55 1f
50 5c 27 08 50 0a 14 4c 04 5b 37 5c 07 04 0b 40 50 7a 75 18 50 09 1b 07 15 13 26 13 50 16 02 09
1e 57 72 08 18 00 52 1e 15 40 26 5c 1f 03 52 18 18 56 72 08 19 08 17 4c 04 56 3e 10 19 0b 15 4c
1a 5c 39 19 03 4b 78 66 24 5b 3b 0f 50 0c 01 4c 04 5b 37 5c 47 11 1a 4c 11 5d 3c 09 11 09 52 3f
04 52 26 19 50 0a 14 4c 04 5b 37 5c 20 00 00 00 50 7c 3c 15 1f 0b 52 1f 00 56 37 1f 18 49 52 1b
18 56 20 19 19 0b 52 25 50 47 37 10 1c 45 0b 03 05 13 3a 13 07 45 22 09 02 5f 72 15 03 45 16 03
19 5d 35 52 50 35 17 1e 1c 13 3b 0f 50 01 1d 05 1e 54 72 1a 19 0b 17 40 50 47 3a 1d 1e 0e 52 15
1f 46 7c 5c 3e 0a 05 4c 04 5b 33 08 50 11 1a 0d 04 14 21 5c 1f 10 06 4c 1f 55 72 08 18 00 52 1b
11 4a 7e 5c 39 42 16 4c 1c 5a 39 19 50 11 1d 4c 03 43 37 12 14 45 06 04 15 13 20 19 03 11 52 03
16 13 26 14 15 45 06 05 1d 56 72 08 15 09 1e 05 1e 54 72 16 1f 0e 17 1f 5e 39 58 35 1e 45 14 0d
13 47 7e 5c 04 0d 17 4c 13 5c 3c 1a 15 17 17 02 13 56 72 13 02 02 13 02 19 49 37 0e 03 45 1a 0d
06 56 72 12 1f 11 1b 0f 15 57 72 08 18 04 06 4c 39 13 21 0c 15 0b 16 4c 1d 5c 21 08 50 0a 14 4c
04 5b 37 5c 04 0c 1f 09 50 47 37 10 1c 0c 1c 0b 50 59 3d 17 15 16 5c 4c 23 5c 72 19 11 06 1a 4c
09 56 33 0e 50 11 1a 09 09 13 35 15 06 00 52 01 15 13 33 5c 1c 0c 06 18 1c 56 72 10 15 16 01 4c
04 5a 3f 19 5c 45 01 03 50 7a 72 14 11 13 17 4c 04 5c 72 1f 18 0a 02 4c 1f 46 26 5c 1d 0a 00 09
50 5c 34 5c 04 0d 17 4c 03 56 20 15 1f 10 01 4c 03 46 30 16 15 06 06 4c 1d 52 26 08 15 17 52 1f
1f 13 33 0f 50 11 1d 4c 1c 56 33 0a 15 45 06 05 1d 56 72 1a 1f 17 52 18 18 56 72 16 1f 0e 17 1f
5e 39 58 39 08 11 00 0d 00 5c 3e 1d 04 0c 1c 0b 50 40 37 0a 15 17 13 00 50 4a 37 1d 02 16 52 05
1e 47 3d 5c 04 0d 17 4c 16 46 26 09 02 00 5e 4c 04 5b 37 05 57 09 1e 4c 15 45 37 12 04 10 13 00
1c 4a 72 1f 18 0a 02 4c 1d 4a 72 08 19 08 17 4c 14 5c 25 12 50 11 1d 4c 04 56 3c 5c 03 00 11 03
1e 57 21 52 50 2c 55 00 1c 13 3a 1d 06 00 52 06 05 40 26 5c 15 0b 1d 19 17 5b 72 08 19 08 17 4c
04 5c 72 0f 11 1c 48 4c 52 7a 75 11 50 17 17 0d 1c 5f 2b 50 50 17 17 0d 1c 5f 2b 5c 15 1d 11 05
04 56 36 5c 11 07 1d 19 04 13 25 14 11 11 52 05 03 13 3a 1d 00 15 17 02 19 5d 35 5c 07 0c 06 04
50 63 37 0e 1c 45 06 04 19 40 72 05 15 04 00 42 50 72 3c 18 50 2c 55 08 50 5f 3b 17 15 45 06 03
50 52 3c 12 1f 10 1c 0f 15 13 26 14 11 11 5e 4c 11 55 26 19 02 45 1e 09 1e 54 26 14 09 45 1c 09
17 5c 26 15 11 11 1b 03 1e 40 7e 5c 37 10 1b 08 1f 13 33 12 14 45 3b 4c 18 52 24 19 50 03 1b 02
11 5f 3e 05 50 01 17 0f 19 57 37 18 5e 4b 5c 4c 4c 54 3d 12 17 5b 52 37 52 67 3b 11 15 42 01 4c
05 43 7c 5c 3e 00 0a 18 50 40 22 19 11 0e 17 1e 50 43 3e 19 11 16 17 4e 2d 39 58 2b 15 09 1e 40
50 4a 3d 09 50 01 1b 08 1e 14 26 5c 02 00 13 00 1c 4a 72 0b 11 0b 06 4c 04 5c 72 17 1e 0a 05 4c
04 5b 33 08 50 04 1c 15 07 52 2b 52 5e 4b 78

Perl程序如下:
[PHP]#!/usr/bin/perl

use strict;

my $DEBUG = 1;
my @CHAR_SET = ("\t", "\r", "\n", map { chr } (32..126));
my $XOR_TABLE = xor_table(@CHAR_SET);
my $ALL_CHARS = join('', @CHAR_SET);

if ($DEBUG) {
    foreach my $c (sort keys(%$XOR_TABLE)) {
        print "0x", unpack("H*", $c), ": ", $XOR_TABLE->{$c}, "\n";
    }
}

my $plain = join('', <DATA>);   # 明文在程序后__DATA__里

my $key = 'p3R|perl';
my $crypt = xor_crypt($plain, $key);
if ($DEBUG) {
    my $p2 = xor_crypt($crypt, $key);
    die "xor error\n" unless $p2 eq $plain;
    print "Key = '$key'\n";
    print "Crypt:\n", hexdump($crypt);
}
crack_xor($crypt);

exit;

sub xor_table {
    my $table = {};   # 联想列表存结果
    for (my $i = 0; $i < @_; $i++) {
        for (my $j = $i + 1; $j < @_; $j++) {
            my $xor = "$_[$i]" ^ "$_[$j]";
            if (exists $table->{$xor}) {
                $table->{$xor} .= $_[$i].$_[$j];
            } else {
                $table->{$xor} = $_[$i].$_[$j];
            }
        }
    }
    return $table;
}

sub crack_xor {
    my ($crypt, $max_key_len) = @_;
    defined $max_key_len or $max_key_len = 23;
    my $crypt_len = length($crypt);
    return if $crypt_len < @CHAR_SET;
    $max_key_len = $crypt_len if $max_key_len > $crypt_len;
GUESS: for (my $key_len = 1; $key_len <= $max_key_len; $key_len++) {
        print "Try key_len = $key_len ...";
        my $count = 0;
        my @key_candidates = ();
        for (my $i = 0; $i < $key_len; $i++) {
            $key_candidates[$i] = "";
            my $tested = {};
            my $c_i = substr($crypt, $i, 1);
            my $xor_i = $XOR_TABLE->{$c_i};
            $xor_i = $ALL_CHARS if $c_i eq "\0";
            print "c[i=$i]=0x", unpack("H*", $c_i), ": $xor_i\n" if $DEBUG;
      CHAR: foreach my $char (split("", $xor_i)) {
                next if exists $tested->{$char} and $tested->{$char} == 0;
                for (my $j = $i+$key_len; $j < $crypt_len; $j += $key_len) {
                    my $c_j = substr($crypt, $j, 1);
                    if ($c_j eq "\0") {
                        $tested->{$char} = 1;
                        next;
                    }
                    my $xor_j = $XOR_TABLE->{$c_j};
                    print "c[j=$j]=0x",unpack("H*", $c_j), ": $xor_j <<$char>> " if $DEBUG;
                    my $regexp = $char;
                    $regexp =~ s/(\W)/\\$1/g;
                    if ($xor_j =~ /$regexp/) {
                        print "found\n" if $DEBUG;
                        $tested->{$char} = 1;
                    } else {
                        print "not found\n" if $DEBUG;
                        $tested->{$char} = 0;
                        next CHAR;
                    }
                }
            }
            print "candidate [" if $DEBUG;
            foreach my $char (keys %$tested) {
                if ($tested->{$char} == 1) {
                    $key_candidates[$i] .= $char;
                    print "$char" if $DEBUG;
                }
            }
            print "]\n" if $DEBUG;
            if (length $key_candidates[$i]) {
                $count++;
            } else {
                print "failed at i = $i.\n";
                next GUESS;
            }
        }
        if ($count == $key_len) {
            print "bingo.\n";
            print "Key candidates: ";
            for (my $i = 0; $i < $key_len; $i++) {
                print "<$key_candidates[$i]>";
            }
            print "\n";
            examine($crypt, @key_candidates);
        }
    }
}

sub xor_crypt {
    my ($crypt, $key) = @_;
    my $crypt_len = length($crypt);
    my $key_len = length($key);
    my $plain = "";
    for (my $i = 0; $i < $crypt_len; $i+=$key_len) {
        my $block = substr($crypt, $i, $key_len);
        $plain .= "$block" ^ substr($key, 0, length($block));
    }
    $plain;
}

sub examine {
    my ($crypt, @key_candidates) = @_;
    my $total = 1;
    my @keys;
    combinations(\@keys, @key_candidates);
    foreach my $key (@keys) {
        my $plain = xor_crypt($crypt, $key);
        if ($plain =~ /[^ -~\n\t\r]/s) {
            print "Key '$key' discarded: found junk char\n";
            next;
        }
        if ($plain !~ /\s\S{1,3}\s/s) {
            print "Key '$key' discarded: could not find word with 1 to 3 letters\n";
            next;
        }
        if ($plain =~ /\S{20}/s) {
            print "Key '$key' discarded: found word with 20 chars\n";
            next;
        }
        print "Key '$key' produces the following text:\n",
              '='x79, "\n$plain\n", '='x79, "\n";
    }

}

sub combinations {
    my ($aref, @cand) = @_;
    return unless @cand;
    my @chars = split('', shift @cand);
    my $count = @$aref;
    die "Too many combinations\n" if $count > 1000000;
    if ($count == 0) {
        push @$aref, @chars;
    } else {
        for (my $i = 0; $i < $count; $i++) {
            my $x = shift @$aref;
            foreach my $c (@chars) {
                push(@$aref, $x . $c);
            }
        }
    }
    combinations($aref, @cand);
}

sub hexdump {
    my $str = pop;
    return unless defined $str;
    my $res = "";
    my $len = length($str);
    for (my $i = 0; $i < $len; $i += 16) {
        my $s = substr($str, $i, 16);
        my $hex = unpack('H*', $s);
        $s =~ s/[\x00-\x1f]/./g;   # 0x00-0x1f will screw up terminal
        $hex =~ s/(\w\w)/$1 /g;
        $res .= sprintf("%-48s    %s\n", $hex, $s);
    }
    return $res;
}

__DATA__
State of the Onion 2003
by Larry Wall
July 16, 2003

This is the 7th annual State of the Perl Onion speech, wherein I tell you how Perl is doing. Perl is doing fine, thank you. Now that that's out of the way, I'd like to spend the rest of the time telling jokes.

This is the 7th annual State of the Perl Onion speech, wherein I tell you how Perl is doing. Perl is doing fine, thank you. Now that that's out of the way, I'd like to spend the rest of the time telling jokes.

In fact, the conference organizers have noticed that I spend most of the time telling jokes. So each year they give me a little less time, so I have to chop out more of the serious subject matter so as to leave time for the jokes.

Extrapolating several years into the future, they'll eventually chop my time down to ten seconds. I'll have just enough time to say: "I'm really, really excited about what is happening with Perl this year. And I'd like to announce that, after lengthy negotiations, Guido and I have finally decided... <gong> ["Time's up. Next speaker please"]

Well, you didn't really want to know that anyway...
[/PHP]

kj501

NND 这么个小儿科的东西居然花了我这么多时间。

看来把一个想法真正实现也不是一件容易的事。