Encryption technique using stream cipher and block cipher

Details Encryption technique using stream cipher and block cipher Encryption technique using stream cipher and block cipher

1998-12-01

2002-07-02

Decady, Albert (Department: 2132)

Cryptography

Communication system using cryptography

C380S037000, C380S283000, C380S028000, C380S030000

Reexamination Certificate

active

06415032

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
This application relates to the following commonly assigned, concurrently filed U.S. patent application:
Ser. No. 09/203,236 invented by Charles M. Doland entitled “METHOD AND APPARATUS FOR DETECTING ALTERATIONS IN DATA MESSAGES”, which is incorporated herein by reference.
FIELD OF THE INVENTION
The present invention relates generally to the field of message encryption and more particularly to the field of pseudo-random sequence generation for message encryption.
BACKGROUND OF THE INVENTION
A wide area network such as the Internet may connect thousands of network nodes, including routers, bridges, hubs, servers, and user terminals. In transmitting a message from a sender node to a receiver node over a wide area network, security is a great concern, because messages in transmission are susceptible to interception by unintended third parties at any network node. This problem is typically addressed by encrypting a private message at the sender node prior to transmission of the message, then decrypting the message at the receiver node. Encryption refers to a process of disguising a message sent from a sender node so that an unintended third party cannot recover the meaning of the message, even if the unintended third party has intercepted the message. Decryption refers to a process of recovering an encrypted message after an intended receiver node has received the encrypted message. For a receiver to recover an encrypted message received from a sender, the sender and the receiver must both agree on a predetermined encryption and decryption system.
An encryption and decryption system can be conveniently described using the following notations, where:
(1) a plain (not encrypted) message is denoted by P;
(2) an encryption transformation function is denoted by E;
(3) an encrypted message is denoted by C, where C=E(P);
(4) a decryption transformation is denoted by D; and
(5) a decrypted message is also denoted by P, where P=D(E(P)).
Note that a decrypted message has the same notation as a plain message, because decrypting an encrypted message returns the original, unencrypted message.
To enhance security, most modern encryption systems use an encryption key, denoted by K
e
, to encrypt messages prior to transmitting the messages, and a decryption key, denoted by K
d
, to decrypt the messages upon receiving the messages. (The decryption key is often transmitted to the receiver node using a secure communication channel, to improve the security of the message, which can then be sent over an insecure channel.) In the available art, there are two general forms of key-based encryption and decryption systems: symmetric-key and public-key. In symmetric-key systems, the encryption key can be calculated from the decryption key and vice versa. Since in many such systems the encryption key K
e
and the decryption key K
d
are the same, the encryption key and the decryption key can be denoted by K. Thus, a symmetric encryption and decryption system can be described using the following notations, where:
(6) a plain message is denoted by P;
(7) a symmetric key is denoted by K;
(8) an encryption transformation is denoted by E
K
;
(9) an encrypted message is denoted by C, where C=E
K
(P);
(10) a decryption transformation is denoted by D
K
; and
(11) a decrypted message is also denoted by P, where P=D
K
(E
K
(P)).
A simple exemplary symmetrical transformation between a sender and a receiver is the XOR logic operation. In this transformation, the plain message is “XORed” bit by bit with the key to generate an encrypted message. To regenerate the message at the receiver node, the encrypted message is once again XORed with the key. This series of operations reproduces the original message. Using the XOR logic operation, a symmetric-key encryption and decryption process can be described as follows:
E
K
(
x
)=
x XOR K;
  (12)
D
K
(
x
)=
x XOR K;
  (13)
C=E
K
(
P
)=
P XOR K;
  (14)
and
P=D
K
(
C
)=
C XOR K=
(
P XOR K
)
XOR K.
  (15)
Symmetric encryption and decryption systems are divided into two categories: stream ciphers and block ciphers. A cipher refers to a mathematical function (such as XOR) used for encryption and decryption. In a stream cipher, a message is encrypted one bit at a time. In a block cipher, a message is encrypted a block at a time.
In real world applications, encrypted messages are subject to attack, a process of recovering the encrypted messages without being informed about the encryption algorithm or the encryption key. The security of an encryption system against attack typically depends on two elements: the strength of the encryption algorithm selected and the length of the key used.
Usually, a more secure encryption algorithm is more complicated than a less secure encryption algorithm. Consequently, greater expense and time are required to attack a more secure encryption algorithm. However, often more time and computing power are also required to perform the encryption and decryption using a more secure encryption algorithm. In some commercial settings, such costs are not necessary or feasible. By way of example, a consumer may use a desktop computer at home to conduct a real-time business transaction. The consumer's desktop computer may not have the computing power to perform a complicated encryption and decryption at such high speed. Further, if the amount of the business transaction is less than $1,000.00, an attacking cost above $1,000.00 will make the attack non-advantageous. As another example, some messages are only confidential for a short period of time, e.g., two months. A simple encryption algorithm is sufficient for such messages, if the attacking time takes more than two months. However, selecting a simple encryption algorithm leaves a user more vulnerable to attack than selecting a more complicated encryption algorithm.
The bit length of the key also affects the security of an encryption system. Any key-based encryption method is susceptible to a “brute force” attack. A brute force attack attempts to decrypt a message by applying the decryption function to the message, using each of the possible keys. To be secure against this type of attack, there must be a sufficient number of possible keys to make the attack too time-consuming to be useful. If a key is represented as a binary integer, the number of possible keys is 2
n
, where n is the number of bits in the key. Thus, in general, longer keys provide greater security against a brute force attack. For any given encryption method, there may be other methods of attacking or breaking the encryption, as well.
The choice between simple and complicated encryption algorithms presents a dilemma. While it is desirable to use simple encryption algorithms to suit some business transaction settings, selecting a simple encryption algorithm leaves an encrypted message vulnerable to attack. Similarly, increasing a key bit length increases the number of possible keys, thus enhancing the security of a encrypted message.
Therefore, there is a need to provide a method of encrypting messages adaptable to using a relatively simple encryption algorithm without compromising the security of encryption.
SUMMARY OF THE INVENTION
The present invention provides a novel method of generating a pseudo-random sequence of integers, and applies the method to the encryption of messages. The method uses a key K and a pair of prime numbers p and q, where q=2p+1. Specifically, a sequence of integers z(i), i=1, 2, . . . , n, is generated as follows.
y
(
i
)=
K
i
mod q
  (16)
z
(
i
)=
y
(
i
), if
y
(
i
)≦
p
  (17)
z
(
i
)=
q−y
(
i
), if
y
(
i
)>
p
  (18)
According to a first aspect of the invention, the sequence of integers is used to generate a stream cipher. Specifically, a sequence of integers z(i) is formed according to equations (16)-(18), where i=1, 2, . . . , n. A sequence of bits b(i) is then forme

Affiliated with

Also associated with

Rating

Encryption technique using stream cipher and block cipher does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Encryption technique using stream cipher and block cipher, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encryption technique using stream cipher and block cipher will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2820430