Điểm:1

Khóa riêng tốt và chống đạn cho các đường cong ECC là gì?

lá cờ it

Tôi còn khá mới đối với các chi tiết toán học cấp thấp về mật mã học, mặc dù đã làm việc trong lĩnh vực mật mã được 2,5 năm trước đó. Vì vậy, nếu tôi sai về bất kỳ phần nào bên dưới, vui lòng sửa cho tôi mà không cần dùng tay vuốt mặt;)

Hiện đã có một số cuộc thảo luận về vấn đề này cùng với các câu hỏi về khóa riêng hợp lệ cho mỗi lần nói là gì, nhưng không có câu trả lời nào trong số đó thuyết phục. Ít nhất thì tôi không đồng ý với lập luận của họ rằng bất kỳ khóa riêng hợp lệ nào cũng là khóa tốt.

ví dụ.

EdDSA (Ed25519) có bất kỳ số ngẫu nhiên nào đủ cho một khóa riêng tốt không? Có .... đã trả lời 28 oct. Frank Denis

Tất cả các khóa riêng EC có thể có đều hợp lệ không? @Fozi: 1 không tốt hơn hoặc xấu hơn 0x3b6ddba1f4b325cee4505084bc507d2019e86539f8d4be027004b69f9aa0bc74, miễn là chúng có xác suất xuất hiện bằng nhau, cụ thể là 1/n hoặc khoảng ¼1/2256, do đó, đối thủ không có xác suất thành công tốt hơn bằng cách đoán cái này hay cái kia đầu tiên. Lưu ý rằng xác suất nhận được một trong số chúng riêng lẻ là không đáng kể, giống như bất kỳ vô hướng bí mật khả thi nào khác. â Squamish Ossifrage Tạo 11 sep.

Đây là lập luận của tôi:

AFAIK, khóa công khai được tính bằng cách nhân N lần của máy phát điểm G, trong đó N là một số ngẫu nhiên được tạo dưới dạng khóa riêng.

khái niệm là quán rượu = n * G

Sau đó, đối với bất kỳ đường cong đã biết nào, tôi có thể tính toán một triệu khóa công khai dưới dạng bảng giống như cầu vồng, trong đó n nằm trong khoảng từ 1 đến 1.000.000. Điều đó sẽ chỉ chiếm không gian 32 MiB trong trường hợp đường cong 256 bit.Nếu ai đó sử dụng bất kỳ giá trị nào trong phạm vi đó để tạo khóa chung, tôi có thể dễ dàng xác định nó bằng cách so sánh nó với bảng. Trong thực tế, các vectơ kiểm tra cho một đường cong nhất định thường bắt đầu từ n = 1, 2, 3, ... ví dụ. https://crypto.stackexchange.com/a/21206/95843

Ở quy mô hoang dã hơn, ai đó có thể lưu trữ loại bảng này thậm chí là 1TiB hoặc 1PiB(ôi tiền!). Vì vậy, theo nghĩa đó, bất kỳ khóa riêng nào nhỏ hơn 2^20 hoặc thậm chí 2^50 đều không tốt!

Bây giờ, từ phép trừ trên, giới hạn dưới của khóa riêng đã được giải quyết. Nhưng có giới hạn trên không? Hoặc bất kỳ có hiệu lực số trên giới hạn dưới là tốt và đủ bằng chứng đạn?

lá cờ jp
0x3b6ddba1f4b325cee4505084bc507d2019e86539f8d4be027004b69f9aa0bc74 là một khóa riêng khá tốt và chống đạn. Bạn nên sử dụng cái đó. (đây là một trò đùa)
jjj avatar
lá cờ cn
jjj
Tại sao ai đó sẽ tạo ra một bảng như vậy? Người ta sẽ không bao giờ bẻ khóa bất kỳ khóa nào được tạo ngẫu nhiên, bởi vì rất ít khả năng chúng nằm trong phạm vi đó. Điều đó nói rằng, chúng tốt như bất kỳ khóa ngẫu nhiên nào khác
jjj avatar
lá cờ cn
jjj
Khi bạn loại trừ một triệu đầu tiên, thì Triệu thứ 2 sẽ trở thành triệu mới đầu tiên. Theo quy nạp, điều đó có nghĩa là không có chìa khóa nào tốt
Match Man avatar
lá cờ it
Cảm ơn rất nhiều cho tất cả mọi người câu trả lời và bình luận cho chủ đề này. Tôi kết thúc cuộc trò chuyện vì tôi đã có những gì tôi đang tìm kiếm.
Điểm:7
lá cờ us

