namdicul's blog

気ままに更新します. CTFと暗号理論について勉強中です.

暗号理論 (1) 〜 古典的暗号 〜

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて


こんにちは.

今日は暗号理論を語るにあたって, 知っておくべき古典的暗号について紹介します. また, その暗号解読法について紹介していきたいと思います.

シーザー暗号 (Cither cryptography)

まず一番単純なシーザー暗号について紹介していきたいと思います.
シーザー暗号では, 元々の平文のアルファベットを決められた文字数分(この値をkeyと定義します)だけずらすという暗号方式です. ここで具体例を見てみましょう.

f:id:tomonori4565:20180521140331j:plain
Cither cryptography

(補足と謝罪:画像に少しミスがあります. 画像右側の矢印, 1つずつずれてますね...申し訳ないです.)

例えば, "hatenablog"をシーザー暗号によって暗号化してみましょう. ここではkey=3, つまり3文字分ずらしてみましょう.
すると,


h → k
a → d
t → w
.
.
.
o → r
g → j

となり, 暗号文は"kdwhqdeorj"となるわけです.

次に, シーザー暗号で暗号化された暗号文を復号化してみましょう. どうすればいいでしょうか考えてみてください.




key=-3として3文字分逆にずらしてやればOKですね. つまり,


k → h
d → a
w → t
.
.
.
r → o
j → g

とずらしてやり, 復号文(つまり平文)は"hatenablog"となるわけです.



いかかでしょうか. シーザー暗号はとても単純な暗号方式であることがわかりますね.




ではここで話を少し変えてみましょう.

あなたは盗聴者です. あなたはAさんからBさんのデータのやり取りを盗聴し, そのデータの内容を取得しようと思っています. しかし, データは暗号化されており, 内容を知ることはできません. 取得した暗号文は"spwwzhzcwo"であることがわかりました. あなたならデータの内容を取得する(つまり暗号文を解読する)ために何をするでしょうか.




一番有効なのは, 暗号文をシーザー暗号だと仮定し, keyを-1, -2, ..., -25, -26とずらしていき, 意味のある復号文を得ようとすることです.
実際にやってみましょう.

-26 shift: spwwzhzcwo
-25 shift: tqxxaiadxp
-24 shift: uryybjbeyq
-23 shift: vszzckcfzr
-22 shift: wtaadldgas
-21 shift: xubbemehbt
-20 shift: yvccfnficu
-19 shift: zwddgogjdv
-18 shift: axeehphkew
-17 shift: byffiqilfx
-16 shift: czggjrjmgy
-15 shift: dahhksknhz
-14 shift: ebiiltloia
-13 shift: fcjjmumpjb
-12 shift: gdkknvnqkc
-11 shift: helloworld
-10 shift: ifmmpxpsme
-9 shift: jgnnqyqtnf
-8 shift: khoorzruog
-7 shift: lippsasvph
-6 shift: mjqqtbtwqi
-5 shift: nkrrucuxrj
-4 shift: olssvdvysk
-3 shift: pmttwewztl
-2 shift: qnuuxfxaum
-1 shift: rovvygybvn

「-11 shift」を見ると, "helloworld"という意味のある文章を得られましたね.

このように, 全ての鍵の候補を試してみるという暗号解読方法をブルート・フォース・アタックと言います.

シーザー暗号に関しては, ブルート・フォース・アタックによって簡単に暗号文を解読することができます. よってシーザー暗号は秘密データを守るには弱すぎることがわかりますね.

では, ブルート・フォース・アタックによって解読されにくい強い暗号化方式は存在しないのでしょうか.

存在します. 次に紹介する単一換字暗号という暗号方式はブルート・フォース・アタックによって解読されにくいです.


以下は, 自作したシーザー暗号の暗号化・復号化ツールです. よかったら利用してみてください.

print('***Cither cryptography***\n')

print('Input message below.')
message = input()
message_list = list(message)

print('\n')

for i in range(1, 27):
    return_message = ''
    for element in message_list:
        if (ord(element) + i) <= 122:
            return_message += chr(ord(element) + i)
        else:
            return_message += chr(ord(element) + i - 26)
            print('{0} shift: {1}'.format(i, return_message))

