Score:0

Find the RSA private key only by knowing the public key, the ciphertext and that each letter in the alphabet was encrypted separately

ht flag

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?

Score:1
in flag

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!

georggr avatar
ht flag
Thank you for your reply. The question I raised is more on how to get the d or phi without refactoring n.
kelalaka avatar
in flag
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...
kelalaka avatar
in flag
More into, RSA-OAPE is CPA secure, that already prevent due the the simple reduction..
georggr avatar
ht flag
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
kelalaka avatar
in flag
What is the origin of this question? If one can find $d$ then [they can factor n](https://crypto.stackexchange.com/q/16036/18298), In this way, as I said, you can break the Inc-CPA security of RSA padding schemes.
Score:1
ng flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.