CAD日記

AutoCAD,DXF,DWG,SXFなどCADのことから、仮想通貨や投資関係、PC関係、プログラミング、国内海外旅行情報など何でもござれ。@caddiary

ソフト開発

暗号

投稿日:2010年5月11日 更新日:

こんな本を買った。
『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桁くらいは独力で出せそうな気がしてきた。
暇で暇でしょうがないときに、やってみようと思う。
こんなことしても、金にならないのが残念なことではあるけれども...。

-ソフト開発
-

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

関連記事

no image

random

JavaScriptと格闘してみたよ。 テーマはランダム。 10個の画像の中から、任意の3個の画像をWebサイトに表示する、 ってのが要求仕様。 Math.floor(Math.random() * …

no image

PMサーバー版リリース

ペーパーモデル化ツールサーバー版の宣伝。 詳しくは、kensetsu21のこちらのサイト(PDF)をご覧あれ。 クライアントは、サーバー上の共有フォルダにファイルを ドラッグ&ドロップするだけ。 サー …

no image

C#勉強中

Cから入ってC++になり、C#をやることになりました。時代はWebアプリケーションということなので。同じCという文字がついているので、まぁ同じようなもんでしょ、と楽観的観測でいたのですが...。初めて …

no image

いたちごっこ1

ソフト開発者とクラッカー。その果てしない戦いの日々をここに記します。現在進行形のその戦いに終止符を打つべく、努力を重ねている今、臨場感をもって伝えられれば、と思います。 その前に、「いたちごっこ」とい …

マルチスレッドプログラミング(C#編)

マルチスレッドプログラミング(C++編)、マルチスレッドプログラミング(VB.net編)に続く第三弾はC#編。