Coverage for local/lib/python2.7/site-packages/sage/crypto/classical_cipher.py : 81%

""" 

Classical Ciphers 

""" 

from __future__ import absolute_import 

#***************************************************************************** 

# Copyright (C) 2007 David Kohel <kohel@maths.usyd.edu.au> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from six.moves import range 

from .cipher import SymmetricKeyCipher 

from sage.monoids.string_monoid_element import StringMonoidElement 

from sage.modules.free_module import FreeModule 

class AffineCipher(SymmetricKeyCipher): 

r""" 

Affine cipher class. This is the class that does the actual work of 

encryption and decryption. Users should not directly instantiate or 

create objects of this class. Instead, functionalities of this class 

should be accessed via 

:class:`AffineCryptosystem <sage.crypto.classical.AffineCryptosystem>` 

as the latter provides a convenient user interface. 

""" 

def __init__(self, parent, key): 

r""" 

Create an affine cipher. 

INPUT: 

- ``parent`` -- an ``AffineCryptosystem`` object. 

- ``key`` -- a secret key. Let `N` be the size of the cipher domain. 

A key of this affine cipher is an ordered pair 

`(a, b) \in \ZZ_N \times \ZZ_N` such that `\gcd(a, N) = 1`. 

EXAMPLES: 

Testing of dumping and loading object:: 

sage: A = AffineCryptosystem(AlphabeticStrings()) 

sage: AC = A(3, 5) 

sage: AC == loads(dumps(AC)) 

True 

""" 

SymmetricKeyCipher.__init__(self, parent, key) 

def __eq__(self, other): 

r""" 

Comparing this ``AffineCipher`` with ``other``. Two ``AffineCipher`` 

objects are the same if they are of the same type, have the same 

parent, and share the same secret key. 

INPUT: 

- ``other`` -- another object to compare with. 

OUTPUT: 

- ``True`` if ``self`` and ``other`` are the same ``AffineCipher`` 

object; ``False`` otherwise. 

EXAMPLES:: 

sage: aff1 = AffineCryptosystem(AlphabeticStrings()) 

sage: aff2 = AffineCryptosystem(AlphabeticStrings()) 

sage: aff1 == aff2 

True 

sage: aff1(1, 2) == aff2(1, 2) 

True 

""" 

return type(self) is type(other) and self.parent() == other.parent() and self.key() == other.key() 

def __call__(self, M): 

r""" 

Return the ciphertext (respectively, plaintext) corresponding to 

``M``. This is the main place where encryption and decryption takes 

place. 

INPUT: 

- ``M`` -- a message to be encrypted or decrypted. This message must 

be encoded using the plaintext or ciphertext alphabet. The current 

behaviour is that the plaintext and ciphertext alphabets are the 

same alphabet. 

- ``algorithm`` -- (default ``"encrypt"``) whether to use the 

encryption or decryption algorithm on ``M``. The flag ``"encrypt"`` 

signifies using the encryption algorithm, while ``"decrypt"`` 

signifies using the decryption algorithm. The only acceptable 

values for ``algorithm`` are: ``"encrypt"`` and ``"decrypt"``. 

OUTPUT: 

- The ciphertext or plaintext corresponding to ``M``. 

EXAMPLES:: 

sage: A = AffineCryptosystem(AlphabeticStrings()); A 

Affine cryptosystem on Free alphabetic string monoid on A-Z 

sage: P = A.encoding("The affine cryptosystem generalizes the shift cipher.") 

sage: P 

THEAFFINECRYPTOSYSTEMGENERALIZESTHESHIFTCIPHER 

sage: a, b = (9, 13) 

sage: E = A(a, b); E 

Affine cipher on Free alphabetic string monoid on A-Z 

sage: C = E(P); C 

CYXNGGHAXFKVSCJTVTCXRPXAXKNIHEXTCYXTYHGCFHSYXK 

sage: aInv, bInv = A.inverse_key(a, b) 

sage: D = A(aInv, bInv); D 

Affine cipher on Free alphabetic string monoid on A-Z 

sage: D(C) 

THEAFFINECRYPTOSYSTEMGENERALIZESTHESHIFTCIPHER 

sage: D(C) == P 

True 

sage: D(C) == P == D(E(P)) 

True 

""" 

# sanity check 

D = self.domain() # = plaintext_space = ciphertext_space 

