公開鍵暗号RSAの数的構造

はじめに

背景

これまで、電子署名DSA/ECDSAの数的構造や電子署名EdDSA(ed25519)の数的構造など、離散対数問題に基づく公開鍵暗号について記事にしてきましたが、オーソドックスながらRSAについても数的な構造と簡単な実装サンプルをまとめてみることにしました。

RSAの特徴

• RSAの機能的特徴
  ※本記事で特には触れませんが予備知識として
  • DH法 ( ディフィー・ヘルマンの鍵交換 ) に次いで古く、非常にポピュラーな公開鍵暗号
  • 暗号化 ( RSA暗号 )・電子署名 ( RSA署名 ) に両用できる、今では珍しい方式
  • 特にRSA署名が、SSL/TLSやSSHなど各所で利用されている
• RSAの数的構造
  • 巨大な数の素因数分解の困難さにより、計算の一方向性を実現
  • べき乗のあまりの周期性を利用し、逆変換の関係にある2処理を実現
    → 暗号化・電子署名への両用のカギ
  • 2つ ( あるいは複数 ) の素数での、べき乗の余りの周期を組み合わせて、大きな周期を作る
    → 素因数分解の結果 ( 各素数 ) を知らない人にとって周期が分からない
    → 一方向性の正体

導入

RSAの話をするにあたって、重要な数学上のトピックがあります。まずはそこから軽く見ていきます。

mod nの世界

RSAは「余り」の計算と切っても切り離せません。つまりmod nの話は必須です。

もしよく分からないということであれば、「電子署名DSA/ECDSAの数的構造(1/2)」の「事前知識」を先にご覧ください。

各素数で割った余りの組み合わせ～中国剰余定理～

小学生時代の算数で、次のような問題に見覚えがないでしょうか。

余りの問題

Q: 11で割ると2余り、13で割ると2余る自然数を挙げよ
A: 2, 145, 288, …

この問題は余りが同じ2であることに気付けば、すぐに解けるものです。
最も小さい 2 はそのままですが、それ以降は143おきに条件を満たす数が見つかります。
これは、143というのが11,13の2数の最小公倍数 ( 共通の倍数の中で最小のもの ) になっているからです。

しかし、次のような問題にすると「余りが同じ」という路線では攻められません。

2素数での一般形

Q: 素数p,qに対し、pで割るとa余り、qで割るとb余る整数はどんな数か?

とはいえ、そうであっても、条件を満たす数が積pq ( 2素数の最小公倍数 ) おきに現れるのは同じです。つまり、p,qで割ったそれぞれの余りが分かっていれば、積pqで割った余りが1通りに決まるということです。

この性質を記述したのが中国剰余定理 ( Chinese Reminder Theorem ) です。
※実際には2つの素数に限らず、複数の素数の場合も含め、もっと一般的な性質を表すものです

RSAでは、実装上の最適化も含め、この中国剰余定理が大きく関係してきます。
この「1通りに決まる」余りを実際に計算する方法については、後の章で出てきます。

べき乗の余りの周期性～フェルマーの小定理～

さて、RSAは余りの計算が重要なわけですが、余りである以上、値の候補は有限であり、周期を生み出します。

その周期性に関わるのがフェルマーの小定理です。

例えば、$2^1,~2^2,~2^3,\cdots$という2のべき乗、それぞれに対する素数11による余りを見てみます。
※以下ではべき乗してから余りを求めてますが、実際には掛け算が発生するたびに都度余りを取って、途中の計算結果が大きくなり過ぎないようにするなど、計算を工夫します。

r	1	2	3	4	5	6	7	8	9	10	11	12
$2^r$	2	4	8	16	32	64	128	256	512	1024	2048	4096
$2^r ~mod ~11$	2	4	8	5	10	9	7	3	6	1	2	4

2のべき乗は決して11の倍数にはなりませんから、余りは1～10の高々10通りしかありません。なので、必ず周期的に繰り返しを見せるのですが、ちょうど11乗したところで元に戻ります。1乗と11乗で結果が同じになっているので周期は10です。
※べき乗する元の数によっては11乗に辿り着く前に元に戻ることもあるのですが、11乗の時点で元に戻っているのは変わりません。

