# Simplified Fiat-Shamir example generates wrong output

I am trying to implement the Fiat-Shamir identification protocol, however the end results always fail to match. I am using algorithm's description from here.

Preparation:

1. Select 2 prime integers and their product:

n = 19 * 23 = 437

2. Select s coprime to n:

s = 242

3. Compute v:

v = (s^2) % n = 6


Now the round:

1. Select random r between 1 and n - 1:

r = 410

2. Calculate x:

x = (r^2) % n = 292

3. Choose e either 0 or 1:

e = 1

4. Calculate y:

y = (r * s^e) % n = 21


Now if y^2 equals (x * v^e) % n then it's accepted. However in my case

y^2 = 441
(x * v^e) % n = 4


Why don't these numbers match? What am I doing wrong here?

• "y^2 equals (x * v^e) % n" should be "$y^2\equiv x\cdot v^e\pmod n$", written here as $y^2\equiv x\cdot v^e\pmod n$, which does hold. That's because 441 - 4 is a multiple of 437, or/and because 441 % 437 == 4 – fgrieu Feb 16 '14 at 17:49
• @fgrieu You mean x * (v^e % n)? It equals 1752. – Babken Vardanyan Feb 16 '14 at 17:56
• No, he means checking whether $y^2 \equiv x \cdot v^e\ (\bmod\ n)$. One way of writing that is checking whether $(y^2 \bmod n) = ((x v^e) \bmod n)$. Remember, the squaring of $y$ occurs within the group, and hence is implicitly done modulo $n$. – poncho Feb 16 '14 at 22:19
• Oh I see now, I mistook the triple bar for equal sign. Now I see it means modular congruence. How can I accept your answers? – Babken Vardanyan Feb 17 '14 at 5:44

The problem is one of notation for modular arithmetic, at the point of the question reading

if y^2 equals (x * v^e) % n then..

if $y^2\equiv x\cdot v^e\pmod n$ then..
By definition of $a\equiv b\pmod n$, that holds if and only if $n$ divides $a-b$ (or equivalently: $|b-a|$ is a multiple of $n$). In the question, 437 divides 441-4, thus $y^2\equiv x\cdot v^e\pmod n$ holds.
Sometime, $a\equiv b\pmod n$ is written as $a=b\pmod n$, but rigorously the later means that $a$ is the set of solutions to the former. $a\equiv b\mod n$ or $a=b\mod n$ are also used, but the later is best avoided, because it is dangerously close to $a=b\bmod n$, to be read as $a=(b\bmod n)$ and thus rigorously meaning $0\le a<n$ and $|b-a|$ is a multiple of $n$. However, only a strict Vulcan would assume $0\le y^2<n$ when seeing $y^2=b\bmod n$.
Note: On this site, $y^2\equiv x\cdot v^e\pmod n$ can be written as $y^2\equiv x\cdot v^e\pmod n$. A right-click on a rendered formula then Show Math As TeX Commands will reveal the TEX code used. I often use this TEX cheat sheet.