Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
2001-09-04
2004-06-15
Cangialosi, Salvatore (Department: 2661)
Cryptography
Particular algorithmic function encoding
Public key
C380S028000
Reexamination Certificate
active
06751318
ABSTRACT:
BACKGROUND OF THE PRESENT INVENTION
1. Field of the Invention
This invention relates to the field of cryptographic systems.
2. Background Art
A cryptographic system is a system for sending a message from a sender to a receiver over a medium so that the message is “secure”, that is, so that only the intended receiver can recover the message. A cryptographic system converts a message, referred to as “plaintext” into an encrypted format, known as “ciphertext.” The encryption is accomplished by manipulating or transforming the message using a “cipher key” or keys. The receiver “decrypts” the message, that is, converts it from ciphertext to plaintext, by reversing the manipulation or transformation process using the cipher key or keys. So long as only the sender and Deceiver have knowledge of the cipher key, such an encrypted transmission is secure.
A “classical” cryptosystem is a cryptosystem in which the enciphering information can be used to determine the deciphering information. To provide security, a classical cryptosystem requires that the enciphering key be kept secret and provided to users of the system over secure channels. Secure channels, such as secret couriers, secure telephone transmission lines, or the like, are often impractical and expensive.
A system that eliminates the difficulties of exchanging a secure enciphering key is known as “public key encryption.” By definition, a public key cryptosystem has the property that someone who knows only how to encipher a message cannot use the enciphering key to find the deciphering key without a prohibitively lengthy computation. An enciphering function is chosen so that once an enciphering key is known, the enciphering function is relatively easy to compute. However, the inverse of the encrypting transformation function is difficult, or computationally infeasible, to compute. Such a function is referred to as a “one way function” or as a “trap door function.” In a public key cryptosystem, certain information relating to the keys is public. This information can be, and often is, published or transmitted in a non-secure manner. Also, certain information relating to the keys is private. This information may be distributed over a secure channel to protect its privacy, (or may be created by a local user to ensure privacy).
A block diagram of a typical public key cryptographic system is illustrated in
FIG. 1. A
sender represented by the blocks within dashed line
100
sends a plaintext message Ptxt to a receiver, represented by the blocks within dashed line
115
. The plaintext message is encrypted into a ciphertext message C, transmitted over some transmission medium and decoded by the receiver
115
to recreate the plaintext message Ptxt.
The sender
100
includes a cryptographic device
101
, a secure key generator
102
and a key source
103
. The key source
103
is connected to the secure key generator
102
through line
104
. The secure key generator
102
is coupled to the cryptographic device
101
through line
105
. The cryptographic device provides a ciphertext output C on line
106
. The secure key generator
102
provides a key output on line
107
. This output is provided, along with the ciphertext message
106
, to transmitter receiver
109
. The transmitter receiver
109
may be, for example, a computer transmitting device such as a modem or it may be a device for transmitting radio frequency transmission signals. The transmitter receiver
109
outputs the secure key and the ciphertext message on an insecure channel
110
to the receiver's transmitter receiver
111
.
The receiver
115
also includes a cryptographic device
116
, a secure key generator
117
and a key source
118
. The key source
118
is coupled to the secure key generator
117
on line
119
. The secure key generator
117
is coupled to the cryptographic device
116
on line
120
. The cryptographic device
116
is coupled to the transmitter receiver
111
through line
121
. The secure key generator
117
is coupled to the transmitter receiver
111
on lines
122
and
123
.
In operation, the sender
100
has a plaintext message Ptxt to send to the receiver
115
. Both the sender
100
and the receiver
115
have cryptographic devices
101
and
116
, respectively, that use the same encryption scheme. There are a number of suitable cryptosystems that can be implemented in the cryptographic devices. For example, they may implement the Data Encryption Standard (DES) or some other suitable encryption scheme.
Sender and receiver also have secure key generators
102
and
117
, respectively. These secure key generators implement any one of several well known public key exchange schemes. These schemes, which will be described in detail below, include the Diffie-Hellman scheme, the RSA scheme, the Massey-Omura scheme, and the ElGamal scheme.
The sender
100
uses key source
133
, which may be a random number generator, to generate a private key. The private key is provided to the secure key generator
102
and is used to generate an encryption key e
K
. The encryption key e
K
is transmitted on lines
105
to the cryptographic device and is used to encrypt the plaintext message Ptxt to generate a ciphertext message C provided on line
106
to the transmitter receiver
109
. The secure key generator
102
also transmits the information used to convert to the secure key from key source
103
to the encryption key e
K
. This information can be transmitted over an insecure channel, because it is impractical to recreate the encryption key from this information without knowing the private key.
The receiver
115
uses key source
118
to generate a private and secure key
119
. This private key
119
is used in the secure key generator
117
along with the key generating information provided by the sender
100
to generate a deciphering key D
K
. This deciphering key D
K
is provided on line
120
to the cryptographic device
116
where it is used to decrypt the ciphertext message and reproduce the original plaintext message.
The Diffie-Hellman Scheme
A scheme for public key exchange is presented in Diffie and Hellman, “New Directions in Cryptography,” IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, November 1976 (The “DH” scheme). The DH scheme describes a public key system based on the discrete exponential and logarithmic functions. If “q” is a prime number and “a” is a primitive element, then X and Y are in a 1:1 correspondence for 1≦X, Y≦(q−1) where Y=a
X
mod q, and X=log
a
Y over the finite field. The first discrete exponential function is easily evaluated for a given a and X, and is used to compute the public key Y. The security of the Diffie-Hellman system relies on the fact that no general, fast algorithms are known for solving the discrete logarithm function X=log
a
Y given X and Y.
In a Diffie-Hellman system, a directory of public keys is published or otherwise made available to the public. A given public key is dependent on its associated private key, known only to a user. However, it is not feasible to determine the private key from the public key. For example, a sender has a public key, referred to as “ourPub”. A receiver has a public key, referred to here as “theirPub”. The sender also has a private key, referred to here as “myPri”. Similarly, the receiver has a private key, referred to here as “theirPri”.
There are a number of elements that are publicly known in a public key system. In the case of the Diffie-Hellman system, these elements include a prime number p and a primitive element g. p and g are both publicly known. Public keys are then generated by raising g to the private key power (mod p). For example, a sender's public key myPub is generated by the following equation:
myPub=
g
myPri
(mod
p
) Equation (1)
Similarly, the receiver's public key is generated by the equation:
theirPub=
g
theirPri
(mod
p
) Equation (2)
Public keys are easily created using exponentiation and modulo arithmetic. As noted previously, public keys are easily obtaina
Cangialosi Salvatore
NeXT Software, Inc.
The Hecker Law Group
LandOfFree
Method and apparatus for digital signature authentication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for digital signature authentication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for digital signature authentication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3350624