スパイにもたせる暗号：日経サイエンス

	日経サイエンスは米国の科学雑誌「SCIENTIFIC AMERICAN」の日本版です。
	HOME

HOME ＞パズリング・アドベンチャー＞スパイにもたせる暗号

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

スパイにもたせる暗号

デニス･シャシャ

　数論は，かつては素数の不思議な性質に関する深遠な学問と考えられたが，今では暗号の基礎をなすようになった。電子商取引でよく使われる公開鍵暗号システムは， 2つの素数を掛け合わせるのは簡単だが，そうしてできた数を因数分解するのは難しいという，証明はされていないが広く信じられている理屈を利用している〔この公開鍵暗号アルゴリズムは，開発者の名前をとって，リベスト（Rivest）‐シャミア（ Shamir）‐エイドルマン（Adleman）の公開鍵暗号アルゴリズム，略してRSAと呼ばれている〕。

　2つの大きな素数の掛け算はいわゆる「一方向関数」の1例だ。通常の掛け算にはコンピューターを使えば100万分の数秒しかかからず，計算時間はその数を2進法で表したときの桁数（ビット数）の2乗に比例して増える。一方，積の値からもとの2つの素数を見つける因数分解には，512ビットでさえ何時間もかかり，しかも，積の桁数（2 進法表現）のベキ乗で増大していく。公に知られているかぎり，2048ビットの因数分解は実行不可能だ。高速の因数分解アルゴリズムがもしあるとすれば，軍や産業界のスパイ活動のために秘密裏に応用されるだろう。

　今月の問題は，スパイの暗号だ。あなたは隣の敵国にスパイ団を送り込もうとしている。彼らが国境を越えて帰ってくるときに，国境警備隊員にパスワードを提示して，自分が密入国者や敵のスパイではなく自国のスパイであることを証明させたい。国境でもたもたするわけにはいかないので，国境警備隊員がすぐに検証できるパスワードでなくてはならない。また，国境警備隊員はバーでつい口を滑らせることがあるので，パスワードそのものを彼らに教えるわけにはいかない（スパイの口の堅さは信じてもよい）。国境警備隊員にはどのような情報をもたせ，スパイにはどのようなパスワードを提示させるようにすればよいだろう？

　このパズルは1950年代にマッカーシー（John McCarthy，プログラミング言語Lisp を発明した人工知能理論の先駆者）が作り，ラビン（Michael Rabin，非常に多数の重要なコンピュータアルゴリズムを設計した陽気な科学者）が解いた。物足りないという読者は，素数を使わないやり方に挑戦してみてほしい。

	山崎秀記（やまさき・ひでき）

	一橋大学商学部教授。専門は計算機科学。

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。原題名 Prime Spies （SCIENTIFIC AMERICAN October 2002）


会社案内　\| 「日経サイエンス」はこんな雑誌　\|　個人情報の取り扱いについて　\|	Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved