RSA で暗号化してみよう (1)

OpenSSL は SSL/TLS だけのライブラリではありません。 SSL/TLS を実装する上で必要な RSA や素数を扱うための機能もライブラリ化されています。
これを利用して、RSA による暗号化・復号化を行いましょう。
なお、本ページを書くにあたり、以下のページを参考にしました。特に「はやわかり RSA」から、拡張ユークリッドの互除法」の数式を拝借させていただきました。作者の方々に感謝します。

はやわかり RSA
RSA暗号体験入門

プログラム概要

このプログラム rsa-1.c は、

RSA 鍵を生成
平文を秘密鍵を用いて暗号化し、暗号文を生成
暗号文を公開鍵で復号化し、平文に戻す
もともとの平文と、復号化した平文を比較し、一致することを確認

という機能を持ちます。コンパイル方法と実行例を以下に示します。

% cc -o rsa-1 rsa-1.c -lcrypto
% ./rsa-1
rsa->p=63214320007386536329786129577 (0xCC41A8F235CA549FFF6B7CA9)
rsa->q=59932084650160127062787457443 (0xC1A6A892F6E56AF2C4C781A3)
rsa->n=3788565977785000843975931845359477952078396303107571091611
       (0x9A82797280EBDCD8B79EE9EB6FF85CBA5ACD2B5616A0889B)
rsa->e=65537 (0x010001)
rsa->d=178800289443963068349444698373681637489855927729961506961
       (0x074AC31A9155105E36044CFBD9CC720AF77B31FBCCE71891)
平文=[hogehoge]
暗号文=[0x4FDCED8636258972E843B19220CAB7791408FFA8DF8A2] (16進数)
復号化した暗号文=[hogehoge]

前半に表示されている数字は、RSA 鍵の内容です。最後の部分で「平文」と「復号化した暗号文」が一致しているので、正しくデータの暗号化・復号化ができたことがわかります。

ではソースを。

rsa-1.c

    1: /*
    2:  * $Id: rsa-1.c,v 1.3 2005/02/19 16:01:53 68user Exp $
    3:  *
    4:  * OpenSSL を使った RSA の実装 (1)
    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 <stdlib.h>
   13: #include <openssl/rsa.h>
   14: #include <openssl/engine.h>
   15: #include <openssl/err.h>
   16: 
   17: #define BN_PUT(bn) { printf(#bn "=%s (0x%s)\n", BN_bn2dec(bn), BN_bn2hex(bn)); }
   18: #define KEYBIT_LEN 192
   19: 
   20: int
   21: main(){
   22:     unsigned char plain_buf[]="hogehoge";
   23:     unsigned char *crypted_buf;
   24:     unsigned char *decrypted_buf;
   25:     int crypted_len;
   26:     int decrypted_len;
   27:     char errbuf[1024];
   28:     RSA *rsa;
   29: 
   30:     ERR_load_crypto_strings();
   31: 
   32:     /* RSA 鍵生成 */
   33:     rsa = RSA_generate_key(KEYBIT_LEN, 65537, NULL, NULL);
   34:     if ( rsa == NULL ){
   35:         printf("in generate_key: err=%s\n", ERR_error_string(ERR_get_error(), errbuf));
   36:         return 1;
   37:     }
   38:     BN_PUT(rsa->p);
   39:     BN_PUT(rsa->q);
   40:     BN_PUT(rsa->n);
   41:     BN_PUT(rsa->e);
   42:     BN_PUT(rsa->d);
   43: 
   44:     /* 暗号文・復号文の領域を確保 */
   45:     crypted_buf = malloc(RSA_size(rsa));
   46:     if ( crypted_buf == NULL ){
   47:         perror("malloc");
   48:         goto ERR;
   49:     }
   50:     decrypted_buf = malloc(RSA_size(rsa));
   51:     if ( decrypted_buf == NULL ){
   52:         perror("malloc");
   53:         goto ERR;
   54:     }
   55: 
   56:     /* 暗号化 */
   57:     crypted_len = RSA_private_encrypt(strlen(plain_buf), plain_buf, crypted_buf, rsa, RSA_PKCS1_PADDING);
   58:     if ( crypted_len == -1 ){
   59:         printf("in encrypt: err=%s\n", ERR_error_string(ERR_get_error(), errbuf));
   60:         goto ERR;
   61:     }
   62: 
   63:     /* 復号化 */
   64:     decrypted_len = RSA_public_decrypt(crypted_len, crypted_buf, decrypted_buf, rsa, RSA_PKCS1_PADDING);
   65:     if ( decrypted_len == -1 ){
   66:         printf("in decrypt: err=%s\n", ERR_error_string(ERR_get_error(), errbuf));
   67:         goto ERR;
   68:     }
   69: 
   70:     printf("平文=[%s]\n", plain_buf);
   71:     {
   72:         int i;
   73:         printf("暗号文=[0x");
   74:         for ( i=0 ; i<crypted_len ; i++ ){
   75:             printf("%X", crypted_buf[i]);
   76:         }
   77:         printf("] (16進数)\n");
   78:     }
   79:     printf("復号化した暗号文=[%.*s]\n", decrypted_len, decrypted_buf);
   80: 
   81:     /* 検証 */
   82:     if ( strncmp(plain_buf, decrypted_buf, decrypted_len) != 0 ){
   83:         printf("  一致せず!");
   84:         goto ERR;
   85:     }
   86: 
   87:     RSA_free(rsa);
   88:     return 0;
   89: 
   90:  ERR:
   91:     RSA_free(rsa);
   92:     return 1;
   93: }

