1

The system is explained here: https://cryptography.fandom.com/wiki/Rabin_cryptosystem

I am trying to prove that the roots

$r \equiv y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p \pmod{N}\\ -r \equiv N - r \pmod{N}\\ s \equiv y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p \pmod{N}\\ -s \equiv N - s \pmod{N}$

are in fact the roots you get in decryption. Where $N=pq; p, q$ are two primes.

So far I have

let \begin{align*} r &\equiv y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p \pmod{N}\\ r^2 &\equiv (y_p \cdot p \cdot m_q + y_p \cdot p \cdot m_q)(y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \pmod{N} \\ &\equiv y_p^2 \cdot p^2 \cdot m_q^2 + 2(y_p \cdot p \cdot m_q \cdot y_q \cdot q \cdot m_p) + y_q^2 \cdot q^2 \cdot m_p^2 \pmod{N} \\ &\equiv y_p^2 \cdot p^2 \cdot m_q^2 + y_q^2 \cdot q^2 \cdot m_p^2 \pmod{N} \end{align*}

I don't know that the next steps are to get to

$r^2 \equiv m \pmod{N}$

Sarah
  • 57

1 Answers1

1

Note that $m_p^2 \equiv c \pmod{p}$ by construction and also $m_q^2 \equiv c \pmod{q}$. Also by EEA, we chose $x_p,x_q$ so that $x_p p + y_q q=1 $ so it follows that

$$x_p \cdot p \equiv 1 \pmod{q} \text{ and } x_q \cdot q \equiv 1 \pmod{p}$$

So using the CRT, look at what $r^2 \pmod{p}$, $r^2 \pmod{q}$ equal:

$$r^2 \equiv m_p^2 \equiv c \pmod{p}\tag{1}$$ and

$$r^2 \equiv m_q^2 \equiv c \pmod{q}\tag{2}$$

so CRT's uniqueness clause says that $r^2 \equiv c \pmod{pq}$

When $r$ has the property so as $-r \equiv n-r \pmod{n}$ as well, of course, in any ring.

The case for $s$ is similar, the cross term cancels out mod $N$ anyway.

Note that the construction of $r$ and $s$ closely follows the construction in the proof of the CRT for two moduli.

Henno Brandsma
  • 242,131