Simplified Fiat-Shamir example generates wrong output

Question

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:

Select 2 prime integers and their product:
```
n = 19 * 23 = 437
```
Select s coprime to n:
```
s = 242
```
Compute v:
```
v = (s^2) % n = 6
```

Now the round:

Select random r between 1 and n - 1:
```
r = 410
```
Calculate x:
```
x = (r^2) % n = 292
```
Choose e either 0 or 1:
```
e = 1
```
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
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 05:44

fgrieu · Accepted Answer · 2014-02-18T06:51:40.523

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..

Likely the textbook is about

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 T_EX code used. I often use this T_EX cheat sheet.

Simplified Fiat-Shamir example generates wrong output

1 Answers1

Linked