# Is this RSA-based IBE Scheme secure?

The PKG performs the following steps

1. Choose $$p,q \in \mathbb{P}$$.
2. Calculate $$N=pq$$.
3. Calculate $$\phi (n)=(p-1)(q-1)$$.
4. Choose $$e$$ with $$gcd(e,\phi(n))=1$$ and $$1 < e < \phi(n)$$.
5. Let it be $$e = {p^{e_1}_1} \cdot {p^{e_2}_2} \cdot \ldots {p^{e_k}_k}$$ the prime factorization of $$e$$ for $$i \in k:p_i \in \mathbb{P},e_i \in \mathbb{N}$$. Choose an injective mapping $$H$$ with \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*}

and $$eH(ID)<\phi(n)$$ for $$i \in \mathbb{n}$$. The publicly available parameters are $$\texttt{params} = \langle e, N, H \rangle$$ and the $$\texttt{master-key}$$ is $$\phi(n) \in \mathbb{Z} / N \mathbb{Z}$$.

The PKG takes then an $$ID \in \{0,1\}^{*}$$ (from Alice) and calculates the corresponding Secret Key $$d_{ID}$$ with \begin{align*} (e H(ID)) d_{ID} \equiv 1 \text{ mod } \phi(n) \end{align*}

When Bob wants to encrypt a message $$m \in \mathbb{Z} / N \mathbb{Z}$$, he takes $$\texttt{params}$$ and calculates \begin{align*} c \equiv m^{e H(ID)} \text{ mod } N \end{align*}

Alice decrypts this ciphertext $$c$$ with \begin{align*} m \equiv c^{d_{ID}} \text{ mod } N \end{align*}

EXAMPLE

1. $$p = 1010231362240711373894507355467 \in \mathbb{P}$$ and
$$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. It apllies $$ID \in \{0,1\}^8$$ with $$ID=\langle b_1,b_2,\ldots,b_8 \rangle$$ for $$i \in 8:b_i \in \{0,1\}$$. Choose $$H$$ as: \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*}

The publicly available parameters are \begin{align*} \texttt{params} &= \langle 1078282205, 801859248185081566400631735533731882269717325788593134781503, H \rangle \end{align*} The $$\texttt{master-key}$$ is \begin{align*} \phi(N) &= 801859248185081566400631735531927912682594599964055691839128 \end{align*}

The PKG takes then $$ID = 01101111$$ as the ID of user "o". Then $$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$$ and $$d_{ID}=308315206989333722335381678529602981822693965290742774973561$$.

User "i" wants now to encrypt the message 3463463463463424234234234. He calculates \begin{align*} c &\equiv 3463463463463424234234234^{17887577132610185} \text{ mod N} \\ &\equiv 353097511425650359803351296367609508451542189692844760010085 \text{ mod N} \end{align*}

User "o" decrypt the ciphertext with: \begin{align*} m &\equiv 353097511425650359803351296367609508451542189692844760010085^{D_{ID}} \text{ mod N} \\ &\equiv 3463463463463424234234234 \text{ mod N} \end{align*}

• Is it the same $e$ in 4 and 5? And also, in 5, does $i\in k$ mean $i\in[1,…,k]$?
– fgrieu
Oct 7 '21 at 12:02
• Yes it is, in 5) it is just the prime factorization of $e$. And yes it does, it is used for the representation of the prime factorization. Oct 7 '21 at 12:04

Problem is that Alice, knowing $$d_{ID}$$ and $$e_{ID}$$, can compute $$f=d_{ID}\cdot e_{ID}-1$$ which is a multiple of both $$p-1$$ and $$q-1$$; then from $$N,f$$ can efficiently factor $$N$$ using the algorithm detailed here; and then can computes $$d_{ID}$$ for any $${ID}$$, and thus decipher the normal way.
Alice knows her own $$eH(ID)$$ and she knows the corresponding private key. But knowing those two is enough to calculate the factorization of $$N$$. A probailitstic algorithm to calculate $$p,q$$ from $$e,d$$ was in the original RSA paper, later and Alexander May showed in Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring a deterministic way to do the same.
So in the end, Alice can just compute the factorization $$p,q$$, and then she is able to read messages to all other receivers as well.