## Cryptography Quilt

### Mathematical Connections

## If you are at the exhibit…

#### The story

The quilt reminds us that mathematics is a deeply human endeavor. One side highlights the mathematics of cryptography; the other depicts drawings and doodles by seven women who made groundbreaking contributions to mathematics.

## Look closely; what do you see?

The cryptography quilt references different scenes in the installation. Can you find the quilt vignette that represents…

- the bakery?
- the knotical expedition?
- the lighthouse?
- the garden?
- the tortoise’s trek?

## Focus on… public key cryptography

Cryptography, the study of encoding and decoding messages, has a fundamental problem: if two people want to communicate using secure messages that only they can understand, they first have to agree on an encoding scheme. How can they create one if they do not already have a secure way to communicate?

The vignette with the chipmunk and squirrel illustrates one of the earliest solutions, called RSA. The chipmunk announces a “public key” that other animals can use to encode messages. However, decoding is only possible using the chipmunk’s secret “private key.”

The squirrel uses the public key to encrypt a message (a lotus, representing peace and calm). The scrambled message is sent to the chipmunk, who successfully decrypts it.

Cryptography or “secret writing” is an old concept. For several millenia at least, people have wanted to communicate messages to distant others in such a way that even if the message was intercepted, it would not be readable by the interceptors. To achieve this, they have used different forms of “encoding” information; would-be interceptors invented corresponding schemes to attempt to decode such encrypted messages. In most traditional schemes, it was essential for the sender and intended recipient to preserve the secret of how the message had been encoded — an interceptor who knew the encryption key would be able to decode the message. Even partial knowledge (for instance, knowing the decoded version for a few encrypted snippets) could be used to “break” a code, using mathematics and intensive computations, such as for Enigma in WWII. This changed in the 20th century, with the invention of public-key cryptosystems. These exploit that there are computations that are easy to carry out (by a small computer) but very hard (even using the best algorithms and most performant computers) to reverse-engineer — for instance, it is not hard to find 200-digit numbers that are prime, and to multiply two of those together. But given a 400-digit number, even if one knows it is the product of two 200-digit primes, it is much much harder to identify those original primes. Our modern society and its international financial transactions rely extensively on secure encryption provided by such public-key systems. Many of these now safely encoded transactions would no longer be secure (because reverse-engineering the computation would no longer be as hard) if (or when?) quantum computers become available; of course other mathematical schemes are already being designed for that era.

The Cryptography Quilt refers to “encoding” and “decoding” in many realms. The quilt itself is quite traditional in its construction, with a central motif surrounded by quilted blocks, organized around it. Working from the center outward, we have:

## Central Padlock

The padlock in the center of the quilt immediately grabs your attention and signals the theme of the quilt: secrecy

and security. The main fabric of the padlock is the same fabric used for the sashing, tying the whole quilt together

visually. All around the padlock are 0s and 1s: a binary code. Can you figure out what it says? As a hint, the binary code uses 8-bit ASCII encoding!

Surrounding the padlock and binary, there is another hidden message. The squares around the central padlock use color to denote 0, 1, and 2 for a ternary code. The ternary code makes use of the fact that with 3 digits, there are 27 possible ternary numbers–very close to the number of letters in the alphabet. Can you decipher this message?

#### Five Vignettes

The five blocks around the padlock each reference a different scene in the Mathemalchemy installation while still connecting to the theme of encoding messages.

## The Bakery Vignette

In this block, we’re given a recipe from Mandelbrot Bakery—a recipe for Mandelbrot (which literally translates to “almond bread”) of course! The recipe is given as a series of pictures, giving a visual way to convey the instructions.

## The Garden Vignette

This block illustrates the concept of public key cryptography, and RSA in particular. The shaded items are private information, but everything else in the speech bubbles is publicly stated for anyone to hear. Using the private information, most notably the factorization of *n* into primes, the chipmunk is able to decode the squirrel’s message. We decided to use the language of flowers for the message since this scene relates to the garden. We made the final design decision in early January, shortly after the riot at the Capitol, and chose the lotus blossom to represent calm and peace.

## The Knotical Vignette

In this block, the sailor is using semaphore flags to convey the letter “S” (for semaphore and sailor). Semaphore was used widely in the 19th century for communication between ships.

## The Lighthouse Vignette

Here the lighthouse is flashing a message in Morse code referencing

light and mathematics. Can you tell what it says?

## Tess’ Vignette

Tess’s story was the rst scene developed for the Mathemalchemy installation. In the quilt block representing her scene, we have her kite with a key dangling off it. This is a reference to a key that can unlock the central padlock, but also to the Benjamin Franklin kite and key experiment to explore electricity. With this electricity, Tess sparked the development of all the other scenes.

#### The Twenty Blocks

