3
$\begingroup$

I am working through an example solution in Nigel Smart's Cryptography: An Introduction, 3E, p. 181, about the encryption and decryption of plaintext in Rabin's cryptosystem. The calculation boils down to some modular arithmetic. Unfortunately, I don't have a lot of experience with that, and my answers are not lining up with his. I'd like some help understanding my mistakes.

Here is the portion of the problem I understand and can replicate.

Let the public and private keys be given by

  • $p=127$ and $q=131$,
  • $N=16637$ and $B=12345$.

To encrypt $m=4410$ we compute

$$c=m(m+B) \mod{N}=4633$$

My solution matches his so far. I took these steps:

$$c=4410(4410+12345)\mod{16637}$$

$$c=73889550\mod{16637}$$

$$c=4633$$

Here is the part that is giving me trouble.

To decrypt we first compute $$t=B^2/4 + c \mod{N}=1500$$

$1500$ doesn't line up with what I'm getting. Here are the steps I took:

$$t=12345^2/4 + 4633\mod{16637}$$ $$t=152399025/4 + 4633\mod{16637}$$ $$t=38099756.25 + 4633\mod{16637}$$ $$t=38104389.25\mod{16637}$$ $$t=5659.25$$

I know I must be making a simple, very ignorant mistake somewhere, but I just can't see it. What am I doing wrong?

$\endgroup$
1
$\begingroup$

$\!\bmod N\!:\,\ m^2\!+\!bm\!-\!c\equiv 0\iff m \equiv -b/2\pm\sqrt{b^2/4+c},\ $ by the quadratic formula.

You are computing the discriminant $\,b^2/4 + c,\,$ where $\,b^2/4\,$ denotes $\, 4^{-1}b^2\pmod{\!N}$

It's easy to invert $\,4\,$ mod $N\,$ by Inverse Reciprocity $ $ & $\,\color{}N = 16637\equiv 37\equiv \color{}1\pmod{\!4}\ $ so

$\!\!\bmod N\!:\,\ \dfrac{1}4\equiv \dfrac{1\!+\!N(\color{#c00}{-1})}4\equiv \overbrace{\color{#0a0}{-4159}}^{\large 12478},\ $ by $\bmod 4\!:\ 0\equiv 1\!+\!N\color{#c00}x\equiv 1\!+\!x\!\iff\! \color{#c00}{x\equiv -1}$

Plugging that value for $\,1/4\,$ into the discriminant formula yields the claimed result.

Remark $ $ Your answer is correct $\ 5659.25 = 5659+1/4\equiv 5659\color{#0a0}{-4159} \equiv 1500$

However it is not common to use decimals to denote modular fractions (even modular fractions are discouraged by some authors in elementary contexts).

$\endgroup$

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.