- 作者: マーカスデュ・ソートイ,Marcus du Sautoy,冨永星
- 出版社/メーカー: 新潮社
- 発売日: 2013/09/28
- メディア: 文庫
- この商品を含むブログ (32件) を見る
マーカス・デュ・ソートイ 富永 星 訳 「素数の音楽」
第十章 <因数分解と暗号解読> メモ
・すべての数は素数の積で表すことができるが、因数分解の効率的な方法は
見つかっていない。・数学者たちは、因数分解が難しい事実を使って暗号の作成法を編み出し、因数分解は
暗号解読の核心となっている。
・公開鍵暗号:二種類の鍵がついたドアのようなもので、ドアを閉めるときには
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桁の数を因数分解した。
・暗号システムは人間のミスに弱い。