頑張らないように頑張る。

努力と怠惰の狭間

「Pythonでいかにして暗号を破るか」を読んだのでまとめた。

積読状態だった「Pythonでいかにして暗号を破るか」にようやく手を付けたので、内容をまとめておく。

なお、本書はソシム社より出版されている。

www.socym.co.jp



🔓全体を通して(Python的なお話)

Python的なお話でいうと、1章から最終章に至るまで、基礎学習に近しい内容であった。
高度な技術を要していたり、よく分からないライブラリを使っていたりという事もなかった。

なので、本書をPythonの入門書としつつ、併せて暗号化アルゴリズムを学ぶという使い方もできると感じた。



🔓暗号の話

暗号学とは

暗号学は、秘密の文字体系を用い科学。
暗号学者は、秘密の符号を使ったり、研究したりしている。
暗号解読者は、コードブレイカーハッカーとも呼ばれる。


「符号」と「暗号」

符号とは、内容を理解できるし、誰でも平文に翻訳できるもの。
暗号とは、平文を秘密にする特別な文字体系であり、相互変換規則の集まり。


符号は、平文を01に変換する事を「エンコード」、01を平文に変換する事を「デコード」という。
暗号は、平文を暗号文に変換する事を「暗号化」、暗号文を平文に変換する事を「復号」という。


符号には、モールス符号などがある。
暗号には、シーザー暗号などがある。(暗号については以降にその他の手法も記載する)


「二重暗号化」について

二重暗号化は、通常の一回の暗号化を行った結果と同じ。(強度面の話)



🔓数学的概念

暗号化方式を学ぶ上で必要な数学的概念を記載する。


モジューラー算術(時計算術)

特定の値に達すると、数値がラップアラウンドする計算。
モジューラ算術の式を書くには、剰余演算子(mod演算子)を使用する。


最大公約数(GCD)

2つの数値に対する、最大かつ共通の因数。
2000年前の数学者ユークリッドは、モジューラー算術を用いて、2つの数値のGCDを算出するアルドリズムを考案した。


素数

1と自分自身以外に因数を持たない整数。

ある範囲内のすべての素数を見つけるアルゴリズムとして「エラトステネスのふるい」がある。方法は以下の通り。

  1. 範囲内から1と偶数を除去
  2. 残った範囲を、最小素数(2,3,5...)から順番に剰余を求め、剰余が0の場合に除去



🔓暗号化方式


逆暗号

説明
暗号鍵 なし
暗号化方法 平文を「逆順」にする
復号方法 逆順になった平文を「逆順」にする
破る方法 復号方法と同じ


転置式暗号

以下のような種類が存在する。

  • 円柱型転置式暗号
  • レールフェンス(rail fence)暗号
  • ルート(route)暗号
  • Myszkowski転置式暗号
  • 不規則(Disrupted)転置式暗号

本書では「円柱型転置式暗号」について解説している。

説明
暗号鍵 1行当たりの箱の数
暗号化方法 「行方向の箱」に1文字ずつ入れていき、「列方向の箱」を取り出す
復号方法 「暗号文の長さ」と「暗号鍵」で必要な列数を割り出し、「行方向の箱」に1文字ずつ入れていき、「列方向の箱」を取り出す
破る方法 総当たり(1行あたりの箱の数を1~nで試行)


シーザー暗号

説明
暗号鍵 インデックスに加算する文字数
暗号化方法 「シンボルのインデックス」に「暗号鍵」を加算し、平文の各文字に対応させて新しい文字に置き換える
復号方法 「シンボルのインデックス」に「暗号鍵」を減算し、平文の各文字に対応させて新しい文字に置き換える
破る方法 総当たり(加算する整数を1~nで試行)


乗法暗号

シーザー暗号に似ているが、加算ではなく乗算で暗号化する。

説明
暗号鍵 インデックスに乗算する数
暗号化方法 「シンボルのインデックス」に「暗号鍵」を乗算し、「シンボル長」との剰余を、平文の各文字に対応させて新しい文字に置き換える
復号方法 「シンボルのインデックス」に「モジューラー逆数」を乗算し、「シンボル長」との剰余を、平文の各文字に対応させて新しい文字に置き換える
破る方法 総当たり(「モジューラ逆数」を1~nで試行)
補足 シンボル長と鍵長は互いに素でないといけない
欠点 「A」は常に「A」に対応してしまう


アフィン暗号

乗法暗号の欠点を補える暗号化方式。

説明
暗号鍵① 乗法暗号で用いる乗算用の整数値
暗号鍵② シーザー暗号で用いる加算用の整数値
暗号化方法 「乗法暗号」で暗号化した後に、「シーザー暗号」で暗号化
復号方法 「シーザー暗号」で復号した後に、「乗法暗号」で復号
破る方法 総当たり(鍵①も鍵②もラップアラウンド効果が同じとなるため、シンボル長以上の整数値は設置できない&鍵①は互いに素である必要があるため更に絞られる=総当たりも実現可能)


単一換字式暗号

シンボルをランダムに配置したものを鍵とする。
(例:アルファベット26文字をランダムに配置した「VJZBGNFEPLITMXDWKQUCRYAHSO」が鍵)


つまり、鍵の総数はシンボル長の階乗となり、総当たりが困難になる。
(例:26の階乗=約403穣通りの鍵が存在する)


やっている事はシーザー暗号や乗法暗号と同じだが、ランダマイズ性が格段に向上する。

