0
$\begingroup$

Is there a way to determine the private key (or the phi value) without n factorisation if one knows the ciphertext and the public key and that each letter of the (English) alphabet has been encrypted individually?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

Is there a way to determine the private key (or the phi value) without $n$ factorization if one knows the ciphertext and the public key and that each letter of the (English) alphabet has been encrypted individually?

No, for proper choice of public and private key.

Argument: if one knows $n$, $e$, and a matching private exponent $d$, then one can factor $n$ with little effort. Same if one knows $n$ and $\varphi(n)$. See this for how. Hence, if what's asked was possible in general, it would not be much harder to factor $n$, which what's asked excludes.

Alternate argument: for like half a century, researchers have tried and failed to find how to factor the public modulus $n$ (or find a working $d$) by putting to good use plaintext/ciphertext pairs for textbook RSA; that's even if they are allowed to iteratively choose the plaintext or the ciphertext.

As an aside, in many definitions of RSA, there are several equivalent private keys, and no way to tell which is the private key.

On the other hand, if $n$ is small enough that it can be factored, or if there is a small $d$ that works, then a working $d$ can be found (computed by one of the normal methods used in RSA, or by enumeration of small $d$ and checking them against the available plaintext/ciphertext pairs). A conclusion of that is: discussing security of RSA with poor choice of key (including, $n$ or $d$ less than some hundred decimal digits) is pointless.

$\endgroup$
1
$\begingroup$

First; Textbook RSA is not secure; for example when the private exponent is 3 and the messages are shorter than $\sqrt[3]{n}$ then cube-root attack is easy to access the messages to remove the confidentiality. This is why we need secure paddings like PKCS#1 v1.5 or OAEP must be used.

Second; encryption is free in the public key systems. I.e. anyone can take your public key and encrypt as many messages as they want, whether one bit or a character or more.

Now, assume that one can get $d$ or $\varphi$ from encrypted short messages with corresponding messages ( not mentioned has secure padding or not) that is almost equivalent to factoring ( computing $\varphi$ is not easier to factoring $n$ RSA paper, and finding $d$ can produce $\varphi$) or one can factor $n$ from $d$

Assume textbook RSA can be broken with given and the secure padding prevents this attack since they are CPA-secure. Remember in RSA the encryption is free and no one can force the attacker to use padding. Therefore they are free to encrypt as many messages without secure padding as they want and then break your private key.

So, if you can break Textbook RSA with the given then you can break secure paddings, too. This is not the way!

$\endgroup$
5
  • $\begingroup$ Thank you for your reply. The question I raised is more on how to get the d or phi without refactoring n. $\endgroup$
    – georggr
    Oct 5, 2022 at 11:16
  • $\begingroup$ They are equivalent; if you can find $d$ you factor it, if you can find $\phi$ then you factor it, too. So you have a great way to factor RSA modulus if you can. A thousand researchers tried to factor RSA modulus effectively... $\endgroup$
    – kelalaka
    Oct 5, 2022 at 11:20
  • $\begingroup$ More into, RSA-OAPE is CPA secure, that already prevent due the the simple reduction.. $\endgroup$
    – kelalaka
    Oct 5, 2022 at 11:22
  • $\begingroup$ The point is do not do any factorisation at all. For there are two notable characteristics that can make the feasible: 1) the number of symbols used for encryption is quite limited (26 words in the alphabet) and 2) Each alphabet is encrypted separately. The question now is how mathematically to use these to discover the key $\endgroup$
    – georggr
    Oct 7, 2022 at 6:21
  • $\begingroup$ What is the origin of this question? If one can find $d$ then they can factor n, In this way, as I said, you can break the Inc-CPA security of RSA padding schemes. $\endgroup$
    – kelalaka
    Oct 7, 2022 at 8:39

Your Answer

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

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