1 02-IntroCryptoCaesar

Previous: 01-InfoSecOverview.html

1.1 Screencasts

1.2 Reading

http://inventwithpython.com/cracking/ Chapters 1-6

1.3 Cryptography: a contentious history (and future)

Cryptography is the ultimate form of non-violent direct action.
- Julian Assange

Cryptography shifts the balance of power from those with a monopoly on violence [the nation state] to those who comprehend mathematics and security design [the people].
- Jacob Appelbaum

Note: Original reference to monopoly on violence in early legal history.

From the first chapter of our first textbook:
I do actually expect that you read each chapter in this book word for word…

"If you could travel back to the early 1990s with this book, the contents of Chapter 23 that implement part of the RSA cipher would be illegal to export out of the United States. Because messages encrypted with RSA are impossible to hack, the export of encryption software like RSA was deemed a matter of national security and required State Department approval. In fact, strong cryptography was regulated at the same level as tanks, missiles, and flamethrowers.

In 1990, Daniel J. Bernstein, a student at the University of California, Berkeley, wanted to publish an academic paper that featured source code of his Snuffle encryption system. The US government informed him that he would need to become a licensed arms dealer before he could post his source code on the internet. The government also told him that it would deny him an export license if he applied for one because his technology was too secure.

The Electronic Frontier Foundation, a young digital civil liberties organization, represented Bernstein in Bernstein v. United States. For the first time ever, the courts ruled that written software code was speech protected by the First Amendment and that the export control laws on encryption violated Bernstein's First Amendment rights.

Now, strong cryptography is at the foundation of a large part of the global economy, safeguarding businesses and e-commerce sites used by millions of internet shoppers every day. The intelligence community's predictions that encryption software would become a grave national security threat were unfounded.

But as recently as the 1990s, spreading this knowledge freely (as this book does) would have landed you in prison for arms trafficking. For a more detailed history of the legal battle for freedom of cryptography, read Steven Levy's book Crypto: How the Code Rebels Beat the Government, Saving Privacy in the Digital Age (Penguin, 2001)."

Export-restricted RSA encryption source code,
printed on a T-shirt made the T-shirt an export-restricted munition,
as a freedom of speech protest against US encryption export restrictions.
(The shirt’s back shows relevant clauses of the United States Bill of Rights,
under a ‘VOID’ stamp.)
Changes in the export law,
means that it is no longer illegal to export this T-shirt from the US,
or for US citizens to show it to foreigners.

The same as seen on: https://www.qubes-os.org/
And, who’s cryptography is shipped in every Chrome/Chromium/Blink/Electron application…

Have the crypto wars ended?
Show recent events…

Discussion question:
What are the implications of making strong cryptography illegal?
On people?
On law enforcement?
On national security?
On banking?
On internet discussion?

1.3.1 What is cryptography?

What does CIA represent in information security?
Why do we need cryptography?

1.3.2 Codes vs. Ciphers


Codes are known to the (literate adult) public for ease of communication.
Codes are sometimes used like encryption.
(spelling something to avoid a child understanding for example),
but are not “secure”.

1.4 Why learn simple ciphers?

Mathematical and theoretical primitives are required to fully understand modern cryptographic algorithms.

1.5 Reverse cipher

Trace the code for reverseCipher.py within the book as an exercise:

# -*- coding: utf-8 -*-

message: str = "Three can keep a secret, if two of them are dead."
translated: str = ""

i = len(message) - 1

while i >= 0:
    translated = translated + message[i]
    i = i - 1


And, a flowchart generated via my little project, py2cfg:
Why this little cipher?
Digestible chunks and baby steps!
Most of our algorithms will operate character by character like this.
The programming pattern of accumulating onto a string character by character will continue!

1.6 Cipher wheel


1.6.1 The Outer Wheel

English alphabet of 26 letters.
Do we start at 0 or 1?

1.6.2 The Inner Wheel

The inner wheel is used to determine the number of shifts

1.6.3 Spin the Inner Wheel


For an animation, see:

1.6.4 How to Determine an Encryption/Decryption Key

Each spin gives an encryption/decryption mapping.
A mapping is equivalent to shifting each letter a fixed number of times.

1.6.5 Encrypt with the cipher wheel

1. Take each letter from the plain-text and match it with the letter on the outer wheel
2. Replace the letter with the corresponding letter on the inner wheel

1.6.6 Decrypt with the cipher wheel

1. Take each letter from the cipher-text and match it with the letter on the inner wheel
2. Replace the letter with the corresponding letter on the outer wheel

1.7 Caesar Cipher

History of Wheel Cipher (>2000 years old)!
This will serve to demonstrate the mathematical formulations of a cipher,
which we will use again and again for more advanced ciphers.

1.7.1 History of Wheel Cipher: Caesar Cipher

Wheel cipher is also called Caesar cipher.
It was developed more than two thousand years ago.
It is also called “shift cipher” or “rot cipher” (rotation).

These algorithms might seem basic,
but they contain the methodological and conceptual precursors,
both in math, and in code,
for the modern algorithms we will cover shortly, e.g., DH, RSA, AES.

