# These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else

 Page 16/24 Date 03.05.2017 Size 186.06 Kb. #18863

## Greatest Common Divisor

• GCD(A, B)
• Largest integer that evenly divides A and B
• i.e. there is no remainder from the division
• Simple, brute-force approach?
• Start with min(A,B) since that is the largest possible answer
• If that doesn't work, decrement by one until the GCD is found
• Easy to code using a simple for loop
• Run-time?
• We want to count how many mods we need to do
• Theta(min(A, B)) – is this good?

## GCD

• Remember exponentiation?
• A and B are N bits, and the loop is linear in the VALUE of min(A,B)
• This is exponential in N, the number of bits!
• How can we improve?
• Famous algorithm by Euclid
• GCD(A,B) = GCD(B, A mod B)
• Ok let's try it
• GCD(30,24) = GCD(24,6) = GCD(6,0) = ?????
• What is missing?
• The base case: GCD(A,B) = A when B = 0
• Now GCD(6,0) = 6 and we are done

## GCD

• Run-time of Euclid's GCD?
• Let's again count number of mods
• Tricky to analyze exactly, but in the worst case it has been shown to be linear in N, the number of bits
• Similar improvement to exponentiation problem
• Also can be easily implemented iteratively
• See handout gcd.txt
• Extended GCD
• It is true that GCD(A,B) = D = AS + BT for some integer coefficients S and T
• Ex: GCD(30,24) = 6 = (30)(1) + (24)(-1)
• Ex: GCD(99,78) = 3 = (99)(-11) + (78)(14)

## Arithmetic Summary

• With a bit of extra logic (same Theta run-time), GCD can also provide the coefficients S and T
• This is called the Extended Greatest Common Divisor algorithm
• Arithmetic summary
• We have looked at multiplication, exponentiation, and GCD (XGCD)
• These will all be necessary when we look at public key encryption next

## Cryptography Motivation and Definitions

• What is Cryptography?
• Designing of secret communications systems
• A SENDER wants a RECEIVER (and no one else) to understand a PLAINTEXT message
• Sender ENCRYPTS the message using an encryption algorithm and some key parameters, producing CIPHERTEXT
• Receiver has decryption algorithm and key parameters, and can restore original plaintext
• PLAINTEXT
• PLAINTEXT
• Sender
• CIPHERTEXT
• algorithm
• key params
• algorithm
• key params

## Cryptography Motivation and Definitions

• Why so much trouble?
• CRYPTANALYST would like to read the message
• Tends to be very clever
• Can usually get a copy of the ciphertext
• Usually knows (or can figure out) the encryption algorithm
• So the key parameters (and how they affect decryption) are really the only thing preventing the cryptanalyst from decrypting
• And he/she hopes to decrypt your message without them (or possibly figure them out in some way)

## Some Encryption Background

• ABCDEFGHIJKLMNO...
• ABCDEFGHIJKLMNOPQR...
• <- original alphabet
• <- letters used in code
• shift = 3
• KHOOR
• <- ciphertext

## Some Encryption Background

• Almost trivial to break today
• Try each shift until right one is found
• Only 25 possible shifts for letters, 255 for ASCII
• Try arbitrary substitution instead: Substitution Cipher
• Code alphabet is an arbitrary permutation of original alphabet
• Much more difficult to break by "guessing"
• With alphabet of S characters, S! permutations

## Some Encryption Background

• But still relatively easy to break today in other ways
• Frequency tables, sentence structure
• Play "Wheel of Fortune" with the ciphertext
• Once we guess some letters, others become easier
• Not a trivial program to write, by any means
• But run-time is not that long – that is the important issue
• Hey Pat, can I buy
• a vowel?
• These "before and after"s
• always give me trouble

## Some Encryption Background

• ALGORITHMS ARE COOL
• ABCDABCDABCDABCDABC
• -------------------
• BNJSSKWLNUCESGCDPQO
• <- original message
• <- key sequence
• <- ciphertext

## Some Encryption Background

• Vigenere Cipher
• Now the same ciphertext character may represent more than one plaintext character
• The longer the key sequence, the better the code
• If the key sequence is as long as the message, we call it a Vernam Cipher
• This is effective because it makes the ciphertext appear to be a "random" sequence of characters

## Some Encryption Background

• Vernam Cipher is provably secure for one-time use (as long as key is not discovered)
• Since a "random" character is added to each character of the message, the ciphertext appears to be completely random to the cryptanalyst
• However, with repeated use its security diminishes somewhat
• Used in military applications when absolute security is required
• See
• http://www.pro-technix.com/information/crypto/pages/vernam_base.html