Basic Cryptography Module

Included in this module are both block ciphers and stream ciphers.

• Shift cipher
• Affine cipher
• Bifid ciphers
• Vigenere’s cipher
• substitution ciphers
• Hill’s cipher
• RSA
• Kid RSA
• linear feedback shift registers (a stream cipher)
• ElGamal encryption

sympy.crypto.crypto.alphabet_of_cipher(symbols='ABCDEFGHIJKLMNOPQRSTUVWXYZ')

Returns the list of characters in the string input defining the alphabet.

Notes

First, some basic definitions.

A substitution cipher is a method of encryption by which “units” (not necessarily characters) of plaintext are replaced with ciphertext according to a regular system. The “units” may be characters (ie, words of length \(1\)), words of length \(2\), and so forth.

A transposition cipher is a method of encryption by which the positions held by “units” of plaintext are replaced by a permutation of the plaintext. That is, the order of the units is changed using a bijective function on the characters’ positions to perform the encryption.

A monoalphabetic cipher uses fixed substitution over the entire message, whereas a polyalphabetic cipher uses a number of substitutions at different times in the message.

Each of these ciphers require an alphabet for the messages to be constructed from.

Examples

>>> from sympy.crypto.crypto import alphabet_of_cipher
>>> alphabet_of_cipher()
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
>>> L = [str(i) for i in range(10)] + ['a', 'b', 'c']; L
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c']
>>> A = "".join(L); A
'0123456789abc'
>>> alphabet_of_cipher(A)
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c']
>>> alphabet_of_cipher()
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

sympy.crypto.crypto.cycle_list(k, n)

Returns the cyclic shift of the list range(n) by k.

Examples