ソース解説

   28:     RSA *rsa;
まず、RSA 構造体 (のアドレスを格納するポインタ) を宣言します。
   18: #define KEYBIT_LEN 192
   33:     rsa = RSA_generate_key(KEYBIT_LEN, 65537, NULL, NULL);
RSA 鍵を生成します。第一引数は鍵長 (ビット数) です。上記の例では 192 としています。第二引数は e です。13 や 65537 などの数を指定することが多いので、ここでも 65537 を使用しています。第三・第四引数は素数生成時の乱数生成に関わるものですが、NULL にしておけば OpenSSL が適切な処理をしてくれます。
RSA 構造体のメモリ確保は RSA_generate_key 内部で行われるので、使い終わったら RSA_free を読んでメモリを開放しましょう。
構造体 RSA は
typedef struct {
    BIGNUM *n;
    BIGNUM *e;
    BIGNUM *d;
    BIGNUM *p;
    BIGNUM *q;
} RSA;
と定義されています (説明する上で不要な部分は省略しています)。 RSA_generate_key はこれらの値を適切に決定してくれる関数なわけです。
BIGNUM とは、多倍長整数を扱うことができる構造体です。暗号技術では 1024bit や 2048bit といった、とても大きな数を扱う必要があります。しかし最近の C 言語処理系でも int が 32bit、long long int が 64bit で、長さが全く足りません。 OpenSSL では、より大きな数を管理するために多倍長整数ライブラリである bn を使用しています。 bn 単体でも使用できるようなつくりになっていますが、詳細は bn(3) をどうぞ。
   38:     BN_PUT(rsa->p);
   39:     BN_PUT(rsa->q);
   40:     BN_PUT(rsa->n);
   41:     BN_PUT(rsa->e);
   42:     BN_PUT(rsa->d);
生成した素数や数字類を表示するデバッグ文です。BN_PUT は
   17: #define BN_PUT(bn) { printf(#bn "=%s (0x%s)\n", BN_bn2dec(bn), BN_bn2hex(bn)); }
として定義したマクロです。要は BIGNUM を 16進数と 10進数で表示しているだけです。ちなみに #bn というのはマクロに渡した引数を文字列として表示するテクニックです。
それぞれの数の意味について復習しておきましょう。

