Partial modular reduction method

Claim 2

In a cryptosystem, a method for inverting a cryptovariable comprising inputting said cryptovariable and representing it as an integer; constructing an approximate inverse to said integer; computing a residual of said inverse by taking a twos complement of a product of said integer with said inverse; testing a spill word included in said residual; improving the accuracy of said inverse until said spill word is zero; partial multiplying said inverse by said residual and adding a shift of said inverse; repeating until desired length and accuracy is obtained; and outputting said inverse.

Claim 3

The method of claim 1 further comprising testing said cryptovariable for maximal condition; using iterations which assure that said spill word will be zero; and using a partial multiply to compute said residual.

Claim 4

The method of claim 1 further comprising shortening said cryptovariable for intermediate results.

Claim 5

The method of claim 1 further comprising truncating said inverse to reduce precision.

Claim 6

The method of claim 1 further comprising representing said inverse in terms of a base and using a power of said base to obtain said approximate inverse.

Claim 7

The method of claim 1 further comprising a sequence of logarithms 2, 3, 4, 6, 10, 18, 34 . . . as lengths for iterations of said inverse.

Claim 8

The method of claim 1 where said cryptosystem is of modular exponential type and said cryptovariable is a modulus.

Claim 9

The method of claim 1 further comprising using said inverse for the modular reduction of other cryptovariables and products of cryptovariables.

Claim 10

In a cryptosystem, a method for modular reduction comprising inputting a modulus; inputting an inverse to said modulus; inputting a cryptovariable; partial multiplying said cryptovariable by said inverse to obtain an integer quotient; partial multiplying said integer quotient by said modulus and partial subtracting from said cryptovariable to obtain a partial residue.

Claim 11

In a cryptosystem, a method for modular reduction comprising inputting a modulus; inputting an inverse to said modulus; inputting a cryptovariable; partial multiplying said cryptovariable by said inverse to obtain an integer quotient; partial multiplying said integer quotient by said modulus and partial subtracting from said cryptovariable to obtain a partial residue.

Claim 12

The method of claim 9 further comprising testing a spill word of said partial residue; partial subtracting said modulus from said partial residue if said spill word is nonzero; and repeating until said spill word is zero.

Claim 13

The method of claim 10 further comprising testing said modulus and said inverse for a condition that assures that said spill word will be zero.

Claim 14

The method of claim 9 further comprising computing said inverse from said modulus.

Claim 15

The method of claim 9 further comprising testing said cryptovariable for a condition that assures that a quotient spill word will be zero.

Claim 16

The method of claim 9 further comprising obtaining said cryptovariable by multiplying two other cryptovariables.

Claim 17

The method of claim 9 further comprising obtaining said cryptovariable by multiplying two other cryptovariables with a subquadratic multiplier.

Claim 18

The method of claim 9 further comprising testing for a leading one in said inverse; copying words from said cryptovariable to achieve multiplication by one; and accumulating other products to said copied words in order to obtained said quotient.

Claim 19

The method of claim 9 further comprising shifting said inverse so that storage requirements are reduced for said inverse; and shifting the product of said shifted inverse to obtain said quotient.

Claim 20

The method of claim 9 further comprising comparing said partial residue to said modulus and possibly subtracting, whereby resultant residue is fully reduced and less than said modulus.

Claim 21

The method of claim 9 further comprising repeating said partial multiplying and subtracting for further modular reduction, and conditionally subtracting said modulus to achieve full reduction.

Claim 22

The method of claim 9 further comprising generating public key messages.

Claim 25

The system of claim 21 further comprising means for testing a spill word of said partial residue; means for partial subtracting said modulus from said partial residue if said spill word is nonzero; and means to repeat until said spill word is zero.

Claim 26

The system of claim 22 further comprising means for testing said modulus and said inverse for a condition that assures that said spill word will be zero.

Claim 27

The system of claim 21 further comprising a subquadratic multiplier.

Claim 28

The system of claim 21 further comprising means for conditionally subtracting said modulus from said partial residue and output a fully reduced residue.

Claim 31

The method of claim 26 wherein said size test is for a zero among the most significant several bits in said modulus.

Claim 32

The method of claim 26 wherein said size test guarantees that a modular reduction spill word is zero.

Claim 33

The method of claim 26 further comprising testing said modulus for primality.

Claim 34

The method of claim 26 further comprising choosing said modulus to have a multiplicative subgroup whose order is a prime of at least 160 bits.

Claim 35

The method of claim 26 further comprising choosing DSA parameters according to NIST secure modulus method.

Claim 36

The method of claim 26 where said inverse can be stored compactly and still have sufficient accuracy for said size test.

Claim 37

A cryptosystem, comprising means to input a cryptovariable; means to multiply said cryptovariable to form a product; a modulus means; means to reduce the product with respect to said modulus means; and said modulus means having an input port for setting the modulus equal to the prime __________________________________________________________________________ 98A3DF52 AEAE9799 325CB258 D767EBD1 F4630E9B 9E21732A 4AFB1624 BA6DF911 466AD8DA 960586F4 A0D5E3C3 6AF09966 0BDDC157 7E54A9F4 02334433 ACB14BCB. __________________________________________________________________________

Claim 38

