指数型ブロック暗号

 最も基本的な暗号として,カエサル暗号 については既に説明しました。しかしこの暗号は簡単に解読され,実用性はありません。ここでは,整数の法計算を応用した指数型暗号(exponentiation cipher)を説明します。この暗号はPohlig と Hellman によって1978年に提案されたものです。

 原理は比較的簡単ですが,強力です。

指数型暗号

 pを素数とします。eをgcd(e,p-1)=1(1≦e≦p-1)となる正整数とします。このとき,p-1 を法とするeの逆元が存在します(整数の合同参照)。それを d (1≦d≦p-1)とします。このとき,

ed ≡ 1 (mod p-1)

が成立します。従って x (0≦x<p)に対して,フェルマーの小定理から,

xed≡x (mod p)

となります。(x=0のときはフェルマーの定理は使えませんが,この場合上の式は明らかに成立します。)


 上の性質からxの範囲が0≦x<p であることを使うと,dを知っていれば,xeから x が求められることになります。一方eからdは簡単に求まりますが,eまたはd を知らなければ,xeから,xを求めることはできません。(勿論 x=0 の場合は除きます。)従って

x →(暗号化)→ xe →(復号化)→ xed≡ x (mod p)

によって,eを暗号化鍵,dを復号化鍵とする暗号が得られます。これを指数型暗号(exponentiation cipher)と言います。

ブロック暗号

 カエサル暗号のように,1文字づつ暗号化した暗号文は,頻度解析の手法によって解読されてしまいます。そこで,何文字かを1つのブロックとしてそれを暗号化するものがブロック暗号です。1ブロックの文字数(長さ)が大きければそれだけ解読が難しくなります。しかし,それに対応して暗号化の手間も多くなります。

 上の指数型暗号の場合 p が大きければそれに対応して,大きなブロックの暗号として使うことができます。

 ブロック化の方法は色々ありますが,最も単純なものが,ECBモード(electronic codebook mode)と言われる方法です。それは,文字列を各々ブロックの長さに区切り,その文字列をブロックとして使うものです。

 例えば,ABCDEFGと言う文字列を2文字ブロックに分けるのは,

AB CD EF G

と分けます。ここでの場合最後の文字が1文字ですが,このような場合は適当なダミー文字を付け加えて同じ文字数に揃えます。

 実際には,このようにブロック化されたものを数値に変換して使います。

 例を使って説明しましょう。カエサル暗号の場合と同様に,アルファベットAからZを使って書かれた文を暗号化することにします。

 今の場合7文字を1ブロックとしてします。すると,

TINYBASICISAFREESOFTWARE

という文章は,7文字で区切り

TINYBAS ICISAFR EESOFTW AREXXXX

となります。最後は3文字です。この場合,適当な文字を追加して全て同じ長さにします。今の場合,Xを必要な分だけ加えています。

となります。この7文字の1ブロックをそれぞれ,2文字づつ前のように,

アルファベット A B C D E F G H I J K L M
対応数 00 01 02 03 04 05 06 07 08 09 10 11 12
アルファベット N O P Q R S T U V W X Y Z
対応数 13 14 15 16 17 18 19 20 21 22 23 24 25

によって,文を数字の列に直します。このようにすると

TINYBAS ICISAFR EESOFTW AREXXXX

は,

19081324010018 08020818000517 04041814051922 00170423232323

となります。


1ブロックを1つの数と見ると,このようにして表れる数の最大数は

25252525252525

です。そこでこれより大きい素数 p を適当にとります。今の場合 p=25252525252561としましょう。

そこで,e として,gcd(e,p-1)=1 となる1≦e≦p-1 を適当に取ります。eは有る程度大きいものとします。例えば,e=9863829462317 とすると,gcd(e,p-1)=1 となります。

 この暗号化鍵 e に対する復号化鍵 d は 合同式

9863829462317x ≡ 1 (mod 25252525252560)

の解として得られます。1<d<p-1の範囲にあるこの解dは d=25064170523384で与えられます。


このe=9863829462317を使って上の文

19081324010018 08020818000517 04041814051922 00170423232323

をそれぞれpを法にして,e乗すると暗号文が得られます。

14737425910067 06115440204283 17560863321121 00850355616163

これらを,pを法にして,d乗するともとの文が得られます。

まとめ

 指数型暗号の暗号化及び復号化で使われる計算は,拡張ユークリッドの互除法と冪乗法です。これらの計算は,高速アルゴリズムがあり,かなり大きな数でも実際的な時間内で計算可能です。一方扱われる数はかなり大きな数ですから,これらを鍵無しで解読することはかなりの困難が伴います。

 実際に使う場合,この例より大きなブロックを使う必要がありますが,Tiny Basic でも上の例の程度の計算は可能です。上の例を実際に計算したプログラムexcipher.tbtここにあります。お試し下さい。