説明
暗号鍵 シンボルをランダムに配置した文字列
暗号化方法 平文のインデックスを、「ランダムにしてないシンボルのインデックス」から「暗号鍵のインデックス」に対応させて新しい文字に置き換える
復号方法 暗号文のインデックスを、「暗号鍵のインデックス」から「ランダムにしてないインデックス」に対応させて新しい文字に置き換える
破る方法 頻度分析(単語を収録した辞書ファイルから単語パターン(暗号単語)を探り、単語パターンから各文字(暗号文字)を特定する(例:「hghhu」という暗号単語は「puppy」「mommy」「lulls」などと対応する可能性がある))
欠点 平文が長ければ長いほど解読が容易になる(含まれる単語が多くなるため)


ヴィジュネル暗号(多表換字式暗号)

仕組みはシーザー暗号と同じだが、暗号化対象が異なる。
シーザー暗号では「平文全体」を暗号化していたが、ヴィジュネル暗号では「平文の各文字」を暗号化する。


<例>
平文「AABBCCDDEE」に対して、鍵「PIZZA」という5文字に設定する
 →「AABBC→(PIZZA)→PIAAC」「CDDEE→(PIZZA)→RLCDE」と変換される
 →「PIAACRLCDE」という暗号文になり、同じ「A」「C」「D」「E」でも異なる暗号文字になる(「B」はたまたま一緒になっただけ))


つまり、シーザー暗号や乗法暗号よりはるかに解読が難しくなる。
また、単一換字式暗号は頻度分析で解読可能であったが、ヴィジュネル暗号は頻度分析をしても効果がない。
さらに、鍵長が長くなればなるほど安全になる。
(例:アルファベット26文字の場合、「PIZZA」は26の5乗=約1100万通りで解読できてしまうが、「PIZZAPASTA」は26の10乗=約141兆通りとなる)
(例として「PIZZA」とか「PASTA」とか使っているが、実際は辞書にあるような文字列は使うべきではない)

説明
暗号鍵 任意の文字列
暗号化方法 平文を「鍵長」で区切り、各文字に対して「シーザー暗号」で暗号(加算)
復号方法 暗号文を「鍵長」で区切り、各文字に対して「シーザー暗号」で復号(減算)
破る方法 ①辞書攻撃
②カシスキー検査(鍵長候補を探り、スペーシングの因数を計算し、最頻を候補にして頻度マッチスコアを計算し、サブ鍵候補を総当たり)


ワンタイムパッド暗号

ヴィジュネル暗号の鍵を、以下の条件とする事で、解読不可能にした暗号化方式。

  • 鍵は暗号化するメッセージと同じ長さを持つ
  • 鍵は真にランダムである
  • 鍵はメッセージの暗号化に一度だけ使用し、再び使用しない
説明
暗号鍵 上記の通り
暗号化方法 「ヴィジュネル暗号」と同じ
復号方法 「ヴィジュネル暗号」と同じ
破る方法 無い
補足 とても不便


公開鍵暗号

これまで説明してきた暗号化方式は、暗号化と復号に同じ鍵を用いていた。
つまり「共通鍵暗号方式」であった。(「対称暗号」とも言う)


公開鍵暗号方式」は、暗号化と復号に異なる鍵を用いる。
「非対称暗号」とも呼ばれる。
暗号化に用いる鍵を「公開鍵」と呼び、復号に用いる鍵を「秘密鍵」と呼ぶ。


公開鍵と秘密鍵の作り方
  1. 2つのランダム&独立&巨大な素数である「p」と「q」を生成
  2. pとqを掛け合わせ、「n」を生成
  3. (p-1)×(q-1)と互いに素である乱数「e」を生成
  4. eのモジューラー逆数を計算した結果「d」を生成


公開鍵は「n」「e」から構成され、
秘密鍵は「n」「d」から構成される。
(※「d」は絶対に知られないように!!!)


公開鍵暗号の仕組み

▼暗号化

  1. ブロックを作成(例:169ブロック)
  2. 文字列をブロック値「M」に変換(例:Howdy→957285919) ←文字列が数字に変換できる
  3. M ^ e mod nで暗号化する

▼復号

  1. C ^ d mod nで復号し、ブロック値を得る(C=ブロック値を暗号化した値(暗号化手順3の結果))
  2. ブロック値を文字列に変換(例:957285919→Howdy)


解読不可能
  • 総当たり攻撃できない
    • (確認すべき鍵の候補数が多過ぎるため)
  • 辞書攻撃できない
    • (鍵が単語ではなく数字のため)
  • 単語パターン攻撃できない
    • (平文に同じ単語があっても、ブロックの場所に応じて異なる値に暗号化されるため)
  • 頻度分析できない
    • (1つの暗号化されたブロックはいくつかの文字を表しており、個々の文字の頻度が得られないため)
  • 素因数分解できない
    • 「p」と「q」から「n」を求めるのは簡単だが、「n」から「p」と「q」を求めるのが数学的にとても困難(計算量が膨大)


脱線:認証のお話

公開鍵暗号方式に限らず、全ての暗号方式は「機密性」は提供できるが、「認証」は提供できない。
そのため、公開鍵暗号方式では「公開鍵基盤(PKI)」に基づき、「認証局(CA)」が証明書を発行する。
(この辺は本書の範囲を超えるので、説明はここまで。)



🔓最後に

暗号技術について、聞いた事があってもアルゴリズムまでは理解してなかったから、本書はとても学びになった。
今後IT研修とかでアルゴリズムなど教える機会があったら、この辺りを使って説明すると、受講者も興味示してくれるかなと思った。

過去に、セスペに2度、情報処理安全確保支援士に2度落ちて心が折れてたけど、やっぱりセキュリティ周りって学んでて楽しい。(セスペとかにアルゴリズム的な問題は出てこないけど)

http://www.socym.co.jp/wp-content/uploads/2020/cover.png