3
$\begingroup$

I'm working on finding an attack on textbook RSA using non-prime, low public exponents $e_1,e_2$ for each encryption.

Given $$c_1 = m^{e_1}\space mod \space n \\ c_2 = m^{e_2} \space mod \space n$$

I found there's the Common Modulus Attack which works when $gcd(e_1,e_2)=1$.

But is there a different way to solve the problem with $gcd(e_1,e_2) \neq 1$ ?

Given $$n=p*q\\e_1 = 2 \\ e_2 = 6$$ $n$ can't be factorized since $p,q$ are both 1024-bit numbers. $m^e>n$ so it wont be attack by $m=c^\frac{1}{e}$

In contrast, what if encryption using multiple $n$? $$c_1 = m^e \space mod \space n_1 \\ c_2 = m^e \space mod \space n_2$$

$\endgroup$
0

2 Answers 2

2
$\begingroup$

In the question, the same message $m$ is encrypted in different ways using textbook RSA. Don't do this in a real application, because it opens to all kinds of attacks (those discussed in the question, and others). Textbook RSA encryption should only be used as a building block to encrypt individually randomized messages, using a process called random padding. See e.g. RSAES-OAEP.

Common message and modulus attack

The example given for the common modulus attack is not RSA, because $e_1$ and $e_2$ are even, thus not coprime with $p-1$ and $q-1$, as required for $e$ in RSA (and unambiguous decryption).

Further, here $e_2=3\,e_1$, thus $c_2={c_1}^3\bmod n$, thus being given $c_2$ can't be of any help (with $n$, $e_1$ and $e_2$ assumed public, it's trivial to find $c_2$ from $c_1$).

We are left to solve $c_1=m^{e_1}\bmod n$, and that's hard when the factorization of $n$ is unknown, unless $m$ is small enough‡ that $m^{e_1}<n$, or close to that. When $e_1$ is a proper RSA exponent for $n$, and $m$ is essentially random in $[0,n)$ as it should be, that's the RSA problem. Here with $e_1=2$, that problem is extracting a modular square root modulo a large composite $n$ of unknown factorization, a problem that's demonstrably as hard as factorization for random $m$.

That's general: when $\gcd(e_1,e_2)=g>1$ in the common modulus attack, the standard "common modulus" attack leaves us with solving $c=m^g\bmod n$ (or $c=m^{g'}\bmod n$ with a $g'$ multiple of $g$ that we can choose, which is not easier), and we are stuck unless $m^g<n$, or close to that. Extracting modular $g^\text{th}$ root is trivial with $g=1$, but for random $n$ is believed intractable for every other $g$ obtained as the GCD of proper RSA exponents, and for $g=2$ as in the question.

There are attacks with "common modulus" in their name that do not require that the GCD of the $e_i$ is $1$, but AFAIK they require largish $\prod e_i$ and small $d_i$, which can't be the case in the question for safe choice of $n$, since the $e_i$ are few and small.

Common message and exponent attack

In the question's final part, the quantity $m^e$ appears in the two mathematical expressions† of the available ciphertexts $c_1$ and $c_2$, before reduction modulo two known $n_1$ and $n_2$ of unknown factorization. Using the Chinese Remainder Theorem allows to compute $m^e\bmod(n_1\,n_2)$, e.g. as $c=\Bigl(\left(n_2^{-1}\bmod n_1\right)\left(c_1-c_2\right)\bmod n_1\Bigr)\,n_2+c_2$. This is an integer $c$ with $0\le c<n_1\,n_2$.

If it happens that $m^e<n_1\,n_2$, then we must have $m^e=c$ which allows attack‡.

It can be seen that when we have $e$ ciphertexts rather than $2$ in the example, $m^e<\prod n_i$ and thus the attack always succeeds. That's Håstad's broadcast attack. The academically correct way to prevent that attack and it's extensions is not to use a large $e$, or use different $e$ for each public key. It's to use random padding at each encryption, as stated in preliminary.


† Notice that the full $m^e$ is not computed in normal use, because modular exponentiation algorithms used to compute $m^e\bmod n$ perform modular reduction along the way, after each modular multiplication or modular squaring.

