Cryptography – Communication system using cryptography – Data stream/substitution enciphering
Reexamination Certificate
1999-06-08
2004-09-14
Darrow, Justin T. (Department: 2132)
Cryptography
Communication system using cryptography
Data stream/substitution enciphering
C380S028000, C380S042000, C380S044000, C380S259000, C382S232000
Reexamination Certificate
active
06792108
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital data encryption. More particularly, the invention relates to data encryption using very long binary sequences (keystream) generated from a sequence generator using initialization parameters, such as a quasi-crystal generator, as described herein.
BACKGROUND OF THE INVENTION
Some current encryption practices known as stream ciphers are based on the use of a keystream generated from an encryption key and which encrypts plaintext into ciphertext according to an encryption scheme. The most common and simple-to-compute encryption scheme is the exclusive-OR or XOR logic function. In the encryption processor, the ciphertext is generated by XOR'ing the computer-word-size blocks of the plaintext with the corresponding computer-word-size blocks of the keystream. To decrypt the message, the same keystream generated using the same key is XOR'ed with the ciphertext to obtain the original plaintext. If the key space is as large as the plaintext space, in which case the key is used as the keystream, and if there is no repetition of the use of the key, the encryption is considered to be unconditionally secure. This encryption process is called a one-time pad.
In such encryption, both the sender and the receiver must share the key. The transmission of the key must be carried out using a secure channel, or using a secure encryption scheme over an unsecure channel. If the key is very long, the transmission of the key creates greater overhead for the encryption communication. This motivates the design of stream ciphers where the keystream is pseudo-randomly generated from a smaller secret key. Common stream ciphers are based on cryptographically secure pseudo-random bit generators (CSPRBG's).
The use of pseudo-random number generators (PRNG's) to provide a stream cipher is known in the art. According to this technique, the shared secret (short) key represents parameters used in PRNG and a stream is obtained from a sequence of pseudo-random generated numbers. This stream is then used for enciphering the plaintext at the sender's end and deciphering the ciphertext at the receiver's end.
PRNGs are much more computationally efficient than CSPRBG's, however they are not cryptographically secure. PRNG's are periodic, and while their period may be very long, specific patterns of the sequence indicate position in that sequence, and it becomes possible for an attacker having some knowledge of the plaintext to determine the position in the periodic sequence and break the cipher. In some cases, PRNG's are so unsecure that an attacker may obtain directly the type of PRNG used only from looking at a small part of the sequence.
U.S. Pat. No. 5,835,597 to Coppersmith et al. and assigned to IBM describes a software-efficient pseudo-random function which maps an index and an encryption key to a pseudo-random bit string useful for constructing a stream cipher. The method begins by preprocessing the encryption key into a table of pseudo-random values. The index and a set of values from the table is then used to generate a set of initial values for the registers. At least some of the register values are modified in part by taking a current value of a register and replacing the current value with a function of the current value and a value retrieved from the table, the latter value being determined by the values in one or more other registers. After modifying the register values in this fashion, the values are masked using other values from the table and the results then concatenated into the pseudo-random bit string. The modification step is repeated and a new masked function of the register values is then concatenated into the pseudo-random bit string. The modification and concatenation steps are repeated to continue growing the pseudo-random bit string until the string reaches some desired length. The publicly known pseudo-random functions lack true randomness and/or require significant computational effort.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a method and apparatus for generating very long binary keystreams. This is done in two main steps: first by generating sequences which are aperiodic and simple to compute, and then by coloring selected elements of the sequences, that is attributing binary strings to selected elements of the sequences.
The invention also provides for the use of PRNG's in combination with aperiodic functions, functions which generates a series of values in an unpredictable manner without any periodic repetition of the series. Aperiodic functions, which can be obtained from quasi-crystals, can be used in order to hide all non-randomness in the PRNG's.
The invention provides a method of encrypting data comprising:
a) defining symmetric key parameters specifying at least one quasi-crystal function and a starting point;
b) calculating consecutive aperiodic values of the quasi-crystal function;
c) using the aperiodic values of the quasi-crystal function in a predetermined process of generating a series of encryption pad values, the predetermined process being defined by the key parameters; and
d) encrypting the data using the pad values.
The method can be used for encrypting a message to be transmitted, and of course for decrypting an encrypted message received. The invention may be used to provide terminal equipment with modest processing power for carrying out the encryption and description for digital communications.
The invention also provides a method of applying a digital watermark to a selected portion of a document, the selected portion being modifiable without being easily detected, the method comprising:
applying a quasi-crystal transformation to the selected portion of the document;
applying a watermark to the transformed selected portion; and
applying an inverse quasi-crystal transformation to the watermarked selected portion. Preferably, the quasi-crystal transformation is a two-dimensional transformation. The watermark applied to the transformed selected portion may comprise a visually identifiable mark.
The encryption method according to the invention has no analog in current cryptographic practice. Its encryption class may be considered to be situated between the one-time-pad method and the stream cipher method with a secret symmetric encryption key. It can be used either for transmission of digital data or as an identification system, allowing a number of hybrid variants and combinations with other encryption types such as block ciphers and watermarks. The encryption system makes use of truly infinite, completely aperiodic point sets (referred to herein as quasi-crystals) which can be generated by a fast algorithm in any dimension from a few real numbers provided in the encryption key. In the one-dimensional case, the points can be taken simply as a discrete set of real numbers, in n-dimensions these are points of an n-dimensional Euclidean space, that is n-tuples of real numbers. The distances between adjacent points along any direction (in n-dimensional quasi-crystal) can take only a small number of distinct values. More information on 2-dimensional quasi-crystals, is given hereinbelow in the description of the watermark embodiment.
The advantage of exploitation of quasi-crystals in comparison with prior art cryptographic methods include:
It can be used for encryption of any type of digital data and of any dimension (for parallel data transmission).
The keystream is derived from quasi-crystal points transformed into a binary form. It can be infinite and aperiodic in the strongest sense: it contains no periodic subsets. Therefore linguistic analysis of the encrypted message is useless: repeated words are encrypted differently: partial knowledge of the content of the encrypted message can be of no help for decryption of the rest of the mesage.
The encryption can be very fast. Quasi-crystals can be generated point by point in real time during the data encryption and decryption, starting from any of its points (seed point). A
Masakova Zuzana
Patera Jiri
Pelantova Edita
Darrow Justin T.
Kudirka & Jobse LLP
Universite De Montreal
LandOfFree
Aperiodic encryption for digital data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Aperiodic encryption for digital data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Aperiodic encryption for digital data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3204989