Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
3  
"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 at 17:49
    
@fgrieu You mean x * (v^e % n)? It equals 1752. –  user2529583 Feb 16 at 17:56
3  
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 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? –  user2529583 Feb 17 at 5:44
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.