なんか大学の先生が「RSA暗号つくってこーい」的な事を言ってたので（実際は言ってない）作ってみましょう。
RSA暗号は有名なアルゴリズムです。でも実態はどうなのかよくわかりませんね。
私は数学には弱いですが、RSA暗号はいろいろなサイトで作り方の解説があるのでそれを参考にすれば理解に一歩近づけるかもしれません。C言語でやっていきます。
注:著者は本当に数学に弱いです( *｀ω´) ﾄﾞﾔｧ
追記:
やっぱCだと辛いなと思ったのでGithubの方にPythonで書いたのも追加しました。
Step0-RSA暗号とは
RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号[1]とデジタル署名を実現できる方式として最初に公開されたものである。
ウィキペディアの執筆者. “RSA暗号”. ウィキペディア日本語版. 2019-08-16. https://ja.wikipedia.org/w/index.php?title=RSA%E6%9A%97%E5%8F%B7&oldid=73876254, (参照 2019-08-16).
との事。噛み砕くと素因数分解を利用して、文を暗号化(よく判らん文字列)する鍵A、文を復号化(元に戻す)する鍵Bを作り出すアルゴリズム。
Step1-RSA暗号を読み解く
RSA暗号を理解するにはフェルマーの少定理が必要です。
高校数学＋α：基礎と論理の物語(著者:宮腰 忠,出版社:共立出版,20010年9月15日初版18刷発行)っていう高校生向けの数学書にRSA暗号について記述があるので要所を抜粋・引用します。
注:特に明記しない限り、この章の引用は高校数学＋α：基礎と論理の物語よりとします
注2:引用ブロック内で最後に記載されている文字はページ数
mod 5で2の2乗,3乗,5乗を計算してみてください.2^4=16≡1(mod 5).よって2^5≡2(mod 5)ですね.mod4で2を5乗すると2戻りましたね。mod 5で2を5乗すると2に戻りましたね。これは単なる偶然ではありません.(略)このようなことが一般に成り立つことを示したのがフェルマーの定理です:
pを任意の素数とする.このとき,任意の整数aに対してa^p≡a(mod\ p) \ \ \ \ (aは任意の整数)が成り立つ.特にaがpで割り切れない時
a^{p-1}≡1(mod\ p) \ \ \ \ (a≠0 (mod\ p))が成り立つ.
54
という事で、「はぁ(´・ω・｀)わからん」となります。詳細は同本の55ページに対偶を用いる証明があるので気になった方は図書館で探すか、買ってみてください。ちなみに証明を見たときの私は「はぁ(´・ω・｀)わからん」です。はい。
ここで重要なのは
a^p-1≡1(mod\ p) \ \ \ \ (a≠0 (mod\ p))56
これです。これがRSA暗号につながるのです。この式だけならそう難しい事は書いてないですね。
それを、2式用意して変形したりすると(過程が気になった方は図書館で探すか、買ってみてください)
整数aを文字aと呼ぶと,文字aを暗号文字a'に変換し,元のaに戻すには,E, Dをある自然数として上式が
a^{n(p-1)(q-1)+1}=a^{ED}=(a^E)^D≡a \ \ \ (mod\ pq)のように表され,
a'≡a^E \ \ \ (mod\ pq),a'^D≡a \ \ \ (mod\ pq)となっていれば良いですね.その条件は
n(p-1)(q-1)+1=EDです
56-57
この時Eは公開鍵でDは秘密鍵,nは自然数です。
この条件を満たせばRSA暗号鍵をつくれるんですね。
具体的な暗号鍵・復号鍵の作成使用について
注:ここら先の内容の正確性について責任を持てません。悪意はありませんが間違っている可能性があります。
基礎はわかったのでwikipediaのRSA暗号の鍵生成を見ましょう。
手順
1.ランダムな素数p,qを求める
2.n=pq
3.(p-1)(q-1)とお互いに素なeを求める。
4.de≡1 mod((p-1)(q-1))からdを求める。
dの求め方
\frac{de}{(p-1)*(q-1)}=x...b
とすると
de-x(p-1)(q-1)=1
この式は拡張ユークリッドの互除法で解けるのがわかる
de - x(p-1)(q-1) = gcd(e, (p-1)(q-1))
gcd(e, (p-1)*(q-1))=1
ちなみに以下の式
d= \frac{x(p-1)(q-1)-1}{e}
見覚えがありますね。先程の暗号鍵と復号鍵を作成する為の条件式に帰ってきました。
アルゴリズムとしての拡張ユークリッドの互除
なんか調べると乗法の逆元を求めるためのアルゴリズムとかいう説明もありました。
乗法の逆元で代表的なのは逆数ですね。xの逆元は1/x
x\frac{1}{x}=1
拡張ユークリッドの互除法は
mx+ny=gcd(m, n)
となるm,nを求めるものなのですが、これは言い換えるとx,yにm,nを掛けてgcd(m, n)とする逆元を求めるという事ですね。
拡張ユークリッドの互除を使っていきましょう。
これも解説したかったんですが、残念な事に文章化できるだけの理解に達しませんでした。
はやわかり RSAさんがとても参考になるので、それを参考にしてみてください。
できたコード。
/*拡張ユークリッド互除法
** ax+by=gcd(a,b)を求める問題を解く
** ただ、この関数ではgcd(a,b)=1の時のみ解く
*/
long euclidEx(long a,long b){
long x;
long y;
long x1 = 1;
long x2 = 0;
long x3;
long y1 = 0;
long y2 = 1;
long y3;
long result1 = a;
long result2 = b;
long result3;
long q;
while(1){
q = result1 / result2;
x3 = x1 - (q*x2);
y3 = y1 - (q*y2);
result3 = result1 - q*result2;
if(result3==1){
if(y3<0){
return y3+a;
}
return y3;
}
x1 = x2;
y1 = y2;
result1 = result2;
x2 = x3;
y2 = y3;
result2 = result3;
}
return 0;
}
これは結果が、0より小さい時は(p-1)(q-1)を足して正の整数にするための操作です。mod((p-1)(q-1))からみると同じ値です。
if(y3<0){
return y3+a;
}
暗号化
b=a^{e}\ mod\ n
の計算をすればOKです......が、素直にやるとaのe乗はとんでもない桁数で容易くオーバーフローします。
なので、少し工夫します。
例として3の5乗と法5に対して合同な値を求めたいとします。
3^5≡b\ mod\ 2
は
3^{4+1}≡b\ mod\ 2
です。この時
(3^4≡a_1 \ mod\ 2)×(3^1≡a_2 \ mod\ 2)≡b\ mod\ 2
の様に分解しても成り立ちます。
試してみましょう。
Aパターン
3^5=243
243\ modulo\ 2=1(=b)
Bパターン
(3^4≡a_1 \ mod\ 2)×(3^1≡a_2 \ mod\ 2)=1×1=1
1\ modulo\ 2\ =1
この通りです。こうすることでオーバーフローを防げます。
また、
3^5=3^{4+1}=3^{2^2+1}
ですが、これ指数部を2進数に治すと
5(10)=2^2+2^0(10)=101(2)
注:かっこの中の数字は基数
というようにプログラムと相性がよく、バイナリ法というアルゴリズム名があります。
Wikipediaに綺麗なコードがあるので、理解した後採用しましょう。
long encryption(long a,long e,long n,){
return modpow(a,e,n);
}
復号化
a=b^d\ mod\ n
です。暗号化と同じですね。
完成！
できました。
ソースコードはGithubにあげてるので興味があればどうぞ。
$ gcc -lm rsa.c
$ ./a.out
n(公開鍵1)->9379243
e(公開鍵2)->3538897
d(秘密鍵)->2261073
634を9379243,3538897で暗号化->5390988
5390988を9379243,2261073で復号化->634
試しに634を暗号化してみると、5390988という数値になってそれを元に復号すると634に戻っていることを確認できます。
やったー！
課題:p,qが大きいと途中でオーバーフローして戻りません。Cだからね......
拡張されたユークリッドの互除法も理解しきれていない。