An RSA key with special prime numbers

Question

$(N,5)$ is a public RSA key with prime numbers $p,q$ such that $N =pq, q = 2p-3$ and $p>5$. Show that:

1. $p \equiv 3 \mod 5$
2. $(N,d)$ with $d =\frac{1}{5} (1+(p-1)(q-1))$ is a valid private RSA key to the public key $(N,5)$.

Here is my attempt to proof item 2:

We know that (from the construction of the RSA cryptosystem)

$$d \cdot e ≡ 1 \mod \varphi(N)$$

Since $\varphi(N) = (p-1)(q-1)$ and $e=5$, we have to solve

$$d \cdot 5 ≡ 1 \mod (p-1)(q-1)$$

for $d$ which is the same as

$$d \cdot 5 ≡ 0 \mod ((p-1)(q-1)+1)$$

and we directly see that

$$d =\frac{1}{5} (1+(p-1)(q-1))$$

which proves item 2.

Is that correct and can anybody help me with item 1?

Answer 1

Item 1. Look at the values $r=p\bmod 5.$ If $r=0$ then $p$ is not prime. If $r=1$ or $r=2$ (i.e. $q\bmod 5=1$) you have $\phi \bmod 5 = 0$ and there is no inverse. $r=4$ implies that $q$ is no prime because $q\bmod 5=0$.

So if your RSA system is valid, you necessarily have $p\equiv 3 \pmod 5$, and from the definition $q\equiv 3 \pmod 5.$

Item 2. From 1 we have $\phi = (p-1)(q-1)\equiv 2\times 2\equiv 4 \pmod 5.$ This means that $\phi+1$ is a multiple of $5$. Let $$d = \frac{\phi+1}{5}=\frac{(p-1)(q-1)+1}{5}$$ Then $$5d=5\frac{\phi+1}{5}=\phi+1 \equiv 1 \pmod {\phi},$$ i.e. $d\,$ is the multiplicative inverse of $5$ modulo $\phi$ and a valid private key for $(N,5).$

Note: As already mentioned in a comment, this specific RSA system is insecure, because you can easily factor $N$. You get a quadratic equation in integers from $N=p(2p-3)$ $$2p^2-3p-N=0$$ with the positive solution $$p=\frac{3+\sqrt{8N+9}}{4}$$

Answer 2

1. For $(N,5)$ to qualify as an RSA public key, we must have $\gcd(\varphi(N),5)=1$.

   As $\varphi(N)=(p-1)(q-1)$, this means that $\gcd(p-1,5)=\gcd(q-1,5)=1$, so $p$ and $q$ must equal $0,2,3,$ or $4 \bmod 5$. $p$ and $q$ are prime, and we are told that $p > 5$ and $q=2p-3$, so $p$ and $q$ must be non-zero $\bmod 5$. This leaves $2,3,$ and $4$ as possible values for $p \bmod 5$ and $q \bmod 5$.

   Now for each of these possible values for $p \bmod 5$, use $q=2p-3$ to find the corresponding value of $q \bmod 5$. What are the permissible pairs $(p \bmod 5,q\bmod 5)$?

2. From $$d \cdot 5 ≡ 0 \mod ((p-1)(q-1)+1)$$ you can't conclude that $$d =\frac{1}{5} (1+(p-1)(q-1))$$

   You have to approach it differently:

   • show (using part 1) that $d=\frac{1}{5} (1+(p-1)(q-1))$ is an integer;
   • show that $5d = 1 \bmod \varphi(N)$.