Encryption

Symmetric Encryption

Encryption is transforming something and sending it to another user who is able to decrypt back to it's original form. In symmetric encryption the key that is held by

both users is the same.

This is an example of an early encryption device .

A Scytale works with the a scroll of paper that is wrapped around a wooden stick. The diameter of the stick and the length serve as the key. Once the scroll

is wrapped around the stick the words can be read in an horizontal manner.

Substitution Cipher

This is the cipher that most people are familiar with and maybe used it as a game when we were kids. There are different variations of it. The shift

cipher involves moving the characters by some position. The position number is the key. Wit the position as 1 we can write out the alphabet as:

Plain: 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

Cipher: Z 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

The word "cat" is encrypted to "bzs" .What is the plain text for the encrypted word "etm" ?

In this cipher a single letter will always map to another letter. This sort of cipher is not secure. As an example the below is

some cipher text:

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

Frequency analysis on the above produces the following result.

In the above text "I" is most common character. The most 2 letter combination characters are "XL" and the most 3 letter combination characters are "XLI" .

Now we guess that "I" maps to "e" as "e" is the most common character and "XL" maps to "th" and "XLI" maps to "the" as "th" and "the" are the most common combinations. This means that "X" maps to "t" and "L" maps to "h" . This produces:

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

We can keep going along this route and guessing words in the block above.

Polyalphabetic cipher

The polyalphabetic cipher overcomes the weakness by using a cipher such that a single letter can be mapped to many different letters. The Vigenère cipher is one

such scheme.

Let's assume our key is "CAT" and we want to encrypt the word "SELLER". We keep repeating the key below our plain text.

PLAINTEXT: S E L L E R

KEY: C A T C A T

The letter "C" represents a shift of 3 characters. The letter "S" will be encrypted as "U"

The plaint letter "A" will be written as "C" . To help us we can use a Vigenere square.

PLAINTEXT: S E L L E R

KEY: C A T C A T

For the first letter "S" the key is "C" so we look in the row that starts with "C" and then look for "S" as the column on the very top row . We hit "U" as the intersection.

PLAINTEXT: S E L L E R

KEY: C A T C A T

ENCRYPTED: U E E N E K

We can see in the above case that the plain text had 2 L's but they got translated to different characters "E" and "N" because the keys were "T" and "C" making an attack more difficult.

What is the plain text given the following:

KEY: C A T C A T

ENCRYPTED: R U S B L X

We can see another helpful aid to aid in the translation for one single shift and that is the cipher disk.

Engima

Now let us study a different kind of polyalphabetic cipher in play called the "The Engima" . This machine has been dramatized in the movie "The Imitation Game" .

Trailer for the movie:

https://www.youtube.com/watch?v=nuPZUUED5uk

The machine is portable and needs a battery to work with. The design itself is not very complicated. There are different configurations of the machine, It works

with a rotar that has 26 grooves on it representing the letters and has 26 contact points on each side . Inside the rotor there is wiring connecting the 26 points.

The Enigma is an electromechanical device. The device looks like a typewriter. When we press the character "A" a circuit gets formed and the letter "B" may get lighted up depending on the circuit. But now the right most rotor also moves one notch clock wise.This creates a brand new circuit and now if we press "A" then some other letter might light up. Once the rightmost rotor rotates 26 times then the left ( middle ) rotor moves one notch. Once the middle rotor moves 26 times then the leftmost rotor will move one notch. Each time a brand new circuit will be created. To add complexity a plug-in board was also added and that will let a user add cables to certain points.

To make it more difficult 5 rotors were used and 3 of them could be selected and then again we could place these 3 rotors in 6 different ways. The different setting was a staggering

huge number.

158,962,555,217,826,360,000

There are 3 rotors and they can be set initially . So instead of "A" , "A", "A" we can have an initial setting of "C", "A". "B" . This serves as the symmetric key. The user1 will start the encryption process and note down the characters that light up another panel. The user2 will also rotate the rotors to the initial symmetric key. Now the electrical configuration is the same as when user1 started with. Remember when we pressed say "A" the letter "B" lighted up. That formed a loop. So now if our circuit is the same and we press "B" then letter "A" will light up. This is how the message gets decrypted.

