アフィン暗号

アフィン暗号は、アルファベットの各文字を対応する数字にマッピングし、簡単な数学関数を使用して暗号化した後、文字に戻すという、単一アルファベット置換暗号の一種です。使用される式は、各文字が別の 1 つの文字に暗号化され、またその逆になることを意味しています。つまり、この暗号は、どの文字がどの文字に対応するかを規定する規則を持つ、基本的に標準的な置換暗号です。そのため、すべての置換暗号の弱点を持っています。各文字は、関数 $(ax + b) mod 26$ を使用して暗号化されます。ここで、 $b は$ シフトの大きさです。

説明

$ここでは、サイズm$ のアルファベットの文字が、まず $0 ... m - 1の$ 範囲の整数にマッピングされます。次に、モジュラー演算を使用して、各平文文字に対応する整数を、暗号文文字に対応する別の整数に変換します。1文字の暗号化関数は次のようになります。

E(x)=(ax+b){\bmod {m}}

ここで、法 $m$ はアルファベットのサイズ、 $a$ と $bは$ 暗号の鍵です。値 $aは$ $a$ と $m$ が互いに素となるように選択する必要があります。復号関数は

D(x)=a^{-1}(xb){\bmod {m}}

ここで、 $a -1$ $は、 m$ を法とする $a$ のモジュラー逆数である。すなわち、次の式を満たす。

1=aa^{-1}{\bmod {m}}

$a$ の逆数は、 $a$ と $m$ が互いに素である場合にのみ存在します。したがって、 $a$ の制約がなければ、復号化は不可能になる可能性があります。復号化関数は暗号化関数の逆であることが次のように示されます。

{\begin{aligned}D(E(x))&=a^{-1}(E(x)-b){\bmod {m}}\\&=a^{-1}( ((ax+b){\bmod {m}})-b){\bmod {m}}\\&=a^{-1}(ax+bb){\bmod {m}}\\&=a^{-1}ax{\bmod {m}}\\&=x{\bmod {m}}\end{aligned}}

弱点

アフィン暗号は依然として単一アルファベット置換暗号であるため、そのクラスの暗号の弱点を継承しています。シーザー暗号は、暗号化関数が単純に線形シフトに簡略化されるため、 $a = 1$ のアフィン暗号です。アトバシュ暗号は $a = -1$ を使用します。

英語のメッセージを暗号化する特定のケース（つまり、 $m = 26$ ）を考えると、26 の自明なシーザー暗号を除いて、合計 286 の非自明なアフィン暗号が存在します。この数は、26と互いに素で 26 未満の数が 12 個あるという事実に由来します（これらは $aの可能な値です）。$ $a$ の各値には、 26 の異なる加算シフト（ $b$ 値）があります。したがって、12 × 26 または 312 の可能なキーがあります。この多様性の欠如は、ケルクホフの原理に照らして考えると、システムが非常に安全でないことを示しています。

この暗号の主な弱点は、暗号解読者が (頻度分析、ブルートフォース、推測などによって) 暗号文の 2 つの文字の平文を発見できれば、同時方程式を解くことで鍵を取得できるという点にあります。aと $m は互いに素で$ $ある$ ことがわかっているので、これを利用して自動化システムで多数の「偽の」鍵を迅速に破棄することができます。

アフィン暗号で使用されるのと同じタイプの変換が、擬似乱数生成器の一種である線形合同生成器で使用されます。この生成器は、アフィン暗号が安全でないのと同じ理由で、暗号的に安全な擬似乱数生成器ではありません。

例

暗号化と復号化を示すこの例では、アルファベットは A から Z までの文字になり、対応する値は次の表のようになります。

暗号化

この暗号化の例では、^[1]暗号化される平文は「アフィン暗号」であり、各文字の数値については上記の表を使用し、 $a$ を 5、 $b$ を 8、 $m$ を 26 とします (使用されているアルファベットには 26 文字あるため)。a の値のみが制約を受けます。これは、a が 26 と互いに素でなければならないためです。a が取り得る値は $1、3、5、7、9、11、15、17、19、21、23$ $、$ および 25 です。b の値は、 $a$ $が$ 1 でない限り任意です。これは暗号のシフトであるためです。したがって、この例の暗号化関数は $y = E (x) = (5 x + 8) mod 26$ になります。メッセージを暗号化する最初のステップは、各文字の数値を書き込むことです。

ここで、 $x$ の各値を取り、方程式の最初の部分 $(5 x + 8)を解きます。各文字の$ $(5 x + 8)$ の値を見つけたら、 $(5 x + 8)$ の結果を 26 で割った余りを取ります。次の表は、暗号化プロセスの最初の 4 つの手順を示しています。

メッセージを暗号化する最後のステップは、表内の各数値から対応する文字を検索することです。この例では、暗号化されたテキストは IHHWVCSWFRCP になります。以下の表は、アフィン暗号でメッセージを暗号化するための完成した表を示しています。

復号化

この復号化の例では、復号化される暗号文は暗号化の例の暗号文です。対応する復号化関数は $D (y) = 21(y - b) mod 26$ です。ここで、 $a -1$ は 21 と計算され、 $b は$ 8 です。まず、暗号文の各文字に相当する数値を、次の表のように書き出します。

次のステップは、 $21(y -8)$ を計算し、その結果を26で割った余りを取ることです。次の表は、両方の計算の結果を示しています。

暗号文を復号化する最後のステップは、表を使用して数値を文字に戻すことです。この復号化の平文は AFFINECIPHER です。以下は、最終ステップが完了した表です。

アルファベット全体をエンコード

暗号化と復号化を高速化するために、アルファベット全体を暗号化して、平文と暗号文の文字間の 1 対 1 のマップを作成することができます。この例では、1 対 1 のマップは次のようになります。

プログラミング例

次のPythonコードを使用して、アフィン暗号でテキストを暗号化できます。

# アフィン暗号の転置表を出力します。
def  affine ( a :  int ,  b :  int ,  s :  str ): 
    import  string

    D  =  dict ( enumerate ( string . ascii_lowercase ,  start = 0 )) 
    E  =  { v :  k  for  k , v  in  D . items ()} 
    size  =  len ( string . ascii_lowercase ) 
    ret  =  "" 
    print ( size ) 
    for  c  in  s : 
        N  =  E [ c ] 
        val  =  a  *  N  +  b 
        val  =  val  %  size 
        print ( f " { c } ( { N } ) -> { D [ val ] } ( { val } )" ) 
        ret  +=  D [ val ] 
    return  ret

アフィン( 7 ,  3 ,  'foobar' )

参照

参考文献

^ Kozdron, Michael. 「アフィン暗号」(PDF) . 2014年4月22日閲覧。

[1] Kozdron, Michael. 「アフィン暗号」(PDF) . 2014年4月22日閲覧。