Basic Cryptography

Understanding the Implementation of Simple Cryptosystems

Gregory M. Kapfhammer

September 16, 2024

What is cryptography?

Establish secure and confidential communication channels
Supports creation of digital signatures
Allows us to support the “AAA principles”:
- Authentication
- Authorization
- Accounting
Ensures that attackers cannot “listen in” to communication
Ensures non-repudiation of digital communication

Important Insight: cryptography is one of the key building blocks of computer security!

Key Reminder: it is deceptively difficult to deploy cryptographic algorithms correctly!

Admonition: avoid the temptation to “roll your own” cryptography algorithms! Problems!

Cryptography Terms

Plaintext: the original message
Ciphertext: the encrypted message
Cipher: the algorithm used to encrypt the message
Key: the secret used to encrypt the message
- Symmetric Key: the same key to encrypt and decrypt
- Asymmetric Key: different keys to encrypt and decrypt

Key Questions: What are the trade-offs between different types of keys? Ways to balance security, privacy, and performance? How?

Creating Simple Cryptosystems

What is the benefit of studying weak cryptography algorithms like those in Cracking Codes with Python?
- Understand the basics of cryptography
- Learn why these systems are not secure
- Feasibly explore the steps of cryptanalysis

Reverse Cipher Program

How does this cipher work?
Does this cipher have a key?
How would you break this cipher?
Task: Run this cipher with different messages

Caesar Cipher Program

Task: Run this cipher with different messages and modes

Recap on the Caesar Cipher

Key Benefit: basic cryptography algorithm previously used
Important Reminder: easily susceptible to cryptanalysis

Review Questions:
- What is the purpose of the key variable?
- What is the purpose of the mode variable?
- What if a letter is not in the SYMBOLS string?
- Why does the algorithm need to handle “wraparound”?
- Can you explain the assignment of translated = translated + SYMBOLS[translatedIndex]?

Brute Force Caesar Cipher Attack

Recap on Caesar Cipher Attack

Key Insight: “brute force” means to try all possible keys
Important Reminder: feasible due to the small key space

Review Questions:
- Which key value ultimately decrypts the message?
- What is the purpose of the mode variable?
- How does this connect to the encryption technique?
- Why does the algorithm need to handle “wraparound”?
- Can you explain the assignment of symbolIndex = SYMBOLS.find(symbol)?

Transposition Cipher Encryption

Task: Try different values for current_message and current_key

Recapping Transposition Encryption

Key Insight: key space depends on the message’s length
Important Reminder: focuses on columnar transposition

Review Questions:
- What does it mean if it works in a “columnar” fashion?
- Is this more difficult to break than the Caesar cipher?
- How does this connect to the encryption technique?
- What are the functions inside of this algorithm?
- What is the purpose of the | character in the output?

Transposition Cipher Decryption

Recapping Transposition Decryption

Key Insight: assumes knowledge of share secret key
Important Reminder: decryption different than encryption

Review Questions:
- Recovers plaintext by reading columns from a grid
- Blank, not needed, cells appear at end of the grid
- Must use the same key for encryption and decryption
- Purpose of int(math.ceil(len(message) / float(key)))?
- How do you know that the algorithm worked correctly?

How to Test a Cipher?

Test the Transposition Cipher to ensure its correctness!
Generate random messages, encrypt, and then decrypt
Run for a range of keys, which determine the cipher’s shift
Use random messages and keys, covering various scenarios
A fixed seed ensures the test is repeatable, aiding debugging
Decryption fails when message does not match original

Key Questions: How can we implement this for the transposition cipher? What amount of testing is sufficient to confirm correctness?

Transposition Cipher Testing

Standard Approach

flowchart LR
  A(Plain Text) --> B[Encryption Algorithm]
  B --> C(Cipher Text)
  C --> D[Decryption Algorithm]
  D --> E(Plain Text)
  style A fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style B fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style C fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style D fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style E fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  linkStyle 0,1,2,3 stroke:#1c1c1c,color:#1c1c1c

Iterative Approach

