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.:
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.
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP