RSA Duplicate-Signature Attack

Question

I'm trying to duplicate an RSA signature, and am having trouble at the last couple of steps. I'll detail what I've tried.

I used OpenSSL to generate some 128-bit RSA parameters. Here are my public modulus and exponent:

N = 0xdb52a89a63825f9e498144c240f5c23b
e = 65537

The (hashed, unpadded) message and signature are:

m = 200491217728191104277162087173636532728
s = 238661990926400143633637156414542417630

To verify the signature, we check $s^e = m \mod N$. I want to craft public parameters $(N',e')$ such that $s^{e'} = m \mod N'$. I found an algorithm to do this here, in Section 4.1. To do this, I choose two primes such that:

1. $N < pq$
2. $p-1$ is smooth
3. $q-1$ is smooth
4. $m$ and $s$ should each be primitive roots mod $p$ and mod $q$
5. $\gcd(p-1,q-1) = 2$

The primes need to be smooth so that I can solve the discrete log problem in small subgroups with the Pohlig-Hellman algorithm. $m$ and $s$ need to be primitive roots so that the discrete logs exist.

I chose two primes:

p = 18446744073709558081
q = 18446744073709755467

$p-1$ has factorization $2^6\cdot 3^2 \cdot 5 \cdot 167^2 \cdot 409 \cdot 761 \cdot 859^2$.

$q-1$ has factorization $2 \cdot 13 \cdot 107 \cdot 701 \cdot 15647 \cdot 23099 \cdot 26171$.

They satisfy all the properties listed above. $N'$ is easy:

N_prime = p*q = 340282366920942343108801213731143778827

I used Pohlig-Hellman to compute $e'_p = e' \mod p$ and $e'_q = e' \mod q$. I verified these exponents solve $s^{e'_p} = m \mod p$ and $s^{e'_q} = m \mod q$.

ep = 12805870501641979644
eq = 12267640565537452735

Now here's where I'm stuck. I think I should be able to stitch together $e'_p$ and $e'_q$ with the Chinese Remainder Theorem to get $e'$:

e_prime = CRT( (ep, p-1), (eq, q-1) ) = 199703471997348597303557477228581222008

But I don't think this will work since the $p-1$ and $q-1$ are not coprime (the GCD will be at least 2 since $p-1$ and $q-1$ are always even). Besides, when I test it, it doesn't work:

pow(s, e_prime, N_prime) = 20617548250412763970655475611439323667
m % N_prime = 200491217728191104277162087173636532728

Also, for RSA, we need $\gcd(e', (p-1)(q-1)) = 1$, but for me, this quantity is 24. The source I linked to also proposes a solution, but it didn't work for me either.

Anyone have any advice and where I'm going wrong?

Answer 1

You forgot step 4:

4. $m$ and $s$ should each be primitive roots mod $p$ and mod $q$

$m$ is not a primitive root mod $p$. We can easily deduce that (without the bother of actually performing any nontrivial math) from the relation you gave:

$$s^{e_p} = m \bmod p$$

for $e_p$ even; hence $m$ must be a quadratic residue, and hence cannot be primitive.

As $e_p$ is even and $e_q$ is odd, there is no solution to the CRT...

For your reference, $m$ will be a primitive root of a prime $p$ if, for every prime factor $r$ of $p-1$, we have $m^{(p-1)/r} \not\equiv 1 \bmod p$