2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Is it the same $e$ in 4 and 5? And also, in 5, does $i\in k$ mean $i\in[1,…,k]$? $\endgroup$
    – fgrieu
    Oct 7 at 12:02
  • $\begingroup$ 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. $\endgroup$
    – marius
    Oct 7 at 12:04
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.