Có gì đặc biệt về 1 triệu đầu tiên phím? Không phải cũng có một bảng cầu vồng nhỏ chứa các khóa trong khoảng 1M đến 2M và một bảng cầu vồng nhỏ chứa các khóa trong khoảng 2M đến 3M và một bảng cầu vồng nhỏ chứa các khóa trong khoảng 842347283958M đến 842347283959M, v.v.?

Logic tương tự khiến bạn lo lắng về các khóa nhỏ (dưới 1M) cũng có thể khiến bạn lo lắng không kém về các khóa trong không tí nào phạm vi! Bất kể tôi có chìa khóa nào, thực sự có một chiếc bàn cầu vồng nhỏ ngoài kia một vài nơi điều đó có thể cho phép ai đó dễ dàng phá khóa của tôi. Nhưng kẻ tấn công sẽ phải biết cái nào trong số $2^{236}$ trong số các bảng cầu vồng có thể (phạm vi phím) để thử!

Tôi nghĩ đó là một sai lầm khi nghĩ về một cụ thể phạm vi khóa (ví dụ: từ 0 đến 1M) có vấn đề theo một cách đặc biệt. Nếu phạm vi khóa thấp nhất đặc biệt xấu, thì quá trình tạo khóa nên tránh chúng. Nhưng sau đó tiếp theo phạm vi phím thấp nhất trở nên tồi tệ theo cùng một logic, vì vậy bạn cũng nên tránh chúng. Chuỗi logic này kết thúc mà không có khóa an toàn nào để lựa chọn.

lá cờ cn
Vấn đề có thể là nếu con người chọn `n` theo cách thủ công thì họ có xu hướng chọn các giá trị rất thấp. Tôi biết một số người có thể nhận ra hàm băm md5 của một chuỗi trống vì họ đã thấy nó quá thường xuyên. Sẽ không ngạc nhiên nếu một số người làm việc nhiều với tiền điện tử có thể nhận ra một số khóa luôn được sử dụng trong các ví dụ.
Match Man avatar
lá cờ it
Bởi vì nó rất dễ dàng để tìm ra. Và rẻ. Ngoài ra, nhờ một số "chuyên gia" trong lĩnh vực bảo mật tuyên bố rằng 0 hoặc 1 an toàn hơn như 0x3b6ddba1f4b325cee4505084bc507d2019e86539f8d4be027004b69f9aa0bc74 nên ai đó sẽ sử dụng chúng làm số "ngẫu nhiên" bằng chứng đạn để tạo khóa chung của họ. Và một bên có khả năng có thể quét tất cả khóa công khai để xem liệu ai đó "may mắn" sử dụng một số ngẫu nhiên quá nhỏ để tạo ra nó hay không. Các quy tắc tương tự cũng áp dụng cho lý do tại sao `123456` hoặc ngày sinh của bạn không phải là một mật khẩu tốt. Vì tất cả chúng đều rất dễ dùng thử.
lá cờ us
Bảo mật không phải là thuộc tính nội tại của khóa *cụ thể*. Nó xuất phát từ *quy trình* chọn khóa. Nếu bạn có quy trình phù hợp, thì tất cả những lo lắng này sẽ biến mất.
Match Man avatar
lá cờ it
>Chuỗi logic này kết thúc mà không có chìa khóa an toàn nào để lựa chọn.
Match Man avatar
lá cờ it
Thứ hai, chuỗi không lặp lại vô hạn do giới hạn lưu trữ. Giới thiệu https://theconversation.com/the-worlds-data-explained-how-much-were-producting-and-where-its-all-stored-159964#:~:text=In%202018%2C%20the% 20total%20amount,One%20zettabyte%20is%208%2C000%2C000%2C000%2C000%2C000%2C000%2C000%20bits., đến năm 2020 có 59 kho lưu trữ ZB trên thế giới. Sau đó, * gần như * không thể lưu trữ bảng 590 ZB, ngay cả khi được cung cấp bởi công nghệ nén. Theo nghĩa đó, một số ngẫu nhiên lớn hơn 590 ZB được coi là an toàn chống đạn. Đó là hơn 2^82.
Match Man avatar
lá cờ it
Đó là hơn 2^82.... Nhưng nó vẫn còn tương đối nhỏ so với toàn bộ không gian khóa như 2^256 hoặc 2^512.
lá cờ us
Vì vậy, bất kỳ khóa nào trên $2^{82}$ đều là "an toàn chống đạn". Sau đó, bạn có đề xuất có một quy trình tạo khóa loại trừ hoàn toàn các khóa
Match Man avatar
lá cờ it
Không, vấn đề là bất cứ ai cũng có thể chọn một phạm vi mà anh ta cho là đủ an toàn. Và một nhóm có khả năng, hay nói một kẻ săn mồi chỉ đuổi theo mục tiêu dễ dàng nhất.
Điểm:2
lá cờ ng

