3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Your link to the algorithm points to an entire proceedings, can you point to the specific paper ? $\endgroup$
    – Ruggero
    May 17, 2017 at 8:54
  • $\begingroup$ Thanks, I updated my answer with a link to the paper. It's in Section 4.1. $\endgroup$
    – user47922
    May 17, 2017 at 14:33
  • 1
    $\begingroup$ The link is to the original version of the paper. An update is available from the second author, in postscript; here is a pdf. $\endgroup$
    – fgrieu
    May 17, 2017 at 15:04

1 Answer 1

3
$\begingroup$

You forgot step 4:

  1. $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$

$\endgroup$
2
  • $\begingroup$ In the revised paper, the requirement becomes 2(b) and 3(d) in section 4.1, asking that $s$ and $m$ are both generators of $\mathbb Z_p^*$ and $\mathbb Z_q^*$. $\endgroup$
    – fgrieu
    May 17, 2017 at 15:12
  • $\begingroup$ Thanks! Of course that was my error. In my Python script, I wrote "for r in factors(p-1): assert pow(m, (p-1)/r, p). That's it. No "!= 1" as I had deleted it by mistake. I was so proud of myself too! Thanks again. $\endgroup$
    – user47922
    May 17, 2017 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.