暗号解読に興味を持つ
松井氏に暗号の世界にのめり込むきっかけを与えた差分解読法の論文。1990年開催の国際学会「Crypto’90」で，イスラエルの研究者Eli Biham氏とAdi Shamir氏が発表した。タイトルは「Differential Cryptanalysis of DES―like Cryptosystems」。この解読法の発表は，学会を中心にセンセーションを巻き起こした。その後幾つかの暗号アルゴリズムに対して，この原理を適用した評価結果が報告されている。
論文を読んで驚いた。そこで繰り広げられていたのは，単純な原理から鮮やかな結果を導き出す，極めてエレガントな数学理論だったのだ。暗号については素人の松井でも，すらすらと論文を読み進めることができた。
松井が手にした論文は，1990年4月にイスラエルの研究者Adi Shamirらが記したものである。この論文で提案した解読法は，後に「差分解読法」として広く世に知られるようになる。
計算量を劇的に減らす
松井を驚かせたのは，この手法が暗号解読に必要な計算量を劇的に減らせることだった。FEALなどの，いわゆる共通鍵暗号の解読とは，唯一の秘密情報である鍵データを推定することである。鍵データを解読者に特定されれば，秘匿した情報はたちどころに暴かれてしまう。
当時，暗号の解読法として確立していたのは「全数探索法」と呼ばれるものだった。考えられるすべての鍵の組み合わせを試して正しい鍵を求める方法だ。ただしこの手法は計算量が膨大であり，必ずしもすべての暗号を解読できるとは限らない。通常，暗号が解読不能と見なされるのは，鍵データを求める計算量が膨大で，事実上特定できないからだ。例えば鍵の長さが56ビットの場合，256組，すなわち約7京個の鍵を用意して計算する必要がある。当時の最先端のスーパーコンピュータを使っても2000年かかる計算量であり，事実上解読不可能といわれた。
鍵を推定する「暗号解読」
共通鍵暗号は，送り手と受け手が同一の秘密の鍵を共有することで，第三者に内容が漏れない通信を可能にする。共通鍵暗号の解読とは，暗号アルゴリズムを知った上で，唯一の秘密情報である鍵データを推定することである。
暗号処理の「偏り」を利用
Shamirらの差分解読法は，鍵データを求めるのに必要な計算量を大幅に引き下げる。基本的な発想は，暗号化処理に潜む「偏り」を利用しようというものだ。どんな暗号の中にもわずかな相関が潜んでいる。これを手掛かりに，暗号解読に必要な計算量を減らそうというのである。 ＝敬称略
―― 次回へ続く ――
