Abstract:
Innovative Innovative techniques over the conventional random number generators and randomization procedures are disclosed. The improved techniques use irrational numbers over the pseudo-random numbers generated by LFSR and use irrational number generators involve floating-point operations over the conventional integer arithmetic and logic operations. These innovative techniques can be applied to various cryptography applications such as hashes, ciphers, and random number generators. Particularly, the cubic root and inverse cubic root are two suitable functions for use in this invention.

Description:
CROSS REFERENCE TO RELATED APPLICATION  
       [0001]    Referenced is made to and priority claimed from U.S. Provisional Application No. 60/303,351, filed Jul. 5, 2001, entitled “Method and apparatus of using floating-point operations in data security,” which is incorporated herein by reference. 
     
    
     
       COPYRIGHT NOTIFICATION  
         [0002]    Pursuant to 37 C.F.R. §1.71(e), Applicant note that a portion of this disclosure contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.  
         BACKGROUND OF THE INVENTION  
         [0003]    1. Field of the Invention  
           [0004]    The present invention relates to cryptography, and more particularly, to use irrational numbers as random numbers and randomization procedures for various cryptographic applications.  
           [0005]    2. Description of the Related Art  
           [0006]    Cryptography always involves random numbers. Random numbers generated can be used to scramble data in hash functions, block ciphers, and stream ciphers, etc.  
           [0007]    A hash function is used to scramble an input data with certain procedures such that generating results is straight forward but recovering the input from the results is extremely difficult. The hash function may incorporate keys for flexibility and more varieties. A set of data can be encrypted by ciphers that include a predetermined procedure and a key. If a cipher operates on data in real time, this cipher is referred to as a stream cipher. Otherwise if the cipher operates on data block-by-block, this cipher is referred to as a block cipher.  
           [0008]    Either hash functions or ciphers depend on a procedure for randomization and a key for encryption and decryption. The cryptography in the past tended to keep both procedures and keys secret for maximum security. But the cryptography of current trend tends to keep the procedure open but hold the keys secret. If the effort of attacking a cipher takes as much as of trying out the keys exhaustively, this cipher is said to be very secure. A continuous bit stream of no repetitive patterns, call one-time pad, is the most secured cipher.  
           [0009]    So far, all the randomization procedures in cryptography involve only integer arithmetic and logic operations, such as Boolean operation, modulus arithmetic, permutation, substitution, or multiply exponential. The conventional random number generators are based on Linear Feedback Shift Register (LFSR) of various kinds.  
           [0010]    [0010]FIG. 1 is a block diagram depicting a prior art LFSR  100 , that is commonly used in stream ciphers. In the LFSR  100 , N number of flip-flops  104 ,  106 ,  108  . . . are connected in series. The output  102  of the LFSR  100  is the output of Nth flip-flop  110  (N−1). The exclusive-OR gates  112 ,  114 ,  116 , . . . ,  118  have one input from the exclusive-OR output of the flip-flop in the previous stage, and the other input from either the output of the current flip-flop or hardwired to logic 0. The switches  120 ,  122 ,  124 , . . . ,  126  select the input for each exclusive-OR gate either from a corresponding flip-flop outputs or from logic 0, to simply bypass the output of the current flip-flop. The output from the exclusive-OR gate  112  is connected to the input of the first flip-flop  104  to complete a feedback loop. The switches are selected to produce a 2 N −1 maximum length of pseudo-random numbers, according to algorithms well known to one skilled in the art.  
           [0011]    [0011]FIG. 2 shows a block diagram of Data Encryption Standard (DES) system  200  that is commonly used in block ciphers. A 64-bit plaintext  202  is provided as input to the DES  200  and goes into the initial permutation  204 . Through 16 rounds of encryption processes  206  through  208 , and inverse initial permutation  210 , to produce the output ciphertext  212 . In the first round of encryption process  206 , the 64-bit plaintext  202  input provided through the initial permutation  204  is split into a left 32-bit L 0    214  and aright 32-bit R 0   216 . The right 32-bit R 0    216  is the output  218  of left 32-bit L 1    220  after the first round process  206 . The right 32-bit R 0    216  undergoes an encryption function f  222  with a key K 1    224 . The result is fed into an exclusive-OR gate  226  with the key K 1    224  to produce the right 32-bit output R 1    228  after the first round process  206 . In summary, in a DES system, the function f takes the 32-bit input, expanding into 48 bits, exclusive-OR&#39;ed with a 48-bit K i , and feeds into 6 S-boxes to perform substitution and then permutation for output. The key K i  is the permutation of the original key K for round i.  
           [0012]    Various cryptographic procedures, such as hash functions, stream ciphers, block ciphers, or random number generators, can be referred to Douglas Stinson&#39;s “Cryptography: Theory and Practice”, by CRC Press, 1995, for example.  
           [0013]    The random number generators made of LFSR  100  suffer two problems: (1) the maximum length is finite and is limited to 2 N −1, no matter how large the number of stage N is; and (2) once 2N consecutive bits are known, the follow on bits can, be predicted. There are several variations of LFSRs by using multiple LFSRs combined with threshold logic. Nevertheless, they are still very vulnerable to attack. The block cipher such as DES has small key length that can be easily attacked by using fast computers in exhaustive trials.  
           [0014]    Thus, there is a need for improved random number generators to approach the one-time pad and better randomization procedures other than using integer and Boolean logic operations in cryptography.  
         SUMMARY OF THE INVENTION  
         [0015]    This invention is about using irrational numbers as random numbers in the random number generators and using irrational number generators as randomization procedures for cryptographic applications.  
           [0016]    Most irrational numbers show no repetitive bit patterns. The irrational bits generated with no correlation between bits, and are distributed statistically random that are perfect candidates for random numbers. The Irrational Number Generators (ING) can be applied to many cryptographic applications in various ways.  
           [0017]    The irrational number generators can be used as random number generators, hash functions, or ciphers, etc. The irrational number generators can generate random numbers per se. A hash function can be embodied by combining the input data with a key and then undergoing an irrational number generator to produce a hashed output. Combining the input data with a key can be implemented by XORs, for example. Similarly, a block cipher can be embodied by combining the input data block by block with a key and undergoing an irrational number generator. If the irrational number generator is equipped with a buffer in the output, this bit stream can be combined with an input bit stream in real time for stream cipher. The combination can be implemented by XORs, for example.  
           [0018]    The irrational number generator can be embodied as method, apparatus, or computer readable medium. The method is the underline procedure to perform irrational number generator. The hardware implementation can be realized by running a CPU executing instructions, or by designing in hardwire using random logic. The software implementation can be the instruction code stored in any kinds of memory devices for computers or CPUs to run on. The computer readable medium can be various kinds of memory devices such as semiconductor memory or magnetic storage devices.  
           [0019]    The irrational number generator consists of weak key filter, pre-scale, integer-to-floating conversion, floating-point operation, floating-to-integer conversion, bit skip, deskew, and truncation units.  
           [0020]    The crucial part of the irrational number generator is the floating-point operation. The floating-point operation can be any functions that can generate irrational numbers such as sinusoidal, logarithmic, exponent, cubic root or higher root functions. The preferred embodiments are to choose those functions that can produce quality irrational numbers and yet easy to implement. Though the square-root function is easy to implement, the results generated show repetitive patterns when represented in continued fraction. Therefore, the ciphers made of square-root can be easily attacked. The cubic root and inverse cubic root are preferred embodiments.  
           [0021]    Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by ways of example the principle of the invention. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0022]    The present invention will be readily understood by the following detailed description in conjunction with the accompanying drawings, wherein like reference numerals designate like structural elements, and in which:  
         [0023]    [0023]FIG. 1 is a block diagram showing a Linear Feedback Shift Register (LFSR) that is commonly used as a stream cipher;  
         [0024]    [0024]FIG. 2 is a block diagram depicting a Data Encryption Standard (DES) system that is commonly used in a block cipher;  
         [0025]    [0025]FIG. 3 is an exemplary one embodiment illustrating implementing an irrational number generator implemented in hash functions of the present invention;  
         [0026]    [0026]FIG. 4 is an exemplary embodiment of depicting having an irrational number generator implemented in block ciphers of the present invention;  
         [0027]    [0027]FIG. 5 is an alternative embodiment showing utilizing an irrational number generator implemented in block ciphers of the present invention;  
         [0028]    [0028]FIG. 6 is an exemplary embodiment illustrating using an irrational number generators implemented in stream ciphers of the present invention;  
         [0029]    [0029]FIG. 7 is a block diagram showing an irrational number generator of the present invention;  
         [0030]    [0030]FIG. 8 is a table showing a selection table of cubic root function in radix 4 SRT method using 4 bits of partial results Q and 9 bits of partial remainder P for indexing; and  
         [0031]    [0031]FIG. 9 is a block diagram depicting a hardware embodiment in generating cubic root for radix r SRT method. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0032]    The present invention utilizes irrational numbers as random numbers and irrational number generators set forth as encryption processes for various cryptographic applications.  
         [0033]    Most irrational numbers show no repetitive patterns and are statistically random. If the irrational numbers and the processes of generating cryptographic applications are properly chosen, the bit stream generated is close to the one-time pad that can result in a highly secured code. Some irrational numbers when represented in certain forms can show some traits of repetitive patterns. For example, the square root of any integers, when represented in a continued fraction, always shows repetitive patterns. The well-known irrational number “e”, the base of the natural logarithm, when represented in continued fractions, show some traits of predictability:  
         e   =     2   +       1     1   +            1     2   +            1     1   +            1     1   +            1     4   +            1     1   +            1     1   +   6                     …                    ,                         
 
         [0034]    However, a cubic root of 2 shows no repetitive patterns when represented in continued fraction for more than 50 terms.  
         [0035]    The irrational number generators can be readily embodied for various kinds of cryptographic applications such as hash functions, block ciphers, and stream ciphers, etc.  
         [0036]    [0036]FIG. 3 is a block diagram illustrating an exemplary embodiment of using irrational number generator implemented in a hash function  300  of the present invention. The input data, i.e., the initial key  302 , combined with a random number provided by a pseudo random number generator  304  in the data combination unit  306  and then input to a irrational number generator  308  to produce the hashed data  310 . The data combination unit  306  can be implemented on the one hand in bit-by-bit exclusive-OR gates in a simple logic, or can be implemented in complicated permutation, substitution, or modulus arithmetic of all kinds. The hash function  300  is normally used to scramble the key  302  with a random number into a session key  312 . The one-way hash function when applied to the original key  302  can protect the key from being recovered.  
         [0037]    [0037]FIG. 4 is a block diagram depicting an exemplary embodiment of using irrational number generator in a block cipher in the present invention. The input data  402  goes through m rounds of encryption procedure  404  through  408  to generate the ciphertext output  410 . The input key  412  is scrambled in hash units  414 ,  416 , . . . , to generate a new session key for each round of scrambling. In the first round of encryption  404 , the key  412  goes into an irrational number generator  418  to produce an n-bit result  420  and then are combined with the input data  402  in the combination unit  422  to generate an output  424 . The combination unit  422  can be implemented on the one hand in bit-by-bit exclusive-OR gates in a simple logic, or alternatively can be implemented in complicated permutation, substitution, or modulus arithmetic of all kinds. The same encryption blocks can be repeated m rounds to increase security. At each round, the key is further hashed to provide more protection.  
         [0038]    [0038]FIG. 5 is an alternative embodiment showing utilizing an irrational number generator implemented in alternative block ciphers of the present invention. The input data  502  with keys  504  goes through m rounds of encryption procedure  506  through  510  to generate the ciphertext  512  output. In the first round of encryption  506 , the input data  502  is combined with a key  504  in a combination unit  514  and are input to an irrational number generator  516  to produce output  518  for the next round of encryption  508 . The combination unit  514  can be implemented on the one hand in bit-by-bit exclusive-OR gates in a simple logic, or alternatively in-complicated permutation, substitution, or modulus arithmetic of all kinds on the other hand of complicated logic. The key can be further hashed in  520 ,  522 ,  524  . . . for the subsequent rounds  508 , . . . ,  510  to provide more security. The number of rounds m and the actual implementation may vary and still within the scope of the invention for those skilled in the art.  
         [0039]    [0039]FIG. 6 is an exemplary embodiment illustrating using an irrational number generators implemented in a stream cipher of the present invention. A key  602  is connected as an input to an irrational number generator  604  to generate a bit stream of statistically random bits  606 . This bit stream  606  is stored in a bit buffer  608  to accommodate the different rates of input between the incoming bit stream  610  and the random bit stream  606 . The bit buffer  608  can be implemented as a First-In-First-Out (FIFO) buffer, or simple in a memory either single-ported or dual-ported. Then the buffered bit stream is combined with the input bit stream  610  in the combination unit  612 , and then output to bit stream  614 . The combination unit  612  can be implemented simply in exclusive-OR (XOR) gates, or through any integer or Boolean operations.  
         [0040]    [0040]FIG. 7 is a block diagram showing an irrational number generator  700  of the present invention. The irrational number generator  700  includes a weak key filter  702 , a pre-scale unit  704 , an integer-to-floating conversion  706 , floating-point operation  708 , floating-to-integer conversion  710 , bit skip unit  712 , deskew unit  714 , and truncation unit  716 .  
         [0041]    The floating-point operation  708  is a key feature of the irrational number generator  700 . A variety of floating-point operations such as sinusoidal, exponent, logarithmic or roots are capable of producing a stream of irrational bits. In a preferred embodiment, the floating-point operation  708  has the following features: (1) generate irrational numbers without repetitive patterns in any representations; (2) resultant bits are statistical random; and (3) hardware or software implementation efficient. A square root function can generate irrational numbers and are implementation efficient. But any square root of an integer always shows repetitive patterns when represented in continued fraction. For example,  
         2     =     1   +       1     2   +            1     2   +            1     2   +            1     2   +            1     2   +            1     2   +            1     2   +   2                     …                   3     =     1   +       1     1   +            1     2   +            1     1   +            1     2   +            1     1   +            1     2   +            1     1   +   2                     …                    ,                         
 
         [0042]    Therefore, the square root function is not suitable to generate irrational numbers for cryptography. Two particularly suitable floating-point operations are cubic root and inverse cubic root.  
         [0043]    The sinusoidal function, sin(x), is used to illustrate the different functional blocks in the irrational number generator  700 . For those skilled in the art should understand that any floating-point operations can be applied to this invention and are still within the scope of this invention. The weak key filter  702  eliminates weak keys such as 0, π/2, or π for sinusoidal function, and perfect cubic or nearly perfect cubic numbers for cubic root function. After the weak key is found and then discarded or replaced, the key goes to prescale unit  704  to scale the key into a suitable range. If the key is a 48-bit integer as an input to a sinusoidal function, the accuracy of π needs to be many times of 48 bits to scale the input into the appropriate quadrant before actual calculation can be carried out. However, if the key is scaled to a 6-bit integer with 42-bit fraction, the accuracy requirement for π can be much less. After the key is pre-scaled, this key is converted into floating-point format in integer-to-floating conversion unit  7706 , and then a function sin(x) is applied to in the floating-point operation  708 . The result of the floating-point operation  708  is converted back into integer in floating-to-integer conversion unit  710  with proper post-scaling. The bit skip unit  712  receives a stream of irrational bits from the floating-to-integer conversion unit  710 . The bit skip unit  712  skips the integer portion and also the large fractional portion. Therefore, the output of the bit skip unit  712  contains a small fractional portion of the irrational bit stream. The deskew unit  714  further increases the randomness by discarding “00” or “11” and replaced “01” by “1” and “10” by 0, for example. The methods of deskewing a bit stream may vary and the different schemes of deskewing are still within the scope of this invention. The truncation unit  716  truncates the remaining fractional portion of the irrational bit stream into finite length. Not all the functional blocks in FIG. 7 are needed for a given floating-point operation. The actual implementations may vary for the functional blocks  702  through  716  and are still within the scope of the invention for those skilled in the art.  
         [0044]    An example of the floating-point operation  708  in irrational number generator  700  is illustrated as follows. The key is, for instance, 41 or 0010,1001 binary. With properly prescaled in  704  by 16, the input to the sinusoidal function is 2.5625 decimal or 10.1001 binary. The output of the sinusoidal function sin(x) in 708 is 0.547264749925465 . . . decimal, or 0.100011000001100110001010111 . . . binary. If the first 6 bits of the fraction is skipped in  712 , the result is 000001100110001010111 . . . binary. After the deskew unit 714, the result is 101000. . . .  
         [0045]    Two embodiment of the floating-point operation  708  in the irrational number generator  700  are cubic root or inverse cubic root. The cubic root or inverse cubic root functions can be implemented by either iterative method or direct bit-by-bit method.  
         [0046]    The inverse cubic root of “a” can be obtained by solving the following equation by Newton-Ralphson&#39;s iteration: 
           f ( x )=1 /x   3   −a   
         [0047]    After the initial guess x, the next iteration x′ can be found as: 
           x′=x−f ( x )/ f ′( x )= x /3(4 −ax   2 ) 
         [0048]    The initial guess can be obtained by looking up a table for accuracy up to 8 bits, for example. The first iteration will get the result accurate to 16 bits. The second and third iterations can provide accuracy up to 32 and 64 bits, respectively. The accuracy also depends on the available bits in the multiplication and addition units.  
         [0049]    Similarly, the cubic root of “a” can be calculated by solving the following equations iteratively and multiplying the result by “a”: 
           f ( x )=1 /x   3   −a   2   
         [0050]    The next result by Newton-Ralphson&#39;s method is 
           x′=x−f ( x )/ f ( x )= x /3(4 −a   2   x   2 ) 
         [0051]    After several iterations until the desired accuracy x n  is reached, the cubic root of “a” can be obtained as 
         {cube root}{square root over ( a )}= ax   n   
         [0052]    In the iterative method, calculating inverse cubic-root is simpler than cubic root by two multiplications. This iterative method can be implemented in software or firmware routines. More bits can be generated by a similar procedure.  
         [0053]    The direct bit-by-bit method can generate one bit, two bits, or more bits at a time, the so-called radix 2, 4, 8 or higher radix method. The result bits can be all positives or can be positive and negative mixed, the so-called Sweeney-Robertson-Toucher (SRT) method. The SRT method allows the resultant bits be negative, such that there can be more than one way to determine the partial resultant bits in each time. The redundant representation in SRT method offers some freedom in choosing the partial resultant bits. The partial root remainder can be negative as quite different from the regular pencil-and-paper calculation, the non-SRT method.  
         [0054]    The procedure to obtain a cubic root can be formulated as follows:  
         [0055]    Let P 0  be the number for cubic root. The partial resultant bits q 1 , q 2 , q 3  . . . are obtained one at a time. The partial result is  
                 Q   j     =       ∑     i   =   1     j            q   i          r     -   1             ,           (     eq   .              1     )                               
 
         [0056]    where r is the radix and j is the j-th calculation. The partial resultant bits are carefully chosen such that the partial root remainder 
           P   j   =r   J ( P   0   −Q   J   3 )  (eq. 2) 
         [0057]    will be minimized.  
         [0058]    Based on eq. (2), the recursive relationship between two adjacent partial remainders P j  and P j+1  can be readily known as 
           P   J+1   =rP   J   −r   J+1 ( Q   j+1   3   −Q   j   3 )  (eq. 3) 
         [0059]    The residual error in each bit calculation can be known as:  
                   P   0     3     -     Q   j       =       ∑     i   =     j   +   1       ∞            q   i          r     -   1                   (     eq   .              4     )                               
 
         [0060]    The bounds in the residual error for non-SRT methods are:  
               0   ≤         P   0     3     -     Q   j         =           ∑     i   =     j   +   1       ∞            q   i          r     -   i           &lt;       ∑     i   =     j   +   1       ∞            q   max          r     -   i             =     kr     -   j                 (     eq   .                5a       )                               
 
         [0061]    and for SRT method:  
                        P   0     3     -     Q   j            =           ∑     i   =     j   +   1       ∞            q   i          r     -   i           ≤       ∑     i   =     j   +   1       ∞            q   max          r     -   i             =     kr     -   j                 (     eq   .                5b       )                               
 
         [0062]    where q max =r−1, and k=1 for non-SRT; and q max =log 2 (r), and k=q max /(r−1) for SRT method.  
         [0063]    Based on eq. (2),(3), and (5a), the bounds for each partial remainder can be readily obtained for non-SRT method as: 
         0 ≦P   j   &lt;r   J (( Q   j   +kr   −J ) 3   −Q   j   3 )  (eq. 6a) 
         [0064]    The goal is to choose q j+1  based on Q j  and P j  such that P j+1  can satisfy the same eq. (6a) for index j+1. Substituting eq (1), (3) into eq. 6(a), the inequalities for range of P J  can be found for non-SRT as: 
           r   j [(( Q   J   +q   J+1   r   −J−1 ) 3   −Q   J   3   ]≦P   J   &lt;r   J [(( Q   j +( q   J+1   +k ) r   −J−1 ) 3   −Q   j   3 ]  (eq. 7a) 
         [0065]    The equation (7a) limits q j+1  selection based on the ranges of P j  and Q j . Particularly, for radix 2, r=2: 
           q   j+1 =1 . . . 2 j [(( Q   j +2 −j−1 ) 3   −Q   J   3   ]≦P   J &lt;2 j [(( Q   J +2 −j ) 3   −Q   J   3 ]  (eq. 8a.1) 
           q   J+1 =0 0 ≦P   J &lt;2 J [(( Q   J +2 −J−1 ) 3   −Q   J   3 ]  (eq. 8a.2) 
         [0066]    The selection rule for radix 2 non-SRT method is straight forward. The partial result bits q j+1  can be either 0 or 1 depending on the result of P J  whether or not P J  &lt;2 1 [((Q j +2 −J−1 ) 3 −Q j   3 ]. Only one subtraction is involved in determining each partial result bit. The non-restoring method can be applied: if the partial remainder is negative after one subtraction, the next round to generate the next partial remainder will be changed to addition.  
         [0067]    Similarly, for radix 4, r=4, the selection rules for q j+1  are: 
           q   j+1 =3 . . . 4 j [(( Q   J +3·4 −j−1 ) 3   −Q   J   3   ]≦P   J &lt;4 j [(( Q   J +4 −j ) 3   −Q   J   3 ]  (eq.9a) 
           q   j+1 =2 . . . 4 J [(( Q   j +2·4 −J−1 ) 3   −Q   j   3   ]≦P   j &lt;4 J [(( Q   j +3·4 −J−1 ) 3   −Q   j   3 ] 
           q   j+1 =1 . . . 4 j [(( Q   J 30 4 −j−1 ) 3   −Q   j   3   ]≦P   J &lt;4 j [(( Q   j +2·4 −j−1 ) 3   −Q   j   3 ] 
           q   j+1 =0 0 ≦P   J &lt;4 J [(( Q   J +4 −j−1 ) 3   −Q   j   3 ] 
         [0068]    To determine whether or not q j+1  is 0, 1, 2, or 3, three comparisons are needed. Each comparison would need an adder. The hardware resources consideration may not favor this approach.  
         [0069]    Instead, the SRT method of radix 4 or higher for cubic root calculation is more favorable and is shown in the following.  
         [0070]    Based on eq. (2),(3), and (5b), the bounds for each partial remainder can be readily obtained for SRT method as: 
           r   J (( Q   j   −kr   −j ) 3   −Q   j   3 )≦ P   j   ≦r   j (( Q   j   +kr   −J ) 3   −Q   j   3 )  (eq. 6b) 
         [0071]    The goal is to choose q j+1  based on Q j  and P j  such that P j+1  can satisfy the same eq. (6b) for index j+1. Substituting eq (1), (3) into eq. 6(b), the inequalities for ranges of P j  can be found as: 
           r   j [(( Q   j +( q   j+1   −k ) r   −j−1 ) 3   −Q   J   3   ]≦P   j   ≦r   j [(( Q   j +( q   j+1   +k ) r   −j−1 ) 3   −Q   j   3 ]  (eq. 7b) 
         [0072]    The equation (7b) limits the q j+1  selection based on ranges of P j  and Q j . Particularly, for radix 2, r=2 and k=1, the selection rules are: 
           q   j+1 =1 . . . 0 ≦P   J ≦2 j [(( Q   J +2 −j ) 3   −Q   J   3 ]  (eq. 8a.1) 
           q   j+1 =0 . . . 2 J [(( Q   J −2 −J−1 ) 3   −Q   J   3   ]≦P   J ≦2 J [(( Q   j +2 −J−1 ) 3   −Q   J   3 ]  (eq.8a.2) 
           q   j+1 =−1 . . . 2 j [(( Q   j −2 −j ) 3   −Q   J   3   ]≦P   J ≦0  (eq. 8a.3) 
         [0073]    The number for cubic root a=P o  can be normalized to be within ¼≦P 0 &lt;½ without loss of generality. Consequently, q 1 =1 and Q 1 =½. Based on eq. (8a. 1), (8a.2), and (8a.3), the following sets of selection criteria can be derived: 
           q   J+1 =1 if  P   j ≧0;  q   j+1 =−1 if  P   j &lt;0.  Selection criteria 1: 
           q   J+1 =1 if P J &gt;0;  q   J+1 =0 if  P   J =0;  q   J+1 =−1 if  P   J &lt;0.  Selection criteria 2: 
           q   J+1 =1 if  {tilde over (p)}   0 &amp;( p   1 |( {tilde over (p)}   2 &amp;  {tilde over (p)}   3 )); q   j+1 =0 if  {tilde over (p)}   0 &amp;  {tilde over (p)}   1 &amp;( {tilde over (p)}   2   |{tilde over (p)}   3 ); q   J+1 =−1 if  p   0 ,  Selection criteria 3: 
         [0074]    where P J =P 0 .P 1 P 2 P 3  . . . in 2&#39;s complement, &amp; and | are AND and OR in Boolean operations.  
         [0075]    The same treatment can be extended to radix 4 through more elaboration. The number for cubic root a=P 0  can be normalized to be within {fraction (1/64)}≦P 0 &lt;⅛ and ¼≦Q&lt;½ without loss of generality. Consequently, q 1 =1 and Q 1 =¼. For radix 4, r=4 and k=⅔, the selection rules for q j+1  are:  
                     q     j   +   1       =   2                            4   j          [     (         (       Q   j     +       4   3          4       -   j     -   1           )     3     -     Q   j   3         ]       ≤                                              P   j     ≤       4   j     [     (         (       Q   j     +       8   3          4       -   j     -   1           )     3     -     Q   j   3             ]                   q     j   +   1       =   1                            4   j          [     (         (       Q   j     +       1   3          4       -   j     -   1           )     3     -     Q   j   3         ]       ≤                                              P   j     ≤       4   j     [     (         (       Q   j     +       5   3          4       -   j     -   1           )     3     -     Q   j   3             ]                   q     j   +   1       =   0                            4   j          [     (         (       Q   j     -       2   3          4       -   j     -   1           )     3     -     Q   j   3         ]       ≤                                                    P   j     ≤       4   j     [     (         (       Q   j     +       2   3          4       -   j     -   1           )     3     -     Q   j   3               ]                   q     j   +   1       =     -   1                              4   j          [     (         (       Q   j     -       5   3          4       -   j     -   1           )     3     -     Q   j   3         ]       ≤                                              P   j     ≤       4   j     [     (         (       Q   j     -       1   3          4       -   j     -   1           )     3     -     Q   j   3             ]                   q     j   +   1       =     -   2                              4   j          [     (         (       Q   j     -       8   3          4       -   j     -   1           )     3     -     Q   j   3         ]       ≤                                              P   j     ≤       4   j     [     (         (       Q   j     -       4   3          4       -   j     -   1           )     3     -     Q   j   3             ]                   (     eq   .                 9b.1-5       )                               
 
         [0076]    [0076]FIG. 9 is a table showing a selection table based on selection rules illustrated in eq . (9b. 1-9b.5). Four bits of Q j =0.01a 0 a 1 a 2 a 3  and 9 bits of P J =P 0 .P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8  . . . are sufficient to look up a table to determine q j+1 , where p 0  is the sign bit in the 2&#39;s complement format. Three cells have different values for j=2 than the others j&#39;s. Note that some cells may have more than one selections. This is a unique property of the SRT method.  
         [0077]    The selection criteria can be readily deducted from the Table 1 as:  
         [0078]    # p j =[p0,p1,p2,p3,p4,p5,p6,p7,p8] and q j =[a0 a1 a2 a3]. 0 is MBS  
         [0079]    # SRT-4 method for Cubic Root  
         [0080]    # {fraction (1/64)}&lt;=p j &lt;⅛, ¼&lt;=q j &lt;½ 
         [0081]    if(p J &lt;=255)  
         [0082]    if (p j &lt;=4+qj) q=0;  
         [0083]    else if(q J ==0 &amp;&amp; p J &lt;=19) q=1;  
         [0084]    else if(q j &lt;=2 &amp;&amp; p j &lt;=(18+3*q j )) {q=1; } 
         [0085]    else if(q j &lt;=6 &amp;&amp; p J &lt;=(26+3*(q J −3)) ) q=1;  
         [0086]    else if(q j &gt;=7 &amp;&amp; p J &lt;=(34+4*(q J −6))) q=1;  
         [0087]    else q=2;  
         [0088]    if(p J &gt;255) # P J &lt;0  
         [0089]    {p J =512−p J ;  
         [0090]    if (p J &lt;=6+q J ) q=0;  
         [0091]    else if(q J ==0 &amp;&amp; p j &lt;=19) q=−1;  
         [0092]    else if(q j &lt;=3 &amp;&amp; p j &lt;=(21+2*(q j −1))) q=−1;  
         [0093]    else if(q j &lt;=7 &amp;&amp; p J &lt;=(28+3*(q j −4))) q=−1;  
         [0094]    else if(q J &gt;=8 &amp;&amp; p J &lt;=(41+4*(q J −8))) q=−1;  
         [0095]    else q=−2;  
         [0096]    if (j==2 &amp;&amp; q j ==1 &amp;&amp; p j ==21) q=−2; #491  
         [0097]    if (j==2 &amp;&amp; q j ==0 &amp;&amp; p j ==19) q=−2; #493  
         [0098]    if (j==2 &amp;&amp; q j ==0 &amp;&amp; p j ==18) q=−2; #494  
         [0099]    The procedure to calculate the resultant bits of a cubic root can be formulated step-by-step as:  
         [0100]    1. Scale P 0  to be within 1/r 3 &lt;=P 0 &lt;8/r 3  so that 1/r&lt;=Q&lt;2/r;  
         [0101]    2. q 1 =1; Q 0 =0; Q 2   0 =0; j=1; qbit=1/r; #qbit holds the bit position  
         [0102]    3. qqbit=q J *qbit;  
         [0103]    4. Q j =Q j−1 +qqbit; #partial results  
         [0104]    5. Q 2   j =Q 2   j−1 +2* Q j−1 *qqbit+qqbit*qqbit; #sqare of partial results  
         [0105]    6. P 1 =r*P j−1 (3*Q 2   j−1 +3* Q j−1 *qqbit+qqbit*qqbit)*q j ; #partial remainder  
         [0106]    7. q j+1 =select (P j , Q j ,j);  
         [0107]    8. qbit=qbit/r; j=j+1  
         [0108]    9. Go to step 3 until sufficient bits are obtained.  
         [0109]    This procedure can continue until the desirable bits are obtained. Note that the partial remainder in the last step could be negative, such that the final partial result may be larger than the actual result. This is quite different from the non-SRT method that the final partial result is always less than the actual number. Some adjustment and rounding may be necessary. For some P J , Q J , there may be more than one selection. For cryptography, there is a need to standardize the selection table. One example is to select those partial results that are close to zero.  
         [0110]    The partial results from the SRT method may have positive and negative bits. The final cubic-root can be obtained by subtracting the positive bits by the negatives. This may involve very long bit length of subtraction, which may take a substantial amount of time to calculate.  
         [0111]    One embodiment to reduce computation is to subtract the two types of bits for some block size at a time, 64 bits for example. An alternative embodiment is to exclusive-OR the two types of bits. Of course, the resultant bits of these two embodiments will not be identical to the cubic root.  
         [0112]    The process of cubic root can be implemented in hardware. FIG. 9 is a diagram illustrating an examplary hardware embodiment of cubic root process of the present invention. The registers  902 ,  904 ,  906  store Q J , P J , and Q 2   J , the partial result, partial remainder, and square of the partial result, respectively, at j-th clock cycle. After each calculation, they will be updated in the same registers with index j+1. The Q 1  and Q 2   j  are initialized to 1/r and 1/r 2 , respectively, when P 0  is scaled to be within [1/r 3 , 2/r 3 ). The qb most significant bits of Q J , and pb most significant bits of P j , are used to index a lookup table  900  for the next q j+1 . The lookup table can be implemented in ROM, RAM, PLA, flash, or random logic, for example. Each box in registers  902 ,  904 , and  906  represents r bits according to radix r SRT method. Updating Q register  902  is straight-forward by placing the new q j+1  in proper bit position, namely r(j+1)-th bits from the left. The Q 2  register  906  can be updated by adding 2·Q j ·q j+1  and q 2   j+1  in an adder  908 . Adding q 2   j+1  is simply putting q 2   j+1  in 2r(j+1)-th bit position from the left. Adding 2·Q j ·q j+1  may need shifting and a few additions depending on how high the radix r is. Similarly, the P register  904  can be updated at the same time as the Q register  906  in a four-operand adder  910 . When both Q J+1  and P J+1  are available, the q J+2  can be indexed in the next clock cycle to get the next r bits. The control logic  912  designed in state machines controls the operations in updating registers, indexing lookup table to generate r bits every clock.  
         [0113]    Although the present invention has been described in terms of specific embodiment, it is anticipated that alterations and modifications thereof will no doubt become apparent to those skilled in the art. It is therefore intended that the following claims be interpreted as covering all such alterations and modifications as falls within the true spirit and scope of the invention.