衒思力発電所

TWOR 解析 (2)

前回の続き．

http://dvorak.jp/archive/twor_subekey_sample.zip (9.5 MiB)

今回は，前回得た上記の一次元のサンプリングデータから何がわかるか^*1調べてみよう，というようなことをやってみる．

いきなりものものしいアルゴリズムで始めるのもなんなので，手始めに各 1 文字の出現頻度を調べてみる．「特に頻出の文字」 「頻度が少ない文字」 などが存在するかしないかが調べられることになる．

twor1.py とかこういうのを書いて実行：

  : 1200046
! : 199954
" : 199460
# : 200069
$ : 199927
% : 199931
& : 199930
' : 200294
( : 199659
) : 200283
* : 199927
+ : 199899
, : 200310
- : 199874
. : 199737
/ : 200209
0 : 199993
1 : 199899
2 : 200050
3 : 199829
4 : 200182
5 : 200006
6 : 200281
7 : 199667
8 : 200237
9 : 199911
: : 199861
; : 199832
< : 200267
= : 199679
> : 200304
? : 200360
@ : 199668
A : 199954
B : 200003
C : 199883
D : 200087
E : 199996
F : 199927
G : 200400
H : 200056
I : 200023
J : 200288
K : 200199
L : 199780
M : 200053
N : 200065
O : 199758
P : 200170
Q : 200037
R : 200035
S : 199964
T : 200514
U : 199946
V : 200023
W : 200192
X : 199963
Y : 199992
Z : 200273
[ : 200189
¥ : 200251
] : 199424
^ : 200156
_ : 199728
` : 199701
a : 199627
b : 200106
c : 199833
d : 199730
e : 200364
f : 200088
g : 199896
h : 200362
i : 199858
j : 199859
k : 200213
l : 199734
m : 199618
n : 200157
o : 199661
p : 199895
q : 200209
r : 199978
s : 200187
t : 199971
u : 199870
v : 200162
w : 200104
x : 199982
y : 200081
z : 199733
{ : 200160
| : 199946
} : 199874
~ : 200177

直感的に以下のふたつのことが推測できる^*2．

• ほとんどの文字の出現頻度は同じ
• スペースの出現頻度は，他の文字の 6 倍

文字単位で見るとスペース除けば全て同じ頻度っていうのは，意外性がないというか，完全ランダムならそうだろうし常識的にそうだろうなっていう気がしますが，もうちょっと後の考察を踏まえると再び意味を持つかなと思うので，一応押さえておきたいポイント．

スペースの頻度が他の文字の 6 倍（きれいな倍数）というのは素直に面白い結果． これだけ見ても，出題文字列は単なるランダムではなくある程度考えられたロジックに基づくものなんじゃないかなぁという香りはしてくる．

今度は文字単位ではなくて， 隣り合った 2 文字をセットにして，2 文字セットの出現頻度を見てみよう^*3． たとえば 「ab」 と 「ac」 では頻度が異なるだろうか？ とかいう話ね．

先ほどのスクリプトを手直しして，n 文字セットでカウントできるようにする（twor2.py）． 出力を使いやすいように，区切り文字はタブ文字に変えた．

n = 2 とした結果の抜粋 （全体は若干サイズあるのでリンク）：

aa  2389
ab  2990
ac  663
ad  3432
ae  844
af  2257
ag  3465
ah  663
ai  4425
aj  1388
ak  2179
al  4743
am  389
an  5731
ao  2296
ap  2034
aq  6466
ar  429
as  6337
at  3326
au  2318
av  7572
aw  811
ax  6494
ay  4588
az  2299
a{  209
a|  51
a}  183
a~  27

ということで，2 文字にしてめでたく偏った． 先に文字単位の頻度は等しいことを確認しているので，「av」は 7572 回あって，「a~」は 27 回しかないという 100 倍オーバーの差は，有意とかそういうレベルではない^*4明々白々たる偏りである．

この時点で

• 一文字単位で都度ランダムに取ってきた文字を並べているわけではない
• 頻出の文字列パターンがどうやら存在する

ことが言える．第一目標は達成した^*5．

次に気になるのは当然パターンそのものがどうなっているのか．

といってもいきなりその詳細は調べようがないので，各文字列長 n についてもっとも頻度が高い一団を抽出し，そこから法則が推測できないかとやってみる．

すなわち頻度を調べる文字列長を n = 3, 4, 5, 6 と大きくしていく．ただ，さっきまで使ってた馬鹿アルゴリズムでカウントするのは効率的にアレなので，ここらでインデクスを作っておくような賢いアルゴリズムを使うことにする．

自分で実装は面倒なので SUFARY を使った． 先に mkary でインデクスを作っておけば，

sang -n 6 -t 1000 out2.txt

とすることで長さ 6 文字の部分文字列のうち 1000 回以上出現したものがそれなりに高速に出力される，とかそんな感じ（-t 指定しなければ全部出る）．

これを利用して調査したところ，

• 3 文字では閾値 3000 くらいで最頻出の一団が取り出せる^*6 （twor3_out.txt）
• 4 文字では 2000 くらい （twor4_out.txt）
• 5 文字では 1300 くらい （twor5_out.txt）
• 6 文字では 1000 くらい （twor6_out.txt）
• 7 文字では 500 くらい （twor7_out.txt）

となった．

これはまた色々なヒントが隠された結果に思える．

まず，6 文字とかいう割と長い設定でも， 10 万回に 1000 回以上出現しているパターンが 100 オーバー見つかったということ．これは練習したりする上で実用に耐えるレベルのパターンだ．

そして，n 文字から n+1 文字へと一文字増える毎に約 2/3 とかそれくらいに最頻出の一団の頻度が減っているわけだけど，n+1 文字目には均等に文字が出てくると仮定した場合にはこれは 1/95 になるはず^*7なので， 2/3 という減り方は超ゆるやか．ちなみに，ここには載せなかったが n = 8 とか n = 9 でもいきなり 1/95 になることはなかった．それ以上になるとサンプル数が十分でなく，S/N 比が小さくなってくるので参考にならないが．

感覚的には明らかだけど一応ついでに書くと，n+1 文字のパターンは n 文字のパターンに新たな 1 文字を付け加えたものになっている．ただし，n 文字のパターン全てに，対応する n+1 文字のパターンが存在するわけではない．

このことから，以下のことが推測できる：

• 長さの決まったパターンの基本単位のようなものは無い
  　（少なくとも長さ 9 以下ではありえない）
• パターンの元（ソース文字列）があるとすればそれは十分に長く，その部分が実際の頻出パターンとして表れている

さらにこれは根拠のない話だけど，一文字ごとに約 1/3 の確率でソース文字列からの転写の継続をやめ，別のパターン（ソースの別の位置？）に飛ぶというような処理を考えれば，上記のように最頻出のパターンの出現数が減ることに説明がつくかも．

この辺りになるとまだ俺もあんまり確信していることは多くなくて^*8，推測とかばかりになってきて申し訳ないが，ここで特筆に値するポイントがある．

twor6_out.txt を見て，眺めてみて何か感じないだろうか．

わかりやすそうなところを貼ると

1091 AQt%Aa
1058 BRu&Bb
1107 CSv'Cc
1023 DTw(Dd
1069 EUx)Ee
1088 FVy*Ff
1029 GWz+Gg
1091 HX0,Hh
1011 IY1-Ii

もう分かったと思うのでもったいぶらずにいけば，文字列の各文字をアルファベット順に「ずらす」^*9と次のパターンの文字列になっている．

• 文字を「ずらす」操作がなんらかの法則に従って行われている

ことが推測される．そして，そうして「ずらす」ことによって作れるパターン群をまとめて（オリジナルパターンとでも呼ぶか） 1 つとして数えると，

• 6 文字の最頻出オリジナルパターンは 2 種類
• 5 文字では 3 種類
• 4 文字でも 3 種類
• 3 文字では 4-5 種類

等と，その数が激減する．このことを踏まえて，「ずらして作れる文字列」を同一視して改めて初めから調べてみると何かわかるかもしれない^*10．

要素の列挙になっていて本質的な解析が全然進んでいないという話はあって，これらの情報を統合できるのかどうか甚だ怪しいんですが，まあヒントは少ないより多い方がいいに決まっている．

さらにもう一点（One more thing…）．

今まで部分文字列に注目してきたけど，ちょっと視点を変えて，out2.txt をそのままソートしてみたらどうなるだろうか，とやってみた．
（twor_subekey_sample_sorted.zip）

適当に切り出してきた一部分はこんな感じ：

]a0{=f&.Pjp7Ko4[Ft*( yt  38;d7.DY#{_S(#NN#)_n(¥Ni-A c<-XXr`HSwEg10;Rv5~qq!Ial&XL++ k&/MU9>bt4]Cey|Q3] fn=Au#.FVx)Kk-#Pz7 TZ[ Yo'`d3~@i);Tns!Nr7^Iw-+C1w  6">g";Gb&~|W+&QQ:?A0? Zu]MKp|^jj3BUe8Qt$$|d8)G2
]a0{=f&.PjpAKo4[Ft*J y] j38;d7.DY#{_S(#NN-< w< Wr@JHm_@gg~ Q' Nq!Cca5HDzz*Rku/g9>>Ht/]W)*|l3$ 0nAAa# Fpx{K4-[Oe6<Tt@OY8'Jd.~Dix: m#D~r<^cw1MX1' R6@WM hp?CHZ/GWy*Llj$QL88Vas ap({e42¥je<<ot"Ot8_Jx.,E2x 
]a0{=f&.Pkp7Ko4[Ft*( yt  38;d7.DY#{_T(#NN-< w< Wr@JHm_@gg0 Qb5Nq!!_a5&Dzz*Rku/gU>>Ht/]We*|l3$ Ln8Aa# Fpx{K4-[FVy*Ff)8Lw4 LR/^Rh!@Rr?+X8'JXdv dt- d31[jf=>jp7Lq5]Hp&$ wr}~v1*X2) T1<:J83EFT$[ Z?KfZz{Vf&Q
]a0{=f&.PkpAKo4[Ft*J y] j38;d7.DY#{_T(#NN-< w< Wr@JHm_@gg~ Q' Nq!Dca5HDzz*Rku/g9>>Ht/]W)*|l3$ 0nAAa# Fpx{K4-[Pe6<Tt@OY8'J<Zr1[ bw_O1r~dl; D!,DSv&Ih+!Mw4 RXp}Wm%]b0y>gb./kq8Lp5¥Gu+(Azu  39<e8/EZ$|`T)$O
]a0{=f&.Qkp7Ko4[Ft*( yt  38;d8.DY#{_T(#NN-< w< Wr@JHm_@gg0 Qb5Nq!!_a5&Dzz+Sku/gU>>Ht/]We*|l3$ Ln8Aa# Fpx{K4-[Pe6<Tt@-Y8'Jdi~Eix; n#D~r<^c/?Az> Zt]LJo|]ij BT)AQs$Ffc7KF12OUm`Tj"[Yyw;dY,,~n5' 2?DDc& Hr}
]a0{=f&.Qkp7Ko4[Ft*( yt  38;d8.DY#{_T(#NN-< x< Xr@JHm_[gg0 Rb5Nq!!_a5&Dz0+Sku/hU>>Ht/]We*|l3$ Ln8Aa# Fpx{K4-[$=Id( iY-KS7<[r2[ cw`O1r~dl; EW,DSv&Ihf!MI45RXp}Wm%]b1y>gb./kq8Lp5¥Gu+(Azu  P9<{U/EZYy`Td$O
]a0{=f&.QkpAKo4[Ft*J y] j38;d7.DY#{_T(#NN-< w< Wr@JHm_@gg~ Q' Nq!Dca5HDzz*Sku/g9>>Ht/]W)*|l3$ 0nAAa# Fpx{K4-[Pe6<Tt@OY8'Jd.~Eix; m#D~r<^cw1MX1' R6@WM! Gv&,|q+_Qk:CAf?:Za]}K9|Hj4 WTyB tt39<e8/EZ$|`T)$O
]a0{=f&.QkpAKo4[Ft*J y] j38;d8.DY#{_T(#NN-< x< Xr@JHm_[gg~ R' Nq!Dca5HDz0+Sku/h9>>Ht/]W)*|l3$ 0nBAa# Fpx{K4-[Pe6<Tt[OY8'Jd.~Eix; n#D~r<^cw2MX1' R6@WM! Gv&,|q+_Qk:DAf?:Za]}K9|Hj4 WTyB ttGLd=Ka2.Ppn(UP#
]a0{>f&.Qkp7Kp4[Ft*(Ayt  38;e8.EY${_T($NNYdw ds,~i75_mi?@Dx&:H#}MMm/HR1BCW'] b@)gf5 ak+=Vp^FPu9`Ky/Pt3| o8GYj$=Jd) iY-KS7<¥r2[Acw`O1r dl; EW,DTv'Iif!NI45RXp}Wm%^b1z>gb//lq8Lp5¥Gu+)Azu  P9<{U/EZZy`Ud$O
]a0{>f&.Qkp7Lp4¥Fu*(Ayu  38<e8.EY${_T($NO-= x< Xr[KHm`[gh1 Rb6Oq"!_a5&D00+Sku:hU?>Hu/]We*|l3% Lo8Ba$ Fpx{K4-¥Pe7<Ut[-Z8'Jdj~Eiy; n$D~s=^cw2+X1( S6[>M"6HH',|q+_Ql:DBf?:aa^}K9}Hj4 WUzB tt$Ldo)a2..Bn)=P#
]a0{>f&.Qkp7Lp4¥Fu*(Ayu  38<e8.EY${_T($NO-= x< Xr[KHm`[gh1 Rb6Oq"!_a5&D00+Sku:hU?>Hu/]We*|l3% Lo8Ba$ Fpx{K4-¥Pe7<Ut[-Z8'Jdj~Eiy; n$D~s=^cw2+X1( S6[>M"6HH',|q+_Ql:DBf?:aa^}K9}Hj4 WUzB tt$Ldo)a2..Bn)e$O

こんな大きなヒントを今まで見逃していたとは． これは決して OCR で読み込むときに同じ回を二度記録してしまったとかいうものではない^*11．また文字列長は 200 だから，たった 10 万回の試行でたまたま同じようなものが出ましたとかいう偶然でもありえない．すなわち，全体としてこれだけ似ているワードが出題されることがあるのだ．

何より注目するべきは，途中はもちろん最後の方に至るまで（数パターンはあるけども）類似性が見られること．ここから，文字列を生成している途中に乱数に応じてまったく違うパターンに遷移して戻ってこないということはあまりなさそうで，初期値がまずあって，その初期値が何らかの形で後々にも再利用されるようなロジックであることが推測される．

これまでのヒントと合わせてまた根拠無く考えれば，長大なソース文字列のどの地点から読み始めるかを乱数で決定し（初期値），順次そこから読んで出題文字列として採用していくが，その都度ある確率で文字をずらしたり，別の場所から x 文字読み出して代用するような処理が挟まることがある……というような処理を書けばこのような結果が得られる気がする．十分条件のひとつに過ぎないけど．

まあとにかく

• 出題文字列の生成においては，初期値依存性がとても高い

ことは確か．

というわけで，調べたり無いところもあるが，基本的性質いくつかが示され，頻出パターンといってもいいものの存在が確信でき，さらに，役立ちそうなヒントがたくさん見つかった． まだこれらをつなぎあわせるには至っていないが，何歩かは進めた気がする．

# それにしても，今回出てきたことのほとんど全てを経験的に見抜いていたとりのさんがすごすぎる

次回予告

TWOR を取り巻くオカルトじみた噂． 「時間帯によってワードの傾向が変わる」．

多くのタイパーがそのことを示唆し，表舞台を去っていった．

時を刻まない時計，二次元サンプリングデータは，その詳細を解き明かすことができるのか．

次回 「静止した時の中で」 

この次も，サービスしちゃうわよ！

1. わざわざこのように断る理由は，エントリ末尾次回予告にあるように時間を考慮にいれる必要性を感じるから． [↩]
2. 暇なら標本分散計算するなどして検証するべき． [↩]
3. 要するに N-gram 分解の頻度チェックをやっている． [↩]
4. 本当は検定ｒｙ [↩]
5. なんも証明してないけど． [↩]
6. 4000 とか 5000 とかある子は，スペースを含んでいる．スペースは先に調べたとおり頻度が 6 倍であるのでその影響と考えられる．一旦無視． [↩]
7. すべキーの文字種は 95． [↩]
8. 試行錯誤しながらエントリ書いてる段階だ． [↩]
9. ちゃんと言えば ascii code を +1 する． [↩]
10. まだやってない．方法としてはある文字と次の文字の文字コードの差を取ったデータを解析すればいいと思う．興味湧いた方はチャレンジして情報公開してくれると俺が楽できて助かりますので遠慮なくどうぞ． [↩]
11. 元々のサンプルデータでは隣り合ってないし． [↩]

Trackback URL

コメント (6) to TWOR 解析 (2)

コメントをどうぞ