Làm thế nào để Prime Factorization phá vỡ ECDSA?

Question

Tôi nghe nói rằng ECDSA sẽ bị phá vỡ trong tương lai không xa (khoảng 15-25 năm) bởi Máy tính lượng tử chạy Thuật toán Shor. Tuy nhiên, theo hiểu biết của tôi, mục đích duy nhất của Thuật toán Shor là nhanh chóng tìm ra các thừa số nguyên tố của các số rất lớn. Mặc dù tốn thời gian nhưng việc phân tích nhân tử như vậy không có nghĩa là không thể trên các máy tính hiện đại. Hệ số nguyên tố của khóa công khai trên đường cong Secp256k1 có thể được tìm thấy trong vài giờ với thuật toán thích hợp. Có công thức nào có khả năng lấy được khóa ECDSA riêng tư từ khóa công khai nếu các yếu tố chính của khóa công khai đó được tiết lộ không, hoặc có một số khía cạnh khác của quá trình phân tích nhân tử gây ra rủi ro bảo mật lớn như vậy không? Tôi đã không thể tìm thấy bất kỳ thông tin nào về các phương tiện mà các cuộc tấn công lượng tử này có thể phá vỡ mã hóa khóa công khai mặc dù rất lo lắng về nó. Bất kỳ lời giải thích nào, đặc biệt là với các ví dụ toán học, sẽ được đánh giá rất cao.

Answer 1

Tuy nhiên, theo hiểu biết của tôi, mục đích duy nhất của Thuật toán Shor là nhanh chóng tìm ra các thừa số nguyên tố của các số rất lớn.

Sự hiểu biết của bạn là không chính xác. Thuật toán Shor có thể sử dụng cho cả tính toán số nguyên và tìm logarit rời rạc.

Thuật toán của Shor hoạt động theo hai phần. Đầu tiên, nó biến bài toán (bao thanh toán hoặc nhật ký rời rạc) thành một bài toán tìm chu kỳ của một hàm. Bước đầu tiên này là phi lượng tử. Sau đó, nó tìm khoảng thời gian bằng cách sử dụng Biến đổi Fourier Lượng tử (QFT). Khi bạn có chu kỳ của hàm, bước đầu tiên có thể được đảo ngược để tìm ra giải pháp cho vấn đề ban đầu.

Thuật toán của Shor có thể được sử dụng mà không có phần Lượng tử và mô phỏng QFT, tuy nhiên sau đó nó sẽ chậm hơn đáng kể so với các thuật toán cổ điển được biết đến nhiều nhất. Việc triển khai python này mô phỏng QFT và có thể hỗ trợ sự hiểu biết.