flowchart LR
  B[Start] --> A[Generate Random Message] --> C[Encrypt Message]
  C --> D[Decrypt Message]
  D --> E{Random == Decrypted?}
  E -->|Yes| F[Test Passed]
  E -->|No| G[Test Failed]
  F --> H[End]
  G --> H
  H -->|Repeat| B
  style A fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style B fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style C fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style D fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style E fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style F fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style G fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  style H fill:#fff,color:#1c1c1c,stroke:#1c1c1c,stroke-width:2px
  linkStyle 0,1,2,3,4,5,6,7,8 stroke:#1c1c1c,color:#1c1c1c

Repeatedly generate random messages, checking cipher output each round! Continue testing until you have established confidence in the cipher.

Testing the Transposition Cipher

Revisiting the Fernet Cipher

from cryptography.fernet import Fernet

def encrypt_string(input_string: str, key: str):
    """Encrypt a string using a symmetric key."""
    # convert the string into bytes
    data_bytes = input_string.encode()
    # create a Fernet object
    fernet = Fernet(key)
    # encrypt and return the data
    encrypted_data = fernet.encrypt(data_bytes)
    return encrypted_data

def decrypt_string(encrypted_data: bytes, key: str):
    """Decrypt data using a symmetric key."""
    # create a Fernet object
    fernet = Fernet(key)
    # decrypt and return the data
    decrypted_data = fernet.decrypt(encrypted_data)
    return decrypted_data.decode()

Testing Function for Fernet Cipher

from cryptography.fernet import Fernet
import random, string

def test_encryption_decryption(message):
    """Test the encryption and decryption of a message."""
    # generate a symmetric key
    key = Fernet.generate_key()
    # encrypt the string
    encrypted_data = encrypt_string(message, key)
    # decrypt the data
    decrypted_data = decrypt_string(encrypted_data, key)
    # check if the decrypted data matches the original message
    assert decrypted_data == message, 'Decryption does not match original message'

def generate_random_string(length):
    """Generate a random string of letters."""
    letters = string.ascii_letters
    return ''.join(random.choice(letters) for i in range(length))

Running Tests for Fernet Cipher

i = 0
while i < 14:
    length = random.randint(10, 50)
    message = generate_random_string(length)
    test_encryption_decryption(message)
    print(f"Test: {message}, Status: Test passed.")
    i += 1

Test: gxPwPAsepVldYcPGAWvEkO, Status: Test passed.
Test: WfrhsJcmjMZjrnfRQgAlcU, Status: Test passed.
Test: UnxMXYLhdJhw, Status: Test passed.
Test: JxGgIlfmtHoBpVfUxmXBT, Status: Test passed.
Test: DqQMwNWzFmizMPrZViazsBZujjSQxmkwbXad, Status: Test passed.
Test: SyBXRBSiIAGCMofmhewlbfBmyzGTuyGjQzMucEmQPcTxFUGC, Status: Test passed.
Test: OOyQsVbGJhEGQJpeuto, Status: Test passed.
Test: NriNYNRJOdrNTKihLPPjIbySYlmUFXGfPeoxEHKj, Status: Test passed.
Test: dnHzzoVDair, Status: Test passed.
Test: QkNYXzuQRktLEdaBVNJMXVFTfkYGnxubu, Status: Test passed.
Test: kuHGHsuvLLDxuXRMQQthGKjkwlPn, Status: Test passed.
Test: wIfXhoNZwZHOoODaZimDEAjMZFBBdnHOtWlhWCWedEJ, Status: Test passed.
Test: ePOBuYeJMlyTOn, Status: Test passed.
Test: elYkrEnQJjcnA, Status: Test passed.

Recapping Cipher Testing

Key Insight: establish a confidence in cipher correctness
Important Reminder: ensure that functions are invertible

Review Questions:
- What is the overall approach in cipher testing?
- What is the purpose of the assert statement?
- How does the test_encryption_decryption function work?
- How does the generate_random_string function work?
- What are the limitations of this testing approach?

Hacking the Transposition Cipher

How can we hack the transposition cipher?
- Make these assumptions:
  - Assume that the cipher is in use
  - Not clear what language is in use
  - Do not know the key or its length