print('\n****************************\n')

for i in range(-26, 0):
    return_message = ''
    for element in message_list:
        if (ord(element) + i) >= 97:
            return_message += chr(ord(element) + i)
        else:
            return_message += chr(ord(element) + i + 26)
    print('{0} shift: {1}'.format(i, return_message))

単一換字暗号 (simple substitution cipher)

単一換字暗号とは, アルファベット上の文字からアルファベット上の文字に対して, 1対1の対応関係を持たせて暗号化する方式です.

f:id:tomonori4565:20180521145354j:plain
simple substitution cipher

上の画像のように, 元のアルファベットと暗号先のアルファベットの対応関係を表した表のことを換字表と言います.

自作したプログラムを元に単一換字暗号を実際に実行してみましょう.

import random

print('***Single substitution***\n')

print('Input message below.')
message = input()
message_list = list(message)
alphabet_list = list('abcdefghijklmnopqrstuvwxyz')
print(alphabet_list)

random.shuffle(alphabet_list)

print(alphabet_list)

return_message = ''
for element in message_list:
    return_message += alphabet_list[ord(element) - 97]

print(return_message)

print('\n****************************\n')

以下は実行結果です.

***Single substitution***

Input message below.
hatenablog

['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
['a', 'g', 'f', 'v', 'p', 's', 'i', 'n', 'l', 'c', 'k', 'j', 'o', 'd', 'u', 'z', 'w', 'r', 'e', 'b', 'q', 'x', 'y', 'm', 't', 'h']
nabpdagjui

****************************

いま, "hatenablog"という平文を単一換字暗号で暗号化しています. 換字表は2つのリスト構造で表現されています.

つまり,


h → n
a → a
t → b
.
.
.
b → g
l → j
o → u
g → i

というように暗号化しています. 結果的に, 暗号文は"nabpdagjui"になっていることがわかりますね.



復号化するには, 暗号化に用いた換字表を用いて, 逆変換してやればOKです.





では, シーザー暗号のときと同じ質問をします.

あなたは盗聴者です. あなたはAさんからBさんのデータのやり取りを盗聴し, そのデータの内容を取得しようと思っています. しかし, データは暗号化されており, 内容を知ることはできません. 取得した暗号文は"spwwzhzcwo"であることがわかりました. あなたならデータの内容を取得する(つまり暗号文を解読する)ために何をするでしょうか.


先ほど学んだブルート・フォース・アタックを実行しようと考えた方もいるかもしれません. しかしよく考えてみてください.


シーザー暗号のときは, 鍵の候補は26通りしか存在しなかったので, ブルート・フォース・アタックによって簡単に暗号解読をすることができました. では, 単一換字暗号の場合はどうでしょうか.


最大26!通り存在することがわかります. 26! = 1×2×3×...×25×26=403291461126605635584000000なので, 全ての鍵を試すことは実質不可能であることがわかります.


では, 単一換字暗号は一生解読することができないのでしょうか.

実はそういう訳でもありません. 一度, 解読方法を考えてみてください.





単一換字暗号を解読するには, 「頻度分析」というものを使うのがよさそうです.


アルファベットは, どの文字も等確率で現れる訳ではなく, 多少偏りを持って出現します. xの出現確率とaの出現確率は, 直感でも違うことがわかりますね. このように, 暗号文に出てくる文字の出現頻度を分析して, 平文に直す作業のことを頻度分析というのです.


英語の文章では, e, t, a, o, i, n, s, ... という順に出現頻度が小さくなっていきます. もし, 暗号文にwの文字が多く出現している場合は, 元の文字がeやtやaである確率が高い訳です. そのようにして暗号文を復号化していくのです.



いずれにせよ, シーザー暗号のブルート・フォース・アタックに比べて, 骨の折れる作業であることは間違い無いですね.


エニグマ (Enigma)

編集中です.すいませんm(__)m

暗号技術入門 第3版

暗号技術入門 第3版

暗号理論入門 原書第3版

暗号理論入門 原書第3版