# Computational Thinking in a Liberal Arts Cryptology Course

Marcus Schaefer

Department of Computer Science

DePaul University

Chicago, Illinois 60604, USA

mschaefer@cdm.depaul.edu

April 2, 2009

## Abstract

We describe aspects of computational thinking as covered in the course Codes and Ciphers (CSC 233).

## Cryptology and Computational Thinking

Cryptology consists of cryptography and cryptanalysis, or, in other words, the making and the breaking of ciphers. History suggests that one cannot successfully do one without the other: too many ciphers were designed by enthusiasts without any knowledge of cryptanalysis, and the consequences were typically dire. In our Codes and Ciphers courses, the breaking of ciphers is therefore a central part of discussion and student activity. Histori cally too, the breaking of ciphers has typically been the motor of advances in cryptography, including Al-Kindi’s description in 900 AD of how to use frequency analysis to break substitution ciphers in Arabic and the work of Bletchley Park on breaking the German Enigma cipher during World War II. Throughout history, the cryptographic process has become more algorithmic, as ciphers became more mechanical, mathematical, and, eventually, digital. But even before the mechanization of cryptography in the 19th century (not accidentally coinciding with the advent of computing machines, both analogue and digital), a cryptographer’s work was best described in algorithmic terms, and in Codes and Ciphers the students will see evidence of that when breaking many classical ciphers.

The following is not a complete account of the topics covered in Codes and Ciphers; it concentrates on some of the relevant examples, and it recasts them in a more systematic fashion to emphasize the computational thinking lessons. For the purposes of this document, computational thinking is understood (narrowly) as the way of thinking involved in eﬀective problem solving. No attempt is made to explain the ciphers discussed in detail; Simon Singh’s The Code Book is a good, popular introduction; it is also, currently, the textbook for the course.

## Substitution and Frequency Analysis

The Shift Cipher

One of the oldest ciphers in use is the shift cipher: take each letter in a piece of text and replace it with the letter that occurs k positions later in the alphabet (after letter “z” start over again with “a”). There are several ways of breaking this (highly insecure) cipher, two of which are covered in class and that illustrate diﬀerent aspects of computational thinking.

Shift Cipher ExercisesPen and Pencil Solutions

⋄ Perform shift cipher encryptions and decryptions.

⋄ Break a shift cipher with pencil and paper by trying all possible keys.

Why is this possible?

⋄ How can that process be simpliﬁed (for pencil and paper solution)?

⋄ Are there any simple tools you could build using pencil/paper/scissor

that help in breaking the shift cipher?

Automated Solutions

⋄ What do plain- and ciphertext of a shift cipher have in common? What

does not change when making the shift substitution? Hint: look at

frequencies.

⋄ How can we exploit this observation to break the shift cipher?

⋄ Analyze this solution: what tools can it be performed by and how

eﬃcient is it?

⋄ Could this solution be used for other ciphers? What property do they

need to have?

2

Discussion

(i) Try al l possible keys. The realization that the number of possibilities

is small and can be explored exhaustively, leads to the idea of exhaus-

tive search, which is a core strategy in computational problem solving.

Modern chess programs, for example, at their core still follow this

strategy, of course in a much more sophisticated way. However, even

in the easy case of the shift cipher it is possible for the students to come

up with ways to improve the actual work performed (when breaking

the cipher by hand), emphasizing another goal of computational think-

ing: reducing the amount of computational resources required (what

is cheap, what is expensive, what is at hand? Pencil, paper, desktop

computer, . . .).

(ii) Paper strips. One way to mechanize breaking a shift cipher is to

create vertical strips of paper listing the letters “a” through “z” in

order; aligning the strips so they spell the ciphertext, one can then

look through the remaining rows to ﬁnd the plaintext. To make this

work well, each strip needs to list the alphabet twice (simulating the

wraparound). Paper strips like this were used to break ciphers in the

19th century (though not the shift cipher in particular).

(iii) Frequency analysis. Exhaustive search makes little use of the struc-

