Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1999-12-02
2004-10-12
Barrón, Gilberto (Department: 2132)
Cryptography
Particular algorithmic function encoding
C380S045000, C708S497000, C708S607000, C708S630000, C713S176000
Reexamination Certificate
active
06804354
ABSTRACT:
THE FIELD OF THE INVENTION
The present invention generally relates to cryptosystems, and more particularly relates to private-key stream cipher cryptosystems which employ at least one pseudo-random number generator (PRNG) and post-processing cryptographic isolator to obscure the PRNG state. The combination of PRNG and isolator produces pseudo-random bit keystreams for combining with plaintext to encrypt the plaintext into ciphertext and for combining with the ciphertext to decipher the ciphertext into plaintext.
BACKGROUND OF THE INVENTION
Cryptosystems perform cryptography to transform plaintext into ciphertext so that only an authorized receiver can transform the ciphertext back into the original plaintext. Encryption or enciphering is the process that transforms plaintext into ciphertext. Decryption or deciphering is the process that transforms ciphertext into plaintext.
A parameter called an encryption key is employed by a cryptosystem to prevent the plaintext from being easily revealed by an unauthorized person. A sender transforms a given plaintext into a large variety of possible ciphertext selected by the specific encryption key. A receiver of the ciphertext deciphers the ciphertext by employing a parameter referred to as a decryption key. In a publickey cryptosystem, the encryption key is made public while the decryption key is kept secret. Therefore, in public key cryptosystems, the decryption key must be computationally infeasible to deduce from the encryption key. In a private-key cryptosystem, the sender and the receiver typically share a common key that is used for both enciphering and deciphering. In such a private-key cryptosystem, the common key is alterable and must be kept secret.
Private-key cryptosystems are typically implemented as block cipher cryptosystems or stream cipher cryptosystems. Block cipher cryptosystems divide the plaintext into blocks and encipher each block independently using a stateless transform. In block cipher cryptosystems if one fixed common private-key is employed to encipher different occurrences of a particular plaintext block, all of these occurrences are encrypted into identical corresponding ciphertext blocks. Therefore, the block size is preferably selected to be large enough to frustrate attacks from a crytanalysis, which analyzes the occurrence frequencies of various patterns among the ciphertext blocks. Example block sizes are 64 bits and 128 bits.
In stream cipher cryptosystems, the plaintext is typically encrypted on a bit-by-bit or word-by-word basis using a stateful transform that evolves as the encryption progresses. In encrypting the plaintext binary data sequence for transmission as a ciphertext binary data sequence, the common private-key is a parameter which controls a pseudo-random number generator (PRNG) to create a long sequence of binary data referred to as a keystream. The stream cipher cryptosystem includes a cryptographic combiner, which combines the keystream with the plaintext sequence. The cryptographic combiner is typically implemented with exclusive-or (XOR) bit-wise logic gates, which perform bit-wise modulo-2 addition. The cryptographic combiner produces the ciphertext. At the receiver, the common private-key controls a receiver PRNG to produce a decryption keystream. The decryption keystream is combined with a decryption combiner to decrypt the ciphertext to provide the plaintext to the receiver. The receiver decryption combiner operation must be the inverse of the sender encryption combiner operation. For this reason, the most common combiner operation is bit-wise XOR which is its own inverse.
One problem with stream cipher cryptosystems is the difficulty of generating a long, statistically uniform, and unpredictable sequence of binary data in the keystream from a short and random key. Such sequences are desirable in the keystream in cryptography to make it impossible, given a reasonable segment of its data and sufficient computer resources, to find out more about the sequences.
There are three general requirements for cryptographically secure keystream PRNGs. First, the period of a keystream must be large enough to accommodate the length of the transmitted message. Second, the keystream output bits must be easy to generate. Third, the keystream output bits must be hard to predict. For example, given the PRNG and the first N output bits, a(
0
), a(
1
), . . . , a(N−1), it should be computationally infeasible to predict the (N+1)
th
bit a(N) in a sequence with better than a 50—50 chance. In otherwords, a cryptanalyst should not be able to generate other forward bits or backward bits if presented with a given portion of the keystream output sequence.
The PRNG employed in stream cipher cryptosystems, often employs a feedback shift register (FSR) which includes N storage elements and a feedback function that expresses each new element a(t) of the sequence, in terms of the previous generated elements a(t−N), a(t−N+1), . . . , a(t−1). Each individual storage element of the FSR is called a stage, and the binary signals a(
0
), a(
1
), a(
2
), . . . , a(N−1) are loaded into the stages as initial data to generate the Keystream sequence. The period of the keystream sequence produced by the FSR depends both on the number of stages and on the details of the feedback function. The maximal period of a keystream sequence generated by an N-stage FSR with a non-singular feedback function is 2
N
, which represents the number of possible states of the N-stage FSR.
Depending on whether the feedback function is linear or is non-linear, the FSR is referred to respectively as a linear feedback shift register (LFSR) or a non-linear feedback shift register (NLFSR).
In particular, the LFSR is employed in many PRNGs for stream cipher cryptosystems. The LFSR feedback function is of the form a(t)=c
1
a(t−1) XOR c
2
a(t−2) XOR . . . XOR C
N−1
a(t−N+1) XOR a(t−N), where c
j
is an element of the set {
0
,
1
}. The feedback function of an LFSR can be represented formally by what is referred to as a feedback polynomial:
f
(
x
)=1+
c
1
x+c
2
x
N−2
+ . . . +c
N−1
x
N−1
+x
N
where the intermediate x has no other meaning than as a mathematical symbol. This feedback polynomial decides the period and the statistical behavior of the keystream output sequence. To avoid trivial output, the zero-state should be excluded from the initial setting. This limits the largest possible period of an LFSR to 2
N
−1.
In general, to generate the largest possible period 2
N
−1 for the output sequence, the feedback polynomial f(x) of the LFSR should be primitive. A sequence generated by an LFSR with a primitive feedback polynomial is referred to as a maximal-length LFSR sequence or simply an m-sequence. However, m-sequences cannot be used as keystreams without undergoing further cryptographic transformation. Without this further cryptographic transformation, the key of secrecy (i.e., the initial state of the LFSR and the feedback function of the LFSR) of an N-stage LFSR can be determined from just 2N successive bits of the output sequence.
Efficient synthesis procedures exist for finding feedback polynomials of the shortest LFSR that would generate a given output sequence. The length of such an LFSR is referred to as the linear complexity of the sequence. As a result, an LFSR suitable for employment in a cryptosystem, must guarantee a large enough key independent lower bound to the linear complexity of the sequences the LFSR generates.
The “known plaintext” cryptanalysis attack combines known or guessed plaintext with ciphertext to recover the keystream. Recovering 2N bits destroys the secrecy of an LFSR. Therefore, maximal-length LFSR output sequences cannot be used as keystreams without undergoing further cryptographic transformation. A common method for providing this further cryptographic transformation is to add cryptographic isolators, which provide post-processing of the output of an L
Barrón Gilberto
Fredrick Kris T.
Honeywell International , Inc.
Stulberger Cas
LandOfFree
Cryptographic isolator using multiplication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cryptographic isolator using multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cryptographic isolator using multiplication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3286652