DGK 密碼系統加密加速
在@poncho在這裡很好地澄清了 RSA 加速之後，讓我們看看我是否能夠在DGK 密碼系統的情況下做同樣的事情：
我們有 pk = (n, g, h, u), sk = (p, q, $ v_p $ , $ v_q $ ) 生成如下：
- 我們有 3 個數字， $ k > t > l $
- 我們選擇 u 作為下一個大於 $ 2^{l+2} $ （有超過 $ l + 2 $ 位）
- 我們選擇 2 個隨機 t 位素數， $ v_p $ , $ v_q $
- 我們生成長度為 p 和 q 的素數 $ k/2 $ 位這樣 u 和 $ v_p $ 劃分 $ p-1 $ 你和 $ v_q $ 劃分 $ q-1 $
- 我們生成 h 的順序 $ v_p*v_q $ 模 p 和 q
- 我們生成 g 的順序 $ uv_pv_q $ 模 p 和 q
加密： $ E(m,r) = g^mh^r\pmod n $
解密： $ E(m,r)^{v_p} = (g^{v_p})^m\pmod p $ ，它唯一地確定 m，因此我們預先計算右側的所有可能值（因為消息空間 u 非常小）並且在解密期間我們只搜尋 $ c^{v_p} $ 在預先計算的值中。後來編輯：對原始論文的更正指出 $ c^{v_p} $ 唯一確定 m，所以沒有必要使用 $ c^{v_pv_q} $ . 我無法弄清楚他們是如何得出這個結論的，但它似乎確實有效。
我知道缺少很多細節，但是對於那些好奇的人，我建議閱讀整篇論文以及隨後的安全更正（將 v 替換為 $ v_p $ 和 $ v_q $ ).
現在，我們想加快加密過程，因為那些取模 n 的指數相當慢，所以我們表示 $ E(m,r) $ 在 $ \mathbb{Z}_n^* $ 作為 $ E_p(m,r) $ 和 $ E_q(m,r) $ 在 $ \mathbb{Z}_p^* \times \mathbb{Z}_q^* $ :
- $ E_p(m,r) = g^mh^r \pmod p $
- $ E_q(m,r) = g^mh^r \pmod q $
現在我們應用中國剩餘定理來獲得 $ E(m,r) \pmod n $ . 用於實現此目的的公式是：$$ \sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i} $$
所以我們有：$$ E(m,r) = E_p(m,r)q(q^{-1}\bmod p) + E_q(m,r)p(p^{-1}\bmod q) \pmod n \Rightarrow $$
$$ E(m,r) = (g^mh^r \bmod p)q(q^{-1}\bmod p) + (g^mh^r \bmod q)p(p^{-1}\bmod q) \pmod n $$
上面的公式似乎有道理，對吧？正確的？
因為需要進一步優化，所以我需要以某種方式分兩步計算上述公式。更準確地說，隨機數有時可以在不同的過程中生成，所以我需要分裂的能力 $ E(m,r) = g^mh^r\pmod n $ 一半：
- 第一次計算 $ E_{nonrand}(m,r) = g^m \pmod n $
- 然後隨機化： $ E(m,r) = E_{nonrand}(m,r) * h^r\pmod n $
我的直覺告訴我，在這種情況下我仍然可以執行加密加速，公式應該如下所示：
$$ E_{nonrand}(m,r) = (g^m \bmod p)q(q^{-1}\bmod p) + (g^m \bmod q)p(p^{-1}\bmod q) \pmod n $$
$$ E(m,r) = E_{nonrand}(m,r) * [(h^r \bmod p)q(q^{-1}\bmod p) + (h^r \bmod q)p(p^{-1}\bmod q)] \pmod n $$
我測試了這個公式，它似乎有效，但我不確定我做對了……另外，是否可以跳過 $ \pmod n $ 計算時的操作 $ E_{nonrand}(m,r) $ ? 在我看來，這是多餘的。
事實證明，這只是一個初學者問題，我想我設法弄明白了。自從 $ E(m,r) = g^mh^r \pmod n $ ，我可以把它一分為二： $ E(m,r) = (g^m \pmod n) (h^r\pmod n) $ 然後在兩邊應用 CRT 技巧，之後我可以將結果相乘以取回原始結果：
$ E_{nonrand}(m,r) = (g^m \bmod p)q(q^{-1}\bmod p) + (g^m \bmod q)p(p^{-1}\bmod q) \pmod n $
$ R_{h}(r) = (h^r \bmod p)q(q^{-1}\bmod p) + (h^r \bmod q)p(p^{-1}\bmod q) \pmod n $
$ E(m,r) = E_{nonrand}(m,r)R_{h}(r) \pmod n $
誰能想到我不應該跳過（mod n）減少的任何原因 $ E_{nonrand}(m,r) $ 和 $ R_{h}(r) $ ? 在我看來它們是多餘的……
LE：在實踐中，(mod n) 減少在每一步都是有用的，以避免數字增加，這會損害性能。