俺が説明すると余計難しくなるのでここ参考にどうぞ。

http://pgp.iijlab.net/crypt/rsa.html

最小公倍数と最大公約数と素数判定な処理を書くことと、
x = a ^ b mod c
の計算をどううまくやるかが重要です。

RSA暗号では3桁乗とかやったりするんですが、ふつーにオーバーフローします。
なんなら41682 ^ 634 % 91246とかやってみてください。
凡人の計算機じゃ計算できません。
なのでうまく計算してあげる必要がありまして、

hogehoge(n, a, b) {
ret = 1;
for (i = 1; i <= a; i*=2) {
if (a & i) {
ret = (ret * n) % b;
}
n = (n * n) % b;
}
return ret;
}

ざっくりこんな感じにしていただければ
n ^ a % b
な計算がそこそこできちゃうって寸法ですわ。


最小公倍数とかはユークリッドなんちょれとかも使うので、数学マニアにはたまりません。
俺は数学マニアじゃないので頭が痛くなりました。

あとやっぱ素数判定はどうしても総当たり的なものになってしまうんだけども、どうにかならんのだろうか。




ほんでじゃぁ完成したRSA暗号&復号モジュールでなにしようかってと、パスフレーズの暗号化くらいだよね・・・。
md5とかsha1でハッシュにしたパスフレーズを、更に10進数変換→RSA暗号にすればなんかかっこいいじゃん、なんか。たぶん。