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

暗号技術入門 第3版

暗号技術のすべて

こんにちは.

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

シーザー暗号 (Cither cryptography)

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

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の対応関係を持たせて暗号化する方式です.

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版

RSA暗号 ～まとめ～

暗号技術入門 第3版

暗号理論入門 原書第3版

お久しぶりです.

最近CTFの勉強をしていて, RSA暗号に触れる機会があったのでまとめておこうと思います. 出来るだけほかの人にもわかりやすく書いていこうと思います. 
昨年授業でRSA暗号については一通り習ったのですが, やはり1年も経つと忘れてましたね...これを機にもう一度覚えなおしていきたいと思います.

この記事を作るにあたって, 以下のサイトには大変お世話になりました. 本当にありがとうございました.
mathtrain.jp

tsujimotter.hatenablog.com

RSA暗号とは

RSA暗号とは, 公開鍵暗号方式を利用した暗号方法です. 暗号方式には共通鍵暗号方式と公開鍵暗号方式というものが存在します. RSA暗号ではそのうち公開鍵暗号方式を利用しているんですね.
RSA暗号を理解するには, 高校数学で1通り学ぶ初等整数論を理解している必要があります. 合同式を利用するので, 合同式を用いた計算は１通りできておいたほうが良いと思います. またフェルマーの小定理というものを途中で使用するのですが, これは大学の数学で学ぶことなので, 紹介はしますが証明まではしません. 詳しい証明が知りたい人は個人で調べてもらえるとありがたいです.

そもそも暗号化とは？

これは説明するまでもないと思いますが, 暗号化とはデータの内容を他人にはわからないようにするための方法です. 例えば, オンラインショッピングをするとき, クレジットカードのカード番号がそのままネットワーク上に流れてしまったらどうなるでしょうか. 当然そのデータが盗聴されてしまったらカードが不正利用されてしまい, 大変なことになってしまいますよね. そのため, 見られたくないデータをネットワークを通してやり取りする場合は, 暗号鍵を利用して暗号化をしなければいけません.
また暗号化したら, 復号化出来なければいけません. 暗号化したまま復号化出来なければ, もとのデータは利用できなくなってしまい,本末転倒ですね. なので, 復号鍵を利用して暗号化データをもとのデータに直してやる必要があります. もし暗号鍵と復号鍵が同じである場合は「共通鍵暗号方式」, 違う場合は「公開鍵暗号方式」といいます. つまり, RSA暗号では暗号鍵と復号鍵は別のものであるということです.

RSA暗号の仕組み

平文(暗号化する前のデータ)を, 暗号文をとします. また2つの暗号鍵(公開鍵なので他人に知られても大丈夫)をとします. ここで, 平文から暗号文を得る暗号化方法は以下の通りです.

つづいて, 暗号文から平文を得る復号化方式は以下の通りです. ここで, とは復号鍵のことを指します. 復号鍵は秘密鍵なので, 他人に知られてはいけません.

ここで(1), (2)から

となります. つまり, (3)を満たすような復号鍵が存在すれば復号化することができます.
このあとも説明しますが, 実はこのような復号鍵は存在するのです. しかし, この復号鍵を公開鍵から計算して導出することは現実に難しいです(理論的に不可能ではないのですが, 計算する時間が膨大になってしまいます). つまり, 暗号文を復号するのは復号鍵を知っている人にしかできないという仕組みになっているのです.

RSA暗号の仕組み(さらに詳しく)

RSA暗号の公開鍵は2つ存在しますが(の2つ), そのうちは非常に大きい素数を用いて,

となります. 先ほど復号鍵は秘密鍵なので知られてはいけないといいましたが, 実はこのも他人に知られてはいけません. ここもポイントなのですが, こうすることによってRSA暗号の安全性と信頼性が担保されることになるのです(のちに詳しく説明します).

さてここから, なぜRSA暗号がうまく機能するのか説明していこうと思います.

復号鍵の一意存在性

ここでオイラーの定理 というものを使用します. オイラーの定理はこのサイトを利用して説明を省略しようと思います.

オイラーの定理を使用すると, は互いに素なので,

となります(は整数).
(4)を少し変形します. 両辺にをかけると,

となります. ここで(3)と指数部を比較してみましょう. すると,

となります.
細かいですが, さらに変形して,

さて, ここまで色々な式変形をしてきましたが, ここで知りたいことはタイトルにもあるように「復号鍵が一意に存在するか」ということです. つまり(7)を満たすような整数が存在すればOKです.

ここで高校数学を思い出しましょう. 以下の定理, 覚えているでしょうか.

「一次不定方程式の整数解」

を互いに素な整数としたとき, を満たすような整数解が存在する.

これを(7)に適用してみましょう. いまが互いに素であるならば, (7)を満たすような整数が存在します. 整数は何を選んでもよいので, 素数を選んでしまえばOKそうですね.
このことから復号鍵は一意に存在することが示せました.

(補足)少し複雑な説明は省略してしまいましたが, は複数の解をもちます. そのうち, が正となるものを選んであげてください.

他人が復号鍵を計算することの困難性

復号鍵が一意に存在することはわかりましたが, もしから復号鍵が生成できてしまったらどうでしょう. 暗号化する意味がなくなってしまいますよね. ここでは, 復号鍵も持たない他人が復号鍵を生成することができるのかということを説明していきたいと思います.

もう一度(7)の式を見てみましょう.(は既知なのでということを忘れないでください). もしが計算できてしまったら復号鍵が生成できてしまいます. でも, すでには既知だから, は簡単に計算できてしまうんじゃないの？と思う方もいるかもしれません.

ここで少し前に説明したことを思い出してほしいのです.

RSA暗号の公開鍵は2つ存在しますが(の2つ), そのうちは非常に大きい素数を用いて,

となります.

そして, は以下のように計算することができます.

もし仮にの値を事前に知っていないのならば, を素因数分解しなければなりません. しかし, は非常に大きな素数なので, 素因数分解するには膨大な時間がかかってしまうのです. なので先ほども言いましたが, は他人に知られてはいけないのです. ここがミソなんです.

すなわち, 暗号化したデータを復号化できるのは,

• 復号鍵を保持している人(つまりの値を知っている人)

に限られてくるのです.

このようにしてRSA暗号の安全性を担保することができるのです.

まとめ

分かりやすかったでしょうか. RSA暗号は美しい数学的性質をうまく利用した暗号化方式であることがわかりましたね.
しかし, 今後量子コンピュータなどが登場した場合, を簡単に素因数分解できてしまう可能性も否めません. 時代に即した暗号化方式を適用する必要がありますね.

暗号技術入門 第3版

暗号理論入門 原書第3版