72982


<https://ja.stackoverflow.com/a/72891/754> の質問を調べていく過程で、 RSA の秘密鍵は、その素数`p`,
`q`
以外にも、いくつかの値を前もって計算しておくことで、復号化の処理を高速化しているのだ、という記述を見つけました。具体的には、この回答から抜粋すると以下です。

[code]

    modulus:         n := p * q
    publicExponent:  e := 65537  (==0x10001)
    privateExponent: d := e^-1 mod LCM(p-1, q-1) ※LCM は 最小公倍数関数
    prime1:          p
    prime2:          q
    exponent1:       dP := d mod (p-1)
    exponent2:       dQ := d mod (q-1)
    coefficient:     q_inv := q^(-1) mod p
    
[/code]

このとき、 [英語版 Wikipedia
の記述](https://en.m.wikipedia.org/wiki/RSA_\(cryptosystem\)#Using_the_Chinese_remainder_algorithm)に依れば、クライアントから送られてきた暗号文`C
== M^e` に対して、以下の処理を行なうと、その結果 `M'` は、その実、RSA 暗号を復号化した原文(`M`)になっている、すなわち、 `M' ==
(M^e)^d mod n == M` が成立するそうです。

[code]

    m1 := C^dP mod p
    m2 := C^dQ mod q
    h  := q_inv * (m1 - m2) mod p
    M' := m2 + h * q mod n
    
[/code]

ちょっと考えて、どうしてこのように計算すると `M' == M` が成立するのかが、自分には理解できていません。

# 質問

上記 RSA の復号化処理の高速化は、どうしてたしかに正しく復号ができているのでしょうか?

# 追記@2020/12/29

中国人剰余定理自体は理解していて、つまり、以下という認識です。

互いに素な数`a`, `b` があったとき、ある数`x`が

  * `x ≡ n_a mod a`
  * `x ≡ n_b mod b`

を満たすとき、

[code]

    x ≡ n mod (a * b)
    
[/code]

が一意に存在する、ということです。この定理をどのように適用すると、この高速化が確かに正しい計算結果を得ていることになるのかが、分かっていないことです。


CC BY-SA 4.0
2020-12-26T04:42:36.263
72900
2021-12-25T05:37:07.980
2020-12-30T07:25:37.440
754
754
question
数学 暗号理論 rsa
RSA の復号化を中国人剰余定理で高速化する際に、どうしてこれで正しく計算できているのかが分からない


# 1\. `C^d ≡ m1 mod p` かつ `C^d ≡ m2 mod q`

まず、 `C^d ≡ m1 mod p` かつ `C^d ≡ m2 mod q`を示す。同様の証明となるため、`p` についてのみ示す。

## 1.1 `C` が `p` の倍数の場合

`C`が`p`の倍数であれば、`C^dP`も`p`の倍数であるから、 `m1 := C^dP ≡ 0 ≡ C^d mod p`

## 1.2 `C` が `p` の倍数ではない場合

`p` は素数なので、`C` と `p` は互いに素。  
フェルマーの小定理により、 `C^(p-1)≡1 mod p`。  
また定義より、ある数`k`が存在して、`d = k*(p-1) + dP`。

`mod p` の下、  
`C^d = C^(k*(p-1) + dP) = (C^(p-1))^k * C^dP ≡ 1^k * C^dP = C^dP`

よって、 `C^d ≡ m1 mod p`

# 2\. 中国人剰余定理の適用

`p != q` であれば、中国人剰余定理の、具体的な計算をすればよくなる。この場合、その実、 `h` や `M'` の計算は、 1.
で表された前提に対して、中国人剰余定理を素直に適用しているに過ぎない。結果として計算される `M'` は、`p*q` を法として `C^d` と合同になる。

以下、証明を付けておくと、

今、 `C^d ≡ m2 mod q` より、ある`k`が存在して、`C^d = k*q + m2`.  
これを `p` の方の合同式に代入して、

`k*q + m2 ≡ m1 mod p`

`p` は素数であり、素数体上の演算が可能なので、これについて解いて、

`k ≡ (m1 - m2)*q_inv mod p = h`

であって、よって、ある`X` が存在して、 `k = X*p + h`。  
k の定義代入しなおして、

`C^d = (X*p + h)*q + m2 ≡ h*q + m2 mod p*q`

以上より示された。  
(`p` = `q` は、多分セキュリティ上の理由で、`p`, `q` 生成の段階ではじくべきだと考えられる。)

# 2021/12/25 追記

スタックオーバーフローでは、数式が表示できないので、自分のブログに rsa と中国人剰余定理まわりをまとめて記述しました。

<https://blog.yukii.work/posts/2021-12-22-rsa-and-chinese-remainder-theorem>


CC BY-SA 4.0
2020-12-30T07:59:37.290
72982
2021-12-25T05:37:07.980
2021-12-25T05:37:07.980
754
754
72900
answer