ture of the shift cipher; a shift cipher is a substitution cipher and as

such does not change the frequency distribution of the letters, it just

disguises it by renaming the letters. This observation, with a little

bit of statistical mathematics, can be used to automate the exhaustive

breaking of the shift cipher, that is, the process can be done by a com-

puter (or simulated by hand) without any human involvement. For

the students to understand and recreate this process, they need to un-

derstand one of the most basic principles in computational thinking:

when trying to understand a process (be it a shift cipher, a sorting

algorithm, or some other more complex procedure) it is diﬃcult to

argue about what changes; indeed, it is necessary to understand what

a particular process does not change. In the case of the shift cipher,

one such property is the frequency proﬁle; an invariant property of a

process is known as a loop invariant in computer science. This is a

very simple example of the analysis of change through invariant char-

acteristics, but one that students can easily experiment with visually

(the excel spreadsheet used for this cipher visualizes the invariant).

3

The ideas sketched above lead to a complete and satisfactory solution

of the shift cipher; in class these ideas are developed by breaking examples

of texts encoded by shift ciphers by hand, so the students have to develop

these ideas themselves by abstracting from the particular examples they see.

2.2 The Substitution Cipher

The substitution cipher is a generalization of the shift cipher in which each

letter is replaced by some other (unique) letter of the alphabet.

Substitution Cipher Exercises

⋄ Perform some substitution cipher encryptions and decryptions.

⋄ Can we try all possible keys to break the cipher? How many keys are

there?

⋄ How long would it take to try all keys by hand? On a computer? How

would we recognize English plaintext?

⋄ Does the frequency approach used for the shift cipher work?

⋄ Does the frequency approach lead to a mechanizable solution of sub-

stitution ciphers? How could it be extended to work?

⋄ What information about English words would be helpful in solving a

substitution cipher by hand?

Discussion

(i) Frequency analysis. Some (overly optimistic) texts claim that substi-

tution ciphers are easily solved by frequency analysis; when trying this

by hand, the students will quickly ﬁnd out that this is at best a half-

truth. The loop invariant approach that worked very well for the shift

cipher and which, at least in theory, applies to all substitution ciphers,

fails to lead to good results. Students realize that an approach can be

heuristic, i.e. only lead to partial or suboptimal solutions which might

not even be fully correct. The question then is how to improve results.

(ii) Trial and Error. A form of exhaustive search, trial and error quickly

becomes painful for substitution ciphers; students realize that addi-

tional understanding of the syntactic nature of English text is required

before this approach is meaningful. Indeed, using a combination of fre-

quency cliques, bigrams, and other information about English words,

leads to a collection of rules which together with frequency analysis

4

can be used to solve substitution ciphers in which word separations

have been maintained. The process is no longer automatic and re-

quires trial and error, but that trial and error is guided by rules based

on the behavior of letters in English words.

(iii) Frequency analysis again. Simple frequency analysis can be comple-

mented by information about the frequency of bigrams and trigrams

(this is particularly useful for ciphertexts in which word separations

have been eliminated).

(iv) Trial and Error again. On a computer it is quite feasible to try all pos-

sible keys one by one, reducing the problem to how we would recognize

English plaintext automatically. For that we can adapt the method of

recognizing plaintext in the shift cipher.

The are several computational thinking lessons here: extending a solu-

tion of another problem (frequency analysis to solve a shift cipher) to the

current problem is a form of reasoning by analogy; one tries to reduce a

problem to the solution of a problem one already knows. However, this

simple-minded approach fails in this particular case; if complemented with

additional rules, however, it can be made to work reasonably well. The

students learn that problem-solving itself is an iterative process and that

there is value in heuristic solutions when exact solutions are hard to come

by. Using a modern computer we can perform an exhaustive search of the

keyspace, and recognize English plaintext since that problem reduces to the

problem of recognizing plaintext for the shift cipher.

Learning Goals and Assessment

Goal. Use statistical analysis and trial and error to break a monoalphabetic

