Method for exponentiating in cryptographic systems

• US 5,299,262 A
• Filed: 08/13/1992
• Issued: 03/29/1994
• Est. Priority Date: 08/13/1992
• Status: Expired due to Term

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: United States Department of Energy
• Inventors: McCurley, Kevin S., Gordon, Daniel M., Brickell, Ernest F.
• Primary Examiner(s): Swann, Tod R.
• Application Number:
  US07/929,929
• Time in Patent Office: 593 Days
• Field of Search: 380/28, 380/30, 380/50, 380/49
• US Class Current: 380/28
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

An improved cryptographic method utilizing exponentiation is provided which has the advantage of reducing the number of multiplications required to determine the legitimacy of a message or user. The basic method comprises the steps of selecting a key from a preapproved group of integer keys g; exponentiating the key by an integer value e, where e represents a digital signature, to generate a value g^e ; transmitting the value g^e to a remote facility by a communications network; receiving the value g^e at the remote facility; and verifying the digital signature as originating from the legitimate user. The exponentiating step comprises the steps of initializing a plurality of memory locations with a plurality of values g^xi ; computi

The United States Government has rights in this invention pursuant to Contract No. DE-AC04-76DP00789 between the Department of Energy and AT&T Company.

Claims

1. In a cryptographic system, a method for transforming a first signal into a second signal in a manner infeasible to invert, said method comprising the steps of:

(a) prestoring in a computing device a plurality of values g^x.sbsp.i in a plurality of memory locations within said computing device where x_i is selected such that an integer e=Σ

a_i x_i, where a_i is an integer weight such that 0≦

a_i ≦

h, and h is a positive integer, and g is a fixed signal unique to said cryptographic system;

(b) representing a first randomly generated input digital signal as said integer e;

(c) exponentiating said fixed signal, g, by the said integer e to generate said second signal, y=g^e, wherein said step of exponentiating further comprises;

for each integer d with 1≦

d≦

h, computing the individual values of c_d =π

_a.sbsb.i_=d g^x.sbsp.i, i.e., c_d will be the product of all the said values g^x.sbsp.i, for the said memory locations, i, for which the value a_i is equal to d;

computing the product, ##EQU3## for the said individual values, c_d to thereby determine a value for said second signal, y=g^e.

2. The method recited in claim 1 wherein said step of computing the product of π

_d=1^h C_d^d further comprising selecting positive integers r and s so that r+s=h, and

setting C_r =C_r C_h ;

setting C_s =C_s C_h ; and

setting C_i =C_i for 1≦

i≦

h-1, i≠

r or s

computing π

_d=1^h-1 C_d^d

which equals;

##EQU4##

3. The method of claim 1, where the set x_i is selected according to the rule x_i =mb^k and where b represents an integer base and the values of m are selected from a set M and the values for k are greater than or equal to 0 less than or equal to 1+ log_b N , where N is the maximum possible value for the integer e, and the set M is chosen so that the set of integers jm, where m varies over the elements of M, and j varies between 0 and a predetermined integer h, is a basic digit set.

4. A method for generating digital signatures to assure the legitimacy of a message, said method comprising the steps of:

(a) prestoring in a computing device a plurality of values g^x.sbsp.i in a plurality of memory locations within said computing device where x_i is selected such that an integer e=Σ

a_i x_i, where a_i is an integer weight such that 0≦

a_i ≦

h, and h is a positive integer, and g is fixed signal unique to said digital signature method;

(b) representing a first randomly generated input digital signal as said integer e;

(c) exponentiating said fixed signal, g, by the said integer e to generate a second signal, y=g^e, wherein said step of exponentiating further comprises;

for each integer d with 1≦

d≦

h, computing the individual values of c_d =π

_a.sbsb.i_=d g^x.sbsp.i, i.e., c_d will be the product of all the said values g^x.sbsp.i, for the said memory locations, i, for which the value a_i is equal to d;

computing the product, ##EQU5## for the said individual values, c_d to thereby determine a value for said second signal, y=g^e.,

(d) generating a digital signature, s, of a message, m, using said second signal, y, and particular inputs specified by a particular digital signature scheme; and

(e) verifying said digital signature, s, as originating from said legitimate user.

5. The method recited in claim 4 wherein said step of computing the product of π

_d=1^h C_d^d further comprising selecting positive integers r and s so that r+s=h, and

setting C_r =C_r C_h ;

setting C_s =C_s C_h ; and

setting C_i =C_i for 1≦

i≦

h-1, i≠

r or s

computing π

_d=1^h-1 C_d^d

which equals;

##EQU6##

6. The method of claim 4, where the set x_i is selected according to the rule x_i =mb^k and where b represents an integer base and the values of m are selected from a set M and the values for k are greater than or equal to 0 less then or equal to 1+ log_b N , where N is the maximum possible value for the integer e, and the set M is chosen so that the set of integers jm, where m varies over the elements of M, and j varies between 0 and a predetermined integer h, is a basic digit set.

7. A method for verifying of an individual or device, said method comprising the steps of:

(a) prestoring in a computing device a plurality of values g^x.sbsp.i in a plurality of memory locations within said computing device where x_i is selected such that an integer e=Σ

a_i x_i, where a_i is an integer weight such that 0≦

a_i ≦

h, and h is a positive integer, and g is fixed signal unique to said verification method

(b) representing a first randomly generated input digital signal as said integer e;

(c) exponentiating said fixed signal, g, by the said integer e to generate a second signal, y=g^e, wherein said step of exponentiating further comprises;

for each integer d with 1≦

d≦

h, computing the individual values of C_d =π

_a.sbsb.i_=d g^x.sbsp.i, i.e., C_d will be the product of all the said values g^x.sbsp.i, for the said memory locations, i, for which the value a_i is equal to d;

computing the product, ##EQU7## for the said individual values, c_d to thereby determine a value for said second signal, y=g^e ;

(d) sending said second signal, y, to a verifier;

(e) receiving a third signal, z, from the verifier;

(f) generating a fourth signal, x, using said second signal, said third signal, and other inputs as specified by a particular identification scheme; and

(g) verifying said fourth signal as originating from said individual or device.

8. The method recited in claim 7 wherein said step of computing the product of π

_d=1^h c_d^d further comprising selecting positive integers r and s so that r+s=h, and

setting C_r =C_r C_h ;

setting C_s =C_s C_h ; and

setting C_i =C_i for 1≦

i≦

h-1, i≠

r or s

computing π

_d=1^h-1 c_d^d

which equals;

##EQU8##

9. The method of claim 7, where the set x_i is selected according to the rule x_i =mb^k and where b represents an integer base and the values of m are selected from a set M and the values for k are greater than or equal to 0 less than or equal to 1+ log_b N , where N is the maximum possible value for the integer e, and the set M is chosen so that the set of integers jm, where m varies over the elements of M, and j varies between 0 and a predetermined integer h, is a basic digit set.