Technique for reducing RSA Crypto variable storage

In a public key cryptosystem of the modulo exponentiation type whose modulus is the product of two prime binary numbers P and Q, a method of generating at least one of the primes P and the modulus, comprising the steps of:

• supplying a secret x-bit first binary number X;
• supplying a nonsecret d-bit second binary number D;
• expanding the bit size of X according to a predefined nonsecret function using binary number D to generate said prime number P,
• dividing a predetermined constant by said prime number P to produce a quotient;
• expanding the bit size of said quotient according to a predefined nonsecret function using binary number D to generate said prime number Q;
• and
• multiplying said prime numbers P and Q together to produce a product which is said modulus.

A method of transmitting a public key and modulus to a requesting user from a key distribution center, said public key and modulus being used in a public key cryptosystem of the modulo exponentiation type whose modulus is the product of two prime binary numbers, said method of transmitting comprising the steps of:

• providing a non-secret cryptovariable having a number of bits m less than the number of bits n of either of said public key and modulus;
• transmitting said cryptovariable together with a user identification and sequence number and a number of bits to pad the transmitted block to a total of n bits;
• expanding the received cryptovariable using a predefined nonsecret function to provide said public key and modulus, and
• wherein said step of providing said nonsecret cryptovariable is performed using a trial and error technique and n=400 bits and m=260 bits.

A method of transmitting a public key and modulus to a requesting user from a key distribution center, said public key and modulus being used in a public key cryptosystem of the modulo exponentiation type whose modulus is the product of two prime binary numbers, said method of transmitting comprising the steps of:

• providing a non-secret cryptovariable having a number of bits m less than the number of bits n of either of said public key and modulus;
• transmitting said cryptovariable together with a user identification and sequence number and a number of bits to pad the transmitted block to a total of n bits;
• expanding the received cryptovariable using a predefined nonsecret function to provide said public key and modulus, and
• wherein said step of providing said nonsecret cryptovariable is performed by generating an n-bit modulus N as the function of CR+S of a nonsecret r-bit first binary number R, a non-secret s-bit second binary number S, and a c-bit system constant C where s<c+r.

In public key cryptosystem of the modular exponentiation type, a method of generating an n-bit modulus N as the function CR+S of a nonsecret r-bit first binary number R, a nonsecret s-bit second binary number S, and a c-bit system constant C, where s<c+r, said method comprising the steps of

• supplying the nonsecret r-bit first binary number R,
• supplying the nonsecret s-bit second binary number S,
• multiplying R by the c-bit system constant C, and
• adding S to the product RC to form N.

In a public key cryptosystem of the modulo exponentiation type whose modulus is the product of two prime binary number P and Q, a method of generating a cryptovariable corresponding to at least one of the primes P in the modulus comprising the steps of:

• arbitrarily choosing a secret x-bit first binary number X;
• selecting a nonsecret d-bit binary number D which when used with a computation function produces a trial value for said prime number P;
• testing said trial value for primality, and if the test for primality fails, selecting another nonsecret d-bit binary number until all possible values of D have been exhausted or said trial value passes the test for primality, but if all possible values of D have been exhausted and said trial value fails the test for primality, choosing a different X and repeating the steps of selecting and testing until said trial value passes the test for primality,
• dividing a predetermined constant by a trial value of P which has passed the test for primality to produce a quotient;
• and
• choosing said d-bit number D such that when used with said computation function to expand said quotient a second trial value for Q is produced;
• and
• testing said second trial value for primality, and if said second trial value fails the test for primality, choosing a different number D until all possible values of D are exhausted or said second trial value passes the test of primality, but if all possible values of D are exhausted, then selecting a new number X and repeating the steps of selecting the number D until both said first and second trial values pass the test of primality.