During fabrication of the quilt, the blocks were labeled A through T so we could easily reference the blocks even though we were working together across big distances. We start with Block A in the top left, and proceed clockwise around the quilt. These blocks were divided into four different levels of sophistication:

- Basic and universally recognized symbols 🗝
- Historical cryptography 🕊
- More complex cryptography 🕶
- Modern mathematical cryptography ❃

## Block A: Hamming Code 🕶

This block shows the “encoding” step of the Hamming code, an error correcting code. The idea behind error correcting codes is that the message may be corrupted in transmission, and the receiver will need to have a way of correcting what they receive to recover the original message. In this block, the person sending the message 0111 adds extra digits that will help the receiver make sure that they can figure out what the message was, even if a digit gets changed accidentally. For the decoding step, see Block K!

## Block B: Blockchain ❃

This block gives a stylistic representation of blockchain, the mathematics behind cryptocurrrencies such as bitcoin.

## Block C: Vigenère Cipher 🕶

Blaise de Vigenère is known as the originator of the polyalphabetic substitution, having written *Traicté des Chiffres*, in 1585 in which he catalogs cipher methods as well as giving a key to solving polyalphabetic ciphers. In the Vigenère cipher, you use several different shifts of the alphabet to encode your message, making it more complicated than the Caesar cipher, which only uses one shift.

## Block D: Elliptic Curve Cryptography ❃

Elliptic curves are deffined by equations of the form *y*^{2} = *x*^{3} + *ax* + *b*. Elliptic curve cryptography is a public-key cryptosystem making use of the fact that there is a way to add two points on an elliptic curve to get a third point. The block shows how to add a point P to itself.

## Block E: Electricity Plug 🗝

Modern cryptography relies on computers and therefore on electricity. This block also relates to the block with Tess’s kite and key.

## Block F: Carrier Pigeon and Letter Locking 🕊

One way that people kept messages secret in times before modern cryptography was with letter locking|intricate ways of folding and sealing their letters so that it would be clear if someone had opened the letter. This was popular in the 17th and 18th centuries, when letters were folded into themselves without envelopes. Many people developed their own unique ways of locking their letters. Pigeons were used to carry messages between people across long distances from ancient times until telephones were introduced.

## Block G: Knapsack Cryptography 🕶

In the knapsack problem, one person puts a set of weights into the bag, and the question is whether you can tell which weights were used if all you know is the possible weights used and the total weight of the bag. For example, if you knew that the weights could be 1, 2, 5, or 10 pounds, and the knapsack weighed 16 pounds, could you tell which weights were used? What if each weight can be used at most once? In a simple knapsack cryptosystem, the hidden message is which weights are in the knapsack and the encrypted message is the total weight. While simpler knapsack cryptosystems have been broken, some modern knapsack cryptosystems are believed to be good candidates for post-quantum cryptography.

## Block H: Lattice-based Cryptography ❃

Lattices-based cryptosystems such as GGH and NTRU use difficult problems about lattices to hide messages. One difficult lattice problem is the shortest vector problem, which in a simple example asks you to find an integer combination of vectors (for example, (4; 7) and (7; 11)) that has smaller coefficients. Sometimes, a “bad” basis (like the vectors given) is the public key that is used to encrypt, while the secret “good” basis of shorter vectors is the private key that is used for decryption. In this block, we can see a lattice with the public basis of longer vectors clearly indicated, while the private basis is less obvious. Lattice-based cryptosystems are important candidates for post-quantum cryptography.

## Block I: DNA Double Helix 🗝

DNA is the code of life! This block also references the Knotical scene

of the installation (with the ship in the bay) with the entanglements of knots. DNA is knotted to fit inside cells, and it is a tricky mathematical problem to figure out how to “unknot” the DNA to replicate it.

## Block J: Caesar Cipher 🕊

While Julius Caesar mentioned the method of delivery of a campaign message in his *Gallic Wars*, it was Suetonius who related the Caesar wrote to friends by replacing a letter of the alphabet by one 3 places further on, without changing the order of the alphabet.

## Block K: Hamming Code Revisited 🕶

In this block, we see the receiving end of Block A, the top-left block. The message from Block A (which was padded with extra information) was received with an error, and this block shows the error correction step. After some computation, the original message is recovered. Using error-correcting codes like the Hamming code allows us to ensure that the messages received are the same as the ones intended. They are used in many applications, such as check digits in credit card numbers or bar codes. The message in our two blocks is a reference to the month we finally met to complete the installation, and it is considered a lucky number!

## Block L: Pollard’s Rho Algorithm ❃

Some cryptosystems rely on the idea that factoring large numbers is a difficult problem. For example in RSA, a public key is a composite numbers which is the product of two large primes. The two primes are the secret private key used to decrypt messages, so if it were possible to factor easily, anyone would have the information they needed to decode a message. Pollard’s rho algorithm is a method for factoring numbers which are the product of two primes. It is named for the Greek letter rho (ρ) because it is an iterative process that eventually creates a cycle, which can be visualized like the shape ρ. And in case you were wondering, this algorithm is not efficient enough to attack RSA given the size of the primes currently being used.

