DiaryINDEX｜past｜will
| 2004年06月27日(日) | 素数が作る魔法の鍵 |
素数の性質を使うと、暗号化する鍵を一般に公開しながら、しかもこれを解く鍵がなければだれも解けないという理想の暗号がはじめて可能になる。そのしくみを、「数あてクイズ」を使って、できるだけやさしく説明してみよう。
まず、友人に１〜３２までのなかで、好きな数をひとつきめてもらう。いま仮に、それをｘ１としよう。つぎに、その数を二乗してもらう。もし二乗した数が＜３３＞より小さかったらその数を、＜３３＞より大きかったら３３で割ったあまりをｘ２とする。さらにこの操作をもう二回繰り返して、ｘ４を求めてもらい、それを発表して貰う。
たとえば、ｘ１＝６だとしよう。そうすると、６×６＝３６、３６−３３＝３なので、ｘ２＝３である。さらに、３×６＝１８なので、ｘ３＝１８。１８×６＝１０８、１０８−９９＝９なので、ｘ４＝９ということになる。だから、友人は、「得た数字は９です」と告げるだろう。
そうすると、私は＜ｘ４＝９＞という情報をもとに、もとの数であるｘ１を求めなければならないわけだ。そのためには、このあと、同じ操作をあと７回（１１−４＝７）繰り返してｘ１１を求めればよい。なぜなら、ｘ１＝ｘ１１が成り立つことが分かっているからだ。つまり、次のようにして、ｘ１＝６が得られる。
ｘ５＝２１、ｘ６＝２７、ｘ７＝３０、ｘ８＝１５、ｘ９＝２４、ｘ１０＝１２、ｘ１１＝ｘ１＝６
この計算はなかなか面倒だが、コンピュータなら一瞬だろう。そしてこの「数あてクイズ」こそ、現代行われている暗号技術のエッセンスである。少し整理すると次のようになる。
�仝曲牽�１を（３３、４）で暗号化して、ｘ４を求める。ｘ４が得られた暗号文である。
��暗号文ｘ４を解読鍵＜３３＝３×１１、ｘ１１＝ｘ１＞で解読して、原文ｘ１を得る。
ここで大切なのは、暗号化する手続き（暗号化キー）と、解読する手続き（解読キー）が別々なことだ。そして、さらに重要なのは、ｘ４からｘ１１を求めることはできても、ｘ４から、ｘ３，ｘ２と遡ってｘ１を求めることは不可能に近いということである。この不可逆性によって、暗号文の安全性がまず保障されている。
それでは、＜ｘ１１＝ｘ１＞という解読キーは大丈夫だろうか。実は、素数の性質について詳しい人なら、このくらいのことはたちどころに見破ることができる。次のような簡単な計算から、この式が導かれるからだ。
まず、＜３３＞という数字が、３×１１という素数の積であることに注目する。そして、３と１１から、それぞれ１を引いて、３−１＝２、１１−１＝１０という二つの数字を得る。さらに、２と１０の（最小）公倍数を求めると１０。これに１を足して１１という数字が得られる。この１１を使って、ｘ１１＝ｘ１を導く。
つまり途中を省略して言えば、＜３３＞が＜３＞と＜１１＞に素因数分解できれば、この暗号はだれにでも解けるということだ。式であらわすと、次のようになる。
ｎ＝（ｓ−１）（ｖ−１）＋１
＝（３−１）（１１−１）＋１
＝（２×１０）＋１
＝２１（２と１０の最小公倍数１０を使うと１１）
しかし、これは＜３３＞という数が小さいからである。昨日の日記に書いたように、これが１００桁を超えるような大きな数字だと、＜あらかじめその答えを知っている者＞以外、これを二つの素数に分解することはむつかしい。つまり、巨大な素数をつかうことで、この暗号文の安全性はいくらでも高めることができる。
さて、以上の議論を一般化しておこう。暗号制作者は、まずｓとｖという二個の素数を考え、これの積ｗ＝ｓｖを求め、ｗで公開用の暗号鍵を作る。この暗号鍵を渡された人は、これによって、文ｘ１をｘｍへと暗号化する。ここでｍはｗの値によって導かれる適当な整数である。「数あてクイズ」ではｗ＝３３，ｍ＝４であった。つまり公開鍵は（ｗ、ｍ）＝（３３，４）である。
こうして作られた暗号文ｘｍを解読するには解読鍵＜ｗ＝ｓｖ、ｘ１＝ｘｎ＞を使えばよい。ここで整数ｎはどうして求めるかといえば、ｓ−１とｖ−１の２数の最小公倍数を求め、これに１を加える。「数あてクイズでは、＜ｗ＝ｓｖ、ｘ１＝ｘｎ＞＝＜３３＝３×１１、ｘ１＝ｘ１１＞であった。暗号の安全性はｗ＝ｓｖの素因数分解が容易でないことである。
素数を使ったこのすばらしい暗号化の理論は１９７７年に生まれた。MIT （マサチューセッツ工科大学） に勤務していた Rivest, Shamir, Adleman という三人の研究者によって発明されたので、これは、「ＲＳＡ暗号」と呼ばれている。その後、Rabin 暗号、ナップザック暗号、ElGamal 暗号、楕円暗号などが発明されたが、現在まで実際に広く実用化されているのはＲＳＡ暗号 だけだ。
ＲＳＡ暗号はインターネットのセキュリティや軍事情報などの国家機密にも使われている。したがって、重要な戦略物資として、技術の輸出が厳しく規制されている。暗号技術先進国のアメリカの場合、政府は自国で素因数分解可能な桁数の「暗号」しか流通を認めようとしないのではないかといわれている。ときおり暗号の基準が高度なものにまで緩和されることがあるが、これはアメリカ政府のセキュリティ機関ＮＳＡ でその長さの暗号の解読が可能となっていることの証拠だという。
情報化した世界を根底で支えているＲＳＡ暗号の安全性は、素因数分解の困難性によって厳重に保障されている。しかし、素因数分解を効率的に行う方法が奇跡的に発見されたら、一挙に世界の安全性は崩れ去る。
こんな物騒な研究をしていたら、命がいくつあってもたりない。日本の民間企業は世界一の高速コンピュータを作ることに熱心だが、これはアメリカにとって原子爆弾以上に危険なことだ。いまに「年次改革要望書」で、政府は改善を要求されるに違いない。いや、しっかり読めば、もうどこかに書かれているのだろう。
（参考サイト）
http://www.maitou.gr.jp/rsa/index.html
