:$Id: rsa-2.html,v 1.5 2004/06/12 05:28:25 68user Exp $

:start RSA で暗号化してみよう (2)
:desc OpenSSL にそれほど頼らない RSA の実装

<!--=====================================-->
:term 自分で暗号化・復号化

前ページで作成した rsa-1.c では、素数生成・RSA 鍵生成・暗号化・復号化のすべてをライブラリにまかせました。
今回はなるべくライブラリに頼らず、自力で作ってみましょう。
:p
プログラムの目的は rsa-1.c と同様で、鍵を作成して暗号化・復号化するだけです。
コンパイル方法と実行結果は以下の通り。

:cmd
% cc -o rsa-2 rsa-2.c -lcrypto
% ./rsa-2
rsa-&gt;n=244572674926805241062968088611600028071 (0xB7FEFBDBC2E745B2C627DA1EA15D51A7)
rsa-&gt;e=65537 (0x010001)
rsa-&gt;d=541114757532184261555825717500966193 (0x6837047074F48984C2444C589FF531)
rsa-&gt;p=16764777456439012943 (0xE8A87445E5862E4F)
rsa-&gt;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]
:cmd

:hr

まずは RSA の鍵生成です。前ページの rsa-1.c では

:code
RSA *rsa = RSA_generate_key(KEYBIT_LEN, 65537, NULL, NULL);
:code

だけで済んでいましたが、今度は自分で計算しなくてはいけません。

:preinclude rsa-2.c 24-27

まずは e, n, d の領域を確保します。
<tt>BN_new</tt> を呼ぶと BIGNUM 用の領域が生成されます。
また、<tt>BN_set_word</tt> を使って、e に 65537 をセットします。
:p
さらに <tt>BN_CTX_new</tt> を使って BN_CTX 構造体を生成します。
BN_CTX は、BIGNUM 用の関数が一時的に使用する作業用領域です。
:p
例えば BIGNUM の乗算・除算のたびに作業用領域が必要になりますが、
毎回動的にメモリを確保していては時間がかかってしまいます。
よって、あらかじめ呼び出し側で作業用領域を確保しておき、
乗算や除算のたびにそれを使いまわすわけです。
:p
なお、<tt>BN_new</tt> したら、最後に <tt>BN_free</tt> を、
<tt>BN_CTX_new</tt> なら <tt>BN_CTX_free</tt>
を呼ばないとメモリリークしますのでご注意を。

:hr
:preinclude 31-35

<tt>BN_generate_prime</tt> を呼び、素数 p と q を生成します。
素数のビット数は鍵長の 1/2 を指定しています。なぜ 1/2 かと言うと、
:code
n = p * q
M &lt; n (M は平文のメッセージ)
:code
という条件があるので、鍵長/2 のビット数同士をかけたら n は狙いの鍵長になるのかなと思ったからですが、
いまいち自信がありません。
:p
第三引数に真となる値を渡すと、safe prime (strong prime)
と呼ばれる素数を生成します。素数 p があるとき、(p-1)/2 も素数であるものを
safe prime というようです。よくわかりませんが、格の高い素数みたいなもんですかね。
なんとなく 1 を指定して、格の高い素数を得てみることにしました。
:p
その他の引数はいろいろ便利なことができるようなので、調べてみてください。

:hr
:preinclude 44-57

なにをしているかと言うと、
:code
n = p * q
L = lcm(p-1, q-1)
   注: lcm(a,b) … a と b の最小公倍数
:code

これだけです。ただし、OpenSSL のライブラリには最大公約数を求める関数はありますが、
最小公倍数を求める関数はないので、

:code
 lcm(a,b) = a*b/gcd(a,b)
   注: gcd(a,b) … a と b の最大公約数
:code

という公式を使っています。
:p
このプログラムで使用している BN のライブラリ関数を、以下に軽く紹介しておきます
(他にも数十個の関数があります)。

