1
$\begingroup$

It is know that elements from $[1..N-1]$, where $N$ is RSA modulus can have different orders. So some of the elements can have very small order generating subgroup of only few elements.

Now, if the adversary for a message chooses $m$ that has small order, the adversary does not have to know the private exponent $d$ to forge the signature for this $m$, since the same signature can be produced using smaller exponent $x$ $(d \equiv x \mod ord(m))$, which can be found easier than the private exponent $d$.

Why is this not a concern in RSA signature scheme?

Update: The cyclic attack does not depend on the order of $m$. The answer should be related to the distribution of orders for elements in $[1..N-1]$. Since the order of element divides $\phi(n)$, the choice of $p$ and $q$ should have some effect on the feasibility of this attack.

$\endgroup$
  • $\begingroup$ I don't yet understand your phrase "if the adversary .....". Normally a message m is chosen by the user and padded to produce a ciphertext c. Which one is to be chosen by the adversary? $\endgroup$ – Mok-Kong Shen Sep 23 '16 at 9:09
  • 1
    $\begingroup$ How do you define "RSA signature scheme"? If the signature of message $m$ was defined as $m^d\bmod N$, then yes this would be a concern (for example the signature of messages $0$, $1$, and $N-1$, are the message itself; that's an existential forgery; but hint: how hard is it to find other examples of elements of small order?). For this reason (and others), "RSA signature scheme" is usually defined otherwise, in a way such that an adversary in the situation of choosing $m$ has constraints on what ends up raised to the $d$. $\endgroup$ – fgrieu Sep 23 '16 at 11:01
  • $\begingroup$ @Mok-KongShen: in the attack that FaST4 is considering, the attacker selects a message $m$, and is attempting to forge a signature for that. What FaST4 is asking is if the attacker can compute $m^{ie}$ for successive $i$, and find that $m^{ie} = m$ (and if so, $m^{(i-1)e}$ is the signature); why isn't that a risk? $\endgroup$ – poncho Sep 23 '16 at 12:49
  • 1
    $\begingroup$ @poncho: I don't see how this is a duplicate, given that this question is about RSA signatures and the one you linked to is about RSA encryption. If there's some way in which the answers to the other question answer this one, it's probably non-trivial enough to merit a separate answer explaining the connection. $\endgroup$ – Ilmari Karonen Sep 24 '16 at 14:36
  • 1
    $\begingroup$ "but hint: how hard is it to find other examples of elements of small order?" @fgrieu, this seems to be the question asked. $\endgroup$ – FaST4 Sep 26 '16 at 10:54
2
$\begingroup$

The order $o$ of an element $m\in(\mathbb Z/pq\mathbb Z)^\times = (\mathbb Z/p\mathbb Z)^\times\times(\mathbb Z/q\mathbb Z)^\times$ is the least common multiple of its (multiplicative) orders modulo $p$ and modulo $q$.

If this order $o$ is known to the attacker (or at least small enough that one can find it, e.g., by baby-step giant-step), then the attacker can factor $N=pq$ if the multiplicative order of $m$ modulo $p$ differs from its order modulo $q$: The attacker raises $m$ to the power of $\frac{o}{r}$ for all prime factors $r$ of $o$, until modulo one prime factor of $N$, but not the other, the order of $m$ divides $\frac{o}{r}$, which can be detected by $0<\mathrm{gcd}(m^\frac{o}{r}-1\bmod N, N)<N$, breaking the RSA.

So what you are asking for allows the attacker either to break RSA or to find an element $m\ne 1$ that has simultaneously the same small multiplicative order $o$ for unknown primes $p$ and $q$ given just their product $N$, which I'd expect to be a hard problem ($m$ is modulo $p$ a $(\frac{p-1}{o})$-th, modulo $q$ a $(\frac{q-1}{o})$-th power).

$\endgroup$

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