În semnarea RSA găsiți n din e și multe perechi de m și c

Când semnați folosind RSA cu $e = 65537$ și multe perechi de m și c, Unde $$c^e \bmod (n)=m$$ Există o modalitate de a găsi n (n este de 2048 de biți)?

Am plănuit să fac calcul $ c^e-m $ și apoi tratându-le ca pe o bază pentru o zăbrele. Dar $c^e$ era prea mare.

Există o modalitate de a găsi n (n este de 2048 de biți)?

Da, dacă presupuneți căptușeală deterministă (care este uneori folosită pentru semnături, care pare să fie cazul pe care îl luați în considerare)

Sunteți pe drumul cel bun luând în considerare $c^e - m$ (care va fi un multiplu al $n$); având în vedere că avem mai multe, ceea ce putem face este să luăm două și să calculăm:

$$\gcd( c^e-n, c'^e-m' )$$

Asta o să fie $n$ (înmulțit cu un număr întreg cu o probabilitate mare de a fi mic; este ușor de eliminat); asta e raspunsul tau.

Valorile pentru care luăm GCD sunt aproximativ $2^{27}$ biți în lungime - utilizarea algoritmilor binari standard sau euclidieni ar dura probabil mai mult decât am prefera să așteptăm. In orice caz, Algoritmul GCD al lui Lehmer ar trebui să-l aducă într-un interval care nu este intolerabil...