:ul
:li <tt>BN_new()</tt> … 新たな BIGNUM の領域を確保し、戻り値で返す
:li <tt>BN_free(a)</tt> … a の領域を開放
:li <tt>BN_add(r, a, b)</tt> … a + b の結果を r にセット
:li <tt>BN_sub(r, a, b)</tt> … a - b の結果を r にセット
:li <tt>BN_mul(r, a, b, ctx)</tt> … a * b の結果を r にセット
:li <tt>BN_div(dv, rem, a, b, ctx)</tt> … a / b の結果を dv に、余りを rem にセット<br>
    (余りが不要であれば rem に NULL をセットすればよい)
:li <tt>BN_gcd(r, a, b, ctx)</tt> … a と b の最小公倍数を r にセット
:li <tt>BN_one(r)</tt> … r に 1 をセット
:li <tt>BN_zero(r)</tt> … r に 0 をセット
:li <tt>BN_is_zero(a)</tt> … a が 0 なら 1 を、0 以外なら 0 を返す。
:li <tt>BN_cmp(a, b)</tt> … a&lt;b なら -1 を、a==b なら 0 を、a&gt;b なら 1 を返す
:li <tt>BN_copy(to, from)</tt> … from の値を to にコピー
:li <tt>BN_CTX_new()</tt> … 新たな一時作業用の領域確保し、戻り値で返す
:li <tt>BN_CTX_free(c)</tt> … 一時作業用領域 c の領域を開放
:/ul

:hr

次に d を求めます。d は「(e * d) % L = 1」となる数です。d はたくさんの数が見付かりますが、
d は 1&lt;d&lt;L を満たす必要があります。
:p
文章で書くと簡単ですが、プログラムで実現するのはちょっと面倒です。
詳しい説明は省略しますが、「(e * d) % L = 1」というのは、「L*x + e*d = 1」
となる x と d を求めることと等価です。
:p
x と d を求めるには、「拡張ユークリッドの互除法」を用います。
これまた詳しい説明はしませんが、まず

:code
(x1, y1, z1) ← (1, 0, L)
(x2, y2, z2) ← (0, 1, e)
:code

と初期化します。そして z2 がゼロになるまで以下の計算を繰り返します。
:code
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)
:code

z2 がゼロになったとき、y1 に求める d が入っています。
ただし y1 が負になる場合があります。d は 1&lt;d&lt;L を満たす必要がありますので、
その場合は y1 に L を足したものを d とします。

:p
これをコード化したものが以下のソースです。

:preinclude 68-78
:preinclude 82
:preinclude 88-98
:preinclude 101-104

:p

これでやっと公開鍵 (d と n)・秘密鍵 (e と n) が手に入りました。

:hr
次に暗号化・復号化です。平文は

:preinclude 20

で、30文字あります (240 ビット)。

一方、鍵の長さは

:preinclude 16

です (ビット数であることに注意)。平文が鍵の長さを上回っているので、
これでは暗号化することはできません。そこで、平文を一定の長さで切り出し、
切り出したそれぞれの部分ごとに RSA で暗号化することにしましょう。

:hr

:preinclude 120-143

かなり見づらいソースで恐縮です。
まず <tt>bn_chunk</tt> という数を作ります。ここに切り出した平文を格納します。
:p
BIGNUM だと見づらいので、int に置き換えてみたのが以下のコードです。

:code
int bn_chunk = 0;
for ( i=0 ; i&lt;strlen(plain_str) ; i++ ){
   bn_chunk <<= 8;
   bn_chunk += plain_str[i];
}
:code

例えば plain_str が "abcd" で KEYBIT_LEN が 32 であれば、
(a〜d の文字コードは 0x61〜0x64 ですから) bn_chunk は 0x61626364 になります。

