Patent ID: 7327847

Claim:
A method for distributed computation of an RSA inverse value (y) for asynchronous authentication for communication of encrypted messages in an asynchronous network for at least two input values (x, e) among n−1 participating network devices compromising t<n/4 faulty devices and a non-faulty leader device, the participating network devices holding share values of the Euler function (μ(N)) of RSA modulus (N), each participating network device performing the steps of: a. choosing a first random value (q) and a second random value (r); b. sharing over integers (Z) the first random value (q), the second random value (r), and the zero value (0); c. the leader device performing additionally the steps of: i. receiving a first, second, and third sub-share value (q i , r i , 0 i ,) from at least t+1 participating network devices; ii. broadcasting identities of said participating network devices; d. receiving the identities and corresponding sub-share values (q i , r i , 0 i ,); e. deriving a sum-share value (F) from one of the sub-share values, the at least one input value (e), and the corresponding first, second and third sub-share values (q i , r i , 0 i ,) defined by the identities; f. broadcasting the sum-share values (F); g. receiving 2t+1 sum-share values (F i ); h. deriving a polynomial (ƒ) interpolating the sum-share values (F i ) and an exponent share value (d p ) dependent on the polynomial (ƒ), and an inverse-share value (y p ) dependent on the exponent share value (d p ) and the RSA modulus (N); i. broadcasting the inverse-share value (y p ); j. receiving t+1 inverse share values (y i ); k. verifying the validity of the received values for authenticating participating network devices by obtaining the RSA inverse value (y) from the received inverse-share values (y i ), determining the validity of the obtained RSA inverse value (y) using at least two input values (x, e,), and, in the event of a positive determination, broadcasting the RSA inverse value (y), and stopping further calculations; and l. applying the derived exponent share values for encryption of communications with authenticated participating network devices.