一般の数式としては $a^p~\equiv~a~~\bmod~p~(~p:素数~)$ で、これは数学者の名前にちなんでフェルマーの小定理と呼びます。
上の表はちょうど $a=2,~p=11$ のケースに該当します。

RSAの数的構造

では、導入で説明したトピックを元に、RSAの構造を見ていきます。
なお、以下では2つの素数を使うポピュラーな方式について説明しますが、一般には3つ以上の複数の素数を使うこともできます。

2つの周期の組み合わせ

$a^r~\bmod~p~(pは素数~)$ は、( もっと短い周期になる可能性はあるにしても ) 必ず $p-1$ 毎に繰り返すという話がありました。

では2つの素数でその周期を組み合わせてみるとどうなるでしょうか。
次の表は、$2^r~\bmod~11$と$2^r~\bmod~13$の周期性を並べたものです。

そうすると、$2^r~\bmod~11$と$2^r~\bmod~13$は、周期10,12の最小公倍数である60周期で、値が2になるところが重なります。
つまり、表の更に先まで挙げていくと、次のようになっています。

• $2\equiv 2^1\equiv 2^{61}\equiv 2^{121} \equiv 2^{181} \equiv 2^{241} \equiv 2^{301} \equiv \cdots~\bmod~11$
• $2\equiv 2^1\equiv 2^{61}\equiv 2^{121} \equiv 2^{181} \equiv 2^{241} \equiv 2^{301} \equiv \cdots~\bmod~13$

ここで、今度は中国剰余定理も絡めていきます。
11,13両方で割った余りが同じであれば、143で割った余りも同じになるというのが中国剰余定理から言える内容でした。
そうすると、11,13で割った余りが共に60周期で繰り返すので、143で割った余りも60周期で繰り返していることも分かります。

• $2\equiv 2^1\equiv 2^{61}\equiv 2^{121} \equiv 2^{181} \equiv 2^{241} \equiv 2^{301} \equiv \cdots~\bmod~143$

ここまで、2のべき乗で周期を見てきましたが、これはどの数を元にしてべき乗を計算しても同じ周期性があります。つまり、

• $2\equiv 2^1\equiv 2^{61}\equiv 2^{121} \equiv 2^{181} \equiv 2^{241} \equiv 2^{301} \equiv \cdots~\bmod~143$
• $3\equiv 3^1\equiv 3^{61}\equiv 3^{121} \equiv 3^{181} \equiv 3^{241} \equiv 3^{301} \equiv \cdots~\bmod~143$
• $4\equiv 4^1\equiv 4^{61}\equiv 4^{121} \equiv 4^{181} \equiv 4^{241} \equiv 4^{301} \equiv \cdots~\bmod~143$
• $5\equiv 5^1\equiv 5^{61}\equiv 5^{121} \equiv 5^{181} \equiv 5^{241} \equiv 5^{301} \equiv \cdots~\bmod~143$
• $\cdots$

※くどいようですが、元になる数によってはもっと短い周期で繰り返すこともあります。が、60おきに見て繰り返しになっているのは同じです。

変換・逆変換

ここまでで、べき乗の mod 143 の剰余が60周期で繰り返していることが分かりました。

• $2\equiv 2^1\equiv 2^{61}\equiv 2^{121} \equiv 2^{181} \equiv 2^{241} \equiv 2^{301} \equiv \cdots~\bmod~143$
• $3\equiv 3^1\equiv 3^{61}\equiv 3^{121} \equiv 3^{181} \equiv 3^{241} \equiv 3^{301} \equiv \cdots~\bmod~143$
• $\cdots$

ここで、上の式に現れる指数として301を取り上げてみます。
この数でないといけないということはありませんが、これは $301=7\times 43$と周期である60より小さい2数の積の形に表すことができる数です。( 他にも $481=13\times 37$ などがあります )