:code
if ( *p == '\0' ){
   c = '\0';
}
:code
は文字列が鍵長の長さに満たない場合に 0 をパディングしています。
:tips
この対応では、本来のデータ長が保存されませんので、パディング方法としては不十分です。
ゼロ終端された文字列しか暗号化しないのであればこれでもよいですが、
バイナリデータを扱うと末尾にゴミが付くことがあるでしょう。
また、0 でパディングするのはセキュリティ的によくないため
(特にデータ長が短い場合)、ランダムなデータでパディングすべきです。
:p
PKCS#1 であれば、こういうところもちゃんと考えられて作られています。
:tips

:hr

前のプログラム rsa-1.c では

:code
暗号化: 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)
:code

としていました。ここを自分で処理するよう変更します。

:p

といっても、非常に簡単です。RSA における暗号化・復号化とは、以下の計算にすぎないことを思い出してください。

:ul
:li 暗号化 … 「暗号文 = (平文^e) % n」
:li 復号化 … 「平文 = (暗号文^d) % n」
:/ul

ありがたいことに、OpenSSL には「a を p 乗して n で割った余りを求める」
というまさにこの目的の関数が用意されています。これを使うと、
以下のように簡単に実現できます。

:preinclude 149

bn_chunk を bn_e 乗して bn_n で割った余りを bn_encrypt に代入します。
これが秘密鍵による暗号化です。

:preinclude 153

bn_encrypt を bn_d 乗して bn_n で割った余りを bn_decrypt に代入します。
これが公開鍵による復号化です。
:p
この段階で、bn_chunk の数 (平文) と bn_decrypt (平文を暗号化して復号化したもの) の数は一致するはずです。
:hr

最後に、数である bn_decrypt から文字列に変換し、復号化した文字列を表示します
(bn_chunk 生成と逆のことを行います)。


:preinclude 157-164

最上位バイトから 1 バイトずつ取り出して、<tt>outbuf</tt> に格納します。
<tt>bn_decrypt</tt> が int として書くと以下のようになります。

:code
for ( i=0 ; i&lt;KEYBIT_LEN/8 ; i++ ){
    outbuf[i] = (bn_decrypt &gt;&gt; (KEYBIT_LEN/8-i-1)) &amp;&amp; 0xff;
}
:code

実行結果の後半部分を再掲します。

:cmd
平文: [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]
:cmd

この例では、鍵長 KEYBIT_LEN が 128、平文が 240 ビット (30 バイト) のため、
:ul
:li 1 回目の while ループ … 前半 128 ビット (16 バイト) を処理
:li 2 回目の while ループ … 後半 112 ビット (14 バイト) を処理
:/ul
となっています。ただし、2 回目のループでもパディングが 2 つ (16 ビット) が付加され、
暗号化・復号化はいずれも 128 ビット行われています。

<!--=====================================-->
:term まとめ

rsa-2.c は、rsa-1.c と比べると鍵長より長い文字列を暗号化できるようになりました。
しかし、パディング方法が退化してしまいました。
:p
「ライブラリに頼らずに」と言いつつ、まだ以下の部分を OpenSSL のライブラリに頼っています。

:ol
:li 多倍長整数ライブラリ
:li 最大公約数を求める方法
:li 数を e 乗して m で割った余りを求める方法
:li 素数生成
:/ol

:p
1・2 はあまりおもしろそうではありません。1 は結局は実装するだけです
(ま、言うのは簡単で、実際にやるのは難しいわけですが)。
2 は「ユークリッドの互除法」という有名で簡単なアルゴリズムがあります。
:p
一方、おもしろそうなのは 3・4 です。3 は、大きな数を素直に e 乗していると時間がかかります。
そこを高速化する過程で、mod の考え方を理解できるでしょう。
4 は、結局は素数判定の方法に行きつくわけですが、
フェルマーテストやミラーテストなど非常におもしろいやり方がありますので、
挑戦してみるとおもしろいのではないでしょうか。

:p
rsa-2.c のソース全文は以下の通りです。
:p

:preinclude rsa-2.c