Friday, January 8, 2010

Encrypting Text Using Linear Algebra

Each letter is first encoded as a number. Often the simplest scheme is used: A = 0, B =1, ..., Z=25, but this is not an essential feature of the cipher. A block of n letters is then considered as a vector of n dimensions, and multiplied by a n × n matrix, modulo 26. (If one uses a larger number than 26 for the modular base, then a different number scheme can be used to encode the letters, and spaces or punctuation can also be used.) The whole matrix is considered the cipher key, and should be random provided that the matrix is invertible in \mathbb{Z}_{26}^n (to ensure decryption is possible).
Consider the message 'ACT', and the key below (or GYBNQKURP in letters):
\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix}
Since 'A' is 0, 'C' is 2 and 'T' is 19, the message is the vector:
\begin{pmatrix} 0 \\ 2 \\ 19 \end{pmatrix}
Thus the enciphered vector is given by:
\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix} \begin{pmatrix} 0 \\ 2 \\ 19 \end{pmatrix} = \begin{pmatrix} 67 \\ 222 \\ 319 \end{pmatrix} \equiv \begin{pmatrix} 15 \\ 14 \\ 7 \end{pmatrix} \pmod{26}
which corresponds to a ciphertext of 'POH'. Now, suppose that our message is instead 'CAT', or:
\begin{pmatrix} 2 \\ 0 \\ 19 \end{pmatrix}
This time, the enciphered vector is given by:
\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix} \begin{pmatrix} 2 \\ 0 \\ 19 \end{pmatrix} \equiv \begin{pmatrix} 31 \\ 216 \\ 325 \end{pmatrix} \equiv \begin{pmatrix} 5 \\ 8 \\ 13 \end{pmatrix} \pmod{26}
which corresponds to a ciphertext of 'FIN'. Every letter has changed. The Hill cipher has achieved Shannon's diffusion, and an n-dimensional Hill cipher can diffuse fully across n symbols at once.
Article found at http://en.wikipedia.org/wiki/Hill_cipher
Alexander Abi Chaker 20091978
Posted by at
Labels:

1 comment:

  1. UnknownJanuary 8, 2010 at 9:49 AM

    OK Alexander, this is a better post, even though this idea has been written many times before. So, nothing new in your post. But better than before.

    Zeina

    ReplyDelete

Subscribe to: Post Comments (Atom)