Score:2

Is this RSA-based IBE Scheme secure?

tv flag

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*}

fgrieu avatar
ng flag
Is it the same $e$ in 4 and 5? And also, in 5, does $i\in k$ mean $i\in[1,…,k]$?
marius avatar
tv flag
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.
Score:5
ng flag

No, this is not secure.

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.

Score:3
cn flag

No, it's not.

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.