955363782ce90bfbc2e6ca31b335d780c1013aea
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.
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.
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.
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
19 from szyfrow
.support
.utilities
import *
20 from szyfrow
.support
.language_models
import *
22 modular_division_table
= {
23 (multiplier
, (multiplier
* plaintext
) % 26): plaintext
24 for plaintext
in range(26)
25 for multiplier
in range(26)
29 def affine_encipher_letter(accented_letter
, multiplier
=1, adder
=0, one_based
=True):
30 """Encipher a letter, given a multiplier and adder.
32 Accented version of latin letters (such as é and ö) are converted to their
33 non-accented versions before encryption.
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'
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()
51 return unpos(cipher_number
)
55 def affine_decipher_letter(letter
, multiplier
=1, adder
=0, one_based
=True):
56 """Encipher a letter, given a multiplier and adder
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'
65 if letter
in string
.ascii_letters
:
66 cipher_number
= pos(letter
)
67 if one_based
: cipher_number
+= 1
69 modular_division_table
[multiplier
, (cipher_number
- adder
) % 26]
71 if one_based
: plaintext_number
-= 1
72 if letter
in string
.ascii_uppercase
:
73 return unpos(plaintext_number
).upper()
75 return unpos(plaintext_number
)
79 def affine_encipher(message
, multiplier
=1, adder
=0, one_based
=True):
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'
86 enciphered
= [affine_encipher_letter(l
, multiplier
, adder
, one_based
)
88 return cat(enciphered
)
90 def affine_decipher(message
, multiplier
=1, adder
=0, one_based
=True):
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'
97 enciphered
= [affine_decipher_letter(l
, multiplier
, adder
, one_based
)
99 return cat(enciphered
)
103 def affine_break(message
, fitness
=Pletters
):
104 """Breaks an affine cipher using frequency analysis.
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.
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...)
118 sanitised_message
= sanitise(message
)
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
)
131 best_multiplier
= multiplier
133 best_one_based
= one_based
135 return (best_multiplier
, best_adder
, best_one_based
), best_fit