IntroCryptoCaesar

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

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

++++++++++++++++++++
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?

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

#!/usr/bin/python3
# -*- 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

print(translated)

And, a flowchart generated via my little project, py2cfg:
IntroCryptoCaesar/reverseCipher_cfg.svg

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!

#!/usr/bin/runghc

main :: IO ()
main = do
  let message = "Three can keep a secret, if two of them are dead."
  putStrLn (reverse message)

1.6 Cipher wheel

1.6.1 The Outer Wheel

1.6.2 The Inner Wheel

1.6.3 Spin the Inner Wheel

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

IntroCryptoCaesar/04cipher_wheel_encrypt.png

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
IntroCryptoCaesar/05cipher_wheel_encrypt.png

IntroCryptoCaesar/05cipher_wheel_encrypt.png

1.6.6 Decrypt with the cipher wheel

IntroCryptoCaesar/06cipher_wheel_decrypt.png

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.
IntroCryptoCaesar/disk.jpg

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

Mention:
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

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?

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:

1.9 Code for the Caesar Cipher

#!/usr/bin/python3
# -*- 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 Garcia 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]
    else:
        # Append the symbol without encrypting/decrypting:
        translated = translated + symbol

# Output the translated string:
print(translated)

#!/usr/bin/runghc

module CaesarCipher (encryptString, decryptString) where

import Data.List
import Data.Maybe ()
import System.Random (randomRIO)
import Test.QuickCheck

symbolSet :: String
symbolSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890 !?."

m = length symbolSet

-- |
-- >>> encodeChar 'A'
-- Just 0
encodeChar :: Char -> Maybe Int
encodeChar symbol = elemIndex symbol symbolSet

-- |
-- >>> decodeChar 0
-- 'A'
decodeChar :: Int -> Char
decodeChar index = symbolSet !! index

-- |
-- >>> addKeyPoint 1 4
-- 5

-- |
-- >>> addKeyPoint 1 65
-- 0
addKeyPoint :: Int -> Int -> Int
addKeyPoint key codePoint = mod (codePoint + key) m

-- |
-- >>> subKeyPoint 1 5
-- 4

-- |
-- >>> subKeyPoint 1 0
-- 65
subKeyPoint :: Int -> Int -> Int
subKeyPoint key codePoint = mod (codePoint - key) m

-- |
-- >>> encryptChar 1 'A'
-- 'B'
encryptChar :: Int -> Char -> Char
encryptChar key c = case encodeChar c of
  Nothing -> c
  Just codePoint -> decodeChar (addKeyPoint key codePoint)

-- |
-- >>> decryptChar 1 'B'
-- 'A'
decryptChar :: Int -> Char -> Char
decryptChar key c = case encodeChar c of
  Nothing -> c
  Just codePoint -> decodeChar (subKeyPoint key codePoint)

-- |
-- >>> encryptString 1 "zed."
-- "1feA"
encryptString :: Int -> String -> String
encryptString key = map (encryptChar key)

-- Eta reduced from this:
-- encryptString key message = map (encryptChar key) message

-- |
-- >>> decryptString 1 "1feA"
-- "zed."
decryptString :: Int -> String -> String
decryptString key = map (decryptChar key)

-- Eta reduced from this:
-- decryptString key message = map (decryptChar key) message

-- |
-- >>> quickCheck test
-- +++ OK, passed 100 tests.
test :: Int -> String -> Bool
test key message = message == (decryptString key . encryptString key) message

keyGen :: IO Int
keyGen = randomRIO (1, m) :: IO Int

main :: IO ()
main = do
  let message = "All human beings have three lives: public, private, and secret. Gabriel Garcia Marquez"
  -- let key = 13
  key <- keyGen
  putStrLn ("Your key was: " ++ show key)
  putStrLn "Your encrypted message is:"
  putStrLn (encryptString key message)
  putStrLn "Your decrypted ciphertext is:"
  putStrLn (decryptString key (encryptString key message))

This Haskell program was built with tiny functions,
a reliable way to incrementally improve your code.
We could have writte the python one the same way.

1.9.1 Cyptanalysis of Caesar Cipher

Discuss:
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?

#!/usr/bin/python3
# -*- coding: utf-8 -*-

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

message: str = (
    "NyyJu8zn1Jorv1t6Jun9rJ7u5rrJyv9r6:J38oyvp,J35v9n7r,Jn1qJ6rp5r7MJTno5vryJTn5pvnJZn548r?"
)
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]

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

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

#!/usr/bin/runghc

import CaesarCipher
import Data.List

caesarHacker :: String -> [(Int, String)]
caesarHacker message = [(key, decryptString key message) | key <- [0 .. 65]]

main :: IO ()
main = do
  let message = "All human beings have three lives: public, private, and secret. Gabriel Garcia Marquez"
  let key = 13
  putStrLn "Your encrypted message is:"
  putStrLn (encryptString key message)
  putStrLn "Your cracked ciphertext is:"
  putStrLn (intercalate "\n" (map show (caesarHacker (encryptString key message))))

#!/bin/bash

message=$(</dev/stdin)
symbols="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890 !?."
successfulTranslation="Error: none of the decrypted messages have any English in them!"
translationScore=4

for key in $(seq 2 ${#symbols}); do
    (("key--")) #range 1-65
    translated=""
    messageScore=0
    for index in $(seq 1 ${#message}); do
        (("index--"))
        char=${message:index:1}
        remaining=${symbols#*"$char"}
        symbolIndex=$((${#symbols} - ${#remaining} - 1))
        if ((symbolIndex == -1)); then
            translated=$translated$char
        else
            translatedIndex="$(((symbolIndex - key + 66) % 66))"
            translated=$translated${symbols:translatedIndex:1}
        fi
    done
    query=${translated^^}
    query=$(echo "$query" | tr -d '[:punct:]')
    for word in $query; do
        if grep -xq "$word" dictionary.txt; then
            (("messageScore++"))
        fi
    done
    if [ "$messageScore" -gt "$translationScore" ]; then
        translationScore=$messageScore
        successfulTranslation=$translated
        break
    fi
done
echo "$successfulTranslation"

1 IntroCryptoCaesar

1.1 Screencasts

1.2 Reading

1.3 Cryptography: a contentious history (and future)