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:
- $N < pq$
- $p-1$ is smooth
- $q-1$ is smooth
- $m$ and $s$ should each be primitive roots mod $p$ and mod $q$
- $\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?