Revisiting Cryptography

Understanding the Role of Cryptography in Security

Gregory M. Kapfhammer

November 25, 2024

What role should cryptography play in secure software?

• Hashing
• Signatures
• Encryption
• Decryption

Example: Using SSH Keys on GitHub

• Step 1: Generate a new SSH key
• Step 2: Add the SSH key to your GitHub account
• Step 3: Run an SSH agent in the background
• Step 4: Clone a repository using SSH

• In-Class Discussion:
  • What program(s) did you use to complete these steps?
  • Does this use symmetric or asymmetric cryptography?
  • How does this different from using a password?
  • What are the trade-offs of these different approaches?

Practical Exploration: Try to use the ssh-keygen program! What do the public and private keys look like?

What are some other cryptographic methods?

• Affine ciphers
• Substitution ciphers
• Vigenere ciphers

Cryptography Reminders

• Explore ciphers to understand key principles of cryptography
• Offer initial implementations in Python — but explore others!

Mathematical Background

def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a

def mod_inverse(a: int, m: int) -> int:
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    raise ValueError("Modular inverse does not exist.")

• In-Class Discussion
  • What are the input and output types of these functions?
  • What is the purpose of the % operator in these functions?
  • What do the gcd and mod_inverse functions do?

Using the gcd Function

a = 10
b = 26
gcd_result = gcd(a, b)
print(f"gcd({a}, {b}) = {gcd_result}")

a = 5
b = 26
gcd_result = gcd(a, b)
print(f"gcd({a}, {b}) = {gcd_result}")

a = 17
b = 31
gcd_result = gcd(a, b)
print(f"gcd({a}, {b}) = {gcd_result}")

gcd(10, 26) = 2
gcd(5, 26) = 1
gcd(17, 31) = 1

What do outputs show about the gcd function’s behavior?

Using the mod_inverse Function

a = 10
m = 26
try:
    mod_inverse_result = mod_inverse(a, m)
    print(f"mod_inverse({a}, {m}) = {mod_inverse_result}")
except ValueError as e:
    print(e)

a = 17
m = 31
try:
    mod_inverse_result = mod_inverse(a, m)
    print(f"mod_inverse({a}, {m}) = {mod_inverse_result}")
except ValueError as e:
    print(e)

Modular inverse does not exist.
mod_inverse(17, 31) = 11

What is the behavior of the mod_inverse function?

Goal: Find the number x such that when a is multiplied by x and then divided by m, the remainder is 1!

Checking mod_inverse

a = 17
m = 31
numerator = 17 * 11
denominator = 31
result = numerator // denominator
remainder = numerator % denominator
print(f"The result of {numerator} divided by {denominator}")
print(f"is {result} with a remainder of {remainder}")

The result of 187 divided by 31
is 6 with a remainder of 1

• Did the mod_inverse function return the correct result?
• What is the time complexity of the mod_inverse function?
• How does this connection to affine ciphers?
• Okay, let’s explore this cryptosystem in greater detail!

Encryption with Affine Ciphers

def affine_encrypt(plaintext: str, a: int, b: int) -> str:
    if gcd(a, 26) != 1:
        raise ValueError("a and 26 are not coprime, choose a different 'a' value.")
    ciphertext = ""
    for char in plaintext:
        if char.isalpha():
            # convert character to 0 to 25 range
            x = ord(char.lower()) - ord('a')
            # apply affine transformation
            encrypted_char = (a * x + b) % 26
            # convert back to character and preserve case
            if char.islower():
                ciphertext += chr(encrypted_char + ord('a'))
            else:
                ciphertext += chr(encrypted_char + ord('A'))
        else:
            ciphertext += char
    return ciphertext

plaintext = "Make a security synapse"
a = 5
b = 8
encrypted = affine_encrypt(plaintext, a, b)
print(f"Encrypted: {encrypted}")

Encrypted: Qigc i ucsepwzy uyvifuc

Decryption with Affine Ciphers

def affine_decrypt(ciphertext: str, a: int, b: int) -> str:
    if gcd(a, 26) != 1:
        raise ValueError("a and 26 are not coprime, choose a different 'a' value.")
    plaintext = ""
    # find modular inverse of the integer a
    a_inv = mod_inverse(a, 26)
    for char in ciphertext:
        if char.isalpha():
            # convert character to 0 to 25 range
            y = ord(char.lower()) - ord('a')
            # apply inverse affine transformation
            decrypted_char = (a_inv * (y - b)) % 26
            # convert back to character and preserve case
            if char.islower():
                plaintext += chr(decrypted_char + ord('a'))
            else:
                plaintext += chr(decrypted_char + ord('A'))
        else:
            plaintext += char
    return plaintext

decrypted = affine_decrypt(encrypted, a, b)
print(f"Decrypted: {decrypted}")

Decrypted: Make a security synapse

Recapping the Affine Cipher

Lessons Learned about Affine Cipher

• Affine ciphers use modular arithmetic and inverses

• Code segment from the encryption function:

  • encrypted_char = (a * x + b) % 26

• Code segment from the decryption function:

  • decrypted_char = (a_inv * (y - b)) % 26

• Importantly, it is vulnerable to frequency analysis attacks

• However, it illustrates role of modular arithmetic and primes!

• Any questions about the encrypt or decrypt functions?

