はじめに
背景
こちらは Cyber Security Advent Calendar 2022 に相乗りし、その17日目ということで、RSA暗号絡みの小ネタを記事にしたものです。
この話の本編は、Togetterまとめ「RSA暗号で実はpが素数でなかったら?」の「暗号化・復号処理の破綻」の話題に関連するものなので、そちらを一通り読んでおくことをお勧めします。
また、RSAの数学的な面が強いので、公開鍵暗号RSAの数的構造程度の予備知識は必要になります。予めご注意ください。
あらすじ
上で挙げたTogetterまとめのあらすじですが、以下のような感じになっています。
- RSAでは2つ(以上)の巨大な素数を鍵データの一部に使う
- しかし巨大であるがゆえに、ほんの僅かに素数でない数を使ってしまう可能性がある
- もし仮に、( 現実的ではないけど ) 非素数が紛れた場合、暗号化・復号処理の破綻する様子が見られるのではないか?
- 実際に OpenSSL で試してみたら、色々あったけど破綻する状況を作り出すことができた
その上で、この記事では、このまとめで触れているけど詳しくは言及していない部分、作ったツールやそれで実際に行っている計算、そう言った部分を補足していきます。
話題
ミラー・ラビンテスト
まずは、まとめ中 ( フェルマーテストと対照的に ) 詳細に触れなかった、ミラー・ラビンテストについてです。
以前RSAなら、自分の好きな文字列を含む公開鍵が作れる件で触れた「ミラー・ラビン素数判定法」にはこのテストが組み込まれています。
※アルゴリズム自体は、FIPS186-4のAppendix C、C.3.1 にも載っています。
ミラー・ラビンテストの概要
フェルマーテストが、「フェルマーの小定理 $a^{p-1}\equiv 1~ ~mod~p$ が成立すること」を見るテストであったのに対し、ミラー・ラビンテストは ( 暗黙の内にフェルマーテストを含んだ上で ) 「$x^2\equiv 1~~mod~p$ の解が $x\equiv \pm 1~ ~mod~p$ のみであること」を見るテストと言えます。
以下、$p=4633=41\times 113$ という合成数に対して、底として $a=723,1016,1567$ の3つを例にとり、実際のテストのやり方をなぞってみます。この $p$ は合成数なのでテストに失敗する底は必ず出てきます。実際、この選ばれた3つの候補の内2つは失敗します。
- $p-1$をできるかぎり2で割る
今回、$p-1=4632=2^3\times 579$ なので、2で3回割って579が得られます。 - 1.で得られた579を使い $mod(a^{579},p)$ を計算し、結果が 1 なら成功と判定しテストを終わる
今回の$a$では該当なしです - 1.の579から始めて指数を倍々にしていって、$p-1$乗の手前まで同じようにべき剰余を計算して値を見る。今回、$mod(a^{579},p),~mod(a^{1158},p),~mod(a^{2316},p)$ という順になる
3-1. 途中で値が$p-1$となったなら成功と判定し、テストを終わる
$a=1567$ の場合、$mod(1567^{1158},p)=4632=p-1$ なので、このケースに該当します
3-2. 途中で値が1となったなら失敗と判定し、テストを終わる
$a=1016$ の場合、$mod(1016^{1158},p)=3730,~mod(1016^{2316},p)=1$ で、このケースに該当します
※$a=1567$ の場合でも $mod(1567^{2316},p)=1$ ですが、先に 3-1. でテストを終えているため、こちらには該当しません - ここまで成功とも失敗とも判定できなかった場合、失敗と判定する
$a=723$ の場合、 $mod(723^{579},p)=4111,~mod(723^{1158},p)=3770,~mod(723^{2316},p)=3489$ で、3-1,3-2ともに該当しないため、ここで失敗という判定になります
なお、手順 3 で順々にべき剰余を計算していくのですが、手順 2 からの計算結果を二乗+余り計算していけば済みますので、実際は次のように二乗を繰り返す方で実装します。
$mod(a^{1158},p)=mod(~(mod(a^{579},p)^2,~p~),~ ~mod(a^{2316},p)=mod(~(mod(a^{1158},p)^2,~p~)$
また、手順 3. の初回は 2. で兼ねるのが現実的ですが、同じ値になるケース同士をまとめているので、内容的には同等ながら、実際の手順と少し変えていることになります。
さて、以上の手順を振り返って、テストをパスするのは手順 2 のところと、手順 3-1 のところですが、ここから更に指数を倍々にしていくと、結局 $mod(a^{p-1},p)=1$ という、フェルマーテストをパスする条件を満たすことが分かります。
そして、手順 3-2 のところは、同じようにフェルマーテストをパスできる条件でありながら、こちらは失敗扱いとなります。
つまり、ミラー・ラビンテストは、フェルマーテストより少し手順を積むことで、より厳しい内容のテストを課しているものとなっています。
チェックの厳しさ
フェルマーテストと比較した場合、ミラー・ラビンテストの方が厳しいチェックとなるわけですが、実際次のような特徴があります。
- フェルマーテストにおけるカーマイケル数のような、「合成数でありながら全ての底でテストをパスする数」が存在しない
- 合成数に対しては、テストをパスできる底が、全候補の高々1/4しかない。
※実際は、大抵の合成数で、テストをパスできる底の割合はもっと低い
なので、ランダムな底をある程度試す「ミラー・ラビン素数判定法」で、非常に精度高く素数判定が可能になっています。
テストをパスする様子
なぜこのような特徴があるのか。それは、素数の場合にどのようにテストをパスするかを見ることで、ある程度実感できるのではないかと思います。
例えば $p=337~ ~(~p-1=21\times 2^4~)$ の場合。
詳細は割愛しますが、$1\sim 336$ の数値は、原始元と呼ばれる数値 $g$ ( 例えば $g=10,19$ 等、複数候補あります ) に対して、$g^0\sim g^{335}$ と$mod~p$ 上で1対1に対応します。
中でも、$g$ に関わらず $g^0\equiv g^{336}\equiv g^{336\times 2}\equiv \cdots\equiv g^{336k}\equiv 1,~ ~g^{168}\equiv -1$ と、指数が $p-1$ 周期で 1 に、その半周期で -1 に対応することは変わりません。これは $x^2\equiv 1$ の解が $x\equiv 1,-1$ であることに対応しています。
そこで、ミラー・ラビンテストとして、21乗→42乗→84乗→168乗 の推移を見てみると、$g$ の指数の2べき成分で分かれることが分かります。
- $a\equiv g^{16k}$
$a^{21}\equiv g^{336k}\equiv 1$ のため、最初の21乗でパスとなります。 - $a\equiv g^{16k+8}$
$a^{21}\equiv g^{336k+168}\equiv g^{168}\equiv -1$ のため、こちらも最初の21乗でパスとなります。 - $a\equiv g^{8k+4}$
$a^{21}\equiv g^{168k+84}$ → $a^{42}\equiv g^{168}\equiv -1$ のため、42乗の時点でパスとなります。 - $a\equiv g^{4k+2}$
$a^{21}\equiv g^{84k+42}$ → $a^{42}\equiv g^{168k+84}$ → $a^{84}\equiv g^{168}\equiv -1$ のため、84乗の時点でパスとなります。 - $a\equiv g^{2k+1}$
$a^{21}\equiv g^{42k+21}$ → $a^{42}\equiv g^{84k+42}$ → $a^{84}\equiv g^{168k+84}$ → $a^{168}\equiv g^{168}\equiv -1$ のため、最後の168乗まで行ってパスとなります。
いずれにせよ最初の段階でパスするか、そうでなければ指数を倍々にしていくことで半周期の168乗に辿り着くので、$p$ が素数であれば全ての底でテストにパスするということです。
また、指数の2べき部分だけで「いつパスするのか」が決まるので、それぞれ何個の底が該当するのかを見積もることができます。具体的には、半数の底が最後でパス、1/4の底が最後の手前でパス、…というように、パスする手順が1手早くなる毎に、該当する底の数は半減していきます。
ところが、$p$ が合成数となると状況が大きく変わります。先程取り上げた $p=4633=41\times 113$ で 579乗→1158乗→2316乗と試す状況を観察してみます。
まず、$x\equiv 1,-1~~mod~p$ という条件ですが、$p$ が合成数であるために $x\equiv 1,-1~ ~mod~41~\land~x\equiv 1,-1~ ~mod 113$ と、複数の法での条件の複合になります。このことは、あたかも複数のミラー・ラビンテストを同時進行で行う ( 全てパスした時のみトータルでパスとする ) ような話になっています。
そして、フェルマーの小定理に対応するべき乗の値の繰り返しは $mod~41$の場合で40周期、$mod~113$の場合で112周期なので、例えば最初の579乗の部分は、以下のような複合条件に置き換わります。
$$
\begin{matrix}
~&a^{579}\equiv 1~ ~mod~p \\
\Leftrightarrow & a^{579}\equiv 1~ ~mod~41~\land~a^{579}\equiv 1~ ~mod~113 \\
\Leftrightarrow & a^{19}\equiv 1~ ~mod~41~\land~a^{19}\equiv 1~ ~mod~113
\end{matrix}
$$
ということは、$mod~p$ で 579乗→1158乗→2316乗を見るというのは、$mod~41,~ ~mod 113$ の両方で 19乗→38乗→76乗を見ていることに他ならず、しかも 41 に対するテストを行った場合の 5乗→10乗→20乗、113 に対するテストを行った場合の 7乗→14乗→28乗→56乗という、「確実にパスできる指数の推移」とズレているため、テストにパスするのが困難になってしまっています。
$a=1567$ では、それでもテストにパスしていたのですが、これは $mod~41,~mod~113$ に対するそれぞれの原始元 $g_{41}=7,~g_{113}=3$ に対し $a\equiv {g_{41}}^{10}~ ~mod~41,~a\equiv {g_{113}}^{28}~ ~mod~113$ という特殊な指数状況になっていたためです。
これにより、$a^{1158}\equiv {g_{41}}^{20}\equiv -1~ ~mod~41,~a^{1158}\equiv {g_{113}}^{56}\equiv -1~ ~mod~113$ と、丁度$mod~41,~mod~113$ 両方で -1 がタイミング良く揃っています。
タイミングが揃う時
ということで、「指数の推移のズレ」が「テストをパスするのが困難」という性質に結びついており、特に $p$ を素因数分解した時の素因数が増える程、困難さを増していきます。
ただ、それだけであればフェルマーテストでもそれほど違いはありません。ミラー・ラビンテストがより厳しくなっているのには「-1になるタイミングを揃える必要がある」という点が一役買っています。
ここで、「指数の推移のズレ」が最も小さい例として、$p=r(2r-1)$ の形の2素数の積として、$p=337\times 673=226801$ を取り上げてみます。
$p-1=14175\times 2^4$ であるため、ミラー・ラビンテストは、14175乗→28350乗→56700乗→113400乗で推移します。
これを $mod~337,~mod~673$ で見てみると、共に 63乗→126乗→252乗→504乗の推移であり、337に対するテストでの 21乗→42乗→84乗→168乗と、673に対するテストでの 21乗→42乗→84乗→168乗→336乗に対して指数が3倍されているだけの違いしかありません。つまり、「どこかで -1 に辿り着く」こと自体にハードルがないことになります。
しかし、$a\equiv {g_{337}}^2~ ~mod~337,~a\equiv {g_{673}}^2~ ~mod~673$ のような底 $a$ だと、以下のように -1 が出るタイミングが 126乗と252乗とずれてしまいます。
※このずれは、$mod~p$ で見た場合、-1 を経由しないでいきなり 1 が現れるように観測されます。
- $mod~337$ での状況
$a^{63}\equiv {g_{337}}^{252},~a^{126}\equiv {g_{337}}^{504}\equiv {g_{337}}^{168}\equiv -1$ - $mod~673$ での状況
$a^{63}\equiv {g_{673}}^{252},~a^{126}\equiv {g_{673}}^{504},~a^{252}\equiv {g_{673}}^{1008}\equiv {g_{673}}^{336}\equiv -1$
この「-1 が出るタイミング」を考えると、揃う底の割合は以下の表のようにまとめられ、全体の 43/256 ( 約1/6 ) に過ぎないことが分かります。
※337や673の倍数はそもそも 1,-1 になるタイミングがないので除いて考えています。
| 法 | - | - | - | - | - | 計 |
|---|---|---|---|---|---|---|
| $mod~337$ | 32乗 1:1/16, -1:1/16 |
42乗 -1:1/8 |
84乗 -1:1/4 |
168乗 -1:1/2 |
- | - |
| $mod~673$ | 32乗 1:1/32, -1:1/32 |
42乗 -1:1/16 |
84乗 -1:1/8 |
168乗 -1:1/4 |
336乗 -1:1/2 |
- |
| $mod~p$ | 14175乗 1:1/512, -1:1/512 |
28350乗 -1:1/128 |
56700乗 -1:1/32 |
113400乗 -1:1/8 |
- | 43/256 |
この割合が最も高くなるケースは、$p=r(2r-1)$ の $r$ に関して「$r-1$ が4の倍数でない偶数」のケース ( 例えば $p=31\times 61=1891$ )で、以下の表のように、タイミングが揃う底の割合が全体の 1/4 になります。
ミラー・ラビンテストの「合成数でテストをパスする底は高々1/4」というのは、おそらくここから来ているものと思われます。
| 法 | - | - | 計 |
|---|---|---|---|
| $mod~r$ | $\frac{r-1}{2}$乗 1:1/2, -1:1/2 |
- | - |
| $mod~2r-1$ | $\frac{r-1}{2}$乗 1:1/4, -1:1/4 |
$r-1$乗 -1:1/2 |
- |
| $mod~p$ | $\frac{p-1}{2}$乗 1:1/8, -1:1/8 |
- | 1/4 |
処理が破綻する鍵の作成
作成方針
さて、ミラー・ラビンテストにそこそこ通る合成数として、$p=r(2r-1)$ 型の数を見つけたため、それによって鍵を作って破綻を試そうとしました。
方法としては簡単で、通常であれば「素数 p,q をランダムに見つける」「e から d を逆計算する」「関連パラメータを求める」という手順であるところ、一方の素数 $p$ に対し「$r-1$が4の倍数でない偶数となる素数$r$を見つける」「$2r-1$も素数となることを確認する」「$p=r(2r-1)$とする」というだけです。
この形の $p$ は、前述の通り 1/4 の底でミラー・ラビンテストを通る上、半分の底でフェルマーテストに失敗するものです。
※フェルマーテストに全部パスするカーマイケル数は、少なくとも3つの素因数を掛け合わせる必要があるため、2つの素数の積であるこの $p$ では、必ずフェルマーテストで失敗する底が出てくることになる。
破綻条件の見落とし
しかし、ここで破綻条件に見落としがあったため、「非素数 $p$ を入れて鍵を作ったものの、処理が破綻しない」という問題が発生することになりました。
なぜなら、「$p$ を非素数とする」というのは、$a^{p-1}\not\equiv 1~ ~mod~p$ となる $a$ が ( 確率的に ) 出てくることを目的としたものです。
しかし、RSA に求められるのは、$a^{ed_p-1}\equiv 1~ ~mod~p$ ( 効率的な秘密鍵処理の場合 ) あるいは、$a^{ed-1}\equiv 1~ ~mod~p$ ( ナイーブな秘密鍵処理の場合 ) であって、いずれも $a^{k(p-1)}\equiv 1~ ~mod~p$ と、フェルマーテストの形の指数に更に何倍かのゲタが履かされています。このため、「フェルマーテストに通らなくてもRSAで破綻しない」というケースがあり得るのでした。
実際、$p=r(2r-1)$ 型の $p$ の場合、$a^{p-1}\not\equiv 1~ ~mod~p$ となる $a$ はありますが、$a^{2(p-1)}\equiv 1~ ~mod~p$ は成立してしまいます。これは、ミラー・ラビンテストを考えた時の指数の遷移がほぼぴったり当てはまっている形での副作用と言えます。
そして、一般的に、秘密鍵のパラメータ d は $ed\equiv 1~ ~mod~(p-1)(q-1)$ を解いて計算しますので、$a^{ed-1}~mod~p$ の計算において指数部分は $ed-1=t(p-1)(q-1)=2(p-1)\cdot\frac{t(q-1)/2}$ と $2(p-1)$ の倍数となり、絶対破綻が起こらない形となってしまいました。
結局、$p=r(3r-2)$ 型に変更することで回避したわけですが、このような見落としに気を付ける必要があったということです。
ツール群
これまでの章で説明してきた内容について、実際に計算を行うためのツールを作成して試していましたので、それらを紹介します。
なお、ファイルはgithub上のリポジトリにも保存しています。
破綻用の鍵の作成
ファイル名: rsa-genbkey.rb
非素数を仕込んだRSA秘密鍵を作成するRubyスクリプトです。
基本的な所はRSAなら、自分の好きな文字列を含む公開鍵が作れる件の時に実装した内容と大差ありませんが、今回は真面目にASN.1処理をライブラリに頼るようにして、鍵のbit長を可変にできるようにしました。
以下の作成例のように、引数としてビット長と、それから $p=r(3r-2)$ 型なら 3、$p=r(2r-1)$ 型なら 2 を引数として指定することで、「ミラー・ラビンテストをそれなりに通す」非素数を1つ使って鍵を作ります。
※後者は2,3以外も指定可能で、その場合 $k$ の指定に対し $p=r(kr-k+1)$ 型で作ろうとします。また、省略した場合は 2 の指定になります。
その上で、その非素数がどのような素数の積になっているかも最初に出力します。
$ ruby rsa-genbkey.rb 512 3
testing pprime 195881276460665973395367634824264903451 * 587643829381997920186102904472794710351
-----BEGIN RSA PRIVATE KEY-----
MIIBPAIBAAJBAMFMc8W0Ydkyn0wVsN3cr71D0/oOFqS6dKgQvvonFL5EU3t/rovV
wq8WC2+gAMT2V+ATVa19+S6RHyDHu1rc6TECAwEAAQJBAKAbv1lnTBUoBSJ0ZQeg
IEDYyeA5gy/28WG0XTu+20OsyM4XfmB4AxzOcauk+I2POZ0wJetybmfbsGLxxK0z
WUECIQD+fQ8Q2Ercs0vfIhfAKlPFX1BLz7+495gF+JLou03oVQIhAMJyWzQVVwGT
zi3qULdvCr3oEgGkvDlDF7GyIMDlbgltAiEAqR8xAO/MqGjbFhlREVrPuw4BjbAt
aF3agLVV5CZ9utUCIGfGophkf0APQ23L7XJI6EG8dse7xN0GysGCoOpySEztAiEA
143sE257cnTRXSxddJqGjBpjK5/i9VozIx9NR6NDFIw=
-----END RSA PRIVATE KEY-----
各種チェック
ファイル名: rsatest.py
各チェック用の関数を実装したPythonスクリプトです。
このファイルを直接 python rsatest.py のように実行しても、単にデモが出力されるだけで、from rsatest import * のように import してライブラリとして使うことを想定しています。
実装されているのは、以下の3種類です。
- checkfermat
底 ( 複数 ) とテスト対象の数を指定して、フェルマーテストを行い、結果を出力します。
以下は、底 2～9 に対して、1891 のフェルマーテストを行う実行例です。checkfermat実行例$ python -q >>> from rsatest import * >>> checkfermat(range(2,10),1891) a=2 -> a^p=1645 mod p ( p=1891 ) NG a=3 -> a^p=3 mod p ( p=1891 ) OK a=4 -> a^p=4 mod p ( p=1891 ) OK a=5 -> a^p=5 mod p ( p=1891 ) OK a=6 -> a^p=1153 mod p ( p=1891 ) NG a=7 -> a^p=1030 mod p ( p=1891 ) NG a=8 -> a^p=907 mod p ( p=1891 ) NG a=9 -> a^p=9 mod p ( p=1891 ) OK 4 / 8 OK - checkmillerrabin
底 ( 複数 ) とテスト対象の数を指定して、ミラー・ラビンテストを行い、結果を出力します。
結果がOKの場合は、何乗のところでテストを終了したのかの情報も出します。
以下は、底 2～9 に対して、1891 のミラー・ラビンテストを行う実行例です。checkmillerrabin実行例$ python -q >>> from rsatest import * >>> checkmillerrabin(range(2,10),1891) a=2: NG a=3: OK ... a^b=-1 mod p ( p=1891, b=945 ) a=4: NG a=5: NG a=6: NG a=7: NG a=8: NG a=9: OK ... a^b=1 mod p ( p=1891, b=945 ) 2 / 8 OK - checkrsa
メッセージに相当する数値 ( 複数 ) と、秘密鍵のパラメータp,qを指定して、暗号化→復号で破綻が発生しないか ( 元に戻るか ) をテストします。
秘密鍵による復号方法としては、ファイル内に実装している関数rsadec_e,rsadec_nの2種類からどちらかを指定します。前者が効率的な実装、後者がナイーブな実装です。
p,q 以外の鍵のパラメータは自動計算されるのですが、e に関してはデフォルトで 11 を使います。変更する場合はモジュール変数の e を直接書き換えます。
以下は、2～9 のメッセージに対して、p=1891, q=911 での破綻を見る実行例です。途中で e の値を17に書き換えて2回試しています。checkrsa実行例$ python -q >>> from rsatest import * >>> import rsatest >>> checkrsa(range(2,10),rsadec_e,1891,911) m=2 -> c=2048 -> m(decoded)=2 OK m=3 -> c=177147 -> m(decoded)=3 OK m=4 -> c=748902 -> m(decoded)=4 OK m=5 -> c=592497 -> m(decoded)=5 OK m=6 -> c=1029846 -> m(decoded)=6 OK m=7 -> c=1388696 -> m(decoded)=7 OK m=8 -> c=547406 -> m(decoded)=8 OK m=9 -> c=338193 -> m(decoded)=9 OK 8 / 8 OK >>> rsatest.e = 17 >>> checkrsa(range(2,10),rsadec_e,1891,911) m=2 -> c=131072 -> m(decoded)=56484 NG m=3 -> c=1660289 -> m(decoded)=3 OK m=4 -> c=1094812 -> m(decoded)=4 OK m=5 -> c=1693152 -> m(decoded)=5 OK m=6 -> c=641385 -> m(decoded)=169452 NG m=7 -> c=1178266 -> m(decoded)=197694 NG m=8 -> c=1650566 -> m(decoded)=225936 NG m=9 -> c=230783 -> m(decoded)=9 OK 4 / 8 OK
なお、出力例を見て頂ければ分かる通り、各関数共通で、底あるいはメッセージの候補数とOKになった数の統計を最後に出力します。
もし全ケース出力する必要がなければ、OKのみ、NGのみ、OKもNGも出力しない ( 統計のみ ) を、最後のパラメータ outmode ( 省略可 ) で指定できます。それぞれ OutMode.OKONLY, OutMode.NGONLY, OutMode.NOOUT です。( 省略時は OutMode.ALL )
以下は、OutMode.NOOUTを指定して、統計のみを出力した例です。
$ python -q
>>> from rsatest import *
>>> checkmillerrabin(range(2,1890),1891,OutMode.NOOUT)
448 / 1888 OK
OpenSSLでの破綻チェック
一旦、破綻を起こせるものと見込んだ鍵で暗号化→復号を試しても、破綻が見られなかったというところで、まとめでは次のように説明していました。
「効率の良い」復号法を試して得られたデータを再び公開鍵の処理にかけて、正しく復号できているかがエラーチェックとして組み込まれているのである。
最後はこちらについての補足です。
2種類のRSA秘密鍵処理
公開鍵暗号RSAの数的構造で説明している通り、秘密鍵による復号/署名作成の処理は、次の2種類があります。
変換前の値を $h$、変換後の値を $s$ としたとき、それぞれ次のような計算となります。
- ナイーブな ( 非効率な ) 計算
- $s = mod( h^d, n )$ とする
- 中国剰余定理を活用した現実的な計算
- $c_p=mod(h^{d_p},p),~c_q=mod(h^{d_q},q)$ とする
- $s=c_q+mod((c_p−c_q)\times q_{inv},p)\times q$ とする
なお、$d_p, d_q, q_{inv}$ は $d_p=mod(d,p−1),~d_q=mod(d,q−1),~q_{inv}\equiv q^{-1}~mod~p$
として、予め計算して秘密鍵の一部としている数値です。
逆に言えば、これらの数値が秘密鍵に含まれていれば、後者の計算法が取れるため、前者ではなく後者で計算を行うのです。
ところが、OpenSSLのRSA処理では、敢えて前者の計算を行う状況があったということです。
妥当性チェック
その状況というのが、「中国剰余定理を活用した計算」の結果をチェックして「正しくない」と判断した場合です。
ご存じの通り、RSAの計算では秘密鍵で $s\rightarrow h$ と計算した後、更に公開鍵で $h\rightarrow s'~~(~s'=mod(h^e,n)~)$ の計算を行うと、$s=s'$ と元の値に戻る性質があります。
逆に言えば、この性質が成立していなければ計算結果が妥当でないと分かるということです。
なお、毎回この妥当性チェックを行っていることになるわけで、それは計算時間のロスにつながるのではないかと思われる方もいるかも知れませんが、公開鍵による計算は秘密鍵による計算より数十倍のレベルで処理量が少ないので、現実的には大したロスにならないということでしょう。
ただ、今回のように「$p,q$が実は素数ではない」という状況でもない限り妥当性チェックに引っかかることもないはずで、OpenSSLでなぜこのようなチェックを行う実装となったのかは不思議なところです。
コード上の該当箇所
では、今回使用した OpenSSL 1.1.1n のソース crypto/rsa/rsa_ossl.c で、そのあたりの処理を追ってみます。
まず、秘密鍵処理の実態は、367行目からの rsa_ossl_private_decrypt であり、433行目の条件分岐で中国剰余定理が使えると判断できれば、rsa_mod_exp で参照されている関数を呼び出し、実際の処理を行います。
static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
unsigned char *to, RSA *rsa, int padding)
{
…(略)…
/* do the decrypt */
if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
(rsa->version == RSA_ASN1_VERSION_MULTI) ||
((rsa->p != NULL) &&
(rsa->q != NULL) &&
(rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
goto err;
その関数は、同ファイル597行目からの rsa_ossl_mod_exp であり、メインの計算は割愛しますが、891行目からの後処理で、チェック用の値として公開鍵 ( 数値 rsa->e,rsa->n ) で処理し直した値 vrfy を計算しています。
static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
{
…
tail:
if (rsa->e && rsa->n) {
if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) {
if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx,
rsa->_method_mod_n))
goto err;
} else {
bn_correct_top(r0);
if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
rsa->_method_mod_n))
goto err;
}
そして、元の値との差分をとっておいて、921行目からの以下のコードの部分でゼロになるかどうかによる「戻っているか」の判断と、チェックに失敗した場合のフォールバックとしてナイーブな計算を行っていることが分かります。
※コメントにも "raw (slower) mod_exp" とあります。
if (!BN_is_zero(vrfy)) {
/*
* 'I' and 'vrfy' aren't congruent mod n. Don't leak
* miscalculated CRT output, just do a raw (slower) mod_exp and
* return that instead.
*/
…(略)…
if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx,
rsa->_method_mod_n)) {
BN_free(d);
goto err;
}
このように、OpenSSLのコードで実装されていることが読み取れます。
なお、フォールバック後の妥当性チェックは行われないので、まとめのときのように、「誤復号」の結果が出ることは防げていません。
おわりに
この「処理の破綻」を引き起こす鍵が作られる確率は、そもそも現実レベルのものではないので、今回の話がなにか処理の欠陥につながったりすることはありません。そういう意味で実用的ではないのですが、周辺の数学面の話の理解を深めるのに役立てば幸いかと思います。