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.
Let’s first consider how Hill cipher encryption is commonly presented in introductory texts on cryptography or even Wikipedia. Let be a invertible matrix over and let be a matrix also over . We call the encryption key and is referred to as the plaintext. The ciphertext corresponding to is given by
Hill cipher encryption in Sage works differently from that presented above. If is the encryption matrix key and is the plaintext matrix, then the ciphertext is the matrix . Here, is still a square () matrix and is an matrix where the entries are filled from left to right, top to bottom. According to this scheme of encryption, with and as in (1) and (2), respectively, we get
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
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 least significant bits of a binary string. For example, given a positive integer , let be the binary representation of so that is a binary string of length . Then the least significant bit of is . If , then the least significant bits of are . 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)  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 is a private key, then is the corresponding public key. Furthermore, we have .
sage: p, q, a, b = prikey sage: pubkey == p * q True sage: gcd(p, q) == a*p + b*q == 1 True
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 has a Blum prime, the smallest such prime being 7. The interval 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