The Vigenère cipher and Sage

Posted on by

The Vigenère cipher is named after Blaise de Vigenère, a sixteenth century diplomat and cryptographer, by a historical accident. Vigene`re actually invented a different and more complicated cipher. The so-called “Vigenère cipher” cipher was actually invented by Giovan Batista Belaso in 1553. In any case, it is this cipher which we shall discuss here first.

This cipher has been re-invented by several authors, such as author and mathematician Charles Lutwidge Dodgson (Lewis Carroll) who claimed his 1868 “The Alphabet Cipher” was unbreakable. Several others claimed the so-called Vigenère cipher was unbreakable (e.g., the Scientific American magazine in 1917). However, Friedrich Kasiski and Charles Babbage broke the cipher in the 1800’s [1]. 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 Vigenère cipher (now on display in the NSA Museum in Fort Meade) [1].

The so-called Vigenère cipher is a generalization of the Cesaer shift cipher. Whereas the shift cipher shifts each letter by the same amount (that amount being the key of the shift cipher) the so-called Vigenère 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 Vigenère cipher is actually a shift cipher with a shift of 2 (since “C” is the 2-nd 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 Vigenère cipher will shift letters in even positions by 2 and letters in odd positions are left alone (or shifted by 0, since “A” is the 0-th letter, if you start counting at 0).

REFERENCES:
[1] Wikipedia article on the Vigenere cipher.

Using Sage, let’s look at a message (a chant at football games between rivals USNA and West Point):

sage: AS = AlphabeticStrings()           
sage: A = AS.alphabet()
sage: VC = VigenereCryptosystem(AS, 1) # sets the key length to be = 1
sage: m = VC.encoding("Beat Army!"); m  # trivial example
BEATARMY

Now, we choose for illustration a simple key of length 1, and encipher this message:

sage: key = AS("D")
sage: c = VC.enciphering(key, m)
sage: c  # a trivial example
EHDWDUPB

You see here that in this case the cipher boils down to the Caesar/shift cipher (shifting by 3).

Deciphering is easy:

sage: VC.deciphering(key, c)
BEATARMY

Next, we choose for illustration a simple key of length 2, and encipher the same message:

sage: VC = VigenereCryptosystem(AS, 2)
sage: key = AS("CA")
sage: m = VC.encoding("Beat Army!"); m
BEATARMY
sage: c = VC.enciphering(key, m); c
DECTCROY

Since one of the key letters is “A” (which shifts by 0), half the plaintext is unchanged in going to the ciphertext.

Here is the algorithmic description of the above (so-called) Vigenère cipher:

    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)

  Identify the alphabet A, ..., Z with the integers 0, ..., 25. 
    Step 1: Compute from the string key a list L1 of corresponding
            integers. Let n1 = len(L1).
    Step 2: Compute from the string m a list L2 of corresponding
            integers. Let n2 = len(L2).
    Step 3: Break L2 up sequencially into sublists of size n1, and one sublist
            at the end of size <=n1. 
    Step 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.
    Step 5: Assemble these lists C by concatenation into a new list of length n2.
    Step 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“, or the “Kasiski attack” (although it was first discovered by Charles Babbage).

The cipher Vigenère 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)

  Identify the alphabet A, ..., Z with the integers 0, ..., 25. 
    Step 1: Compute from the string m a list L2 of corresponding
            integers. Let n2 = len(L2). 
    Step 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).
    Step 3: Compute a new list C given by C[i] = L1[i]+L2[i] (mod 26), for each i.
            Note n2 = len(C).
    Step 5: Compute from the new list a string c of corresponding letters.

Note how the key is mixed with the plaintext to create the enciphering of the plaintext to ciphertext in Steps 2 and 3.

A screencast describing this has been posted to vimeo.

Michael Reid’s Happy New Year Puzzle, 2012

Posted on by

Here is another puzzle from Michael Reid on NOBNET. (Michael also notes that if you find a solution (a,b,c,d,e,f) then (d,e,f,a,b,c) is another solution.)

Puzzle: Replace a, b, c, d, e, f with the first six prime numbers, in some order, to make the expression a\cdot b^c + d \cdot e^f equal to the New Year.

Best wishes for a happy, healthy and prosperous New Year!

Bifid cipher and Sage

Posted on by

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×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×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.

The Bifid cipher was discusses in Alasdair McAndrew’s book on Cryptography and Sage. We shall follow his discussion. As an example of a Polybius square for the Bifid cipher, pick the key to be “encrypt” (as Alasdair does). In that case, the Polybius square is \left(\begin{array}{rrrrr} E & N & C & R & Y \\ P & T & A & B & C \\ D & E & F & G & H \\ I & K & L & M & N \\ O & P & Q & R & S \end{array}\right). BTW, the 6\times 6 analog is: \left(\begin{array}{rrrrrr} E & N & C & R & Y & P \\ T & 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 & 0 & 1 & 2 \end{array}\right).

Here is Sage code to produce the 6\times 6 case (the 5\times 5 case is in Alasdair’s book):

def bifid(pt, key):
    """
    INPUT:
        pt - plaintext string      (digits okay)
        key - short string for key (no repetitions, digits okay)
    
    OUTPUT:
        ciphertext from Bifid cipher (all caps, no spaces)

    This is the version of the Bifid cipher that uses the 6x6
    Polybius square.

    AUTHOR:
        Alasdair McAndrew

    EXAMPLES:
        sage: key = "encrypt"
        sage: pt = "meet me on monday at 8am"
        sage: bifid(pt, key)
        [[2, 5], [0, 0], [0, 0], [1, 0], [2, 5], [0, 0], [3, 0], 
         [0, 1], [2, 5], [3, 0], [0, 1], [1, 3], [1, 1], [0, 4], 
         [1, 1], [1, 0], [5, 4], [1, 1], [2, 5]]
        'HNHOKNTA5MEPEGNQZYG'

    """
    AS = AlphabeticStrings()
    A = list(AS.alphabet())+[str(x) for x in range(10)]
    # first make sure the letters are capitalized
    # and text has no spaces
    key0 = [x.capitalize() for x in key if not(x.isspace())]
    pt0 = [x.capitalize() for x in pt if not(x.isspace())]
    # create long key
    long_key = key0+[x for x in A if not(x in key0)]
    n = len(pt0)
    # the fractionalization
    pairs = [[long_key.index(x)//6, long_key.index(x)%6] for x in pt0]
    print pairs
    tmp_cipher = flatten([x[0] for x in pairs]+[x[1] for x in pairs])
    ct = join([long_key[6*tmp_cipher[2*i]+tmp_cipher[2*i+1]] for i in range(n)], sep="")
    return ct

def bifid_square(key):
    """
    Produced the Polybius square for the 6x6 Bifid cipher.

    EXAMPLE:
        sage: key = "encrypt"
        sage: bifid_square(key)
        [E N C R Y P]
        [T 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 0 1 2]

    """
    AS = AlphabeticStrings()
    A = list(AS.alphabet())+[str(x) for x in range(10)]
    # first make sure the letters are capitalized
    # and text has no spaces
    key0 = [SR(x.capitalize()) for x in key if not(x.isspace())]
    # create long key
    long_key = key0+[SR(x) for x in A if not(x in key0)]
    # the fractionalization
    pairs = [[long_key.index(SR(x))//6, long_key.index(SR(x))%6] for x in A]
    f = lambda i,j: long_key[6*i+j] 
    M = matrix(SR, 6, 6, f)
    return M

Have fun!

Michael Reid’s Digit operation puzzles

Posted on by

Michael Reid (http://www.math.ucf.edu/~reid/index.html) posted these questions on Nobnet recently. I’m reposting them here.

Consider two rules for modifying a positive integer:

i) replace a substring of its digits by the square of the number represented by the substring
ii) if a substring is a perfect cube, replace the substring by its cube root

Neither the substring being replaced, nor the string replacing it may have leading zeroes.

For example, starting with 123, we may square `23′ to obtain 1529. Then we can square `29′ to get 15841, then square `5′ to get 125841, and then we could take the cube root of `125′ to get 5841, and so on.

What is the smallest number we can obtain from the number 2011 with a sequence of these operations?

Now suppose the two operations are instead

iii) replace a substring by its cube
iv) replace a substring which is a square by its square root

What is the smallest number we can get with these operations if we start from 2011?

Here is another “digit operations” puzzle that I hope you will find a nice challenge.

Consider two rules for modifying a positive integer:

i) replace a substring of its digits by 7 times the number represented by the substring
ii) if a substring is a perfect 7th power, replace the substring by its 7th root

Neither the substring being replaced, nor the string replacing it may have leading zeroes.

For example, starting with 347, we may replace the substring `34′ by `238′ (multiplying by 7) to obtain 2387. Then we can multiply the substring `3′ to get 22187. Now we can take the 7th root of `2187′ to get 23, and so on.

What is the smallest number we can obtain from the number 2011 with a sequence of these operations?

Now suppose the two operations are instead

iii) if a substring is divisible by 7, we may divide the substring by 7
iv) replace a substring by its 7th power

(which are the reverses of operations i) and ii) above).

What is the smallest number we can get with these operations if we start from 2011?

Differential equations and crime

Posted on by

A group of mathematicians in Los Angeles have developed, in a series of papers, a systems of two partial differential equations, in time and space coordinates, which describe the risk of a criminal attack. Andrea Bertozzi, director of the Computational and Applied Math group in the UCLA Math Dept, has co-arthored many papers on the subject.

An introduction is at The Mathematics of Clumpy Crime.

Review of “Introduction to Cryptography with Open-source Software” by Alasdair McAndrew

Posted on by

Again, a disclaimer: I got this book free and I know (by numerous emails over the years), the author of this text. Second, this book was also helped by Minh Van Nyuyen who I also know (by email); Minh was a student of McAndrew when the book was being written. If memory serves, I first emailed the author after reading his fine book Introduction to Digital Image Processing with MATLAB, hoping someone would write a corresponding book using Sage or Octave. That never happened, but this book did, and students of cryptography, old and young, will be grateful for it.

This is a well-written book on cryptography, suitable as a textbook for an undergraduate or graduate course in the topic. It is also useful for someone who just wants a reference book on how to do cryptographic computations in Sage. (Sage is a free and open-source mathematical software system, available from http://www.sagemath.org.)Each chapter has an extensive set of exercises, as well as a glossary. The exercises are broken into four groups: Review Exercises, Beginning Exercises, Sage Exercises, and Further (or more advanced) Exercises. The text tries to be self-contained, with definitions and key ideas illustrated with examples, many of which are supported by corresponding Sage commands.

The chapters will be briefly summarized next.

The first chapter, Introduction to Cryptography, sketches basic ideas such as confidentiality, various types of attacks, cryptographic protocols, and computer security. Some simple ciphers are given as examples.

Basic Number Theory is chapter 2. It covers some basic mathematical definitions in elementary number theory, talks about some of the commonly used computations such as the Euclidean algorithm and modular exponentiation.
Also, primality testing is covered.

Chapter 3 is Classical Cryptosystems. This covers the Caesar cipher, the Vigenère cipher, the one-time pad, and several permutation ciphers and matrix ciphers.

The fourth chapter, Introduction to Information Theory, introduces entropy and uncertainty, and illustrates the notions by estimating the entropy of typical English language text.

Chapter 5, Public-Key Cryptosystems Based on Factoring, covers the RSA cryptosystem, Rabin’s cryptosystem and ends with a discussion on the Pollard rho method of factoring large integers.

Public-Key Cryptosystems Based on Logarithms and Knapsacks, the sixth chapter, covers the discrete logarithm problem, El Gamal’s cryptosystem, the Diffie-Hellman key exchange, and Knapsack cryptosystems.

Chapter 7, Digital Signatures, talks about the RSA signature scheme, Rabin digital signatures, and the El Gamal digital signature scheme.

The eighth chapter, Block Ciphers and the Data Encryption Standard, discusses Block ciphers, DES, and Feistel ciphers.

Chapter 9 is a review of finite fields.

The Advanced Encryption Standard is chapter 10. This chapter covers both the usual AES but also a simplified Rijndael cipher. Both of these are implemented in Sage and Sage examples illiustrate the computations.

Chapter 11 is on Hash Functions. Their security, construction, and uses are discussed.

Chapter 12 is on Elliptic Curve Cryptosystems.About half the chapter sketches background on elliptic curves. This is a very technical topic, but one which Sage has a great deal of computational functionality implemented. The rest of the chapter covers elliptic curve cryptosystems, elliptic curve signature schemes, and related topics.

Random Numbers and Stream Ciphers is chapter 13. It covers such topics as pseudo-random number generators, Stream ciphers, RC4, and the Blum-Goldwasser cryptosystem.

The last chapter is Advanced Applications and Protocols. It covers topics such as zero knowledge proofs,
digital cash and voting protocols.

There are two appendices: one is an introduction to the mathematical software system Sage and the other summarizes some more advanced aspects of computational number theory. The book also has a good index.

Review of “Sage: beginner’s guide” by Craig Finch

Posted on by

Title: Sage – beginner’s guide
Sage: beginner's guide

Author: Craig Finch

Technical Reviewers: Dr David Kirkby and Minh Nyugen.

Publisher: Packt Publishing, Open Source series

Review

Complete disclosure: I received this book for free from the publisher, with only the promise to put a review on this blog. Also, I have worked with one of the book’s reviewers (Minh) on a few projects. However, I didn’t receive any other renumeration, don’t know the author of the text under review, and no one asked to pre-approve this review.

The book under review is a book on Sage, an open source mathematical software package started by William Stein, a mathematician at the University of Washington. It is very carefully written (either that, or very carefully reviewed by the Technical Reviewers!) and aimed, as the title suggests, at the beginner. However, it is assumed that the reader knows some undergraduate mathematics, say the level one obtains from getting an engineering degree. In fact, it has a bit of an applied slant with many examples from physics and engineering mathematics. This is a welcome contrast to the excellent Sage Tutorial (available free from the Sage website, http://www.sagemath.org) which has a more of a pure slant. It’s nice to see a publisher like Packt Publishing take the risk of publishing a book like this on an open source software program which already has free documentation (in pdf form).

There are 10 chapters and it’s about 350 pages. Although Sage of course has color plotting, all figures in this book are in black and white, so the reader really must try out the Sage code given in the book to get the full effect. Each chapter features many Time for action Sage code examples (also conveniently listed in the table of contents at the front of the book), followed by a What just happened? section explaining in detail (and without computer code) what the example did. These make the book more useful to the beginner as well as for someone wanting a quick reference for one of the examples. All these examples use the command-line version of Sage (typing your commands into a terminal window at a sage: prompt) but there are several sections explaining the GUI version of Sage (typing your commands into a Mathematica-like “notebook cell”) as well.

Here is a chapter-by-chapter summary:

The first chapter, What can you do with Sage?, is a survey of some of Sage‘s most commonly used capabilities. Examples such as solving a differential equations, plotting experimental data, and some simple example matrix computations are presented.

The second chapter is Installing Sage. This covers the steps you go though for a Mac OS, Windows, and Linux installation of Sage. Since this is scary for a number of users who are not very computer-savvy, it is nice an entire chapter is devoted to this.

The third chapter, Getting started with Sage, introduces the new Sage user to the user interface, basic Sage syntax, user-defined functions, and some of the available data types (such as strings and real number types). For example, the (black and white version of the) Sage plot of the sinc function,

     sage: f(x) = sin(x)/x
     sage: plot(f, x, xmin=-15, xmax = 15, thickness=2, color="red", legend_label="sinc")

is discussed, among many other things.


This motivates a more detailed introduction to Python, given in the next chapter.

Introducing Python and Sage, the fourth chapter, introduces syntax for Python lists, dictionaries, for loops, if-then statements, and also reading and writing to files. Sage is based on Python, a popular language used extensively in industry (at google among other places). This chapter introduces some very useful stuff, but is pretty basic if you know Python already.

The 5th chapter is Vectors, matrices and linear algebra, and you can guess what it is about. Sage has very wide functionality in linear algebra, with specialized packages for numerical computations for real and complex matrices, matrices over a finite field, or matrices having symbolic coefficients, such as functions of a variable x.

Sage‘s functionality in two-dimensional and three-dimensional plotting is described in the 6th chapter, Plotting with Sage. There is 3-d “live-view” (i.e., you can use the mouse to rotate a plot of a surface or solid in 3-space), histogram plots, as well as simpler plots using Sage‘s 2-d plotting package, matplotlib.

Chapter 7 is Making symbolic mathematics easy. Various topics are covered, from various calculus operations, such as limits, derivatives, integrals, and Laplace transforms, to exact
solutions to equations with variable coefficients, to infinite sums such as power series, to solving ordinary differential equations.

Solving problems numerically is the next chapter. This is the meat-and-potatoes for an applied mathematician. Sage includes many packages which have been developed to solve optimization problems, linear programming problems, numerical solutions of ordinary differential equations, numerical integration, and probability and statistics. These are introduced briefly in this chapter.

The 9th chapter is Learning advanced python programming. Here object-oriented programming is introduced by means of examples, and it is shown how Python handles errors and imports.

The last chapter Where to go from here discusses selected miscellaneous advanced topics.
Topics covered include: LaTeX, interactive plotting using the Sage notebook, as well as a fairly detailed example of analyzing colliding spheres in Sage from several different approaches.

The book has a very good index and, overall I believe is a very welcomed addition to the literature of Sage books.

Zombies and Mathematics

Posted on by

What do you do if there is a Zombie attack? Can mathematics help? This post is (humorously) dedicated to collecting links to papers or blog posted related to the mathematical models of Zombies.

George Romero‘s 1968 Night of the Living Dead, now in the public domain, introduced reanimated ghouls, otherwise known as zombies, which craved live human flesh. Romero’s script was insired on Richard Matheson’s I Am Legend. In Romero’s version, the zombies could be killed by destroying the zombie’s brain. A dead human could, in some cases be “reanimated,” turning into a zombie. These conditions are modeled mathematically in several papers, given below.

Public domain 1968 film Night of the Living Dead by George Romero.

God’s number for the Rubik’s cube in the face turn metric

Posted on by

This is an update to the older post.

The story is described well at cube20.org but the bottom line is that Tom Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge have established that every cube position can be solved in 20 face moves or less. The superflip is known to take 20 moves exactly (in 1995, Michael Reid established this), so 20 is best possible – or God’s number in the face turn algorithm. Google (and, earlier, Sony) contributed computer resources to do the needed massive computations. Congradulations to everyone who worked on this!

This would make a great documentary I think!