本日も暗号への道を進もうと思います。
過去分はこちら。
↓↓↓
暗号: ラインセグメント日記
本日は数学的な名称の付いた暗号です。
Affine cipher - Wikipedia
アフィン暗号というらしく、個人的にアフィンといえば、相対性理論に出て来るアフィン変換という概念を連想します。
線形変換+平行移動($y=ax+b$)がアフィン変換です。
さて、このアフィン変換をモチーフにした暗号は、数字から数字への変換です。
アルファベットを変換前の数字にするために、a〜zを0〜25の26種類の数字に対応付けておきます。
そして、それらの数字に対して、アフィン変換をほどこして、0〜25に収めるために26の剰余をとります。
アフィン暗号の暗号化
式にすると、変換前の数字を$x$、変換対象の数字の種類を$m$とすると、 \[ y=\left(ax+b\right)\mod m \] とするわけです。
$a$と$b$がCipher Key(暗号鍵)として選ぶ数です。
ここで、暗号としての要請から、異なる$x$に対して異なる$y$に変換します。
そのため、$m=26$と互いに素となる$a$を選ぶ必要があります。
互いに素とは、$m$と$a$の最大公約数が$1$であるということです。
$m=26$の場合、$m$と互いに素な自然数は、$1$、$3$、$5$、$7$、$9$、$11$、$15$、$17$、$19$、$21$、$23$、$25\cdots$の自然数です。
もう1つの暗号鍵$b$は$\mod26$の制限があるので、意味がある$b$の範囲は0〜25となります。
過去分はこちら。
↓↓↓
暗号: ラインセグメント日記
本日は数学的な名称の付いた暗号です。
Affine cipher - Wikipedia
アフィン暗号というらしく、個人的にアフィンといえば、相対性理論に出て来るアフィン変換という概念を連想します。
線形変換+平行移動($y=ax+b$)がアフィン変換です。
さて、このアフィン変換をモチーフにした暗号は、数字から数字への変換です。
アルファベットを変換前の数字にするために、a〜zを0〜25の26種類の数字に対応付けておきます。
そして、それらの数字に対して、アフィン変換をほどこして、0〜25に収めるために26の剰余をとります。
アフィン暗号の暗号化
式にすると、変換前の数字を$x$、変換対象の数字の種類を$m$とすると、 \[ y=\left(ax+b\right)\mod m \] とするわけです。
$a$と$b$がCipher Key(暗号鍵)として選ぶ数です。
ここで、暗号としての要請から、異なる$x$に対して異なる$y$に変換します。
そのため、$m=26$と互いに素となる$a$を選ぶ必要があります。
互いに素とは、$m$と$a$の最大公約数が$1$であるということです。
$m=26$の場合、$m$と互いに素な自然数は、$1$、$3$、$5$、$7$、$9$、$11$、$15$、$17$、$19$、$21$、$23$、$25\cdots$の自然数です。
もう1つの暗号鍵$b$は$\mod26$の制限があるので、意味がある$b$の範囲は0〜25となります。
モジュラ逆数
復号化のときは、上記のアフィン変換+$m$による剰余の逆変換を行います。
式で書くと、
\[ x=a^{-1}left(y-b\right)\mod m \] となります。
ここで、$\displaystyle a^{-1}$は、$\mod m$の下での$a$の逆元となるのですが、これを$m$を法とするモジュラ逆数と呼ぶそうです。
モジュラ逆数 - Wikipedia
\[ a^{-1}\equiv x\mod m \]
$\displaystyle a^{-1}$の求め方は、$mn+1$($n$は整数)が$a$で割り切れたときの商となるみたいです。
例えば、$\displaystyle5^{-1}$を求めてみます。
$26\cdotp4+1$は$5$で割り切れて、その商は21となります。
条件を満たせば$\displaystyle5^{-1}$なので、答えとしては$21+26n$($n$は整数)です。
アフィン暗号の復号化
これで、復号化のメンバーは揃いました。
試しに$x$から18へ変換した$18=\left(5x+8\right)\mod 26$の逆変換を考えると、 \begin{eqnarray*} x&=&5^{-1}\left(18-8\right)\mod26\\ &=&21\left(10\right)\mod26\\ &=&210\mod26\\ &=&2 \end{eqnarray*} より、暗号化する前の数字が2だったことがわかります。
確認のため、2を同じ暗号鍵$5,8$で暗号化してみると、 \begin{eqnarray*} y&=&\left(5\cdotp2+8\right)\mod26\\ &=&\left(18\right)\mod26\\ &=&18\mod26\\ &=&18 \end{eqnarray*} となって、$2$から$18$へ暗号化していたことが確かめられます。
アフィン暗号の所感
いよいよ数学(数論)的な知識も導入して、複雑化した暗号方式です。
とくに、$\mod$のような、人間の目には見えにくい法則性を用いている点で、これまでのアトバシュ暗号、ポリュビオス暗号表、シーザー暗号とは一線を画しています。
この辺の整数を扱う数学の知識を用いていくと良いように思えます。
アフィン暗号の時点では、やはり単一換字式暗号ですので、同じ暗号鍵を用いている文章では頻度分析により破られます。
いかに難しくしても、変換後の文字が定まっているという性質があるためです。
このアフィン変換の工夫可能性を絞り出してみます。
・大文字・小文字、数字、記号、ひらがな、カタカナなどを組み合わせて、$m$を大きくする。
この工夫がセキュリティ的に安全性を高めるかどうかは不明です。
最後に、アフィン暗号のアプリケーションを作成しました。
半角のアルファベットの大文字・小文字に対応しています。
↓↓↓
アフィン暗号で暗号化