前へ << 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 までお願いします。