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)[0]

Bit-based

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)