ハッカーの記事を深く理解する
この記事が面白そうなので、
勉強しながら、気づいた点をメモ
詳しくは、ここに書かれている。
今度、じっくり読もう。
まずは、公開鍵情報の見方
- Modules - 2つの素数の積
- Exponent - 通常は65537（0b10000000000000001だから）。詳しくは上のリンクを参照
次は、「Fermat法」について
Fermat法は素数同士の積からなる合成数において、二つの素数の差が小さい場合に有効なアルゴリズムである。 具体的には、合成数nの平方根周辺のある値をxとしたとき、(x-k)*(x+k) == nとなるkを小さいものから求める
らしいが、数式にするとわかりやすかった
√n ≒ x
n = (x+k)(x-k)
こうすると、直感的には理解出来る。
GCDって何や？！
GCDは、Greatest Common Divider の略で、
英語のwikiで、説明読んで、
一瞬、ん？ってなったけど、「最大公約数」のことらしい。
お次は、「フェルマーの小定理」
Stage3のプログラムを読んでいたら、
is_prime()関数に、謎の素数判別プログラムがあった。
まず、pow(x, y, z)って命令は、
x ** y % z
と等価です。
そして、この関数は、フェルマーの小定理に則っていて、
a^(p-1) == 1 (mod p) が成り立つ時、pは素数
というもので、(mod p)というのは、
両辺をpで、除算した余りとしたとき、式が成り立つよ!って意味です。
さて、最後のWiener's Attackだけど、
理解に時間がかかりそうなので、
次の機会にまとめます。
