8
$\begingroup$

Given an RSA public key $(n,e)$ and the textbook-RSA encryption $c$ of a valid matching private exponent $d$, computed as $c\gets d^e\bmod n$can we factor $n$ ?

Assume $n,e,d$ are per PKCS#1v2.2. If that helps, additionally assume any common (or not overly unlikely) condition helping towards a solution, e.g.:

  1. $n$ product of two large primes $p$ and $q$
  2. $d=e^{-1}\bmod\varphi(n)$ where $\varphi$ is the Euler totient
  3. $d=e^{-1}\bmod\lambda(n)$ where $\lambda$ is the Carmichael function
  4. $e$ small, perhaps just $e=3$
  5. $e$ prime
  6. $\gcd(p-1,q-1)=2$
  7. $q<p<2q$

Motivation is this question, which I could only partially answer.

Problem is, textbook RSA encryption is conjectured secure for random secret plaintext. Random secret implies independent of the key, except for public modulus magnitude. Independent of the key is not met when encrypting $d$. As rightly pointed there, we are in unsafe territory. And for some plaintexts dependent on the private key, that would be totally unsafe. Example: if we reveal the encryption of $p$, that is $c'\gets p^e\bmod n$, we can decipher that as $p\gets \gcd(c',n)$. Other examples: revealing the encryption of $9\,q$ or of $d^d\bmod n$ breaks the security.

$\endgroup$
11
  • 2
    $\begingroup$ @kelalaka: $q<p<2q$ is a quantitative way to state that $p$ and $q$ are about the same size, which is often recommended. In some contexts involving RSA moduli, it simplifies things slightly (see e.g. last paragraph of key generation in Paillier cryptosystem). It also specifies that $q$ is the smaller of the two. I could have written the stronger and common condition $2^{k-1/2}<q<p<2^{k}$, which insures $n$ is exactly $2\,k$ bits. $\endgroup$ – fgrieu Jul 22 '20 at 20:08
  • 2
    $\begingroup$ i.e. having $c = m^{e}\pmod{n}$ can we find $m$? Can't see any reason that we can find $n$ or even the message $m$. I can't see why is more interesting if we encrypt the secret key $d$. $\endgroup$ – 111 Jul 26 '20 at 11:40
  • 1
    $\begingroup$ @111: See new paragraph at end of question. Also, notice that $n$ is a given. $\endgroup$ – fgrieu Jul 26 '20 at 12:26
  • 1
    $\begingroup$ OK. thanks. see your point better now. Although, a second thought... you can't use $p$ as message since is not in the message space, ${\mathbb{Z}}_n^{*}.$ $\endgroup$ – 111 Jul 26 '20 at 13:07
  • 1
    $\begingroup$ @111: yes you can encipher $p$, if $p\ne q$. Under that condition, RSA encryption/decryption works for all messages in $\Bbb Z_n$, with the usual formulas. We have several Q/A on that theme, see e.g. this one $\endgroup$ – fgrieu Jul 26 '20 at 13:10
1
$\begingroup$

We can compute the amount of $E=e^{e-1} mod(n)$ then compute $C=c^E=(d^e)^{e^{e-1}}=d^{e^e} mod(n)$. Now we can compute the secret key $d$ as below:

$C^c=(d^{e^e})^{d^e} mod(n)=d^{e^e.d^e}=d^{(e.d)^e}=d^{1^e}=d \mod(n)$

$\endgroup$
3
  • 1
    $\begingroup$ Nice try, but that does not work. Counterexample: $e=3$, $p=5$, $q=11$, $n=55$, $\lambda(n)=\text{lcm}(p-1,q-1)=20$, $d=e^{-1}\bmod\lambda(n)=7$, $c=d^e\bmod n=13$, $E=e^{e-1}=9$, $C=c^E\bmod n=28$, $d'=C^c\bmod n=18$, $d'\not\equiv d\bmod\lambda(n)$. The error in the proof puzzled me for some time, it's in the step reading $C^c=(d^{e^e})^{d^e}$. That really means $C^c\equiv(d^{(e^e)})^{(d^e)}\bmod n$, and that's wrong, because $c$ is defined as $c=d^e\bmod n$, not $c=d^e$ or $c=d^e\bmod\lambda(n)$. $\endgroup$ – fgrieu Nov 14 '20 at 7:45
  • $\begingroup$ I think that, the amount of $d$, according to the RSA definition, should equal to $d=e^{-1}\ \bmod(\varphi(n))=27$. Because $\varphi(n)=40$ in your example. $\endgroup$ – mehdi mahdavi oliaiy Nov 14 '20 at 16:15
  • 1
    $\begingroup$ Depends on what RSA, and it does not fix the answer. In the original RSA article, it is used $e=d^{-1}\bmodφ(n)$, which became $d=e^{-1}\bmodφ(n)$. In PKCS#1v2.2 of the question, it is is allowed any $d∈[1,n)$ with $e\,d\bmodλ(n)=1$, which allows $d=e^{-1}\bmod\varphi(n)$. In FIPS-186 it is required $d=e^{-1}\bmodλ(n)$, which often does not. $\endgroup$ – fgrieu Nov 14 '20 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.