そうすると、べき乗の指数の性質から、次のことが分かります。

• $(2^{7})^{43}\equiv (2^{43})^{7}\equiv 2^{7\times 43}\equiv 2^{301}\equiv 2~\bmod~143$
• $(3^{7})^{43}\equiv (3^{43})^{7}\equiv 3^{7\times 43}\equiv 3^{301}\equiv 3~\bmod~143$
• $\cdots$

つまり、143未満の自然数同士の変換として、$x\rightarrow mod(x^{7},143),~x\rightarrow mod(x^{43},143)$ の2つが、お互いに逆変換の関係にあるということです。
※前者の変換を行ってから後者の変換を行っても、後者の変換を行ってから前者の変換を行っても元の値に戻る。

なお、python/python3コマンドが使える環境であれば、pow関数によって簡単に計算が試せます。Pythonのpow関数は、べき乗の剰余を一発で計算できるからです。
以下、2→前者の変換→128→後者の変換→2、3→後者の変換→16→前者の変換→3 を計算した例です。

pythonでの変換・逆変換計算

$ python3
…(略)…
>>> pow(2,7,143)
128
>>> pow(128,43,143)
2
>>> pow(3,43,143)
16
>>> pow(16,7,143)
3

この変換・逆変換が暗号処理に活用できるのです。

ナイーブなRSAの実装

暗号化と署名

さきほどの変換・逆変換を用いて、暗号化および署名機能を実装することができます。

• 鍵生成

  • 秘密の素数 $p,q$ を決め、$n=pq,~r=LCM(p-1,q-1)$ を計算します。
    ※今までの 11,13 が $p,q$、積 143 が $n$、周期60が $r$ に相当します。
  • $ed\equiv 1~\bmod~r$ を満たす $(e,d)$のペアを探します。
    ※上での7,43のペアが該当します。ちょうど 7×43=301 が周期60の倍数+1 になっているということです
  • $(n,e)$ の組を公開鍵として一般に公開します。$(n,d)$ の組は秘密鍵として特定の使用者のみが持ちます。

• 暗号化

  • 暗号化
    • 対象のメッセージ(平文)に対し、$n$ 未満の自然数を公知の規則で対応させ、$m$ とします。
      
    • 公開鍵により $c=mod(m^e,n)$ を計算し、$c$ を暗号文とします。
      ※上での $mod(2^7,143)=128$ という計算に相当
  • 復号
    • 暗号文 $c$ に対し、秘密鍵により $m'=mod(c^d,n)$ を計算します。
      ※上での $mod(128^{43},143)=2$ という計算に相当
    • こうして計算した $m'$ は暗号化した $m$ と一致するため、そこから元のメッセージを得ることができます。

• 署名

  • 署名(生成)
    • 対象のメッセージに対し、$n$ 未満の自然数を公知の規則で対応させ、$h$ とします。
      
    • 秘密鍵により $s=mod(h^d,n)$ を計算し、$s$ を署名データとします。
      ※上での $mod(3^{43},143)=16$ という計算に相当
  • (署名)検証
    • 対象のメッセージに対し、署名(生成)側と同様に $h$ を対応させます。
    • 署名データ $s$ に対し、公開鍵により $h'=mod(s^e,n)$ を計算します。 ※上での $mod(16^7,143)=3$ という計算に相当
    • $h,h'$ が一致していれば検証成功として、署名は正しかったと判断します。不一致なら不正な署名と判断します。
      

いずれの場合も、秘密鍵での処理が「特定の人にしかできない」用途になっています。
※特定の人しか「復号」により元のメッセージを見られない、特定の人しか「署名」により正しい署名を作れない。
変換→逆変換の順序をどちらで使うかで、RSAは2つの機能に対応しているのです。これは、現存するメジャーな公開鍵暗号の中では、RSAのみの特異な性質と言えます。

計算の一方向性

このRSAで計算の一方向性、つまり秘密鍵を持ってない人でも処理できてしまうことを防ぐために、2つのポイントがあります。

