#!/usr/bin/env python -i import random from fractions import gcd class Coding: def encode(self, chars): nums = [] for char in chars: char = char.upper() nums.append(ord(char) - ord('A')) return nums def decode(self, nums): chars = [] for num in nums: chars.append(chr(num + ord('A'))) return chars class AffineCipher: m = 0 k = [0, 0] ce = Coding() # The encoding engine def __init__(self, m = 26): self.keygen(m) def egcd(self,a, b): if a == 0: return (b, 0, 1) else: g, y, x = self.egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(self, a, m): g, x, y = self.egcd(a, m) if g != 1: raise Exception('modular inverse for '+a+' modulo '+m+ ' does not exist') else: return x % m def keygen(self, m = 26): self.m = m # This is a cryptographic safe pseudorandom number generator # (PRG), in contrast to the build-in PRG. rand = random.SystemRandom() # Selects random numbers in the range [0, m-1], as long as the # first one is coprime with m. a_ok = False while not a_ok: self.k[0] = rand.randrange(0, self.m) a_ok = (gcd(self.m, self.k[0]) == 1) self.k[1] = rand.randrange(0, self.m) return True def get_naive_security(self): # Approximately how many bits must be guessed in order to guess # the key? Note that this approximation is too high. Why? return 2 * self.m.bit_length() def encrypt(self, msg): # msg should be a string without any spaces. Case insensitive. chars = list(msg) nums = self.ce.encode(chars) for i in range(0, len(nums)): nums[i] = (self.k[0] * nums[i] + self.k[1]) % self.m chars = self.ce.decode(nums) return ''.join(chars) def decrypt(self, c): # c should be a string without any spaces. Case insensitive. chars = list(c) nums = self.ce.encode(chars) for i in range(0, len(nums)): nums[i] = (self.modinv(self.k[0], self.m) * (nums[i] - self.k[1])) % self.m chars = self.ce.decode(nums) return ''.join(chars) def bruteforce(self, c): # You need to complete this snippet yourself. Here's the # structure you should follow. # We need to generate all valid keys. Since we want to try all # keys, we should do it systematically, starting with the first # and ending with the last. The key generation routine is # therefore not good -- it's a random algorithm, but we can # copy some of the code from it. triedall = False while not triedall: # Generate the next key. # # To avoid manual labour, search for the given string # instead of printing everything. print self.k, self.decrypt(c) # Remember to set triedall = True when you have generated # the last key, which ought to be (25, 25). # For elegance: Reset k to the key it was before we started the # search. print """ Usage: python -i affine.py or: ./affine.py (if you have set the executable flag) The file provides the class AffineCipher, which you can use by typing cs = AffineCipher() If no argument is given, the plain text space is 26 by default. cs is now an variable holding an instance of the cryptosystem. It contains the following methods: keygen(m): Generates a new key with plaintext space size m encrypt(msg): Encrypts the string msg decrypt(c): Decrypts the ciphertext c get_naive_security(): Gives a crude approximation of the keylength in bits. The figure is too large, why? bruteforce(c): Does a bruteforce search for the key. You need to implement this one yourself! Example cs = AffineCipher(26) c1 = cs.encrypt('HEI') c1 cs.decrypt(c1) Exercise: Decrypt the following ciphertext. You can assume that the system is instantiated with m = 26, but you need to implement the bruteforce method yourself. c1 = 'BILEEHPNZA' It is known that the plaintext contains the substring 'GU'. """