- Wow, this hack requires a lot of implementation!

Detecting the English Language

# Detect English module
# https://www.nostarch.com/crackingcodes (BSD Licensed)
# (There must be a "dictionary.txt" file in this directory with all English
# words in it, one word per line.)
UPPERLETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
LETTERS_AND_SPACE = UPPERLETTERS + UPPERLETTERS.lower() + ' \t\n'

def loadDictionary():
    dictionaryFile = open('dictionary.txt')
    englishWords = {}
    for word in dictionaryFile.read().split('\n'):
        englishWords[word] = None
    dictionaryFile.close()
    return englishWords

ENGLISH_WORDS = loadDictionary()

def getEnglishCount(message):
    message = message.upper()
    message = removeNonLetters(message)
    possibleWords = message.split()
    if possibleWords == []:
        return 0.0
    matches = 0
    for word in possibleWords:
        if word in ENGLISH_WORDS:
            matches += 1
    return float(matches) / len(possibleWords)

def removeNonLetters(message):
    lettersOnly = []
    for symbol in message:
        if symbol in LETTERS_AND_SPACE:
            lettersOnly.append(symbol)
    return ''.join(lettersOnly)

def isEnglish(message, wordPercentage=20, letterPercentage=85):
    wordsMatch = getEnglishCount(message) * 100 >= wordPercentage
    numLetters = len(removeNonLetters(message))
    messageLettersPercentage = float(numLetters) / len(message) * 100
    lettersMatch = messageLettersPercentage >= letterPercentage
    return wordsMatch and lettersMatch

Preview the Dictionary File

AARHUS
AARON
ABABA
ABACK
ABAFT
ABANDON
ABANDONED
ABANDONING
ABANDONMENT
ABANDONS
ABASE
ABASED
ABASEMENT
ABASEMENTS
ABASES
ABASH
ABASHED
ABASHES

Revisiting the Transposition Cipher

import math

# Transposition Cipher Encryption
# https://www.nostarch.com/crackingcodes/ (BSD Licensed)
def encryptMessage(key, message):
    ciphertext = [''] * key
    # loop through each column in ciphertext:
    for column in range(key):
        currentIndex = column
        # keep looping until currentIndex goes past the message length:
        while currentIndex < len(message):
            # place the character at currentIndex in message at the
            # end of the current column in the ciphertext list
            ciphertext[column] += message[currentIndex]
            # move currentIndex over
            currentIndex += key
    # convert the ciphertext list into a single string value and return it:
    return ''.join(ciphertext)

def decryptMessage(key, message):
    numOfColumns = int(math.ceil(len(message) / float(key)))
    numOfRows = key
    # the number of "shaded boxes" in the last "column" of the grid
    numOfShadedBoxes = (numOfColumns * numOfRows) - len(message)
    # each string in plaintext represents a column in the grid:
    plaintext = [''] * numOfColumns
    column = 0
    row = 0
    for symbol in message:
        plaintext[column] += symbol
        column += 1
        # if there are no more columns OR we're at a shaded box, go back
        # to the first column and the next row:
        if (column == numOfColumns) or (column == numOfColumns - 1 and
            row >= numOfRows - numOfShadedBoxes):
            column = 0
            row += 1
    return ''.join(plaintext)

Setup Transposition Cipher Hacking

def perform_transposition_hack():
    myMessage = """AaKoosoeDe5 b5sn ma reno ora'lhlrrceey e  enlh na  indeit n uhoretrm au ieu v er Ne2 gmanw,forwnlbsya apor tE.no euarisfatt  e mealefedhsppmgAnlnoe(c -or)alat r lw o eb  nglom,Ain one dtes ilhetcdba. t tg eturmudg,tfl1e1 v  nitiaicynhrCsaemie-sp ncgHt nie cetrgmnoa yc r,ieaa  toesa- e a0m82e1w shcnth  ekh gaecnpeutaaieetgn iodhso d ro hAe snrsfcegrt NCsLc b17m8aEheideikfr aBercaeu thllnrshicwsg etriebruaisss  d iorr."""
    hackedMessage = hackTransposition(myMessage)
    if hackedMessage == None:
        print('Failed to hack encryption.')
    else:
        print(hackedMessage)

