$(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?

  • $\begingroup$ after "and we directly see that", I would have said $\exists k \in \mathbb{N}, 5d = k(1+(p-1)(q-1))$. Or am I missing something, like a bound on $d$? $\endgroup$ – Vincent Sep 2 '16 at 10:02
  • $\begingroup$ As formulated the claims are not generally true. Take e.g. $p=7, q=11$. Then $5$ has no inverse $\bmod \phi(N)$ and empirically this occurs often for other $p,q$. May be the items can be shown if you assume that the inverse of $5$ exists. And obviously your RSA case is insecure because you can easily factor $N$. $\endgroup$ – gammatester Sep 2 '16 at 10:24
  • $\begingroup$ @gammatester: Every RSA public key $(N,e)$ must satisfy $\gcd(\varphi(N),e)=1$. $\endgroup$ – TonyK Sep 2 '16 at 10:55
  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)$.

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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.