โครงการ IBE ที่ใช้ RSA นี้ปลอดภัยหรือไม่

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 < อี < \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{กรณี} \{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{กรณี} \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}$ กับ \begin{align*} (e H(ID)) d_{ID} \equiv 1 \text{ mod } \phi(n) \end{จัดตำแหน่ง*}

เมื่อ Bob ต้องการเข้ารหัสข้อความ $m \in \mathbb{Z} / N \mathbb{Z}$, เขาทำ $\texttt{params}$ และคำนวณ \begin{align*} c \equiv m^{e H(ID)} \text{ mod } N \end{จัดตำแหน่ง*}

อลิซถอดรหัสข้อความรหัสนี้ $ค$ กับ \begin{align*} m \equiv c^{d_{ID}} \text{ mod } N \end{จัดตำแหน่ง*}

ตัวอย่าง

1. $p = 1010231362240711373894507355467 \ใน \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 \ใน 8:b_i \ใน \{0,1\}$. เลือก $H$ เช่น: \begin{align*} 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{กรณี} \end{จัดตำแหน่ง*}

พารามิเตอร์ที่เปิดเผยต่อสาธารณะคือ \begin{align*} \texttt{params} &= \langle 1078282205, 801859248185081566400631735533731882269717325788593134781503, H \rangle \end{จัดตำแหน่ง*} เดอะ $\texttt{มาสเตอร์คีย์}$ เป็น \begin{align*} \phi(N) &= 801859248185081566400631735531927912682594599964055691839128 \end{จัดตำแหน่ง*}

PKG ใช้เวลานั้น $ID = 01101111$ เป็น ID ของผู้ใช้ "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 เขาคำนวณ \begin{align*} c &\equiv 3463463463463424234234234^{17887577132610185} \text{ mod N} \ &\equiv 353097511425650359803351296367609508451542189692844760010085 \text{ mod N} \end{จัดตำแหน่ง*}

ผู้ใช้ "o" ถอดรหัสข้อความเข้ารหัสด้วย: \begin{align*} m &\equiv 353097511425650359803351296367609508451542189692844760010085^{D_{ID}} \text{ mod N} \ &\equiv 3463463463463424234234234 \text{ mod N} \end{จัดตำแหน่ง*}

ไม่มันไม่ใช่.

อลิซรู้ตัวเอง $eH(รหัส)$ และเธอรู้รหัสส่วนตัวที่เกี่ยวข้อง แต่การรู้ทั้งสองนี้ก็เพียงพอที่จะคำนวณการแยกตัวประกอบของ $N$. อัลกอริทึมความน่าจะเป็นในการคำนวณ $p,q$ จาก $e,d$ อยู่ในกระดาษต้นฉบับของ RSA ต่อมา Alexander May ปรากฏตัว การคำนวณรหัสลับ RSA นั้นถูกกำหนดไว้แล้ว เวลาพหุนามเทียบเท่ากับการแยกตัวประกอบ วิธีการกำหนดที่จะทำเช่นเดียวกัน

ในที่สุดอลิซก็สามารถคำนวณการแยกตัวประกอบได้ $p,q$จากนั้น เธอก็สามารถอ่านข้อความไปยังผู้รับคนอื่นๆ ทั้งหมดได้เช่นกัน