• $e\rightarrow d$の推定の困難さ
  
  • $e$は公開鍵の一部として公開されるデータです。ここから秘密鍵に含まれる$d$が推定されては問題です。
  • ここで両者は $ed\equiv 1~\bmod~r~(~r=LCM(p-1,q-1)~)$ の関係を持って作られた数値です。
  • つまり $r$ が判明していれば mod の逆元計算として $e$→$d$ が容易に計算できます。
    ※この計算は拡張ユークリッドの互除法により行うことができます。
  • しかし $r$ を知るには、元の素数 $p,q$ が必要です。$n=pq$ の素因数分解の困難さが、$e\rightarrow d$の推定の困難さにつながっています。
• べき乗の逆計算の困難さ
  
  • 暗号化における $c=mod(m^e,n)$ において、公開鍵 $(e,n)$・暗号文 $c$ は第三者の目に触れる可能性のあるデータです。
  • ここから元のメッセージに対応する $m$ が秘密鍵なしで推定されては問題です。
  • また、署名における $s=mod(h^d,n)$ において、$n$ は公開鍵にも含まれるデータであり、また $h,s$ も第三者の目に触れる可能性のあるデータです。
  • ここから秘密鍵の一部である $d$ が推定されては問題です。
  • つまり、以下に挙げるべき乗の2つの逆計算の mod 版の困難性が暗黙のうちに仮定されています。
    • べき根 … $y=x^n$ に対する $x=\sqrt[n]{y}$
      ※この場合は、$c\equiv m^e~\bmod~n$ に対する $c\rightarrow m$
    • 対数 … $y=a^x$ に対する $x=\log_a{y}$
      ※この場合は、$s\equiv h^d~\bmod~n$ に対する $s\rightarrow d$ ( 離散対数 )
      ※この離散対数は、DHやDSA、各種の楕円曲線暗号でも重要な概念です。

メッセージと数との対応

前項、暗号化・復号における「メッセージ→$m$」、署名・検証における「メッセージ→$h$」は、どちらも同じ「n未満の自然数への対応」ですが、その性質に違いがあります。

• 暗号化における「メッセージ→$m$」の対応
  復号処理の際、「$m$→メッセージ」の逆の対応が必要になります。つまり、この対応は1対1のものです。
  そのため、扱えるメッセージの種類は非常に少なく、ほんのサイズの小さなデータを暗号化することしかできません。
• 署名における「メッセージ→$h$」の対応
  「$h$→メッセージ」の逆の対応は不要であるため、扱えるメッセージの種類を好きなように広くとることができます。
  ただし、同じ $h$ に対応づく複数のメッセージが容易に見つかる ( 衝突が発生する ) ようだと「署名の偽造」につながり問題ですから、衝突が容易に発生せず小さなデータを作り出せるという性質を持つ技術、つまり「暗号学的ハッシュ」により対策する必要があります。

現実のRSA

これまでの話は各所でもよく出てくる話なので、ご存知の方も多いかもしれません。
これだけだと、公開鍵と秘密鍵には $e,d$ の、どちらを公開用に選ぶかだけの違いがあるだけで、実際は対等のものに見えます。
※署名の説明で「秘密鍵で暗号化」というデマが出回ったのも、公開鍵・秘密鍵が対等と見られていた時期があったからと推測できます。( 参考: 「電子署名=『秘密鍵で暗号化』」という良くある誤解の話 )

が、現実のRSAでは公開鍵と秘密鍵には明確な違いがあります。以降ではその違いについて見ていきます。

実際の鍵データのサンプル

RSAの鍵データを使うためのフォーマットは色々ありますが、メジャーなものとして、OpenSSLというツールで作れるPEM形式のデータを見てみます。

鍵を作る場合は、これまで出てきた $n$ の ( 2進数における ) 桁数を鍵長として指定します。
最近の一般的な鍵長は 2,048bit 以上で、これは10進数にして600桁超となりますが、ちょっと記事内で表示するには長いので、桁数1/16の128bitのサンプルを見てみます。OpenSSLを使い、以下のコマンドで秘密鍵・公開鍵を作ることができます。
※秘密鍵ファイルは公開鍵を同梱したデータとなるため、秘密鍵作成→公開鍵抽出の2段階になっています。

