Điểm:1

Crypto

Lỗ hổng RSA khi M được mã hóa không đồng nguyên tố với N

Chen

00:27, 04/07/2023

Tôi đã thử nghiệm với một vài trường hợp thử nghiệm, có vẻ như bản mã $M^e$ của RSA luôn nguyên tố cùng nhau với N khi e=3. Có một lý do tại sao? Điều gì sẽ xảy ra nếu bản mã $M^e$ không nguyên tố cùng nhau với M khi e=3?

120

0 + 0

fgrieu

07:00, 04/07/2023

Khi $(N,e)$ là một khóa công khai RSA hợp lệ với $N$ là tích của hai số nguyên tố bí mật riêng biệt $p$ và $q$, thì có khả năng khoảng $1/p+1/q$ là một thông báo ngẫu nhiên $M $ sao cho $M^e$ không nguyên tố cùng nhau với $N$. Vì cả $p$ và $q$ đều phải lớn (hàng trăm chữ số thập phân) để RSA an toàn, xác suất đó hoàn toàn không đáng kể trong việc sử dụng RSA thực tế. Câu hỏi đang xem xét điều gì đó mà trong thực tế sử dụng sẽ không xảy ra đối với $M$ ngẫu nhiên hoặc giả ngẫu nhiên hoặc đối với $M\in[1,N)$ được chọn bởi một người không biết (cũng không thể tìm thấy) hệ số của $N$ .

Hồi đáp

kelalaka

19:57, 04/07/2023

RSA là một hoán vị cửa sập. Điều này ngụ ý bạn bất cứ điều gì?

Hồi đáp

Điểm:3

Crypto

meshcollider

00:46, 04/07/2023

Khi nào $N = pq$ là tích của hai số nguyên tố, hai số duy nhất không nguyên tố cùng nhau $N$ là những cái có chứa một trong hai $p$ hoặc $q$ như một yếu tố. Chắc chắn là có thể có $M^3$ chia hết cho một trong hai $p$ hoặc $q$ vì vậy quan sát của bạn là không đúng sự thật nói chung. Một ví dụ:

$$ M = 42\ N = 7*13 = 91\ M^3 \equiv 14 \pmod{91} $$ Rõ ràng 14 và 91 không nguyên tố cùng nhau - cả hai đều có chung $7$ như một yếu tố. Tính toán GCD của $c = M^3$ và $N$ do đó rò rỉ $7$ như một yếu tố của $N$, phá vỡ RSA.

0 + 0

Chen

16:56, 04/07/2023

Ok, tôi đã không nghĩ về điều này.Trong trường hợp đó, đó là một lỗ hổng bảo mật nghiêm trọng, vì bằng cách lấy GCD của bản mã (C) và N rò rỉ p hoặc q?

Hồi đáp

Chen

17:23, 04/07/2023

Việc sử dụng OAEP trên C không đồng nguyên tố với N có giải quyết được sự cố không?

Hồi đáp

fgrieu

17:34, 04/07/2023

@Chen: Tôi không hiểu ý của bạn khi "sử dụng OAEP trên C"; nhưng việc sử dụng OAEP để tạo đầu vào $M$ cho mã hóa RSA thô $M\mapsto C=M^e\bmod N$ để bảo mật $N$ trên thực tế chắc chắn sẽ "giải quyết vấn đề", nếu có. Giờ đây, chúng tôi có thể mã hóa bội số của $p$ hoặc $q$ một cách an toàn. Một lần nữa, ngay cả khi không sử dụng OAEP, cũng không có vấn đề thực tế nào, bởi vì việc chọn $M$ hoặc $C$ trong $[1,n)$ với $\gcd(C,N)\ne1$ là không thể đối với một người không biết ( cũng không thể tìm thấy) thừa số của $N$.

Hồi đáp

Chen

17:48, 04/07/2023

Xin lỗi, ý tôi là sử dụng OAEP trên M. Ý của bạn là không thể chọn một M có mục đích mang lại $gcd(C,N)– 1$ nếu không biết p và q?

Hồi đáp

Chen

18:04, 04/07/2023

và tại sao điều đó là không thể? Nó vẫn có thể xảy ra với xác suất thành công là 1/p + 1/q chứ?

Hồi đáp

meshcollider

20:23, 04/07/2023

@Chen sẽ không khác gì kẻ tấn công chỉ đoán các yếu tố ngẫu nhiên của $N$ :)

Hồi đáp

poncho

21:17, 04/07/2023

@Chen: đối với $p, q$ có kích thước thực tế, nghĩa là $2^{-1024}$ hoặc nhỏ hơn, $1/p + 1/q$ thực sự là "không thể"

Hồi đáp

Phan Văn Trường

Câu hỏi này là trong các ngôn ngữ khác:

EN: RSA Vulnerability when the Encrypted M is not coprime with N

TH: ช่องโหว่ RSA เมื่อ M ที่เข้ารหัสไม่ได้อยู่ร่วมกับ N

RO: Vulnerabilitatea RSA atunci când M criptat nu este coprime cu N

RU: Уязвимость RSA, когда зашифрованное M не взаимно просто с N

VI: Lỗ hổng RSA khi M được mã hóa không đồng nguyên tố với N

Đă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.