With the advent of computers it became easier to do symmetric encryption . The alphabet became a sequence of 1's and 0's but now we can write a program to do the

encryption and decryption. DES ( Data Encryption Standard) was an early algorithm and is no longer used but is useful to study in terms of technique and algorithm.

DES

http://page.math.tu-berlin.de/~kant/teaching/hess/krypto-ws2006/des.htm

Asymmetric Encryption

With the advent of the web a new problem arose we have the client ( browser ) and the server; 2 different machines separated by many routers and information

travelling on the network. If we try to pass the symmetric key then it can be intercepted and the messages decrypted. This is where the concept of asymmetric encryption comes in. We have 2 keys called key1 and key2. A message that is encrypted with "key1" can only be decrypted with "key2". Even "key1" cannot decrypt it. Similarly a message that is encrypted with "key2" can only be decrypted with "key1

".

RSA Algorithm

This algorithm was created by 3 people Rivest , Shamir, Adleman and is named after them. It is one of the schemes that implements Asymmetric Encryption.

Some definitions.

Coprime: A number is coprime to another number if no other number other than 1 can be a divisor to both the numbers. The number does not have to be prime.

Ex:

4 and 7

4 is copriome to 7 because no number goes into 4 and 7 except 1.

7 and 13 . 7 is co prime to 13 .

if a number x1 is prime then if we find a number x2 that does not divide into x1 then the 2 numbers are co-prime to each other.

Totient of 2 numbers p and q is ( p-1 ) * ( q-1 ) .

If the 2 numbers are 11 and 3 then the totient is ( 11 - 1 ) * ( 3 -1 ) = 20

Modulus Inverse: Assume the divisor is n and the number is a . The modulus inverse is the number x1 * a modulus n . equals 1 .

Say we have 2 numbers 7 and 20 .

We have 3 as an inverse because . 3 * 7 modulus 20 = 1

We can have more than one inverse. Actually we can alway find more inverses using the following:

( 3 * 7 ) . + ( 20 * x1 * 7 )

--------------------------------------

20

Where x1 can be 0 or a greater number.

Example:

1) Choose 2 prime numbers p = 11 and q = 3 . Multiply them to get n = 33

2) Compute the totient which is ( p-1 ) * ( n-1 ) = 10 * 2 = 20

3) Choose e > 1 a co-prime to 20

We choose e as 7 . We only need to choose e as a prime number that does not go into 20 .

4) Choose d such that

d * e . mod 20 = 1

We choose d as 3 since 3 * 7 mod 20 = 1

Public Key is:

n = 33

e = 7

Private Key

n = 33

d = 3

Let's encrypt the number 5 with the public key.

5 power 7 mod 33 = 14

Let's decrypt this value 14 with the private key.

14 power 3 mod 33 = 5

Exercise

Using

Public Key is:

n = 33

e = 7

Private Key

n = 33

d = 3

Encrypt the number 13 using the private key and decrypt using the public key.

Hashing

A hash algorithm in cryptography works on a message ( message can be data of any length ) to produce a fixed size value. It is a one-way function and are the workhorses of encryption. They are used in anything involving digital signatures or certificates .

It should have

the following properties.

1) If it runs on the same message again it should produce the same result.

2) It should not take a long time to run.

3) We should not be able to create a message given the hash ,

4) We should not be able to create 2 messages that produce the same hash.

5) A change to the message should produce a significant change in the hash.

Interesting thing about the hash function is that the algorithm will be known to everyone and there is no key that is involved. Let us create

our own simple hashing algorithm .

If our message has characters then we use a variable storage where we will add the ascii character value and then do a modulo 15 on it.

Example : " C A T"

These translate to the following ascii numbers.

"67 65 84"

Initially "storage" has the value 0 .

storage = 0 + 67 modulus 15

= 7

