Cryptography – Communication system using cryptography – Data stream/substitution enciphering
Reexamination Certificate
1998-06-23
2002-12-03
Hayes, Gail (Department: 2132)
Cryptography
Communication system using cryptography
Data stream/substitution enciphering
C380S042000, C380S044000, C380S046000
Reexamination Certificate
active
06490354
ABSTRACT:
BACKGROUND OF THE DISCLOSURE
1. Field of the Invention
The invention relates to cryptography, particularly a word-oriented technique for generating a pseudo-random sequence, such as a keystream for use in, e.g., a stream cipher. Advantageously, this technique is not only fast and secure but also requires relatively little processing power to implement, i.e., is “lightweight”.
2. Description of the Prior Art
Over the centuries, for as long as information has been communicated between two individuals, the information has been susceptible to third-party interception, eavesdropping, compromise and/or corruption. Clearly, the problem of securely protecting information from such acts has existed for quite a long time.
Traditionally, this problem has been handled through the development, over the years, of increasingly sophisticated cryptographic techniques. One class of these techniques involves key-based ciphers. Through a key-based cipher, sequences of intelligible data, i.e., plaintext, that collectively form a message are each mathematically transformed, through an enciphering algorithm, into seemingly unintelligible data, i.e., so-called ciphertext. Not only must the transformation be completely reversible, i.e., two way in the sense that the ciphertext must be invertable back to its corresponding original plaintext but also on a 1:1 basis, i.e., each element of plaintext can only be transformed into one and only one element of ciphertext. In addition, a particular cipher that generated any given ciphertext must be sufficiently secure from cryptanalysis. To provide a requisite level of security, a unique key is selected which defines only one unique corresponding cipher, i.e., precluding, to the extent possible, a situation where multiple differing keys each yields reversible transformations between the same plaintext-ciphertext correspondence. The strength of any cryptographic technique and hence the degree of protection it affords from third-party intrusion is directly proportional to the time required, by a third-party, to perform cryptanalysis, e.g., with a key-based cipher to successfully convert the ciphertext into its corresponding plaintext without prior knowledge of the key. While no encryption technique is completely impervious from cryptanalysis, an immense number of calculations and an extremely long time interval required therefor—given the computing technology then available—required to break a cipher without prior knowledge of its key effectively renders many techniques, for all practical intents and purposes, sufficiently secure to warrant their widespread adoption and use.
Key-based ciphers include both symmetric and public-key algorithms. Inasmuch as public-key algorithms are not relevant to the present invention, they will not be discussed any further.
Symmetric algorithms are those through which the encryption key can be calculated from the decryption key, and vice versa. Generally, in these algorithms, the two keys are the same, with the security of the algorithm resting, in good measure, on the security of the key. Symmetric algorithms themselves are divided into stream ciphers (also referred to as “stream algorithms”) and block ciphers. A stream cipher operates on a bit or byte of plaintext at a time, in contrast to block ciphers which operates on a predefined group of bits (a “block”, such as 64 bits) of plaintext at a time. Since block ciphers are also not relevant to the present invention, they will also not be discussed any further.
A very simple form of a stream cipher relies on generating, at an encryption end and through a so-called keystream generator, a pseudo-random sequence (K) of bits k
1
, k
2
, k
3
, . . . , k
n
. These bits are combined, on a bit-by-bit exclusive-OR (XOR) basis, with incoming bits of plaintext (P), specifically p
1
, p
2
, p
3
, . . . , p
n
to yield resulting bits (C), specifically c
1
, c
2
, c
3
, . . . , c
n
, of ciphertext. At a decryption end, the bits of ciphertext are combined, again on a bit-by-bit XOR basis, with an identical keystream to recover the plaintext bits. With this cipher, the security of the cipher itself, apart from that of the key itself, rests entirely on the keystream, i.e., the level of difficulty which a cryptanalyst encounters in attempting to discern, from the ciphertext, the algorithm that generates the pseudo-random keystream. With a stream cipher, both the encrypting and decrypting ends of a communications link use identical keystream generators that are initialized in the same manner and operate in synchronization with respect to the ciphertext. Identical keystreams assure, in the absence of transmission and other errors, that the recovered plaintext will match the incoming plaintext. For further details on stream ciphers, the reader is referred to B. Schneier,
Applied Cryptography—Second Edition
(© 1996, John Wiley and Sons) pages 197-199 and 397-398; and G. Simmons,
Contemporary Cryptography
(©1992, IEEE Press), pages 67-75—which are all incorporated by reference herein.
As recently as a few years ago, if a cipher was of such complexity that it required on the order of man-years or more to break, in view of the state of the processing technology then available to do so, the underlying cryptographic technique was viewed by many as rendering a sufficient degree of security to warrant its use. However, computing technology continues to rapidly evolve. Processors, once unheard of just a few years ago in terms of their high levels of sophistication and speed, are becoming commercially available at ever decreasing prices. Consequently, processing systems, such as personal computers and workstations, that were previously viewed as not possessing sufficient processing power to break many so-called “secure” cryptographic ciphers are now, given their current power and sophistication, providing third parties with the necessary capability to effectively break those same ciphers. What may have taken years of continual computing a decade ago can now be accomplished in a very small fraction of that time. Hence, as technology evolves, the art of cryptography advances in lockstep in a continual effort to develop increasingly sophisticated cryptographic techniques that withstand correspondingly intensifying cryptanalysis.
Over the past few years, the Internet community has experienced explosive and exponential growth—growth that, by many accounts, will only continue increasing. Given the vast and increasing magnitude of this community, both in terms of the number of individual users and web sites and sharply reduced costs associated with electronically communicating information, such as e-mail messages and electronic files, over the Internet between one user and another as well as between any individual client computer and a web server, electronic communication, rather than more traditional postal mail, is rapidly becoming a medium of choice for communicating information, whether it be, e.g., an e-mail message or a program update file. In that regard, the cost of sending an electronic file between computers located on opposite sides of the Earth is a very small fraction of the cost associated with storing that file on a diskette (or other media) and transporting that media between these locations even through the least expensive class of postal mail service. However, the Internet, being a publicly accessible network, is not secure and, in fact, has been and increasingly continues to be a target of a wide variety of attacks from various individuals and organizations intent on eavesdropping, intercepting and/or otherwise compromising or even corrupting message traffic flowing on the Internet or illicitly penetrating sites connected to the Internet. This security threat, in view of the increasing reliance placed on use of the Internet as a preferred medium of communication, exacerbates the efforts in the art, otherwise fostered by primarily continuing advances in computing power, to develop increasingly strong cryptographic techniques that provide enhanced levels of security to electronic communication.
Boneh Dan
Venkatesan Ramarathnam R.
Hayes Gail
Meislahn Douglas J.
Michaelson Peter L.
Michaelson & Wallace
Microsoft Corporation
LandOfFree
Lightweight word-oriented technique for generating a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lightweight word-oriented technique for generating a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lightweight word-oriented technique for generating a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2981775