Archive

Archive for the ‘cryptography’ Category

Challenge your cryptology skills

25 December 2010 1 comment

In science, mathematics, and informatics there are various problem solving competitions aimed at challenging and expanding the talents of high school students. In the biological science, we have the International Biology Olympiad, in mathematics the International Mathematical Olympiad, and in informatics the International Olympiad in Informatics and the Internet Problem Solving Contest.

But cryptology is very much at the intersection of mathematics and informatics. There are some famous competitions in cryptology such as the National Institute of Standards and Technology (NIST) call in 1997 for a new encryption standard, a challenge that was met in late 2001 with the adoption of the Rijndael cipher as the Advanced Encryption Standard (AES) to replace the aging Data Encryption Standard (DES). The latest cryptology competition from NIST is a call for a new hash algorithm, called the Cryptographic Hash Algorithm Competition. As of this writing, the competition is in its third round of selection of a new hash algorithm.

The latter two competitions are oddly out of place for high school students. What comes close to a cryptology challenge for high school students is a competition I very recently learned about: the Crypto Challenge Contest. The contest is not really designed exclusively for high school students. You can find cryptology challenges suitable for high school students and up to cryptology researchers. However, many of the problems in Level I of the Crypto Challenge Contest are suitable for high school students. For those students who love a programming challenge, you might want to have a go at the problems in Level II. Happy problem solving.

Advertisements

Converting from binary to integer

26 October 2010 1 comment

The following is an updated and edited version of my posts to this sage-support thread.

Problem

You have a bitstring as output by

sage.crypto.stream.blum_blum_shub

and you want to convert that bitstring to an integer. Or in general, you want to convert a bit vector to its integer representation.

Solution

Here are two ways, assuming that you want the bits in little-endian order, i.e. you read the bits from right to left in increasing order of powers of 2.

sage: version()
'Sage Version 4.5.3, Release Date: 2010-09-04'
sage: from sage.crypto.stream import blum_blum_shub
sage: b = blum_blum_shub(length=6, lbound=10**4, ubound=10**5); b
100110
sage: type(b)
<class 'sage.monoids.string_monoid_element.StringMonoidElement'>
sage: # read in little-endian order
sage: # conversion using Python's built-in int()
sage: int(str(b), base=2)
38
sage: # conversion using Sage's built-in Integer()
sage: Integer(str(b), base=2)
38

Now assume you read the bitstring as output by blum_blum_shub in big-endian order, i.e. from left to right in increasing order of powers of 2. You simply convert the bitstring to a string, reverse that string, and apply any of the above two methods.

sage: # reversing a string
sage: str(b)
'100110'
sage: str(b)[::-1]
'011001'
sage: # read in big-endian order
sage: int(str(b)[::-1], base=2)
25
sage: Integer(str(b)[::-1], base=2)
25

Or you can do as follows:

sage: b = "100110"
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b))
25
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b[::-1]))
38

Another way is to use Horner’s method. Here’s a Sage function that computes the integer representation of a bit vector read using big-endian order. A usage example is also shown.

sage: def horner(A, x0):
...       # Evaluate the polynomial P(x) at x = x_0.
...       #
...       # INPUT
...       #
...       # - A -- list of coefficients of P where A[i] is the coefficient of
...       #   x_i.
...       # - x0 -- the value x_0 at which to evaluate P(x).
...       #
...       # OUTPUT
...       #
...       # An evaluation of P(x) using Horner's method.
...       i = len(A) - 1
...       b = A[i]
...       i -= 1
...       while i >= 0:
...           b = b*x0 + A[i]
...           i -= 1
...       return b
sage: A = [1, 0, 0, 1, 1, 0]
sage: horner(A, 2)
25

As an exercise, modify the function horner to output the integer representation of a bit vector that is read using little-endian order.

Number theory & RSA public key cryptography

14 October 2010 Leave a comment

I have released version 1.1 of the Sage tutorial “Number theory and the RSA public key cryptosystem”. There is little change in terms of content. However, note that I now use the GNU Free Documentation License v1.3+ for the tutorial. Here are the relevant files you can download for your reading pleasure.

All versions of the tutorial are available from the download page on its website. For the adventurous of heart, I have also made the full \LaTeX source of the document available.

The tutorial is meant to be educational. I don’t pretend that it is complete in any way. Any suggestions and/or criticisms for improving the tutorial are more than welcome. Enjoy and happy Sage’ing.

Version 0.4 of book “Sage for High School” released

31 July 2010 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.

Hill cipher in Sage

2 June 2010 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

Blum-Goldwasser probabilistic encryption

24 February 2010 1 comment

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

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:

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

Journal of Craptology, volume 6 released

20 May 2009 Leave a comment

Are you studying or involved in cryptography? Looking for some fresh academic literature besides PHD Comics? Then look no further than volume 6 of the Journal of Craptology.

In this latest installment, M.P. Abramson and W.J. Layton detail an idea to delay any attack against a cryptographic algorithm. The idea is very simple and most if not all people involved in computing would have come across it. I’m talking about none other than patents (well, food and sleep come to my mind as well). First, if you’ve designed a really cool new hip cryptographic algorithm that you think beats the bit bucket out of all existing competing algorithms, then you can patent your algorithm. To collect royalties on your years of toil, you can license your patented algorithm to anyone or any organization who’s willing to fork over the cash. As an added protection, you can specify in the licensing terms that users are not allowed to cryptanalyze your algorithm. But if somehow an attack against your algorithm emerges in the literature, then you can implement that attack and apply for a patent claiming that the idea is now on how to recover lost keys. These brilliant ideas are just the tip of an iceberg. Abramson and Layton also suggest that you patent the method of patenting an attack against a cryptographic algorithm. For further details, refer to their paper On Repairing Broken Cryptographic Algorithms.

The paper How to Trivially Perform Identify Theft, and How to Prevent It by R.R. Martin shows in just one page how you can prevent identity theft against yourself. The two most famous people in the cryptology world are Alice and Bob. If your name happens to be either Alice or Bob, then you should definitely change it to something else. I suggest “Jane Doe” or “John Smith” as these names rarely, if ever, occur in cryptology.

D.A. Madore’s paper Perfect Localized Security of the Fourtytwofish Cipher in the Delphic Oracle Model talks about how to achieve a great measure of security with the Fourtytwofish cipher. The paper starts off with the venerable history of Fourtytwofish cipher, whose world-famous predecessors were the Blowfish and Twofish ciphers by Schneier. It then goes on to discuss in some details about security, with a particular focus on localized security, and then moving on to the notion of an oracle. The latter concept is a very powerful theoretical tool for cryptology, not least because it has recently demonstrated its prowess by subsuming (the) Sun. Some experts have speculated that the fish family of ciphers actually has its origin in Dr. Seuss’ classic cipher One Fish Two Fish Red Fish Blue Fish, which didn’t catch on because of the fiendishly long name.

Finally, J. Birkett discusses the problem of the travelling cryptographer. The author does so not by using arcane publication technologies like books or journal papers, but by distributing the research result via a (MeAnd)YouTube video. Known as the travelling cryptographers problem, it was believed to have been proposed as a method for travelling salesmen and women to solve the problem of wifi insecurity. This common computer and network security problem that travelling salespeople encounter is commonly referred to in the literature as the travelling salesman problem.

Categories: cryptography, humour Tags: ,