p,q … n と d の元になる素数
n … RSA-modules (OpenSSL 的には public modulus と表記)
e … 暗号化指数 (encryption exponent または public exponent) ここではRSA_generate_key に渡した 65537 となる
d … 復号化指数 (decryption exponent または private exponent)
実行結果を再度以下に示します。なお、素数はランダムに生成されるため、実行結果は毎回変わります。
rsa->p=63214320007386536329786129577 (0xCC41A8F235CA549FFF6B7CA9)
rsa->q=59932084650160127062787457443 (0xC1A6A892F6E56AF2C4C781A3)
rsa->n=3788565977785000843975931845359477952078396303107571091611
       (0x9A82797280EBDCD8B79EE9EB6FF85CBA5ACD2B5616A0889B)
rsa->e=65537 (0x010001)
rsa->d=178800289443963068349444698373681637489855927729961506961
       (0x074AC31A9155105E36044CFBD9CC720AF77B31FBCCE71891)
そして RSA における「公開鍵」「秘密鍵」、「暗号化」「復号化」とは何か、も復習しましょう。

公開鍵 … e と n
秘密鍵 … d と n
暗号化 … 「暗号文 = (平文^e) % n」
復号化 … 「平文 = (暗号文^d) % n」

RSA 鍵ができたので、暗号化します。
   22:     unsigned char plain_buf[]="hogehoge";
   23:     unsigned char *crypted_buf;
plain_buf は平文です。 crypted_buf は暗号化したデータを格納する領域です。
   45:     crypted_buf = malloc(RSA_size(rsa));
暗号化したデータの長さは、RSA_size であらかじめ知ることができますので、長さ分の領域を malloc します。
   57:     crypted_len = RSA_private_encrypt(strlen(plain_buf), plain_buf, crypted_buf, rsa, RSA_PKCS1_PADDING);
RSA_private_encrypt で秘密鍵による暗号化を行います。

第一引数 … 平文の長さ
第二引数 … 平文
第三引数 … 暗号化したデータを格納する領域
第四引数 … RSA 構造体。この場合は秘密鍵による暗号化なので、rsa->d と rsa->n が使用される
第五引数 … パディング方式
パディング方式について説明しましょう。RSA では、平文のサイズが鍵の長さに満たない場合、パディングを行う必要があります。パディングについては送信側と受信側が合意していればどんなものでもよいのですが、既に PKCS#1 によってパディング方式が定められています。RSA_PKCS1_PADDING を指定することで、PKCS#1 方式のパディング方式が使用されます。
一方、RSA_NO_PADDING を指定するとパディングは自動的に行われなくなります。その場合、パディングを行うのはプログラム側の責任となります。
PKCS (Public-Key Cryptography Standard) は RSA 社が定めた暗号技術の標準です。RSA 社は一企業に過ぎませんので PKCS に従う義務はありません。しかし既にデファクトスタンダードになっていますので、PKCS に従った方が楽です。 PKCS は #1～#15 まで存在します (#14 は欠番。#2・#4 は #1 に統合)。例えば #1 は RSA、#5 は共通鍵暗号方式、#13 は楕円暗号方式について定めています。
なお、PKCS の一部は RFC にもなっています。基本的に PKCS の内容を変更せず、そのまま RFC として発行したものです。
RSA_private_encrypt の戻り値は暗号文の長さです。暗号文は ('\0' で終端された) 文字列ではなく、0 を含むかもしれないバイナリデータなので、
   printf("%s\n", crypted_buf);
などと普通の文字列のように扱ってはいけません。必ずデータの長さを意識した操作をしましょう。
   64:     decrypted_len = RSA_public_decrypt(crypted_len, crypted_buf, decrypted_buf, rsa, RSA_PKCS1_PADDING);
