Tham gia Đăng nhập
Điểm:0
Cryptomathician avatar Crypto

RSA: tại sao $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{ mod}~ \varphi(n)$ giữ cho một cài đặt cụ thể của RSA

lá cờ in
Cryptomathician

Để cho $p,q$ là số nguyên tố và $n = pq$ như trong mọi cài đặt RSA và hiện sử dụng ngẫu nhiên $e$ chứa các thuộc tính sau

  • $gcd(e, \phi(n)) \neq 1$
  • $(e^{-1} ~\text{mod} ~\phi(n))^{4}\cdot3 < n$
  • $e^{-1} ~\text{mod} ~\phi(n) < \sqrt[3]{n}$ (căn bậc hai số nguyên), trong đó $\sqrt[3]{n} \in \mathbb{Z}$

ở đâu $\phi$ là hàm totient của euler. Cái này $e$ được sử dụng làm số mũ công khai cho khóa công khai và $d$ là số mũ riêng cho khóa riêng.

Nhớ lấy $\phi(n) | biên tập - 1$, như $ed = 1 + k \cdot \phi(n)$ Giữ cho $k \in \mathbb{Z}$. Câu hỏi đặt ra là, tại sao nó giữ như vậy $$(e^{-1} ~\text{mod}~ n \cdot \phi(n)) ~\text{mod}~ \ \phi(n) = e^{-1} ~\text{mod }~ \phi(n)\text{?}$$ Ai đó có thể giải thích nó bằng toán học hoặc đưa ra bằng chứng tại sao điều đó đúng không?

Một câu hỏi liên quan đến nhiều $\phi(n)$ được hỏi trong này câu hỏi. Thật không may, tôi không hiểu mối quan hệ giữa bội số của $\phi(n)$, các $gcd$ và tại sao phương trình này $ed = 1 ~\text{mod}~ k \cdot \phi(n)$ nắm giữ $ed = 1 ~\text{mod}~ \phi(n)$ vì $k \in \mathbb{Z}$.

Ngoài ra, thật tuyệt khi đọc một bằng chứng cho câu hỏi liên quan về bội số của $\phi(n)$, nếu ai đó biết tại sao điều đó lại xảy ra.

85
0 + 0
poncho avatar
lá cờ my
poncho
$(e^{-1} \bmod \phi(n))^4 \cdot 3
0
Hồi đáp
Cryptomathician avatar
lá cờ in
Cryptomathician
Vâng, nó nên dễ bị tổn thương. @poncho
0
Hồi đáp
Điểm:1
poncho avatar Crypto
lá cờ my
poncho

Câu hỏi đặt ra là, tại sao nó giữ như vậy $(e^{â1} \bmod n \cdot \phi(n)) \bmod \phi(n)=e%{â1} \bmod \phi(n)$?

Trên thực tế, chúng ta có bản sắc tổng quát hơn $(A \bmod BC) \bmod C \equiv A \bmod C$, với mọi số nguyên $A, B, C$. Trong trường hợp cụ thể của bạn, chúng tôi có $A = e^{-1} \bmod \phi(n)$, $B = n$, và $C = \phi(n)$

Có thể dễ dàng nhìn thấy bản sắc tổng quát hơn này từ hai sự kiện:

$X \bmod Y = X + k \cdot Y$ cho một số nguyên $k$ (có thể là tiêu cực)

$X \bmod Y = Z \bmod Y$ nếu và chỉ nếu $X - Z = k'\cdot Y$ cho một số nguyên $k'$.

Từ thực tế đầu tiên, chúng ta có thể thấy rằng $A \bmod BC = A + kBC$ (đối với một số nguyên $k$ - chúng tôi không quan tâm số nguyên đó là gì)

Từ thực tế thứ hai, chúng ta thấy rằng $(A + kBC) \bmod C = A \bmod C$ giữ nếu chúng ta có $A + kBC - A = k'C$ cho một số nguyên $k'$; chúng ta có thể thấy ngay rằng điều này đúng cho số nguyên $k' = kB$, do đó điều này là đúng.

Vì danh tính chung có trong mọi trường hợp nên nó cũng có trong trường hợp cụ thể của bạn.

0 + 0
Cryptomathician avatar
lá cờ in
Cryptomathician
Cảm ơn. Tôi tự hỏi gcd đóng vai trò ở đâu như được đề cập trong câu trả lời "đúng" của câu hỏi liên quan trên trao đổi stackoverflow toán học. Có phải e và n nguyên tố cùng nhau ($gcd(e,n)$) để giữ danh tính đó không?
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@Cryptomathician: tốt, nếu $e$ và $n$ không nguyên tố cùng nhau, thì $e^{-1} \bmod (n \cdot \phi(n))$ sẽ không tồn tại.
1
Hồi đáp
Cryptomathician avatar
lá cờ in
Cryptomathician
OK đã nhận nó. Cảm ơn bạn đã giải thích chi tiết.
0
Hồi đáp
Cryptomathician avatar
lá cờ in
Cryptomathician
có phải là một câu hỏi khác khi tôi muốn biết khi nào $y = x^{-1} ~(\text{mod}~ k \cdot \phi(n))$ giữ, do đó $xy \equiv 1 ~( \text{mod}~ \phi(n))$ giữ một số $k \in \mathbb{Z}$ ? Tôi cũng đang cố gắng tìm hiểu xem điều này có thể xảy ra khi nào. @poncho
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@Cryptomathician: trên thực tế, nó giữ cho tất cả $k \in \mathbb{Z}$; cùng một loại logic: $y = x^{-1} \pmod{k \phi(n)}$ có nghĩa là có một $k' \in \mathbb{Z}$ với $yx = 1 + k'( k \phi(n))$; điều này ngụ ý rằng có một $k''$ với $yx = 1 + k'' \phi(n)$, nghĩa là, $yz \equiv 1 \pmod{\phi(n)}$
1
Hồi đáp
Cryptomathician avatar
lá cờ in
Cryptomathician
Được rồi, cảm ơn bạn. Tôi đã tính toán giống như bạn đã làm và muốn chắc chắn rằng tôi không mắc lỗi. Cảm ơn bạn! Có lẽ phương trình cuối cùng phải là $yx \equiv 1 ~(\text{mod}~ \phi(n))$ thay vì $yz \equiv 1 ~(\text{mod}~ \phi(n))$ phải không?
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@Cryptomathician: chính xác, $yz$ là lỗi đánh máy...
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.