# RSA private key finding method

Bob uses RSA with $p=83$ and $q=103$. His public key is $e=445$. Alice claims that she can calculate Bob's private key without using the definition $d=e^{−1}\bmod φ(n)$? But how?

• Maybe she tries the various possibilities of $d$ until she hits one where $(M^e)^d = M$. With these toy parameters, that is eminently doable... – poncho Feb 10 '16 at 0:52
• – mikeazo Feb 10 '16 at 16:20
• @mikeazo That's cheating. – Melab Feb 10 '16 at 16:32
• @Melab: attackers are assumed to cheat. – fgrieu Feb 11 '16 at 13:50
• @Melab, if you consider this cheating, you should update your threat model to fix this and don't complain... – SEJPM Feb 11 '16 at 18:05

If performing as in a typical description of textbook RSA, Bob has:

1. secretly drawn distinct primes $p=83$ and $q=103$;
2. computed $n=p\cdot q=8549$;
3. computed $\varphi(n)=(p-1)\cdot(q-1)=8364$ where $\varphi(n)$ is Euler's totient function;
4. chosen $e=445$, as some arbitrary $e>1$ with $\gcd(e,\varphi(n))=1$;
5. published his public key $(n,e)\;$, which in particular Alice knows;
6. computed $d=e^{-1}\bmod \varphi(n)\;$ using the extended Euclidean algorithm, giving $d=7537$; Bob's private key is $(n,d)$, and he does its best to keep $d$ secret.

The definition of RSA worded in PKCS#1 allows Bob to choose $d$ as any positive integer less than $n$ such that $e\cdot d-1$ is a multiple of $\lambda(n)$, where $\lambda$ is Carmichael's function, with (since $n$ is the product of distinct primes $p$ and $q$) $\lambda(n)=\operatorname{lcm}(p-1,q-1)=4182\;$. That allows $d=e^{-1}\bmod\lambda(n)\;$, which is the smallest positive working $d$ (here $d=3355\;$), and often gives Bob a little less work when using his private key. Bob would have more than two possible $d$ for some other choices of $p$ or $q$, or if we removed the mathematically arbitrary constraint $0<d<n$. In particular, $d=11719$ or $d=-827$ are functional.

## Factorization

One way Alice has to find Bob's private key is to factor $n=8549$, finding it's prime factors $83$ and $103$. She then knows, within order, the $p$ and $q$ chosen by Bob at step 1, can repeat steps 3 and 6, and find Bob's private key as computed in step 6. However that's prohibited by the question's "without using the definition $d=e−1\bmod\varphi(n)\;$". More importantly, if Bob had chosen $p$ and $q$ as random primes of more than 384 bits, Alice would have to perform a factorization more difficult than was ever openly performed. For random 1024-bit primes (a common practice), Bob is likely safe from a factorization of his $n$ directly from $n$, for the time being.

## Enumeration

As pointed by poncho, Alice can find by enumeration the smallest positive odd $d$ such that $((r^e)\bmod n)^d\bmod n\;=r$ for $r$ the first few primes. That will give Alice $d=3355$, after in the order of $1700$ modular multiplications (noting that most unsuitable $d$ will be eliminated for $r=2$, and that going from one candidate $d$ to the next can be done with a single modular multiplication by $r^{2e}$). That will give Alice the smallest working $d$ such that $(n,d)$ behaves as Bob's private key. Alice may not have calculated Bob's actual private key, but the difference is semantic and it could be fixed by various methods. However, that way of finding $d$ would be impractical if Bob had chosen $p$ and $q$ as primes of $45$ bits or more.

## Other ways

Alice can perform as she claims in several other ways:

• coerce Bob to reveal his private key, by force, law, or trickery;
• read the information about Bob's private key from the device(s) Bob uses to store his private key or make use of it; absent encryption under a strong passphrase (e.g. stored un-encrypted, or under the protection of a short PIN), only physical security measures can prevent such extraction once Alice gets her hands on the device(s); Alice's job is made significantly easier by the fact that she can verify a guess of $d$ (e.g. by the method used for enumeration);
• as a special case of trickery (or law, in some countries and times), steal Bob's private key by using a Trojan horse somewhat planted in Bob's device(s); the insertion could be by Bob unknowingly (letting some vulnerable software) installing the trojan; by some evil maid; during transport of the device before delivery to Bob; or by (exploitation of a weakness left by) the manufacturer of (some part of) the device at time of manufacture (intentionally or not); there are numerous accounts of such practices, and it is extremely difficult to demonstrate one is safe from them (it is easier to be likely safe from them);
• as a refinement of read above, analyze the power consumed, the electromagnetic radiation, or perhaps just the noise emitted by Bob's device(s) when Bob uses his private key, which in the most naive implementations of RSA will directly leak the bits of $d$;
• other side-channel attacks, including timing, allowing factorization of $n$, then performing steps 3 and 6;
• fault attacks: for some possible construction of Bob's device, induce it to make computation errors when using his private key, and exploiting the erroneous results to factor $n$; this is the so-called Bellcore attack: D. Boneh, R. DeMillo, and R. Lipton, On the importance of checking cryptographic protocols for faults (pdf); however if Bob's device checks its results before revealing them, by way of the public key, as it should, this attack simply won't work.