Modular exponentiation and reduction device and method

Claim 2

In a public key cryptosystem of modular exponential type, a method for processing cryptographic variables comprising the steps of transforming said cryptographic variables into large integers, using one of said integers as the modulus, using an approximate inverse to said modulus, using the method of repeated squaring, shifting, and multiplying for computing an exponential, incomplete modular reducing at each stage to generate an approximate residue, using an array subtracter to generate a final residue from said modulus and said approximate residue, and transforming said final residue into an output cryptographic variable.

Claim 3

The method of claim 1 wherein squaring is performed by a partial array multiplier and by doubling certain terms.

Claim 4

The method of claim 1 further comprising reducing the number of multiplications and modular reductions by using selected precomputed powers.

Claim 5

The method of claim 1 further comprising transforming said modulus into said approximate modulus inverse.

Claim 6

The method of claim 1 further comprising inverting using Newton's method.

Claim 7

The method of claim 1 further comprising generating digital signatures, authentications, or related public key signals.

Claim 8

In a public key cryptosystem of modular exponential type, a method for processing cryptographic variables comprising the steps of transforming said cryptographic variables into large integers, multiplying said large integers to yield an even larger integer, using another said large integer as a modulus, having a precomputed approximate modulus inverse to said modulus, performing an incomplete modular reduction on said larger integer by using a partial array multiplier to generate an approximate quotient from an input signal and said modulus inverse, and using a partial array multiplier and an array subtracter to generate an approximate residue from said modulus, said input, and said approximate quotient.

Claim 9

In a public key cryptosystem of modular exponential type, a method for processing cryptographic variables comprising the steps of transforming said cryptographic variables into large integers, multiplying said large integers to yield an even larger integer, using another said large integer as a modulus, having a precomputed approximate modulus inverse to said modulus, performing an incomplete modular reduction on said larger integer by using a partial array multiplier to generate an approximate quotient from an input signal and said modulus inverse, and using a partial array multiplier and an array subtracter to generate an approximate residue from said modulus, said input, and said approximate quotient.

Claim 10

The method of claim 7 wherein using an array subtracter to generate an exact residue from said modulus and said approximate residue.

Claim 11

The method of claim 7 wherein said method uses shifting to align intermediate quantities.

Claim 12

The method of claim 7 wherein said precomputed approximate modulus inverse has been truncated based on the favorable position of zeros.

Claim 13

The method of claim 7 wherein said method uses full array multiplying instead of partial array multiplying.

Claim 14

The method of claim 7 wherein using said modular reducing for public key encrypting and decrypting.

Claim 15

The method of claim 7 further comprising generating digital signatures, authentications, or related public key signals.

Claim 16

Apparatus for processing an ordinary digital signal comprising means for representing said digital signal inputs as large integers stored in register arrays, one or more register adder circuits, one or more register subtracter circuits, one or more register multiplier circuits, one or more partial array multipliers using said multiplier circuit(s) and said adder circuit(s), one or more array subtracters using said subtracter circuit(s), having a precomputed approximate modulus inverse, means for multiplying two of said large integers, means for incomplete modular reduction using said partial array multiplier and said array subtracter, means for modular exponentiation using said partial array multiplier, said incomplete modular reduction, and said array subtracter, and means for representing output large integer as a digital signal.

Claim 17

Apparatus for processing an ordinary digital signal comprising means for representing said digital signal inputs as large integers stored in register arrays, one or more register adder circuits, one or more register subtracter circuits, one or more register multiplier circuits, one or more partial array multipliers using said multiplier circuit(s) and said adder circuit(s), one or more array subtracters using said subtracter circuit(s), having a precomputed approximate modulus inverse, means for multiplying two of said large integers, means for incomplete modular reduction using said partial array multiplier and said array subtracter, means for modular exponentiation using said partial array multiplier, said incomplete modular reduction, and said array subtracter, and means for representing output large integer as a digital signal.

Claim 18

The apparatus of claim 14 wherein several of said register adders, subtracters, and multipliers act in parallel.

Claim 19

The apparatus of claim 14 further comprising the means to use selected precomputed powers to reduce the number of multiplications and modular reductions.

Claim 20

The apparatus of claim 14 further comprising the means to transform an input modulus into said approximate modulus inverse.

Claim 21

The apparatus of claim 14 implemented as a custom or semi-custom integrated circuit.

Claim 22

System for incomplete modular reduction of cryptographic variables, comprising a large integer as a modulus, a precomputed approximate modulus inverse to said modulus, a partial array multiplier to generate an approximate quotient from one of said cryptographic variables and said modulus inverse, and a partial array multiplier and an array subtracter to generate an approximate residue from said modulus, an input, and said approximate quotient.

Claim 23

System for incomplete modular reduction of cryptographic variables, comprising a large integer as a modulus, a precomputed approximate modulus inverse to said modulus, a partial array multiplier to generate an approximate quotient from one of said cryptographic variables and said modulus inverse, and a partial array multiplier and an array subtracter to generate an approximate residue from said modulus, an input, and said approximate quotient.

Claim 24

The system of claim 19 further comprising means to accept the modulus as an input, and means to transform said modulus into said approximate modulus inverse.

Claim 25

The system of claim 19 further comprising means to convert said approximate residue to an exact residue.

Claim 26

The system of claim 19 wherein said system is a modular reduction stage in a public key cryptosystem of modular exponential type.

Claim 27

The system of claim 19 wherein said system is used to generate digital signatures, authentications, or related public key signals.

Claim 28

A partial array multiplier, comprising registers for storing inputs, means for storing a carry bit, initially zero, means for multiplying two registers and putting the product in two output registers, means for adding said carry bit to the more significant of said output registers, and an adder which stores resultant carry in said carry bit storage.

Claim 29

A partial array multiplier, comprising registers for storing inputs, means for storing a carry bit, initially zero, means for multiplying two registers and putting the product in two output registers, means for adding said carry bit to the more significant of said output registers, and an adder which stores resultant carry in said carry bit storage.