1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ "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 $\endgroup$ – fgrieu Feb 16 '14 at 17:49
  • $\begingroup$ @fgrieu You mean x * (v^e % n)? It equals 1752. $\endgroup$ – Babken Vardanyan Feb 16 '14 at 17:56
  • 3
    $\begingroup$ 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$. $\endgroup$ – poncho Feb 16 '14 at 22:19
  • $\begingroup$ 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? $\endgroup$ – Babken Vardanyan Feb 17 '14 at 5:44
5
$\begingroup$

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

| improve this answer | |
$\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.