Làm thế nào để biết các yếu tố của khóa giúp tôi giải mã?

Tôi đã xem qua Thuật toán của Shor (giải quyết vấn đề sau: "Cho một số nguyên N, tìm các thừa số nguyên tố của nó").

Trên thực tế, thuật toán của Shor giải quyết vấn đề "đã cho một hàm tuần hoàn $f$, nghĩa là, nếu $\underbrace{f(f(... f(a))...)}_{k\text{ times}} = a$, cái gì $k$?"

Bằng cách chỉ định $f$ khéo léo, chúng ta có thể sử dụng điều này để giải quyết vấn đề chia thành thừa số. Tôi lưu ý điều này bởi vì nó cũng có thể được sử dụng để giải các bài toán thú vị khác.

Trong mọi trường hợp, điều bạn thực sự hỏi là "nếu chúng tôi có thể xác định được chìa khóa, thì điều đó giúp chúng tôi phá vỡ RSA như thế nào"? Lưu ý rằng RSA phụ thuộc vào độ khó của hệ số hóa; các phương pháp khác (chẳng hạn như Diffie-Hellman) cũng dễ bị tổn thương trước thuật toán của Shor, nhưng chúng sử dụng một thuật toán khác $f$ chức năng.

Chà, với RSA, số mũ công khai $e$ và số mũ riêng $d$ có liên quan bởi $e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$. Nó chỉ ra rằng nếu chúng ta biết các thừa số nguyên tố $p, q$ và chúng ta biết số mũ công khai $e$ (được đưa ra trong khóa chung), thật dễ dàng để tính toán số mũ riêng $d$; điều đó ngay lập tức cho chúng ta một cách để giải mã thông qua $P = C^d \bmod n$.