| 前へ << RSA で暗号化してみよう (1) | inetdとは >> 次へ |
プログラムの目的は rsa-1.c と同様で、鍵を作成して暗号化・復号化するだけです。 コンパイル方法と実行結果は以下の通り。
% cc -o rsa-2 rsa-2.c -lcrypto % ./rsa-2 rsa->n=244572674926805241062968088611600028071 (0xB7FEFBDBC2E745B2C627DA1EA15D51A7) rsa->e=65537 (0x010001) rsa->d=541114757532184261555825717500966193 (0x6837047074F48984C2444C589FF531) rsa->p=16764777456439012943 (0xE8A87445E5862E4F) rsa->q=14588483238879488297 (0xCA74B4367126E929) 平文: [abcdefghijklmnop] bn_chunk=129445976596022050476432668810952994672 (0x6162636465666768696A6B6C6D6E6F70) bn_encrypt=26437649953676003874386347523956214860 (0x13E3B4C797083D991B599C78D08B0C4C) bn_decrypt=129445976596022050476432668810952994672 (0x6162636465666768696A6B6C6D6E6F70) 復号した暗号文: [abcdefghijklmnop] 平文: [qrstuvwxyz1234] bn_chunk=150797027069492699164330601711972646912 (0x7172737475767778797A313233340000) bn_encrypt=25390034121517778044968204977444792045 (0x1319F154CFA3597BEDA48F1BBACCA6ED) bn_decrypt=150797027069492699164330601711972646912 (0x7172737475767778797A313233340000) 復号した暗号文: [qrstuvwxyz1234]
RSA *rsa = RSA_generate_key(KEYBIT_LEN, 65537, NULL, NULL);だけで済んでいましたが、今度は自分で計算しなくてはいけません。
24: BIGNUM *bn_e = BN_new(); BN_set_word(bn_e, 65537); 25: BIGNUM *bn_n = BN_new(); 26: BIGNUM *bn_d = BN_new(); 27: BN_CTX *bn_ctx_tmp = BN_CTX_new();まずは e, n, d の領域を確保します。 BN_new を呼ぶと BIGNUM 用の領域が生成されます。 また、BN_set_word を使って、e に 65537 をセットします。
さらに BN_CTX_new を使って BN_CTX 構造体を生成します。 BN_CTX は、BIGNUM 用の関数が一時的に使用する作業用領域です。
例えば BIGNUM の乗算・除算のたびに作業用領域が必要になりますが、 毎回動的にメモリを確保していては時間がかかってしまいます。 よって、あらかじめ呼び出し側で作業用領域を確保しておき、 乗算や除算のたびにそれを使いまわすわけです。
なお、BN_new したら、最後に BN_free を、 BN_CTX_new なら BN_CTX_free を呼ばないとメモリリークしますのでご注意を。
31: BIGNUM *bn_p = BN_new(); /* 素数 p */ 32: BIGNUM *bn_q = BN_new(); /* 素数 q */ 33: 34: BN_generate_prime(bn_p, KEYBIT_LEN/2, 1, NULL, NULL, NULL, NULL); 35: BN_generate_prime(bn_q, KEYBIT_LEN/2, 1, NULL, NULL, NULL, NULL);BN_generate_prime を呼び、素数 p と q を生成します。 素数のビット数は鍵長の 1/2 を指定しています。なぜ 1/2 かと言うと、
n = p * q M < n (M は平文のメッセージ)という条件があるので、鍵長/2 のビット数同士をかけたら n は狙いの鍵長になるのかなと思ったからですが、 いまいち自信がありません。
第三引数に真となる値を渡すと、safe prime (strong prime) と呼ばれる素数を生成します。素数 p があるとき、(p-1)/2 も素数であるものを safe prime というようです。よくわかりませんが、格の高い素数みたいなもんですかね。 なんとなく 1 を指定して、格の高い素数を得てみることにしました。
その他の引数はいろいろ便利なことができるようなので、調べてみてください。
44: BIGNUM *bn_pm = BN_new(); /* p-1 (p minus 1) */ 45: BIGNUM *bn_qm = BN_new(); /* q-1 (q minus 1) */ 46: BIGNUM *bn_pmqm = BN_new(); /* (p-1)*(q-1) */ 47: BIGNUM *bn_gcd_pmqm = BN_new(); /* (p-1) と (q-1) の最小公倍数 */ 48: BIGNUM *bn_L = BN_new(); /* L。(p-1) と (q-1) の最小公倍数 */ 49: BIGNUM *bn_one = BN_new(); /* 1 */ 50: BN_one(bn_one); 51: 52: BN_mul(bn_n, bn_p, bn_q, bn_ctx_tmp); 53: BN_sub(bn_pm, bn_p, bn_one); 54: BN_sub(bn_qm, bn_q, bn_one); 55: BN_mul(bn_pmqm, bn_pm, bn_qm, bn_ctx_tmp); 56: BN_gcd(bn_gcd_pmqm, bn_pm, bn_qm, bn_ctx_tmp); 57: BN_div(bn_L, NULL, bn_pmqm, bn_gcd_pmqm, bn_ctx_tmp);なにをしているかと言うと、
n = p * q L = lcm(p-1, q-1) 注: lcm(a,b) … a と b の最小公倍数これだけです。ただし、OpenSSL のライブラリには最大公約数を求める関数はありますが、 最小公倍数を求める関数はないので、
lcm(a,b) = a*b/gcd(a,b) 注: gcd(a,b) … a と b の最大公約数という公式を使っています。
このプログラムで使用している BN のライブラリ関数を、以下に軽く紹介しておきます (他にも数十個の関数があります)。
文章で書くと簡単ですが、プログラムで実現するのはちょっと面倒です。 詳しい説明は省略しますが、「(e * d) % L = 1」というのは、「L*x + e*d = 1」 となる x と d を求めることと等価です。
x と d を求めるには、「拡張ユークリッドの互除法」を用います。 これまた詳しい説明はしませんが、まず
(x1, y1, z1) ← (1, 0, L) (x2, y2, z2) ← (0, 1, e)と初期化します。そして z2 がゼロになるまで以下の計算を繰り返します。
q ← z1 を z2 で割った商 (x3, y3, z3) ← (x1, y1, z1) - q * (x2, y2, z2) (x1, y1, z1) ← (x2, y2, z2) (x2, y2, z2) ← (x3, y3, z3)z2 がゼロになったとき、y1 に求める d が入っています。 ただし y1 が負になる場合があります。d は 1<d<L を満たす必要がありますので、 その場合は y1 に L を足したものを d とします。
これをコード化したものが以下のソースです。
68: BIGNUM *bn_x1 = BN_new(); BN_one(bn_x1); 69: BIGNUM *bn_y1 = BN_new(); BN_zero(bn_y1); 70: BIGNUM *bn_z1 = BN_new(); BN_copy(bn_z1, bn_L); 71: BIGNUM *bn_x2 = BN_new(); BN_zero(bn_x2); 72: BIGNUM *bn_y2 = BN_new(); BN_one(bn_y2); 73: BIGNUM *bn_z2 = BN_new(); BN_copy(bn_z2, bn_e); 74: BIGNUM *bn_x3 = BN_new(); 75: BIGNUM *bn_y3 = BN_new(); 76: BIGNUM *bn_z3 = BN_new(); 77: BIGNUM *bn_q = BN_new(); 78: BIGNUM *bn_tmp = BN_new();
82: while ( ! BN_is_zero(bn_z2) ){
88: BN_div(bn_q, NULL, bn_z1, bn_z2, bn_ctx_tmp); 89: BN_mul(bn_tmp, bn_q, bn_x2, bn_ctx_tmp); 90: BN_sub(bn_x3, bn_x1, bn_tmp); 91: BN_mul(bn_tmp, bn_q, bn_y2, bn_ctx_tmp); 92: BN_sub(bn_y3, bn_y1, bn_tmp); 93: BN_mul(bn_tmp, bn_q, bn_z2, bn_ctx_tmp); 94: BN_sub(bn_z3, bn_z1, bn_tmp); 95: 96: BN_copy(bn_x1, bn_x2); BN_copy(bn_y1, bn_y2); BN_copy(bn_z1, bn_z2); 97: BN_copy(bn_x2, bn_x3); BN_copy(bn_y2, bn_y3); BN_copy(bn_z2, bn_z3); 98: }
101: BN_copy(bn_d, bn_y1);
102: if ( BN_cmp(bn_d, bn_zero) == -1 ){
103: BN_add(bn_d, bn_d, bn_L);
104: }
これでやっと公開鍵 (d と n)・秘密鍵 (e と n) が手に入りました。
20: unsigned char plain_buf[]="abcdefghijklmnopqrstuvwxyz1234";で、30文字あります (240 ビット)。 一方、鍵の長さは
16: #define KEYBIT_LEN 128です (ビット数であることに注意)。平文が鍵の長さを上回っているので、 これでは暗号化することはできません。そこで、平文を一定の長さで切り出し、 切り出したそれぞれの部分ごとに RSA で暗号化することにしましょう。
120: char *p = plain_buf;
121: int finished = 0;
122:
123: while ( ! finished && *p != '\0' ){
124: int i;
125: BIGNUM *bn_chunk = BN_new();
126: BN_init(bn_chunk);
127:
128: /* 平文を鍵長のバイト数に区切る */
129: printf("平文: [");
130: for ( i=0 ; i<KEYBIT_LEN/8 ; i++ ){
131: char c;
132: if ( *p == '\0' ){
133: finished = 1;
134: c = '\0';
135: } else {
136: c = *p++;
137: }
138: printf("%c", c);
139: BN_lshift(bn_chunk, bn_chunk, 8);
140: BN_add_word(bn_chunk, c);
141: }
142: printf("]\n");
143: BN_PUT(bn_chunk);
かなり見づらいソースで恐縮です。
まず bn_chunk という数を作ります。ここに切り出した平文を格納します。
BIGNUM だと見づらいので、int に置き換えてみたのが以下のコードです。
int bn_chunk = 0;
for ( i=0 ; i<strlen(plain_str) ; i++ ){
bn_chunk <<= 8;
bn_chunk += plain_str[i];
}
例えば plain_str が "abcd" で KEYBIT_LEN が 32 であれば、
(a〜d の文字コードは 0x61〜0x64 ですから) bn_chunk は 0x61626364 になります。
if ( *p == '\0' ){
c = '\0';
}
は文字列が鍵長の長さに満たない場合に 0 をパディングしています。
PKCS#1 であれば、こういうところもちゃんと考えられて作られています。
暗号化: RSA_private_encrypt(strlen(plain_buf), plain_buf, crypted_buf, rsa, RSA_PKCS1_PADDING) 復号化: RSA_public_decrypt(crypted_len, crypted_buf, decrypted_buf, rsa, RSA_PKCS1_PADDING)としていました。ここを自分で処理するよう変更します。
といっても、非常に簡単です。RSA における暗号化・復号化とは、以下の計算にすぎないことを思い出してください。
149: BN_mod_exp(bn_encrypt, bn_chunk, bn_e, bn_n, bn_ctx_tmp);bn_chunk を bn_e 乗して bn_n で割った余りを bn_encrypt に代入します。 これが秘密鍵による暗号化です。
153: BN_mod_exp(bn_decrypt, bn_encrypt, bn_d, bn_n, bn_ctx_tmp);bn_encrypt を bn_d 乗して bn_n で割った余りを bn_decrypt に代入します。 これが公開鍵による復号化です。
この段階で、bn_chunk の数 (平文) と bn_decrypt (平文を暗号化して復号化したもの) の数は一致するはずです。
157: BIGNUM *bn_tmp = BN_new();
158: char outbuf[sizeof(plain_buf)+1];
159: for ( i=0 ; i<KEYBIT_LEN/8 ; i++ ){
160: BN_rshift(bn_tmp, bn_decrypt, (KEYBIT_LEN/8-i-1)*8);
161: BN_mask_bits(bn_tmp, 8);
162: outbuf[i] = (char)BN_get_word(bn_tmp);
163: }
164: printf("復号した暗号文: [%.*s]\n", KEYBIT_LEN/8, outbuf);
最上位バイトから 1 バイトずつ取り出して、outbuf に格納します。
bn_decrypt が int として書くと以下のようになります。
for ( i=0 ; i<KEYBIT_LEN/8 ; i++ ){
outbuf[i] = (bn_decrypt >> (KEYBIT_LEN/8-i-1)) && 0xff;
}
実行結果の後半部分を再掲します。
平文: [abcdefghijklmnop] bn_chunk=129445976596022050476432668810952994672 (0x6162636465666768696A6B6C6D6E6F70) bn_encrypt=26437649953676003874386347523956214860 (0x13E3B4C797083D991B599C78D08B0C4C) bn_decrypt=129445976596022050476432668810952994672 (0x6162636465666768696A6B6C6D6E6F70) 復号した暗号文: [abcdefghijklmnop] 平文: [qrstuvwxyz1234] bn_chunk=150797027069492699164330601711972646912 (0x7172737475767778797A313233340000) bn_encrypt=25390034121517778044968204977444792045 (0x1319F154CFA3597BEDA48F1BBACCA6ED) bn_decrypt=150797027069492699164330601711972646912 (0x7172737475767778797A313233340000) 復号した暗号文: [qrstuvwxyz1234]この例では、鍵長 KEYBIT_LEN が 128、平文が 240 ビット (30 バイト) のため、
「ライブラリに頼らずに」と言いつつ、まだ以下の部分を OpenSSL のライブラリに頼っています。
1・2 はあまりおもしろそうではありません。1 は結局は実装するだけです (ま、言うのは簡単で、実際にやるのは難しいわけですが)。 2 は「ユークリッドの互除法」という有名で簡単なアルゴリズムがあります。
一方、おもしろそうなのは 3・4 です。3 は、大きな数を素直に e 乗していると時間がかかります。 そこを高速化する過程で、mod の考え方を理解できるでしょう。 4 は、結局は素数判定の方法に行きつくわけですが、 フェルマーテストやミラーテストなど非常におもしろいやり方がありますので、 挑戦してみるとおもしろいのではないでしょうか。
rsa-2.c のソース全文は以下の通りです。
1: /*
2: * $Id: rsa-2.c,v 1.4 2005/02/19 16:01:53 68user Exp $
3: *
4: * OpenSSL を使った RSA の実装 (2)
5: * 素数生成はライブラリまかせ。RSA 鍵生成・暗号化・復号化は自前で版。
6: *
7: * written by 68user http://X68000.q-e-d.net~68user/
8: */
9:
10: #include <stdio.h>
11: #include <string.h>
12: #include <openssl/bn.h>
13: #include <openssl/engine.h>
14:
15: #define BN_PUT(bn) { printf(#bn "=%s (0x%s)\n", BN_bn2dec(bn), BN_bn2hex(bn)); }
16: #define KEYBIT_LEN 128
17:
18: int
19: main(){
20: unsigned char plain_buf[]="abcdefghijklmnopqrstuvwxyz1234";
21:
22: ERR_load_crypto_strings();
23:
24: BIGNUM *bn_e = BN_new(); BN_set_word(bn_e, 65537);
25: BIGNUM *bn_n = BN_new();
26: BIGNUM *bn_d = BN_new();
27: BN_CTX *bn_ctx_tmp = BN_CTX_new();
28:
29: {
30: /* 素数生成 */
31: BIGNUM *bn_p = BN_new(); /* 素数 p */
32: BIGNUM *bn_q = BN_new(); /* 素数 q */
33:
34: BN_generate_prime(bn_p, KEYBIT_LEN/2, 1, NULL, NULL, NULL, NULL);
35: BN_generate_prime(bn_q, KEYBIT_LEN/2, 1, NULL, NULL, NULL, NULL);
36:
37: /* n = p*q
38: * pm = p-1
39: * qm = q-1
40: * pmqm = (p-1)*(q-1)
41: * gcd_pmqm = (p-1) と (q-1) の最大公約数
42: * L = (p-1) と (q-1) の最小公倍数 = (p-1)*(q-1)/gcd(p-1,q-1)
43: */
44: BIGNUM *bn_pm = BN_new(); /* p-1 (p minus 1) */
45: BIGNUM *bn_qm = BN_new(); /* q-1 (q minus 1) */
46: BIGNUM *bn_pmqm = BN_new(); /* (p-1)*(q-1) */
47: BIGNUM *bn_gcd_pmqm = BN_new(); /* (p-1) と (q-1) の最小公倍数 */
48: BIGNUM *bn_L = BN_new(); /* L。(p-1) と (q-1) の最小公倍数 */
49: BIGNUM *bn_one = BN_new(); /* 1 */
50: BN_one(bn_one);
51:
52: BN_mul(bn_n, bn_p, bn_q, bn_ctx_tmp);
53: BN_sub(bn_pm, bn_p, bn_one);
54: BN_sub(bn_qm, bn_q, bn_one);
55: BN_mul(bn_pmqm, bn_pm, bn_qm, bn_ctx_tmp);
56: BN_gcd(bn_gcd_pmqm, bn_pm, bn_qm, bn_ctx_tmp);
57: BN_div(bn_L, NULL, bn_pmqm, bn_gcd_pmqm, bn_ctx_tmp);
58:
59: BN_PUT(bn_p); BN_PUT(bn_q); BN_PUT(bn_n); BN_PUT(bn_pm);
60: BN_PUT(bn_qm); BN_PUT(bn_pmqm); BN_PUT(bn_gcd_pmqm); BN_PUT(bn_L);
61:
62: /* a*x + b*y = 1 を満たす x と y (y>0) を見付ける。この y が d となる
63: * ここでは a は L、b は e。e に大きい数を指定した場合は、逆にすべきかも。*/
64: {
65: /* (x1, y1, z1) ← (1, 0, a) ここでの a は L
66: * (x2, y2, z2) ← (0, 1, b) ここでの b は e
67: */
68: BIGNUM *bn_x1 = BN_new(); BN_one(bn_x1);
69: BIGNUM *bn_y1 = BN_new(); BN_zero(bn_y1);
70: BIGNUM *bn_z1 = BN_new(); BN_copy(bn_z1, bn_L);
71: BIGNUM *bn_x2 = BN_new(); BN_zero(bn_x2);
72: BIGNUM *bn_y2 = BN_new(); BN_one(bn_y2);
73: BIGNUM *bn_z2 = BN_new(); BN_copy(bn_z2, bn_e);
74: BIGNUM *bn_x3 = BN_new();
75: BIGNUM *bn_y3 = BN_new();
76: BIGNUM *bn_z3 = BN_new();
77: BIGNUM *bn_q = BN_new();
78: BIGNUM *bn_tmp = BN_new();
79: BIGNUM *bn_zero = BN_new(); BN_zero(bn_zero);
80:
81: /* z2 が 0 になったらループ終了 */
82: while ( ! BN_is_zero(bn_z2) ){
83: /* q ← z1 を z2 で割った商
84: * (x3, y3, z3) ← (x1, y1, z1) - q * (x2, y2, z2)
85: * (x1, y1, z1) ← (x2, y2, z2)
86: * (x2, y2, z2) ← (x3, y3, z3)
87: */
88: BN_div(bn_q, NULL, bn_z1, bn_z2, bn_ctx_tmp);
89: BN_mul(bn_tmp, bn_q, bn_x2, bn_ctx_tmp);
90: BN_sub(bn_x3, bn_x1, bn_tmp);
91: BN_mul(bn_tmp, bn_q, bn_y2, bn_ctx_tmp);
92: BN_sub(bn_y3, bn_y1, bn_tmp);
93: BN_mul(bn_tmp, bn_q, bn_z2, bn_ctx_tmp);
94: BN_sub(bn_z3, bn_z1, bn_tmp);
95:
96: BN_copy(bn_x1, bn_x2); BN_copy(bn_y1, bn_y2); BN_copy(bn_z1, bn_z2);
97: BN_copy(bn_x2, bn_x3); BN_copy(bn_y2, bn_y3); BN_copy(bn_z2, bn_z3);
98: }
99:
100: /* ここで y1 が求めたい d である。ただし d が負なら L を足して、次の候補に補正 */
101: BN_copy(bn_d, bn_y1);
102: if ( BN_cmp(bn_d, bn_zero) == -1 ){
103: BN_add(bn_d, bn_d, bn_L);
104: }
105:
106: BN_PUT(bn_e);
107: BN_PUT(bn_d);
108:
109: BN_free(bn_x1); BN_free(bn_y1); BN_free(bn_z1);
110: BN_free(bn_x2); BN_free(bn_y2); BN_free(bn_z2);
111: BN_free(bn_x3); BN_free(bn_y3); BN_free(bn_z3);
112: BN_free(bn_q); BN_free(bn_tmp); BN_free(bn_zero);
113:
114: }
115:
116: BN_free(bn_p); BN_free(bn_q); BN_free(bn_pm); BN_free(bn_qm);
117: BN_free(bn_pmqm); BN_free(bn_gcd_pmqm); BN_free(bn_L); BN_free(bn_one);
118: }
119:
120: char *p = plain_buf;
121: int finished = 0;
122:
123: while ( ! finished && *p != '\0' ){
124: int i;
125: BIGNUM *bn_chunk = BN_new();
126: BN_init(bn_chunk);
127:
128: /* 平文を鍵長のバイト数に区切る */
129: printf("平文: [");
130: for ( i=0 ; i<KEYBIT_LEN/8 ; i++ ){
131: char c;
132: if ( *p == '\0' ){
133: finished = 1;
134: c = '\0';
135: } else {
136: c = *p++;
137: }
138: printf("%c", c);
139: BN_lshift(bn_chunk, bn_chunk, 8);
140: BN_add_word(bn_chunk, c);
141: }
142: printf("]\n");
143: BN_PUT(bn_chunk);
144:
145: BIGNUM *bn_encrypt = BN_new();
146: BIGNUM *bn_decrypt = BN_new();
147:
148: /* 暗号化 */
149: BN_mod_exp(bn_encrypt, bn_chunk, bn_e, bn_n, bn_ctx_tmp);
150: BN_PUT(bn_encrypt);
151:
152: /* 復号化 */
153: BN_mod_exp(bn_decrypt, bn_encrypt, bn_d, bn_n, bn_ctx_tmp);
154: BN_PUT(bn_decrypt);
155:
156: /* bn_decrypt を文字列に戻す */
157: BIGNUM *bn_tmp = BN_new();
158: char outbuf[sizeof(plain_buf)+1];
159: for ( i=0 ; i<KEYBIT_LEN/8 ; i++ ){
160: BN_rshift(bn_tmp, bn_decrypt, (KEYBIT_LEN/8-i-1)*8);
161: BN_mask_bits(bn_tmp, 8);
162: outbuf[i] = (char)BN_get_word(bn_tmp);
163: }
164: printf("復号した暗号文: [%.*s]\n", KEYBIT_LEN/8, outbuf);
165:
166: BN_free(bn_tmp);
167: BN_free(bn_encrypt);
168: BN_free(bn_decrypt);
169: BN_free(bn_chunk);
170: }
171: BN_CTX_free(bn_ctx_tmp);
172: return 0;
173: }
| 前へ << RSA で暗号化してみよう (1) | inetdとは >> 次へ |
ご意見・ご指摘は Twitter: @68user までお願いします。