Tham gia Đăng nhập
Điểm:2
James avatar Crypto

Bẻ khóa mật mã đường cong Elliptic

lá cờ br
James

Tôi còn khá mới đối với nghiên cứu về mật mã đường cong elip và vì vậy tôi có thể đang hỏi điều gì đó với một giải pháp trần tục, nhưng tôi không thể dễ dàng tìm thấy giải pháp như vậy trực tuyến. Hiểu biết của tôi về ECC là bạn có thể tạo khóa riêng (một số nguyên $k$), một điểm bắt đầu trên đường cong ($G$), và phương trình đường cong, sau đó tạo khóa công khai thông qua việc tìm $kG$. Theo hiểu biết của tôi thì máy tính của bạn sẽ hoạt động tuy nhiên cần có nhiều thao tác để tìm $kG$ (nếu $k$ là 16 thì đó sẽ là bốn hoạt động).

Với dữ liệu này, điểm bắt đầu $G$, phương trình đường cong và khóa công khai được công khai. Điều tôi thắc mắc là tại sao kẻ tấn công không thể cố gắng tìm ra khóa riêng $k$ đơn giản là, lấy điểm bắt đầu và thực hiện các thao tác cho đến khi chúng đạt được khóa chung và như vậy biết điều gì $k$ Là? Có phải dựa trên thực tế là người gửi chỉ cần 4 thao tác để tính toán $kG$ trong khi kẻ tấn công sẽ cần 16 thao tác (đối với ví dụ đã cho)?

1127
1 + 7
lá cờ ca
MaiaVictor
Bạn cần đoán khóa riêng tư trước khi bắt đầu thực hiện các thao tác. Nếu chúng ta đang nói về khóa riêng tư 256 bit, thì có các khóa `2^256` để thử. Bạn sẽ chỉ tiếp cận được khóa công khai của mục tiêu nếu bạn đoán đúng khóa riêng tư. Điều đó có nghĩa là, nếu bạn chọn một khóa riêng tư ngẫu nhiên và thực hiện các thao tác với hy vọng đạt được khóa chung của mục tiêu, thì chỉ có `0,0000000000...(+66 số 0)...8` cơ hội thành công cho mỗi lần thử.
1
Hồi đáp
James avatar
lá cờ br
James
Nhưng nếu máy tính của người dùng chẳng hạn, mất 10 phép tính để tính khóa công khai (một ví dụ đơn giản), thì máy tính của kẻ tấn công chỉ cần bắt đầu từ $G$ và thực hiện khoảng 1024 phép tính để đạt đến điểm $kG$. Tôi có thể thấy đây có khả năng là một sự khác biệt khá lớn, nhưng có vẻ như một siêu máy tính có thể vượt qua một ví dụ lớn hơn trong một khoảng thời gian hữu hạn (vài tuần hoặc lâu hơn).
0
Hồi đáp
dave_thompson_085 avatar
lá cờ cn
dave_thompson_085
Đối với các kích thước hiện được coi là an toàn (256 hoặc 255 bit trở lên), 'cuộc tấn công' này tiêu tốn nhiều năng lượng hơn mức tồn tại trong vũ trụ. Bạn cần kiểm soát số lượng khổng lồ -- hàng nghìn tỷ tỷ tỷ -- của các vũ trụ khác, có nghĩa là bạn phải là một vị thần, và hồ sơ của bạn không xác định bạn là một vị thần. Xem https://crypto.stackexchange.com/questions/58373/how-to-calculate-a-private-key-from-public-key-on-elliptic-curve và nhiều liên kết khác tại đó.
1
Hồi đáp
fgrieu avatar
lá cờ ng
fgrieu
Xem câu chuyện ngụ ngôn về [lúa mì và bàn cờ](https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem), chỉ với bàn cờ lớn hơn khi thực sự sử dụng Đường cong Elliptic (trong đó $k$ có thể mất $n\approx2^{ 256}$ giá trị). Ngẫu nhiên, "lấy điểm bắt đầu và thực hiện các thao tác cho đến khi chúng đạt được khóa chung" không phải là chiến lược tốt nhất: nếu có $n$ giá trị có thể có của $k$, nó yêu cầu các bước $\Theta(n)$, khi đó là những chiến lược chỉ yêu cầu các bước $\Theta(\sqrt n)$.
3
Hồi đáp
lá cờ jp
user253751
@James Được rồi, bây giờ nếu máy tính của người dùng thực hiện 256 phép tính để tính khóa chung thì sao? Máy tính của kẻ tấn công cần thực hiện bao nhiêu phép tính?
0
Hồi đáp
PrincePolka avatar
lá cờ cn
PrincePolka
"Có phải dựa trên thực tế là người gửi chỉ cần 4 thao tác để tính kG trong khi kẻ tấn công sẽ cần 16 thao tác (đối với ví dụ đã cho)?" Đúng
1
Hồi đáp
James avatar
lá cờ br
James
Cảm ơn bạn cho tất cả các ví dụ và câu trả lời. Tôi hiểu cuộc tấn công đơn giản này trở nên không khả thi về mặt tính toán nhanh như thế nào.
0
Hồi đáp
Điểm:5
jjj avatar Crypto
lá cờ cn
jjj

