[US Patent & Trademark Office, Patent Full Text and Image Database]
[Home] [Boolean Search] [Manual Search] [Number Search] [Help]
[HIT_LIST] [Bottom]
[View Shopping Cart] [Add to Shopping Cart]
[Image]
( 1 of 1 )
-------------------------------------------------------------------------------
United States Patent 5,848,159
Collins , et al. December 8, 1998
-------------------------------------------------------------------------------
Public key cryptographic apparatus and method
Abstract
A method and apparatus are disclosed for improving public key encryption and
decryption schemes that employ a composite number formed from three or more
distinct primes. The encryption or decryption tasks may be broken down into
sub-tasks to obtain encrypted or decrypted sub-parts that are then combined
using a form of the Chinese Remainder Theorem to obtain the encrypted or
decrypted value. A parallel encryption/decryption architecture is disclosed to
take advantage of the inventive method.
-------------------------------------------------------------------------------
Inventors: Collins; Thomas (Saratoga, CA); Hopkins; Dale (Gilroy, CA); Langford;
Susan (Sunnyvale, CA); Sabin; Michael (Sunnyvale, CA)
Assignee: Tandem Computers, Incorporated (Cupertino, CA)
Appl. No.: 784453
Filed: January 16, 1997
Current U.S. Class: 380/30; 380/29; 380/277; 705/64; 713/174
Intern'l Class: H04L 009/30; H04L 009/00
Field of Search: 380/9,28,29,30,49,50
-------------------------------------------------------------------------------
References Cited [Referenced By]
-------------------------------------------------------------------------------
U.S. Patent Documents
4200770 Apr., 1980 Hellman et al..
4218582 Aug., 1980 Hellman et al..
4405829 Sep., 1983 Rivest et al..
4424414 Jan., 1984 Hellman et al..
4514592 Apr., 1985 Kawamura et al. 380/28.
4995082 Feb., 1991 Schnorr 380/23.
5046094 Sep., 1991 Kawamujra et al. 380/28.
5321752 Jun., 1994 Iwamura et al. 380/28.
5351298 Sep., 1994 Smith 380/30.
Other RSA Moduli Should Have 3 Prime Factors* by Captain Nemo, No
References Date or Publication Given.
International Search Report (PCT), ISA/US; Apr. 6, 1998.
Primary Examiner: Gregory; Bernarr E.
Attorney, Agent or Firm: Bennett, Esq.; Robert J. Townsend & Townsend & Crew
LLP
-------------------------------------------------------------------------------
Claims
-------------------------------------------------------------------------------
What is claimed:
1. A method for establishing cryptographic communications comprising the step
of:
encoding a plaintext message word M to a ciphertext word signal C, where M
corresponds to a number representative of a message and
0.ltoreq.M.ltoreq.n-1
n being a composite number formed from the product of p.sub.1 .multidot.p.sub.2
.multidot.. . . .multidot.p.sub.k where k is an integer greater than 2,
p.sub.1, p.sub.2, . . . p.sub.k are distinct prime numbers, and where C is a
number representative of an encoded form of message word M, wherein said
encoding step comprises the step of:
transforming said message word signal M to said ciphertext word signal C
whereby
C=M.sup.e (mod n)
where e is a number relatively prime to (p.sub.1 -1).multidot.(p.sub.2 -1).
2. The method according to claim 1, comprising the further step of:
decoding the ciphertext word signal C to the message word signal M, wherein
said decoding step comprises the step of: transforming said ciphertext word
signal C, whereby:
M=C.sup.d (mod n)
where d is a multiplicative inverse of e(mod(lcm((p.sub.1 -1), (p.sub.2 -1), .
. . , (p.sub.k -1)))).
3. A method for transferring a message signal M.sub.i in a communications
system having j terminals, wherein each terminal is characterized by an
encoding key E.sub.i =(e.sub.i, n.sub.i) and decoding key D.sub.i =(d.sub.i,
n.sub.i), where i=1, 2, . . . , j, and wherein M.sub.i corresponds to a number
representative of a message-to-be-transmitted from the i.sup.th terminal,
n.sub.i is a composite number of the form
n.sub.i =P.sub.i,1 .multidot.p.sub.i,2 .multidot., . . . ,.multidot.p.sub.i,k
where k is an integer greater than 2,
p.sub.i,1, p.sub.i,2, . . . , p.sub.i,k are distinct prime numbers,
e.sub.i is relatively prime to lcm(p.sub.i,1 -1, p.sub.1,2 -1, p.sub.i,k -1)
d.sub.i is selected from the group consisting of the class of numbers
equivalent to a multiplicative inverse of
e.sub.i (mod(lcm((p.sub.i,1 -1), (p.sub.i,2 -1), . . . , (p.sub.i,k -1)))),
comprising the step of:
encoding a digital message word signal M.sub.A for transmission from a first
terminal (i=A) to a second terminal (i=B), said encoding step including the
sub-step of:
transforming said message word signal M.sub.A to one or more message block word
signals M.sub.A ", each block word signal M.sub.A " corresponding to a number
representative of a portion of said message word signal M.sub.A in the range
0.ltoreq.M.sub.A ".ltoreq.n.sub.B -1,
transforming each of said message block word signals M.sub.A " to a ciphertext
word signal C.sub.A, C.sub.A corresponding to a number representative of an
encoded form of said message block word signal M.sub.A ", whereby:
C.sub.A .ident.M.sub.A ".sup.eB (mod n.sub.B).
4. A cryptographic communications system comprising:
a communication medium;
an encoding means coupled to said channel and adapted for transforming a
transmit message word signal M to a ciphertext word signal C and for
transmitting C on said channel, where M corresponds to a number representative
of a message and
0.ltoreq.M.ltoreq.n-1 where n is a composite number of the form
n=p.sub.1 .multidot.p.sub.2 .multidot.. . . .multidot.p.sub.k
where k is an integer greater than 2 and p.sub.1, p.sub.2, . . . , p.sub.k are
distinct prime numbers, and where C corresponds to a number representative of
an enciphered form of said message and corresponds to
C.ident.M.sup.e (mod n)
where e is a number relatively prime to lcm(p.sub.1 -1, p.sub.2 -1, . . . ,
p.sub.k -1); and
a decoding means coupled to said channel and adapted for receiving C from said
channel and for transforming C to a receive message word signal M' where M'
corresponds to a number representative of a deciphered form of C and
corresponds to
M'.ident.C.sup.d (mod n)
where d is selected from the group consisting of the class of numbers
equivalent to a multiplicative inverse of
e(mod(lcm((p.sub.1 -1), (p.sub.2 -1), . . . , (p.sub.k -1)))).
5.
5. A cryptographic communications system having a plurality of terminals
coupled by a communications channel, including a first terminal characterized
by an associated encoding key E.sub.A =(e.sub.A, n.sub.A) and decoding key
D.sub.A =(d.sub.A, n.sub.A), wherein n.sub.A is a composite number of the form
n.sub.A =p.sub.A,1 .multidot.p.sub.A,2 .multidot.. . . .multidot.p.sub.A,k
where k is an integer greater than 2, p.sub.A,1, p.sub.A,2, . . . , p.sub.A,k
are distinct prime numbers, e.sub.A is relatively prime to
lcm(p.sub.A,1 -1, p.sub.A,2 -1, . . . , p.sub.A,k -1),
d.sub.A is selected from the group consisting of the class of numbers
equivalent to a multiplicative inverse of
e.sub.A (mod(lcm((p.sub.A,1 -1), (p.sub.A,2 -1), . . . , (p.sub.A,k -1)))),
and including a second terminal, comprising:
blocking means for transforming a message-to-be-transmitted from said second
terminal to said first terminal to one or more transmit message word signals
M.sub.B, where M.sub.B corresponds to a number representative of said message
in the range
0.ltoreq.M.sub.B .ltoreq.n.sub.A -1,
encoding means coupled to said channel and adapted for transforming each
transmit message word signal M.sub.B to a ciphertext word signal C.sub.B and
for transmitting C.sub.B on said channel,
where C.sub.B corresponds to a number representative of an enciphered form of
said message and corresponds to
C.sub.B .ident.M.sub.B.sup.eA (mod n.sub.A)
wherein said first terminal comprises:
decoding means coupled to said channel and adapted for receiving said
ciphertext word signals C.sub.B from said channel and for transforming each of
said ciphertext word signals to a receive message word signal M.sub.B, and
means for transforming said receive message word signals M.sub. ' to said
message, where M.sub. ' is a number representative of a deciphered form of
C.sub.B and corresponds to
M.sub.B '.ident.C.sub.B.sup.da (mod n.sub.A).
6. The system according to claim 5 wherein said second terminal is
characterized by an associated encoding key E.sub.B =(e.sub.B, n.sub.B) and
decoding key DB=(D.sub.B, d.sub.B), where:
n.sub.B is a composite number of the form
n.sub.B =p.sub.B,1 .multidot.p.sub.B,2 .multidot.. . . .multidot.p.sub.B,k
where k is an integer greater than 2, p.sub.B,1, p.sub.B,2, . . . , p.sub.B,k
are distinct prime numbers, e.sub.B is relatively prime to
lcm(p.sub.B,1 -1, p.sub.B,2 -1, . . . , p.sub.B,k -1),
d.sub.B is selected from the group consisting of the class of numbers
equivalent to a multiplicative inverse of
e.sub.B (mod(lcm((p.sub.B,1), (p.sub.B,2 -1), . . . , (p.sub.B,k -1)))),
wherein said first terminal comprises:
blocking means for transforming a message-to-be-transmitted from said first
terminal to said second terminal, to one or more transmit message word signals
M.sub.A, where M.sub.A corresponds to a number representative of said message
in the range
0.ltoreq.M.sub.A.sup.eB (mod n.sub.B)
encoding means coupled to said channel and adapted for transforming each
transmit message word signal M.sub.A to a ciphertext word signal C.sub.A and
for transmitting C.sub.A on said channel,
where C.sub.A corresponds to a number representative of an enciphered form of
said message and corresponds to
C.sub.A .ident.M.sub.A.sup.eB (mod n.sub.B)
wherein said second terminal comprises;
decoding means coupled to said channel and adapted for receiving said
ciphertext word signals C.sub.A from said channel and for transforming each of
said ciphertext word signals to a receive message word signal M.sub.A ', and
means for transforming said receive message word signals M.sub.A to said
message,
where M' corresponds to a number representative of a deciphered form of C and
corresponds to
M.sub.A '.ident.C.sub.A.sup.dB (mod n.sub.B).
7. A method for establishing cryptographic communications comprising the step
of:
encoding a digital message word signal M to a cipher text word signal C, where
M corresponds to a number representative of a message and
0.ltoreq.M.ltoreq.n-1,
where n is a composite number having at least 3 whole number factors greater
than one, the factors being distinct prime numbers, and
where C corresponds to a number representative of an encoded form of message
word M,
wherein said encoding step comprises the step of:
transforming said message word signal M to said ciphertext word signal C
whereby
C.ident.a.sub.e M.sup.e +a.sub.e-1 M.sup.e-1 +. . . +a.sub.0 (mod n)
where e and a.sub.e, a.sub.e-1, . . . , a.sub.0 are numbers.
8. In the method according to claim 7 where said encoding step includes the
step of transforming M to C by the performance of a first ordered succession of
invertible operations on M, the further step of:
decoding C to M by the performance of a second ordered succession of invertible
operations on C, where each of the invertible operations of said second
succession is the inverse of a corresponding one of said first succession, and
wherein the order of said operations in said second succession is reversed with
respect to the order of corresponding operations in said first succession.
9. A communication system for transferring message signals M.sub.i, comprising:
j stations, each of the j stations being characterized by an encoding key
E.sub.i =(e.sub.i, n.sub.i) and decoding key D.sub.i =(d.sub.i, n.sub.i) ,
where i=1,2, . . . ,j, and wherein
M.sub.i corresponds to a number representative of a message signal to be
transmitted from the i.sup.th terminal, and
0.ltoreq.M.sub.i .ltoreq.n.sub.i -1,
n.sub.i is a composite number of the form
n.sub.i =pi.sub.i,1 .multidot.p.sub.i,2 .multidot.. . . .multidot.p.sub.i,k
where k is an integer greater than 2,
p.sub.i,1, p.sub.i,2, . . . , p.sub.i,k are distinct prime numbers,
e.sub.i is relatively prime to lcm(p.sub.i,1 -1,p.sub.i,2 -1, . . . , p.sub.i,k
-1),
d.sub.i is selected from the group consisting of the class of numbers
equivalent to a multiplicative inverse of
e.sub.i (mod(lcm((p.sub.i,1 -1), (p.sub.i,2 -1), . . . , (p.sub.i,k -1))));
a first one of the j terminals including
means for encoding a digital message word signal M.sub.A for transmission from
said first terminal (i=A) to a second one of the j terminals (i=B), and
means for transforming said message word signal M.sub.A to a signed message
word signal M.sub.As, M.sub.As corresponding to a number representative of an
encoded form of said message word signal M.sub.A, whereby:
M.sub.As .ident.M.sub.A.sup.dA (mod n.sub.A).
10. The system of claim 9 further comprising:
means for transmitting said signal message word signal M.sub.As from said first
terminal to said second terminal, and wherein said second terminal includes
means for decoding said signed message word signal M.sub.As to said message
word signal M.sub.A, said second terminal including:
means for transforming said signed message word signal M.sub.AS to said message
word signal M.sub.A, whereby
M.sub.A .ident.M.sub.As.sup.eA (mod n.sub.A).
11.
11. A communications system for transferring a message signal M.sub.i, the
communications system comprising
j communication stations each characterized by an encoding key E.sub.i =
(e.sub.i, n.sub.i) and decoding key D.sub.i =(d.sub.i, n.sub.i), where i=1, 2,
. . . , j, and wherein M.sub.i corresponds to a number representative of a
message signal to be transmitted from the i.sup.th terminal, n.sub.i is a
composite number of the form
n.sub.i =p.sub.i,1 .multidot.p.sub.i,2 .multidot.. . . .multidot.p.sub.i,k
where
k is an integer greater than 2,
p.sub.i,1, p.sub.i,2, . . . ,p.sub.i,k are distinct prime numbers,
e.sub.i is relatively prime to lcm(p.sub.i,1 -1,p.sub.i,2 -1, . . . ,p.sub.i,k
-1),
d.sub.i is selected from the group consisting of the class of numbers
equivalent to a multiplicative inverse of
e.sub.i (mod(lcm((p.sub.i,1 -1), (p.sub.i,2 -1), . . . , (p.sub.i,k -1))))
a first one of the j communication stations including
means for encoding a digital message word signal M.sub.A for transmission from
said first one of the j communication stations (i=A) to a second one of the j
communication stations (i=B),
means for transforming said message word signal M.sub.A to one or more message
block word signals M.sub.A ", each block word signal M.sub.A ' being a number
representative of a portion of said message word signal M.sub.A ' in the range
0.ltoreq.M.sub.A .ltoreq.n.sub.B -1, and
means for transforming each of said message block word signals M.sub.A " to a
ciphertext word signal C.sub.A, C.sub.A corresponding to a number
representative of an encoded form of said message block word signal M.sub.A ",
whereby:
C.sub.A .ident.M.sub.A ".sup.Eb (mod n.sub.B).
12.
12. The system of claim 11 further comprising:
means for transmitting said ciphertext word signals from said first terminal to
said second terminal, and
wherein said second terminal includes means for decoding said ciphertext word
signals to said message word signal MA, said second terminal including:
means for transforming each of said ciphertext word signals C.sub.A to one of
said message block
word signals M.sub.A ", whereby
M.sub.A ".ident.C.sub.A.sup.Db (mod n.sub.B)
means for transforming said message block word signals M.sub.A " to said
message word signal M.sub.A.
13. In a communications system, including first and second communicating
stations interconnected for communication therebetween,
the first communicating station having
encoding means for transforming a transmit message word signal M to a
ciphertext word signal C where M corresponds to a number representative of a
message and
0.ltoreq.M.ltoreq.n-1
where n is a composite number having at least 3 whole number factors greater
than one, the factors being distinct prime numbers, and
where C corresponds to a number representative of an enciphered form of said
message and corresponds to
C.ident.a.sub.e M.sup.e +a.sub.e-1 M.sup.e-1 +. . . +a.sub.0 (mod n)
where e and a.sub.e, a.sub.e -1, . . . , a.sub.0 are numbers; and
means for transmitting the ciphertext word signal C to the second communicating
station.
-------------------------------------------------------------------------------
Description
-------------------------------------------------------------------------------
This application claims the benefit of U.S. Provisional Application No. 60/
033,271 for PUBLIC KEY CRYTOGRAPHIC APPARATUS AND METHOD, filed Dec. 9, 1996,
naming as inventors, Thomas Colins, Dale Hopkins, Susan Langford and Michale
Sabin, the discolsure of which is incorporated by reference.
BACKGROUND OF THE INVENTION
This invention relates generally to communicating data in a secure fashion, and
more particularly to a cryptographic system and methods using public key
cryptography.
Computer systems are found today in virtually every walk of life for storing,
maintaining, and transferring various types of data. The integrity of large
portions of this data, especially that portion relating to financial
transactions, is vital to the health and survival of numerous commercial
enterprises. Indeed, as open and unsecured data communications channels for
sales transactions gain popularity, such as credit card transactions over the
Internet, individual consumers have an increasing stake in data security.
Thus, for obvious reasons, it is important that financial transaction
communications pass from a sender to an intended receiver without intermediate
parties being able to interpret the transferred message.
Cryptography, especially public key cryptography, has proven to be an effective
and convenient technique of enhancing data privacy and authentication. Data to
be secured, called plaintext, is transformed into encrypted data, or
ciphertext, by a predetermined encryption process of one type or another. The
reverse process, transforming ciphertext into plaintext, is termed decryption.
Of particular importance to this invention is that the processes of encryption
and decryption are controlled by a pair of related cryptographic keys. A
"public" key is used for the encryption process, and a "private" key is used to
decrypt ciphertext. The public key transforms plaintext to ciphertext, but
cannot be used to decrypt the ciphertext to retrieve the plaintext therefrom.
As an example, suppose a Sender A wishes to send message M to a recipient B.
The idea is to use public key E and related private key D for encryption and
decryption of M. The public key E is public information while D is kept secret
by the intended receiver. Further, and importantly, although E is determined by
D, it is extremely difficult to compute D from E. Thus the receiver, by
publishing the public key E, but keeping the private key D secret, can assure
senders of data encrypted using E that anyone who intercepts the data will not
be able to decipher it. Examples of the public key/private key concept can be
found in U.S. Pat. Nos. 4,200,770, 4,218,582, and 4,424,414.
The prior art includes a number of public key schemes, in addition to those
described in the above-identified patents. Over the past decade, however, one
system of public key cryptography has gained popularity. Known generally as the
"RSA" scheme, it is now thought by many to be a worldwide defacto standard for
public key cryptography. The RSA scheme is described in U.S. Pat. No. 4,405,829
which is fully incorporated herein by this reference.
The RSA scheme capitalizes on the relative ease of creating a composite number
from the product of two prime numbers whereas the attempt to factor the
composite number into its constituent primes is difficult. The RSA scheme uses
a public key E comprising a pair of positive integers n and e, where n is a
composite number of the form
n=p.multidot.q (1)
where p and q are different prime numbers, and e is a number relatively prime
to (p-1) and (q-1); that is, e is relatively prime to (p-1) or (q-1) if e has
no factors in common with either of them. Importantly, the sender has access to
n and e, but not to p and q. The message M is a number representative of a
message to be transmitted wherein
0.ltoreq.M