Vladimir Dobrushkin

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the appendix entitled GNU Free Documentation License.


Cryptography is the study of the techniques of writing and decoding messages in code. In the language of cryptography, codes are called the ciphers, non-coded messages are called plaintext, and coded messages are called cipher text. The main reason for the use of cryptography, is to communicate with another person without allowing access to anyone outside that party. To do so, party members use some sort of algorithm to make their message unreadable to everyone except for them. Cryptography is very important with the Internet's flow of sensitive information such as personal information and other sensitive information that can be easily monitored by third-parties.

Suppose you like to send a secure message to a friend that no one can understand but the two of you using linear algebra. The first thing we must do is to establish what letters of the alphabet correspond with the numbers. To make this simple, one will be using this key with 27 corresponding with * (space):

 A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
 1  2  3  4  5  6  7  8  9  10  11  13  13  14  15  16  17  18  19  20  21  22  23  24  25  26

Message: > > > L I N E A R * A L G E B R A

Now that we established a key and a message, we can begin to construct our relevant matrices. Here are the numbers that will end up composing our original message.

\[ L(12) I(9) N(14) E(5) R(18) *(27) A(1) L(12) G(7) E(5) B(2) R(18) A(1) \]

STEP 1: We must construct our original message matrix; for this example, we will use rows of 3. The letters will be assembled column to column; we will fill the end of the matrix with 27s to use as “spaces”.

\[ {\bf M} = \begin{bmatrix} 12&5&1&5&1 \\ 9&18&12&2&27 \\ 14&27&7&18&27 \end{bmatrix} . \]

STEP 2: Now that we have our original message, we need an encoding matrix that will be used to create a random message. It is necessary that it is invertible due to the decoding we will be doing later.

\[ {\bf E} = \begin{bmatrix} 1&2&3 \\ 4&5&6 \\ 7&8&1 \end{bmatrix} . \]

STEP 3: Next we must multiply our message matrix by the encoding matrix to obtain a cyphertext matrix X.

\[ {\bf X} = \begin{bmatrix} 72&122&46&63&136 \\ 177&272&106&138&301 \\ 170&206&110&69&250 \end{bmatrix} . \]

STEP 4: The receiver must have a decoding matrix that is used to obtain the original message. This is the inverse of the encoding matrix we created above.

\[ {\bf E}^{-1} = \frac{1}{24} \begin{bmatrix} -43&22&-3 \\ 38&-20&6 \\ -3&6&-3 \end{bmatrix} . \]

STEP 5: Finally we multiple our X matrix by our decoding matrix to retrieve our original message. As you can see it is the exact same matrix that corresponds to our message.

\[ {\bf NM} = {\bf E}^{-1} {\bf X} = \begin{bmatrix} 12&5&1&5&1 \\ 9&18&12&2&27 \\ 14&27&7&18&27 \end{bmatrix} . \]

Conclusion: In all, there are many ways linear algebra can be applied to real world situations, one of which is cryptography. There are different approaches to take when securing a message between partys and this can be done with matrices; all it takes is the knowledge of inversing and multiplying matrices.

RSA Public Key Enscription Scheme

A public-key cryptosystem can be used to enscript messages sent between two communicating parties so that an eavesdropper who overhears the enscripted messages will not be able to decode them. The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978. Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters, had developed an equivalent system in 1973, but this was not declassified until 1997. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message.

 Ronald Rivest    Adi Shamir    Leonard Adleman

Ronald Linn Rivest (born 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). He was a member of the Election Assistance Commission's Technical Guidelines Development Committee, tasked with assisting the EAC in drafting the Voluntary Voting System Guidelines. Adi Shamir (born 1952) is an Israeli cryptographer who made numerous contributions to the fields of cryptography and computer science. Leonard Adleman (born 1945) is an American computer scientist. He received the 2002 Turing Award, often called the Nobel prize of Computer science.