換字式暗号 -シーザー暗号より強い、アフィン変換型の換字式暗号-【ANGOUのすゝめ】#4

シーザー暗号は「足し算」である

　前回、シーザー暗号について、その仕組みと解読をしてみました。シーザー暗号は鍵の数が少なくブルートフォースな方法で解読できることがわかりましたね。

今回は、一般的な記事ではあまり紹介されない乗算型の換字式暗号について紹介します。この仕組みは単純ですが、シーザー暗号とは一線を画す解読の困難さを手に入れられます。

シーザー暗号の仕組みと数学復習

　ここで、一旦シーザー暗号の数学的表現を見直してみます。

合同式 (Mod)を用いて、

\[E(x) = (x + k) \mod{n}\]

\(x\): 平文の文字（0から始まる番号）

\(k\): 鍵（ずらす数）

\(n\): アルファベットなどの文字数

\(\mod{26}\): 「26で割った余り」という意味。

乗算を用いたらどうなる？乗算型換字式暗号

シーザー暗号の置き換え位置は \(x + k\)と足し算でしたが、 \(a \times x\)の様に掛け算にしたらどうでしょうか？

合同式 (Mod)を用いて、

\[E(x) = (ax) \mod{n}\]

\(x\): 平文の文字（0から始まる番号）

\(a\): 鍵（ずらす量の掛け算の係数）

\(n\): アルファベットなどの文字数

下側のADG..は、ABC..を置き換えた時の並びになります。

図 n=3 の時の置き換え 2文字飛ばしで置き換えます。

とびとびになって解読が難しくなりました。

　乗算にすることで、B(1) \( \to \) D(3), C(2)\( \to\) G(6)の様にとびとびに置き換わるので、乗算の換え字暗号であることがわからない限り、解読が困難になりました。

a と n は互いに素

　掛け算の暗号でつかえる\(a\)は何でもいいわけではありません。もし\(a\)が\(n\)の約数になってしまうと、すべての文字を１対１対応できなくなってしまいます。

ダメな例　：\(a = 2\)にすると、アルファベットの\(n=26\)と互いに素でないので、ちょうど一周してしまい、置き換え元と置き換え先が１対１対応にできません。

下側のACE..は、ABC..を置き換えた時の並びになり、MNO..　も ACE..に置き換わるので戻せなくなる。

図 n=2 の時の置き換え先　1対１対応できない。

有効な鍵は？

　互いに素でないとカギになれないといいましたが、実際鍵の数はいくつになるのでしょうか？

「全体の文字数-1から、約数で割れるやつを消せばいいじゃん」という声が聞こえてきそうですが、アルファベットの26文字の例を用いて、ちょこっと数学的な表現で考えてみようと思います。

乗法逆元

まず、暗号化と復号の式を定義します。アルファベットの文字数を \(n=26\) とします。

暗号化: \(E(x) \equiv ax \pmod{26}\)
復号: \(D(y) \equiv a^{-1}y \pmod{26}\)

ここで \(x\) は平文、 \(y\) は暗号文、\(a\) は鍵（係数）です。

※ここでいう　a^-1 の -1はマイナス１乗の意味ではありません。

逆元の存在

暗号として成立するためには、暗号文 \(y\) から平文 \(x\) をただ一つに復元（復号）できなければなりません。

数学的には、「\(a\) の乗法逆元 \(a^{-1} \pmod{26}\) が存在すること」が必要です。

これが成立するための条件は、以下の通りです。

\[ \gcd(a, 26) = 1\]

つまり、鍵 \(a\) は \(26\) と「互いに素（coprime）」でなければなりません。

もし \(a\) と \(26\) が公約数を持つ（互いに素でない）場合、異なる平文が同じ暗号文になってしまい、復号できなくなります。

参考：gcdとは？拡張ユークリッドの互除法(乗法的逆元についてもここで紹介してます)

ユークリッドの互除法を図解し、その仕組みを理解する。また、ユークリッドの互除法からどのように拡張ユークリッドの互除法が導かれるのか分かりやすく紹介する記事のサムネイル

【図解】ユークリッドの互除法とは？gcdを徹底解説 -拡張ユークリッドの互除法-

RSA暗号などにも使われる「ユークリッドの互除法」とその拡張版を解説。最大公約数を求める基本的な仕組みから、暗号技術に必須となる「乗法的逆元」の計算方法まで、アルゴリズムの挙動を図解と数式で直感的に理解しましょう。

