ありのままに生きる

社会不適合なぼっちおやじが、自転車、ジョギング等々に現実逃避する日々を綴っています。

マーカス・デュ・ソートイ 富永 星 訳 「素数の音楽」

素数の音楽 (新潮文庫)

素数の音楽 (新潮文庫)

マーカス・デュ・ソートイ 富永 星 訳 「素数の音楽」


第十章 <因数分解と暗号解読> メモ


・すべての数は素数の積で表すことができるが、因数分解の効率的な方法は
 見つかっていない。

・数学者たちは、因数分解が難しい事実を使って暗号の作成法を編み出し、因数分解
 暗号解読の核心となっている。


公開鍵暗号:二種類の鍵がついたドアのようなもので、ドアを閉めるときには
 A(公開鍵)という鍵を使い、開けるときには別のBという鍵を使う。

・顧客は鍵Aを用いて個人情報を暗号化し、サイト側は鍵Bで復合化する。


公開鍵暗号は、スタンフォード大のホイット・ディフィーとマーチン・ヘルマンが
 1976年の論文で提案した。

・MITのロン・リヴェスト、アディ・シャミア、レオナルド・アドルマンがRSA暗号
 を編み出した。


・ネット上の取引のほとんどがRSAを使った暗号化により守られている。

公開鍵暗号システムの起源はピエール・ド・フェルマーによる「フェルマーの小定理」と
 ガウスの時計計算機にある。


フェルマーの小定理

 x^p = x(modulo p)

 適当な素数数xを選んでp時間の時計計算機でp乗すると、p回動いたところで常に
 元の数に戻る


オイラーによる、盤面が N=p×q (p、qは素数)時間の時計計算機への一般化

 (p-1)×(q-1)+1乗目でパターンの繰り返しが始まる


RSA暗号の仕組み>
・ウェブ上の会社は顧客に時計計算機の盤面の時間数"N"(公開鍵)を伝える。

・この時間数"N"は60桁ほどの二つの素数p,n(秘密鍵)の積から成り、桁数は120桁に及ぶ。
 
・顧客はもうひとつの数"E"(暗号化鍵)を受け取る。

・この"E"は時関数"N"と同様、すべての顧客に共通で公にされている。

・顧客はカード番号"C"をサイト上の時計計算機を使用して"E"乗し、暗号化する。


ハッカーは時間数"N"と暗号鍵"E"を見つけられるかもしれないが、N時間の時計計算機の
 上でE乗したときに暗号化されたカード番号になるような数を見つけるのは困難。

・時間数"N"は100桁を越えているため、素数p、qを見つけることも困難。


・ウェブ上の会社は、複合鍵"D"を用いて暗号化されたカード番号をD乗して元の
 カード番号を取り出す。

・秘密の素数p、qを知らない限りこのDを求めることはできない。
 D=(p-1)×(q-1)+1

・p、qを知っているのはウェブ上の会社だけであり、暗号の安全性は時関数Nを因数分解
 するのが困難だという事実にかかっている。


・1977年まで、因数分解のもっとも洗練された方法はフェルマーが見つけた方法だった。

ポメランスの二次ふるい法:フェルマー因数分解法を使いながら、因数分解を試みる
 時計計算機を連続的に変えていく

ポメランスの二次ふるい法は、多数のコンピュータに分散負荷させることができ、
 ネット上のコンピュータ等を結んでRSA129の129桁の数を因数分解した。


・暗号システムは人間のミスに弱い。

RSAでも、実際に運用する人間が容易に因数分解できる数を選んでしまうと威力は弱まる。