substitution cipher.

To assess this goal, the students will get a (individual) monoalphabetic

substitution cipher to solve on their homework.

3 The Vigen´ere Cipher and Reductionism

The Vigen´ere cipher is a Renaissance cipher that is still known as the “un-

breakable cipher”, even though it is far from unbreakable and this fact was

known in the Renaissance. The attacks on the Vigen´ere cipher became in-

creasingly more sophisticated, and, with Friedman’s statistical work at the

5

beginning of the 20-th century, reached maturity. The Vigen´ere cipher works

by taking a keyword and adding that keyword to the plaintext; in general,

the plaintext will be longer than the keyword, so we repeat the keyword as

often as necessary.

Vigen´ere Cipher Exercises

⋄ Perform some Vigen´ere cipher encryptions and decryptions.

⋄ Can we try all possible keys to break the cipher? How many keys are

there? How many keys are there if we assume a bound on the length

of the keyword?

⋄ Assuming we have keywords of length at most ℓ how long would it

take to break the Vigen´ere cipher by hand? On a computer? How

long must the keyword be for the Vigen´ere cipher to be more secure

against a brute force attack than a substitution cipher?

⋄ Is the Vigen´ere cipher a substitution cipher? How does it relate to

substitution and shift ciphers?

⋄ Suppose we knew the length of the keyword, would that help in break-

ing the cipher?

⋄ Encrypt some plaintext with very short keywords; does the ciphertext

show any structure that gives you a hint on how to determine the

length of the keyword? Hint: look for repeated letter sequences. What

do they mean?

⋄ What is the relationship between the index of coincidence and the

length of the keyword? Why? Hint: remember how we broke the shift

cipher automatically.

⋄ What is the size of the keyspace in the Yale key system?

⋄ How many keys are required to break the system using Blaize’s idea?

What is the similarity to breaking the Vigen´ere cipher?

Discussion

(i) Guessing keywords. A traditional, and often successful method. Like

password guessing, it can serve as a reminder to the student that an

exhaustive search need not be truly exhaustive, it can concentrate on

the most likely candidates of the search space ﬁrst (as in a dictionary

attack); a crude, but eﬀective heuristic. For the Vigen´ere cipher the

keyspace is inﬁnite in principle, but in practice one can assume that

keywords have bounded length.

6

(ii) Shift ciphers. As the students play with the system, they will quickly

notice that the Vigen´ere cipher is nothing but a series of ℓ parallel

shift ciphers, where ℓ is the length of the keyword. However, shift

ciphers are easy to break automatically, as we saw earlier, so if we

knew ℓ, we could break the problem into ℓ shift cipher problems, solve

them separately (automatically), and combine the solutions. We have

modularized the problem, by splitting it into two orthogonal prob-

lems: ﬁnding the keylength (which we do not yet know how to do)

and breaking shift ciphers (which we do know how to do). Breaking

problems into orthogonal components like this (i.e. components that

can be handled independently), is an important technique in compu-

tational thinking, related to divide & conquer (which also occurs here

when we split the Vigen´ere cipher into several shift ciphers). The third

computational technique illustrated here is reduction to a known prob-

lem: we reduce the solution of the Vigen´ere cipher to the solution of

several shift ciphers; to do this we need to ignore, for the moment,

that we do not yet know how to solve the ﬁrst problem: how to ﬁnd

the keylength. One of the advantages of modularization is that we can

deal with this issue separately.

(iii) Finding the keylength. There have been many methods to determine

the keylength of a Vigen´ere cipher, from Porta’s observation on re-

peated letters, the Kasiski test (looking for repeated subwords in the

ciphertext), and Friedman’s kappa test (index of coincidence). There

are more, but these are the three we discuss in class; Porta’s (weak)

heuristic naturally leads the way to the Kasiski test as a powerful

generalization (abstracting from the irrelevant repeated letters); the

Kasiski test was invented at a time when mechanization of society was

