最も基本的な暗号として，カエサル暗号 については既に説明しました。しかしこの暗号は簡単に解読され，実用性はありません。ここでは，整数の法計算を応用した指数型暗号(exponentiation cipher)を説明します。この暗号はPohlig と Hellman によって１９７８年に提案されたものです。 原理は比較的簡単ですが，強力です。
pを素数とします。eをgcd(e,p-1)=1（1≦e≦p-1）となる正整数とします。このとき，p-1 を法とするeの逆元が存在します（整数の合同参照）。それを d （1≦d≦p-1）とします。このとき， ed ≡ 1 (mod p-1) が成立します。従って ｘ （0≦ｘ＜p）に対して，フェルマーの小定理から， xed≡x (mod p) となります。（ｘ＝０のときはフェルマーの定理は使えませんが，この場合上の式は明らかに成立します。） 上の性質からxの範囲が0≦ｘ＜p であることを使うと，dを知っていれば，xeから x が求められることになります。一方eからdは簡単に求まりますが，eまたはd を知らなければ，xeから，xを求めることはできません。（勿論 x=0 の場合は除きます。）従って x →（暗号化）→ xe →（復号化）→ xed≡ x (mod p) によって，eを暗号化鍵，dを復号化鍵とする暗号が得られます。これを指数型暗号(exponentiation cipher)と言います。
カエサル暗号のように，１文字づつ暗号化した暗号文は，頻度解析の手法によって解読されてしまいます。そこで，何文字かを１つのブロックとしてそれを暗号化するものがブロック暗号です。１ブロックの文字数（長さ）が大きければそれだけ解読が難しくなります。しかし，それに対応して暗号化の手間も多くなります。 上の指数型暗号の場合 p が大きければそれに対応して，大きなブロックの暗号として使うことができます。 ブロック化の方法は色々ありますが，最も単純なものが，ECBモード（electronic codebook mode)と言われる方法です。それは，文字列を各々ブロックの長さに区切り，その文字列をブロックとして使うものです。 例えば，ABCDEFGと言う文字列を２文字ブロックに分けるのは， AB CD EF G と分けます。ここでの場合最後の文字が１文字ですが，このような場合は適当なダミー文字を付け加えて同じ文字数に揃えます。 実際には，このようにブロック化されたものを数値に変換して使います。
例を使って説明しましょう。カエサル暗号の場合と同様に，アルファベットAからZを使って書かれた文を暗号化することにします。 今の場合７文字を１ブロックとしてします。すると， TINYBASICISAFREESOFTWARE という文章は，７文字で区切り TINYBAS ICISAFR EESOFTW AREXXXX となります。最後は３文字です。この場合，適当な文字を追加して全て同じ長さにします。今の場合，Xを必要な分だけ加えています。 となります。この７文字の１ブロックをそれぞれ，２文字づつ前のように，
によって，文を数字の列に直します。このようにすると TINYBAS ICISAFR EESOFTW AREXXXX は， 19081324010018 08020818000517 04041814051922 00170423232323 となります。 １ブロックを１つの数と見ると，このようにして表れる数の最大数は 25252525252525 です。そこでこれより大きい素数 p を適当にとります。今の場合 p=25252525252561としましょう。 そこで，e として，gcd(e,p-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はここにあります。お試し下さい。 |