- 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
- 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 ## 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 - Early encryption schemes were quite simple
** ABCDEFGHIJKLMNO...** **ABCDEFGHIJKLMNOPQR...** - <- original alphabet
- <- letters used in code
- shift = 3
## 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 - Better if "structure" of ciphertext differs from that of plaintext
**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
**Share with your friends:** |