Cryptography

Cryptography which is both an art and a science deals with techniques for encoding and decoding messages that are exchanged between two parties. 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.

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”.

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.

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

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.

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.

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 inverting and multiplying matrices.

Hill Method

Hill's cipher was introduced in 1929 by Hunter College (NY) mathematician Lester S. Hill (1892--1961). This method is a symmetric cryptographic techniques that employs matrices for encryption/decryption purposes using modular arithmetic and modular matrices.

An essential part of Hill's method is modulo inversion of a square matrix that include the folloing steps.

• First, compute the determinant of the matrix, detA. If detA is coprime to p, then you can be sure that A is invertible modp.
• Find the inverse of detA modulo p. This matrix we denote by (detA)⁻¹ and will be the unique integer between 0 and p which satisfie (detA) × (detA)⁻¹ ≡ 1 mod p.
• Next, compute the matrix of cofactors of A, call this B. So, this is the matrix which would have been the usual inverse of A, without division by the determinant.
• The matrix (detA)⁻¹ × B is an inverse to A modulo p. All entries of this matrix must be between 0 and p.

For example, suppose you need to find the inverse matrix modulo 26 of \( {\bf N} = \begin{bmatrix} 1 & 5 \\ 3 & 4 \end{bmatrix} . \) Since its determinant is −11, which is 15 modulo 26, we have

The determinant is −11 (mod 26). So Hence the inverse is suppose to be 7 rather than −7. So

suppose a plain text message ‘EJ' must be sent. The letters reduce to the vector x = [4, 9]^T. Now consider matrix

Then Therefore, the reciever gets a message \( \begin{bmatrix} \mbox{F} \\ \mbox{O} \end{bmatrix} . \) The receiver picks the message FO transforms it to vector z = [6, 15]^T.

To find modular inverse of k, it is m if and only if k m mod p = 1. Namely,

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 Ronald 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.

 

Subsection: Exercises