Keyless encryption of messages using challenge response

Details Keyless encryption of messages using challenge response Keyless encryption of messages using challenge response

1999-06-21

2003-03-18

Barron, Gilberto (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S152000

Reexamination Certificate

active

06535980

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to secure electronic data transfer and, more particularly, to a method of secure electronic transfer of data whose security does not rely on encryption with keys.
2. Background Description
A cryptosystem is an apparatus used to facilitate the transfer of a confidential message (such as a password or credit card number) between two parties via an insecure communication channel that allows the message to be snooped (intercepted and worked on). Traditional approaches to constructing such an apparatus involve providing the construction of an encryption scheme (at the sender's end) that uses some encryption keys to transform the message into a coded or ciphertext, and a decryption scheme (at the receiver's end) to recover the original message from the ciphertext again using some decryption keys. Note that the decryption scheme must be the inverse of the encryption scheme to recover the message correctly. By coding the message, a party eavesdropping on the unsecure channel will not be able to understand the message, even though he will be able to listen to it. All cryptosystems have three potential parties—the sender of the message, the receiver for whom it is intended, and the eavesdropper.
Existing methods for cryptosystems can be broadly divided into two categories—message encryption and authentication. A message encryption system is used when the sender wishes to transmit a message that the receiver does not know the message in advance. In an authentication system, on the other hand, the receiver typically knows the correct message in advance, and the message is used as a password to authenticate the credential of the sender. Note that message encryption systems can also be used for authentication purposes, and are in fact so used in many places.
Cryptosystems generally use a key to encode the message. The key is a number (or string) used by the encryption method in mapping the message string to a coded string. The same key or another key is then used by receiver to decode or unlock the message. Key based message cryptosystems can be broadly classified as private key or public key systems.
A private-key cryptosystem is one where the encryption and decryption keys are private and agreed upon in advance. For an example of such a system, see U.S. Pat. No. 4,424,414 to Hellman and Pohlig. In this system, the keys must be kept secret, since the same key is generally used both to encrypt and decrypt the message.
A public-key cryptosystem overcomes the shortcoming of having previously agreed upon secret keys between the communicating parties. In this scheme, each member publishes one or more public keys announced publicly and associated with this member. Anyone wishing to send a message to this member can then encode the message using a procedure that employs this member's announced public key. The central idea is that a message so encoded can be decoded efficiently only by the member itself who has some additional private information, while a snooper trying to decode this message is up against a computationally intractable task. Some of the first methods to implement such a cryptosystem are described in U.S. Pat. No. 4,405,829 to Rivest, Shamir and Adleman, for “Cryptograpic communications system and method”, and U.S. Pat. No. 4,200,770 to Hellman, Diffie and Merkle, for “Cryptographic apparatus and method”. See also U.S. Pat. No. 4,218,582 to Hellman and Merkle, for “Public key cryptographic apparatus and method”. Public key cryptosystems can be broken even if a single message is encrypted and sent, given enough time. For this reason, strong encryption demands the use of long keys.
In contrast to public/private key systems, authentication systems can be built using a “challenge response” scheme. See, for example, U.S. Pat. No. 4,723,284 to Munck and Chapin, for “Authentication system”. After the receiver (authenticator) and the sender (user) have contractually agreed upon a set of challenge-response pairs, whenever this user wants to gain access, the authenticator poses a challenge randomly chosen from among the set of agreed upon pairs. The user authenticates himself or herself by looking through the predetermined list to pick out the appropriate response and providing it to the system. On verifying the correctness of this response, the system provides access to the user. The table of predetermined challenge-response pairs may be replaced by computational procedures that, using a much shorter private key provided to both the system and the user, generates a challenge at the system side given the identity of the user, and given such a challenge and the local private key, generates the appropriate response, which in turn can be verified by the system. See, for example, U.S. Pat. No. 4,935,962 to Austin, for “Method and system for authentication”, and U.S. Pat. No. 4,999,258 to Davies, for “Apparatus and methods for granting access to computers”. The method disclosed in U.S. Pat. No. 5,406,623 to Beller and Jacobi, for “Public key authentication and key agreement for low-cost terminals”, is particularly suited to a system and user with asymmetric computational resources. Challenge response systems have the advantage over Public Key encryption systems that a single exchange is insufficient to break the system. Even if the eavesdropper listened to one challenge and response, the response will be useless if he tries to access the system, since a new challenge will be thrown the next time around. However, the traditional challenge response system is not suited for sending an arbitrary message but is used to achieve authentication.
Strong encryption, such as RSA (for Rivest, Shamir and Adleman) encryption using 128-bit keys, is a good way of secure electronic data transfer. However, for various reasons, the option of using strong encryption is not always available. For instance, laws of many nations proscribe the use of strong encryption in communications that cross national boundaries.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a keyless encryption of messages.
According to the invention, there is provided a secure method of data transfer using a challenge response in which a correct response to a challenge is used to transmit the value “1”, while a deliberately false response is made to transmit the value “0”. Any message can be transmitted as a binary string using successive applications of this method.
This invention extends the challenge-response system from a purely authentication system to that of a message encryption system suitable for sending arbitrary message in a secret fashion. In the new method, the sender and receiver agree on a set of challenge-response pairs as usual. When the sender wishes to send an arbitrary message, the sender converts the message into binary format (using a standard convention, e.g. ASCII (American Standard Code for Information Interchange) if the message is a string). Then, each bit of the message is sent as a response. For every bit, the receiver issues a challenge. If the bit that the sender has to transmit is a one, the sender sends the correct response. If the bit is a zero, he sends a randomly chosen wrong response to indicate that the bit is a zero (the function of correct and incorrect responses could be reversed, in a pre-agreed manner). The conversation ends when the entire message is transmitted this way, either by sending the length of the message in the beginning, pre-agreeing on the length of the message, or by sending a suitable sequence of bits to indicate termination. For simplicity, we will restrict our description to the case where k, the number of bits in the message is fixed. It is easy to extend this system to one that can transmit an arbitrarily large number of bits, for example, by either sending the number of bits contained in the message up front or by sending a previously agreed upon termination bit pattern at the end of a message. In many applications (e.g., the transmissio

Affiliated with

Also associated with

Rating

Keyless encryption of messages using challenge response does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Keyless encryption of messages using challenge response, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Keyless encryption of messages using challenge response will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3006711