オイラーのΦ関数(トーシェント関数)

「\(26\) と互いに素である \(1\) から \(26\) までの整数の個数」を表す関数が、オイラーの \(\phi\) 関数（Euler’s totient function） です。

\[オイラーの \phi関数 : \phi(a) \]

計算プロセスの例

\(n = 26\) を素因数分解すると、

\[26 = 2 \times 13\]

となります。

\(\phi\) 関数の性質（乗法性）を利用すると、以下のように計算できます。

\[\begin{aligned} \phi(26) &= \phi(2 \times 13) \\ &= \phi(2) \times \phi(13) \end{aligned}\]

ここで、素因数分解しているので、出てきた数はすべて素数になっているはずです。素数 \(p\) に対して \(\phi(p) = p – 1\)（素数より小さい正の整数はすべてその素数と互いに素であるため）なので、

\[\begin{aligned} \phi(2) &= 2 – 1 = 1 \\ \phi(13) &= 13 – 1 = 12 \end{aligned}\]

したがって、

\[\phi(26) = 1 \times 12 = 12\]

26に対して 12という解が得られました。

3. 実際の鍵の候補と除外される数

実際にどの数が鍵として使えるのか、集合として見てみましょう。

鍵として使える数（\(26\) と互いに素な数）

奇数かつ、\(13\) の倍数ではない数です。

\[a \in \{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}\]

（※ \(a=1\) は平文が変わらないため、実用的な暗号としては意味をなしませんが、数学的な定義上の鍵空間には含まれます）

鍵として使えない数（不適格な数）

偶数（2の倍数）: \(2, 4, 6, \dots, 26\) （\(26\) と公約数 \(2\) を持つため）
13の倍数: \(13, 26\) （\(26\) と公約数 \(13\) を持つため）

上で例に挙げたようにn=2とすると、元に戻せません。結論として、使用可能な鍵 \(a\) の候補は数学的に「12通り」しか存在しません。

鍵の数が減った？

　ここで、おやおや？と気づいた人もいるかと思いますが、シーザー暗号の２５個よりも乗算置換式暗号では、鍵の数が11(1は平文のままなので除外）個となっており、減ってしまっています。

これでは、暗号の強度が下がってしまいますね、では、どうすればいいのでしょうか？

乗算と通常のシーザー暗号(加算暗号)の移動を組み合わせることで、鍵パターンが一気に増えてより強力な暗号となります。これは、移動と乗算を用いるので、アフィン変換型の換字式暗号と呼ばれます。

アフィン変換型換字式暗号

アフィン変換(線形変換)型の換字式暗号は以下の様に表現できます。

合同式 (Mod)を用いて、

\[E(x) = (ax + b) \mod{n}\]

\(x\): 平文の文字（0から始まる番号）
\(a\): 鍵1（ずらす量の掛け算の係数）
\(b\): 鍵2（ずらす量）
\(n\): アルファベットなどの文字数

どのくらい鍵がある？

　アフィン変換型の換字式暗号では、乗算部と定数の移動部の組み合わせだけ鍵パターンが存在できるので、

\[アフィン変換型鍵パターン数\alpha = (乗算のパターン数) \times (移動のパターン数) \]

\[ \alpha = 12 \times 26 \]

\(\alpha\)のうち、乗算部が１で、移動部が０の時は、平文のままなので、これは使えないので、アフィン変換型の鍵パターンは、\( \alpha = 12 \times 26 – 1 = 311\)通りに増えます。

今のところ１次の線形変換を用いていますが、二次以上の式で置き換えを行えばもっと鍵のパターンは増えます。鍵として使える組みの計算などが大変なので、ここでは触れないこととしますが興味があれば、考えてみてください。

まとめ

シーザー暗号(加算暗号)に乗算を組み合わせることでより強力なアフィン変換型換字式暗号を作れることがわかりました。

鍵の数も 12倍になっており強力になりました。しかし、現代のPCでは容易に全パターン試せてしまいます。

「単一の文字」をずらすのではなく、「複数の文字」を複雑なルールで混ぜ合わせたらどうなるでしょうか？次回は、数世紀にわたって「解読不可能」と言われた最強の暗号、「ヴィジュネル暗号」(ビジネル暗号)へと歴史を進めてみます。

次回、ヴィジュネル暗号編でお会いしましょう。