def hackTransposition(message):
    print('Hacking...')
    for key in range(1, len(message)):
        print('Trying key #%s...' % (key))
        decryptedText = decryptMessage(key, message)
        if isEnglish(decryptedText):
            print('Possible encryption hack:')
            print('Key %s: %s' % (key, decryptedText[:100]))
            return decryptedText
    return None

Running Transposition Hacking

perform_transposition_hack()

Hacking...
Trying key #1...
Trying key #2...
Trying key #3...
Trying key #4...
Trying key #5...
Trying key #6...
Possible encryption hack:
Key 6: Augusta Ada King-Noel, Countess of Lovelace (10 December 1815 - 27 November 1852) was an English mat
Augusta Ada King-Noel, Countess of Lovelace (10 December 1815 - 27 November 1852) was an English mathematician and writer, chiefly known for her work on Charles Babbage's early mechanical general-purpose computer, the Analytical Engine. Her notes on the engine include what is recognised as the first algorithm intended to be carried out by a machine. As a result, she is often regarded as the first computer programmer.

Generate all possible keys
Print the decrypted message if it is English

Performance of Fernet Cipher

import time

def performance_encryption_decryption(message):
    key = Fernet.generate_key()
    start_encryption = time.time()
    encrypted_data = encrypt_string(message, key)
    end_encryption = time.time()
    start_decryption = time.time()
    decrypted_data = decrypt_string(encrypted_data, key)
    end_decryption = time.time()
    encryption_time = (end_encryption - start_encryption) * 1000
    decryption_time = (end_decryption - start_decryption) * 1000
    assert decrypted_data == message, 'Decryption does not match original message'
    return encryption_time, decryption_time

Use the time module to measure the performance of Fernet
Elapsed time in milliseconds for encryption and decryption

Performance Study for Fernet Cipher

i = 0
while i < 14:
    length = random.randint(10, 30)
    message = generate_random_string(length)
    (etime, dtime) = performance_encryption_decryption(message)
    print(f"M: {message:30} S: Passed, ET: {etime:.4f}ms, DT: {dtime:.4f}ms.")
    i += 1

M: GibfZBjoIyNfHYaoSMsYovxqvF     S: Passed, ET: 0.5987ms, DT: 0.1235ms.
M: rvySwRsvRYKNXRSIBxTAMldKurT    S: Passed, ET: 0.2396ms, DT: 0.1163ms.
M: wnKqXEXwtkkuTkEQJHKkmLRuF      S: Passed, ET: 0.0789ms, DT: 0.0634ms.
M: nmpgWINreDQUWbVk               S: Passed, ET: 0.0646ms, DT: 0.0606ms.
M: uAvJWbuUqvA                    S: Passed, ET: 0.0634ms, DT: 0.0587ms.
M: hXPJYtlsgSKF                   S: Passed, ET: 0.0598ms, DT: 0.0551ms.
M: qhJeUTOiynnIacRPmekHgHNr       S: Passed, ET: 0.0591ms, DT: 0.0558ms.
M: NYTLWUstSfsistBzDJoZzAhre      S: Passed, ET: 0.0579ms, DT: 0.0558ms.
M: hWoyPTEwZGJ                    S: Passed, ET: 0.0584ms, DT: 0.0553ms.
M: fFkEEKeDoqsQxRlsMEFrNx         S: Passed, ET: 0.0577ms, DT: 0.0882ms.
M: nnfgWPwDMpCzvvEpBzY            S: Passed, ET: 0.0648ms, DT: 0.0577ms.
M: opfSCggJrtBpuwJESkvJs          S: Passed, ET: 0.0579ms, DT: 0.0563ms.
M: OaXMscBdCxCiEFL                S: Passed, ET: 0.0591ms, DT: 0.0551ms.
M: PZNucblbLsLICdrwJl             S: Passed, ET: 0.0577ms, DT: 0.0548ms.