Thông thường RSA sử dụng số mũ mã hóa $e$ với $\gcd(e,\phi(N))=1$.
Cái này câu hỏi cho thấy lý do tại sao cần phải như vậy: Đối với $\ne1$ có thể tồn tại không có số mũ giải mã $d$ bởi vì khác $m'\ne m$ có thể tồn tại với $m^e \equiv (m')^e \bmod N$.
Tuy nhiên nếu chúng tôi sản xuất của chúng tôi $m$ Thích:
$$m = m_0^{e} \mod N$$
hoặc tổng quát hơn
$$m = m_0^{e^{r_1}\cdot r_2} \mod N \tag{I}$$
Chúng tôi luôn có thể (ngoại trừ một số trường hợp đặc biệt mà chúng tôi bỏ qua ở đây) tìm số mũ giải mã $d$ vì $c \equiv m^e \mod N$
$$d \equiv e^i \equiv e^{\phi(\phi(N))-1} \mod \phi(N)$$
với
$$c^d \equiv (m^{e})^d \equiv m^{\displaystyle e^1\cdot e^{{\phi(\phi(N))-1}}} \equiv m^ {\displaystyle e^{{\phi(\phi(N))}}} \equiv m \mod N$$
Tất nhiên tin nhắn này $m$ không thể truyền nhiều thông tin mục tiêu. Một số thông tin bit thấp có thể được truyền bằng cách tạo ngẫu nhiên $m$ cho đến khi các bit đầu tiên mang thông tin đích. Không hiệu quả chút nào nhưng điều đó không quan trọng ở đây.
Câu hỏi đặt ra là liệu kẻ thù có dễ dàng hơn (nhiều) để tìm ra số mũ giải mã không $d$ cho như vậy $e$?
Nếu $\gcd(e,\phi(N))\gg 1$ được biết đến thừa số của $N$ có thể trở nên dễ dàng hơn nhiều và với điều này sẽ phá vỡ tính bảo mật của RSA.
Q1: Nhưng điều gì xảy ra nếu $\gcd(e,\phi(N))\gg 1$ Là không phải được biết đến? Để đảm bảo rằng chúng tôi chọn một $e$ mà là khó để yếu tố hóa.
Có một kẻ thù vẫn là một lợi thế lớn của việc chỉ cần biết $\gcd \ne1$ ?
Nó có thể phụ thuộc rất nhiều vào các yếu tố được lựa chọn.
Chúng tôi giả sử ở đây (trường hợp sử dụng mục tiêu)
$$N = P \cdot Q$$
$$P = 2 \cdot p_s \cdot p_b +1$$
$$Q = 2 \cdot q_s \cdot q_b +1$$
$$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b$$
$$e = (2^2 \cdot p_b \cdot q_b) \cdot e_b > 2^{3000} \text{ (khó phân tích thành thừa số)}$$
$$\gcd(e,\phi(N))=2^2\cdot p_b \cdot q_b = 2^2\cdot (2\cdot 3\cdot b_0+1) \cdot (2\cdot 3\cdot q_0 +1) = B$$
$$B > 2^{2000} \text{ (khó phân tích thành thừa số)}$$
$$\phi(\phi(N)) = 2^3 \cdot 3^2 \cdot \phi(p_s) \cdot \phi(q_s) \cdot (q_0\cdot b_0)$$
$$\phi(p_s) \cdot \phi(q_s) /4= S \approx 2^{200} \ll B$$
(trong trường hợp sử dụng mục tiêu $p_s,q_s$ có hình thức $p_s = 2\cdot p_1\cdot p_2 \cdot p_3+1$)
(tất cả các thừa số nguyên tố biến là duy nhất)
$e$ cần phải là một hình vuông của một modulo gốc nguyên thủy $p_s$ và $q_s$.
Với điều này chúng ta có thể sản xuất $S$ các giá trị khác nhau với $m^{e^i} \bmod N$. Tùy thuộc vào bắt đầu $m$ chúng tôi nhận được 4 tập hợp khác nhau có kích thước đó (cộng với một số trường hợp đặc biệt nhỏ hơn mà chúng tôi bỏ qua ở đây).
Yếu tố bổ sung $e_b$ là cần thiết để che giấu mối quan hệ với $\phi(N)$ và $B$. Với cái này $e\gg N$ đây.
Chúng tôi cho rằng đối thủ cũng biết $S$ bao gồm cả nó là thừa số nguyên tố.
quý 2: Câu hỏi liên quan đến trường hợp sử dụng cũng cho phép các giá trị mục tiêu $n\ne m$ nhưng được tạo ra như $(\text{I})$ (và được biết là có một giải pháp):
Liệu đối thủ có thể tìm thấy $i$ Trong $n\equiv m^{e^i} \bmod N$ với đã biết $e,n,m,N,S$ nhanh hơn so với $O(p_s + q_s) \approx O(\sqrt{S})$?
Điều này có thể đạt được bằng cách tìm ra giải pháp cho $j,k$ Trong $n^{\displaystyle p_s} \equiv (m^{\displaystyle {p_s}})^{e^j} \bmod N$ và $n^{\displaystyle q_s} \equiv (m^{\displaystyle {q_s}})^{e^k} \bmod N$ với thử nghiệm từng bước. Bước khổng lồ không thể được thực hiện như $\phi(N)$ chưa biết và $e^{2^{50}}$ quá lớn để tính toán mà không có nó. Hoặc nó có thể được thực hiện nhanh hơn?
(đồ chơi)-Ví dụ:
Đây $p_b,q_b < p_s,q_s$ được sử dụng. Trong trường hợp sử dụng mục tiêu, chúng sẽ là $p_b,q_b \gg p_s,q_s$ (và tất cả các giá trị lớn hơn nhiều)
$N=P\cdot Q = 6565236619157488809896588016937$
$P = 2 \cdot p_s \cdot p_b +1 = 2500987802965403$
$Q = 2 \cdot q_s \cdot q_b +1 = 2625057431856779$
$p_b = 2 \cdot 3 \cdot p_0 = 2 \cdot 3 \cdot 4547= 27283$
$p_s = 2 \cdot p_1 \cdot p_2 \cdot p_3 + 1 = 2 \cdot 2579\cdot 2963\cdot 2999 + 1=45834178847$
$q_b = 2 \cdot 3 \cdot q_0 = 2 \cdot 3 \cdot 4007= 24043$
$q_s = 2 \cdot q_1 \cdot q_2 \cdot q_3 + 1 = 2 \cdot 2819\cdot 3023\cdot 3203 + 1=54590887823$
$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b = 6565236619157483683851353194756$
$\phi(\phi(N))=2^5\cdot3^2 \cdot p_0\cdot p_1\cdot p_2 \cdot p_3\cdot q_0\cdot q_1\cdot q_2\cdot q_3$
$\phi(\phi(N)) = 3282361465954844745126356151456$
số mũ $e,d$ chỉ có một yếu tố lớn bổ sung duy nhất để làm cho quá trình phân tích trở nên khó khăn.
$e = 3681846424601561452716738001396 = 2^2 \cdot p_b \cdot q_b \cdot 1403217197574083942221 $
$d = 1568810657844451193145575929268 = 2^2 \cdot p_b \cdot q_b \cdot 597901661545558066493 $
Đây $B<S$ nhưng trong trường hợp sử dụng mục tiêu $B \gg S$
$S = p_1\cdot p_2\cdot p_3\cdot q_1\cdot q_2\cdot q_3 = 625532128948867853353$
$B = 2^2 \cdot p_b \cdot q_b = 2^2 \cdot 27283 \cdot 24043=2623860676$
Đối thủ sẽ biết $N$,$e$,$S$ bao gồm cả yếu tố hóa của $S$. Nhưng anh ấy không biết phân tích thừa số của $N,e,B$.