## Block M: The Enigma Machine 🕶

Turning at disk ciphers to rotor disks happened as early as Thomas Edison, though it’s unknown how much use anyone made of such a machine. The most notorious known use is the lag which told the rotors how to shift and rotor system of the Enigma Machine used by both sides in WWII.

## Block N: Pigpen Cipher 🕊

The Pigpen cipher is one of those ciphers whose origins are unknown due to its simplicity and of little use in modern society. The base is two tic-tac-toe grids as well as two large X grids with the second of each with a dot in the grid. A letter of the alphabet is assigned to each location, and replicating its “pen” is used to represent the letter.

## Block O: ℤ=*p*ℤ^{x} is Cyclic ❃

This block shows the special structure of the integers modulo a prime number (in the case of this particular block, the prime is 19). If you exclude 0, every number modulo 19 is a power of 2; this is what we mean when we say 2 is a primitive root modulo 19. Every prime has a primitive root, and primitive roots are used, for example, in Diffie-Hellman key exchange, where two people can communicate information publicly, but end up with a shared secret.

## Block P: Quipu 🕊

The ancient Inca used patterns of knots in strings as a way to encode numerical data. As in a historical quipu, the knots in this block record numbers and multiple sets of strands add to the same value. It is thought that this was a kind of bookkeeping or error correction.

## Block Q: Shield 🗝

This block represents the security of cryptography. We rely on cryptography to protect our secrets, like our credit card numbers and other personal information. Secret stealing seems medieval, and we need a defense.

## Block R: Scytale 🕊

To obscure the message, it is written on a thin strip of paper while it is wrapped around a stick. Once the paper is removed from the stick, the letters are jumbled. The key to decoding the message is what diameter of stick to use. Because of the technical limitation of the time (1st through 12th centuries CE), getting a uniform cylinder of a specific diameter was difficult.

## Block S: Knitting Morse Code 🗝

In this block, two knitter are using Morse code in their knitting to have a conversation. One uses cables to encode the message; the other uses colorwork. Women hid Morse code messages in their knitting using knots in the yarn during WWI and WWII. Famously, Madame Defarge knit names into her scarves in the Charles Dickens novel *A Tale of Two Cities*. The knitting patterns for the pieces in the quilt are their own kind of code. You have to know the key to understand the instructions.

## Block T: Fingerprint 🗝

Our fingerprints are a code unique to each of us. It was observed by Arab merchants as early as 850 that Chinese merchants used fingerprints to authenticate contracts. Sir Henry T Head saw this in India around 1858 but it was not put on a scientific basic for almost 30 years. Part of the problem was how to index the ridges and patterns. Fictional accounts of fingerprints include Mark Twain’s *Pudd’nghead* *Wilson* in 1893 and Sir Conan Doyle in a 1903 Sherlock Holmes story set in 1894. Now many of us use our fingerprints as a key to open electronic devices instead of using a traditional password.

### The Quilt Binding

The binding of the quilt incorporates yet another code: the code for the fabrics we used to make the quilt! Since we were making the quilt from three different (and distant) locations, we all got the same fabrics and labeled them with letters so we could easily reference them with each other. It turned out that there were 26 total fabrics used exactly the number of letters in the alphabet!

Working your way around the binding on the edge of the quilt, you’ll first see all 26 fabrics. This is the “key” to our code, the fabrics A through Z. Then, continuing to circle the quilt, we have the initials of each of the 24 members of the Mathemalchemy team (in alphabetical order by last name). We used the white fabric (Z) as a spacer between each set of initials since no one has a name starting with Z.

## Answers

Don’t look until you’re ready! But if you’re sure…

## The binary code around the padlock says

*you are a mathematician*

## The color-based ternary code surrounding the padlock says

*math is beautiful*

## The Mandelbrot recipe is

1 cup slivered toasted almonds + ½ teaspoon salt + ½ teaspoon baking soda + 2 teaspoons baking powder + 3 ½ cups flour + 1 ½ tsp vanilla + ½ cup vegetable oil + 1 cup sugar + 3 eggs + 2 tsp grated orange zest.

Form into 11″ log and bake at 350° for 30 — 40 minutes. Cut log into 3/4″ slices and bake for 12 more minutes.

## The lighthouse Morse code says

*Mathematics illuminates the world*

## The numerical message being sent is

7

## The quipu strands record

1000+729 and 1728+1, showing that 1729 can be written as a sum of two cubes in two different ways. In a famous anecdote, Srinavasa Ramanujan

pointed this fact out to G.H. Hardy in 1919.

## The knit messages are

*Math is fun and I agree *

## One thought on “Cryptography Quilt – Mathematical Connections”