次に復号化です。さきほどは秘密鍵で暗号化したので、それを復号するには RSA_public_decrypt を使って公開鍵で復号化します。
「公開鍵で暗号化したら、秘密鍵で復号化」「秘密鍵で暗号化したら、公開鍵で復号化」というのは覚えていますか?
引数の渡し方は暗号化の場合と同じなので、説明は省略します。
   70:     printf("平文=[%s]\n", plain_buf);
   71:     {
   72:         int i;
   73:         printf("暗号文=[0x");
   74:         for ( i=0 ; i<crypted_len ; i++ ){
   75:             printf("%X", crypted_buf[i]);
   76:         }
   77:         printf("] (16進数)\n");
   78:     }
   79:     printf("復号化した暗号文=[%.*s]\n", decrypted_len, decrypted_buf);
ここでは、以下のような結果を表示します。
平文=[hogehoge]
暗号文=[0x4FDCED8636258972E843B19220CAB7791408FFA8DF8A2] (16進数)
復号化した暗号文=[hogehoge]
暗号文はバイナリデータなので、16進数で表示しています。暗号文と同様に復号文も '\0' 終端されていないので、
   79:     printf("復号化した暗号文=[%.*s]\n", decrypted_len, decrypted_buf);
と表示する文字列の長さを指定しています。

平文の長さ制限

このプログラムでは
#define KEYBIT_LEN 192
unsigned char plain_buf[]="hogehoge";
と、鍵長を 192 ビット、平文を 64 ビット (8 バイト) としています。平文の長さをひとつずつ増やしていくと、plain_buf[]="hogehogehogeho" と 14文字にしたときに
in encrypt: err=error:0406C06E:rsa routines:RSA_padding_add_PKCS1_type_1:data too large for key size
と「データが長すぎる」というエラーになります。
RSA では、平文を M としたとき、「M < n」でなければならないという制限がありますが、それならば平文が 192 ビット (24 バイト) になったときにエラーになるはずです。しかし 14 文字では 112 ビットにしかなりませんが、実際にはエラーになっています。
PKCS1 とか padding とか書いてあるので、そこらへん? たしかパディングのために 11 バイトくらい必要だったようなそうでないような…。原因は調査中です。

エラー処理

例えば秘密鍵で暗号化を行う関数 RSA_private_encrypt は、エラーが発生したら戻り値として -1 を返します。ここでエラーの原因を詳しく知りたい場合は、 ERR_get_error 関数を使います。
この関数はエラーの原因を表す unsigned long の値、例えば 67551342 を返します。こんな数を返されてもわけがわかりませんね。
そこでこの数を ERR_error_string に渡すことで、
error:0406C06E:lib(4):func(108):reason(110)
というような文字列を得ることができます。しかし。これでもさっぱりわかりません。
もっとわかりやすいエラーメッセージが欲しい場合は、あらかじめ ERR_load_crypto_strings 関数を実行しておく必要があります。これを事前に実行しておけば、ERR_error_string は
error:0406C06E:rsa routines:RSA_padding_add_PKCS1_type_1:data too large for key size
という文字列を返すようになります。 ERR_load_crypto_strings 関数で確保されたメモリを開放するには ERR_free_strings 関数を呼ぶ必要がありますが、めんどくさいのでこのプログラムでは呼んでいません。
なお、エラーメッセージは openssl コマンドの errstr を実行することでも参照できます。
% openssl errstr 0406C06E
error:0406C06E:rsa routines:RSA_padding_add_PKCS1_type_1:data too large for key size

ライブラリを使うだけじゃあ…

OpenSSL を使うと簡単に RSA が実現できて楽なのですが、実際には用意されたブラックボックスを組み合わせているだけで、全然おもしろくないですね。
もうちょっと深いところまで自分でやってみましょう。

前へ << SSL/TLS でアクセスしてみよう (2)

RSA で暗号化してみよう (2) >> 次へ

TOP >> ネットワークプログラミングの基礎知識 >> RSA で暗号化してみよう (1)

$Id: rsa-1.html,v 1.4 2005/02/27 12:07:35 68user Exp $

RSA で暗号化してみよう (1)

ライブラリで RSA を実現

プログラム概要

ソース解説

平文の長さ制限

エラー処理

ライブラリを使うだけじゃあ…