cryptographyPresenta tion

Coding and Cryptography: 

Coding and Cryptography By: Joe, Wendy, and Mindy

What is Cryptography?: 

What is Cryptography? Cryptography is the science of information security. It can also be defined as “the means and methods for hiding information and preventing its modification”.

Important Terms: 

Important Terms Encryption- to put into code. Ciphers- is any method of concealing the meaning of text using substitution and transposition. Plaintext- readable text before it’s transposed or (encrypted). Ciphertext- encrypted text.

Important Terms (continued): 

Important Terms (continued) Decryption- taking encrypted text (ciphertext) and changing it back to it’s original readable text (plaintext). Key- a variable applied to a block or string of unencrypted text (plaintext) to an encrypted text (ciphertext) or vise versa.

How it Works: 

How it Works Encryption: A cipher takes the plaintext and applies a transformation function using a key. This produces the ciphertext. This is then sent to the receiver. Decryption: The receiver then applies another transformation to the ciphertext using a different key to unlock the plaintext.

What’s the secret?: 

What’s the secret? Good ciphers rely on the key being unknown and secure even if the algorithm is known. This makes it easy to use cryptography in every day life because it relies on a standard set of ciphers and can be used to ensure communication between all parties.

What is cryptography used for?: 

What is cryptography used for? Confidentiality- guarantees message can be read only by the people intended to read it Integrity- guarantees message can’t be altered Authenticity- guarantees message came from the person who the receiver thought it came from.

Cryptography in History: The Enigma Machine: 

Cryptography in History: The Enigma Machine The Enigma Machine was invented by Arthur Scherbius in 1918 It was used by the Germans during WWII Its purpose was to disguise military messages that could be intercepted by an enemy

The Enigma enciphers a message by performing a number of substitutions one after the other via electrical connections: 

The Enigma enciphers a message by performing a number of substitutions one after the other via electrical connections The first substitution: If an electrical voltage is applied to the letter ‘Q’, the lamp ‘M’ on the bottom row will light. ‘M’ is now the substitution letter for ‘Q’.

The second Substitution:: 

The second Substitution: Known as the Caesar shift, the second set of wirings is displaced by two letters. So, our original ‘Q’ which was substituted by ‘M’ is now displaced by two, making it a ‘K’. The ‘K’ is then wired to trigger the ‘J’, which is also displaced by two, turning it into an ‘L’.

The building of the machine: 

The building of the machine The wiring embodying the substitutions was set in a wheel Then the shifts were achieved by the rotation(s) of one wheel against the other Next, a third wheel was added, which used different displacements

Slide12: 

The Enigma Machine

Slide13: 

The output from the third wheel is then fed into a fixed reflector plate (i.e. a swapping of letters). This output is passed back through the rotors in reverse direction. A total of seven substitutions are performed within the Enigma.

Slide14: 

This allows for 17,576 different substitutions… Can it be cracked??

The Germans made two BAD mistakes:: 

The Germans made two BAD mistakes: 1. The Enigma did not need to be switched from encipher mode to decipher mode due to the reflector. Thus, if ‘A’ is enciphered to ‘Q’, then ‘Q’ will be enciphered to ‘A’ in the same configuration. 2. The message was required to be typed twice in succession

Another HUGE mistake:: 

Another HUGE mistake: A German typed a 4000 letter message, but the operator at the other end didn’t get it. Both set their machines back to the same starting position (forbidden). The German typed the message again, which had different substitutions. He was too lazy to type its succession message, so he simplified it. August 30, 1941

The message is deciphered!!: 

The message is deciphered!! John Tiltman deciphered the code He knew the first and second messages were the same because they were both entitled with the same message number With the slight variation in substitutions, he was able to determine the appropriate letters

Cracking the System: 

Cracking the System Bill Tutte (chemist) was given the enciphered and deciphered code He wrote down every pattern he could find He found repetition With help from a few others, Tutte figured out the entire structure of the Enigma machine This structure is AKA the Lorenz

The Result: 

The Result Many messages still took weeks to decipher The world’s first programmable electronic computer (Colossus) was designed by Max Newman It sped up this lengthy process Colossus proved to be a key contributor on D-Day This led to the end of WWII

Public Key Cryptography: 

Public Key Cryptography Let’s suppose Alice and Bob are trying to communicate without Eve being able to understand. In addition, lets assume the two following conditions Alice and Bob have never before spoken. Eve can hear every message transmitted.

Six General Steps to Public Key Cryptography: 

Six General Steps to Public Key Cryptography Public Steps: Steps that we must assume that anyone interested, including Eve, can hear. Private Steps: Steps that exactly one person knows.

Slide22: 

Step One (Public): Alice gets Bob’s attention. Alice sends Bob a message in plaintext such as “We need to talk.” Remember, Eve can also hear this and so her ears perk up as well.

Slide23: 

Step Two (Private): Bob goes to work. Chooses two prime numbers, p=3 and q=5. Evaluates n=pq=15. Finds ø(n) = (p-1)(q-1)=8. Ø(n) can also be calculated using the prime factorization of the number, n. (Euler’s Theorem) Chooses a number, k=7, relatively prime to n.