in full swing, and, not surprisingly, it is a process that lends itself

to automation (and it was automated in WWI and before). Looking

for automatable solutions is, of course, a trademark, of computational

thinking. Finally, Friedman’s kappa test is slightly more sophisticated

needing some statistical argument, but the students can easily under-

stand it and see that in terms of automation it is superior to Kasiski

(which was easy to mechanize, but is more painful, in terms of compu-

tational resources, to implement on a computer); it also reuses ideas

we saw when breaking the shift cipher automatically. An important

point here is that the students get to appreciate that diﬀerent solu-

tions for the same problem are possible that have diﬀerent properties

in terms of computational resources and that their appropriateness

7

varies by application (trenches in WWI are diﬀerent from a computer

desktop in 2008). This is another important aspect of modularization:

as long as the interface remains the same (we determine the keylength)

we can replace the module with another module performing the same

task, but possibly having other properties that are better suited to

the environment in which we have to solve the problem (do we need a

quick solution, do we have limited memory resources, and so on).

(iv) Pushing the envelope. The weakness of the Vigen´ere cipher lies in

repeating the keyword; students are naturally led to the question of

what happens if the keyword has the same length as the plaintext?

Studying this option, one observes that this would still leave too much

structure in the ciphertext that can be exploited for a break (though

we need diﬀerent methods from the ones mentioned above; this is ac-

tually a slightly diﬃcult problem, so in class we move right on). What

happens though, if we chose the keyword at random to destroy this

structure? The students have learnt to parameterize the system; at

this point the students realize that a system can be parameterized,

that is, we can make some aspect of the system variable and change it

to improve the system. This is an essential step in understanding how

a system works and why it works or fails. Moreover it leads the path to

improved systems, in this case the letter one-time pad, that was indeed

invented between WWI and WWI I used in several forms. A thorough

investigation of this system is beyond this class, but it immediately

leads to Shannon’s theory of information (and he, in turn, was led by

considerations like this) which is the foundation of modern computer

science. There are two lessons here, one that computational thinking

requires theorizing: a well-understood system has mathematical un-

derpinnings; and, secondly, something once understood can become

a building block (if appropriately adjusted) in a new endeavor. In-

deed, bright students at this point might realize that there is a much

stronger form of the Vigen´ere cipher possible if instead of combining

the keyword with shift ciphers one combines it with substitution ci-

phers; such ciphers are known and easily breakable today, but, in the

Renaissance, would have oﬀered the security that the Vigen´ere cipher

did not; however, the two ideas were put together rather late, and this

version of the Vigen´ere cipher never became very popular as a paper

and pen cipher; it did, however, eventually lead to rotor ciphers and

the Enigma (which is covered in the next section).

8

(v) Application. Computational problem-solving has two aspects: mod-

eling and algorithmic problem-solving; the modeling part is less ob-

viously computational than the algorithmic part, but it is one of the

most powerful tricks of computational thinking: recasting one problem

as another problem that has already been solved; prime examples in

computer science include linear programming and network ﬂows; com-

putational complexity theory is based on the notion of reduction be-

tween problems. To be able to model a problem successfully, one must

be able to see structural connections between problems that might

not be apparent at the surface; one such example which ties in with

the Vigen´ere cipher is Matt Blaize’s ingenious break into the Yale key

system; Blaize showed that it is to break the Yale key system if there

is a master key and one has access to a single lock (in that case one

can easily reconstruct the master key). Blaize’s solution is structurally

the same as the break into the Vigen´ere cipher: the problem is broken

into a small set of independent problems that can be solved in par-

allel, which leads to a signiﬁcant reduction in the size of the search

space. The analogy between the two problem solutions drives home

the importance of understanding a problem structurally, at an abstract

level.

At this point students have seen the brute-force approach to breaking a

cipher repeatedly, and they realize that the size of the keyspace is a ﬁrst,

rough, measure of complexity for breaking a cipher. Also, all examples so

far have illustrated that it can be a very misleading measure: the size of the

