暗号とは何か、何であるべきか
暗号のモデル化
暗号は図2で与えるように2変数関数でモデル化される。Mを平文(ひらぶん)と呼び、それを暗号化したものCを暗号文と呼ぶ。k_{c}を暗号化鍵、k_{d}を復号鍵と呼ぶ。fは暗号化を行う暗号化関数であり、f^{-1}はその逆関数である復号関数である。以下、k_{c}はkに対してcという文字を下付きに添えることを表す。f^{-1}はfに対して-1を上付きに添えることを表し、fの-1乗のことである。
コンピュータネットワークの出現以降の近代(現代)暗号では、MやCは、一般にビット列、あるいはそれらを束ねたバイト列、ワード列、または整数である。k_{c}とk_{d}はそれが同一か否かによって、共通鍵暗号と公開鍵暗号に分かれる。以下では、特に断らない限り、暗号化鍵、復号鍵を同一とする共通鍵暗号を扱う。
暗号を設計することはfという関数を設計することである。通常、fは数式や、nビット入力nビット出力(鍵を考慮すると、k+nビット入力、ただしkは鍵のビット長)の論理回路あるいは状態遷移関数となる。ここで、MやCの入力および出力ビット幅はnビットとする。暗号化鍵を固定し、nビットのMに対して、ただ1つのCが決定するとき、この暗号を「ブロック暗号」と呼ぶ。一方、同様に暗号化鍵を固定したとき、nビットのMだけでは出力であるCが決定できず、一般に過去のM、すなわち暗号ブロックの影響によってCが変化する暗号を「ストリーム暗号」と呼ぶ。
DESやAESと呼ばれる暗号はブロック暗号であり、RC4はストリーム暗号である。一般にストリーム暗号はブロック暗号に比較して高速である。安全性に関する議論に関しては、ブロック暗号に比較してストリーム暗号は必ずしも進んでいないが、近年、活発に研究が行われている。
近代暗号の条件
キューブリック監督の「2001年宇宙の旅」という古典的SF映画に出てくるHALというコンピュータの名前は、ある文字、もしくは記号やビット列をほかの文字に入れ替えるという換字暗号の例として有名である。特に、HALのようにアルファベットの位置をずらす方式は、最も古典的な暗号である「シーザー暗号」と呼ばれている。
シーザー暗号をモデル化した暗号化関数に当てはめると、アルファベットの各1文字が平文となり、暗号関数は文字をずらす操作となる。鍵はA→B、B→C...、のように入れ替える方式であることから、A→C、B→D...、あるいはA→D、B→Eというようにずらす文字数である1から25までの25通りである。シーザー暗号が暗号であったゆえんは、暗号化関数fと鍵が同時に第三者に漏えいしない仮定であった。シーザー暗号であるとわかれば、鍵は25通りしかないゆえにすべての鍵を試すことによって解読が可能となる。
鍵については、コンピュータやネットワークの出現によって、10^{30}以上の鍵が必要となった。事実、1974年から1994年まで米国商務省認定の標準暗号であったDESは、事実上の鍵長が56ビット、すなわち鍵数が2^{56}≒10^{16}程度であり、1997年にインターネットを介して7万台以上のパソコンを利用し、96日間で鍵の全数探索によって解読されている。
このような鍵の全数探索による解読方法を一般に「ブルートフォースアタック」と呼ぶ。現在では56ビット鍵程度であれば、10万台のパソコンを利用して、数分以内に解読することが可能である。鍵の全数探索のみで評価するならば、56ビット鍵が仮に1秒で全数探索可能であるとすれば、現在の暗号の標準的な鍵長である128ビットであれば、100兆年かかる計算となる。
鍵長が128ビット以上であることは暗号の安全性にとって必要条件であるが、鍵長が128ビット、すなわち鍵数が10^{30}以上あるからと言って、安全とは限らない。事実、第二次世界大戦当時に各国が英知を結集して開発した暗号方式もすべて鍵数が10^{30}以上であった。しかし大戦後、それぞれの暗号がほとんどすべて解読されていたことが知られている。この第一の原因は、国家機密であった暗号器が容易に流出したことによる。暗号器および暗号アルゴリズムの欠点をついて、鍵の全数探索よりも効率的に解読する方法を「ショートカットアタック」と呼ぶ。
暗号が国家機密でなく、民生用に用いられる現在、非常に特殊な用途で利用し、かつ多大なコストをかけない限り、暗号アルゴリズム、すなわち暗号化関数fを秘匿することは不可能である。現在では、暗号アルゴリズムは公開し、その安全性を鍵のみに依存させることを前提としている。