Crypto Tools¶

Notes from reading and function prototypes

Character-based string manipulation and statistics¶

from collections import defaultdict
import logging
from random import choice
from scipy.stats import chisquare
from string import ascii_lowercase as alphabet
from typing import List, Dict
def rot(given: str, n: int) -> str:
"""
Passes anything that is not lowercase ascii
"""
return "".join(
[
alphabet[(alphabet.index(letter.lower()) + n) % 26]
if letter.lower() in alphabet
else letter
for letter in given
]
)
en_freq = {
"e": 0.1201,
"t": 0.0911,
"a": 0.0813,
"o": 0.0768,
"i": 0.0731,
"n": 0.0695,
"s": 0.0628,
"r": 0.0602,
"h": 0.0592,
"d": 0.0432,
"l": 0.0398,
"u": 0.0288,
"c": 0.0271,
"m": 0.0261,
"f": 0.0230,
"y": 0.0211,
"w": 0.0209,
"g": 0.0203,
"p": 0.0182,
"b": 0.0149,
"v": 0.0111,
"k": 0.0069,
"x": 0.0017,
"q": 0.0011,
"j": 0.0010,
"z": 0.0007,
}
def compare_frequency(given: str, lang_dict: Dict[str, float] = en_freq) -> float:
"""
Calculate frequency distribution, test against language, return liklihood of belonging
One sided Chi Squared Test: lower results signify that given more likely drew from the same distribution as lang_dict
"""
given = given.replace(" ", "")
freq = defaultdict()
for letter in lang_dict.keys():
freq[letter] = 0
for letter in given:
if letter.lower() in lang_dict.keys():
freq[letter.lower()] += 1 / len(given)
else:
logging.warning(f"{letter} not in language alphabet")
observed = [freq[k] for k in alphabet]
expected = [lang_dict[k] for k in alphabet]
return chisquare(observed, expected)

Large number math shortcuts¶

# Fermat Primality Test -- (Paar, Pezl. Pg 189)
# probabalistic on s
# beware Carmichael numbers (false positives)

def is_prime_fermat(candidate: int, s: int) -> bool:
candidate = abs(candidate)
for i in range(s):
try:
alpha = choice(range(2, candidate - 2))
except IndexError:  # lookup candidate <= 4
if candidate in [2, 3]:
return True
else:
return False
if alpha ** (candidate - 1) % candidate != 1:
return False
return True
# Fast decryption with Chinese Remainder Theorem (CRT) -- (Paar, Pezl. Pg 184)

def mod_multiplicative_inverse(remainder: int, base: int) -> int:
"""
What x solves: x * remainder % base == 1?
"""
for x in range(1, base):
if ((remainder % base) * (x % base)) % base == 1:
return x
return None

def decrypt_crt(ciphertext: int, p: int, q: int, d: int) -> int:
"""
"total speedup obtained through CRT is a factor of 4" (Paar 186).
"""
ciphertext_p = ciphertext % p
ciphertext_q = ciphertext % q
plain_p = ciphertext_p ** (d % (p - 1)) % p
plain_q = ciphertext_q ** (d % (q - 1)) % q
cp = mod_multiplicative_inverse(q, p)
cq = mod_multiplicative_inverse(p, q)
return (q * cp * plain_p + p * cq * plain_q) % (p * q)