Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1997-12-31
2001-06-19
Swann, Tod (Department: 2132)
Cryptography
Particular algorithmic function encoding
C380S037000, C380S042000, C380S046000, C380S262000
Reexamination Certificate
active
06249582
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to transmission of encrypted information over a communications channel, and in particular, to an apparatus and method of reducing overhead in block cipher encryption and decryption without decreasing security of the content of the encrypted information below a desired level. Alternatively, the invention relates to reducing overhead in block cipher operations to produce a pseudo-random number sequence without decreasing security of the sequence. More specifically, this invention has to do with a way of reducing the burden of re-synchronizing a block cipher, regardless of application of the block cipher, without having to unduly sacrifice overall cycle length.
2. Problems in the Art
The need for secure communications systems continues to expand. It is many times desirable to keep data confidential from both innocent or intentional interlopers or viewers. It is also true of communications of voice.
Most communication of intelligible information is based on alphabetic or numeric systems. Therefore, the content of most data or voice messages is in one sense initially “coded”. The English alphabet and the decimal number system are examples of such coding. By using the rules of those systems, the content of the data or voice can be immediately interpreted by those who understand the rules of and can “read” the information coded by that particular alphabet or number system. However, because the alphabets and number systems of the world are open and public domain, there is no substantial limitation on who can understand (“decode”) the communication, and thus there is no substantial communication security for such.
A variety of methods have been developed to try to keep knowledge of the content of the information away from certain persons or entities. One example of a secure communications system is set forth in U.S. Pat. No. 4,893,339. Encryption is a well-known method of securing information. Encryption transforms the coded information into a form that is unintelligible when using the normal rules of the particular alphabet or number system originally used for that information.
A variety of encryption methods have been developed. Many function to output information that is made up of the same types of individual characters (letters or numbers) used to code the original intelligible message, but the output is unintelligible. Many operate at a digital level. The original intelligible coded information (e.g. alphanumeric words) is converted into digital words (e.g. bytes), with each character of each word being coded into a set of individual digital values (e.g. bits). Another example is audio (e.g. voice). Voice is converted to an analog electrical signal through a microphone. The analog signal is sampled. The samples are digitized by quantifying each sample digitally. Sections of audio (e.g. frames) can then be digitally quantified and used to reconstruct the analog signal.
In the above examples, the information can be immediately interpreted by those that intercept it by using compatible equipment, or by applying widely known techniques to make it intelligible. Therefore, many encryption methods concentrate on ways to make it difficult or practically impossible to derive the true meaning of the information from the encrypted communication.
One commonly used encryption method is called block cipher. The art of block ciphers is well known. The Data Encryption Standard (DES) is a common example of a block cipher, which is described in Federal Information Processing Standard FIPS-46-2, published by the National Institute of Standards and Technology. Furthermore, methods of using block ciphers to protect information are also well know. FIPS-81 describes methods of using DES in four different modes. FIPS-46-2 and FIPS-81 are incorporated by reference herein.
In conventional block cipher systems, the information to be encrypted is digitized. It can be digitally encoded data or voice (audio). This original, intelligible information is many times referred to as “plaintext”, connoting that it contains the information that is intelligible and meaningful, i.e. it contains the message in an understandable form when decoded by easy methods. Block cipher systems tend to take chunks of digitally encoded information (fixed size sets of bits called “blocks”) and combine each block with a block created by a pseudo-random number generator. The combined block, known as “ciphertext”, is then unintelligible if decoded using conventional decoding techniques, unless it first is decrypted. This requires the receiving party to know ahead of time the identical pseudo-random number block used to transform the plaintext block to a ciphertext block. In communications systems, this means that the transmitter must tell the receiver certain information, apart from the message itself, to allow the receiver to know how to decrypt the message. Sources such as Schneier, Bruce,
Applied Cryptography, Second Edition,
John Wiley & Sons (1996) provide a discussion of cryptography and random numbers and their generation, and is incorporated by reference herein.
When using a cipher to protect communications traffic, certain features are highly desirable. First, the amount of overhead should be minimal. Overhead is data which is required for purposes other than that of sending the desired message, and may be necessary for such things as keeping the cipher at the receiving end in synchronization with the cipher at the transmitting end. Thus, overhead uses up room or bandwidth in a communication. More throughput of the actual message to be communicated can be achieved by minimizing overhead.
Second, the cipher should have a very long cycle before it begins to repeat itself. The overall cycle length refers to the number of pseudo-random bits a cipher can produce before repeating itself. Generally, the longer the overall cycle length, the more secure the cipher, because there are more possible bit combinations for each time a combination is generated. This is widely known and discussed in the Schneier book referenced above.
Of the various modes of operating a block cipher, cipher feedback (CFB) and output feedback (OFB) are the most popular for use in communications applications. One way in which CFB and OFB block ciphers are used is to input plaintext (containing the actual message to be communicated) into the block cipher. The output would be the ciphertext of the message to be communicated. Another use of these types of block ciphers is as a pseudo-random number generator. The pseudo-random numbers which are generated can be used to then encrypt digital data that contains the message to be communicated. The pseudo-random numbers could also be used for other purposes. For example, the pseudo-random number stream could be used as a rolling code for analog scrambling techniques such as frequency hopping, frequency inversion, or spectral rotation.
It is the use of a block cipher as a pseudo-random number generator (PRNG) that is addressed herein. The input to the block cipher will still be referred to sometimes as “plaintext” and the output “ciphertext”, but it is to be understood that it is the output of the block cipher that is a secure pseudo-random number stream. In digital encryption, for example, when combined with digital data comprising a message, it creates the ultimate encrypted data message. This description will mainly discuss use as a PRNG in digital encryption, but it is not limited to such uses.
A block cipher makes an excellent pseudo-random number generator (PRNG) because it has a very long cycle time, offers many possible output sequences which are key dependent, and is totally deterministic, so that it is easy to construct multiple PRNGs which yield identical pseudo-noise or pseudo-random number (PN) bit streams. Furthermore, it is valuable, in the context of creating a high quality pseudo-random number stream that it also can be generated with high accuracy at a number of devices, either transmitters or receivers or both. Therefore, it i
Darrow Justin T.
Swann Tod
Transcrypt International, Inc.
Zarley McKee Thomte Voorhees & Sease
LandOfFree
Apparatus for and method of overhead reduction in a block... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for and method of overhead reduction in a block..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for and method of overhead reduction in a block... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2459292