1.8 How to formalize and “compute” the Caesar Cipher


1.8.1 Mathematical Formulations


1.8.2 Basic general definitions/components for any cipher

X: the plaintext symbol/value domain

Y: the ciphertext symbol/value domain

K: the key symbol/value domain

E: the encryption function,
where E below is like a black box function:
\(E(x,k) \rightarrow y\)

D: the decryption function,
where D below is like a black box function:
\(D(y,k) \rightarrow x\)


1.8.3 Basic Definitions/Components for Caesar Cipher

What is the plaintext domain?
What is the ciphertext domain?
What is the key domain?
What is the encryption function for the Caesar cipher?
What is the decryption function for the Caesar cipher?

X: \(\mathbb{Z}_{26} = \{0, 1, 2, \ldots, 25 \}\)

Y: \(\mathbb{Z}_{26} = \{0, 1, 2, \ldots, 25 \}\)

K: \(\mathbb{Z}_{26} = \{0, 1, 2, \ldots, 25 \}\)

E: the encryption function
\(E(x,k) = x+k \mod 26\)

D: the decryption function
\(D(y,k) = y-k \mod 26\)

What is the deal with -x mod 26 ?

Negative mod?
Take a positive example:
9 + 5 mod 12 = 2

What is the reverse operation,
where we subtract 5 from 2, mod 12?
Does it return us back to 9?

The negative is not consistently defined in math,
and is programming language dependent,
but works as expected here in python,
reversing the mod operation:
(2 - 5) mod 12 = 9
2 - 5 = -3
-3 + 12 = 9

1.9 Code for the Caesar Cipher

Trace the code in the book caesarCipher.py

# -*- coding: utf-8 -*-

# Caesar Cipher
# https://www.nostarch.com/crackingcodes (BSD Licensed)

# The string to be encrypted/decrypted:
message: str = "All human beings have three lives: public, private, and secret. Gabriel Garcaa Marquez"

# The encryption/decryption key:
key: int = 13

# Whether the program encrypts or decrypts:
# Set to either 'encrypt' or 'decrypt'.
mode: str = "encrypt"

# Every possible symbol that can be encrypted:
SYMBOLS: str = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890 !?."

# Stores the encrypted/decrypted form of the message:
translated: str = ""

for symbol in message:
    # Note: Only symbols in the `SYMBOLS` string can be encrypted/decrypted.
    if symbol in SYMBOLS:
        symbolIndex = SYMBOLS.find(symbol)

        # Perform encryption/decryption:
        if mode == "encrypt":
            translatedIndex = symbolIndex + key
        elif mode == "decrypt":
            translatedIndex = symbolIndex - key

        # Handle wrap-around, if needed: What is this computing?
        if translatedIndex >= len(SYMBOLS):
            translatedIndex = translatedIndex - len(SYMBOLS)
        elif translatedIndex < 0:
            translatedIndex = translatedIndex + len(SYMBOLS)

        translated = translated + SYMBOLS[translatedIndex]
        # Append the symbol without encrypting/decrypting:
        translated = translated + symbol

# Output the translated string:


1.9.1 Cyptanalysis of Caesar Cipher

Security of Caesar Cipher

What happens with a key of 0?
What happens with a key of 25 (assuming a symbol set size of 26 and counting from 0)?
What happens with a key of 26?
How to break Caesar cipher?
What is the main problem with the Caesar cipher?
How many keys does it take trying to break the Caesar cipher?
Can we generalize this lesson?

1.10 Cracking the Caesar cipher

How many for loops in the original encryption and decryption code?
How many in the crack?

Trace the code in the book: caesarHacker.py

# -*- coding: utf-8 -*-

# Caesar Cipher Hacker
# https://www.nostarch.com/crackingcodes (BSD Licensed)

message: str = "NyyJu8zn1Jorv1t6Jun9rJ7u5rrJyv9r6:J38oyvp,J35v9n7r,Jn1qJ6rp5r7MJTno5vryJTn5pnnJZn548r?"
SYMBOLS: str = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890 !?."

# Loop through every possible key:
for key in range(1, len(SYMBOLS)):
    # It is important to set translated to the blank string so that the
    # previous iteration's value for translated is cleared.
    translated = ""

    # The rest of the program is almost the same as the original program:

    # Loop through each symbol in `message`:
    for symbol in message:
        if symbol in SYMBOLS:
            symbolIndex = SYMBOLS.find(symbol)
            translatedIndex = symbolIndex - key

            # Handle the wrap-around:
            if translatedIndex < 0:
                translatedIndex = translatedIndex + len(SYMBOLS)

            # Append the decrypted symbol:
            translated = translated + SYMBOLS[translatedIndex]

            # Append the symbol without encrypting/decrypting:
            translated = translated + symbol

    # Display every possible decryption:
    print("Key #%s: %s" % (key, translated))


1.11 What about layering and depth? Let’s double-encrypt!

Is double-encrypting with the Caesar cipher stronger?

1.12 How might we make a similar but better cipher?

What about key-space?

Next: 03-TranspositionCiphers.html