• 128bit 秘密鍵作成 … openssl genrsa -out 秘密鍵ファイル 128
• 公開鍵抽出 … openssl rsa -pubout -in 秘密鍵ファイル -out 公開鍵ファイル

実際に作ったサンプルファイルとしては次のようになります。

128bit秘密鍵

-----BEGIN RSA PRIVATE KEY-----
MGECAQACEQC/tHmNaE9TvKH0LXk0AEDfAgMBAAECEDWLchwGE4oefENbgSNCpakC
CQD4zGTrPrE+lQIJAMVBBBxb/cijAggDA6btWrMXCQIIHADW7I/Cv7ECCBj8I5vI
+H87
-----END RSA PRIVATE KEY-----

ペアになる公開鍵

-----BEGIN PUBLIC KEY-----
MCwwDQYJKoZIhvcNAQEBBQADGwAwGAIRAL+0eY1oT1O8ofQteTQAQN8CAwEAAQ==
-----END PUBLIC KEY-----

これは、数値データをバイナリで表してBase64変換によりテキストデータにしたものなので、そのままでは内容がつかめません。しかし、OpenSSLの場合、openssl rsaコマンドで各数値を見ることができます。

秘密鍵に含まれる数値の確認

$ openssl rsa -text -noout -in 秘密鍵ファイル
Private-Key: (128 bit)
modulus:
    00:bf:b4:79:8d:68:4f:53:bc:a1:f4:2d:79:34:00:
    40:df
publicExponent: 65537 (0x10001)
privateExponent:
    35:8b:72:1c:06:13:8a:1e:7c:43:5b:81:23:42:a5:
    a9
prime1: 17927815178186997397 (0xf8cc64eb3eb13e95)
prime2: 14213646418806950051 (0xc541041c5bfdc8a3)
exponent1: 217200745403062025 (0x303a6ed5ab31709)
exponent2: 2017848944574513073 (0x1c00d6ec8fc2bfb1)
coefficient: 1800353103039987515 (0x18fc239bc8f87f3b)

公開鍵に含まれる数値の確認

$ openssl rsa -text -noout -pubin -in 公開鍵ファイル
Public-Key: (128 bit)
Modulus:
    00:bf:b4:79:8d:68:4f:53:bc:a1:f4:2d:79:34:00:
    40:df
Exponent: 65537 (0x10001)

桁数の大きなデータは複数行に分割されて出力されます。このサンプルは次の数値に対応するものです。

• $p,q$ ( prime1,prime2 ) … 17927815178186997397, 14213646418806950051
• $n=pq$ ( Modulus ) … 254819626004470498658400945583046017247
• $e$ ( publicExponent ) … 65537
• $d$ ( privateExponent ) … 71173127454900780892529103473834370473

なお、$r=LCM(p-1,q-1)$ については、計算すると 127409813002235249313129741993026034900 であり、それを元にして $ed\equiv 1~\bmod~r$ であることも確認できます。

…ところが、秘密鍵データの中には、exponent1, exponent2, coefficient というこれまでの話に出ていない3つの数値が含まれています。これは後述する公開鍵処理と秘密鍵処理の非対称性に関連するデータです。

公開鍵と秘密鍵の決め方

まず、公開鍵の$e$と秘密鍵の$d$についてです。
次のように値を再掲しますが、$e$の方が極端に値が小さいことに気付くと思います。

• $e$ ( publicExponent ) … 65537
• $d$ ( privateExponent ) … 71173127454900780892529103473834370473

これは実は、$e$の値はもともと小さな固定値を使うようになっているからです。( 今は65537が一般的 )
そうして $d$ は $ed\equiv 1~\bmod~r$から逆計算して決めます。
※なお、$d$の値が解なしになる可能性が高くなるので、$e$としてはそこそこの大きさの素数を選択します。

