Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
sagemath
GitHub Repository: sagemath/sagelib
Path: blob/master/sage/crypto/classical_cipher.py
4045 views
1
"""
2
Classical Ciphers
3
"""
4
5
#*****************************************************************************
6
# Copyright (C) 2007 David Kohel <[email protected]>
7
#
8
# Distributed under the terms of the GNU General Public License (GPL)
9
#
10
# http://www.gnu.org/licenses/
11
#*****************************************************************************
12
13
from cipher import SymmetricKeyCipher
14
from sage.monoids.string_monoid_element import StringMonoidElement
15
from sage.modules.free_module import FreeModule
16
17
class AffineCipher(SymmetricKeyCipher):
18
r"""
19
Affine cipher class. This is the class that does the actual work of
20
encryption and decryption. Users should not directly instantiate or
21
create objects of this class. Instead, functionalities of this class
22
should be accessed via
23
:class:`AffineCryptosystem <sage.crypto.classical.AffineCryptosystem>`
24
as the latter provides a convenient user interface.
25
"""
26
27
def __init__(self, parent, key):
28
r"""
29
Create an affine cipher.
30
31
INPUT:
32
33
- ``parent`` -- an ``AffineCryptosystem`` object.
34
35
- ``key`` -- a secret key. Let `N` be the size of the cipher domain.
36
A key of this affine cipher is an ordered pair
37
`(a, b) \in \ZZ_N \times \ZZ_N` such that `\gcd(a, N) = 1`.
38
39
EXAMPLES:
40
41
Testing of dumping and loading object::
42
43
sage: A = AffineCryptosystem(AlphabeticStrings())
44
sage: AC = A(3, 5)
45
sage: AC == loads(dumps(AC))
46
True
47
"""
48
SymmetricKeyCipher.__init__(self, parent, key)
49
50
def __eq__(self, other):
51
r"""
52
Comparing this ``AffineCipher`` with ``other``. Two ``AffineCipher``
53
objects are the same if they are of the same type, have the same
54
parent, and share the same secret key.
55
56
INPUT:
57
58
- ``other`` -- another object to compare with.
59
60
OUTPUT:
61
62
- ``True`` if ``self`` and ``other`` are the same ``AffineCipher``
63
object; ``False`` otherwise.
64
65
EXAMPLES::
66
67
sage: aff1 = AffineCryptosystem(AlphabeticStrings())
68
sage: aff2 = AffineCryptosystem(AlphabeticStrings())
69
sage: aff1 == aff2
70
True
71
sage: aff1(1, 2) == aff2(1, 2)
72
True
73
"""
74
return type(self) == type(other) and self.parent() == other.parent() and self.key() == other.key()
75
76
def __call__(self, M):
77
r"""
78
Return the ciphertext (respectively, plaintext) corresponding to
79
``M``. This is the main place where encryption and decryption takes
80
place.
81
82
INPUT:
83
84
- ``M`` -- a message to be encrypted or decrypted. This message must
85
be encoded using the plaintext or ciphertext alphabet. The current
86
behaviour is that the plaintext and ciphertext alphabets are the
87
same alphabet.
88
89
- ``algorithm`` -- (default ``"encrypt"``) whether to use the
90
encryption or decryption algorithm on ``M``. The flag ``"encrypt"``
91
signifies using the encryption algorithm, while ``"decrypt"``
92
signifies using the decryption algorithm. The only acceptable
93
values for ``algorithm`` are: ``"encrypt"`` and ``"decrypt"``.
94
95
OUTPUT:
96
97
- The ciphertext or plaintext corresponding to ``M``.
98
99
EXAMPLES::
100
101
sage: A = AffineCryptosystem(AlphabeticStrings()); A
102
Affine cryptosystem on Free alphabetic string monoid on A-Z
103
sage: P = A.encoding("The affine cryptosystem generalizes the shift cipher.")
104
sage: P
105
THEAFFINECRYPTOSYSTEMGENERALIZESTHESHIFTCIPHER
106
sage: a, b = (9, 13)
107
sage: E = A(a, b); E
108
Affine cipher on Free alphabetic string monoid on A-Z
109
sage: C = E(P); C
110
CYXNGGHAXFKVSCJTVTCXRPXAXKNIHEXTCYXTYHGCFHSYXK
111
sage: aInv, bInv = A.inverse_key(a, b)
112
sage: D = A(aInv, bInv); D
113
Affine cipher on Free alphabetic string monoid on A-Z
114
sage: D(C)
115
THEAFFINECRYPTOSYSTEMGENERALIZESTHESHIFTCIPHER
116
sage: D(C) == P
117
True
118
sage: D(C) == P == D(E(P))
119
True
120
"""
121
# sanity check
122
D = self.domain() # = plaintext_space = ciphertext_space
123
if M.parent() != D:
124
raise TypeError("Argument M must be a string in the plaintext/ciphertext space.")
125
126
from sage.rings.finite_rings.integer_mod import Mod
127
A = list(D.alphabet()) # plaintext/ciphertext alphabet as a list
128
N = self.domain().ngens() # number of elements in this alphabet
129
a, b = self.key() # encryption/decryption key (a,b)
130
# Let I be the index list of M. That is, the i-th element of M has
131
# index k in the cipher domain D. We store this cipher domain index
132
# as the i-th element of I.
133
I = [A.index(str(e)) for e in M]
134
135
# Encrypt the plaintext M. For each element i in I, the ciphertext
136
# corresponding to i is ai + b (mod N). This can also be used for
137
# decryption, in which case (a, b) is the inverse key corresponding
138
# to a secret key.
139
return D([ A.index(A[Mod(a*i + b, N).lift()]) for i in I ])
140
141
def _repr_(self):
142
r"""
143
Return the string representation of this affine cipher.
144
145
EXAMPLES::
146
147
sage: A = AffineCryptosystem(AlphabeticStrings())
148
sage: A(1, 2)
149
Affine cipher on Free alphabetic string monoid on A-Z
150
"""
151
# The affine cipher has the plaintext and ciphertext spaces defined
152
# over the same non-empty alphabet. The cipher domain is the same
153
# as the alphabet used for the plaintext and ciphertext spaces.
154
return "Affine cipher on %s" % self.parent().cipher_domain()
155
156
class HillCipher(SymmetricKeyCipher):
157
"""
158
Hill cipher class
159
"""
160
def __init__(self, parent, key):
161
"""
162
Create a Hill cipher.
163
164
INPUT: Parent and key
165
166
EXAMPLES::
167
168
sage: S = AlphabeticStrings()
169
sage: E = HillCryptosystem(S,3)
170
sage: E
171
Hill cryptosystem on Free alphabetic string monoid on A-Z of block length 3
172
sage: M = E.key_space()
173
sage: A = M([[1,0,1],[0,1,1],[2,2,3]])
174
sage: A
175
[1 0 1]
176
[0 1 1]
177
[2 2 3]
178
sage: e = E(A); e
179
Hill cipher on Free alphabetic string monoid on A-Z of block length 3
180
sage: e(S("LAMAISONBLANCHE"))
181
JYVKSKQPELAYKPV
182
183
TESTS::
184
185
sage: S = AlphabeticStrings()
186
sage: E = HillCryptosystem(S,3)
187
sage: E == loads(dumps(E))
188
True
189
"""
190
# TODO: some type checking that the key is an invertible matrix?
191
SymmetricKeyCipher.__init__(self, parent, key)
192
193
def __eq__(self, right):
194
return type(self) == type(right) and self.parent() == right.parent() and self.key() == right.key()
195
196
def __call__(self, M):
197
S = self.domain() # = plaintext_space = ciphertext_space
198
if not isinstance(M, StringMonoidElement) and M.parent() == S:
199
raise TypeError, "Argument M (= %s) must be a string in the plaintext space." % M
200
m = self.parent().block_length()
201
if len(M) % m != 0:
202
raise TypeError, "The length of M (= %s) must be a multiple of %s." % (M, m )
203
Alph = list(S.alphabet())
204
A = self.key() # A is an m x m matrix
205
R = A.parent().base_ring()
206
V = FreeModule(R,m)
207
Mstr = str(M)
208
C = []
209
for i in range(len(M)//m):
210
v = V([ Alph.index(Mstr[m*i+j]) for j in range(m) ])
211
C += (v * A).list()
212
return S([ k.lift() for k in C ])
213
214
def _repr_(self):
215
r"""
216
Return the string representation of this Hill cipher.
217
218
EXAMPLES::
219
220
sage: H = HillCryptosystem(AlphabeticStrings(), 3)
221
sage: M = MatrixSpace(IntegerModRing(26), 3, 3)
222
sage: A = M([[1,0,1], [0,1,1], [2,2,3]])
223
sage: e = H(A); e
224
Hill cipher on Free alphabetic string monoid on A-Z of block length 3
225
"""
226
return "Hill cipher on %s of block length %s" % (
227
self.parent().cipher_domain(), self.parent().block_length() )
228
229
def inverse(self):
230
E = self.parent()
231
try:
232
B = E.inverse_key(self.key())
233
except:
234
raise ValueError, "Argument\n\n%s\n\nmust be an invertible cipher." % self
235
return E(B)
236
237
class ShiftCipher(SymmetricKeyCipher):
238
r"""
239
Shift cipher class. This is the class that does the actual work of
240
encryption and decryption. Users should not directly instantiate or
241
create objects of this class. Instead, functionalities of this class
242
should be accessed via
243
:class:`ShiftCryptosystem <sage.crypto.classical.ShiftCryptosystem>`
244
as the latter provides a convenient user interface.
245
"""
246
247
def __init__(self, parent, key):
248
r"""
249
Create a shift cipher.
250
251
INPUT:
252
253
- ``parent`` -- a ``ShiftCryptosystem`` object.
254
255
- ``key`` -- a secret key.
256
257
EXAMPLES::
258
259
sage: S = ShiftCryptosystem(AlphabeticStrings()); S
260
Shift cryptosystem on Free alphabetic string monoid on A-Z
261
sage: P = S.encoding("The shift cryptosystem generalizes the Caesar cipher.")
262
sage: P
263
THESHIFTCRYPTOSYSTEMGENERALIZESTHECAESARCIPHER
264
sage: K = 7
265
sage: C = S.enciphering(K, P); C
266
AOLZOPMAJYFWAVZFZALTNLULYHSPGLZAOLJHLZHYJPWOLY
267
sage: S.deciphering(K, C)
268
THESHIFTCRYPTOSYSTEMGENERALIZESTHECAESARCIPHER
269
sage: S.deciphering(K, C) == P
270
True
271
"""
272
SymmetricKeyCipher.__init__(self, parent, key)
273
274
def __eq__(self, other):
275
r"""
276
Comparing this ``ShiftCipher`` with ``other``. Two ``ShiftCipher``
277
objects are the same if they are of the same type, have the same
278
parent, and share the same secret key.
279
280
INPUT:
281
282
- ``other`` -- another object to compare with.
283
284
OUTPUT:
285
286
- ``True`` if ``self`` and ``other`` are the same ``ShiftCipher``
287
object; ``False`` otherwise.
288
289
EXAMPLES::
290
291
sage: shift1 = ShiftCryptosystem(AlphabeticStrings())
292
sage: shift2 = ShiftCryptosystem(AlphabeticStrings())
293
sage: shift1 == shift2
294
True
295
sage: shift1 = ShiftCryptosystem(HexadecimalStrings())
296
sage: shift2 = ShiftCryptosystem(BinaryStrings())
297
sage: shift1 == shift2
298
False
299
"""
300
return type(self) == type(other) and self.parent() == other.parent() and self.key() == other.key()
301
302
def __call__(self, M):
303
r"""
304
Return the ciphertext (respectively, plaintext) corresponding to
305
``M``. This is the main place where encryption and decryption takes
306
place.
307
308
INPUT:
309
310
- ``M`` -- a message to be encrypted or decrypted. This message must
311
be encoded using the plaintext or ciphertext alphabet. The current
312
behaviour is that the plaintext and ciphertext alphabets are the
313
same alphabet.
314
315
OUTPUT:
316
317
- The ciphertext or plaintext corresponding to ``M``.
318
319
EXAMPLES:
320
321
These are indirect doctests. Functionalities of this class are
322
usually invoked from
323
:class:`ShiftCryptosystem <sage.crypto.classical.ShiftCryptosystem>`.
324
325
::
326
327
sage: S = ShiftCryptosystem(AlphabeticStrings())
328
sage: S.enciphering(12, S.encoding("Stop shifting me."))
329
EFABETURFUZSYQ
330
sage: S = ShiftCryptosystem(HexadecimalStrings())
331
sage: S.enciphering(7, S.encoding("Shift me now."))
332
cadfd0ddeb97d4dc97d5d6ee95
333
sage: S = ShiftCryptosystem(BinaryStrings())
334
sage: S.enciphering(1, S.encoding("OK, enough shifting."))
335
1011000010110100110100111101111110011010100100011001000010001010100110001001011111011111100011001001011110010110100110011000101110010110100100011001100011010001
336
"""
337
dom = self.domain() # = plaintext_space = ciphertext_space
338
if not isinstance(M, StringMonoidElement) and M.parent() == dom:
339
raise TypeError("Argument M (= %s) must be a string in the plaintext/ciphertext space." % M)
340
from sage.rings.finite_rings.integer_mod import Mod
341
A = list(dom.alphabet()) # plaintext/ciphertext alphabet as a list
342
N = self.domain().ngens() # number of elements in this alphabet
343
K = self.key() # encryption/decryption key
344
# Here, M is a message encoded within the ciphertext/plaintext
345
# alphabet of this shift cryptosystem. The list A above is a list of
346
# all elements of this alphabet, each element being associated with
347
# an index 0 <= i < n, where n is the size of A. Now get the index
348
# of each character in the message M, storing all these indices
349
# in the index list I.
350
# TODO: the following two lines are coded with clarity and
351
# readability in mind. It is possible to remove the overhead of
352
# doing a list comprehension to get the index associated with each
353
# element of M. For example, the next two lines can be crammed into
354
# one list comprehension as follows:
355
# return dom([ A.index(A[Mod(A.index(str(i)) + K, N).lift()]) for i in M ])
356
# But it performs badly compared to the following two lines.
357
I = [A.index(str(e)) for e in M]
358
# Perform encryption/decryption on the whole message M, returning
359
# the result as a string encoded in the alphabet A.
360
return dom([ A.index(A[Mod(i + K, N).lift()]) for i in I ])
361
362
def _repr_(self):
363
r"""
364
Return the string representation of this shift cipher.
365
366
EXAMPLES::
367
368
sage: S = ShiftCryptosystem(AlphabeticStrings())
369
sage: S(3)
370
Shift cipher on Free alphabetic string monoid on A-Z
371
sage: S = ShiftCryptosystem(HexadecimalStrings())
372
sage: S(5)
373
Shift cipher on Free hexadecimal string monoid
374
sage: S = ShiftCryptosystem(BinaryStrings())
375
sage: S(1)
376
Shift cipher on Free binary string monoid
377
"""
378
# The shift cipher has the plaintext and ciphertext spaces defined
379
# over the same non-empty alphabet. The cipher domain is the same
380
# as the alphabet used for the plaintext and ciphertext spaces.
381
return "Shift cipher on %s" % self.parent().cipher_domain()
382
383
class SubstitutionCipher(SymmetricKeyCipher):
384
"""
385
Substitution cipher class
386
"""
387
def __init__(self, parent, key):
388
"""
389
Create a substitution cipher.
390
391
INPUT: Parent and key
392
393
EXAMPLES::
394
395
sage: S = AlphabeticStrings()
396
sage: E = SubstitutionCryptosystem(S)
397
sage: E
398
Substitution cryptosystem on Free alphabetic string monoid on A-Z
399
sage: K = S([ 25-i for i in range(26) ])
400
sage: K
401
ZYXWVUTSRQPONMLKJIHGFEDCBA
402
sage: e = E(K)
403
sage: m = S("THECATINTHEHAT")
404
sage: e(m)
405
GSVXZGRMGSVSZG
406
407
TESTS::
408
409
sage: S = AlphabeticStrings()
410
sage: E = SubstitutionCryptosystem(S)
411
sage: E == loads(dumps(E))
412
True
413
"""
414
SymmetricKeyCipher.__init__(self, parent, key)
415
416
def __eq__(self, right):
417
return type(self) == type(right) and self.parent() == right.parent() and self.key() == right.key()
418
419
def __call__(self, M):
420
S = self.domain() # = plaintext_space = ciphertext_space
421
if not isinstance(M, StringMonoidElement) and M.parent() == S:
422
raise TypeError, "Argument M (= %s) must be a string in the plaintext space." % M
423
A = list(S.alphabet())
424
K = str(self.key()) # K is a string, while we want the indices:
425
I = [ A.index(K[i]) for i in range(len(K)) ]
426
Mstr = str(M)
427
return S([ I[A.index(Mstr[i])] for i in range(len(Mstr)) ])
428
429
def _repr_(self):
430
r"""
431
Return the string representation of this substitution cipher.
432
433
EXAMPLES::
434
435
sage: A = HexadecimalStrings(); S = SubstitutionCryptosystem(A)
436
sage: K = A([16-i for i in xrange(16)]); S(K)
437
Substitution cipher on Free hexadecimal string monoid
438
sage: A = AlphabeticStrings(); S = SubstitutionCryptosystem(A)
439
sage: K = A([26-i for i in xrange(26)]); S(K)
440
Substitution cipher on Free alphabetic string monoid on A-Z
441
sage: A = OctalStrings(); S = SubstitutionCryptosystem(A)
442
sage: K = A([8-i for i in xrange(8)]); S(K)
443
Substitution cipher on Free octal string monoid
444
sage: A = BinaryStrings(); S = SubstitutionCryptosystem(A)
445
sage: K = A([2-i for i in xrange(2)]); S(K)
446
Substitution cipher on Free binary string monoid
447
sage: A = Radix64Strings(); S = SubstitutionCryptosystem(A)
448
sage: K = A([64-i for i in xrange(64)]); S(K)
449
Substitution cipher on Free radix 64 string monoid
450
"""
451
return "Substitution cipher on %s" % self.parent().cipher_domain()
452
453
def inverse(self):
454
E = self.parent()
455
K = E.inverse_key(self.key())
456
return E(K)
457
458
class TranspositionCipher(SymmetricKeyCipher):
459
"""
460
Transition cipher class
461
"""
462
def __init__(self, parent, key):
463
"""
464
Create a transposition cipher.
465
466
INPUT: Parent and key
467
468
EXAMPLES::
469
470
sage: S = AlphabeticStrings()
471
sage: E = TranspositionCryptosystem(S,14)
472
sage: E
473
Transposition cryptosystem on Free alphabetic string monoid on A-Z of block length 14
474
sage: K = [ 14-i for i in range(14) ]
475
sage: K
476
[14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
477
sage: e = E(K)
478
sage: m = S("THECATINTHEHAT")
479
sage: e(m)
480
TAHEHTNITACEHT
481
482
EXAMPLES::
483
484
sage: S = AlphabeticStrings()
485
sage: E = TranspositionCryptosystem(S,15);
486
sage: m = S("THECATANDTHEHAT")
487
sage: G = E.key_space()
488
sage: G
489
Symmetric group of order 15! as a permutation group
490
sage: g = G([ 3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13 ])
491
sage: e = E(g)
492
sage: e(m)
493
EHTTACDNAEHTTAH
494
495
TESTS::
496
497
sage: S = AlphabeticStrings()
498
sage: E = TranspositionCryptosystem(S,14)
499
sage: E == loads(dumps(E))
500
True
501
"""
502
n = parent.block_length()
503
if isinstance(key, list) and not len(key) == n:
504
raise ValueError, "key (= %s) must have block length %s" % (key, n)
505
SymmetricKeyCipher.__init__(self, parent, key)
506
507
def __call__(self, M, mode = "ECB"):
508
S = self.domain() # = plaintext_space = ciphertext_space
509
if not isinstance(M, StringMonoidElement) and M.parent() == S:
510
raise TypeError, "Argument M (= %s) must be a string in the plaintext space." % M
511
if not mode == "ECB":
512
raise NotImplementedError, "Enciphering not implemented for mode (= %s) other than 'ECB'." % mode
513
g = self.key()
514
N = len(M)
515
m = self.parent().block_length()
516
if not N%m == 0:
517
raise TypeError, "Argument M (= %s) must be a string of length k*%s." % (M, m)
518
Melt = M._element_list # this uses the internal structure of string monoids
519
# Caution: this is parsed as an outer loop in k and an inner loop in i:
520
# for k in range(N//m):
521
# for i in range(m):
522
# S([ Melt[g(i+1)-1+k*m]
523
return S([ Melt[g(i+1)-1+k*m] for k in range(N//m) for i in range(m) ])
524
525
def inverse(self):
526
E = self.parent()
527
K = E.inverse_key(self.key())
528
return E(K)
529
530
class VigenereCipher(SymmetricKeyCipher):
531
"""
532
Vigenere cipher class
533
"""
534
def __init__(self, parent, key):
535
"""
536
Create a Vigenere cipher.
537
538
INPUT: Parent and key
539
540
EXAMPLES::
541
542
sage: S = AlphabeticStrings()
543
sage: E = VigenereCryptosystem(S,11)
544
sage: K = S("SHAKESPEARE")
545
sage: e = E(K)
546
sage: m = S("THECATINTHEHAT")
547
sage: e(m)
548
LOEMELXRTYIZHT
549
550
TESTS::
551
552
sage: S = AlphabeticStrings()
553
sage: E = VigenereCryptosystem(S,11)
554
sage: E == loads(dumps(E))
555
True
556
"""
557
SymmetricKeyCipher.__init__(self, parent, key)
558
559
def __call__(self, M, mode = "ECB"):
560
S = self.domain() # = plaintext_space = ciphertext_space
561
if not isinstance(M, StringMonoidElement) and M.parent() == S:
562
raise TypeError, "Argument M (= %s) must be a string in the plaintext space." % M
563
if not mode == "ECB":
564
raise NotImplementedError, "Enciphering not implemented for mode (= %s) other than 'ECB'." % mode
565
K = self.key()
566
m = self.parent().period()
567
n = S.ngens()
568
# This uses the internal structure of string monoids
569
Melt = M._element_list
570
Kelt = K._element_list
571
return S([ (Melt[i]+Kelt[i%m])%n for i in range(len(M)) ])
572
573
def inverse(self):
574
E = self.parent()
575
K = E.inverse_key(self.key())
576
return E(K)
577
578
579
580
581
582