Understanding the Role of Cryptography in Security
November 25, 2024
ssh-keygen program! What do the public and private keys look like?Cryptography Reminders
% operator in these functions?gcd and mod_inverse functions do?gcd Functiona = 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) = 1What do outputs show about the gcd function’s behavior?
mod_inverse Functiona = 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) = 11What is the behavior of the mod_inverse function?
x such that when a is multiplied by x and then divided by m, the remainder is 1!mod_inversea = 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 1mod_inverse function return the correct result?mod_inverse function?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 uyvifucdef 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 synapseLessons Learned about Affine Cipher
Affine ciphers use modular arithmetic and inverses
Code segment from the encryption function:
encrypted_char = (a * x + b) % 26Code segment from the decryption function:
decrypted_char = (a_inv * (y - b)) % 26Importantly, it is vulnerable to frequency analysis attacks
However, it illustrates role of modular arithmetic and primes!
Any questions about the encrypt or decrypt functions?
key to encrypt messagesvigenere_encryptvigenere_decryptdef 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 wwxencidef 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 synapseLessons 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
compute_word_frequencytop_k_frequent_wordsbottom_k_frequent_wordsfrom 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]Counter class from the collections modulek words# 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)frequency variable is a Counter with word frequencytop_k_words and bottom_k_words are lists of tuplesprint(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.: 1How does this help a cryptographer break a simple cipher?
Security Synapse