keyspace might be inﬂated. The core concept emphasize by the breaking of

the Vigen´ere cipher, however, is modularization: the weakness of the cipher

lies in the fact that its complexity is illusionary, it can easily be separated

into two independent parts that can easily be tackled separately.

Learning Goals and Assessment

Goal. Be able to break a Vigen´ere cipher using divide and conquer: de-

termining the key length with the Kasiski test and index of coincidence,

splitting the problem into several Caesar ciphers and then using frequency

analysis to break the Caesar ciphers.

To assess this goal, the students will have to break a piece of ciphertext

encrypted in the Vigen´ere system.

9

4 Enigma and the Mechanization of Cryptology

Breaking the enigma code was one of the ma jor intelligence triumphs of

WWI I; the ﬁrst breaks into the German enigma system were found by the

Polish cipher bureau; later Bletchley Park completed this work. Today a

desktop computer can break an enigma cipher in a matter of minutes (given

enough ciphertext), but this, of course, was not the case in the 1940s. The

Polish contribution to breaking the enigma again illustrates the importance

of ﬁnding an invariant; the enigma cipher is a progressive cipher: a substi-

tution cipher in which the substitution changes for each encrypted letter;

what Rejewski, the head of the Polish cipher bureau realized, was that from

the ciphertext one could abstract information that allowed one to identify

the rotor settings of the enigma machine (if one had suﬃciently many ci-

phertexts). To make this method operational, this information had to be

collected and indexed in a large catalogue; this method was barely practical

and Bletchley Park improved on it: as in the case of the Vigen´ere cipher

(and the Yale key system), Alan Turing realized that one could separate

out the eﬀects of the rotor settings from the eﬀects of the steckerboard (an

added, ﬁxed, substitution cipher); modularizing the problem thus split the

problem into two: ﬁnding the rotor settings (which, with a guided search,

was amenable to automated search by the bombes, special purpose com-

puters performing an exhaustive search of the keyspace), and the solution

of a simple (restricted) substitution cipher. Not coincidentally, the work

on the enigma also led Turing to work on and help design one of the ﬁrst

general purpose computers (the Colossus), as a more general tool for break-

ing ciphers. Interestingly this work extends Turing’s theoretical work in

the foundations of computability: he was the ﬁrst to rigorously model what

a computer is and ask (and answer) the question of what is, in principle,

computable with a computer. Breaking the enigma was one of the path-

ways into the modern computer. Turing did not foresee the reﬁnements

his work led to: distinguishing computable problems into feasible and in-

feasible problems, but he laid the foundation for this program that turned

into modern theoretical computer science and the study of resource-bounded

computation. The importance of studying resource bounded computation

is discussed in the next section.

Learning Goals and Assessment

Goal. Understand the workings of a rotor based encryption system like the

Enigma cipher and how it can broken by ﬁnding invariants of the system

10

and exploiting them (in the case of Enigma by a divide and conquer attack

combined with exhaustive search).

To assess this goal, the students will be asked to break a single-rotor

system using a known-plaintext attack and build a menu for breaking the

Enigma again based on a piece of known plaintext.

5 Public-Key Cryptography and the Mathemati-

zation of Cryptology

For much of its history, cryptology has been an arcane art, and it still

is. However, starting in the 20th century, there has been a notable trend

towards mathematical methods in both the making and the breaking of

ciphers. One of the earliest examples (only quickly discussed in class) is the

Hill cipher based on matrix multiplication; modern cryptography is based on

modular arithmetic, elliptic curves, and many other mathematical concepts.

Public-key cryptography is a strong departure from classical cryptog-

raphy: in public-key cryptography two parties (typically called Alice and

Bob) can communicate securely over a public channel, even if they have

never met before or exchanged any secret information: they can establish

secure communication between them while other parties are listening (the

other person is always known as Eve, the eavesdropper). Intuitively, this

seems impossible: how could you exchange a secret with somebody you

don’t know over the phone, say, in the presence of other people listening in