Exploring Substitution Ciphers Like Vigenere

• Example of of substitution cipher
• Uses a key to encrypt messages
• Encrypts each letter with a different shift value
• Let’s explore these functions:
  • vigenere_encrypt
  • vigenere_decrypt

Encrypting with Vigenere

def vigenere_encrypt(plaintext: str, key: str) -> str:
    key = key.lower()
    key_length = len(key)
    ciphertext = ""
    for i, char in enumerate(plaintext):
        if char.isalpha():
            shift = ord(key[i % key_length]) - ord('a')
            if char.islower():
                encrypted_char = chr((ord(char) - ord('a') + shift) % 26 + ord('a'))
            else:
                encrypted_char = chr((ord(char) - ord('A') + shift) % 26 + ord('A'))
            ciphertext += encrypted_char
        else:
            ciphertext += char
    return ciphertext

plaintext = "Make a security synapse"
key = "key"
encrypted = vigenere_encrypt(plaintext, key)
print(f"Encrypted: {encrypted}")

Encrypted: Weio y wcmypsxw wwxenci

Decrypting with Vigenere

def vigenere_decrypt(ciphertext:str, key:str) -> str:
    key = key.lower()
    key_length = len(key)
    plaintext = ""
    for i, char in enumerate(ciphertext):
        if char.isalpha():
            shift = ord(key[i % key_length]) - ord('a')
            if char.islower():
                decrypted_char = chr((ord(char) - ord('a') - shift + 26) % 26 + ord('a'))
            else:
                decrypted_char = chr((ord(char) - ord('A') - shift + 26) % 26 + ord('A'))
            plaintext += decrypted_char
        else:
            plaintext += char
    return plaintext

decrypted = vigenere_decrypt(encrypted, key)
print(f"Decrypted: {decrypted}")

Decrypted: Make a security synapse

Recapping the Vigenere Cipher

Lessons Learned about Vigenere Cipher

• Vigenere ciphers use a repeating key to shift letters

• Code segment from the encryption function:

  • encrypted_char = chr((ord(char) - ord('a') + shift) % 26 + ord('a'))

• Code segment from the decryption function:

  • decrypted_char = chr((ord(char) - ord('a') - shift + 26) % 26 + ord('a'))

• Importantly, it is more secure than simple substitution ciphers

• However, it is still vulnerable to frequency analysis for long ciphertexts

Frequency Analysis

• Analyze the frequency of words in a text
• Find the most and least frequent words
• Use frequency analysis to break simple ciphers
• Implement the following functions:
  • compute_word_frequency
  • top_k_frequent_words
  • bottom_k_frequent_words

Frequency Analysis Functions

from collections import Counter

def compute_word_frequency(text: str) -> Counter:
    words = text.lower().split()
    frequency = Counter(words)
    return frequency

def top_k_frequent_words(frequency: Counter, k: int) -> list:
    return frequency.most_common(k)

def bottom_k_frequent_words(frequency: Counter, k: int) -> list:
    return frequency.most_common()[:-k-1:-1]

• Accept as input a string of plaintext or ciphertext
• Use the Counter class from the collections module
• Use functions to find the top and bottom k words

Running Frequency Analysis

# define a simple text string for analysis
text = "This is a sample text. " \
       "This text is for testing the frequency analysis. " \
       "Frequency analysis is useful."

# compute word frequency and return a Counter
frequency = compute_word_frequency(text)

# determine the top-3 most frequent words
top_k = 3
top_k_words = top_k_frequent_words(frequency, top_k)

# determine the bottom-3 least frequent words
bottom_k = 3
bottom_k_words = bottom_k_frequent_words(frequency, bottom_k)

• The frequency variable is a Counter with word frequency
• The top_k_words and bottom_k_words are lists of tuples

Output from Frequency Analysis

# display an output label
print("Word Frequency:")
# display the frequency of each word
for word, freq in frequency.items():
    print(f"{word}: {freq}")

Word Frequency:
this: 2
is: 3
a: 1
sample: 1
text.: 1
text: 1
for: 1
testing: 1
the: 1
frequency: 2
analysis.: 1
analysis: 1
useful.: 1

Most and Least Frequent Words

print(f"Top-{top_k} Most Frequent Words:")
for word, freq in top_k_words:
    print(f"{word}: {freq}")

print(f"\nBottom-{bottom_k} Least Frequent Words:")
for word, freq in bottom_k_words:
    print(f"{word}: {freq}")

Top-3 Most Frequent Words:
is: 3
this: 2
frequency: 2

Bottom-3 Least Frequent Words:
useful.: 1
analysis: 1
analysis.: 1

How does this help a cryptographer break a simple cipher?

How Can Frequency Analysis Be Used to Break Ciphers?

• Determine the frequency of words over plaintexts
• Analyze the frequency of words in a ciphertext
• Use the frequency analysis to determine the key
• Decrypt the ciphertext to plaintext using the key

Cryptography Review

Cryptography Roles

• Hashing
• Signatures
• Communication
• Cryptanalysis

SSH Keys

• Generate and add SSH keys
• Run SSH agent
• Clone repositories using SSH

Affine Ciphers

• Modular arithmetic
• Encryption and decryption

Vigenere Ciphers

• Repeating key shifts
• Enhances simple substitution

Frequency Analysis

• Compute word frequency
• Break simple ciphers