こんな本を買った。
『RSA 暗号技術の基礎からC++による実装まで』
ソフトの認証を行うのに、シリアル番号とパスワードを使いたいから。
シリアルは、一定の桁数のランダムな数値とする。
パスワードは、シリアル番号に対してある演算をすることで求められる値とし、
パスワードに逆の演算を行うと、シリアル番号に戻る。
まさに暗号と復号であり、これが何とも奥が深い。
他人に予想できず、それらしい演算である必要がある。
とりあえず、自己流につくってはみたが、どうも満足できない。
ネット上にそれっぽいものが落ちてないか何度も調べたが、なかなかない。
そこで何度も引っかかってきたのが前記の本。
本を買ってまで実装するものかと迷うこと、5年。
ずいぶん長いこと迷ったものだが、昨日この本が届いたので、
ななめに読んで30分で内容をつかんだ。
RSA暗号とは．．．。（Wikipediaから引用）
桁数が大きい合成数の素因数分解問題が困難であることを安全性の
根拠とした公開鍵暗号の一つである。
暗号(Cipher)とデジタル署名(Digital signature)を実現できる方式として
最初に公開されたものである。
RSAでは、512ビットの鍵を使うのが一般的だ。
512ビットの数値ということは、2の512乗のことであり、
10進数にすると154桁の整数ということになる。
C言語の標準で扱える最大の桁数は、doubleの16桁程度。
16桁と154桁では、天と地ほど違う。
しかも、512ビットでは解読されてしまうリスクがあるらしく、
今後は1024ビットや2048ビットの鍵が使われるとのこと。
616桁の整数を扱うってことだ。
こんな巨大な整数のことを、Multi-Precision IntegersといいMPIと略す。
和・差・積・商といった基本的な演算から始まり、素因数分解や
最小公倍数、最大公約数、素数、乱数を求める。
要するに、小さい値を基本語長の値として演算を行い、
オーバーフローしそうになったら、もうひとつの基本語長の値を利用して、
繰り上げていくというわけだ。
考え方はシンプルだが、この処理をいかに高速にするかが超難しい。
昔、分数を約分するコードを独自に書いたことを思い出した。
2,3,5,7,11といった小さな素数で順番に割っていくという、
何の工夫もない、くだらないプログラムだ。
約分するためには、最小公倍数で割っていけばいいということは
わかっていたが、この最小公倍数を求めるのが難しい。
ユークリッドの互除法というのを、この本で知った。
aとbの最大公約数を求める関数を転記してみる。
long getGCD( long a, long b )
{
while( b != 0)
{
long w = a % b;
a = b;
b = w;
}
return( a );
}
たったこれだけかと、唖然とした。
世の中、頭がいい人はいるものだ。
この際、暗号はどうでもよくなってきた。
円周率を1兆数千億桁求めて世界記録達成、なんてのがニュースになる。
円周率は3.05より大きいことを証明せよ。こんなテーマに取り組んだことがある。
円周率の整数部をたった1桁導き出すのに、たいへんな苦労をしたものだ。
この本で学んだことで、100桁くらいは独力で出せそうな気がしてきた。
暇で暇でしょうがないときに、やってみようと思う。
こんなことしても、金にならないのが残念なことではあるけれども．．．。