Saturday, September 21, 2013

Notes - Affine Ciphers

The following are notes from Introduction to Cryptography with Coding Theory.
  • This is a strengthened version of a shift cipher where x -> ax+B
    • example a = 9, B = 2
    • affine -> CVVWPM
  • Decryption involves reversing the cipher
    • y = 9 x + 2
    • In modular arithmetic we need to find the inverse differently than we would in algebra, more clearly described in Chapter 3
      • Since we are using the alphabet, we need to work with mod 26
      • therefore we need to find gcd(9,26) = 1
      • What we can do is use the extended euclidean algorithm to solve for a multiplier to 9 that would result 1 mod 26 aka
        • 9 x ≡ 1 (mod 26)
        • we can also see that multiplying 9 by 3 will also result in a remainder of 1 which satisfies this congruence
      • Therefore 3 is the desired inverse
    • x ≡ 3(y-2) ≡ 3y -6 ≡ 3y +20 (mod 26)
    • Example
      • map the letter V
      • V = 21
      • 3*21 +20
      • 81
      • 81 ≡ 5 mod(26)
      • the letter f
    • This decryption will allow us to return the plaintext of affine from CVVWPM
    • We must be able to find the inverse in modular arithmetic in order to have a usable key so arbitrary keys may result in multiple returns for a singular input
  • Possible Attacks
    • Ciphertext only
      • 312 keys only means its easy for a computer to break, however difficult by hand
    • Known Plaintext
      • knowing even some of the plaintext reduces the possibilities and can potentially result in breaking the code even without a computer
    • Chosen Plaintext
      •  if ab is chosen as plaintext we can immediately break the code
    • Chosen Ciphertext
      • again if AB is chosen as ciphertext we find the encryption key but we already have the decryption key in this case so no additional work is needed

No comments:

Post a Comment