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.

Improve this question
$\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, 2020 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, 2020 at 11:40
  • 1
    $\begingroup$ @111: See new paragraph at end of question. Also, notice that $n$ is a given. $\endgroup$
    – fgrieu ♦
    Jul 26, 2020 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, 2020 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, 2020 at 13:10

1 Answer 1

Reset to default
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)$

Improve this answer
$\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, 2020 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$
    – Mahdi Mahdavi
    Nov 14, 2020 at 16:15
  • 2
    $\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, 2020 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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