使用 RSA-CRT 創建雜湊數據簽名

我取了兩個素數 p=137 q=131 M=64 我想創建一個數字簽名

n=pxq=17947
phi=(p-1)x(q-1)=17680
e=3                                     (I have taken public key e=3 as gcd(3,n)=1)
d=e^-1 mod phi
=3^-1 mod 17680 = 11787
dP= d^-1 mod (p-1)
 = (11787)^-1 mod 136 = 3
dQ= d^-1 mod (q-1)
 = (11787)^-1 mod 130 = 3
qinv= q^-1 mod p 
   = (131)^-1 mod 137 = 114
mp= M ^dP mod p
 = 64^3 mod 137 = 87
mq= M ^dQ mod q
 = 64^3 mod 131 = 121
h= 114*(87-121) mod 137
=97                              (after converting to positive remainder)
Sig= mq+ h*q
  =121+ 97*131
  =12828

確認

M= (Sig)^e mod N
= (12828)^3 mod 17947
= 8301

與消息 M=64 不匹配。我在哪裡做錯了？

問題的公式dP= d^-1 mod (p-1)有誤。相當， $ d_P=d\bmod(p-1) $ , 或者更直接 $ d_P=e^{-1}\bmod(p-1) $ ，這使得無需計算 $ d $ . 相同的 $ d_Q $ . 有關公式的證明，請參見此答案。

在 RSA 中使用 CRT 是轉換的另一種計算方式¹ $ x\mapsto x^d\bmod n $ . 選擇的條件 $ p $ , $ q $ , $ e $ 維持不變。它們依賴於參考。理論工作的共同點是一些小的 $ e\ge3 $ ， 和 $ p $ 和 $ q $ 不同的大隨機素數使得 $ \gcd(e,p-1)=1=\gcd(e,q-1) $ 並且具有大約相同的位大小。

---

注意：問題的計算是用RSA實際數字簽名步驟之一的小*參數說明。*但

• 使用的素數對於安全性來說太小了。實際的 RSA 密鑰使用素數 $ p $ 和 $ q $ 用數百個十進制數字，使公共模數 $ n=p,q $ 很難考慮。
• 在實際的 RSA 數字簽名中，私鑰函式的輸入不是消息。相反，消息（任意大的數據）被散列和填充以形成 $ x\mapsto x^d\bmod n $ 轉型。

---

¹ 私鑰轉換是公鑰轉換的逆 $ y\mapsto y^e\bmod n $ 什麼時候 $ n=p,q $ 和 $ e,d\equiv1\pmod{\lambda(n)} $ 或者 $ e,d\equiv1\pmod{\varphi(n)} $ . 這些轉換在集合上 $ \Bbb Z_n $ 或者 $ \Bbb Z_n^* $ . 這取決於參考。

引用自：https://crypto.stackexchange.com/questions/82083