Patent ID: 7555646

Claim:
A method of verifying knowledge of a secret number s in a prover device by a verifier device having no knowledge of the secret number, the method comprising a zero-knowledge protocol using a Montgomery representation of numbers and Montgomery multiplication operations therein, wherein the zero knowledge protocol comprises the Fiat-Shamir protocol, the method further comprising: (i) providing to the verifier device a value v=s 2 being the Montgomery multiplication of the secret number s by itself, (ii) computing, by the prover device, a value x=r x m r, where r is a random number, and transmitting the value x to the verifier device; (iii) selecting, by the verifier device, a challenge value of e from a set [0, 1] and transmitting the challenge value to the prover device; (iv) computing, by the prover device, a value y=r x m s e , and transmitting the value y to the verifier device; and (v) the verifier device checking an authenticity of the prover's response according to the values x, y and v previously received and according to the challenge value e.