it-swarm-vi.com

Số mũ công khai RSA chỉ nên ở {3, 5, 17, 257 hoặc 65537} do các cân nhắc về bảo mật?

Trong dự án của tôi, tôi đang sử dụng giá trị của số mũ công khai là 4451h. Tôi nghĩ rằng nó an toàn và ổn cho đến khi tôi bắt đầu sử dụng một thư viện mã hóa RSA thương mại. Nếu tôi sử dụng số mũ này với thư viện này, nó sẽ ném ngoại lệ.

Tôi đã liên hệ với các nhà phát triển của thư viện này và nhận được câu trả lời sau: "Tính năng này là để ngăn chặn một số cuộc tấn công vào các khóa RSA. Hậu quả là giá trị số mũ bị giới hạn ở {3, 5, 17, 257 hoặc 65537}. Việc tắt kiểm tra này là vẫn đang được điều tra, vì những rủi ro có thể rất lớn. "

Đây là lần đầu tiên trong đời tôi nghe rằng các giá trị khác ngoài {3, 5, 17, 257 hoặc 65537} được sử dụng để phá vỡ RSA. Tôi chỉ biết sử dụng 3 với phần đệm không phù hợp là dễ bị tổn thương.

Có thật vậy không? Chắc chắn, tôi có thể sử dụng một thư viện khác, nhưng sau câu trả lời như vậy tôi lo lắng về bảo mật cho giải pháp của mình.

70
Vladislav Rastrusny

Không có điểm yếu nào được biết đến đối với bất kỳ số mũ công khai ngắn hay dài nào đối với RSA, miễn là số mũ công khai là "chính xác" (nghĩa là tương đối chính với p-1 cho tất cả các số nguyên tố p mà chia mô-đun).

If bạn sử dụng số mũ nhỏ bạn không sử dụng bất kỳ phần đệm nào để mã hóa bạn mã hóa chính xác cùng một tin nhắn với Một số khóa công khai riêng biệt, sau đó tin nhắn của bạn có nguy cơ: if e = 3 và bạn mã hóa tin nhắn m bằng khóa chung n1, n2 n3, sau đó bạn có ctôi = m3 mod ntôi for i = 1 đến 3. Theo Định lý còn lại của Trung Quốc , sau đó bạn có thể xây dựng lại m3 mod n1n2n3, hóa ra là m3 (không có bất kỳ modulo nào) vì n1n2n3 là số nguyên lớn hơn. Một trích xuất gốc khối (không phải mô-đun) sau đó đủ để giải nén m.

