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



Download 186.06 Kb.
Page16/24
Date03.05.2017
Size186.06 Kb.
#18863
1   ...   12   13   14   15   16   17   18   19   ...   24

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
  • Receiver
  • 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

Download 186.06 Kb.

Share with your friends:
1   ...   12   13   14   15   16   17   18   19   ...   24




The database is protected by copyright ©sckool.org 2022
send message

    Main page