‡ If $m^e<n$, then $c=m^e\bmod n\,=\,m^e$ without modular reduction and we can find $m$ by computing $m=\sqrt[e]c$ in standard integers $\mathbb Z$. There are extensions that allow somewhat larger $m$, see this old question that I'm attempting to revive.

$\endgroup$
0
$\begingroup$

Firstly, let me mention some improprieties in your example:

Given
$n=p∗q$
$e_1=2$
$e_2=6$
$n$ can't be factorized since $p$,$q$ are both 1024-bit numbers. $m^e>n$ so it wont be attack by $m=c^{1/e}$

1) $e_1=2$ and $e_2=6$ are not valid public exponents for Textbook RSA-2048 since the public exponent $e$ must meet the condition of $gcd(e,ϕ(n))=1$. You are working on "finding an attack on textbook RSA using non-prime, low public exponents" so lets stay in the boundries of the problem.

2) Assumption of $m^e>n$ is not always valid for Textbook RSA. Different padding methods are used in current systems in order to make the output size equals to the size of the RSA modulus $n$. However, we cannot guarantee that $m^e>n$ for Textbook RSA unless we make a restriction on message such that $m>n^{1/e}$.

If I answer your actual questions:

But is there a different way to solve the problem with $gcd(e_1,e_2)≠1$ ?

Not always. The Common Modulus Attack allows one to obtain $m^a$ ($mod$ $n$) where $m$ is the desired plaintext and $a=gcd(e_1,e_2)$. However, extracting $a-th$ roots for ultimate goal will be probably hard. In other words, The Common Modulus Attack reduces your problem to different RSA instance. As mentioned here, if you have an oracle that can solve this problem, then you should also be able to solve RSA problem for related values.

On the other hand, there are some works that improve the other attacks in the literature by using Common Modulus Attack as mentioned here. Originally, Wiener's Attack requires $d<$$(1/3)$ $n^{0.25}$ for the recovery of the private exponent $d$. In this work, it is relaxed to $n^{0.357}$ by using another instance. Additional results for different number of instances can be found in this paper as:

enter image description here

So for the situation of $gcd(e_1,e_2)≠1$, Common Modulus Attack can be more effective for the small private exponent case which is not suitable your request. - since you are interested in small public exponents which guarantee private exponent to be large-

In contrast, what if encryption using multiple n?
$c_1=m^e$ $mod$ $n_1$
$c_2=m^e$ $mod$ $n_2$

It is totally different and more desirable attack scenario when you are working with small public exponent. You can check "Hastad's Broadcast Attack" which is very powerful in this concept. For $e=3$, you may recover the message $m$ from

$c_1=m^3$ $mod$ $n_1$, $c_2=m^3$ $mod$ $n_2$, and $c_3=m^3$ $mod$ $n_3$

by using Chinese Remaninder Theorem.

$\endgroup$
3
  • $\begingroup$ Some errors in the common modulus part of this answer: (1) Extracting $a^\text{th}$ roots is irrelevant in the common modulus attack. (2) That attack works equally well for small and large exponents. What matters is that the GCD of the exponents is 1. (3) The other common modulus attacks that are linked to assume a small $d$, and use that to factor $n$, which has nothing to do with the question. $\endgroup$
    – fgrieu
    Commented Sep 25, 2023 at 8:57
  • $\begingroup$ 1) It is the same thing you explained in the paragraph starting with "That's general" in your answer. 2) That attack is not only valid for the gcd(e1,e2))=1. For gcd(e1,e2))>1, there are some combined attack for small $d$ case as mentioned. However, it is basically another rsa instance for the case of $d$ is large but still valid. 3)No, I think it is related with the question. $\endgroup$
    – NB_1907
    Commented Sep 25, 2023 at 13:32
  • $\begingroup$ I misunderstood you. You meant extracting $a^\text{th}$ roots modulo $n$, and indeed that's relevant. The confusion I made comes from the fact that extracting $a^\text{th}$ roots, in the sense that has in $\mathbb R$ or $\mathbb Z$, is relevant to Håstad's broadcast attack. For 2/3 I don't think the other attacks with "common modulus attack" in their description are relevant in the context of the question, since the question uses two small $e_i$, thus presumably large $d_i$, and said other attacks require small $d_i$ and large $\prod e_i$. $\endgroup$
    – fgrieu
    Commented Sep 25, 2023 at 14: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.