[ 詳解 RSA暗号化アルゴリズム ] 動作確認は Linux + gcc で行っています。暗号理論やRSAに関する基本的なこ とは 猿にも分かるRSA暗号 ( http://www.maitou.gr.jp/rsa/index.html ) を 参照してください。他にも検索エンジンなどで調べると概要や基本的な仕組み などの説明が見つかると思われます。 最初に簡単なRSAの概要を説明します。ここでは「素数」や「最小公倍数」や 「最大公約数」といった言葉を使いますので、(おそらく小学生くらいで習っ たはず) 忘れた方は検索してください。 1. 鍵生成 ではRSA暗号化の概要を説明します。 まずは、2つの大きな素数 p, q を選びます。(p, q は 3 以上であればいいの だが実際にはかなり大きくなければならない。具体的には 200桁 とか)そして それらを掛けたものを n とします。 n = p*q さらに p, q それぞれから 1 減算した値同士のの最小公倍数を求めそれを M とします。( lcm(a, b) は a と b の最小公倍数を表していると考えてくださ い ) M = lcm( (p-1), (q-1) ) 実はこの部分はほとんどのRSAの解説本では「p, q それぞれから 1 減算した 値同士を乗算した値を M とする」と書かれてあります。つまり M = ( (p-1) * (q-1) ) ということですがこちらでも構いませんし、暗号化アルゴリズムには影響あり ません。しかし、どちらかと言うと最小公倍数をとる方が正しいようです。よ ってこの記事では最小公倍数をとります。 さて p, q はもういりませんので頭の中から削除してください。残ったものは n と M ですね。では、ここまでを実数で行ってみます。 p = 11, q = 13 ( 3 以上の素数ならばなんでもいいです。勝手に決めて下さい) n = 11 * 13 n = 143 M = lcm( (11-1), (13-1) ) M = lcm( 10, 12 ) 10, 12 の最小公倍数は 60 ですね。 次に d と M の最大公約数をとります。( gcd(a, b) は a と b の最大公約数 を表していると考えてください ) 1 = gcd( d, M ) これが成り立つような d を求めます。(解は１つではありません) d と 60 の最大公約数が 1 になるような d を求めます。ただし d は 2 以上 でなければなりません。 gcd( 2, 60 ) = 2 gcd( 7, 60 ) = 1 gcd(12, 60 ) = 12 gcd(17, 60 ) = 1 gcd( 3, 60 ) = 3 gcd( 8, 60 ) = 4 gcd(13, 60 ) = 1 gcd(18, 60 ) = 6 gcd( 4, 60 ) = 4 gcd( 9, 60 ) = 3 gcd(14, 60 ) = 2 gcd(19, 60 ) = 1 gcd( 5, 60 ) = 5 gcd(10, 60 ) = 10 gcd(15, 60 ) = 15 gcd(20, 60 ) = 20 gcd( 6, 60 ) = 6 gcd(11, 60 ) = 1 gcd(16, 60 ) = 4 gcd(21, 60 ) = 3 えー、一通り計算してみました。全部暗算ですので間違ってたらごめんなさい。 さて gcd( d, 60 ) = 1 を満たす d の値が結構ありましたね。 7, 11, 13, 17, 19 ですね。この中ならどれでもいいのですが、 まぁ 11 と 13 は p, q で使ったので、19 くらいを使っときましょう。よって d = 19 とします。さて今あるのは d = 19, M = 60, n = 143 ですね。次に e * d = 1 ( M を法とする世界 ) を満たす e を求めます。 「 3 を法とする世界」とは「 3 を 0 とみなす世界」と考えることができま す。つまり私たちの世界の 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16..... は 3 を法とする世界ならば 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1..... となります。 5 を法とする世界ならば 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1..... となります。 14 を法とする世界ならば 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13, 0, 1, 2..... となります。 M = 60, d = 19 なので e * 19 = 1 ( 60 を法とする世界 ) を満たす e を求めることになります。(解は１つではありません) 1 * 19 = 19 6 * 19 = 54 11 * 19 = 29 16 * 19 = 4 ... 2 * 19 = 38 7 * 19 = 13 12 * 19 = 48 17 * 19 = 23 ... 3 * 19 = 57 8 * 19 = 32 13 * 19 = 7 18 * 19 = 42 79 * 19 = 1 4 * 19 = 16 9 * 19 = 51 14 * 19 = 26 19 * 19 = 1 ... 5 * 19 = 35 10 * 19 = 10 15 * 19 = 45 ... 139 * 19 = 1 19, 79, 139 の時に満たされることが分かりました。 この中ならどれでもいいので e = 79 にしましょう。これで役者は揃いました。 +-------------------------------------------------------------+ | 公開鍵 n = 143, e = 79 秘密鍵 d = 19 | +-------------------------------------------------------------+ となります。M はもういりません。これで鍵の生成は完了です。 2. 暗号化 では実際に暗号化してみましょう。 平文を 14 とします。(平文は n より小さな数でなければなりません) 公開鍵は n = 143 と e = 79 ですね。平文を c と置き、暗号文を m と置き ます。暗号化の処理はいたって簡単です。 式にするとこう(↓)なります。( 2^5 は「2の5乗」を意味します ) m = c^e ( n を法とする世界 ) 実数でやってみましょう。 m = 14^79 (143 を法とする世界 ) 計算してみます。(14の79乗ですね。しかし数は 143 を法とする世界なので 143 以上になることはありません。) 14^79 = (14^2)^39 * 14 = 196^39 * 14 196 は 143 を法とする世界では 53 ですので 53^39 と表すことができます。 = 53^39 * 14 = (53^2)^19 * 53 * 14 = 2809^19 * 53 * 14 2809 は 143 を法とする世界では 92 ですので 92^19 と表すことができます。 = 92^19 * 53 * 14 = (92^2)^9 * 92 * 53 * 14 = 8464^9 * 92 * 53 * 14 8464 は 143 を法とする世界では 27 ですので.... = 27^9 * 92 * 53 * 14 = (27^2)^4 * 27 * 92 * 53 * 14 = 729^4 * 27 * 92 * 53 * 14 729 は 143 を法とする世界では 14 ですので.... = 14^4 * 27 * 92 * 53 * 14 = (14^2)^2 * 27 * 92 * 53 * 14 = 196^2 * 27 * 92 * 53 * 14 196 は 143 を法とする世界では 53 ですので.... = 53^2 * 27 * 92 * 53 * 14 = 2809 * 27 * 92 * 53 * 14 2809 は 143 を法とする世界では 92 ですので.... = 92 * 27 * 92 * 53 * 14 = 169567776 169567776 は 143 を法とする世界では 92 ですので最終的な暗号文は 92となります。この 92 が暗号文として送信されます。 では 92 を秘密鍵で復号化してみましょう。d = 19, n = 143 ですね。n は公 開鍵ですが暗号化にも復号化にも使用します。 c = m^d ( n を法とする世界 ) 92^19 = (92^2)^9 * 92 = 8464^9 * 92 8464 は 143 を法とする世界では 27 ですので.... = 27^9 * 92 = 729^4 * 27 * 92 729 は 143 を法とする世界では 14 ですので.... = 14^4 * 27 * 92 = 196^2 * 27 * 92 196 は 143 を法とする世界では 53 ですので.... = 53^2 * 27 * 92 = 92 * 27 * 92 = 228528 228528 は 143 を法とする世界では 14 ですので最終的な平文は 14 となりま す。見事 平文と一致していますね。 これが RSA 暗号化の概要です。ではこれをプログラムにしてみます。 3. プログラム http://ruffnex.oc.to/kenji/src/rsa00.c [kenji@localhost rsa]$ gcc -Wall rsa00.c [kenji@localhost rsa]$ ./a.out 11 13 19 79 14 p = 11 q = 13 (p * q) n = 143 lcm((p-1),(q-1)) M = 60 gcd(d, M) d = 19 (e*d = 1) e = 79 暗号化を始めます (平文) c = 14 (暗号文) m = 92 復号化を始めます (暗号文) m = 92 (平文) c = 14 終了 [kenji@localhost rsa]$ 上記の計算例と同じ値を渡しました。ちゃんと暗号文が一致しています。そし て無事に復号化もされています。ではプログラムの説明をします。まずは関数 から。 UINT TheWorld(UINT x, UINT n) { while(n <= x) x = x - n; return x; } この関数は x の値を n を法とした世界の値にし、それを戻り値とします。例 えば n = 10 を法とした世界で x に 99 という数字が代入されてた場合は x が 10 以下になるまで 99 から 10 を減算し続けます。結果的に x = 9 とな り、「10 を法とする世界では 99 は 9 である」ということになります。 UINT lcm(UINT x, UINT y) { UINT a = x; UINT b = y; while(a != b){ if(a < b) a = a + x; else b = b + y; } return a; } 関数名から分かる通り、最大公倍数を取得する関数です。x, y を比較して小 さい方にその変数を加算します。それを続けていきそれぞれが同じ値になれば それが最大公倍数ということになります。 例：12, 15 48, 45 24, 15 48, 60 24, 30 60, 60 (一致！) 36, 30 36, 45 では main関数の説明をします。スミの数字は行数です。 27: n = p * q; DEBUG(n, "(p * q) n"); M = lcm((p-1), (q-1)); DEBUG(M, "lcm((p-1),(q-1)) M"); 簡単ですね。n と M を取得しています。 45: l = 1; i = c; j = e; while(j > 1){ if(j % 2 == 1) l = l * i; j = j / 2; k = TheWorld(i*i, n); l = TheWorld(l, n); i = k; } m = TheWorld(k*l, n); ここが暗号化の処理です。m = c^e ( n を法とする世界 ) この計算をやって います。c には平文が入ってますのでそれをまず i に移します。j が指数で k が値となります。まず平文を二乗して指数 j を 1/2 にします。もしあまり があったならば l に i を掛けます。これは数学の常識ですね。i^j は (i^2)^(j/2) のように i の二乗の j/2 乗と変換できますし、もし余りがあっ たなら i を余分にかけなければならないのでとりあえず余分なものは l にい れとくということです。 最後に k*l をして n を法とする世界の数にして m に代入しています。これ が暗号文です。 66: l = 1; i = m; j = d; while(j > 1){ if(j % 2 == 1) l = l * i; j = j / 2; k = TheWorld(i*i, n); l = TheWorld(l, n); i = k; } c = TheWorld(k*l, n); 復号化の処理ですね。 c = m^d ( n を法とする世界 ) この計算を行っていま す。アルゴリズムは暗号化と同じですので、問題無いかと思います。最終的に c に平文が入ります。 次に進みます。 p, q はともかくとしても、d, e はできればプログラムに計算させたいですね。 ということで d, e を計算してくれるバージョンを以下に示します。 http://ruffnex.oc.to/kenji/src/rsa01.c [kenji@localhost rsa]$ gcc -Wall rsa01.c -o rsa01 [kenji@localhost rsa]$ ./rsa01 11 13 14 p = 11 q = 13 (p * q) n = 143 lcm((p-1),(q-1)) M = 60 gcd(d, M) d = 7 (e*d = 1) e = 43 暗号化を始めます (平文) c = 14 (暗号文) m = 27 復号化を始めます (暗号文) m = 27 (平文) c = 14 終了 [kenji@localhost rsa]$ 今度は引数は p, q, 平文 の 3つ でＯＫです。d, e は勝手に計算して決めて くれます。ではプログラムの解説に行きます。 UINT gcd(UINT x, UINT y) { UINT r; while(y != 0){ r = x % y; x = y; y = r; } return x; } これは最大公約数を求める関数です。何故こうやれば求まるのかは数学を勉強 してください。Euclidの互除法とかで検索すればもしかしたら分かるかもしれ ないです。 int judge(UINT x) { UINT i; for(i=2; i != x; i++){ if((x % i) == 0) return 1; } return 0; } かなり力技ですが、素数かどうかを判定する関数です。2 からその数になるま での全ての数で除算した余りがすべて存在すれば素数である。という判定方法 です。 41: d = 1; while(gcd(++d, M) != 1); DEBUG(d, "gcd(d, M) d"); e = 1; do{ e++; k = TheWorld(e*d, M); }while(k != 1); DEBUG(e, "(e*d = 1) e"); ここが問題でしょう。d, e を求める処理です。d はそのままgcd関数に渡して いき戻り値が 1 となった時点でその数を使用するようにしています。 e は M を法とした世界で e*d = 1 を満たす e を求めなければならないので TheWorld関数にいれて戻り値が 1 になるまで調べています。ただし、これだ と d, e はそれぞれ最初にみつかった数を使用してしまうので「なんかなー」 という感じです。(少なくとも私は^^;)だから次のバージョンではこのへんを ランダムに選ぶようにしようかなと。あと一文字では無くてちゃんとファイル からデータを読み込んで、暗号化していくみたいなカタチに。 4. ちょっと実用的なプログラム http://ruffnex.oc.to/kenji/src/makeKey.c キーを生成してくれるプログラムです。そして http://ruffnex.oc.to/kenji/src/rsa.c 暗号化、復号化してくれるプログラムです。実際に試してみます。 [kenji@localhost rsa]$ gcc -Wall makeKey.c -o makeKey [kenji@localhost rsa]$ gcc -Wall rsa.c -o rsa [kenji@localhost rsa]$ [kenji@localhost rsa]$ cat test.txt これはRSAテストファイルです。 ちゃんと暗号化されたかどうかを判定します。 わはははははははははは。 アルファベットなども書きましょう。 abcdefgffd::@[]\/.--^\^1-2\^1-q;lqa/zzzz?_?>}+`P~|=~)&!kfjd ちゃんと暗号化されるでしょうか。 [kenji@localhost rsa]$ [kenji@localhost rsa]$ ./makeKey p = 11 q = 199 (p * q) n = 2189 lcm((p-1),(q-1)) M = 990 gcd(d, M) d = 29 (e*d = 1) e = 9149 [kenji@localhost rsa]$ [kenji@localhost rsa]$ ./rsa e 9149 2189 test.txt test2.txt ここで暗号化が完了しました。test2.txt をみるとちゃんと暗号化されてます。 では復号化してみます。 [kenji@localhost rsa]$ ./rsa d 29 2189 test2.txt test3.txt [kenji@localhost rsa]$ cat test3.txt これはRSAテストファイルです。 ちゃんと暗号化されたかどうかを判定します。 わはははははははははは。 アルファベットなども書きましょう。 abcdefgffd::@[]\/.--^\^1-2\^1-q;lqa/zzzz?_?>}+`P~|=~)&!kfjd ちゃんと暗号化されるでしょうか。 [kenji@localhost rsa]$ 無事、復号化することができました。パチパチ... ではソースの方をみてみます。 ----makeKey.c 19: srandom(getpid()); if(argc < 2){ while(judge(p = (random() % 255) + 3)); }else{ if(judge(p = atoi(argv[1]))){ fprintf(stderr, "%s 素数じゃないです\n", argv[1]); exit(1); } } srandom, random を利用してランダムな値を取得し、それが素数だったら while を抜けます。素数がでるまで何度もやってます。ランダムな値の範囲は 3 から 257 です。同じ方法で 素数 q も取得しています。 48: if(argc < 4){ d = 1; i = (random() % 10) + 1; while(i-- > 0) while(gcd(++d, M) != 1); }else{ if(gcd(d = atoi(argv[3]), M) != 1){ fprintf(stderr, "%s が正しくありません\n", argv[3]); exit(1); } } d を取得するところです。ソースを見ればわかりますね。ちょっと強引な方 法ですが... e を取得するところも同じです。 makeKey.c はランダムな値を使用してキーを作っているだけです。さほど問題 は無いでしょう。では次は rsa.c にいきます。 ----rsa.c 33: if(stat(argv[4], &st) < 0){ fprintf(stderr, "%s not found.", argv[4]); exit(-1); } if((fp = fopen(argv[4], "rb")) == NULL){ fprintf(stderr, "%s open error.\n", argv[4]); exit(-1); } stat でファイルの存在を調べてます。あるならサイズが st.st_size に入る のでそれをあとで利用します。 43: if(*argv[1] != 'e') st.st_size = st.st_size / 4; if((c_buf = (char *)calloc(st.st_size, sizeof(char))) == NULL){ fprintf(stderr, "calloc c_buf\n"); exit(-1); } if((m_buf = (unsigned int *)calloc(st.st_size, sizeof(unsigned int))) == NULL){ fprintf(stderr, "calloc m_buf\n"); exit(-1); } if(*argv[1] == 'e') fread(c_buf, 1, st.st_size, fp); else fread(m_buf, 4, st.st_size, fp); fclose(fp); st.st_size にファイルのサイズが入ってるのでその分だけ calloc を利用し てメモリを確保します。43: は、もし復号化するなら サイズを 4 で割ります。 そしてデータ(暗号文)を m_buf に unsigned int 型で取得します。もし暗号 化するならデータ(平文)を char 型で取得します。何故こんなことをするのか というと 1byte は 0...255 までですよね。 n を法とする世界で例えば n = 270 だった場合に 1byte ずつ暗号化してい くと 269 になる可能性があります。しかし 269 は 1byte では表せません。 よって必然的に暗号化後のファイルのサイズは大きくなってしまいます。 逆に n = 50 だった場合、平文の 205 (1byte) というデータは扱えません。 平文は必ず n より小さくなければならないからです。 つまり問題として n は 256(1byte) あるいは 65535(2bytes) といった 8 の 倍数ビット数で表せる数でなければならなくなります。これなら 1byte 取得 して暗号化しても、きっかり 1byte で表せる数を返せます。65535 なら 2bytes ずつ取得すればいいわけです。 しかしできれば任意の n を使用したいものです。 この解決策として、暗号化後のファイルサイズを 4倍 にすることにしました。 (もちろん他にもいろいろと解決策はあるでしょうが) n を 255...4294967295 までの範囲と決め付け、1byte を暗号化したらそのデータが 1byte 以上であ ろうが未満であろうが、4bytes として保存します。つまり復号化は 4bytes を取得して 1bytes に戻すことになります。 こうすると n が 255...4294967295 までの間ならなんでもＯＫということに なります。 62: for(i=0; i < st.st_size; i++){ if(*argv[1] == 'e') a = *(c_buf + i); else a = *(m_buf + i); l = 1; j = key; while(j > 1){ if(j % 2 == 1) l = l * a; j = j / 2; k = TheWorld(a*a, n); l = TheWorld(l, n); a = k; } if(*argv[1] == 'e') *(m_buf + i) = TheWorld(k*l, n); else *(c_buf + i) = (unsigned char)TheWorld(k*l, n); } rsa01.c とほとんど同じです。ただ暗号化と復号化で処理を分岐させています。 c_buf は unsigned char 型の 1byte で 平文 を扱います。 m_buf は unsigned int 型の 4bytes で 暗号文 を扱います。 暗号化の場合は c_buf から m_buf へ、復号化の場合は m_buf から c_buf へ 処理を行ったデータを移動させます。 85: if((fp = fopen(argv[5], "wb")) == NULL){ fprintf(stderr, "%s open error.\n", argv[5]); exit(-1); } if(*argv[1] == 'e') fwrite(m_buf, 4, st.st_size, fp); else fwrite(c_buf, 1, st.st_size, fp); fclose(fp); これは簡単ですね。最終的にファイルに書き込んでいます。 5. 最後に これで終了です。RSA暗号化の仕組みが理解できたと思います。仕組みとして は DES よりも単純だと思われますが、暗号化と復号化が別々の鍵で行えると いうところがすばらしいですね。実際にRSAを企業レベルで利用する場合は鍵 生成に使用する素数 p, q は 200桁 くらいの数を使うらしいです。このよう に単純に桁数を増やすだけで強度が増すというのはDESではありえないことで すね。トリプルDESなどで頑張ってはいますがコンピュータの進化が速すぎて DESの存在があやうくなっている今日このごろです。それはそうと暗号理論は やっぱ数学ができなきゃダメだなぁ。 End. written by kenji aiko 2003/12/09 Copyright (C) 2003 kenji aiko All Rights Reserved