Tại sao các trường hữu hạn rất quan trọng trong mật mã?

Tôi mới bắt đầu tìm hiểu về mật mã học và hiện đang học bằng cách thử triển khai một số thuật toán mật mã.

Hiện đang triển khai thuật toán chia sẻ bí mật Shamir, điều tôi nhận thấy là các trường hữu hạn tiếp tục xuất hiện.

Tôi chỉ không hiểu tại sao chúng lại có liên quan.

Tôi thấy một điều là họ có thể đảm bảo rằng không có kết quả nào của bạn là số thập phân, vì vậy không có lỗi làm tròn, nhưng tôi thực sự nghi ngờ đó là lý do họ rất quan trọng. Sẽ thật tuyệt nếu ai đó có thể cho tôi trực giác về lý do tại sao chúng cần thiết.

Ngoài ra, thực tế là chúng hữu hạn có hại cho bảo mật không?

Tôi sẽ cố gắng đưa ra câu trả lời chung cho điều này.

Một trường hữu hạn được biểu thị bằng ${F_p}$, trong đó p là số nguyên tố, hoạt động tốt với các thuật toán mã hóa như AES, RSA, v.v. vì những lý do sau:

• Chúng ta cần giải mã tin nhắn được mã hóa, điều này chỉ có thể thực hiện được khi có sẵn một hàm nghịch đảo (điển hình) duy nhất. Điều này chỉ có thể xảy ra khi không có ước số 0 trong hàm và nó cũng có tính nội xạ và tính từ.

• Ngoài ra, nó cung cấp hoạt động đóng, có nghĩa là, bất kỳ thao tác nào bạn thực hiện trong trường, kết quả sẽ vẫn ở trong trường, điều này giúp dễ dàng triển khai các thuật toán mã hóa.

• Trường hữu hạn được tạo bởi số nguyên tố (số nguyên tố hoặc đa thức bất khả quy) có các đặc điểm bắt buộc này.

• Nó không chỉ được sử dụng trong Mật mã học mà còn trong mã hóa kênh như mã hóa BCH hoặc Reed-Solomon. nó phổ biến trong hầu hết các mã sửa lỗi giao tiếp, bảo mật dữ liệu/nội dung, cũng như các tiện ích mở rộng của chúng như Nhóm và Nhẫn được sử dụng trong Hóa học và các lĩnh vực khoa học khác.

Những điểm được Mark và SSA nêu ra là những điều chính. Chúng tôi có một lớp cấu trúc được nghiên cứu kỹ lưỡng cùng với các vấn đề phù hợp hiện được cho là khó tính toán (mặc dù đã được nghiên cứu kỹ lưỡng). Trên thực tế tất cả các ánh xạ tuyến tính affine $x\mapsto ax+b$ là những dự đoán (xem những gì Mark đã nói về entropy tối đa) bất cứ khi nào $a$ là một phần tử khác không của trường. Nếu chúng tôi không có một lĩnh vực cụ thể, điều này sẽ không giữ được.

Tôi cũng muốn thêm một vài tính chất của trường hữu hạn của đặc trưng hai nói riêng ($GF(2^n)$ hoặc $\Bbb{F}_{2^n}$):

• Không gian khóa (hoặc không gian thông báo hoặc không có gì) sau đó có kích thước là một số nguyên chính xác của bit. Điều này được thừa nhận không phải là một mối quan tâm cấp bách. Giống như một sự tiện lợi.
• Có cấu trúc trường xung quanh giúp phân tích các hoạt động tính toán hiệu quả nhất định từ quan điểm bảo mật. Ví dụ, các hàm đơn thức đã được nghiên cứu rộng rãi từ quan điểm của thám mã vi phân. Tìm kiếm các hàm APN (=Phi tuyến tính gần như hoàn hảo). Với một cấu trúc ngẫu nhiên hơn, các phân tích như vậy sẽ bị đánh thuế nhiều hơn.

Tuy nhiên, cũng có những hạn chế đối với các lĩnh vực này

• cấu trúc bổ sung có nghĩa là ví dụ DLP có thể dễ quản lý hơn A) trong nhóm "hộp đen" có cùng kích thước hoặc thậm chí B) trong trường nguyên tố có kích thước gần như nhau

Tại sao một lĩnh vực: Ý tưởng đằng sau việc chia sẻ bí mật của Shamir vừa là tái tạo lại bí mật (chức năng) vừa chứng minh rằng bất kỳ bí mật được chia sẻ nào cũng có thể thực hiện được (bảo mật) bằng cách sử dụng phép nội suy đa thức.

Mặc dù phép nội suy đa thức có thể được thực hiện trên nhiều cấu trúc đại số, nhưng nó sẽ luôn hoạt động trên một trường. (Trong một trường, một đa thức khác 0 có nhiều nhất là số 0 bằng bậc của nó. Trong các cấu trúc đại số liên quan khác, điều này thường không đúng.)

Trong khi chia sẻ bí mật của Shamir thường được thực hiện trên các trường, nó đã được thực hiện trên nhiều cấu trúc đại số khác. Điều này thường đòi hỏi sự cẩn thận cao độ và phức tạp. Trừ khi bạn thực sự phải làm, thực hiện nó trên các lĩnh vực sẽ dễ dàng và thích hợp hơn nhiều.

Tại sao hữu hạn: Nó không đủ để bảo mật rằng mọi bí mật được chia sẻ đều có thể xảy ra, mọi bí mật được chia sẻ cũng phải (gần như) có khả năng như nhau. Sử dụng các trường hữu hạn cho phép chúng ta chọn tính ngẫu nhiên từ một phân phối đồng nhất, điều này hóa ra lại cho chúng ta chính xác những gì chúng ta muốn.

