Việc rò rỉ $k$ trong RSA tệ đến mức nào?

Trong RSA sử dụng số mũ công khai nhỏ $e$ Như là $65537$, thật tệ biết bao nếu giá trị $k$ rò rỉ? $k$ như trong các phương trình sau:

$ed - 1 = k \phi(n)$

hoặc

$ed - 1 = k \cdot \operatorname{lcm}(p-1,q-1)$

Theo trực giác, điều này sẽ chỉ làm giảm sự phức tạp của việc phá vỡ hệ thống bằng cách $65535$ lần, không nơi nào đủ quan trọng, mặc dù tôi cho rằng GNFS sẽ không được cải thiện khi biết $k$.

CHỈNH SỬA: Điều này nảy ra trong suy nghĩ về những gì sẽ xảy ra nếu cao bit của $d$ rò rỉ trái ngược với các bit thấp. Các bit thấp của $d$ rò rỉ dẫn đến key factorization. Tuy nhiên, các bit cao chỉ tiết lộ $k$, bởi vì $n$ có thể được sử dụng như là một xấp xỉ của $\phi(n)$ để tính nửa cao của $d$ được cho $k$.

Nó không tệ chút nào.

Đối số thực tế: nhiều triển khai tính toán $d$ như $e^{-1} \mod \mathrm{lcm}(p-1,q-1)$ (OpenSSL, wolfCrypt, Mbed TLS) hoặc $e^{-1} \mod \mathrm{(p-1)(q-1)}$ (Cryptlib, cây tầm ma). Vì vậy, trong thực tế, một đối thủ dù sao cũng có thể đoán đúng.

Đối số meta: số mũ riêng RSA khớp với khóa chung $(n,e)$ là bất kỳ $d$ như vậy mà $\forall x, (x^e)^d = x \mod{n}$. Lựa chọn nào cũng được â nếu không thì quá trình giải mã RSA sẽ không hoạt động, vì quá trình mã hóa chỉ phụ thuộc vào $n$ và $e$. Vì vậy, tiết lộ sự lựa chọn cụ thể của $d$ người giữ khóa riêng sử dụng không làm rò rỉ bất kỳ thông tin nào về khóa riêng. Nó chỉ làm rò rỉ thông tin về cách thực hiện thao tác khóa riêng.

Đối số toán học: bạn đã chọn một số mũ riêng $d = k \, a$ ở đâu $a = \mathrm{lcm}(p-1,q-1)$. Giả sử đối thủ tìm thấy giá trị của $k$và sử dụng kiến ​​thức này để tìm một số mũ riêng ứng cử viên $d'$. Đối thủ kiểm tra dự đoán của họ bằng cách tính toán $(x^e)^{d'} \mod{n}$. Không quan trọng liệu họ có tìm thấy cùng một số mũ riêng mà bạn đang sử dụng hay không: điều đó không ảnh hưởng đến việc xác thực dự đoán $d'$và nó không ảnh hưởng đến tính hữu ích của việc biết $d'$.

Lý do duy nhất bị rò rỉ $k$ hoàn toàn có thể quan trọng nếu có một kênh phụ trong việc triển khai thao tác khóa riêng và việc biết số mũ riêng nào được sử dụng sẽ giúp khai thác kênh phụ này. Đối với phân tích toán học, bước bị ảnh hưởng là “sử dụng kiến ​​thức này để tìm một số mũ riêng ứng cử viênâ: nếu bước này sử dụng các chi tiết nội bộ về triển khai của bạn, thì có thể dễ dàng hơn nếu $k$ đã được biết đến. Điều này chỉ liên quan đến các triển khai sử dụng số mũ riêng: hầu hết các triển khai sử dụng tối ưu hóa CRT, với các lũy thừa cho sức mạnh của $d_P$ và $d_Q$và kích thước của hai giá trị đó không tương quan với kích thước của $d$ (để thực hiện bất kỳ mối tương quan nào như vậy, bạn cần biết $p$ và $q$, đó sẽ là một sự phá vỡ riêng biệt của chính nó). Một kênh bên có khả năng tiết lộ kích thước gần đúng của $d$ dù sao. Một kênh phụ rò rỉ một số thông tin về $d$ mà không tiết lộ kích thước của nó có vẻ xa vời đối với tôi, nhưng tôi không có lý lẽ vững chắc rằng điều đó không thể xảy ra.