Relatively Prime Numbers: 

Relatively Prime Numbers Two numbers m and n are relatively prime if: gcd(m,n) = 1 the prime factorizations of m and n have no primes in common. lcm(m,n) = mn you can express 1 as a linear combination of m and n. If you can express 1 as a combination of m and n, then you can express 1 as a combination of ma and nb, where m, n, a, and b are real numbers

Slide25: 

Step Three (Public): Bob tells Alice (and anyone else who may be listening) the values of n and k. Alice has all she needs to encrypt the message. Step Four (Private): Alice takes each number, ay…az, that comprises her message (say the ANSI values for the letters of the message) and raises it to the kth power in arithmetic modulus n to arrive at a new number, by…bz. The numbers by…bz are the encoded message.

Modular Arithmetic: 

Modular Arithmetic In arithmetic (mod n) the counting number starts over at n. Example: The first letter of the message is “D” whose ANSI value is 68. If k=7 and we are using modulus 15, then 687(mod15) = ?

687(mod15) = ?: 

687(mod15) = ? 68 = 8 (mod15) 682 = 82 (mod15) = 4 (mod15) 684=(82)2(mod15)=42(mod15)=1 (mod15) 687 = 684 x 682 x 68 = 1 x 4 x 8 (mod15) = 32 (mod15) = 2 (mod15)

Slide28: 

Step Five (Public): Alice sends Bob (and everyone else) the encrypted message. Step Six (Private): Bob takes the numbers, by…bz and, using his knowledge of ø(n), finds the kth root of b in arithmetic modulus n. The resulting numbers, ay…az, comprise the original message that Alice wanted to send. Key: Only Bob knows what ø(n) is. Therefore, only he can decrypt the sent message.

The All Important Ø(n).: 

The All Important Ø(n). To find the kth root of b in mod n, we find a number x such that xk=b (modn). In the previous example, we would need to find a seventh root of 2 in modulus 15. Find x such that x7 = 2(mod15)

x7 = 2(mod15): 

x7 = 2(mod15) Step 1: Find Ø(15) Bob chose this right away, but it can also be found from the prime factorization of 15. Ø(15) = 15(2/3)(4/5) = 8 Step 2: Is 2 relatively prime to 15? Is 7 relatively prime to 8?

x7 = 2(mod15): 

x7 = 2(mod15) Step 3: Find the reciprocal of 7 in modulus 8. “works by the virtue that the numerator, 7, is relatively prime to the modulus, 8” (Gross & Harris). Essentially, we need to find the quotient 1/7 (mod8).

1/7 (mod8) = ?: 

1/7 (mod8) = ? Solve 7x = 8y + 1 (Euclidean Algorithm) 8 = 1 x 7 + 1 1 = 8 – (1 x 7) *8=0 (mod8) 1 = -1 x 7 (mod8) 1/7 = -1 (mod8) = 7 (mod8) The reciprocal of 7 in arithmetic modulus 8 is 7!

We’re Almost There: 

We’re Almost There Step 4: Evaluate 27 (mod15) 2 = 2 (mod15) 22 = 4 (mod15) 24 = 42 (mod15) = 1 (mod15) 27 = 24 x 22 x 2 = 1 x 4 x 2 (mod15) = 8 (mod15)

Finally….: 

Finally…. We started this mess trying to solve: x7 = 2 (mod15) If 87 = 2 (mod15), we are done. 87/15 = 2,097,152/15 = 139810 R:2! 8 is precisely the number that Alice sent to Bob in the first place.

Why Do Public Key Cryptosystems Work?: 

Why Do Public Key Cryptosystems Work? There are infinitely many primes. A number can be expressed as the product of primes in one and only one way. (Fundamental Theorem of Arithmetic) The encryption/decryption codes can be readily changed with each message.

Why Do Public Key Cryptosystems Work?: 

Why Do Public Key Cryptosystems Work? We could crack a public key relatively easy if the key used small numbers. The code relies on using large numbers, say numbers of 100 digits. To find the prime factorization of a 100 digit number, n, we would have check divisibility by primes up to n1/2.

Why Do Public Key Cryptosystems Work?: 

Why Do Public Key Cryptosystems Work? Today’s fastest computers perform on the order of 1 trillion calculations per second. Let’s say that this computer can perform 1 trillion divisions each second (it takes many calculations to perform each division).

How Many Lifetimes?: 

How Many Lifetimes? 1 trillion = 1012 & our 100 digit number, n, is on the order of 1048. Factoring n could take 1048/1012=1036 seconds. 1036/86400~1031 days. 1031/365~3 x 1028 years. (3 x 1028) / 100~3 x 1026 centuries.

References:: 

References: www.wedgetail.com/technology/crypto.html www.codesandciphers.org.uk/enigma/enigma1.htm Gross, Benedict and Joe Harris. The Magic of Numbers. Pearson Education, Inc. 2004. Schneider, David I. An Introduction to Programming Using Visual Basic.NET. Pearson Education, Inc. 2003.