Tuy nhiên, ai đó có thể giải thích cho tôi bằng các thuật ngữ đơn giản tại sao chúng tôi cần trong ngữ cảnh này một lượng lớn G và nó sẽ góp phần làm cho g^ab an toàn hơn như thế nào
Bối cảnh (có thể bạn đã biết), với El Gamal, bản mã là cặp $g^r, h^r \cdot m$ (ở đâu $h$ là khóa công khai và $r$ là một giá trị ngẫu nhiên); nếu chúng ta có thể tìm ra giá trị $r$ là, chúng ta có thể phục hồi $m$ (vì chúng ta cho rằng chúng ta biết giá trị $h$).
Vì vậy, một trong những điều chúng ta cần đảm bảo là, với giá trị $g^r$, chúng ta không thể suy ra những gì $r$ Là; đây được gọi là "bài toán logarit rời rạc".
Với ý nghĩ đó, đây là một số phép toán đằng sau hiện trường:
Chúng tôi xác định "thứ tự của G" là giá trị nhỏ nhất $k > 0$ mà $G^k = 1$. Điều này thật thú vị bởi vì $G^r$ chỉ có thể đảm nhận $k$ các giá trị khác nhau, $G^1, G^2, ..., G^{k-1}, G^k = 1$. Nếu chúng ta tiếp tục, chúng ta sẽ kết thúc việc lặp lại, bắt đầu lại từ $G^1$, và vì vậy điều đó không giúp ích gì cho chúng tôi.
Nếu chỉ có $k$ các giá trị khác nhau của $r$ cung cấp cho chúng ta các giá trị khác nhau của $G^r$, sau đó nếu $k$ nhỏ, những gì kẻ tấn công có thể làm là thử tất cả $k$ các giá trị khác nhau của $r$ và xem nếu một hoạt động; nếu anh ta có thể làm điều đó, anh ta có thể phục hồi đúng giá trị của $r$ [1]. Trên thực tế, hóa ra nếu kẻ tấn công sử dụng một chút thông minh, anh ta có thể thực hiện tìm kiếm này với khoảng $\sqrt{k}$ phép nhân; do đó nếu chúng ta muốn đảm bảo rằng kẻ tấn công phải thực hiện $2^{128}$ các hoạt động tấn công hệ thống (là tiêu chuẩn hiện tại cho "điều đó vượt quá khả năng của bất kỳ ai"), thì chúng ta cần một $k$ ít nhất $2^{256}$.
Và, hóa ra có một quan sát khác được thực hiện: nếu $k$ là hợp số và có thừa số nguyên tố $s$, kẻ tấn công có thể tính toán $r \bmod s$ với $\sqrt{s}$ hoạt động (bằng cách sử dụng cùng một loại thông minh); điều này làm giảm sức mạnh của một $G$.
sử dụng p = 2q+1 biểu thị rằng bậc của G là 2 và q và "g sau đó đôi khi được chọn để tạo nhóm con thứ tự q của G, thay vì G, do đó ký hiệu Legendre của g^a không bao giờ tiết lộ mức thấp thứ tự chút của a.
Điều này nói về một phương pháp phổ biến để đối phó với các cuộc tấn công trên (không phải là phương pháp duy nhất, tâm trí).
Nó chỉ ra rằng nếu $p = 2q+1$ thủ, ở đâu $q$ cũng là số nguyên tố, và nếu $p \mod 8 = 7$ (điều mà Wikipedia quên đề cập), thì giá trị $g=2$ luôn có đơn đặt hàng $q$; đó là một số nguyên tố lớn. 2 có gì đặc biệt? Chà, nó làm cho việc tính toán lũy thừa dễ dàng hơn một chút (vì nhân với 2 modulo p khá rẻ).
Và, khi nó nói về biểu tượng Legendre tiết lộ điều gì đó về $g^a$, vâng, đó là một phương pháp tìm mục đích đặc biệt $a \bmod 2$; về bản chất, đó là cách tiếp cận tương tự như tôi đã tham khảo ở trên để khôi phục $a \bmod s$ vì $s=2$; nó chỉ hoạt động nếu thứ tự của $g$ có 2 là một yếu tố. Bởi vì chúng tôi đã chọn một $g$ có một thứ tự kỳ lạ $q$, nó không hoạt động.
[1]: Bạn có thể hỏi: ngay cả khi $G^r$ là như nhau, nó sẽ không thể là $H^r$ nhận các giá trị khác nhau? Hóa ra là không, điều đó không thể xảy ra - nếu chúng tôi tìm thấy bất kỳ giá trị nào $r$ mang lại cho anh ta giá trị quan sát của $G^r$, anh ta có thể sử dụng nó để giải mã.
