Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
sagemath
GitHub Repository: sagemath/sagelib
Path: blob/master/sage/crypto/cryptosystem.py
4045 views
1
r"""
2
Cryptosystems
3
4
This module contains base classes for various cryptosystems, including
5
symmetric key and public-key cryptosystems. The classes defined in this
6
module should not be called directly. It is the responsibility of child
7
classes to implement specific cryptosystems. Take for example the
8
Hill or matrix cryptosystem as implemented in
9
:class:`HillCryptosystem <sage.crypto.classical.HillCryptosystem>`. It is a
10
symmetric key cipher so
11
:class:`HillCryptosystem <sage.crypto.classical.HillCryptosystem>` is a child
12
class of
13
:class:`SymmetricKeyCryptosystem <sage.crypto.cryptosystem.SymmetricKeyCryptosystem>`,
14
which in turn is a child class of
15
:class:`Cryptosystem <sage.crypto.cryptosystem.Cryptosystem>`. The following
16
diagram shows the inheritance relationship of particular cryptosystems::
17
18
Cryptosystem
19
+ SymmetricKeyCryptosystem
20
| + HillCryptosystem
21
| + LFSRCryptosystem
22
| + ShiftCryptosystem
23
| + ShrinkingGeneratorCryptosystem
24
| + SubstitutionCryptosystem
25
| + TranspositionCryptosystem
26
| + VigenereCryptosystem
27
+ PublicKeyCryptosystem
28
"""
29
30
#*****************************************************************************
31
# Copyright (C) 2007 David Kohel <[email protected]>
32
#
33
# Distributed under the terms of the GNU General Public License (GPL)
34
#
35
# http://www.gnu.org/licenses/
36
#*****************************************************************************
37
38
import sage.structure.parent_old as parent_old
39
from sage.sets.set import Set_generic
40
41
class Cryptosystem(parent_old.Parent, Set_generic):
42
r"""
43
A base cryptosystem class. This is meant to be extended by other
44
specialized child classes that implement specific cryptosystems.
45
A cryptosystem is a pair of maps
46
47
.. math::
48
49
E : {\mathcal K} \rightarrow {\rm Hom}({\mathcal M},{\mathcal C})
50
51
.. math::
52
53
D : {\mathcal K} \rightarrow {\rm Hom}({\mathcal C},{\mathcal M})
54
55
where `{\mathcal K}` is the key space,
56
`{\mathcal M}` is the plaintext or message space, and
57
`{\mathcal C}` is the ciphertext space. In many instances
58
`{\mathcal M} = {\mathcal C}` and the images will lie in
59
`{\rm Aut}({\mathcal M})`. An element of the image of
60
`E` is called a cipher.
61
62
We may assume that `E` and `D` are injective, hence
63
identify a key `K` in `{\mathcal K}` with its image
64
`E_K := E(K)` in
65
`\mathrm{Hom}({\mathcal M},{\mathcal C})`.
66
67
The cryptosystem has the property that for every encryption key
68
`K_1` there is a decryption key `K_2` such that
69
`D_{K_2} \circ E_{K_1}`. A cryptosystem with the
70
property that `K := K_2 = K_1`, is called a symmetric
71
cryptosystem. Otherwise, if the key `K_2 \ne K_1`, nor is
72
`K_2` easily derived from `K_1`, we call the
73
cryptosystem asymmetric or public key. In that case, `K_1`
74
is called the public key and `K_2` is called the private
75
key.
76
77
INPUT:
78
79
- ``plaintext_space`` -- the plaintext alphabet.
80
81
- ``ciphertext_space`` -- the ciphertext alphabet.
82
83
- ``key_space`` -- the key alphabet.
84
85
- ``block_length`` -- (default: 1) the block length.
86
87
- ``period`` -- (default: ``None``) the period.
88
89
EXAMPLES:
90
91
Various classical cryptosystems::
92
93
sage: ShiftCryptosystem(AlphabeticStrings())
94
Shift cryptosystem on Free alphabetic string monoid on A-Z
95
sage: SubstitutionCryptosystem(HexadecimalStrings())
96
Substitution cryptosystem on Free hexadecimal string monoid
97
sage: HillCryptosystem(BinaryStrings(), 3)
98
Hill cryptosystem on Free binary string monoid of block length 3
99
sage: TranspositionCryptosystem(OctalStrings(), 5)
100
Transposition cryptosystem on Free octal string monoid of block length 5
101
sage: VigenereCryptosystem(Radix64Strings(), 7)
102
Vigenere cryptosystem on Free radix 64 string monoid of period 7
103
"""
104
def __init__(self, plaintext_space, ciphertext_space, key_space,
105
block_length=1, period=None):
106
r"""
107
Create a ``Cryptosystem`` object. See the class ``Cryptosystem``
108
for detailed documentation.
109
110
INPUT:
111
112
- ``plaintext_space`` -- the plaintext alphabet.
113
114
- ``ciphertext_space`` -- the ciphertext alphabet.
115
116
- ``key_space`` -- the key alphabet.
117
118
- ``block_length`` -- (default: 1) the block length.
119
120
- ``period`` -- (default: ``None``) the period.
121
122
EXAMPLES:
123
124
Various classical cryptosystems::
125
126
sage: ShiftCryptosystem(AlphabeticStrings())
127
Shift cryptosystem on Free alphabetic string monoid on A-Z
128
sage: SubstitutionCryptosystem(HexadecimalStrings())
129
Substitution cryptosystem on Free hexadecimal string monoid
130
sage: HillCryptosystem(BinaryStrings(), 3)
131
Hill cryptosystem on Free binary string monoid of block length 3
132
sage: TranspositionCryptosystem(OctalStrings(), 5)
133
Transposition cryptosystem on Free octal string monoid of block length 5
134
sage: VigenereCryptosystem(Radix64Strings(), 7)
135
Vigenere cryptosystem on Free radix 64 string monoid of period 7
136
"""
137
self._cipher_domain = plaintext_space
138
self._cipher_codomain = ciphertext_space
139
self._key_space = key_space
140
self._block_length = block_length
141
self._period = period
142
143
def __eq__(self, right):
144
r"""
145
Comparing ``self`` with ``right``. Two ``Cryptosystem`` objects
146
are the same if they satisfy all of these conditions:
147
148
- share the same type
149
- have the same cipher domain
150
- have the same cipher codomain
151
- share the same key space
152
- share the same block length
153
- have the same period
154
155
INPUT:
156
157
- ``right`` -- a ``Cryptosystem`` object.
158
159
EXAMPLES:
160
161
Pairs of equivalent classical cryptosystems::
162
163
sage: sub1 = SubstitutionCryptosystem(AlphabeticStrings())
164
sage: sub2 = SubstitutionCryptosystem(AlphabeticStrings())
165
sage: sub1 == sub2
166
True
167
sage: shift1 = ShiftCryptosystem(HexadecimalStrings())
168
sage: shift2 = ShiftCryptosystem(HexadecimalStrings())
169
sage: shift1 == shift2
170
True
171
sage: hill1 = HillCryptosystem(AlphabeticStrings(), 4)
172
sage: hill2 = HillCryptosystem(AlphabeticStrings(), 4)
173
sage: hill1 == hill2
174
True
175
sage: tran1 = TranspositionCryptosystem(HexadecimalStrings(), 5)
176
sage: tran2 = TranspositionCryptosystem(HexadecimalStrings(), 5)
177
sage: tran1 == tran2
178
True
179
sage: vig1 = VigenereCryptosystem(AlphabeticStrings(), 7)
180
sage: vig2 = VigenereCryptosystem(AlphabeticStrings(), 7)
181
sage: vig1 == vig2
182
True
183
184
Pairs of different classical cryptosystems::
185
186
sage: sub1 = SubstitutionCryptosystem(AlphabeticStrings())
187
sage: sub2 = SubstitutionCryptosystem(OctalStrings())
188
sage: sub1 == sub2
189
False
190
sage: shift1 = ShiftCryptosystem(HexadecimalStrings())
191
sage: shift2 = ShiftCryptosystem(BinaryStrings())
192
sage: shift1 == shift2
193
False
194
sage: hill1 = HillCryptosystem(Radix64Strings(), 4)
195
sage: hill2 = HillCryptosystem(Radix64Strings(), 5)
196
sage: hill1 == hill2
197
False
198
sage: tran1 = TranspositionCryptosystem(Radix64Strings(), 3)
199
sage: tran2 = TranspositionCryptosystem(HexadecimalStrings(), 3)
200
sage: tran1 == tran2
201
False
202
sage: vig1 = VigenereCryptosystem(AlphabeticStrings(), 7)
203
sage: vig2 = VigenereCryptosystem(Radix64Strings(), 7)
204
sage: vig1 == vig2
205
False
206
"""
207
return type(self) == type(right) and \
208
self._cipher_domain == right._cipher_domain and \
209
self._cipher_codomain == right._cipher_codomain and \
210
self._key_space == right._key_space and \
211
self._block_length == right._block_length and \
212
self._period == right._period
213
214
def plaintext_space(self):
215
r"""
216
Return the plaintext alphabet of this cryptosystem.
217
218
EXAMPLES:
219
220
The plaintext spaces of various classical cryptosystems::
221
222
sage: ShiftCryptosystem(AlphabeticStrings()).plaintext_space()
223
Free alphabetic string monoid on A-Z
224
sage: SubstitutionCryptosystem(HexadecimalStrings()).plaintext_space()
225
Free hexadecimal string monoid
226
sage: HillCryptosystem(BinaryStrings(), 3).plaintext_space()
227
Free binary string monoid
228
sage: TranspositionCryptosystem(OctalStrings(), 5).plaintext_space()
229
Free octal string monoid
230
sage: VigenereCryptosystem(Radix64Strings(), 7).plaintext_space()
231
Free radix 64 string monoid
232
"""
233
return self._cipher_domain
234
235
def cipher_domain(self):
236
r"""
237
Return the alphabet used by this cryptosystem for encoding plaintexts.
238
This is the same as the plaintext space.
239
240
EXAMPLES:
241
242
The cipher domains, or plaintext spaces, of various classical
243
cryptosystems::
244
245
sage: ShiftCryptosystem(AlphabeticStrings()).cipher_domain()
246
Free alphabetic string monoid on A-Z
247
sage: SubstitutionCryptosystem(HexadecimalStrings()).cipher_domain()
248
Free hexadecimal string monoid
249
sage: HillCryptosystem(BinaryStrings(), 3).cipher_domain()
250
Free binary string monoid
251
sage: TranspositionCryptosystem(OctalStrings(), 5).cipher_domain()
252
Free octal string monoid
253
sage: VigenereCryptosystem(Radix64Strings(), 7).cipher_domain()
254
Free radix 64 string monoid
255
"""
256
return self._cipher_domain
257
258
def ciphertext_space(self):
259
r"""
260
Return the ciphertext alphabet of this cryptosystem.
261
262
EXAMPLES:
263
264
The ciphertext spaces of various classical cryptosystems::
265
266
sage: ShiftCryptosystem(AlphabeticStrings()).ciphertext_space()
267
Free alphabetic string monoid on A-Z
268
sage: SubstitutionCryptosystem(HexadecimalStrings()).ciphertext_space()
269
Free hexadecimal string monoid
270
sage: HillCryptosystem(BinaryStrings(), 3).ciphertext_space()
271
Free binary string monoid
272
sage: TranspositionCryptosystem(OctalStrings(), 5).ciphertext_space()
273
Free octal string monoid
274
sage: VigenereCryptosystem(Radix64Strings(), 7).ciphertext_space()
275
Free radix 64 string monoid
276
"""
277
return self._cipher_codomain
278
279
def cipher_codomain(self):
280
r"""
281
Return the alphabet used by this cryptosystem for encoding ciphertexts.
282
This is the same as the ciphertext space.
283
284
EXAMPLES:
285
286
The cipher codomains, or ciphertext spaces, of various classical
287
cryptosystems::
288
289
sage: ShiftCryptosystem(AlphabeticStrings()).cipher_codomain()
290
Free alphabetic string monoid on A-Z
291
sage: SubstitutionCryptosystem(HexadecimalStrings()).cipher_codomain()
292
Free hexadecimal string monoid
293
sage: HillCryptosystem(BinaryStrings(), 3).cipher_codomain()
294
Free binary string monoid
295
sage: TranspositionCryptosystem(OctalStrings(), 5).cipher_codomain()
296
Free octal string monoid
297
sage: VigenereCryptosystem(Radix64Strings(), 7).cipher_codomain()
298
Free radix 64 string monoid
299
"""
300
return self._cipher_codomain
301
302
def key_space(self):
303
r"""
304
Return the alphabet used by this cryptosystem for encoding keys.
305
306
EXAMPLES:
307
308
The key spaces of various classical cryptosystems::
309
310
sage: ShiftCryptosystem(AlphabeticStrings()).key_space()
311
Ring of integers modulo 26
312
sage: SubstitutionCryptosystem(HexadecimalStrings()).key_space()
313
Free hexadecimal string monoid
314
sage: HillCryptosystem(BinaryStrings(), 3).key_space()
315
Full MatrixSpace of 3 by 3 dense matrices over Ring of integers modulo 2
316
sage: TranspositionCryptosystem(OctalStrings(), 5).key_space()
317
Symmetric group of order 5! as a permutation group
318
sage: VigenereCryptosystem(Radix64Strings(), 7).key_space()
319
Free radix 64 string monoid
320
"""
321
return self._key_space
322
323
def block_length(self):
324
r"""
325
Return the block length of this cryptosystem. For some cryptosystems
326
this is not relevant, in which case the block length defaults to 1.
327
328
EXAMPLES:
329
330
The block lengths of various classical cryptosystems::
331
332
sage: ShiftCryptosystem(AlphabeticStrings()).block_length()
333
1
334
sage: SubstitutionCryptosystem(HexadecimalStrings()).block_length()
335
1
336
sage: HillCryptosystem(BinaryStrings(), 3).block_length()
337
3
338
sage: TranspositionCryptosystem(OctalStrings(), 5).block_length()
339
5
340
sage: VigenereCryptosystem(Radix64Strings(), 7).block_length()
341
1
342
"""
343
return self._block_length
344
345
def period(self):
346
if self._period is None:
347
raise TypeError, "Argument has no associated period."
348
return self._period
349
350
class SymmetricKeyCryptosystem(Cryptosystem):
351
r"""
352
The base class for symmetric key, or secret key, cryptosystems.
353
"""
354
def alphabet_size(self):
355
r"""
356
Return the number of elements in the alphabet of this
357
cryptosystem. This only applies to any cryptosystem whose plaintext
358
and ciphertext spaces are the same alphabet.
359
360
EXAMPLES::
361
362
sage: ShiftCryptosystem(AlphabeticStrings()).alphabet_size()
363
26
364
sage: ShiftCryptosystem(BinaryStrings()).alphabet_size()
365
2
366
sage: ShiftCryptosystem(HexadecimalStrings()).alphabet_size()
367
16
368
sage: SubstitutionCryptosystem(OctalStrings()).alphabet_size()
369
8
370
sage: SubstitutionCryptosystem(Radix64Strings()).alphabet_size()
371
64
372
"""
373
return self._cipher_domain.ngens()
374
375
class PublicKeyCryptosystem(Cryptosystem):
376
r"""
377
The base class for asymmetric or public-key cryptosystems.
378
"""
379
380