このようにしても、$e$はもともと公開する前提であるうえ、$r$の値が漏れなければ$d$の値を推測するのも困難であるため、固定値によるデメリットはありません。
逆に、小さな固定値にすることで、公開鍵処理 $c=mod(m^e,n),~h'=mod(s^e,n)$ の方のみですが、非常に処理量を減らせるというメリットがあります。
※このため、秘密鍵処理よりも公開鍵処理の方が圧倒的に速いという特徴があります。

公開鍵処理と秘密鍵処理の非対称性

中国剰余定理を利用した変形

ナイーブなRSAの実装を見る限りでは、公開鍵処理と秘密鍵処理は、使う数値が違うだけの同等の計算を行うものでした。

しかし、秘密鍵を持つ側は$n=pq$という素因数分解の結果を知っているというアドバンテージがあります。これにより、秘密鍵を持つ側のみが行える処理の効率化が、実際には行われています。
ここで関係してくるのが、冒頭で紹介した中国剰余定理で言及した次の性質です。

p,qで割ったそれぞれの余りが分かっていれば、積pqで割った余りが1通りに決まる

これにより変形した秘密鍵処理 $s=mod(h^d,n)$ ( 署名の場合 ) は次のようになります。

• $d_p=mod(d,p-1),~d_q=mod(d,q-1)$ とします
• $c_p=mod(h^{d_p},p),~c_q=mod(h^{d_q},q)$ とします
• $qq_{inv}\equiv 1~\bmod~p$ となる $q_{inv}$を計算します
  ※この計算は $ed\equiv 1~\bmod~r$ を元に $e\rightarrow d$を計算するのと同様、拡張ユークリッドの互除法により行うことができます。
• $s=c_q+mod((c_p-c_q)\times q_{inv},p)\times q$ が最終的な計算結果です

ちょっとこれだけでは実感し辛いかも知れませんので、$p=11,~q=13,~d=43$ という最初に使った数値での、$h=3\rightarrow s=16$ の計算を変形してみます。

• $d_p=mod(43,11-1)=3,~d_q=mod(43,13-1)=7$
• $c_p=mod(3^3,11)=5,~c_q=mod(3^7,13)=3$
• $13q_{inv}\equiv 1~\bmod~11$を解いて$q_{inv}=6$
  ※これを解くときの拡張ユークリッドの互除法については割愛します
• $s=3+mod((5-3)\times 6,11)\times 13=3+mod(12,11)\times 13=16$

この通り、変形した計算でも同様に $s$ を計算できていることが分かります。

こちらの計算の方が却って複雑になっているように見えるかも知れませんが、べき乗計算の指数がそれぞれ $43\rightarrow 3,~43\rightarrow 7$ と目減りしている分、また $mod~11×13$ の計算が $mod~11,~\bmod~13$ とスケールダウンしている分、トータルでの処理量を少なく抑えることができるのです。
※それでも公開鍵処理よりは圧倒的に遅いです。

なお、$d_p,d_q,q_{inv}$に関しては、鍵を生成した時に最初から計算しておくことができます。
その計算結果を秘密鍵ファイルに保存していたのが、実際の鍵データのサンプルで出てきた exponent1, exponent2, coefficient なのです。

変形が有効な根拠

さて、ここでは先ほどの変形が有効な理由について、参考までに記します。
※計算自体は、式さえ知っていればできるので、こちらは興味のある人向けです。

理由の説明は大きく3段階に分かれます。

1. $s\equiv h^d~\bmod~pq$ から $s\equiv c_p\equiv h^{d_p}~\bmod~p,~s\equiv c_q\equiv h^{d_q}~\bmod~q$ が成立すること
   ※中国剰余定理があるため、$mod~pq$を直接計算しなくても、$mod~p,~\bmod~q$ を個別に計算すれば十分ということに繋がっています。
2. $s\equiv c_q~\bmod~q$ から、ある $x$ に対して $s\equiv c_q+xq~\bmod~p$ と表すことができること
3. $s\equiv c_p~\bmod~p,~s\equiv c_q~\bmod~q,~qq_{inv}\equiv 1~\bmod~p$ から $x\equiv (c_p-c_q)\times q_{inv}~\bmod~p$ と表すことができること

