Cât de rău este să scurgi $k$ în RSA?

În RSA folosind un mic exponent public $e$ precum $65537$, cât de rău este dacă valoarea $k$ scurgeri? $k$ ca în următoarele ecuații:

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

sau

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

Intuitiv, acest lucru ar reduce doar complexitatea ruperii sistemului prin $65535$ ori, nicăieri suficient de aproape încât să conteze, deși presupun că GNFS nu ar fi îmbunătățit prin cunoaștere $k$.

EDIT: Acest lucru a apărut când ne gândim la ce se întâmplă dacă înalt bucăți de $d$ scurge, spre deosebire de biții mici. Biții joase ale $d$ scurgerea duce la factorizarea cheii. Biții înalți, totuși, doar dezvăluie $k$, deoarece $n$ poate fi folosit ca o aproximare a $\phi(n)$ pentru a calcula jumătatea superioară a $d$ dat $k$.

Nu e rău deloc.

Argument practic: multe implementări calculează $d$ la fel de $e^{-1} \mod \mathrm{lcm}(p-1,q-1)$ (OpenSSL, wolfCrypt, Mbed TLS) sau $e^{-1} \mod \mathrm{(p-1)(q-1)}$ (Cryptlib, Urzică). Deci, în practică, un adversar poate face o presupunere bună oricum.

Meta argument: un exponent privat RSA care se potrivește cu cheia publică $(n,e)$ este ceva $d$ astfel încât $\forall x, (x^e)^d = x \mod{n}$. Orice alegere va funcționa... altfel decriptarea RSA nu ar funcționa, deoarece criptarea depinde doar de $n$ și $e$. Deci dezvăluind care alegere anume $d$ deținătorul cheii private folosește nu scurge nicio informație despre cheia privată. Scurge doar informații despre cum funcționează implementarea operațiunii cu cheia privată.

Argument matematic: ați ales un exponent privat $d = k \, a$ Unde $a = \mathrm{lcm}(p-1,q-1)$. Să presupunem că adversarul găsește valoarea lui $k$, și folosește aceste cunoștințe pentru a găsi un exponent privat candidat $d'$. Adversarul își testează presupunerea calculând $(x^e)^{d'} \mod{n}$. Nu contează dacă au găsit același exponent privat pe care îl utilizați: asta nu afectează validarea ipotezei $d'$și nu afectează utilitatea cunoașterii $d'$.

Singurul motiv care se scurge $k$ ar putea conta deloc este dacă există un canal secundar în implementarea operațiunii cu cheia privată, iar cunoașterea exponentului privat utilizat ajută la exploatarea acestui canal secundar. În ceea ce privește analiza matematică, pasul afectat este „folosește aceste cunoștințe pentru a găsi un exponent privat candidat”: dacă acest pas folosește detalii interne ale implementării dvs., ar putea fi mai ușor dacă $k$ este cunoscut. Acest lucru se referă doar la implementările care folosesc exponentul privat: majoritatea implementărilor folosesc optimizarea CRT, cu exponențiări la puterea de $d_P$ și $d_Q$, iar dimensiunea acestor două valori nu este corelată cu dimensiunea lui $d$ (pentru a face o astfel de corelare, ar trebui să știți $p$ și $q$, care ar fi o pauză separată). Un canal lateral este probabil să dezvăluie dimensiunea aproximativă a $d$ oricum. Un canal lateral care scurge câteva informații despre $d$ fără să-i dezvălui dimensiunea mi se pare exagerat, dar nu am un argument solid că nu s-ar putea întâmpla.