storage = 7 + 65 modulus 15 =

= 72 modulus 15 =

= 12

storage = 12 + 84 modulus 15

= 96 modulus 15

= 6

We know it satisfies 1 ) . It will produce the same value of we run the hash algorithm on the same message. But 4) is not true.

What happens if we increase one value then the modulus will carry over and then decrease the next character and the end modulus will

decrease by 1 .

So instead of "C A T"

we use "C B S"

storage = 0 + 67 modulus 15

= 7

storage = 7 + 66 modulus 15

= 73 modulus 15

= 13

storage = 13 + 83 modulus 15

= 96 modulus 15

= 6

This hashing function is not going to cut it. One problem is that the hash is very small . It is less than 15 and only needs 4 bits. The other problem is

the algorithm is too simple. We can easily guess how to break it.

MD4 was one of the early algorithms. It is deprecated and not secure but useful to study. It also provided the basis for other algorithms such as MD5, SHA-1 .

The hash is 128 bits. We start out with 4 integer variables initialized with specific values. The message is broken into 512 bits and operations are done with the

4 integer variables and these 512 bits. This block will change the value of the 4 integer variables. Then we fetch another block and this will change the values of

the 4 integer variables also.

MD4 is still used in password checking on the Windows systems . An actual password does not have to be fetched from the server but only the hash. A hash is computed

from the password that the user enters and the 2 hashes are compared. Hashing passwords can also be used when storing passwords somewhere. Let's say you

are storing the passwords in a database and checking the password against that. What if someone gains access to the database and sees the passwords.

Why not store the hash instead of the actual password. If a user loses their password we can ask them to reset it but we never see the actual password.

https://en.wikipedia.org/wiki/MD4

Digital Signatures

Let's say we have a document containing the following text:

"I appoint Mr. Clarence Darrow as my attorney."

A user User1 signs it . Couple of things we can state with certainty:

1) User1 did sign it and can't deny it.

2) The original document has not been modified in any way.

Now user1 can always say : "Hey someone really good forged my signature on this document" .

So now we have a third party called a Notary who will check the user1's id and have the user1 sign in the presence of the notary and the notary will compare the signature with the one on id and stamp the document.

For digital signatures we will take the hash of the text document and get a hash out of it. User1 will have a public and a private key. We will then encrypt the hash with the private key and in addition to the text document attach the encrypted hash and the public key.

Now the receiver user2 will take the text and get its hash say hash1. User2 will then use the user1's public key to decrypt the encrypted hash and compare the 2 values and if they are equal then we can conclude that user1 did sign the document. Now user1 says that look this document is not the same as the document that was given to him. Well then we say we decrypted the hash and the hash is the same hash as this document. If someone had changed the document we would have gotten different hash. That is how hash algorithms work. We cannot change something and get the same hash. And since someone else doesn't have your private key only you could have encrypted the hash . Now user1 says ok what if some other user3 had a private and public key and

encrypted the text with their private key and replaced my public key with his public key. Now we are stuck. What if user1 is telling the truth. Remember the notary with manually signing. Well in this case also we have to use a third party and this is where the CA ( Certificate Authority ) comes in. We ask the user1 to register his public key with the third party so that he cannot deny the owner of the public key.

Certificates

A certificate is a document that contains information such as description of the entity , address, public key and other information. It is digitally signed but signed by a CA .

The receiver is sure that the certificate is valid and the public key belongs to the person stated in the certificate.

The operating system keeps a list of root certificates to make sure the CA certificate that is used to sign a particular certificate is valid.

SSL ( Secure Sockets Layer )

Client Server

Client requests a certificate -->

<-- Server sends a certificate

Client authenticates the certificate

Client gets the public key and encrypts

a symmetric key and sends it to server -->

Server decrypts the symmetric key with it's

private key.

Client and Server now switch to symmetric encryption

Use case of using public, private keys for log in.

https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/ec2-key-pairs.html

https://www.ssh.com/ssh/public-key-authentication#setting-up-public-key-authentication-for-ssh