Điểm yếu, ở đây, là không phải số mũ nhỏ; đúng hơn, đó là việc sử dụng một phần đệm không phù hợp (cụ thể là không có phần đệm nào) để mã hóa. Đệm rất quan trọng đối với bảo mật của RSA, cho dù mã hóa hay chữ ký; nếu bạn không sử dụng một phần đệm thích hợp (chẳng hạn như phần đệm được mô tả trong PKCS # 1 ), thì bạn có nhiều điểm yếu và cho đến nay, điểm yếu được nêu trong đoạn trên không phải là lớn nhất. Tuy nhiên, bất cứ khi nào ai đó đề cập đến một điểm yếu liên quan đến kích thước lũy thừa, anh ta ít nhiều trực tiếp đề cập đến sự xuất hiện này. Đó là một chút truyền thuyết cũ và không chính xác, đôi khi bị đảo ngược thành lệnh cấm đối với lớn số mũ (vì nó là một huyền thoại, huyền thoại ngược cũng là một huyền thoại và không còn nữa - và không ít - chứng minh); Tôi tin rằng đây là những gì bạn quan sát ở đây.

Tuy nhiên, người ta có thể tìm thấy một vài lý do tại sao một số mũ công cộng lớn sẽ được tránh:

  • Số mũ công cộng nhỏ phát huy hiệu quả (đối với các hoạt động khóa công khai).

  • Có vấn đề bảo mật về việc có một private số mũ; một cuộc tấn công phục hồi khóa đã được mô tả khi độ dài số mũ riêng không quá 29% chiều dài số mũ công khai. Khi bạn muốn buộc số mũ riêng ngắn (ví dụ: để tăng tốc độ hoạt động của khóa riêng), bạn ít nhiều phải sử dụng số mũ công khai lớn (lớn như mô đun); yêu cầu số mũ công khai phải ngắn sau đó có thể được xem như một loại biện pháp đối phó gián tiếp.

  • Một số triển khai RSA được triển khai rộng rãi gây nghẹt thở cho các số mũ công cộng RSA lớn. Ví dụ. mã RSA trong Windows (CryptoAPI, được Internet Explorer sử dụng cho HTTPS) nhấn mạnh vào việc mã hóa số mũ công khai trong một Word 32 bit; nó không thể xử lý khóa công khai với số mũ công khai lớn hơn.

Tuy nhiên, "rủi ro có thể rất lớn" trông giống như lời biện minh chung ("đây là vấn đề bảo mật" là cách nói thông thường "chúng tôi đã không thực hiện nó nhưng chúng tôi không muốn thừa nhận bất kỳ loại lười biếng nào").

64
Thomas Pornin

Các nhà phát triển chỉ đơn giản là không chính xác. Không có gì sai với số mũ 0x4451 (số thập phân 17,49); nó không tạo ra bất kỳ vấn đề bảo mật nào.

Từ lâu, mọi người thường nghĩ rằng số mũ nhỏ là một vấn đề, bởi vì một cuộc tấn công mà Thomas Pornin đã giải thích bằng cách gửi cùng một tin nhắn cho nhiều người nhận. Nhưng ngày nay chúng tôi hiểu rằng số mũ không liên quan gì đến nó; vấn đề là đệm không đúng. Những cuộc tấn công được ngăn chặn bằng cách sử dụng đệm đúng cách. Bất kỳ thư viện tiền điện tử nào xứng đáng với muối của nó đều tốt hơn là sử dụng phần đệm thích hợp (nếu không bạn sẽ gặp vấn đề tồi tệ hơn nhiều).

Vì vậy, không có lý do chính đáng để một thư viện tiền điện tử thẳng thừng cấm sử dụng số mũ đó.

Điều đó nói rằng, từ góc độ hiệu suất, số mũ càng nhỏ, hiệu suất càng tốt. Sự lựa chọn tốt nhất là e = 3, vì điều đó mang lại hiệu suất tốt nhất và không có vấn đề bảo mật nào được biết đến. (Trên thực tế, e = 2 thậm chí còn tốt hơn một chút. Nó còn được gọi là mã hóa Rabin. Tuy nhiên, sơ đồ đó không được biết đến nhiều và yêu cầu mã hơi khác nhau, vì vậy nó không được sử dụng rộng rãi.)

21
D.W.

Năm số đó là số nguyên tố Fermat .

Vì chúng có dạng 2 k  + 1, mã hóa là m e  = m · (( m 2)2... k lần...)2, đơn giản và nhanh hơn lũy thừa với số mũ có kích thước tương tự trong trường hợp chung .

Vì chúng là số nguyên tố, bài kiểm tra mà e là nguyên tố của ( p - 1) ( q - 1) chỉ là một thử nghiệm mà e không chia nó.

Vì vậy, điều này có nhiều khả năng về tốc độ hoặc quy ước hơn là về bảo mật. Không có gì sai với việc hiệu quả. Nhưng để chắc chắn, hãy yêu cầu một tài liệu tham khảo như câu trả lời khác được đề xuất.

Cũng xem bài này .

19
aaz

Tôi không biết bất kỳ lý do nào khiến số mũ RSA công khai chỉ nên có trong tập {3,5,17,257,65537}. Như bạn đã đề cập, các số mũ nhỏ như 3 hoặc 5 sẽ nguy hiểm hơn khi sử dụng, bởi vì các tác động tiêu cực của lỗi thực thi (như đệm không đúng cách) có thể lớn hơn. NIST chỉ cho phép số mũ công khai lớn hơn 2 ^ 16, nhưng tôi không biết lý do cho quyết định của họ.

Bạn không nên hài lòng với câu trả lời được đưa ra bởi các nhà phát triển của thư viện mà bạn sử dụng và yêu cầu một tài liệu tham khảo cụ thể. Quá thường xuyên, hóa ra một số giấy đã bị hiểu lầm. Ví dụ, tôi có thể tưởng tượng rằng một số nhà phát triển đọc Phần 4 của bài báo "Chúng ta có thể tin tưởng vào Phần mềm mật mã không? Lỗi mã hóa trong GNU Privacy Guard v1.2.3" của Phong Nguyen và đưa ra kết luận không chính xác, ví dụ như ở trên. Bài báo này thông báo rằng khi khóa công khai do GnuPG tạo ra có giá trị bất thường như 65539, thì kẻ tấn công tìm hiểu một ít thông tin về khóa bí mật. Kết luận là thuật toán tạo khóa của GnuPG có thể được cải thiện, nhưng không phải 65539 là khóa công khai xấu.

8
Accipitridae

Tôi không thể tìm thấy bất kỳ tài liệu tham khảo nào rằng các giá trị khác cho số mũ công khai là dễ bị tổn thương. Nên sử dụng số mũ công khai gần với lũy thừa 2 vì lý do hiệu suất, theo hướng dẫn RSA.com về thuật toán RSA

Theo Wikipedia , NIST không cho phép số mũ công khai nhỏ hơn 65537, vì số mũ nhỏ hơn là một vấn đề nếu chúng không được đệm đúng cách.

7
Andreas Arnold