cryptography | mvngu

Version 0.4 of book “Sage for High School” released

31 July 2010 mvngu 1 comment

I’m happy to announce the release of version 0.4 of the book Sage for High School. My primary concern in this version was to flesh out the chapter “Vectors and Matrices”. The PDF and source tarball are available for download. The chapter outline is as follows:

Scalars and vectors
Add, subtract, and multiply vectors
Three-dimensional vectors
The dot product
Parallel and perpendicular vectors
Matrices and determinants
The cross product

Version 0.4 adds another section to the chapter “Number Theory”, called “Kid RSA”. This additional section explains a simplified version of the RSA cryptosystem, using number theoretic concepts introduced in the chapter “Number Theory”. The simplified cryptosystem is called “Kid RSA”, developed by Neal Koblitz. You can find Kid RSA in his book:

N. Koblitz. Algebraic Aspects of Cryptography. Springer, 1998.

Categories: cryptography, linear algebra, number theory, Sage Tags: book, cryptography, documentation, education, high school, linear algebra, mathematics, number theory, RSA, Sage, tutorial

Hill cipher in Sage

2 June 2010 mvngu 1 comment

Let’s first consider how Hill cipher encryption is commonly presented in introductory texts on cryptography or even Wikipedia. Let ${M}$ be a ${3 \times 3}$ invertible matrix over ${\mathbf{Z}_{26}}$ and let ${P}$ be a ${3 \times n}$ matrix also over ${\mathbf{Z}_{26}}$ . We call ${M}$ the encryption key and ${P}$ is referred to as the plaintext. The ciphertext ${C}$ corresponding to ${P}$ is given by

$\displaystyle C = MP \pmod{26}.$

According to this scheme of encryption, given

$\displaystyle M = \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{bmatrix} \ \ \ \ \ (1)$

and

$\displaystyle P = \begin{bmatrix} 0 \\ 2 \\ 19 \end{bmatrix} \ \ \ \ \ (2)$

then the ciphertext is

$\displaystyle C = \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{bmatrix} \begin{bmatrix} 0 \\ 2 \\ 19 \end{bmatrix} = \begin{bmatrix} 15 \\ 14 \\ 7 \end{bmatrix}.$

Hill cipher encryption in Sage works differently from that presented above. If ${M}$ is the encryption matrix key and ${P}$ is the plaintext matrix, then the ciphertext is the matrix ${PM}$ . Here, ${M}$ is still a square ( ${3 \times 3}$ ) matrix and ${P}$ is an ${n \times 3}$ matrix where the entries are filled from left to right, top to bottom. According to this scheme of encryption, with ${M}$ and ${P}$ as in (1) and (2), respectively, we get

$\displaystyle C = P^T M = \begin{bmatrix} 0 & 2 & 19 \end{bmatrix} \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{bmatrix} = \begin{bmatrix} 16 & 17 & 19 \end{bmatrix}.$

Or using Sage:

sage: version()
Sage Version 4.4.1, Release Date: 2010-05-02
sage: H = HillCryptosystem(AlphabeticStrings(), 3)
sage: M = Matrix(IntegerModRing(26), [[6,24,1], [13,16,10], [20,17,15]])
sage: P = H.encoding("ACT")
sage: H.enciphering(M, P)
QRT

Categories: cryptography, documentation, number theory, Sage, symbolic computation Tags: computer algebra system, cryptography, documentation, mathematics, open source software, primer, Sage, tutorial

Blum-Goldwasser probabilistic encryption

24 February 2010 mvngu 1 comment

Sage 4.3.3 merged an implementation of the Blum-Goldwasser probabilistic public-key encryption scheme described in the following paper:

M. Blum and S. Goldwasser. An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information. In Proceedings of CRYPTO 84 on Advances in Cryptology, pp. 289–299, Springer, 1985.

I wrote that implementation based on a public domain version by Mike Hogan and David Joyner. See ticket #7746 for background information. A big thank you to David Joyner for reviewing that ticket and many suggestions for improvement. The current implementation in Sage 4.3.3 follows the description of the Blum-Goldwasser scheme as described in the following book:

A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.

This implementation is documented in the Sage reference manual. In this post, I will provide some usage examples.

The Blum-Goldwasser encryption and decryption algorithms make use of the least significant bit of a binary string. A related concept is the $k$ least significant bits of a binary string. For example, given a positive integer $n$ , let $b = b_0 b_1 \cdots b_{m-1}$ be the binary representation of $n$ so that $b$ is a binary string of length $m$ . Then the least significant bit of $n$ is $b_{m-1}$ . If $0 < k \leq m$ , then the $k$ least significant bits of $n$ are $b_{m-1-k} b_{m-k} \cdots b_{m-1}$ . The least significant bit of an integer is also referred to as its parity bit, because this bit determines whether the integer is even or odd. In the following example, we obtain the least significant bit of an integer:

