Cryptography – Video cryptography – Video electric signal modification
Reexamination Certificate
1998-10-07
2002-02-05
Tu, Christine T. (Department: 2132)
Cryptography
Video cryptography
Video electric signal modification
C380S200000, C380S212000, C380S255000, C380S268000, C380S044000, C713S150000
Reexamination Certificate
active
06345101
ABSTRACT:
BACKGROUND OF THE INVENTION
There are many real world situations when one would like to protect the information in a message, or any kind of data in general from an eavesdropper. For example, one might need to communicate between two stations over a link that is not secure or one might need to store data at an insecure location. Cryptographic methods provide the means to protect such data. By encrypting the data, one makes it an almost infeasible task for an unwanted third person to obtain the original data from the encrypted data. If only the encrypted data is transmitted over or stored at an insecure channel, then the original data or the information in the data is secure from an eavesdropper.
Cryptographic methods use an algorithm (a sequence of mathematical operations) and one or more “keys” to encrypt and decrypt the data. Security of the data to be communicated or stored over insecure channels relies on the fact that the algorithm used for encryption has no inherent weaknesses which can be exploited to break the algorithm. At the same time no eavesdropper should be able to intercept all or part of the keys that were used for encryption.
Encryption, involves transforming the original data or “plain-text” into encrypted data or “cipher-text.” As described by Shannon [3], the idea behind encryption is to use confusion and diffusion to hide any easy to spot relationship between the plain-text and the cipher-text. Confusion is introduced by changing plain-text locally and diffusion is introduced by spreading the plain-text over a larger region in the cipher-text. The encryption method should be such that one can encrypt the plain-text rather easily, while decryption is very hard without the key, but can be done very easily with the key.
A common class of cryptographic methods, known as “symmetric algorithms,” uses the same key for both encryption and decryption. “Symmetric algorithms” that encrypt a fixed-sized data block at a time are called “block ciphers.” A very popular block cipher is DES, which was developed by IBM. It uses repeated applications of permutations (rounds), substitutions (based on a lookup tables which are called S-boxes, E-boxes and P-boxes), interchanging the left and the right half of the data block and exclusive OR operations (XORs). A detailed description of DES can be found in Ehrsain [1].
DES has undergone extensive scrutiny by the cryptographic community. In the scientific community there are a few unanswered questions about the DES algorithm, e.g. why it has only 16 rounds and how and why its particular S-boxes, E-boxes and P-boxes were chosen. It has also been demonstrated by Shamir and Biham [4], that reduced-round (fewer than 16 round) variants of DES are susceptible to differential cryptanalysis.
The security of an encryption method can be increased by using many complex operations from different algebraic groups for encryption. The disadvantage is that these complex operations require a lot of processing time. The complexity of these operations can also make it difficult to see if a trapdoor is hidden somewhere in the method. A trapdoor is some property of the encryption method that can be exploited to obtain the key more easily than a brute-force, exhaustive search of possible keys.
Another popular block cipher is IDEA. The IDEA cipher derives its security by mixing operations from different algebraic groups. A detailed description of the algorithm can be found in Massey [2]. The operations used in IDEA are the following:
Addition modulo 2
16
XOR
multiplication modulo 2
16
+1
The above mentioned examples of block ciphers help illustrate different ways of constructing block ciphers. They also help point out the shortcomings of the common block ciphers when used in real world applications. One can broadly classify the shortcomings of block ciphers into:
Susceptibility to cryptanalysis. Shamir and Biham[4] have successfully cryptanalysed many block ciphers, including DES, using differential cryptanalysis. Differential cryptanalysis has been very successful in breaking ciphers that use S-boxes. Other methods of cryptanalysis, such as linear cryptanalysis and dictionary attacks, have also been studied and used in this context extensively.
Resource intensiveness. Ciphers such as IDEA use multiplication and addition to enhance their security, but these operations are computationally intensive. One can increase encryption speed by using specialized hardware implementation of these algorithms. Because of the complexity of the operations used in the algorithms, even such hardware can be complex and expensive. In certain applications such as mobile communications, cost and power consumption are very important factors and should be kept as low as possible.
I have designed a method and apparatus for data communication and storage that addresses the above mentioned concerns about block ciphers. The invention can be used for many applications, including, but not limited to:
Secure message exchange in mobile communications.
Secure data transfer over the internet.
Secure online financial transactions by securing credit card numbers or pin numbers for financial transactions.
Transmission of data to and from the satellites.
Prevention of unauthorized access to the contents of files stored on storage mediums such the computer hard drives, floppy disks, and random access memory (RAM), as well as other electronic, magnetic and optical storage media.
Encryption of information stored in integrated circuit memories so that its designs are harder to reverse engineer.
SUMMARY OF THE INVENTION
I present a new method and apparatus to secure data from, among things, eavesdroppers, by encrypting it. The encrypted data can be either transmitted to the destination or stored at a desired location.
The invention avoids the use of many standard techniques used in encryption methods such as multiplication, addition, discrete logarithms, S-boxes. The invention uses the XOR operation along with a new way to shuffle data blocks that can be easily implemented in hardware. In addition, these operations allow for the data block size and key size to be changed without significant modifications to the overall method. The latter, in particular, is a significant advantage over previous block ciphers such as DES where changes in the data block size or key length necessitate redesigning of the S-boxes, E-boxes and P-boxes. And since the operations used in the method are simple and their properties well-understood in the art, trapdoors are unlikely to be present.
To produce the cipher-text of a given plain-text in the method, one needs a key, K, and a data string, S, which is used for the XOR operation. The steps involved in encryption and decryption are as follows:
Generation of the key K, and a string S, which are the same length as defined for the data blocks. The key is used for the shuffle operation and the string is used for one of the XOR operations.
Splitting of the plain-text into data blocks of fixed length. If the last data block is smaller than the desired size, it is padded with extra bits to make it the same size as the other data blocks.
Repeated application (also known as “rounds”) of three operations. The first operation is the XOR of the data block D, with the string S, to obtain a new data block, D
1
=XOR
1
(D,S). The second operation shuffles the bits of the data block D
1
, to obtain a new data block, D
2
=SHUFFLE(D
1
,K). The last operation of every round is a second type of XOR that uses the bits of the data block D
2
, and produces a new data block D
3
=XOR
2
(D
2
). After the last round we obtain the cipher-text which will be referred to as E. These operations will be described in more detail below.
To decrypt the cipher-text E, I follow a procedure similar to the one used to encrypt the data. The number of rounds remains the same and each round has three operations. The operations are modified so that they reverse the effect of the operations used for encryption. The first operation is an
Jack Todd
Tu Christine T.
LandOfFree
Cryptographic method and apparatus for data communication... 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 method and apparatus for data communication..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cryptographic method and apparatus for data communication... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2941531