Chúng ta có thể làm việc trên một trường vô hạn chẳng hạn như các số hữu tỷ, nhưng trong trường hợp này sẽ rất khó để mọi bí mật được chia sẻ có xác suất gần như bằng nhau. Điều này liên quan đến việc không có phân phối đồng đều trên các tập hợp vô hạn. Nói một cách đại khái, một cách để xem xét nó là kích thước của giá trị có liên quan đến kích thước của các hệ số và nơi chúng ta đánh giá, vì vậy nếu chúng ta muốn ẩn một trong các hệ số, chúng ta cần "dìm nó ra" bằng cách có các hệ số khác lớn hơn nhiều.

Có thể thực hiện nó trên các số nguyên (không phải một trường!), nhưng để bảo mật đòi hỏi khá nhiều công việc. Như một tác dụng phụ (ít nhất là đối với kế hoạch mà tôi đã xem xét), cổ phiếu cuối cùng sẽ lớn hơn nhiều. Bạn không muốn những chi phí này trừ khi bạn có lý do chính đáng. (Điều mà bạn làm, đôi khi.)

Chúng ta có thể cố gắng làm việc trên một xấp xỉ của một trường vô hạn chẳng hạn như số thực hoặc số phức, nhưng trong trường hợp này, mọi thứ trở nên phức tạp hơn nhiều, vì chúng ta cũng phải xử lý số học không chính xác. Tôi chưa thấy ai cố gắng làm điều này, ngoại trừ do nhầm lẫn.

Các lĩnh vực mật mã khác: Các trường hữu hạn được sử dụng trên toàn bộ mật mã. Thông thường, điều này liên quan đến các phần tử khác 0 trong các trường có nghịch đảo nhân mà chúng ta rất thường muốn. Hoạt động này cũng có nhiều tính chất tốt đẹp khác, có thể chứng minh được.

Phần hữu hạn thường được yêu cầu cho tính thực tiễn, và đôi khi do các tính chất cụ thể của trường hữu hạn.

• AES: Một ví dụ là trong hộp AES, nơi có nhiều thuộc tính mong muốn xuất phát từ các thuộc tính đại số. Chẳng hạn, bạn sẽ không nhận được các thuộc tính đại số giống nhau từ các số nguyên modulo 256 (một vành).

• Phân nhóm nhân: Một ví dụ khác là nhóm con cấp số nhân của trường hữu hạn (các phần tử khác 0 của trường hữu hạn tạo thành một nhóm tuần hoàn), nhóm này đối với trường hữu hạn được chọn cẩn thận hóa ra lại là một nhóm phù hợp cho mật mã dựa trên d.log.. (Các logarit rời rạc được định nghĩa theo cách tương tự như các logarit thông thường, nhưng hóa ra trong một số nhóm, chúng dường như rất khó tính toán nếu không có máy tính lượng tử.)

  Trong trường hợp này, chúng ta cũng có thể sử dụng một số vành nhất định, nhưng hóa ra trong thực tế, các trường hữu hạn nguyên tố tốt hơn cho loại ứng dụng này. Chẳng hạn, bảo mật không phụ thuộc vào thứ tự nhóm bí mật, cho phép chúng tôi thực hiện một số điều bạn không thể làm nếu thứ tự nhóm không xác định. (RSA hoạt động trên các vòng như vậy, nhưng có các đặc tính và yêu cầu khác.)

• Đường cong elip: Tuy nhiên, một ví dụ khác là các đường cong elip, được sử dụng rộng rãi trong mật mã học (thậm chí cả mật mã hậu lượng tử). Trong khi một cái gì đó rất giống đường cong elip có thể được định nghĩa trên các cấu trúc đại số khác như vành, thì lý thuyết phong phú về đường cong elip đòi hỏi phải làm việc trên các trường.

  Nghiên cứu về các đường cong elip là một phần quan trọng của lý thuyết số, nhưng đối với các mục đích mã hóa, các đường cong được xác định trên các trường vô hạn là không thực tế hoặc không phù hợp cho các mục đích chức năng và không có các thuộc tính bảo mật cần thiết. (Ví dụ: có thể tính toán một nhật ký rời rạc gần đúng bằng cách xem xét kích thước của tọa độ, thứ có thể phá vỡ tính bảo mật, nếu nó không phá vỡ tính thực tế trước tiên.) Mặc dù các đường cong elip được xác định trên các trường vô hạn không được sử dụng theo chức năng trong mật mã, nghiên cứu của họ là cần thiết cho việc phân tích mật mã đường cong elip.

  Các đường cong elip trên các vành hữu hạn nhất định đã được xem xét trong bối cảnh mật mã học, nhưng ngoại trừ các trường hợp tối nghĩa thì không mang lại bất kỳ điều gì đáng quan tâm. (Bao thanh toán đường cong elip rõ ràng bị loại trừ!)

• Các ví dụ khác: Mật mã dựa trên lưới và mật mã dựa trên mã, sử dụng các cấu trúc đại số được xác định trên các trường hữu hạn. Mật mã đa biến, dựa trên các hệ phương trình đa thức trên các trường hữu hạn.

  Một lần nữa, phần lớn điều này có thể được thực hiện trên một số vành hữu hạn nhất định, nhưng có nhiều nhược điểm và thu được không nhiều.

Để biết cụ thể về Chia sẻ bí mật của Shamir, bài viết trên Wikipedia cuộc đàm phán về tại sao các trường hữu hạn được sử dụng, thay vì một vòng khác.Trong một trường hữu hạn, không có thông tin nào về bí mật bị rò rỉ khi biết một số lượng chia sẻ dưới ngưỡng. Lý do cho điều này là mọi hàm trên một trường hữu hạn đều có một biểu diễn đa thức duy nhất (tối đa là q-1)