on your communication? However, public-key cryptography shows that this

is indeed possible, and the mathematics involved for the easier systems is

not very diﬃcult and can be understood by the students.

Public-Key Cryptography Exercises

⋄ Do an example of a Diﬃe/Hellman key exchange. How does this make

public-key cryptography possible?

⋄ Do an example of the three-way protocol. Why can this system not

be broken using logarithms? What about discrete logarithms?

⋄ How can we calculate the average salary of everybody in the room

without anybody learning anybody else’s salary? Hint: the problem

can be solved using a trusted third party (Trent), but what if we do

not even allow that? We can assume that everybody is honest, but we

do not want to share our salary information.

11

⋄ Do an example of bit-commitment using the hardness of the discrete

log problem.

⋄ How can we use bit-commitment to convince somebody that we have

found a legal coloring of a graph?

Discussion

• Key exchange. The Diﬃe/Hellman protocol allows Alice and Bob to

exchange a secret key; they can then use that secret key to use any

traditional cipher to communicate secretly. So while Diﬃe/Hellman is

not a public-key cryptosystem, it fulﬁlls a similar function: it makes

secret communication over an open channel possible without requiring

a shared secret at the start. This is a classical instance of reducing

one problem (secure communication) to another (key exchange).

• Computational limitations. All modern cryptosystems are based on

the assumption that certain mathematical problems are intractable,

that is, hard to solve by a computer. While traditional systems use

estimates on the size of the keyspace as a rough measure of com-

plexity, the hardness of breaking modern systems can often be tied

more closely to mathematical problems. For example, Diﬃe/Hellman

is based on the assumption that a variant of the discrete logarithm

problem is hard, amd RSA is based on the hardness of factoring large

numbers. So in modern cryptography computation is more than a tool,

it has become a meta-tool: the very fact that some task is computa-

tionally hard, can be exploited to build a feasible solution to another

problem (public-key cryptography), and indeed, there are approaches

to cryptography that link the theory of computation to cryptography

(an advanced topic not explored in this class). However, the students

do understand that for certain computational tasks, such as cryptog-

raphy, understanding the nature of computation itself becomes im-

portant. One consequence, and an important one as far as thinking

computationally is concerned, is that when designing a system, such as

a cryptosystem, that it can be useful to make assumptions on the com-

putational power of an opponent, and thereby make possible solutions

to problems that are otherwise unsolvable.

• Randomness. Randomness has been a resource for millennia: simple

games are not possible without a die or some other source of random

choice. However, randomness, being random, at ﬁrst glance, does not

12

seem to be a useful resource in the solution of practical problems. The

opposite turns out to be true: there are areas of computer science,

such as computational geometry, where many basic algorithms require

randomness to become practical, and modern cryptography has also

been able to channel the power of randomness. There are problems

which are, in principle, not solvable in a deterministic computational

model, however, allowing randomness suddenly yields solutions. Zero-

knowledge protocols belong to this area. Slightly simpliﬁed, one can

convince another person that one holds a particular piece of informa-

tion without giving away anything at all about the information itself

(how do you convince somebody that you were able to solve the Times

crossword puzzle without even giving them a single letter of your so-

lution?). We touch on these ideas in the class. Again, students come

to understand, that making the nature of computation (deterministic

versus randomized) the ob ject of study was a central step in making

possible solutions to problems that had been unsolvable before.

Learning Goals and Assessment

Goal. Understand modular arithmetic and randomness and their impor-

tance for modern cryptography.

To assess this goal, the students will set up a Diﬃe/Hellman system for

key-exchange and set up a secret-sharing theme requiring randomness.

13

A Examples and Ideas

The following table shows the relationship between the examples given above

and the computational thinking ideas they illustrate.

idea \ example Caesar shift substitution Vigenere Enigma Public-key

brute-force x x

resource-dependence x x x x

analyzing change x x x

heuristics x x x

reduction x x

modularization x x

parameterization x x

analogy x

randomness x

14