szyfrow/affine.py

   1 """Enciphering and deciphering using the [affine cipher](https://en.wikipedia.org/wiki/Affine_cipher).
   2 Also attempts to break messages that use an affine cipher.
   3
   4 The affine cipher operates one letter at a time. It converts each letter to a
   5 number, then enciphers that number using a multiplier and a number. The result
   6 is taken mod 26 and converted back into a letter.
   7
   8 For a multiplier _m_ and adder _a_, a letter converted to number _x_ is
   9 enciphered as _E(x)_ = (_m_ _x_ + _a_) mod 26. Deciphering uses the modular
  10 inverse of _m_, _m_⁻¹, so that _D(x)_ = _m_⁻¹ (_x_ - _a_) mod 26.
  11
  12 If `one_based` is `True`, the conversion between letters and numbers maps
  13 'a' → 1, 'b' → 2, … 'z'→ 26 and the `mod` function is adjusted to keep
  14 numbers in this range during enciphering and deciphering. If `one_based` is
  15 `False`, the conversion maps 'a' → 0, 'b' → 1, … 'z'→ 25 and `mod` behaves
  16 normally.
  17 """
  18
  19 from szyfrow.support.utilities import *
  20 from szyfrow.support.language_models import *
  21
  22 modular_division_table = {
  23     (multiplier, (multiplier * plaintext) % 26): plaintext
  24     for plaintext in range(26)
  25     for multiplier in range(26)
  26     }
  27
  28
  29 def affine_encipher_letter(accented_letter, multiplier=1, adder=0, one_based=True):
  30     """Encipher a letter, given a multiplier and adder.
  31
  32     Accented version of latin letters (such as é and ö) are converted to their
  33     non-accented versions before encryption.
  34
  35     >>> cat(affine_encipher_letter(l, 3, 5, True) \
  36             for l in string.ascii_letters)
  37     'hknqtwzcfiloruxadgjmpsvybeHKNQTWZCFILORUXADGJMPSVYBE'
  38     >>> cat(affine_encipher_letter(l, 3, 5, False) \
  39             for l in string.ascii_letters)
  40     'filoruxadgjmpsvybehknqtwzcFILORUXADGJMPSVYBEHKNQTWZC'
  41     """
  42     letter = unaccent(accented_letter)
  43     if letter in string.ascii_letters:
  44         letter_number = pos(letter)
  45         if one_based: letter_number += 1
  46         cipher_number = (letter_number * multiplier + adder) % 26
  47         if one_based: cipher_number -= 1
  48         if letter in string.ascii_uppercase:
  49             return unpos(cipher_number).upper()
  50         else:
  51             return unpos(cipher_number)
  52     else:
  53         return letter
  54
  55 def affine_decipher_letter(letter, multiplier=1, adder=0, one_based=True):
  56     """Encipher a letter, given a multiplier and adder
  57
  58     >>> cat(affine_decipher_letter(l, 3, 5, True) \
  59             for l in 'hknqtwzcfiloruxadgjmpsvybeHKNQTWZCFILORUXADGJMPSVYBE')
  60     'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
  61     >>> cat(affine_decipher_letter(l, 3, 5, False) \
  62             for l in 'filoruxadgjmpsvybehknqtwzcFILORUXADGJMPSVYBEHKNQTWZC')
  63     'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
  64     """
  65     if letter in string.ascii_letters:
  66         cipher_number = pos(letter)
  67         if one_based: cipher_number += 1
  68         plaintext_number = (
  69             modular_division_table[multiplier, (cipher_number - adder) % 26]
  70             )
  71         if one_based: plaintext_number -= 1
  72         if letter in string.ascii_uppercase:
  73             return unpos(plaintext_number).upper()
  74         else:
  75             return unpos(plaintext_number)
  76     else:
  77         return letter
  78
  79 def affine_encipher(message, multiplier=1, adder=0, one_based=True):
  80     """Encipher a message
  81
  82     >>> affine_encipher('hours passed during which jerico tried every ' \
  83            'trick he could think of', 15, 22, True)
  84     'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
  85     """
  86     enciphered = [affine_encipher_letter(l, multiplier, adder, one_based)
  87                   for l in message]
  88     return cat(enciphered)
  89
  90 def affine_decipher(message, multiplier=1, adder=0, one_based=True):
  91     """Decipher a message
  92
  93     >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg ' \
  94            'jfaoe ls omytd jlaxe mh', 15, 22, True)
  95     'hours passed during which jerico tried every trick he could think of'
  96     """
  97     enciphered = [affine_decipher_letter(l, multiplier, adder, one_based)
  98                   for l in message]
  99     return cat(enciphered)
 100
 101
 102
 103 def affine_break(message, fitness=Pletters):
 104     """Breaks an affine cipher using frequency analysis.
 105
 106     It tries all possible combinations of multiplier, adder, and one_based,
 107     scores the fitness of the text decipherd with each combination, and returns
 108     the key that produces the most fit deciphered text.
 109
 110     >>> affine_break('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls ' \
 111           'omytd jlaxe mh jm bfmibj umis hfsul axubafkjamx. ls kffkxwsd jls ' \
 112           'ofgbjmwfkiu olfmxmtmwaokttg jlsx ls kffkxwsd jlsi zg tsxwjl. jlsx ' \
 113           'ls umfjsd jlsi zg hfsqysxog. ls dmmdtsd mx jls bats mh bkbsf. ls ' \
 114           'bfmctsd kfmyxd jls lyj, mztanamyu xmc jm clm cku tmmeaxw kj lai ' \
 115           'kxd clm ckuxj.') # doctest: +ELLIPSIS
 116     ((15, 22, True), -340.601181913...)
 117     """
 118     sanitised_message = sanitise(message)
 119     best_multiplier = 0
 120     best_adder = 0
 121     best_one_based = True
 122     best_fit = float("-inf")
 123     for one_based in [True, False]:
 124         for multiplier in [x for x in range(1, 26, 2) if x != 13]:
 125             for adder in range(26):
 126                 plaintext = affine_decipher(sanitised_message,
 127                                             multiplier, adder, one_based)
 128                 fit = fitness(plaintext)
 129                 if fit > best_fit:
 130                     best_fit = fit
 131                     best_multiplier = multiplier
 132                     best_adder = adder
 133                     best_one_based = one_based
 134
 135     return (best_multiplier, best_adder, best_one_based), best_fit