![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
A real matrix K has an inverse if and only if its determinant is non-zero. However, it is important to remember that we are working over We briefly sketch the proof of this fact. First suppose that gcd(det K, 26) = 1. Then det K has an inverse in Hence, K is invertible. Conversely, suppose K has an inverse, K-1. By the multiplication rule for determinants, we have Hence, det K is invertible in REMARK The above formula for K-1 is not very efficient computationally, except for small values of m (say m = 2, 3). For larger m, the preferred method of computing inverse matrices would involve elementary row operations. In the 2 × 2 case, we have the following formula: THEOREM 1.3 Suppose A = (ai,j) is a 2 × 2 matrix over Lets look again at the example considered earlier. First, we have Now, 1-1 mod 26 = 1, so the inverse matrix is as we verified earlier. We now give a precise description of the Hill Cipher over 1.1.6 The Permutation CipherAll of the cryptosystems we have discussed so far involve substitution: plaintext characters are replaced by different ciphertext characters. The idea of a permutation cipher is to keep the plaintext characters unchanged, but to alter their positions by rearranging them. The Permutation Cipher (also known as the Transposition Cipher) has been in use for hundreds of years. In fact, the distinction between the Permutation Cipher and the Substitution Cipher was pointed out as early as 1563 by Giovanni Porta. A formal definition is given in Figure 1.7. As with the Substitution Cipher, it is more convenient to use alphabetic characters as opposed to residues modulo 26, since there are no algebraic operations being performed in encryption or decryption. Here is an example to illustrate:
Example 1.6 Suppose m = 6 and the key is the following permutation π: Then the inverse permutation π-1 is the following: Now, suppose we are given the plaintext shesellsseashellsbytheseashore. We first group the plaintext into groups of six letters: shesel | lsseas | hellsb | ythese | ashore Now each group of six letters is rearranged according to the permutation π, yielding the following: EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS So, the ciphertext is: EESLSHSALSESLSHBLEHSYEETHRAEOS. The ciphertext can be decrypted in a similar fashion, using the inverse permutation π-1. In fact, the Permutation Cipher is a special case of the Hill Cipher. Given a permutation of π of the set {1, . . . , m}, we can define an associated m × m permutation matrix Kπ = (ki,j) according to the formula (A permutation matrix is a matrix in which every row and column contains exactly one 1, and all other values are 0. A permutation matrix can be obtained from an identity matrix by permuting rows or columns.) It is not difficult to see that Hill encryption using the matrix Kπ is, in fact, equivalent to permutation encryption using the permutation π. Moreover, For the permutation π used in the example above, the associated permutation matrices are and The reader can verify that the product of these two matrices is the identity. 1.1.7 Stream CiphersIn the cryptosystems we have studied to this point, successive plaintext elements are encrypted using the same key, K. That is, the ciphertext string y is obtained as follows: Cryptosystems of this type are often called block ciphers. An alternative approach is to use what are called stream ciphers. The basic idea is to generate a keystream z = z1z2 . . . , and use it to encrypt a plaintext string x = x1x2 . . . according to the rule A stream cipher operates as follows. Suppose The keystream element zi is used to encrypt xi, yielding Decrypting the ciphertext string y1y2 . . . can be accomplished by successively computing Here is a formal mathematical definition:
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |