Điểm:2

Tại sao chúng ta cần mod trong thuật toán Shamir's Secret Sharing

lá cờ kr

Tôi đang xem xét thuật toán Chia sẻ bí mật của Shamir và tôi hiểu rõ cách thức hoạt động của thuật toán này nhưng tôi không hiểu lý do chính xác tại sao chúng ta cần tìm một số nguyên tố và thực hiện phép tính modulo bằng cách sử dụng số nguyên tố đó.

Trên Wikipedia, nó nói rằng nếu bạn không sử dụng số học modulo, kẻ tấn công có thể lấy một số thông tin về giá trị mà không có đủ cổ phần.

Trong Niềm vui của mật mã, có vẻ như biện minh cho sự cần thiết của số học modulo bằng cách nói rằng các hệ số đa thức cần được phân phối đồng đều trong Z, điều này không khả thi, vì vậy thay vào đó chúng tôi sử dụng Z_p khi có thể đạt được phân phối đồng đều.

Trên các trang web khác (và ở đây), tôi thấy một số người nói rằng modulo đơn giản là cần thiết để các giá trị không trở nên quá lớn.

Nói tóm lại, tôi không thể tìm ra lý do dứt khoát tại sao số học mô-đun lại thực sự cần thiết. Tất nhiên, nó có thể là sự kết hợp của tất cả các lý do được đề cập ở trên nhưng tôi thấy lạ khi thấy tất cả các nguồn này đưa ra một lời biện minh khác mà không đề cập đến các lý do khác. Vì vậy, bạn có thể giúp tôi tìm ra tại sao cái này có thực sự cần thiết không?

kelalaka avatar
lá cờ in
Một [Sự cần thiết khác đối với số học trường hữu hạn và số nguyên tố p trong Sơ đồ chia sẻ bí mật của Shamir](https://crypto.stackexchange.com/q/5502/18298)
lá cờ kr
Vâng, cả hai câu trả lời này đều hữu ích, cảm ơn rất nhiều! Tôi đoán việc tìm kiếm từ khóa `mod` là sai và thay vào đó tôi nên tìm trường hữu hạn. Cảm ơn rất nhiều!
Điểm:0
lá cờ se

Cả hai lời giải thích mà bạn đã nêu thực sự là hai mặt của cùng một đồng tiền.

Làm thế nào bạn sẽ lấy mẫu một phần tử ngẫu nhiên thống nhất từ $\mathbb{Z}$? Đây là một tập hợp vô hạn. Ngay cả khi bạn có thể, vẫn chưa rõ bạn cần bao nhiêu byte bộ nhớ để biểu diễn "số nguyên" ngẫu nhiên này.

Vì vậy, chúng ta cần lấy mẫu các hệ số từ một tập hợp hữu hạn các phần tử (có thể được biểu diễn bằng số byte cố định). Tuy nhiên, không phải tất cả các tập hữu hạn đều cho phép bạn nội suy các đa thức. Vì vậy, chúng ta cần chọn một tập hợp hữu hạn hoạt động với một thuật toán nội suy đa thức đã biết. Nội suy Lagrange xảy ra để làm việc trên trường hữu hạn (ví dụ.đa thức với các hệ số trong một trường hữu hạn). Ví dụ điển hình nhất của trường hữu hạn là các số nguyên mod một số nguyên tố. Đây là cách biểu diễn dễ hiểu nhất về mặt khái niệm nên nhiều văn bản sẽ sử dụng ví dụ này.

Daniel avatar
lá cờ ru
Điều đáng chú ý là phép nội suy hoạt động trên các vòng hữu hạn tùy ý (không chỉ các trường hữu hạn) miễn là chúng có các điểm đánh giá $\alpha_0,\ldots,\alpha_n$ sao cho mọi chênh lệch khác 0 là khả nghịch. https://crypto.stackexchange.com/questions/48928/shamir-secret-sharing-p-not-prime/96507#96507

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