Comprehension question on a signature protocol based on the RSA assumption

Question

We have the following two-party protocol between Alice and Bob. Alice sends messages $m_1, m_2, \ldots \in_R \mathbb{Z}_n^*$ to Bob and Bob signs these values by calculating $v_1, v_2, \ldots \in_R \mathbb{Z}_n^*$ and $a_1 = \left( G \cdot H^{-v_1} \cdot K^{-m_1} \right)^{1/x}\ \bmod\ n$

$a_2 = \left( G \cdot H^{-v_2} \cdot K^{-m_2} \right)^{1/x}\ \bmod\ n$

...

$x$ is a prime and all values are public. Only $1/x$ is known by Bob because Bob knows the factorization of $n$. It is $a_i, G, H, K \in \mathbb{Z}_n^*$

Is is possible that...

(1) Alice can get $(1/x)$ or the factorization of $n$ by sending lots of messages $m_1, m_2, \ldots$ to Bob and analyse the pairs $(a_i, v_i, m_i)$?

(2) Alice can contruct her own pair $(a_i, v_i, m_i)$ without knowing the factorization of $n$.

I have found this algorithm in a paper and they choose $x$ randomly for each signing process. I ask myself, if it is really necessary to choose $x$ randomly, because finding a big prime number is relatively time-consuming. $v_i$ is under the control of Bob so the signed part between the brackets is always different. Is this enough or should the exponent $1/x$ also be different?

Answer 1

Assuming that $x$ is odd, then the answer is no for number (1); to the best of our knowledge, the attacker would not be able to either compute (1/x) or factor N, even with a huge number of sets $(a_i, v_i, m_i)$, even if he got to select the $m_i$ (and even the $v_i$) values.

This follows directly from the fact that no one knows how to factor an RSA number $n$ given an oracle that computes $F(z) = z^{1/x} \bmod n$ for odd $x$.

On the other hand, we have a definite yes for number (2); if an attacker gets two distinct valid triplet $(a_1, v_1, m_2)$, $(a_2, v_2, m_3)$, that is, with:

$a_1 = \left( G \cdot H^{-v_1} \cdot K^{-m_1} \right)^{1/x}\ \bmod\ n$

$a_2 = \left( G \cdot H^{-v_2} \cdot K^{-m_2} \right)^{1/x}\ \bmod\ n$

Then it is possible that he can construct a third triplet $(a_1^2 \cdot a_2^{-1}, 2v_1-v_2, 2m_1 - m_2)$; this will be a valid set as long as $2v_1-v_2$ and $2m_1-m_2$ are both in range; that will happen nontrivially often. Note that the attacker can compute $a_1^2 \cdot a_2^{-1}$ using $\bmod n$ arithmetic; he can't compute $2v_1-v_2$ using $\bmod \phi(n)$ arithmetic; he has to use standard subtraction, and hope the value is in range, where "in range" means "a value that the verifier will not reject as silly".

As for the expense of finding new prime values $x$ every iteration, the obvious question is "why do they need to be prime?". The only requirement that RSA places on $x$ is that it be relatively prime to both $p-1$ and $q-1$, where $p$ and $q$ are the prime factors of $n$. An easy way to handle this is during RSA key generation, you select $p$ and $q$ such that $p-1$ and $q-1$ have no small prime factors other than 2. If you ensure that neither $p-1$ nor $q-1$ have any odd factors less than $2^{k}$, and you select odd values of $x$ less than $2^{k}$, then that value of $x$ will always work, even if it is composite. On the other hand, perhaps there is something that this protocol needs besides "RSA works"; the paper discussing this protocol might mention any such concern.