Method for generating secure elliptic curves using an arithmetic-geometric mean iteration

Abstract

Methods for determining whether an arbitrary elliptic curve over a binary field is secure, by using a novel non-converging Arithmetic-Geometric Mean iteration to determine the exact number of points on the curve. The methods provide rapid generation of secure curves for Elliptic-Curve Cryptography by selecting a secure curve from among candidate curves with the new method. The secure curve chosen is a curve whose number of points is found to be divisible by a large prime number. The number of points on candidate curves is computed by a first phase, which lifts the curve to a certain related curve, followed by a second phase, which computes a certain norm that yields the result. The new Arithmetic-Geometric Mean iteration is used for the lifting phase or for the norm phase or for both.

1 - 7 . (canceled)  
   
   
       8 . A method for generating a cryptographic key for use in a digital processing system, the method comprising 
 analyzing points on an elliptic curve by using a non-converging arithmetic geometric mean calculation; and    deriving a cryptographic key from the analysis.    
   
   
       9 . The method of  claim 8 , further comprising 
 first and second phases, wherein the first phase includes a lifting procedure, wherein the lifting procedure includes the following steps:    accepting as input a given elliptic curve over a binary field; and    producing as output an approximation of a related elliptic curve, wherein the related elliptic curve is derived from the given elliptic curve.    
   
   
       10 . The method of  claim 9 , wherein at least a portion of the steps of the first phase are achieved using an arithmetic-geometric mean approach.  
   
   
       11 . The method of  claim 9 , further comprising 
 wherein the second phase includes a procedure including the following steps:    accepting as input the related elliptic curve;    computing the norm of a quantity related to the elliptic curve to determine a number of points on the given curve.    
   
   
       12 . The method of  claim 11 , wherein at least a portion of the steps of the second phase are achieved using an arithmetic-geometric mean approach.  
   
   
       13 . An apparatus for generating a cryptographic key for use in a digital processing system, the apparatus comprising 
 a digital processor;    one or more instructions stored in a memory for execution by the digital processor, wherein the one or more instructions include instructions for using a non-converging arithmetic geometric mean calculation to analyze points on an elliptic curve and to derive a cryptographic key from the results of analysis.    
   
   
       14 . A computer data signal embodied in a carrier wave comprising 
 one or more instructions stored in a memory for execution by the digital processor, wherein the one or more instructions include instructions for using a non-converging arithmetic geometric mean calculation to analyze points on an elliptic curve and to derive a cryptographic key from the results of analysis.    
   
   
       15 . A computer-readable medium including instructions for execution by a digital processor, the computer readable medium comprising 
 one or more instructions stored in a memory for execution by the digital processor, wherein the one or more instructions include instructions for using a non-converging arithmetic geometric mean calculation to analyze points on an elliptic curve and to derive a cryptographic key from the results of analysis.