sage: from sage.crypto.util import least_significant_bits
sage: least_significant_bits(123, 1)
[1]
sage: least_significant_bits(123, 4)
[1, 0, 1, 1]

The following encryption/decryption example is taken from Example 8.57, pages 309–310 of (Menezes et al. 1996):

sage: from sage.crypto.public_key.blum_goldwasser import BlumGoldwasser
sage: bg = BlumGoldwasser(); bg
The Blum-Goldwasser public-key encryption scheme.
sage: p = 499; q = 547
sage: pubkey = bg.public_key(p, q); pubkey
272953
sage: prikey = bg.private_key(p, q); prikey
(499, 547, -57, 52)
sage: P = "10011100000100001100"
sage: C = bg.encrypt(P, pubkey, seed=159201); C
([[0, 0, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]], 139680)
sage: M = bg.decrypt(C, prikey); M
[[1, 0, 0, 1], [1, 1, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0], [1, 1, 0, 0]]
sage: M = "".join(map(lambda x: str(x), flatten(M))); M
'10011100000100001100'
sage: M == P
True

Now generate a pair of random public/private keys. Use the public key to encrypt a plaintext. Then decrypt the resulting ciphertext using the private key. Finally, compare the decrypted message with the original plaintext.

sage: from sage.crypto.public_key.blum_goldwasser import BlumGoldwasser
sage: from sage.crypto.util import bin_to_ascii
sage: bg = BlumGoldwasser()
sage: pubkey, prikey = bg.random_key(10**4, 10**6)
sage: P = "A fixed plaintext."
sage: C = bg.encrypt(P, pubkey)
sage: M = bg.decrypt(C, prikey)
sage: bin_to_ascii(flatten(M)) == P
True

If $(p, q, a, b)$ is a private key, then $n = pq$ is the corresponding public key. Furthermore, we have $\gcd(p, q) = ap + bq = 1$ .

sage: p, q, a, b = prikey
sage: pubkey == p * q
True
sage: gcd(p, q) == a*p + b*q == 1
True

The class BlumGoldwasser makes use of various utility functions from the new module util. Here, we compute the ASCII integers of some binary strings:

sage: from sage.crypto.util import ascii_integer
sage: bin = BinaryStrings()
sage: B = bin.encoding("A"); B
01000001
sage: ascii_integer(B)
65
sage: B = bin.encoding("C"); list(B)
[0, 1, 0, 0, 0, 0, 1, 1]
sage: ascii_integer(list(B))
67
sage: ascii_integer("01000100")
68
sage: ascii_integer([0, 1, 0, 0, 0, 1, 0, 1])
69

Compute the binary representation of some ASCII strings:

sage: from sage.crypto.util import ascii_to_bin
sage: ascii_to_bin("A")
01000001
sage: ascii_to_bin("Abc123")
010000010110001001100011001100010011001000110011

Convert some ASCII strings to their binary representations and recover the ASCII strings from the binary representations:

sage: from sage.crypto.util import ascii_to_bin
sage: from sage.crypto.util import bin_to_ascii
sage: A = "Abc"
sage: B = ascii_to_bin(A); B
010000010110001001100011
sage: bin_to_ascii(B)
'Abc'
sage: bin_to_ascii(B) == A
True
sage: A = "123 \" #"
sage: B = ascii_to_bin(A); B
00110001001100100011001100100000001000100010000000100011
sage: bin_to_ascii(B)
'123 " #'
sage: bin_to_ascii(B) == A
True

Testing for the presence of Blum primes within some closed intervals. The interval $[4, 100]$ has a Blum prime, the smallest such prime being 7. The interval $[24, 28]$ has no primes, hence no Blum primes.

sage: from sage.crypto.util import has_blum_prime
sage: from sage.crypto.util import is_blum_prime
sage: has_blum_prime(4, 100)
True
sage: for n in xrange(4, 100):
...       if is_blum_prime(n):
...           print n
...           break
...
7
sage: has_blum_prime(24, 28)
False

Choose a random prime and check that it is a Blum prime:

sage: from sage.crypto.util import random_blum_prime
sage: p = random_blum_prime(10**4, 10**5)
sage: is_prime(p)
True
sage: mod(p, 4) == 3
True

Categories: cryptography, documentation, Sage, symbolic computation Tags: Blum-Goldwasser cipher, cryptography, documentation, mathematics, programming, Python, Sage

Newer Entries Older Entries

mvngu

Archive

Version 0.4 of book “Sage for High School” released

Hill cipher in Sage

Blum-Goldwasser probabilistic encryption

Email Subscription

Blogroll

Categories

Archives

Follow “mvngu”