Patent ID: 6091819
Filing Date: 2000-07-18
Classification: H04L

Abstract:
A computing device implemented method for rapidly choosing a private key k and determining a public key K=g.sup.k modulo p, where g and p are positive integers, and g and k are less than p, the method comprising:(a) performing in a precomputation module precomputation steps of:i. choosing integers .kappa. and n such that the number of ways of choosing .kappa. members from a set of n numbers is sufficiently large;ii. randomly choosing positive integers .alpha..sub.i <ord(g) for i=1, . . . , n,iii. for each said integer .alpha..sub.i, computing a value .beta..sub.i =g.sup..alpha..sbsp.i modulo p,iv. storing said integers .alpha..sub.i and said values .beta..sub.i in pairs (.alpha..sub.i, .beta..sub.i) in a table, and,(b) when a private key k and public key K are desired, performing in an online computation module online steps of:i. randomly selecting .kappa. pairs from said table,ii. evaluating said private key k as a sum of said integers .alpha..sub.i of said selected pairs, the sum being evaluated modulo ord(g),iii. restarting the online steps if the sum is zero, andiv. evaluating said public key K as a product of said values .beta..sub.i of said selected pairs, the product being evaluated modulo p.