Để tính toán $kG$ bạn cần $O(log(k))$ hoạt động. (Đối với mỗi bit, hãy nhân đôi kết quả và cộng thêm $G$ nếu bit là $1$). Như bạn đã đề cập trong một bình luận cho khoảng $k=1024$ bạn sẽ cần như thế $10$ thao tác tính toán $kG$. Nhưng ví dụ này quá nhỏ để sử dụng thực tế và hiệu ứng theo cấp số nhân vẫn chưa thực sự phát huy tác dụng. Thông thường, khi đường cong có trật tự quanh $2^n$, $k$ sẽ có độ lớn tương tự như $2^n$.

Vì vậy, đối với các đường cong với thứ tự $2^{256}$ish bạn cần xung quanh $log(2^{256})=256$ thao tác tính toán $kG$ nhưng $2^{256}$ để tấn công nó. Chỉ có một vấn đề với các đường cong nhỏ vô lý với thứ tự có thể lên tới vài tỷ hoặc nghìn tỷ (như trong ví dụ của bạn).

0 + 3
AAA avatar
lá cờ nl
AAA
Bạn có thể làm tốt hơn $2^{256}$. Bạn có thể sử dụng bước khổng lồ baby-step để khôi phục $k$ trong khoảng $2^{128}$ thời gian. Tuy nhiên, vấn đề là: phải mất thời gian đa thức để tính toán $kG$, nhưng các cuộc tấn công được biết đến nhiều nhất cần thời gian theo cấp số nhân để khôi phục $k$.
3
Hồi đáp
James avatar
lá cờ br
James
Nếu chúng tôi có thể nói rằng ví dụ như một máy tính có thể tính toán 80.000.000.000 thao tác mỗi giây (tám mươi máy tính thực hiện một thao tác mỗi nano giây), tức là khoảng $2^{36}$ thao tác mỗi giây và các cuộc tấn công nhanh nhất có thể tìm thấy khóa trong các hoạt động $2^{n/2}$ trong đó $n$ là kích thước khóa, liệu kích thước khóa 138 có đủ để khiến bất kỳ cuộc tấn công nào trở nên bất khả thi hay không (mất khoảng 3200 năm để tính toán)?
0
Hồi đáp
James avatar
lá cờ br
James
Như một giải pháp thay thế bổ sung, nếu có quá nhiều lo lắng về việc Điện toán lượng tử có thể tấn công mã hóa có kích thước khóa nhỏ hơn, liệu có đủ khả năng để tạo Hệ thống mật mã đường cong Elliptic với kích thước khóa lớn mà không mất quá nhiều thời gian để tính toán hay không (1024 các thao tác dường như không mất quá nhiều thời gian để một máy tính hiện đại thực hiện, ngay cả khi mỗi thao tác mất 1.000.000 nano giây để thực hiện)?
0
Hồi đáp
lá cờ ag
Gabriel Garrett
@AAA có bất kỳ triển khai bước khổng lồ nào được biết đến công khai đối với Mã hóa đường cong Elliptic không?
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

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