Patent ID: 8132006

Claim:
A computer-implemented cryptographic authentication method for at least one of first and second computer systems to prove knowledge of a predefined value π to the other one of the first and second computer systems in execution of a predefined authentication protocol, the value ir being one of a predefined set of values Π; the method comprising the first computer system performing the following operations in accordance with the authentication protocol: (1) receiving, over a computer network, data representing positive integer values N and x whose absolute values are greater than 1, wherein the authentication protocol requires the values N and x to be generated outside of the first computer system and to depend on the value π; wherein the authentication protocol requires each value in the set Π to be associated with a subset θ of a predefined set PP of positive integers, the subset θ consisting of one or more of the positive integers, different values in the set Π being associated with different subsets θ, wherein a product of all of the one or more integers in a subset θ associated with any one of the values in the set Π is different from a product of all of the one or more integers in a subset θ associated with any other one of the values in the set Π; wherein the authentication protocol requires the second computer system to know at least one of (i) the subset θ associated with the value π, (ii) a product P π of all of the one or more integers in the subset θ associated with the value π, (iii) a product P π of all of the one or more integers in the set PP but not in the subset θ associated with the value π; (2) generating data representing an integer e and an integer b, where b is coprime to N; (3) generating data which represent values y and z such that: y is congruent to x e mod N; and z is congruent to b P p mod N; (4) sending the data which represent the values y and z to the second computer system without sending, to the second computer system, data which represent any one or more of the values e, b, P π , P p ; (5) performing at least one of the following operations (5A) and (5B): (5A) receiving first proof data from the second computer system, and checking the first proof data to verify that the second computer system has obtained, from the values y and z: (5A-1) an integer value a congruent to e mod P π ; and (5A-2) the value b; (5B) sending second proof data to the second computer system, the second proof data being operable to prove to the second computer system that the first computer system knows the value a defined in (5A-1) and the value b.