if M.parent() != D: 

raise TypeError("Argument M must be a string in the plaintext/ciphertext space.") 

from sage.rings.finite_rings.integer_mod import Mod 

A = list(D.alphabet()) # plaintext/ciphertext alphabet as a list 

N = self.domain().ngens() # number of elements in this alphabet 

a, b = self.key() # encryption/decryption key (a,b) 

# Let I be the index list of M. That is, the i-th element of M has 

# index k in the cipher domain D. We store this cipher domain index 

# as the i-th element of I. 

I = [A.index(str(e)) for e in M] 

# Encrypt the plaintext M. For each element i in I, the ciphertext 

# corresponding to i is ai + b (mod N). This can also be used for 

# decryption, in which case (a, b) is the inverse key corresponding 

# to a secret key. 

return D([ A.index(A[Mod(a*i + b, N).lift()]) for i in I ]) 

def _repr_(self): 

r""" 

Return the string representation of this affine cipher. 

EXAMPLES:: 

sage: A = AffineCryptosystem(AlphabeticStrings()) 

sage: A(1, 2) 

Affine cipher on Free alphabetic string monoid on A-Z 

""" 

# The affine cipher has the plaintext and ciphertext spaces defined 

# over the same non-empty alphabet. The cipher domain is the same 

# as the alphabet used for the plaintext and ciphertext spaces. 

return "Affine cipher on %s" % self.parent().cipher_domain() 

class HillCipher(SymmetricKeyCipher): 

""" 

Hill cipher class 

""" 

def __init__(self, parent, key): 

""" 

Create a Hill cipher. 

INPUT: Parent and key 

EXAMPLES:: 

sage: S = AlphabeticStrings() 

sage: E = HillCryptosystem(S,3) 

sage: E 

Hill cryptosystem on Free alphabetic string monoid on A-Z of block length 3 

sage: M = E.key_space() 

sage: A = M([[1,0,1],[0,1,1],[2,2,3]]) 

sage: A 

[1 0 1] 

[0 1 1] 

[2 2 3] 

sage: e = E(A); e 

Hill cipher on Free alphabetic string monoid on A-Z of block length 3 

sage: e(S("LAMAISONBLANCHE")) 

JYVKSKQPELAYKPV 

TESTS:: 

sage: S = AlphabeticStrings() 

sage: E = HillCryptosystem(S,3) 

sage: E == loads(dumps(E)) 

True 

""" 

# TODO: some type checking that the key is an invertible matrix? 

SymmetricKeyCipher.__init__(self, parent, key) 

def __eq__(self, right): 

return type(self) is type(right) and self.parent() == right.parent() and self.key() == right.key() 

def __call__(self, M): 

S = self.domain() # = plaintext_space = ciphertext_space 

if not isinstance(M, StringMonoidElement) and M.parent() == S: 

raise TypeError("Argument M (= %s) must be a string in the plaintext space." % M) 

m = self.parent().block_length() 

if len(M) % m != 0: 

raise TypeError("The length of M (= %s) must be a multiple of %s." % (M, m )) 

Alph = list(S.alphabet()) 

A = self.key() # A is an m x m matrix 

R = A.parent().base_ring() 

V = FreeModule(R,m) 

Mstr = str(M) 

C = [] 

