Làm thế nào là khó khăn của vấn đề logarit rời rạc liên quan đến mật mã đường cong elliptic?

Theo định nghĩa, bài toán logarit rời rạc là giải đồng dư sau cho $x$ và người ta biết rằng nói chung không có thuật toán hiệu quả nào cho việc đó.

$$\begin{align*} b^x\equiv r&\pmod p\quad(1)\end{align*}$$ Nó là để tìm $x$ (nếu có) cho trước $r,b$ là số nguyên nhỏ hơn số nguyên tố $p$.

Tôi có đúng cho đến nay không? xin vui lòng sửa cho tôi nếu tôi đang hiểu lầm bất cứ điều gì.

Trong mật mã đường cong elip người ta nói rằng trong $P=a\lần G$ chúng ta không thể tính toán $a$ bằng cách biết $P$ và $G$ bởi vì vấn đề logarit rời rạc là khó giải quyết. Tôi không hiểu rằng điều này liên quan như thế nào đến phương trình 1. Ý tôi là chỉ có thuật ngữ giống nhau trong cả hai vấn đề?

Để làm rõ câu hỏi của tôi, hãy tưởng tượng rằng một thiên tài từ các thế hệ tương lai cuối cùng có thể đưa ra một giải pháp cho phương trình 1 được thực hiện trong thời gian khả thi bằng cách sử dụng một phần cứng trung bình được thiết lập vào thời điểm đó. Thuật toán họ đề xuất có khả năng tìm $x$ (nếu tồn tại) cho bất kỳ số nguyên tố nào $p$ và bất kỳ đưa ra $r, b$. Bây giờ, tôi muốn biết liệu phát minh này có phải là mối đe dọa đối với tính bảo mật của mật mã đường cong elip không? Nói cách khác, kiến ​​thức về thuật toán như vậy có giúp truy xuất $a$ từ $P$?

Nếu có, vui lòng giải thích mối quan hệ này được xác định như thế nào và luồng toán học mà chúng ta có thể tính toán là gì $a$ từ $P$, mà tôi đoán sẽ phải thông qua việc giải một đồng dư tương tự như phương trình 1.

Nếu không, vui lòng cho tôi biết điểm khác nhau giữa độ cứng của bài toán logarit rời rạc trong đường cong elip và trong phương trình 1 và tại sao thuật ngữ này được sử dụng ở đây.

Các bài toán logarit rời rạc có thể được xác định cho bất kỳ nhóm tuần hoàn hữu hạn nào, không chỉ nhóm nhân modulo một số nguyên tố. Ví dụ nổi tiếng nhất là vấn đề mà bạn mô tả, nhưng nó không phải là vấn đề duy nhất.

Các nhóm có thể được viết với ký hiệu phép nhân (như với nhóm nhân modulo $p$), do đó hoạt động nhóm được viết là $*$, $\times$, $\cdot$ hoặc đơn giản là ẩn ý. Trong tất cả các trường hợp này, chúng tôi sử dụng ký hiệu tự nhiên để sử dụng lặp lại thao tác nhóm với một phần tử duy nhất, tức là $b^2:=b*b$ và những khái quát hóa tương tự. Do đó, vấn đề logarit rời rạc chung cho một nhóm tuần hoàn $C$ được viết bằng ký hiệu nhân được tạo bởi $b$ được đưa ra $r\in C$ tìm một số nguyên $x$ như vậy mà $b^x=r$.

Các nhóm khác được viết bằng ký hiệu cộng (ký hiệu này thường dành cho các nhóm abel, bao gồm các nhóm đường cong elip). Trong trường hợp này phép toán nhóm được ký hiệu $+$ (nhưng không nên đọc là phép cộng theo nghĩa thông thường) và một lần nữa, có một ký hiệu tự nhiên để sử dụng lặp lại phép toán nhóm với một phần tử đơn lẻ, tức là. $2G=G+G$ và kể từ đó trở đi. Khi được viết theo cách này, vấn đề logarit rời rạc cho một nhóm tuần hoàn $C$ được tạo ra bởi $G$ trở thành: đã cho $P\trong C$ tìm một số nguyên $x$ như vậy mà $xG=P$.

Người ta tin rằng không có sự dịch rõ ràng giữa các bài toán logarit rời rạc trong các nhóm khác nhau. Có một số nhóm mà vấn đề logarit rời rạc là dễ dàng (ví dụ: nhóm cộng modulo $p$, nhóm nhân modulo $2^n$ và thậm chí (theo nghĩa gần như đa thức) nhóm nhân của $GF(2^n)$).

Đối với trường hợp cụ thể của các nhóm nhân modulo $p$ cuộc tấn công (cổ điển) được biết đến nhiều nhất là sàng trường số giải quyết vấn đề trong thời gian cấp số nhân phụ. Cuộc tấn công này chỉ có thể được áp dụng cho các loại đường cong elip rất hiếm (đường cong MOV) và các cuộc tấn công chung được biết đến nhiều nhất chống lại các đường cong elliptic là các cuộc tấn công ``căn bậc hai'' áp dụng cho tất cả các nhóm.

Lưu ý rằng tất cả các bài toán logarit rời rạc có thể được giải trong thời gian đa thức (lượng tử) bằng cách Thuật toán Shor.

Để cho $E$ là một đường cong elip được xác định trên một trường hữu hạn $\mathbb{F}_p$:

$$E : y^2 = x^3 + Ax + B \text{ với } A, B \in \mathbb{F}_p$$

Để cho $P$ và $T$ được điểm trong $E(\mathbb{F}_p)$. Tìm một số nguyên $a$ Vì thế điều đó

$$ P =aG$$

Đây là vấn đề đối với các đường cong elliptic. Vấn đề có thể được viết lại bằng logarit:

$$ a = log_G (P)$$

Bạn có thể so sánh nó với logarit rời rạc "tiêu chuẩn":

$$ b^x \equiv r \mod p \Rightarrow x = log_b(r)$$

Bây giờ bạn có thấy những điểm tương đồng?

Ghi chú: Thiên tài của bạn nên có một cách hiệu quả để phá vỡ nó, không phải vì anh ta có nguồn lực vô hạn. Và vâng, nếu bạn có một cách hiệu quả để phá vỡ logarit rời rạc, bạn có thể sử dụng một biến thể của cách đó để phá vỡ các đường cong elip. Điểm chính của tiền điện tử đường cong elip là các tính toán nhanh hơn so với các hệ thống logarit rời rạc "tiêu chuẩn" (có rất nhiều ưu điểm khác cho ecc).