Câu hỏi đúng là bất kỳ khóa riêng nào nhỏ hơn 250 có thể được tìm thấy từ khóa chung và phương pháp mà nó mô tả sẽ khả thi. Tuy nhiên

  • Có nhiều phương pháp tốt hơn, có thể tìm thấy khóa ít hơn k2 với nỗ lực tỷ lệ thuận với k (ví dụ. Pollard'd rho) và ít bộ nhớ, với xác suất khá lớn. Như vậy 250 hoạt động là đủ để tìm một khóa nhỏ hơn 2100 với xác suất khá lớn.
  • 250 là một con số nhỏ đối với một số hoạt động để phá vỡ tiền điện tử. Vào những năm 1970, NSA đồng ý rằng DES có 256 phím, bởi vì họ biết rằng họ có thể phá vỡ điều đó nếu cần thiết. Đến năm 2000, mức cơ sở cho an ninh là 280. Đường cơ sở hiện đại có thể là 296, và thực hành cho các hệ thống mới theo thứ tự 2128 hoặc hơn. Đó là trước khi bình phương để giải thích cho các cuộc tấn công ở trên.

có giới hạn trên không?

Đúng. Đối với mọi phương pháp và đường cong chữ ký dựa trên Đường cong Elliptic, có một bộ quy định cho các khóa riêng. Vì ECDSA, đó là khoảng [1, N-1] ở đâu N là thứ tự của trình tạo (không phải là N trong câu hỏi). Giá trị của N phụ thuộc vào đường cong. cho đường cong secp256k1, N thấp hơn 2 một chút256. Do đó, nỗ lực dự kiến ​​để tìm khóa riêng bằng khóa chung bằng Pollard's rho (hoặc bất kỳ phương pháp đã biết nào khác) là theo thứ tự 2128 hoạt động (bổ sung trên Elliptic Curve), hoặc nhiều hơn nữa.

Nếu vượt quá giới hạn trên, khóa riêng tư sẽ bị phần mềm tuân thủ từ chối. Nếu nó không bị từ chối và phần mềm hoạt động chính xác từ quan điểm toán học và đối với các hệ thống chữ ký trong đó khóa riêng trực tiếp là thứ nhân trình tạo để tạo thành khóa chung (như trong câu hỏi và ECDSA), khóa sẽ hoạt động như nếu nó được giảm modulo N (thứ tự của trình tạo), cả để tạo khóa chung và ký.

Quy tắc tạo khóa riêng phụ thuộc vào hệ thống chữ ký; ví dụ. Ed25519 chỉ định một khoảng trống cho khóa riêng lớn hơn nhiều so với N, để cải thiện khả năng chống lại một số cuộc tấn công (nhưng không tìm thấy khóa riêng tạo chữ ký hợp lệ).


Loại bỏ các khóa có thể theo cách mà đối thủ đã biết giảm bảo mật, bởi vì đối thủ có ít khóa hơn để kiểm tra. Của nó chịu được để loại bỏ một vài phím có thể. Nó không phải là mong muốn trong bất kỳ cách nào.

Cách thông thường/được đề xuất/tốt nhất để chọn khóa riêng là ngẫu nhiên đều trong tập hợp các giá trị khóa riêng hợp lệ. Có thể chấp nhận loại trừ một số giá trị (chẳng hạn như giá trị nhỏ như trong câu hỏi), nhưng điều đó chỉ miễn là chỉ một phần nhỏ giá trị bị từ chối. Ví dụ. đối với ECDSA trên secp256k1, bạn có thể từ chối các khóa riêng nhỏ hơn 2192, bởi vì điều đó chỉ loại bỏ một tỷ lệ rất nhỏ khoảng 2-64 (0,000000000000000005%) của không gian khóa. Nhưng điều đó cũng vô nghĩa, bởi vì rất khó có khả năng một trong những khóa bị loại trừ được tạo ra. Và việc tăng giới hạn dưới để tỷ lệ này trở nên không đáng kể sẽ làm giảm đáng kể sự lựa chọn khóa của chúng ta, cho phép thuật toán tìm kiếm khóa được thiết kế đặc biệt tìm thấy nó dễ dàng hơn so với lựa chọn ngẫu nhiên thống nhất.

Khóa riêng ECDSA trên secp256k1 có thể được tạo bằng cách cuộn một xúc xắc lục giác 64 lần (nếu 23 lần ném đầu tiên đều có giá trị như nhau, hãy hỏi xúc xắc và dừng lại). Sử dụng trung thực 64 kết quả, theo thứ tự lớn-endian. Kết quả là một khóa riêng hợp lệ (thử nghiệm chúng tôi đã thực hiện đảm bảo kết quả nằm trong khoảng thời gian thích hợp).

Match Man avatar
lá cờ it
Cảm ơn rất nhiều vì đã chia sẻ những hiểu biết của bạn về chủ đề này. Có 2^128 là một con số hợp lý, nếu xem xét một bên "có năng lực" hơn một cá nhân dân sự.Nhưng nói về giới hạn trên của khóa "tốt", câu hỏi của tôi là nếu bất kỳ khóa đủ lớn hợp lệ nào cũng là khóa tốt, nghĩa là không có giới hạn trên giữa khóa tốt lớn nhất có thể và khóa hợp lệ lớn nhất. ví dụ. toàn bộ diện tích của không gian khóa giống như: [khóa bí mật hợp lệ ít nhất,2^128] ⪠[2^128+1, (phạm vi khóa tốt) , khóa tốt lớn nhất] ⪠[khoảng trống, khóa hợp lệ lớn nhất] â ª [khóa không hợp lệ...]
fgrieu avatar
lá cờ ng
@MatchMan: loại bỏ các khóa có thể có theo cách mà bảo mật _decreases_ của đối thủ đã biết, bởi vì đối thủ có ít khóa hơn để kiểm tra. Có thể _tolerable_ để loại bỏ một số khóa có thể. Nó không phải là mong muốn trong bất kỳ cách nào.
Match Man avatar
lá cờ it
Cảm ơn, nó thực sự rõ ràng đối với tôi bây giờ.
lá cờ id
@fgrieu: Nếu một khóa đang tạo nhiều khóa và ví dụ:. 1% trong số chúng có thể được kiểm tra brute-force rẻ hơn 10% (chi phí *cho mỗi ứng viên*) so với phần còn lại, sau đó kẻ tấn công sẽ có thể tìm kiếm 1% không gian khóa chỉ với 0,9% nỗ lực cần thiết để tìm kiếm tất cả. Nếu một người tạo đủ khóa mà ít nhất một số có khả năng nằm trong 1% đó, thì điều này sẽ giảm khoảng 10% nỗ lực tìm kiếm ít nhất một khóa của kẻ tấn công. Ngược lại, loại trừ 1% khóa đó sẽ chỉ giảm 1% nỗ lực cần thiết của kẻ tấn công.
fgrieu avatar
lá cờ ng
@supercat: Tìm kiếm khóa trong ECC (hoặc DSA hoặc RSA) không phải bằng cách quét vùng phím. Ed25519 có các khóa $>2^{252}$ và việc quét thậm chí 0,00â¦01% (trong đó ⦠thay thế 40 số 0) trong số đó là ngoài tầm với với tất cả nỗ lực lãng phí trong khai thác bitcoin. Các cuộc tấn công ít khả thi hơn tồn tại, tấn công trực tiếp vào các khóa công khai. Trái ngược với tiền điện tử đối xứng đôi khi và RSA ở mức độ thấp hơn nhiều, việc tấn công đồng thời nhiều khóa ECC dường như không làm cho việc phá vỡ một khóa dễ dàng hơn. Và tôi không thấy rằng có những loại khóa khá lớn (1%) có thể bị tấn công nhanh hơn nhiều (-10%) so với những loại khác.
lá cờ id
@fgrieu: Câu trả lời của tôi liên quan đến khái niệm chung rằng người ta không thể xác định số lượng khóa "có vấn đề" đủ rộng để người ta có thể vô tình đánh trúng một phím, mà không quá rộng đến mức loại trừ chúng sẽ làm giảm không gian phím brute-force. Điều đó hoàn toàn đúng đối với các hệ thống mật mã trong đó xác suất nhấn phím "xấu" thực tế không thể phân biệt được với 0, nhưng tôi không nghĩ nó sẽ đúng đối với các hệ thống mật mã mà nó không đúng một cách rõ ràng.

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