Cryptography – Key management
Reexamination Certificate
1998-11-10
2002-06-25
Barron, Jr., Gilberto (Department: 2132)
Cryptography
Key management
C380S028000, C380S030000, C380S286000, C380S001000, C713S171000
Reexamination Certificate
active
06411715
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to cryptographic communications methods and systems that use a public key protocol, and more particularly to verifying the cryptographic security of a selected public and private key pair without knowing the private key.
BACKGROUND OF THE INVENTION
Cryptographic systems are adapted to transfer securely messages between remote locations over unsecured communication networks. Such systems include at least one encoding device at a first location and at least one decoding device at a second location, with the encoding and decoding devices all being coupled to the network. The encoding device accepts, as inputs, a message-to-be-encoded (M) and an encoding key or encryption operator (E). The encoding device transforms the message M in accordance with the encryption operator to produce an encoded version (C) of the message (which is denoted as the ciphertext), where C=E(M). The decoding device accepts, as inputs, a ciphertext-to-be-decoded C and a decoding key or operator (D). The decoding device transforms the ciphertext in accordance with the decryption operator to produce a decoded version (M′) of the ciphertext, wherein M′=D(C) or M′=D(E(M)) and M′=M for all messages. Like the encoding key, the decoding key and decoded message M′ are digital sequences.
In a public-key cryptosystem, each user (e.g., user A) publishes an enciphering operator, or a public key, E
A
. User A keeps private the details of the corresponding deciphering private key D
A
which satisfies the equation D
A
(E
A
(M)=M for any message M. In order for the public key system to be practical, both E
A
and D
A
must be efficiently computable. Furthermore, user A must not compromise the cryptographic security of D
A
when revealing E
A
. That is, it should not be computationally feasible for an eavesdropper to find an efficient way of computing D
A
given only a specification of the enciphering key E
A
. In a public key system, a cryptographically secure selection of keys ensures that only user A is able to compute D
A
efficiently. Whenever another user (e.g., user B) wishes to send a message M to A, that user encodes M using the publicly-available E
A
and then sends the enciphered message E
A
(M) to user A. User A deciphers the message by computing (D
A
(E
A
(M))=M. Since D
A
is not derivable from E
A
in a practical way, only user A can decipher the message E
A
(M). If user A wants to send a response to user B, user A enciphers the message using user B's encryption key E
B
, also available in publicly.
The public key approach is also used to provide signed digital messages that are both message-dependent and signer-dependent. The recipient of a “signed” message not only knows the message substance, but is also assured that the message originated from the identified sender. A signed message precludes the possibility that a recipient could modify the received message by changing a few characters or that the recipient could attach the received signature to any message whatsoever.
When user A wants to send user B a “signed” document M, user A first uses his own decryption key D
A
to transform M into a signed message word M
s
, where M
S
=D
A
(M). User A then uses user B's publicly-available encryption key E
B
to generate a signed ciphertext word C
S
=E
B
(M
S
)=E
B
(D
A
(M)), which is sent to user B. User B initially uses his secret decryption key D
B
to reduce the signed ciphertext C
S
to a signed message word in accordance with D
B
(C
S
)=D
B
(E
B
(M
S
))=M
S
. Now using user A's publicly-available encoding key E
A
, user B decodes the signed message word in accordance With E
A
(M
S
)=E
A
=M. User A cannot deny having sent user B this message, since no one but A could have created M
S
=D
A
(M), provided that D
A
is not Computable from E
A
, i.e. provided that D
A
is cryptographically secure. Furthermore, user B can show that the public key E
A
is necessary to extract the message M so that user B has “proof” that user A has signed the document. User B cannot modify M to a different version M′, since then user B would have to create the corresponding signature D
A
(M′) as well. Therefore user B must have received a document “signed” by A, which he can “prove” that A sent, but which B cannot modify in any detail.
In a communication system which is adapted to pro)vide digital signatures, each transmitting and receiving terminal is provided with both an encoding and decoding device, each device being functionally equivalent to the devices described above but operating on a different set of input words with a different key. The transmitting terminal decoding device transforms a message M using its own decoding key to generate a signed message M
S
. Then the encoding device transforms the resultant signed message M
S
with the intended receiving terminal's encoding key to generate signed ciphertext word C
S
. The receiving terminal's decoding device then transforms the received C
S
with its own decoding key to obtain the signed message M
S
, and then the encoding device transforms the resultant signed message with the transmitting terminal's encoding key to obtain the original message. For example, in a system for transmitting signed messages from user A to user B, the terminal for user A includes at least one encoding device characterized by an encoding key E
B
=(e
B
, N
B
) and at least one decoding device, characterized by a decoding key D
A
=(d
A
, N
A
). Similarly, the terminal for user B includes an encoding device characterized by an encoding key E
A
=(e
A
, N
A
) and a decoding device characterized by a decoding key D
B
=(d
B
, N
B
). The encoding and decoding devices of terminals A and B are described above.
In operation, to provide a signed message, user A first generates a ciphertext signed message word M
S
M
s
≡M
d
A
(mod
N
A
)
and then transforms that signed message word to a signed ciphertext word C
S
: which is then transferred to user B. User A may readily use D
A
and N
A
from his own
C
S
=M
S
e
B
(mod N
B
)
decoding key to reduce the signed ciphertext word to a signed message word, and then perform the encoding transformations using E
B
and N
B
from the publicly available file.
User B deciphers the received C
S
into the signed message word M
S
in accordance with
M
S
≡(C
S
)
d
B
(mod N
B
)
User B then transforms M
S
to M in accordance with
M≡M
S
e
A
(mod
N
A
)
User B may readily perform his decoding transformations since D
B
and N
B
are part of his decoding key and E
A
and N
A
are readily available on the public file.
Because public key cryptography can be used for authentication of transactions, a cryptographically strong key pair (i.e. a public key and a corresponding private key) is desirable to prevent a party to a transaction from subsequently repudiating it. If a transaction is authenticated with a weak key pair, it is easier for a party to the transaction to subsequently repudiate it by arguing that the private key had succumbed to a cryptanalytic attack.
When business transactions are conducted over an unsecured network there is a critical need to assure the cryptographic security of the private key. The integrity of the transactions are assured not only by preventing an unauthorized party to decipher or alter the transmitted message, or by uniquely identifying the sender, but also by preventing the sender from repudiating the transaction later. That is, the author should be the constructor of the private key and the only party having access to the private key. On the other hand, a certifying authority (i.e., a verifier) should be able to verify the cryptographic security of the private key without receiving information sufficient to calculate the private key. In a certifying process, the constructor (i.e., the prover) would prove the cryptographic security of the selected private key to the verifier w
Juels Ari
Liskov Moses
Silverman Robert
Barron Jr. Gilberto
Darrow Justin T.
RSA Security Inc.
Testa Hurwitz & Thibeault LLP
LandOfFree
Methods and apparatus for verifying the cryptographic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for verifying the cryptographic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for verifying the cryptographic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2902140