這個基於 RSA 的 IBE 方案是否安全？

PKG 執行以下步驟

1. 選擇 $ p,q \in \mathbb{P} $ .
2. 計算 $ N=pq $ .
3. 計算 $ \phi (n)=(p-1)(q-1) $ .
4. 選擇 $ e $ 和 $ gcd(e,\phi(n))=1 $ 和 $ 1 < e < \phi(n) $ .
5. 隨它去 $ e = {p^{e_1}_1} \cdot {p^{e_2}_2} \cdot \ldots {p^{e_k}k} $ 的質因數分解 $ e $ 為了 $ i \in k:p_i \in \mathbb{P},e_i \in \mathbb{N} $ . 選擇單射映射 $ H $ 和 $$ \begin{align*} H &: \begin{cases} {0,1}^i \rightarrow \mathbb{Z} / N \mathbb{Z} & \ ID \mapsto m = {p^{e{m_1}}1} \cdot {p^{e{m_2}}2} \cdot \ldots {p^{e{m_k}}k} & (i \in k:p_i \in \mathbb{P},e{m_i} \in \mathbb{N}) \end{cases} \end{align*} $$

和 $ eH(ID)<\phi(n) $ 為了 $ i \in \mathbb{n} $ . 公開可用的參數是 $ \texttt{params} = \langle e, N, H \rangle $ 和 $ \texttt{master-key} $ 是 $ \phi(n) \in \mathbb{Z} / N \mathbb{Z} $ .

然後 PKG 需要一個 $ ID \in {0,1}^{} $ （來自愛麗絲）併計算相應的密鑰 $ d_{ID} $ 和 $$ \begin{align} (e H(ID)) d_{ID} \equiv 1 \text{ mod } \phi(n) \end{align*} $$

當 Bob 想要加密消息時 $ m \in \mathbb{Z} / N \mathbb{Z} $ , 他拿 $ \texttt{params} $ 併計算 $$ \begin{align*} c \equiv m^{e H(ID)} \text{ mod } N \end{align*} $$

愛麗絲解密了這個密文 $ c $ 和 $$ \begin{align*} m \equiv c^{d_{ID}} \text{ mod } N \end{align*} $$

---

例子

1. $ p = 1010231362240711373894507355467 \in \mathbb{P} $ 和

$ q = 793738224882014450642935586909 \in \mathbb{P} $ . 2. $ N=pq=801859248185081566400631735533731882269717325788593134781503 $ 3. $ \phi(N) = 2^3 \cdot 31 \cdot 283 \cdot 29347 \cdot 39547129 \cdot 422250739 \cdot 1354514929 \cdot 17211833615713895353775639 $ . 4. $ e = 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 $ . 5. 它適用 $ ID \in {0,1}^8 $ 和 $ ID=\langle b_1,b_2,\ldots,b_8 \rangle $ 為了 $ i \in 8:b_i \in {0,1} $ . 選擇 $ H $ 作為： $$ \begin{align*} H &: \begin{cases} {0,1}^8 \rightarrow \mathbb{Z} / N \mathbb{Z} & \ ID \mapsto m = {5^{{b_1}}} \cdot {7^{{b_2}}} \cdot \ldots \cdot {29^{{b_8}}} & \end{cases} \end{align*} $$

公開可用的參數是 $$ \begin{align*} \texttt{params} &= \langle 1078282205, 801859248185081566400631735533731882269717325788593134781503, H \rangle \end{align*} $$ 這 $ \texttt{master-key} $ 是 $$ \begin{align*} \phi(N) &= 801859248185081566400631735531927912682594599964055691839128 \end{align*} $$

PKG 需要然後 $ ID = 01101111 $ 作為使用者“o”的ID。然後 $ H(ID) = 5^0 \cdot 7^1 \cdot 11^1 \cdot 13^0 \cdot 17^1 \cdot 19^1 \cdot 23^1 \cdot 29^1 = 16588957 $ , $ eH(ID)=17887577132610185 $ 和 $ d_{ID}=308315206989333722335381678529602981822693965290742774973561 $ .

使用者“i”現在想加密消息 3463463463463424234234234。他計算 $$ \begin{align*} c &\equiv 3463463463463424234234234^{17887577132610185} \text{ mod N} \ &\equiv 353097511425650359803351296367609508451542189692844760010085 \text{ mod N} \end{align*} $$

使用者“o”使用以下命令解密密文： $$ \begin{align*} m &\equiv 353097511425650359803351296367609508451542189692844760010085^{D_{ID}} \text{ mod N} \ &\equiv 3463463463463424234234234 \text{ mod N} \end{align*} $$

不，這不安全。

問題是愛麗絲知道 $ d_{ID} $ 和 $ e_{ID} $ , 可以計算 $ f=d_{ID}\cdot e_{ID}-1 $ 這是兩者的倍數 $ p-1 $ 和 $ q-1 $ ; 然後從 $ N,f $ 可以有效地分解 $ N $ 使用此處詳述的算法；然後可以計算 $ d_{ID} $ 對於任何 $ {ID} $ ，從而以正常方式破譯。

不，這不對。

愛麗絲知道她自己 $ eH(ID) $ 她知道相應的私鑰。但是知道這兩個就足以計算分解 $ N $ . 一種機率計算算法 $ p,q $ 從 $ e,d $ 是在最初的 RSA 論文中，後來 Alexander May 在Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring 中展示了一種確定性的方法來做同樣的事情。

所以最後，Alice 可以計算分解 $ p,q $ ，然後她也可以向所有其他接收者閱讀消息。

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