>>> from sympy.crypto.crypto import cycle_list, alphabet_of_cipher
>>> L = cycle_list(3,26); L
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 0, 1, 2]
>>> A = alphabet_of_cipher(); A
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
>>> [A[i] for i in L]
['D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'A', 'B', 'C']

sympy.crypto.crypto.encipher_shift(pt, key, symbols='ABCDEFGHIJKLMNOPQRSTUVWXYZ')

Performs shift cipher encryption on plaintext pt, and returns the ciphertext.

Notes

The shift cipher is also called the Caesar cipher, after Julius Caesar, who, according to Suetonius, used it with a shift of three to protect messages of military significance. Caesar’s nephew Augustus reportedtly used a similar cipher, but with a right shift of 1.

ALGORITHM:

INPUT:

k: an integer from 0 to 25 (the secret key)

m: string of upper-case letters (the plaintext message)

OUTPUT:

c: string of upper-case letters (the ciphertext message)

STEPS:

0. Identify the alphabet A, ..., Z with the integers 0, ..., 25.
1. Compute from the string m a list L1 of corresponding integers.
2. Compute from the list L1 a new list L2, given by adding (k mod 26) to each element in L1.
3. Compute from the list L2 a string c of corresponding letters.

Examples

>>> from sympy.crypto.crypto import encipher_shift
>>> pt = "GONAVYBEATARMY"
>>> encipher_shift(pt, 1)
'HPOBWZCFBUBSNZ'
>>> encipher_shift(pt, 0)
'GONAVYBEATARMY'
>>> encipher_shift(pt, -1)
'FNMZUXADZSZQLX'

sympy.crypto.crypto.encipher_affine(pt, key, symbols='ABCDEFGHIJKLMNOPQRSTUVWXYZ')

Performs the affine cipher encryption on plaintext pt, and returns the ciphertext.

Encryption is based on the map \(x \rightarrow ax+b\) (mod \(26\)). Decryption is based on the map \(x \rightarrow cx+d\) (mod \(26\)), where \(c = a^{-1}\) (mod \(26\)) and \(d = -a^{-1}c\) (mod \(26\)). (In particular, for the map to be invertible, we need \(\mathrm{gcd}(a, 26) = 1.\))

Notes

This is a straightforward generalization of the shift cipher.

ALGORITHM:

INPUT:

a, b: a pair integers, where gcd(a, 26) = 1 (the secret key)

m: string of upper-case letters (the plaintext message)

OUTPUT:

c: string of upper-case letters (the ciphertext message)

STEPS:

0. Identify the alphabet “A”, ..., “Z” with the integers 0, ..., 25.
1. Compute from the string m a list L1 of corresponding integers.
2. Compute from the list L1 a new list L2, given by replacing x by a*x + b (mod 26), for each element x in L1.
3. Compute from the list L2 a string c of corresponding letters.

Examples

>>> from sympy.crypto.crypto import encipher_affine
>>> pt = "GONAVYBEATARMY"
>>> encipher_affine(pt, (1, 1))
'HPOBWZCFBUBSNZ'
>>> encipher_affine(pt, (1, 0))
'GONAVYBEATARMY'
>>> pt = "GONAVYBEATARMY"
>>> encipher_affine(pt, (3, 1))
'TROBMVENBGBALV'
>>> ct = "TROBMVENBGBALV"
>>> encipher_affine(ct, (9, 17))
'GONAVYBEATARMY'

sympy.crypto.crypto.encipher_substitution(pt, key, symbols='ABCDEFGHIJKLMNOPQRSTUVWXYZ')

Performs the substitution cipher encryption on plaintext pt, and returns the ciphertext.

Assumes the pt has only letters taken from symbols. Assumes key is a permutation of the symbols. This funciton permutes the letters of the plaintext using the permutation given in key. The decription uses the inverse permutation. Note that if the permutation in key is order 2 (eg, a transposition) then the encryption permutation and the decryption permutation are the same.

Examples

>>> from sympy.crypto.crypto import alphabet_of_cipher, encipher_substitution
>>> symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
>>> A = alphabet_of_cipher(symbols)
>>> key = "BACDEFGHIJKLMNOPQRSTUVWXYZ"
>>> pt = "go navy! beat army!"
>>> encipher_substitution(pt, key)
'GONBVYAEBTBRMY'
>>> ct = 'GONBVYAEBTBRMY'
>>> encipher_substitution(ct, key)
'GONAVYBEATARMY'

sympy.crypto.crypto.encipher_vigenere(pt, key, symbols='ABCDEFGHIJKLMNOPQRSTUVWXYZ')

Performs the Vigenere cipher encryption on plaintext pt, and returns the ciphertext.

Notes

The Vigenere cipher is named after Blaise de Vigenere, a sixteenth century diplomat and cryptographer, by a historical accident. Vigene`re actually invented a different and more complicated cipher. The so-called Vigenere cipher cipher was actually invented by Giovan Batista Belaso in 1553.

This cipher was used in the 1700’s, for example, during the American Civil War. The Confederacy used a brass cipher disk to implement the Vigenere cipher (now on display in the NSA Museum in Fort Meade) [R29].

The Vigenere cipher is a generalization of the shift cipher. Whereas the shift cipher shifts each letter by the same amount (that amount being the key of the shift cipher) the Vigenere cipher shifts a letter by an amount determined by the key, which is a word or phrase known only to the sender and receiver).

For example, if the key was a single letter, such as “C”, then the so-called Vigenere cipher is actually a shift cipher with a shift of \(2\) (since “C” is the 2nd letter of the alphabet, if you start counting at \(0\)). If the key was a word with two letters, such as “CA”, then the so-called Vigenere cipher will shift letters in even positions by \(2\) and letters in odd positions are left alone (shifted by \(0\), since “A” is the 0th letter, if you start counting at \(0\)).

ALGORITHM:

INPUT:

key: a string of upper-case letters (the secret key)

m: string of upper-case letters (the plaintext message)

OUTPUT:

c: string of upper-case letters (the ciphertext message)

STEPS:

0. Identify the alphabet A, ..., Z with the integers 0, ..., 25.
1. Compute from the string key a list L1 of corresponding integers. Let n1 = len(L1).
2. Compute from the string m a list L2 of corresponding integers. Let n2 = len(L2).
3. Break L2 up sequencially into sublists of size n1, and one sublist at the end of size smaller or equal to n1.
4. For each of these sublists L of L2, compute a new list C given by C[i] = L[i] + L1[i] (mod 26) to the i-th element in the sublist, for each i.
5. Assemble these lists C by concatenation into a new list of length n2.
6. Compute from the new list a string c of corresponding letters.

Once it is known that the key is, say, \(n\) characters long, frequency analysis can be applied to every \(n\)-th letter of the ciphertext to determine the plaintext. This method is called Kasiski examination (although it was first discovered by Babbage).

The cipher Vigenere actually discovered is an “auto-key” cipher described as follows.

ALGORITHM:

INPUT:

key: a string of upper-case letters (the secret key)

m: string of upper-case letters (the plaintext message)

OUTPUT:

c: string of upper-case letters (the ciphertext message)

STEPS:

0. Identify the alphabet A, ..., Z with the integers 0, ..., 25.
1. Compute from the string m a list L2 of corresponding integers. Let n2 = len(L2).
2. Let n1 be the length of the key. Concatenate the string key with the first n2 - n1 characters of the plaintext message. Compute from this string of length n2 a list L1 of corresponding integers. Note n2 = len(L1).
3. Compute a new list C given by C[i] = L1[i] + L2[i] (mod 26), for each i. Note n2 = len(C).
4. Compute from the new list a string c of corresponding letters.

References

[R29]

(1, 2) http://en.wikipedia.org/wiki/Vigenere_cipher

Examples

>>> from sympy.crypto.crypto import encipher_vigenere
>>> key = "encrypt"
>>> pt = "meet me on monday"
>>> encipher_vigenere(pt, key)
'QRGKKTHRZQEBPR'

sympy.crypto.crypto.decipher_vigenere(ct, key, symbols='ABCDEFGHIJKLMNOPQRSTUVWXYZ')

Decode using the Vigenere cipher.

Examples

>>> from sympy.crypto.crypto import decipher_vigenere
>>> key = "encrypt"
>>> ct = "QRGK kt HRZQE BPR"
>>> decipher_vigenere(ct, key)
'MEETMEONMONDAY'

sympy.crypto.crypto.encipher_hill(pt, key, symbols='ABCDEFGHIJKLMNOPQRSTUVWXYZ')

Performs the Hill cipher encryption on plaintext pt, and returns the ciphertext.

Notes

The Hill cipher [R30], invented by Lester S. Hill in 1920’s [R31], was the first polygraphic cipher in which it was practical (though barely) to operate on more than three symbols at once. The following discussion assumes an elementary knowledge of matrices.

First, each letter is first encoded as a number. We assume here that “A” \(\leftrightarrow\) 0, “B” \(\leftrightarrow\) 1, ..., “Z” \(\leftrightarrow\) 25. We denote the integers \(\{0, 1, ..., 25\}\) by \(Z_{26}\). Suppose your message m consists of \(n\) capital letters, with no spaces. This may be regarded an \(n\)-tuple M of elements of \(Z_{26}\). A key in the Hill cipher is a \(k x k\) matrix \(K\), all of whose entries are in \(Z_{26}\), such that the matrix \(K\) is invertible (ie, that the linear transformation \(K: Z_{26}^k \rightarrow Z_{26}^k\) is one-to-one).

ALGORITHM:

INPUT:

key: a \(k x k\) invertible matrix \(K\), all of whose entries are in \(Z_{26}\)

m: string of \(n\) upper-case letters (the plaintext message) (Note: Sage assumes that \(n\) is a multiple of \(k\).)

OUTPUT:

c: string of upper-case letters (the ciphertext message)

STEPS:

0. Identify the alphabet A, ..., Z with the integers 0, ..., 25.
1. Compute from the string m a list L of corresponding integers. Let n = len(L).
2. Break the list L up into t = ceiling(n/k) sublists L_1, ..., L_t of size k (where the last list might be “padded” by 0’s to ensure it is size k).
3. Compute new list C_1, ..., C_t given by C[i] = K*L_i (arithmetic is done mod 26), for each i.
4. Concatenate these into a list C = C_1 + ... + C_t.
5. Compute from C a string c of corresponding letters. This has length k*t.

References

[R30]

(1, 2) en.wikipedia.org/wiki/Hill_cipher

[R31]

(1, 2) Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly Vol.36, June-July 1929, pp.306-312.

Examples

>>> from sympy.crypto.crypto import encipher_hill
>>> from sympy import Matrix
>>> pt = "meet me on monday"
>>> key = Matrix([[1, 2], [3, 5]])
>>> encipher_hill(pt, key)
'UEQDUEODOCTCWQ'
>>> pt = "meet me on tuesday"
>>> encipher_hill(pt, key)
'UEQDUEODHBOYDJYU'
>>> pt = "GONAVYBEATARMY"
>>> key = Matrix([[1, 0, 1], [0, 1, 1], [2, 2, 3]])
>>> encipher_hill(pt, key)
'TBBYTKBEKKRLMYU'

sympy.crypto.crypto.decipher_hill(ct, key, symbols='ABCDEFGHIJKLMNOPQRSTUVWXYZ')

Deciphering is the same as ciphering but using the inverse of the key matrix.

Examples

>>> from sympy.crypto.crypto import decipher_hill
>>> from sympy import Matrix
>>> ct = "UEQDUEODOCTCWQ"
>>> key = Matrix([[1, 2], [3, 5]])
>>> decipher_hill(ct, key)
'MEETMEONMONDAY'
>>> ct = "UEQDUEODHBOYDJYU"
>>> decipher_hill(ct, key)
'MEETMEONTUESDAYA'

sympy.crypto.crypto.encipher_bifid5(pt, key)

Performs the Bifid cipher encryption on plaintext pt, and returns the ciphertext.

This is the version of the Bifid cipher that uses the \(5 \times 5\) Polybius square.

Notes

The Bifid cipher was invented around 1901 by Felix Delastelle. It is a fractional substitution cipher, where letters are replaced by pairs of symbols from a smaller alphabet. The cipher uses a \(5 \times 5\) square filled with some ordering of the alphabet, except that “i”s and “j”s are identified (this is a so-called Polybius square; there is a \(6 \times 6\) analog if you add back in “j” and also append onto the usual 26 letter alphabet, the digits 0, 1, ..., 9). According to Helen Gaines’ book Cryptanalysis, this type of cipher was used in the field by the German Army during World War I.

ALGORITHM: (5x5 case)

INPUT:

pt: plaintext string (no “j”s)

key: short string for key (no repetitions, no “j”s)

OUTPUT:

ciphertext (using Bifid5 cipher in all caps, no spaces, no “J”s)

STEPS:

1. Create the \(5 \times 5\) Polybius square S associated to the k as follows:

   1. starting top left, moving left-to-right, top-to-bottom, place the letters of the key into a 5x5 matrix,
   2. when finished, add the letters of the alphabet not in the key until the 5x5 square is filled

2. Create a list P of pairs of numbers which are the coordinates in the Polybius square of the letters in pt.

3. Let L1 be the list of all first coordinates of P (length of L1 = n), let L2 be the list of all second coordinates of P (so the length of L2 is also n).

4. Let L be the concatenation of L1 and L2 (length L = 2*n), except that consecutive numbers are paired (L[2*i], L[2*i + 1]). You can regard L as a list of pairs of length n.

5. Let C be the list of all letters which are of the form S[i, j], for all (i, j) in L. As a string, this is the ciphertext ct.

Examples

>>> from sympy.crypto.crypto import encipher_bifid5
>>> pt = "meet me on monday"
>>> key = "encrypt"
>>> encipher_bifid5(pt, key)
'LNLLQNPPNPGADK'
>>> pt = "meet me on friday"
>>> encipher_bifid5(pt, key)
'LNLLFGPPNPGRSK'

sympy.crypto.crypto.decipher_bifid5(ct, key)

Performs the Bifid cipher decryption on ciphertext ct, and returns the plaintext.

This is the version of the Bifid cipher that uses the \(5 \times 5\) Polybius square.

INPUT:

ct: ciphertext string (digits okay)

key: short string for key (no repetitions, digits okay)

OUTPUT:

plaintext from Bifid5 cipher (all caps, no spaces, no “J”s)

Examples

>>> from sympy.crypto.crypto import encipher_bifid5, decipher_bifid5
>>> key = "encrypt"
>>> pt = "meet me on monday"
>>> encipher_bifid5(pt, key)
'LNLLQNPPNPGADK'
>>> ct = 'LNLLQNPPNPGADK'
>>> decipher_bifid5(ct, key)
'MEETMEONMONDAY'

sympy.crypto.crypto.bifid5_square(key)

5x5 Polybius square.

Produce the Polybius square for the \(5 \times 5\) Bifid cipher.

Examples

>>> from sympy.crypto.crypto import bifid5_square
>>> bifid5_square("gold bug")
Matrix([
[G, O, L, D, B],
[U, A, C, E, F],
[H, I, K, M, N],
[P, Q, R, S, T],
[V, W, X, Y, Z]])

sympy.crypto.crypto.encipher_bifid6(pt, key)

Performs the Bifid cipher encryption on plaintext pt, and returns the ciphertext.

This is the version of the Bifid cipher that uses the \(6 \times 6\) Polybius square. Assumes alphabet of symbols is “A”, ..., “Z”, “0”, ..., “9”.

INPUT:

pt: plaintext string (digits okay)

key: short string for key (no repetitions, digits okay)

OUTPUT:

ciphertext from Bifid cipher (all caps, no spaces)

Examples

>>> from sympy.crypto.crypto import encipher_bifid6
>>> key = "encrypt"
>>> pt = "meet me on monday at 8am"
>>> encipher_bifid6(pt, key)
'HNHOKNTA5MEPEGNQZYG'
>>> encipher_bifid6(pt, key)
'HNHOKNTA5MEPEGNQZYG'

sympy.crypto.crypto.decipher_bifid6(ct, key)

Performs the Bifid cipher decryption on ciphertext ct, and returns the plaintext.

This is the version of the Bifid cipher that uses the \(6 \times 6\) Polybius square. Assumes alphabet of symbols is “A”, ..., “Z”, “0”, ..., “9”.

INPUT:

ct: ciphertext string (digits okay)

key: short string for key (no repetitions, digits okay)

OUTPUT:

plaintext from Bifid cipher (all caps, no spaces)

Examples

>>> from sympy.crypto.crypto import encipher_bifid6, decipher_bifid6
>>> key = "encrypt"
>>> pt = "meet me on monday at 8am"
>>> encipher_bifid6(pt, key)
'HNHOKNTA5MEPEGNQZYG'
>>> ct = "HNHOKNTA5MEPEGNQZYG"
>>> decipher_bifid6(ct, key)
'MEETMEONMONDAYAT8AM'

sympy.crypto.crypto.bifid6_square(key)

6x6 Polybius square.

Produces the Polybius square for the \(6 \times 6\) Bifid cipher. Assumes alphabet of symbols is “A”, ..., “Z”, “0”, ..., “9”.

Examples

>>> from sympy.crypto.crypto import bifid6_square
>>> key = "encrypt"
>>> bifid6_square(key)
Matrix([
[E, N, C, R, Y, P],
[T, A, B, D, F, G],
[H, I, J, K, L, M],
[O, Q, S, U, V, W],
[X, Z, 0, 1, 2, 3],
[4, 5, 6, 7, 8, 9]])

sympy.crypto.crypto.encipher_bifid7(pt, key)

Performs the Bifid cipher encryption on plaintext pt, and returns the ciphertext.

This is the version of the Bifid cipher that uses the \(7 \times 7\) Polybius square. Assumes alphabet of symbols is “A”, ..., “Z”, “0”, ..., “22”. (Also, assumes you have some way of distinguishing “22” from “2”, “2” juxtaposed together for deciphering...)

INPUT:

pt: plaintext string (digits okay)

key: short string for key (no repetitions, digits okay)

OUTPUT:

ciphertext from Bifid7 cipher (all caps, no spaces)

Examples

>>> from sympy.crypto.crypto import encipher_bifid7
>>> key = "encrypt"
>>> pt = "meet me on monday at 8am"
>>> encipher_bifid7(pt, key)
'JEJJLNAA3ME19YF3J222R'

sympy.crypto.crypto.bifid7_square(key)

7x7 Polybius square.

Produce the Polybius square for the \(7 \times 7\) Bifid cipher. Assumes alphabet of symbols is “A”, ..., “Z”, “0”, ..., “22”. (Also, assumes you have some way of distinguishing “22” from “2”, “2” juxtaposed together for deciphering...)

Examples

>>> from sympy.crypto.crypto import bifid7_square
>>> bifid7_square("gold bug")
Matrix([
[ G,  O,  L,  D,  B,  U,  A],
[ C,  E,  F,  H,  I,  J,  K],
[ M,  N,  P,  Q,  R,  S,  T],
[ V,  W,  X,  Y,  Z,  0,  1],
[ 2,  3,  4,  5,  6,  7,  8],
[ 9, 10, 11, 12, 13, 14, 15],
[16, 17, 18, 19, 20, 21, 22]])

sympy.crypto.crypto.rsa_public_key(p, q, e)

The RSA public key is the pair \((n,e)\), where \(n\) is a product of two primes and \(e\) is relatively prime to the Euler totient \(\phi(n)\).

Examples

>>> from sympy.crypto.crypto import rsa_public_key
>>> p, q, e = 3, 5, 7
>>> n, e = rsa_public_key(p, q, e)
>>> n
15
>>> e
7

sympy.crypto.crypto.rsa_private_key(p, q, e)

The RSA private key is the pair \((n,d)\), where \(n\) is a product of two primes and \(d\) is the inverse of \(e\) (mod \(\phi(n)\)).

Examples

>>> from sympy.crypto.crypto import rsa_private_key
>>> p, q, e = 3, 5, 7
>>> rsa_private_key(p, q, e)
(15, 7)

sympy.crypto.crypto.encipher_rsa(pt, puk)

In RSA, a message \(m\) is encrypted by computing \(m^e\) (mod \(n\)), where puk is the public key \((n,e)\).

Examples

>>> from sympy.crypto.crypto import encipher_rsa, rsa_public_key
>>> p, q, e = 3, 5, 7
>>> puk = rsa_public_key(p, q, e)
>>> pt = 12
>>> encipher_rsa(pt, puk)
3

sympy.crypto.crypto.decipher_rsa(ct, prk)

In RSA, a ciphertext \(c\) is decrypted by computing \(c^d\) (mod \(n\)), where prk is the private key \((n, d)\).

Examples

>>> from sympy.crypto.crypto import decipher_rsa, rsa_private_key
>>> p, q, e = 3, 5, 7
>>> prk = rsa_private_key(p, q, e)
>>> ct = 3
>>> decipher_rsa(ct, prk)
12

sympy.crypto.crypto.kid_rsa_public_key(a, b, A, B)

Kid RSA is a version of RSA useful to teach grade school children since it does not involve exponentiation.

Alice wants to talk to Bob. Bob generates keys as follows. Key generation:

• Select positive integers \(a, b, A, B\) at random.
• Compute \(M = a b - 1\), \(e = A M + a\), \(d = B M + b\), \(n = (e d - 1) /M\).
• The public key is \((n, e)\). Bob sends these to Alice.
• The private key is \(d\), which Bob keeps secret.

Encryption: If \(m\) is the plaintext message then the ciphertext is \(c = m e \pmod n\).

Decryption: If \(c\) is the ciphertext message then the plaintext is \(m = c d \pmod n\).

Examples

>>> from sympy.crypto.crypto import kid_rsa_public_key
>>> a, b, A, B = 3, 4, 5, 6
>>> kid_rsa_public_key(a, b, A, B)
(369, 58)

sympy.crypto.crypto.kid_rsa_private_key(a, b, A, B)

Compute \(M = a b - 1\), \(e = A M + a\), \(d = B M + b\), \(n = (e d - 1) / M\). The private key is \(d\), which Bob keeps secret.

Examples

>>> from sympy.crypto.crypto import kid_rsa_private_key
>>> a, b, A, B = 3, 4, 5, 6
>>> kid_rsa_private_key(a, b, A, B)
(369, 70)

sympy.crypto.crypto.encipher_kid_rsa(pt, puk)

Here pt is the plaintext and puk is the public key.

Examples

>>> from sympy.crypto.crypto import encipher_kid_rsa, kid_rsa_public_key
>>> pt = 200
>>> a, b, A, B = 3, 4, 5, 6
>>> pk = kid_rsa_public_key(a, b, A, B)
>>> encipher_kid_rsa(pt, pk)
161

sympy.crypto.crypto.decipher_kid_rsa(ct, prk)

Here pt is the plaintext and prk is the private key.

Examples

>>> from sympy.crypto.crypto import kid_rsa_public_key, kid_rsa_private_key, decipher_kid_rsa, encipher_kid_rsa
>>> a, b, A, B = 3, 4, 5, 6
>>> d = kid_rsa_private_key(a, b, A, B)
>>> pt = 200
>>> pk = kid_rsa_public_key(a, b, A, B)
>>> prk = kid_rsa_private_key(a, b, A, B)
>>> ct = encipher_kid_rsa(pt, pk)
>>> decipher_kid_rsa(ct, prk)
200

sympy.crypto.crypto.encode_morse(pt)

Encodes a plaintext into popular Morse Code with letters separated by “|” and words by “||”.

References

[R32]

http://en.wikipedia.org/wiki/Morse_code

Examples

>>> from sympy.crypto.crypto import encode_morse
>>> pt = 'ATTACK THE RIGHT FLANK'
>>> encode_morse(pt)
'.-|-|-|.-|-.-.|-.-||-|....|.||.-.|..|--.|....|-||..-.|.-..|.-|-.|-.-'

sympy.crypto.crypto.decode_morse(mc)

Decodes a Morse Code with letters separated by “|” and words by “||” into plaintext.

References

[R33]

http://en.wikipedia.org/wiki/Morse_code

Examples

>>> from sympy.crypto.crypto import decode_morse
>>> mc = '--|---|...-|.||.|.-|...|-'
>>> decode_morse(mc)
'MOVE EAST'

sympy.crypto.crypto.lfsr_sequence(key, fill, n)

This function creates an lfsr sequence.

INPUT:

key: a list of finite field elements,

\([c_0, c_1, \ldots, c_k].\)

fill: the list of the initial terms of the lfsr

sequence, \([x_0, x_1, \ldots, x_k].\)

n: number of terms of the sequence that the

function returns.

OUTPUT:

The lfsr sequence defined by \(x_{n+1} = c_k x_n + \ldots + c_0 x_{n-k}\), for \(n \leq k\).

Notes

S. Golomb [G33] gives a list of three statistical properties a sequence of numbers \(a = \{a_n\}_{n=1}^\infty\), \(a_n \in \{0,1\}\), should display to be considered “random”. Define the autocorrelation of \(a\) to be

\[C(k) = C(k,a) = \lim_{N\rightarrow \infty} {1\over N}\sum_{n=1}^N (-1)^{a_n + a_{n+k}}.\]

In the case where \(a\) is periodic with period \(P\) then this reduces to

\[C(k) = {1\over P}\sum_{n=1}^P (-1)^{a_n + a_{n+k}}.\]

Assume \(a\) is periodic with period \(P\).

• balance:

  \[\left|\sum_{n=1}^P(-1)^{a_n}\right| \leq 1.\]

• low autocorrelation:

  \[\begin{split}C(k) = \left\{ \begin{array}{cc} 1,& k = 0,\\ \epsilon, & k \ne 0. \end{array} \right.\end{split}\]

  (For sequences satisfying these first two properties, it is known that \(\epsilon = -1/P\) must hold.)

• proportional runs property: In each period, half the runs have length \(1\), one-fourth have length \(2\), etc. Moreover, there are as many runs of \(1\)‘s as there are of \(0\)‘s.

References

[G33]

(1, 2) Solomon Golomb, Shift register sequences, Aegean Park Press, Laguna Hills, Ca, 1967

Examples

>>> from sympy.crypto.crypto import lfsr_sequence
>>> from sympy.polys.domains import FF
>>> F = FF(2)
>>> fill = [F(1), F(1), F(0), F(1)]
>>> key = [F(1), F(0), F(0), F(1)]
>>> lfsr_sequence(key, fill, 10)
[1 mod 2, 1 mod 2, 0 mod 2, 1 mod 2, 0 mod 2, 1 mod 2, 1 mod 2, 0 mod 2, 0 mod 2, 1 mod 2]

sympy.crypto.crypto.lfsr_autocorrelation(L, P, k)

This function computes the lsfr autocorrelation function.

INPUT:

L: is a periodic sequence of elements of \(GF(2)\). L must have length larger than P.

P: the period of L

k: an integer (\(0 < k < p\))

OUTPUT:

the k-th value of the autocorrelation of the LFSR L

Examples

>>> from sympy.crypto.crypto import lfsr_sequence, lfsr_autocorrelation
>>> from sympy.polys.domains import FF
>>> F = FF(2)
>>> fill = [F(1), F(1), F(0), F(1)]
>>> key = [F(1), F(0), F(0), F(1)]
>>> s = lfsr_sequence(key, fill, 20)
>>> lfsr_autocorrelation(s, 15, 7)
-1/15
>>> lfsr_autocorrelation(s, 15, 0)
1

sympy.crypto.crypto.lfsr_connection_polynomial(s)

This function computes the lsfr connection polynomial.

INPUT:

s: a sequence of elements of even length, with entries in a finite field

OUTPUT:

C(x): the connection polynomial of a minimal LFSR yielding s.

This implements the algorithm in section 3 of J. L. Massey’s article [M34].

References

[M34]

(1, 2) James L. Massey, “Shift-Register Synthesis and BCH Decoding.” IEEE Trans. on Information Theory, vol. 15(1), pp. 122-127, Jan 1969.

Examples

>>> from sympy.crypto.crypto import lfsr_sequence, lfsr_connection_polynomial
>>> from sympy.polys.domains import FF
>>> F = FF(2)
>>> fill = [F(1), F(1), F(0), F(1)]
>>> key = [F(1), F(0), F(0), F(1)]
>>> s = lfsr_sequence(key, fill, 20)
>>> lfsr_connection_polynomial(s)
x**4 + x + 1
>>> fill = [F(1), F(0), F(0), F(1)]
>>> key = [F(1), F(1), F(0), F(1)]
>>> s = lfsr_sequence(key, fill, 20)
>>> lfsr_connection_polynomial(s)
x**3 + 1
>>> fill = [F(1), F(0), F(1)]
>>> key = [F(1), F(1), F(0)]
>>> s = lfsr_sequence(key, fill, 20)
>>> lfsr_connection_polynomial(s)
x**3 + x**2 + 1
>>> fill = [F(1), F(0), F(1)]
>>> key = [F(1), F(0), F(1)]
>>> s = lfsr_sequence(key, fill, 20)
>>> lfsr_connection_polynomial(s)
x**3 + x + 1

sympy.crypto.crypto.elgamal_public_key(prk)

Return three number tuple as public key.

Parameters:prk : Tuple (p, r, e) generated by elgamal_private_key Returns:(p, r, e = r**d mod p) : d is a random number in private key.

Examples

>>> from sympy.crypto.crypto import elgamal_public_key
>>> elgamal_public_key((1031, 14, 636))
(1031, 14, 212)

sympy.crypto.crypto.elgamal_private_key(digit=10)

Return three number tuple as private key.

Elgamal encryption is based on mathmatical problem Discrete Logarithm Problem (DLP). For example,

\(a^{b} \equiv c \pmod p\)

In general, if a and b are known, c is easily calculated. If b is unknown, it is hard to use a and c to get b.

Parameters:digit : Key length in binary Returns:(p, r, d) : p = prime number, r = primitive root, d = random number

Examples

>>> from sympy.crypto.crypto import elgamal_private_key
>>> from sympy.ntheory import is_primitive_root, isprime
>>> a, b, _ = elgamal_private_key()
>>> isprime(a)
True
>>> is_primitive_root(b, a)
True

sympy.crypto.crypto.encipher_elgamal(m, puk)

Encrypt message with public key

m is plain text message in int. puk is public key (p, r, e). In order to encrypt a message, random a number a between 2 and p, encryped message is \(c_{1}\) and \(c_{2}\)

\(c_{1} \equiv r^{a} \pmod p\)

\(c_{2} \equiv m e^{a} \pmod p\)

Parameters:

m : int of encoded message

puk : public key

Returns:

(c1, c2) : Encipher into two number

Examples

>>> from sympy.crypto.crypto import encipher_elgamal
>>> encipher_elgamal(100, (1031, 14, 212))     
(835, 271)

sympy.crypto.crypto.decipher_elgamal(ct, prk)

Decrypt message with private key

\(ct = (c_{1}, c_{2})\)

\(prk = (p, r, d)\)

According to extended Eucliden theorem, \(u c_{1}^{d} + p n = 1\)

\(u \equiv 1/{{c_{1}}^d} \pmod p\)

\(u c_{2} \equiv \frac{1}{c_{1}^d} c_{2} \equiv \frac{1}{r^{ad}} c_{2} \pmod p\)

\(\frac{1}{r^{ad}} m e^a \equiv \frac{1}{r^{ad}} m {r^{d a}} \equiv m \pmod p\)

Examples

>>> from sympy.crypto.crypto import decipher_elgamal
>>> decipher_elgamal((835, 271), (1031, 14, 636))
100