3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

PrologAdvent Calendar 2017

Day 7

Prologによるエニグマ暗号器

Last updated at Posted at 2017-07-23

#はじめに

計算機科学者チューリングが破ったことで有名な暗号機エニグマについて、理解を深めるためにPrologでその仕組みを記述しました。

#エニグマの概要
初期のものはアルファベット26文字の刻まれたローターが3枚とプラグで構成されていました。下記のシミュレーターが直観的な理解を与えてくれます。
http://enigmaco.de/enigma/enigma.html

詳細はWikipediaをご参照ください。
https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%8B%E3%82%B0%E3%83%9E_(%E6%9A%97%E5%8F%B7%E6%A9%9F)

#Prologによる実装の使い方

述語enigma/3がその本体です。第1引数に平文あるいは暗号文をリスト形式で与えます。第2引数にローターの初期値をリストで与えます。第3引数には暗号化されたもの、または、復号された平文がリストとして与えられます。

| ?- enigma([h,e,l,l,o],[j,q,d],X).
X = [m,n,c,c,y]
yes
| ?- enigma([m,n,c,c,y],[j,q,d],X).
X = [h,e,l,l,o]
yes
| 

エニグマは1文字入力するごとにローターを回転させて暗号化の仕組みを変えていました。このため連続した文字を与えても異なる暗号文に変換されます。

| ?- enigma([a,a,a,a,a],[j,q,d],X).
X = [y,u,q,m,j]
yes
| 

#述語の説明

connecta/3 第1引数に与えらえれた1文字のアトムをそのローターの状態を表す1文字のもとに変換したものを第3引数に与えます。ローターが回転することにより文字がずれていくことを表現したものです。時計方向に変換します。

2017-07-23_12-16-34.png

connectb/3 connectaと同じ形式ですが、反時計方向に補正します。プラグを経由してリフレクションとして戻るときに使用します。

count/2 第1引数に与えられた初期値を右側の要素から順次時計方向に回転させていきます。

| ?- count([a,a,a],X).
X = [a,a,b]
yes
| ?- count([a,a,z],X).
X = [a,b,a]
yes
| 

ic/2 第1ローターを表す述語データベースです。
iic/2 第2ローターを表す述語データベースです。
iiic/3 第3ローターを表す述語データベースです。

歯車の文字が次のにどの文字に変換されているのかを示しています。

| ?- ic(f,X).
X = i
yes
| 

変換データは英語版wikipediaに記載の1924年製の商用版のものです。
https://en.wikipedia.org/wiki/Enigma_rotor_details

#考察
対称性はプラグにより2文字間で変換していることから生じます。コードでは26文字すべてについて他の文字に変換をしています。これにより反転性が得られるとともに、ある種の不完全性(Wikipedia参照)が生じると考えられます。

群論の知識が必要になるようです。

#参考資料
youtube 「エニグマ暗号とはなんだったのか」
https://www.youtube.com/watch?v=GG1zIELCb6k&t=449s
エニグマ暗号の解説とそれを解読したチューリングらの手法について解説しています。

#コード
GNU-Prolog SWI-Prolog などISO-Prolog準拠の処理系で動作します。拙作O-Prologでも操作します。

% ?- enigma([h,e,l,l,o],[a,a,a],X).
% ?- enigma([s,i,r,h,d],[a,a,a],X).

    
enigma([],_,[]).
enigma([L|Ls],[R1,R2,R3],[M|Ms]) :-
	connecta(L,R3,L1),
    ic(L1,L2),
    connecta(L2,R2,L3),
    iic(L3,L4),
    connecta(L4,R1,L5),
    iiic(L5,L6),
    plug(L6,L7),
    iiic(L8,L7),
    connectb(L8,R1,L9),
    iic(L10,L9),
    connectb(L10,R2,L11),
    ic(L12,L11),
    connectb(L12,R3,M),
    count([R1,R2,R3],R),
    enigma(Ls,R,Ms).

%adjust char when forward 
connecta(X,Y,Z) :-
	char_code(X,Cx),
    char_code(Y,Cy),
    Cz is mod((Cx-97) + (Cy-97),26)+97,
    char_code(Z,Cz).

%adjust char when backward
connectb(X,Y,Z) :-
	char_code(X,Cx),
    char_code(Y,Cy),
    Cz is mod((Cx-97+26) - (Cy-97),26)+97,
    char_code(Z,Cz).

%count up roter
count([X,Y,z],[X,Y1,a]) :-
    Y \== z,
    next(Y,Y1).
    
count([X,z,z],[X1,a,a]) :-
    next(X,X1).

count([X,Y,Z],[X,Y,Z1]) :-
	Z \== z,
    next(Z,Z1).
    
next(X,Y) :-
	char_code(X,C),
    C1 is C+1,
    char_code(Y,C1).

%rotor1
%ABCDEFGHIJKLMNOPQRSTUVWXYZ    
%DMTWSILRUYQNKFEJCAZBPGXOHV    
ic(a,d).
ic(b,m).
ic(c,t).
ic(d,w).
ic(e,s).
ic(f,i).
ic(g,l).
ic(h,r).
ic(i,u).
ic(j,y).
ic(k,q).
ic(l,n).
ic(m,k).
ic(n,f).
ic(o,e).
ic(p,j).
ic(q,c).
ic(r,a).  
ic(s,z).
ic(t,b).
ic(u,p).
ic(v,g).
ic(w,x).
ic(x,o).
ic(y,h).
ic(z,v).



%rotor2
%ABCDEFGHIJKLMNOPQRSTUVWXYZ
%HQZGPJTMOBLNCIFDYAWVEUSRKX
iic(a,h).
iic(b,q).
iic(c,z).
iic(d,g).
iic(e,p).
iic(f,j).
iic(g,t).
iic(h,m).
iic(i,o).
iic(j,b).
iic(k,l).
iic(l,n).
iic(m,c).
iic(n,i).
iic(o,f).
iic(p,d).
iic(q,y).
iic(r,a).
iic(s,w).
iic(t,v).
iic(u,e).
iic(v,u).
iic(w,s).
iic(x,r).
iic(y,k).
iic(z,x).

%rotor3
%ABCDEFGHIJKLMNOPQRSTUVWXYZ
%UQNTLSZFMREHDPXKIBVYGJCWOA
iiic(a,u).
iiic(b,q).
iiic(c,n).
iiic(d,t).
iiic(e,l).
iiic(f,s).
iiic(g,z).
iiic(h,f).
iiic(i,m).
iiic(j,r).
iiic(k,e).
iiic(l,h).
iiic(m,d).
iiic(n,p).
iiic(o,x).
iiic(p,k).
iiic(q,i).
iiic(r,b).
iiic(s,v).
iiic(t,y).
iiic(u,g).
iiic(v,j).
iiic(w,c).
iiic(x,w).
iiic(y,o).
iiic(z,a).

%plug
%ABCDEFGHIJKLMNOPQRSTUVWXYZ
%DPLAXGFMRSOCHZKBYIJVWTUEQN
plug(a,d).
plug(b,p).
plug(c,l).
plug(d,a).
plug(e,x).
plug(f,g).
plug(g,f).
plug(h,m).
plug(i,r).
plug(j,s).
plug(k,o).
plug(l,c).
plug(m,h).
plug(n,z).
plug(o,k).
plug(p,b).
plug(q,y).
plug(r,i).
plug(s,j).
plug(t,v).
plug(u,w).
plug(v,t).
plug(w,u).
plug(x,e).
plug(y,q).
plug(z,n).

3
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?