Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to run in my mind the registration phase that exists in the paper: Internet Voting Protocol Based on Improved Implicit Security (pdf).

I have chosen as parameters the following:

  • the prime $p = 257$
  • the primitive root $g = 233$
  • the exponent $c = 200$
  • the private key $x = 121$
  • the random id $r_{id} = 100$
  • the blinding factor $b = 123$.

Can anyone make it work? Use the numbers you want (if you prefer not to use mine), but lines 5, 6 that result to 7 do not work for me. I am trying to find if I am doing something wrong for over $8$ hours today... in an algorithm of just $7$ lines. There is also an online modulo calculator here if you want a tool to use.

Just a note. I think that at the bullet 4(b) it should be $u^x$ instead of $u$.

I will appreciate it a lot, if anybody could help me.

Thanks in advance.

share|improve this question
    
What exactly is the problem? First, one party computes $d = (r_{id}^x g^x)^c$ and then the other party computes $e = d^{1/x}$. What are the numbers you get for $d$ and $e$? –  TMM May 10 '13 at 18:26
    
In your example, you should get $d \equiv (100^{121} \cdot 233^{121})^{200} \equiv 17$ and $e \equiv 17^{1/121} \equiv 15$, which is equal to $(r_{id} \cdot g)^c \equiv (100 \cdot 233)^{200} \equiv 15$. –  TMM May 10 '13 at 18:31
    
I get d= 17 and e = 240... –  Jasmin May 10 '13 at 18:37
    
@TMM thank you. I'll find what I am doing wrong now –  Jasmin May 10 '13 at 18:38
    
@TMM I can not understand why 17^1/121 is 15. Isn't it the same with 17^17 which makes 240? –  Jasmin May 10 '13 at 18:43

1 Answer 1

up vote 2 down vote accepted

You computed $d \equiv 17$ and $e \equiv 17^{1/121} \equiv 240$, while the result should be $e \equiv 17^{1/121} \equiv 15$. What goes wrong here is that you computed $1/121$ modulo $p$, instead of $1/121$ modulo $p - 1$.

  • Modulo $p = 257$ we have $$1/121 \equiv 17 \mod{257}$$ and thus you get a wrong answer: $$17^{1/121} \stackrel{?}{\equiv} 17^{17} \equiv 240 \mod{257}.$$
  • But modulo $\phi(p) = 256$ we have $$1/121 \equiv 201 \mod{256}$$ and you get the correct answer: $$17^{1/121} \equiv 17^{201} \equiv 15 \mod{257}.$$

A rule of thumb to remember is that in the exponent, you have to do computations modulo $p - 1$ instead of modulo $p$. This is somewhat directly a consequence of Fermat's Little Theorem, which says that $a^{p} \equiv a$, i.e., $a^{p-1} \equiv a^0 \equiv 1$ for $a \neq 0$. So in the exponent, $p - 1 \equiv 0$ rather than $p \equiv 0$.

share|improve this answer
    
Excellent answer. I am choosing it as best answer. Thank you! –  Jasmin May 10 '13 at 18:56
1  
@Andreas: You're welcome! –  TMM May 10 '13 at 18:57

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.