TransWikia.com

In RSA, given public key $(n,e)$ and $d^ebmod n$, can we factor $n$?

Cryptography Asked on November 30, 2021

Given an RSA public key $(n,e)$ and the textbook-RSA encryption $c$ of a valid matching private exponent $d$, computed as $cgets d^ebmod 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}bmodvarphi(n)$ where $varphi$ is the Euler totient
  3. $d=e^{-1}bmodlambda(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^ebmod n$, we can decipher that as $pgets gcd(c’,n)$. Other examples: revealing the encryption of $9,q$ or of $d^dbmod n$ breaks the security.

One Answer

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)$

Answered by mehdi mahdavi oliaiy on November 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP