Sử dụng thuật toán của Shor để truy cập các tin nhắn RSA mà không cần bao thanh toán

Hầu hết thời gian mọi người quên rằng mục đích thực sự của kẻ thù chống lại mã hóa là truy cập vào tin nhắn. Ví dụ, trong trường hợp RSA, chúng ta nói về việc bao thanh toán mô đun để đạt được khóa riêng để tiết lộ các thông báo được mã hóa. Nếu mã hóa thích hợp không được sử dụng thì thay vì bao thanh toán, người ta có thể thử không gian tin nhắn có thể hoặc tấn công khối lập phương.

Trong trường hợp RSA, nếu có bao giờ một kích thước thực được xây dựng cho Thuật toán tìm chu kỳ Shor kẻ tấn công có thể tính mô đun và sau đó có thể tiết lộ thông báo bằng cách sử dụng khóa riêng trong thời gian đa thức hoặc tốt hơn trong BQP.

• Có thể với thuật toán của Shor đã sửa đổi (hoặc thuật toán khác) không tính đến mô-đun nhưng tiết lộ thông báo được mã hóa theo RSA trong sách giáo khoa hoặc RSA được đệm đúng không?
• Có một tác phẩm xuất bản tương tự như thế này?

Điều này chỉ có ý nghĩa trong trường hợp việc tiết lộ các thông báo mà không bao thanh toán có thể yêu cầu ít QBit hơn so với thuật toán của Original Shor.

Đối với mô đun RSA, thuật toán của Shor sẽ (với xác suất cao) trả về một hệ số lớn theo thứ tự cấp số nhân của một số modulo phần tử cơ sở $N$. Các thuật toán cổ điển bổ trợ khác nhau có thể sử dụng điều này để trả về các thừa số của $N$, nhưng đồng thời, người ta có thể trực tiếp sử dụng đầu ra này để tính toán số mũ giải mã hiệu quả mà không cần bận tâm đến việc tính toán các thừa số. Cụ thể, nếu $k$ là đầu ra của thuật toán Shor sau đó giải quyết $de\equiv 1\pmod{100!k}$ có khả năng sẽ cung cấp một số mũ giải mã hiệu quả $d$ (cần lưu ý rằng $100!$ không có yếu tố chung với $e$, nhưng chúng ta chỉ có thể chia chúng ra).

Cách tiếp cận này chỉ thực sự tiết kiệm thời gian cho quá trình xử lý hậu kỳ cổ điển và không tiết kiệm được gì cho tính toán lượng tử. Thuật toán của Shor khá hiệu quả và rất khó để đưa ra những cải tiến đáng kể. Một trường hợp mà tôi có thể tin rằng một tin nhắn đơn lẻ rẻ hơn để tấn công là nếu chúng ta biết/tin rằng bản mã có modulo bậc nhân nhỏ hơn đáng kể $N$. Sau đó, chúng tôi có thể chọn cụ thể thông báo của mình làm cơ sở cho cuộc tấn công của mình bằng thuật toán của Shor. Trong trường hợp này, chúng ta có thể tham số hóa biến đổi Fourier lượng tử của mình để khôi phục các đơn đặt hàng lên đến một số ràng buộc $b$ thay vì đầy đủ $\lambda(N)$, yêu cầu đại khái $2b$ qubit QFT chứ không phải $2\lambda(N)$ qubit QFT. Không có gì trong sách giáo khoa RSA hoặc RSA với phần đệm được tiêu chuẩn hóa để ngăn các đơn đặt hàng nhân nhỏ, nhưng chúng khó xảy ra.

ETA: Nếu chúng tôi phục hồi một đơn đặt hàng nhỏ, hãy nói, $r$ sau đó giải quyết $de\equiv 1\pmod r$ cung cấp một số mũ giải mã hoạt động đối với phần tử có thứ tự nhỏ, nhưng sẽ không hoạt động đối với bản mã chung. Xác suất có đơn đặt hàng nhỏ sẽ phụ thuộc mạnh mẽ vào các yếu tố của $p-1$ và $q-1$. Một rất giới hạn trên thô của tỷ lệ văn bản mật mã có thứ tự nhỏ hơn $b$ sẽ là $$\sum_{d|\lambda(N):d>\lambda(N)/b}\frac1d.$$

Tôi chỉ có thể đưa ra một câu trả lời rất đơn giản.

Trong N. David Mermin's Khoa học máy tính lượng tử: Giới thiệu, trong phần giải thích về mã hóa RSA trong Phần 3.3, anh ấy nói

Việc tìm ra khoảng thời gian hiệu quả được quan tâm trong cài đặt mật mã này không chỉ vì nó trực tiếp dẫn đến phép tính hiệu quả (như được mô tả trong Phần 3.10), mà còn bởi vì nó có thể dẫn trực tiếp Eve đến một cách khác để giải mã thông điệp của Alice $b$ mà không cần cô ấy biết hoặc phải tính toán các yếu tố $p$ và $q$ của $N$ [Khóa công khai của Bob]. Đây là cách nó làm việc:

Sau đó, anh ấy tiếp tục giải thích cách giải mã tin nhắn bằng thuật toán của Shor cho phát hiện thời gian một cách khá đơn giản. Chỉ sau đó đáng kể, trong phần 3.10 sau khi anh ấy đã hoàn thành việc giải thích cách sử dụng thuật toán của Shor để giải mã trực tiếp RSA, anh ấy mới riêng biệt giải thích thuật toán tìm chu kỳ của Shor có thể Mà còn được sử dụng để bao thanh toán các số lớn (do đó cũng có thể được sử dụng để phá vỡ RSA theo một cách khác).

Phương pháp thứ hai này có vẻ phức tạp hơn một chút đối với tôi để hiểu, nhưng tôi không biết phương pháp nào yêu cầu nhiều tài nguyên tính toán hơn. Tôi nghi ngờ rằng chúng khá gần với mức tương đương, bởi vì tôi nghĩ chúng chỉ khác nhau trong quá trình xử lý hậu kỳ cổ điển chứ không phải trong việc sử dụng biến đổi Fourier lượng tử. (Mặc dù, tôi tin rằng quá trình hậu xử lý cổ điển thực sự là nút cổ chai tính toán cho thuật toán của Shor, vì vậy có thể có sự khác biệt đáng kể về tài nguyên.)