Рейтинг:2

Безопасна ли эта схема IBE на основе RSA?

флаг tv

PKG выполняет следующие шаги

  1. выберите $p,q \in \mathbb{P}$.
  2. Рассчитать $N=pq$.
  3. Рассчитать $\фи (n)=(p-1)(q-1)$.
  4. выберите $е$ с $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}$ первичная факторизация $е$ за $i \in k:p_i \in \mathbb{P},e_i \in \mathbb{N}$. Выберите инъективное отображение $Ч$ с \начать{выравнивать*} H &: \begin{случаи} \{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{случаи} \конец{выравнивание*}

и $eH(ID)<\phi(n)$ за $i \in \mathbb{n}$. Общедоступные параметры $\texttt{params} = \langle e, N, H \rangle$ и $\texttt{мастер-ключ}$ является $\phi(n) \in\mathbb{Z} / N \mathbb{Z}$.

Затем PKG принимает $ID \in \{0,1\}^{*}$ (от Алисы) и вычисляет соответствующий секретный ключ $d_{ID}$ с \начать{выравнивать*} (e H(ID)) d_{ID} \equiv 1 \text{ mod } \phi(n) \конец{выравнивание*}

Когда Боб хочет зашифровать сообщение $m \in \mathbb{Z} / N \mathbb{Z}$, он берет $\texttt{параметры}$ и вычисляет \начать{выравнивать*} c \equiv m^{e H(ID)} \text{ mod } N \конец{выравнивание*}

Алиса расшифровывает этот зашифрованный текст $с$ с \начать{выравнивать*} m \equiv c^{d_{ID}} \text{модуль} N \конец{выравнивание*}


ПРИМЕР

  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{случаи} \{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{случаи} \конец{выравнивание*}

Общедоступные параметры \начать{выравнивать*} \texttt{params} &= \langle 1078282205, 801859248185081566400631735533731882269717325788593134781503, H \rangle \конец{выравнивание*} $\texttt{мастер-ключ}$ является \начать{выравнивать*} \фи(N) &= 801859248185081566400631735531927912682594599964055691839128 \конец{выравнивание*}

Затем PKG принимает $ID = 01101111$ как идентификатор пользователя "o". затем $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. Он вычисляет \начать{выравнивать*} c &\equiv 3463463463463424234234234^{17887577132610185} \text{mod N} \ &\equiv 353097511425650359803351296367609508451542189692844760010085 \text{mod N} \конец{выравнивание*}

Пользователь «o» расшифровывает зашифрованный текст с помощью: \начать{выравнивать*} m &\equiv 353097511425650359803351296367609508451542189692844760010085^{D_{ID}} \text{mod N} \ &\equiv 3463463463463424234234234 \text{mod N} \конец{выравнивание*}

fgrieu avatar
флаг ng
Это одно и то же $e$ в 4 и 5? А также в 5 означает ли $i\in k$ $i\in[1,…,k]$?
marius avatar
флаг tv
Да, в 5) это просто простая факторизация $e$. И да, он используется для представления простой факторизации.
Рейтинг:5
флаг ng

Нет, это не безопасно.

Проблема в том, что Алиса, зная $d_{ID}$ и $e_{ID}$, может вычислить $f=d_{ID}\cdot e_{ID}-1$ что кратно обоим $p-1$ и $q-1$; затем из $N,f$ может эффективно учитывать $N$ по подробному алгоритму здесь; а затем может вычислить $d_{ID}$ для любой ${ID}$, и, таким образом, расшифровать обычным способом.

Рейтинг:3
флаг cn

Нет, это не так.

Алиса знает свое $eH(ID)$ и она знает соответствующий закрытый ключ. Но знания этих двух достаточно, чтобы вычислить факторизацию $N$. Вероятностный алгоритм расчета $р,к$ от $е,д$ был в оригинальной газете RSA, позже и Александр Мэй показал в Вычисление секретного ключа RSA является детерминированным Полиномиальный временной эквивалент факторинга детерминированный способ сделать то же самое.

Итак, в конце концов, Алиса может просто вычислить факторизацию $р,к$, а затем она также может читать сообщения всем другим получателям.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.