for i in range(len(M)//m): 

v = V([ Alph.index(Mstr[m*i+j]) for j in range(m) ]) 

C += (v * A).list() 

return S([ k.lift() for k in C ]) 

def _repr_(self): 

r""" 

Return the string representation of this Hill cipher. 

EXAMPLES:: 

sage: H = HillCryptosystem(AlphabeticStrings(), 3) 

sage: M = MatrixSpace(IntegerModRing(26), 3, 3) 

sage: A = M([[1,0,1], [0,1,1], [2,2,3]]) 

sage: e = H(A); e 

Hill cipher on Free alphabetic string monoid on A-Z of block length 3 

""" 

return "Hill cipher on %s of block length %s" % ( 

self.parent().cipher_domain(), self.parent().block_length() ) 

def inverse(self): 

E = self.parent() 

try: 

B = E.inverse_key(self.key()) 

except Exception: 

raise ValueError("Argument\n\n%s\n\nmust be an invertible cipher." % self) 

return E(B) 

class ShiftCipher(SymmetricKeyCipher): 

r""" 

Shift cipher class. This is the class that does the actual work of 

encryption and decryption. Users should not directly instantiate or 

create objects of this class. Instead, functionalities of this class 

should be accessed via 

:class:`ShiftCryptosystem <sage.crypto.classical.ShiftCryptosystem>` 

as the latter provides a convenient user interface. 

""" 

def __init__(self, parent, key): 

r""" 

Create a shift cipher. 

INPUT: 

- ``parent`` -- a ``ShiftCryptosystem`` object. 

- ``key`` -- a secret key. 

EXAMPLES:: 

sage: S = ShiftCryptosystem(AlphabeticStrings()); S 

Shift cryptosystem on Free alphabetic string monoid on A-Z 

sage: P = S.encoding("The shift cryptosystem generalizes the Caesar cipher.") 

sage: P 

THESHIFTCRYPTOSYSTEMGENERALIZESTHECAESARCIPHER 

sage: K = 7 

sage: C = S.enciphering(K, P); C 

AOLZOPMAJYFWAVZFZALTNLULYHSPGLZAOLJHLZHYJPWOLY 

sage: S.deciphering(K, C) 

THESHIFTCRYPTOSYSTEMGENERALIZESTHECAESARCIPHER 

sage: S.deciphering(K, C) == P 

True 

""" 

SymmetricKeyCipher.__init__(self, parent, key) 

def __eq__(self, other): 

r""" 

Comparing this ``ShiftCipher`` with ``other``. Two ``ShiftCipher`` 

objects are the same if they are of the same type, have the same 

parent, and share the same secret key. 

INPUT: 

- ``other`` -- another object to compare with. 

OUTPUT: 

- ``True`` if ``self`` and ``other`` are the same ``ShiftCipher`` 

object; ``False`` otherwise. 

EXAMPLES:: 

sage: shift1 = ShiftCryptosystem(AlphabeticStrings()) 

sage: shift2 = ShiftCryptosystem(AlphabeticStrings()) 

sage: shift1 == shift2 

True 

sage: shift1 = ShiftCryptosystem(HexadecimalStrings()) 

sage: shift2 = ShiftCryptosystem(BinaryStrings()) 

sage: shift1 == shift2 

False 

""" 

return type(self) is type(other) and self.parent() == other.parent() and self.key() == other.key() 

def __call__(self, M): 

r""" 

Return the ciphertext (respectively, plaintext) corresponding to 

``M``. This is the main place where encryption and decryption takes 

place. 

INPUT: 

- ``M`` -- a message to be encrypted or decrypted. This message must 

be encoded using the plaintext or ciphertext alphabet. The current 

behaviour is that the plaintext and ciphertext alphabets are the 

same alphabet. 

OUTPUT: 

- The ciphertext or plaintext corresponding to ``M``. 

EXAMPLES: 

These are indirect doctests. Functionalities of this class are 

usually invoked from 

:class:`ShiftCryptosystem <sage.crypto.classical.ShiftCryptosystem>`. 

:: 

sage: S = ShiftCryptosystem(AlphabeticStrings()) 

sage: S.enciphering(12, S.encoding("Stop shifting me.")) 

EFABETURFUZSYQ 

sage: S = ShiftCryptosystem(HexadecimalStrings()) 

sage: S.enciphering(7, S.encoding("Shift me now.")) 

cadfd0ddeb97d4dc97d5d6ee95 

sage: S = ShiftCryptosystem(BinaryStrings()) 

sage: S.enciphering(1, S.encoding("OK, enough shifting.")) 

1011000010110100110100111101111110011010100100011001000010001010100110001001011111011111100011001001011110010110100110011000101110010110100100011001100011010001 

""" 

dom = self.domain() # = plaintext_space = ciphertext_space 

if not isinstance(M, StringMonoidElement) and M.parent() == dom: 

raise TypeError("Argument M (= %s) must be a string in the plaintext/ciphertext space." % M) 

from sage.rings.finite_rings.integer_mod import Mod 

A = list(dom.alphabet()) # plaintext/ciphertext alphabet as a list 

N = self.domain().ngens() # number of elements in this alphabet 

K = self.key() # encryption/decryption key 

# Here, M is a message encoded within the ciphertext/plaintext 

# alphabet of this shift cryptosystem. The list A above is a list of 

# all elements of this alphabet, each element being associated with 

# an index 0 <= i < n, where n is the size of A. Now get the index 

# of each character in the message M, storing all these indices 

# in the index list I. 

# TODO: the following two lines are coded with clarity and 

# readability in mind. It is possible to remove the overhead of 

# doing a list comprehension to get the index associated with each 

# element of M. For example, the next two lines can be crammed into 

# one list comprehension as follows: 

# return dom([ A.index(A[Mod(A.index(str(i)) + K, N).lift()]) for i in M ]) 

# But it performs badly compared to the following two lines. 

I = [A.index(str(e)) for e in M] 

# Perform encryption/decryption on the whole message M, returning 

# the result as a string encoded in the alphabet A. 

return dom([ A.index(A[Mod(i + K, N).lift()]) for i in I ]) 

def _repr_(self): 

r""" 

Return the string representation of this shift cipher. 

EXAMPLES:: 

sage: S = ShiftCryptosystem(AlphabeticStrings()) 

sage: S(3) 

Shift cipher on Free alphabetic string monoid on A-Z 

sage: S = ShiftCryptosystem(HexadecimalStrings()) 

sage: S(5) 

Shift cipher on Free hexadecimal string monoid 

sage: S = ShiftCryptosystem(BinaryStrings()) 

sage: S(1) 

Shift cipher on Free binary string monoid 

""" 

# The shift cipher has the plaintext and ciphertext spaces defined 

# over the same non-empty alphabet. The cipher domain is the same 

# as the alphabet used for the plaintext and ciphertext spaces. 

return "Shift cipher on %s" % self.parent().cipher_domain() 

class SubstitutionCipher(SymmetricKeyCipher): 

""" 

Substitution cipher class 

""" 

def __init__(self, parent, key): 

""" 

Create a substitution cipher. 

INPUT: Parent and key 

EXAMPLES:: 

sage: S = AlphabeticStrings() 

sage: E = SubstitutionCryptosystem(S) 

sage: E 

Substitution cryptosystem on Free alphabetic string monoid on A-Z 

sage: K = S([ 25-i for i in range(26) ]) 

sage: K 

ZYXWVUTSRQPONMLKJIHGFEDCBA 

sage: e = E(K) 

sage: m = S("THECATINTHEHAT") 

sage: e(m) 

GSVXZGRMGSVSZG 

TESTS:: 

sage: S = AlphabeticStrings() 

sage: E = SubstitutionCryptosystem(S) 

sage: E == loads(dumps(E)) 

True 

""" 

SymmetricKeyCipher.__init__(self, parent, key) 

def __eq__(self, right): 

return type(self) is type(right) and self.parent() == right.parent() and self.key() == right.key() 

def __call__(self, M): 

S = self.domain() # = plaintext_space = ciphertext_space 

if not isinstance(M, StringMonoidElement) and M.parent() == S: 

raise TypeError("Argument M (= %s) must be a string in the plaintext space." % M) 

A = list(S.alphabet()) 

K = str(self.key()) # K is a string, while we want the indices: 

I = [ A.index(K[i]) for i in range(len(K)) ] 

Mstr = str(M) 

return S([ I[A.index(Mstr[i])] for i in range(len(Mstr)) ]) 

def _repr_(self): 

r""" 

Return the string representation of this substitution cipher. 

EXAMPLES:: 

sage: A = HexadecimalStrings(); S = SubstitutionCryptosystem(A) 

sage: K = A([16-i for i in range(16)]); S(K) 

Substitution cipher on Free hexadecimal string monoid 

sage: A = AlphabeticStrings(); S = SubstitutionCryptosystem(A) 

sage: K = A([26-i for i in range(26)]); S(K) 

Substitution cipher on Free alphabetic string monoid on A-Z 

sage: A = OctalStrings(); S = SubstitutionCryptosystem(A) 

sage: K = A([8-i for i in range(8)]); S(K) 

Substitution cipher on Free octal string monoid 

sage: A = BinaryStrings(); S = SubstitutionCryptosystem(A) 

sage: K = A([2-i for i in range(2)]); S(K) 

Substitution cipher on Free binary string monoid 

sage: A = Radix64Strings(); S = SubstitutionCryptosystem(A) 

sage: K = A([64-i for i in range(64)]); S(K) 

Substitution cipher on Free radix 64 string monoid 

""" 

return "Substitution cipher on %s" % self.parent().cipher_domain() 

def inverse(self): 

E = self.parent() 

K = E.inverse_key(self.key()) 

return E(K) 

class TranspositionCipher(SymmetricKeyCipher): 

""" 

Transition cipher class 

""" 

def __init__(self, parent, key): 

""" 

Create a transposition cipher. 

INPUT: Parent and key 

EXAMPLES:: 

sage: S = AlphabeticStrings() 

sage: E = TranspositionCryptosystem(S,14) 

sage: E 

Transposition cryptosystem on Free alphabetic string monoid on A-Z of block length 14 

sage: K = [ 14-i for i in range(14) ] 

sage: K 

[14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 

sage: e = E(K) 

sage: m = S("THECATINTHEHAT") 

sage: e(m) 

TAHEHTNITACEHT 

EXAMPLES:: 

sage: S = AlphabeticStrings() 

sage: E = TranspositionCryptosystem(S,15); 

sage: m = S("THECATANDTHEHAT") 

sage: G = E.key_space() 

sage: G 

Symmetric group of order 15! as a permutation group 

sage: g = G([ 3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13 ]) 

sage: e = E(g) 

sage: e(m) 

EHTTACDNAEHTTAH 

TESTS:: 

sage: S = AlphabeticStrings() 

sage: E = TranspositionCryptosystem(S,14) 

sage: E == loads(dumps(E)) 

True 

""" 

n = parent.block_length() 

if isinstance(key, list) and not len(key) == n: 

raise ValueError("key (= %s) must have block length %s" % (key, n)) 

SymmetricKeyCipher.__init__(self, parent, key) 

def __call__(self, M, mode = "ECB"): 

S = self.domain() # = plaintext_space = ciphertext_space 

if not isinstance(M, StringMonoidElement) and M.parent() == S: 

raise TypeError("Argument M (= %s) must be a string in the plaintext space." % M) 

if not mode == "ECB": 

raise NotImplementedError("Enciphering not implemented for mode (= %s) other than 'ECB'." % mode) 

g = self.key() 

N = len(M) 

m = self.parent().block_length() 

if not N%m == 0: 

raise TypeError("Argument M (= %s) must be a string of length k*%s." % (M, m)) 

Melt = M._element_list # this uses the internal structure of string monoids 

# Caution: this is parsed as an outer loop in k and an inner loop in i: 

# for k in range(N//m): 

# for i in range(m): 

# S([ Melt[g(i+1)-1+k*m] 

return S([ Melt[g(i+1)-1+k*m] for k in range(N//m) for i in range(m) ]) 

def inverse(self): 

E = self.parent() 

K = E.inverse_key(self.key()) 

return E(K) 

class VigenereCipher(SymmetricKeyCipher): 

""" 

Vigenere cipher class 

""" 

def __init__(self, parent, key): 

""" 

Create a Vigenere cipher. 

INPUT: Parent and key 

EXAMPLES:: 

sage: S = AlphabeticStrings() 

sage: E = VigenereCryptosystem(S,11) 

sage: K = S("SHAKESPEARE") 

sage: e = E(K) 

sage: m = S("THECATINTHEHAT") 

sage: e(m) 

LOEMELXRTYIZHT 

TESTS:: 

sage: S = AlphabeticStrings() 

sage: E = VigenereCryptosystem(S,11) 

sage: E == loads(dumps(E)) 

True 

""" 

SymmetricKeyCipher.__init__(self, parent, key) 

def __call__(self, M, mode = "ECB"): 

S = self.domain() # = plaintext_space = ciphertext_space 

if not isinstance(M, StringMonoidElement) and M.parent() == S: 

raise TypeError("Argument M (= %s) must be a string in the plaintext space." % M) 

if not mode == "ECB": 

raise NotImplementedError("Enciphering not implemented for mode (= %s) other than 'ECB'." % mode) 

K = self.key() 

m = self.parent().period() 

n = S.ngens() 

# This uses the internal structure of string monoids 

Melt = M._element_list 

Kelt = K._element_list 

return S([ (Melt[i]+Kelt[i%m])%n for i in range(len(M)) ]) 

def inverse(self): 

E = self.parent() 

K = E.inverse_key(self.key()) 

return E(K)