これらを総合すると、$s\equiv c_q+mod((c_p-c_q)\times q_{inv},p)\times q~\bmod~pq$ になるということです。

1に関しては、冒頭で紹介したフェルマーの小定理による、$mod~p$でのべき乗の周期が$p-1$の話そのものです。
$d_p\equiv d~\bmod~p-1$ となるように $d_p$ を決めていますから、周期$p-1$的には $d$乗も$d_p$乗も同じ値になる、つまり$h^d\equiv h^{d_p}~\bmod~p$ということです。
※$h^d\equiv h^{d_q}~\bmod~q$についても同様です

2に関しては、3の前準備にあたります。
まず $mod~q$での値が分かっているのであれば、$mod$ の部分を数倍にした$mod~pq$なら、$q$の倍数をずらした値として表現ができます。
そのずらした分を $q$の$x$倍として表すことで、まず $s\equiv c_q+xq~\bmod~pq$ となります。
次に $mod~pq$ の法の数 $pq$ を、その約数 $p$ に取り換えても合同式そのものの成立が変わらないことを利用します。これで、$s\equiv c_q+xq~\bmod~p$ となります。

3がいよいよ仕上げです。
2で導入した$x$が何かをここで確定させる、という流れになります。
2の式と、$s\equiv c_p~\bmod~p$ は $mod~p$ が揃っていますので、辺々差し引くと、

$$
\begin{eqnarray}
~&~&s-s &\equiv&c_p-(c_q+xq)~\bmod~p \\
\Rightarrow&~&xq&\equiv&(c_p-c_q)~\bmod~p \\
\Rightarrow&~&x\times(qq_{inv})&\equiv&(c_p-c_q)\times q_{inv}~\bmod~p \\
\Rightarrow&~&x\times 1&\equiv&(c_p-c_q)\times q_{inv}~\bmod~p~ ~ ~ ~\because qq_{inv}\equiv 1~\bmod~p
\end{eqnarray}
$$

と、このように3の式を導くことができます。

サンプルコード

これまでで説明した計算式を実装したサンプルコードを、Python版・Ruby版の2種類用意しました。
以下から取得することができます。

いずれも処理内容は同じになっていて、公開鍵クラスPubKeyと秘密鍵クラスPrivKeyに、同じ名前のメソッドconvertを用意し、公開鍵処理・秘密鍵処理を実装しています。

暗号化encryptと(署名)検証verifyが公開鍵処理、復号decryptと署名(作成)signatureが秘密鍵処理を使用しています。

なお、秘密鍵処理に関しては、引数simpleを有効にすることでナイーブな実装を、無効にすることで効率化した実装を選択します。

それぞれのスクリプトを単に実行すると、ランダムなデータを作って暗号化・復号、署名・検証を試してくれます。

サンプルコード実行(Python版)

$ python3 rsa.py
public key: {'n': 3265831229, 'e': 17}
private key: {'p': 71693, 'q': 45553, 'd': 144075617}
original data: 3021937484
encrypted data: 700584546
decrypted data(simple): 3021937484
decrypted data(complex): 3021937484
signature(simple): 1293356111
signature(complex): 1293356111
verification result: True

サンプルコード実行(Ruby版)

$ ruby rsa.rb
public key: #<MyRSA::PubKey:0x00007fffd518f330 @n=2632872409, @e=17>
private key: #<MyRSA::PrivKey:0x00007fffd518f2e0 @p=72649, @q=36241, @d=83887073>
original data: 1212341098
encrypted data: 2534179160
decrypted data(simple): 1212341098
decrypted data(complex): 1212341098
signature(simple): 1640236472
signature(complex): 1640236472
verification result: true

終わりに

式こそ簡単に見えますが、べき乗の周期性や、効率化された実装にまで踏み込むとそれなりに複雑な方式ではないかと思います。
本記事が、より深い理解につながれば幸いです。