A cryptosystem, comprising means to input a cryptovariable; means to multiply said cryptovariable to form a product; a modulus means; means to reduce the product with respect to said modulus means; and said modulus means having an input port for setting the modulus equal to the prime __________________________________________________________________________ 98A3DF52 AEAE9799 325CB258 D767EBD1 F4630E9B 9E21732A 4AFB1624 BA6DF911 466AD8DA 960586F4 A0D5E3C3 6AF09966 0BDDC157 7E54A9F4 02334433 ACB14BCB. __________________________________________________________________________

Claim 39

The cryptosystem of claim 33 wherein said cryptosystem is based on the discrete logarithm problem.

Claim 40

The cryptosystem of claim 33 wherein said cryptosystem is based on elliptic curves.

Claim 41

The cryptosystem of claim 33 further comprising the multiplicative group with prime order ______________________________________ BB5DFE42 DE115C00 DB5EF1B0 388344D6 C15485AD ______________________________________ and generator __________________________________________________________________________ 5D9E9D4C 6EF57E63 67659293 45D2FA1F 40D84922 37BA8BDA 1E3A3FBC 6FCB118F 991EA62B 256BAB43 8BE5F2CE 979466A6 EDD266BA 1AD0B9D7 B97E5565 25A00A76. __________________________________________________________________________

Claim 42

A cryptosystem, comprising means to input a cryptovariable; means to multiply said cryptovariable to form a product; modulus means; means to reduce the product with respect to said modulus means; and said modulus means having an input port for setting the modulus equal to the prime __________________________________________________________________________ 93E8965D AFD9DFEC FD00B466 B68F90EA 68AF5DC9 FED91527 8D1B3A13 7471E655 96C37FED 0C7829FF 8F8331F8 1A270043 8ECDCC09 447DC397 C685F397 294F722B CC484AED F28BED25 AAAB35D3 5A65DB1F D62C9D7B A55844FE B1F9401E 67134093 3EE43C54 E4DC4594 00D7AD61 248B83A2 624835B3 1FFF2D95 95A5B90B 276E44F9. __________________________________________________________________________

Claim 43

A cryptosystem, comprising means to input a cryptovariable; means to multiply said cryptovariable to form a product; modulus means; means to reduce the product with respect to said modulus means; and said modulus means having an input port for setting the modulus equal to the prime __________________________________________________________________________ 93E8965D AFD9DFEC FD00B466 B68F90EA 68AF5DC9 FED91527 8D1B3A13 7471E655 96C37FED 0C7829FF 8F8331F8 1A270043 8ECDCC09 447DC397 C685F397 294F722B CC484AED F28BED25 AAAB35D3 5A65DB1F D62C9D7B A55844FE B1F9401E 67134093 3EE43C54 E4DC4594 00D7AD61 248B83A2 624835B3 1FFF2D95 95A5B90B 276E44F9. __________________________________________________________________________

Claim 44

The cryptosystem of claim 37 wherein said cryptosystem is based on the discrete logarithm problem.

Claim 45

The cryptosystem of claim 37 wherein said cryptosystem is based on elliptic curves.

Claim 46

The cryptosystem of claim 37 further comprising the multiplicative group with prime order ______________________________________ BB5DFE42 DE115C00 DB5EF1B0 388344D6 C15485AD ______________________________________ and generator __________________________________________________________________________ 69279F8E BAB80E8F 24F01846 2196636C 4C225464 F0133E0F 2F21E7BB ED1D853F 06EB949A 86850A30 A9B5B2CE A830EAAD 00E7BDF6 1EBC81CC 41DEBAFF 1B5BFD9F 2AA4B113 29B13C3D C6951127 FBC86B4D 3533823B F97A58DE 2FF1F9C9 B3177BA3 494ED5E0 00383DBD 6A699D57 89548FCE F507368E 4BE66EEB 0F087573 8CBCFCC5. __________________________________________________________________________

Claim 47

In a modulus-based cryptosystem, a system for representing residue classes comprising a modulus; a bound greater than said modulus, not necessarily explicit; a nonassociative semigroup operation on nonnegative integers less than said bound; and a nonassociative semigroup operation compatible with modular multiplication.

Claim 48

In a modulus-based cryptosystem, a system for representing residue classes comprising a modulus; a bound greater than said modulus, not necessarily explicit; a nonassociative semigroup operation on nonnegative integers less than said bound; and a nonassociative semigroup operation compatible with modular multiplication.

Claim 49

The system of claim 41 wherein said bound is chosen depending on said modulus to guarantee quotient and residue spill words are zero in said nonassociative semigroup operation.

Claim 50

The system of claim 41 wherein said bound is a power of two.

Claim 51

The system of claim 41 further comprising means to extract modular exponentials of cryptovariables with respect to said modulus.

Claim 52

The system of claim 41 further comprising means to change said modulus.

Claim 53

In a cryptosystem, a method for constructing a nonassociative semigroup comprising inputting a modulus; proving existence of a bound greater than said modulus; operating on integers less than said bound by multiplication followed by partial modular reduction; generating said nonassociative semigroup with integers less than said modulus.

Claim 54

In a cryptosystem, a method for constructing a nonassociative semigroup comprising inputting a modulus; proving existence of a bound greater than said modulus; operating on integers less than said bound by multiplication followed by partial modular reduction; generating said nonassociative semigroup with integers less than said modulus.

Claim 55

The method of claim 46 further comprising calculating a modular exponential by first calculating in said nonassociative semigroup and then fully reducing the result.

Claim 56

The method of claim 46 further comprising generating public key messages.