Suggested solutions to programming exercises
You can find some suggested solutions to the programming exercises in the course. There are many ways to solve the implementation tasks, but these suggested solutions typically aim for simplicity, with code reuse as a secondary goal.
You can find some supplementary files that are needed to run the code, but often not to understand the code, at the bottom.
SYM 1
- classic_shift.py
import rnd import classic_monoalphabetic class Shift(classic_monoalphabetic.NumericCipher): def __init__(self, alphabet = "abcdefghijklmnopqrstuvwxyz"): super(Shift, self).__init__(alphabet) def sample_key(self): return rnd.sample_from_uniform(self.length) def encrypt_numeric(self, k, x): return (x+k) % self.length def decrypt_numeric(self, k, x): return self.encrypt_numeric(-k, x) class ShiftAnalysis: def __init__(self, cipher, ciphertext): self._alphabet = cipher._alphabet self._ciphertext = ciphertext def frequency_analysis(self, target = 'e'): self._frequency = classic_monoalphabetic.Frequency(self._alphabet) self._frequency.process(self._ciphertext) return self._frequency.likely_shift(target) def exhaustive(self): return [ Shift(self._alphabet).decrypt(k, self._ciphertext) for k in range(len(self._alphabet)) ] if __name__ == "__main__": def _testing(): print "=== Testing " + __file__ known_answer_tests = [ (3, "hello", "khoor"), (3, "xyz", "abc") ] ed_tests = [ "testing xyz abc" ] classic_monoalphabetic.test_cipher(Shift(), known_answer_tests, ed_tests) plaintext = "dette er et eksempel som viser dekryptering" cipher = Shift() k = cipher.sample_key() c = cipher.encrypt(k, plaintext) analysis = ShiftAnalysis(cipher, c) assert(k == analysis.frequency_analysis()) _testing()
SYM 16
- classic_hill.py
# Only for block size 2 import rnd import gcd import classic_blockcipher class HillCipher(classic_blockcipher.NumericBlockCipher): def __init__(self, alphabet = "abcdefghijklmnopqrstuvwxyz"): super(HillCipher, self).__init__(alphabet, 2) def sample_key(self): while True: a = rnd.sample_from_uniform(self.length) b = rnd.sample_from_uniform(self.length) c = rnd.sample_from_uniform(self.length) d = rnd.sample_from_uniform(self.length) if gcd.gcd((a*d-b*c) % self.length, self.length) == 1: return (a,b,c,d) def decryption_key(self, k): a,b,c,d = k invdet = gcd.inverse_modulo(a*d-b*c, self.length) return (invdet*d % self.length, (-invdet*b) % self.length, (-invdet*c) % self.length, invdet*a % self.length) def encrypt_numeric(self, k, x): a,b,c,d = k u,v = x return ((a*u+b*v) % self.length, (c*u+v*d) % self.length) def decrypt_numeric(self, dk, x): return self.encrypt_numeric(dk, x) if __name__ == "__main__": def _testing(): print "=== Testing " + __file__ known_answer_tests = [ ((1,0,0,1), "helloo", "helloo"), ((0,1,1,0), "abcd", "badc") ] ed_tests = [ "testingxyzabcd" ] classic_blockcipher.test_cipher(HillCipher(), known_answer_tests, ed_tests) classic_blockcipher.test_cipher(HillCipher(), known_answer_tests, ed_tests) _testing()
DH 2
- square_and_multiply.py
import group import rnd def exponentiate(group, x, a): if a == 0: return group.identity if a < 0: return exponentiate(group, x.inverse(), -a) z = group.identity y = x while a > 0: if a % 2 == 1: z = z*y y = y*y a = a >> 1 return z if __name__ == "__main__": def _testing(): print "=== Testing " + __file__ G = group.PrimeFieldGroup(2039, 7, 2038) x = G.generator a = rnd.sample_from_uniform(G.order) assert(exponentiate(G, x, a) == x**a) _testing()
DH 10
- gcd.py
def gcd(a,b): assert(a >= 0 and b >= 0) while b > 0: r = a % b a = b b = r return a def extended_euclid(a,b): assert(a >= 0 and b >= 0) (s,t,d,u,r) = (1,0,a,0,b) while r > 0: (q,tmp_r) = divmod(d,r) tmp_s = s - q*u s = u d = r u = tmp_s r = tmp_r t = (d-a*s)/b return (d,s,t) def inverse_modulo(a,b): a = a%b if a < 0: a += b (d,s,t) = extended_euclid(a,b) assert(d == 1) return s % b if __name__ == "__main__": def _testing(): print "=== Testing " + __file__ assert(gcd(15, 25) == 5) assert(gcd(15, 26) == 1) assert(gcd(15, 3) == 3) assert(gcd(7,0) == 7) assert(gcd(0,7) == 7) assert(gcd(1,7) == 1) assert(extended_euclid(1,7) == (1,1,0)) assert(extended_euclid(7,1) == (1,0,1)) assert(extended_euclid(5,7) == (1,3,-2)) assert(extended_euclid(24,16) == (8,1,-1)) assert(extended_euclid(21,15) == (3,-2,3)) assert(inverse_modulo(5,7) == 3) assert(inverse_modulo(9,25) == 14) _testing()
DH 16/19/24
- dlog_pohlig_hellman.py
import group import chinese import dlog_exhaustive def _log_primepower(G, generator, element, p, power, subgroup_dlog): lg = 0 subgroup = group.CyclicSubGroup(G, generator**(p**(power-1)), p) for i in range(power): lg_digit = subgroup_dlog(subgroup, subgroup.generator, element**(p**(power-1-i))) if lg_digit is None: lg_digit = dlog_exhaustive.log(subgroup, subgroup.generator, element**(p**(power-1-i))) lg += lg_digit*(p**i) element /= generator**(lg_digit*(p**i)) assert(element == G.identity) return lg def _log_chinese(G, generator, element, subgroup_dlog): lgs = [] orders = [] for p,power in G.order_factorisation: r = G.order / p**power lgs.append(_log_primepower(G, generator**r, element**r, p, power, subgroup_dlog)) orders.append(p**power) lg,order = chinese.chinese_many(lgs, orders) assert(order == G.order) return lg def log(G, generator, element, subgroup_dlog = dlog_exhaustive.log): assert(G.order_factorisation is not None) return _log_chinese(G, generator, element, subgroup_dlog) if __name__ == "__main__": def _testing(): print "=== Testing " + __file__ import rnd import dlog_shanks import dlog_pollard_rho # Fixed group, fixed generator, fixed group element test. G = group.PrimeFieldGroup(19, 2, 18) G.order_factorisation = [ (2,1), (3,2) ] g = G.generator a = 7 x = g**a assert(log(G, g, x) == a) # Fixed group, fixed generator, random group element test. G = group.PrimeFieldGroup(73, 5, 72) g = G.generator a = rnd.sample_from_uniform(G.order) x = g**a G.order_factorisation = [ (8,1), (9,1) ] assert(log(G, g, x) == a) G.order_factorisation = [ (2,3), (9,1) ] assert(log(G, g, x) == a) G.order_factorisation = [ (2,3), (3,2) ] assert(log(G, g, x) == a) # Use different subgroup d.log. algorithm G.order_factorisation = [ (8,1), (9,1) ] assert(log(G, g, x, dlog_shanks.log) == a) G.order_factorisation = [ (2,3), (9,1) ] assert(log(G, g, x, dlog_shanks.log) == a) G.order_factorisation = [ (2,3), (3,2) ] assert(log(G, g, x, dlog_shanks.log) == a) assert(log(G, g, x, dlog_pollard_rho.log) == a) _testing()
DH 28
- dlog_shanks.py
def _build_table_and_giant_step(group, generator, table_size): table = {} i = 0 y = group.identity while i < table_size: table[y] = i y *= generator i += 1 return (table, y.inverse()) def _search_using_table(group, table, giant_step, element): j = 0 while element not in table: element *= giant_step j += 1 if j > group.order: raise ValueError("Element " + str(element) + " not in group") return (j, table[element]) def _standard_table_size(group): import integer_sqrt return integer_sqrt.isqrt_floor(group.order) def log_precompute(group, generator, table_size = None): if table_size is None: table_size = _standard_table_size(group) return _build_table_and_giant_step(group, generator, table_size) + (table_size,) def log(group, generator, element, precompute = None): if precompute is None: precompute = log_precompute(group, generator) (table, giant_step, table_size) = precompute (j,i) = _search_using_table(group, table, giant_step, element) return j*table_size + i if __name__ == "__main__": def _testing(): print "=== Testing " + __file__ import rnd import group # Fixed group, fixed generator, fixed group element test. G = group.PrimeFieldGroup(19, 2, 18) g = G.generator a = 7 x = g**a assert(log(G, g, x) == a) pc = log_precompute(G,g); assert(log(G, g, x, pc) == a) # Fixed group, random generator, random group element test. G = group.PrimeFieldGroup(23, 2, 11) gp = G.generator r = rnd.sample_from_uniform(1, G.order) g = gp**r a = rnd.sample_from_uniform(0, G.order) x = g**a assert(log(G, g, x) == a) # Invalid input checking. G = group.PrimeFieldGroup(19, 4, 9) g = G.generator x = group.PrimeFieldGroupElement(G, 2) did_raise = False try: a = log(G, g, x) except ValueError: did_raise = True assert(did_raise) _testing()
DH 34/38
- dlog_pollard_rho.py
import gcd def _partition(G, current): return hash(current) % 3 def _next(G, generator, element, pos): current,a,b = pos #assert(current == generator**a * element**b) partition = _partition(G, current) if partition == 0: return (current*generator, a+1 % G.order, b) elif partition == 1: return (current*current, 2*a % G.order, 2*b % G.order) else: return (current*element, a, b+1 % G.order) def _compute_dlog(G, a, b, c, d): lg = (a-c)*gcd.inverse_modulo(d-b % G.order, G.order) % G.order return lg def log(G, generator, element, max_steps = None): if max_steps is None: max_steps = 4*G.order slow = (element, 0, 1) fast = slow while max_steps > 0: slow = _next(G, generator, element, slow) fast = _next(G, generator, element, _next(G, generator, element, fast)) if slow[0] == fast[0]: if slow[1] == fast[1]: # print "+ fail I" return None return _compute_dlog(G, slow[1], slow[2], fast[1], fast[2]) max_steps -= 1 # print "+ fail II" return None if __name__ == "__main__": def _report_valid_fail_or_assert(result, correct_result): if result is None: print "+ failed to find d.log. This can happen, but should not happen too often." else: assert(result == correct_result) def _testing(): print "=== Testing " + __file__ import group import rnd # Fixed group, fixed generator, fixed group element test. G = group.PrimeFieldGroup(47, 4, 23) g = G.generator a = 7 x = g**a _report_valid_fail_or_assert(log(G, g, x), a) # Fixed group, fixed generator, random group element test. G = group.PrimeFieldGroup(47, 4, 23) g = G.generator a = rnd.sample_from_uniform(G.order) x = g**a _report_valid_fail_or_assert(log(G, g, x), a) # Fixed group, random generator, random group element test. G = group.PrimeFieldGroup(2063, 4, 1031) s = rnd.sample_from_uniform(1,G.order) g = G.generator**s a = rnd.sample_from_uniform(G.order) x = g**a _report_valid_fail_or_assert(log(G, g, x), a) # Fixed group, random generator, random group element test. G = group.PrimeFieldGroup(2147483783, 4, 1073741891) s = rnd.sample_from_uniform(1,G.order) g = G.generator**s a = rnd.sample_from_uniform(G.order) x = g**a _report_valid_fail_or_assert(log(G, g, x), a) _testing()
DH 42/48
- primality.py
import math, rnd, jacobi, sieve def _fermat_test(candidate, witness): return pow(witness, candidate-1, candidate) == 1 def _soloway_strassen_test(candidate, witness): return pow(witness, (candidate-1)/2, candidate) == jacobi.symbol(witness, candidate)%candidate def is_pseudo_prime(candidate, iterations = 80, test = None): assert(candidate > 1) if test is None or test == "soloway-strassen" or test is _soloway_strassen_test: witness_test = _soloway_strassen_test elif test == "fermat" or test is _fermat_test: witness_test = _fermat_test else: raise ValueError("do not know about test " + test + "!") for _ in range(iterations): witness = rnd.sample_from_uniform(2,candidate) if not witness_test(candidate, witness): return False return True def _brute_search_for_pseudo_prime(starting_at): if starting_at % 2 == 0: starting_at += 1 while True: if is_pseudo_prime(starting_at): return starting_at starting_at += 2 def next_pseudo_prime(starting_at, small_primes = None, limit = None): assert(starting_at > 0) if small_primes is None and limit is None: return _brute_search_for_pseudo_prime(starting_at) if small_primes is None: small_primes = sieve.small_primes(limit) length = 2*int(math.log(starting_at))+1 while True: candidates = sieve.sieve_range(starting_at, starting_at+length, small_primes) for i in candidates: if is_pseudo_prime(i): return i starting_at += length if __name__ == "__main__": def _testing(): print "=== Testing " + __file__ for _x in [ 41, 43, 1009, 519335238006017621936447751853 ]: assert(is_pseudo_prime(_x)) assert(is_pseudo_prime(_x, test = _fermat_test)) assert(is_pseudo_prime(_x, test = _soloway_strassen_test)) for _x in [ 27, 105, 519335238006017621936447751857 ]: assert(not is_pseudo_prime(_x, test = _fermat_test)) assert(not is_pseudo_prime(_x, test = _soloway_strassen_test)) start = 10**30 j = start for _ in range(10): j = next_pseudo_prime(j+1, limit = 30) assert(j-start == 687) assert(next_pseudo_prime(10**10) == 10000000019) assert(next_pseudo_prime(10**40, [ 2, 3, 5, 7 ]) == 10000000000000000000000000000000000000121) assert(next_pseudo_prime(10**40, limit = 30) == 10000000000000000000000000000000000000121) _testing()
Supplemental
group.py
- group.py
# A cyclic group needs an identity, a generator and an order import gcd class CyclicSubGroup: def __init__(self, group, generator, order): self._group = group self.identity = group.identity self.generator = generator self.order = order class PrimeFieldGroupElement: def __init__(self, pfg, value): self._pfg = pfg self._value = value % self._pfg._prime assert(self._value != 0) def __repr__(self): return str(self._value) def __hash__(self): return hash(self._value) def __eq__(self, y): assert(self._pfg == y._pfg) return self._value == y._value def __ne__(self, y): assert(self._pfg == y._pfg) return self._value != y._value def __mul__(self, y): assert(self._pfg == y._pfg) return PrimeFieldGroupElement(self._pfg, (self._value * y._value) % self._pfg._prime) def __pow__(self, a): return PrimeFieldGroupElement(self._pfg, pow(self._value, a, self._pfg._prime)) def __div__(self, y): assert(self._pfg == y._pfg) return self*y.inverse() def __truediv__(self, y): assert(self._pfg == y._pfg) return self*y.inverse() def inverse(self): return PrimeFieldGroupElement(self._pfg, gcd.inverse_modulo(self._value, self._pfg._prime)) class PrimeFieldGroup: def __init__(self, prime, generator, order): self._prime = prime self.identity = PrimeFieldGroupElement(self, 1) self.generator = PrimeFieldGroupElement(self, generator) self.order = order def embed(self, value): return PrimeFieldGroupElement(self, value) class PrimeFieldECGroupElement: def __init__(self, ec, point): self._ec = ec self._point = point assert(self._ec.is_on_curve(point)) def __repr__(self): return str(self._point) def __hash__(self): return hash(self._point) def __eq__(self, y): assert(self._ec == y._ec) return self._point == y._point def __ne__(self, y): assert(self._ec == y._ec) return self._point != y._point def _lambda_for_double(self): lambda_den_inverse = gcd.inverse_modulo(2*self._point[1] % self._ec._prime, self._ec._prime) return (3*self._point[0]**2 + self._ec._A) * lambda_den_inverse % self._ec._prime def _lambda_for_distinct_points(self, point): lambda_den_inverse = gcd.inverse_modulo((self._point[0] - point[0]) % self._ec._prime, self._ec._prime) return (self._point[1] - point[1])*lambda_den_inverse % self._ec._prime def _sum_from_lambda(self, lmbd, x2): x3 = (lmbd*lmbd - self._point[0] - x2) % self._ec._prime y3 = (lmbd*(self._point[0] - x3) - self._point[1]) % self._ec._prime return PrimeFieldECGroupElement(self._ec, (x3,y3)) def __mul__(self, y): assert(self._ec == y._ec) if self == self._ec.identity: return y if y == self._ec.identity: return self if self._point[0] == y._point[0]: if self._point[1] == -y._point[1] % y._ec._prime: return self._ec.identity lmbd = self._lambda_for_double() else: lmbd = self._lambda_for_distinct_points(y._point) return self._sum_from_lambda(lmbd, y._point[0]) def __pow__(self, a): assert(a >= 0) if a == 0: return self._ec.identity if a == 1: return self result = self.__pow__(a >> 1) result = result*result if a % 2 == 1: return result*self return result def inverse(self): return PrimeFieldECGroupElement(self._ec, (self._point[0], self._ec._prime - self._point[1])) class PrimeFieldECGroup: def __init__(self, prime, A, B, generator, order): self._prime = prime self._A = A self._B = B self.identity = PrimeFieldECGroupElement(self, (0)) self.generator = PrimeFieldECGroupElement(self, generator) self.order = order def is_on_curve(self, point): if point == (0): return True lhs = (point[1]*point[1]) % self._prime rhs = (point[0]*(point[0]*point[0] + self._A) + self._B) % self._prime return lhs == rhs if __name__ == "__main__": def _testing(): print "=== Testing " + __file__ G = PrimeFieldGroup(19, 2, 18) assert(G.generator**257 == G.embed(13)) G = PrimeFieldECGroup(13, 1, 2, (6,4), 12) P = G.generator**3 Q = G.generator**5 R = G.generator**7 S = G.generator**4 assert(P*Q*S == G.identity) assert(Q*R == G.identity) assert(P*S == R) assert(G.generator*G.generator.inverse() == G.identity) assert(G.generator**12 == G.identity) _testing()
rnd.py
- rnd.py
import random _prng = random.SystemRandom() def sample_from_uniform(a, b = None): if b is None: b = a a = 0 return _prng.randint(a, b-1)
classic_monoalphabetic.py
- classic_monoalphabetic.py
class Cipher(object): def __init__(self, alphabet): self._alphabet = alphabet self.length = len(alphabet) def encryption_key(self, k): return k def decryption_key(self, k): return k def encrypt_letter(self, k, x): assert(False) def decrypt_letter(self, k, x): assert(False) def __workhorse(self, k, m, f): def keyed_f(x): return f(k,x) return "".join(map(keyed_f, m)) def encrypt(self, k, m): ek = self.encryption_key(k) return self.__workhorse(ek, m, self.encrypt_letter) def decrypt(self, k, c): dk = self.decryption_key(k) return self.__workhorse(dk, c, self.decrypt_letter) class NumericCipher(Cipher): def __init__(self, alphabet): super(NumericCipher, self).__init__(alphabet) self._numeric = { c:i for i,c in enumerate(alphabet) } def encrypt_numeric(self, k, x): assert(False) def decrypt_numeric(self, k, x): assert(False) def __workhorse(self, k, x, f): if x in self._numeric: return self._alphabet[f(k, self._numeric[x])] else: return x def encrypt_letter(self, k,x): return self.__workhorse(k, x, self.encrypt_numeric) def decrypt_letter(self, k,x): return self.__workhorse(k, x, self.decrypt_numeric) class Ngram: def __init__(self, alphabet, l): self._alphabet = alphabet self._length = l self._result = dict() def process(self, x): y = filter(lambda c: c in self._alphabet, x) n = len(y) // self._length for i in range(n): c = y[i*self._length:(i+1)*self._length] if c in self._result: self._result[c] += 1 else: self._result[c] = 1 # We ignore partial blocks, if any def most_common(self, n = 1): if n == 1: max = 0 for c in self._result: if self._result[c] >= max: max = self._result[c] common = c return common else: return [ x[0] for x in sorted(self._result.items(), reverse=True, key=lambda t: t[1])[:n] ] class Frequency: def __init__(self, alphabet): self._alphabet = alphabet self._numeric = { c:i for i,c in enumerate(alphabet) } self._result = { c:0 for c in alphabet } def process(self, x): for c in x: if c in self._result: self._result[c] += 1 def distribution(self, shift = 0): if shift == 0: return self._result result = dict() for c in self._result: result[self._alphabet[self._numeric[c]+shift % len(self._alphabet)]] = c return result def most_common(self): max = 0 for c in self._result: if self._result[c] >= max: max = self._result[c] common = c return common def likely_shift(self, target = 'e'): return (self._numeric[self.most_common()] - self._numeric[target]) % len(self._alphabet) def test_cipher(cipher, known_answers, ed_tests): for k,m,c in known_answers: assert(cipher.encrypt(k,m) == c) assert(cipher.decrypt(k,c) == m) for m in ed_tests: k = cipher.sample_key() assert(cipher.decrypt(k, cipher.encrypt(k, m)) == m) if __name__ == "__main__": class NullCipher(Cipher): def __init__(self): super(NullCipher, self).__init__("abcdefghijklmnopqrstuvwxyz") def sample_key(self): return None def encrypt_letter(self, k, x): return x def decrypt_letter(self, k, x): return x class NullNumericCipher(NumericCipher): def __init__(self): super(NullNumericCipher, self).__init__("abcdefghijklmnopqrstuvwxyz") def sample_key(self): return None def encrypt_numeric(self, k, x): return x def decrypt_numeric(self, k, x): return x def _testing(): print "=== Testing " + __file__ known_answer_tests = [ (None, "hello", "hello"), (None, "abc d", "abc d") ] ed_tests = [ "testing xyz abc" ] test_cipher(NullCipher(), known_answer_tests, ed_tests) test_cipher(NullNumericCipher(), known_answer_tests, ed_tests) freq = Frequency("abcdefghijklmnopqrstuvwxyz") freq.process("abbcccddddeeeeeffffggghhi") answer = { 'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':4, 'g':3, 'h':2, 'i':1 } answer.update({ c:0 for c in "jklmnopqrstuvwxyz" }) assert(freq.most_common() == 'e') assert(freq.likely_shift() == 0) assert(freq.distribution() == answer) ngram = Ngram("abcdefghijklmnopqrstuvwxyz", 2) ngram.process("aaaaababbababaccccddee") answer = { 'aa':2, 'ab':2, 'ba':3, 'cc':2, 'dd':1, 'ee':1 } assert(ngram.most_common() == 'ba') for c in ngram._result: if c in answer: assert(ngram._result[c] == answer[c]) else: assert(ngram._result[c] == 0) _testing()
classic_blockcipher.py
- classic_blockcipher.py
class BlockCipher(object): def __init__(self, alphabet, blocklength): self._alphabet = alphabet self.length = len(alphabet) self.blocklength = blocklength def encryption_key(self, k): return k def decryption_key(self, k): return k def encrypt_block(self, k, x): assert(False) def decrypt_block(self, k, x): assert(False) def __workhorse(self, k, m, f): assert(len(m) % self.blocklength == 0) nblocks = len(m) // self.blocklength blocks = [ m[i*self.blocklength:(i+1)*self.blocklength] for i in range(nblocks) ] return "".join([ f(k,x) for x in blocks ]) def encrypt(self, k, m, padding = None): return self.__workhorse(self.encryption_key(k), m, self.encrypt_block) def decrypt(self, k, m, padding = None): return self.__workhorse(self.decryption_key(k), m, self.decrypt_block) class NumericBlockCipher(BlockCipher): def __init__(self, alphabet, blocklength): super(NumericBlockCipher, self).__init__(alphabet, blocklength) self._numeric = { c:i for i,c in enumerate(alphabet) } def encrypt_numeric(self, k, x): assert(False) def decrypt_numeric(self, k, x): assert(False) def __workhorse(self, k, x, f): y = [ self._numeric[c] for c in x ] z = f(k,y) return "".join([ self._alphabet[c] for c in z ]) def encrypt_block(self, k, x): return self.__workhorse(k, x, self.encrypt_numeric) def decrypt_block(self, k, x): return self.__workhorse(k, x, self.decrypt_numeric) def test_cipher(cipher, known_answers, ed_tests): for k,m,c in known_answers: assert(cipher.encrypt(k,m) == c) assert(cipher.decrypt(k,c) == m) for m in ed_tests: k = cipher.sample_key() assert(cipher.decrypt(k, cipher.encrypt(k, m)) == m) if __name__ == "__main__": class NullBlockCipher(BlockCipher): def __init__(self, blocklength): super(NullBlockCipher, self).__init__("abcdefghijklmnopqrstuvwxyz", blocklength) def sample_key(self): return None def encrypt_block(self, k, x): return x def decrypt_block(self, k, x): return x class NullNumericBlockCipher(NumericBlockCipher): def __init__(self, blocklength): super(NullNumericBlockCipher, self).__init__("abcdefghijklmnopqrstuvwxyz", blocklength) def sample_key(self): return None def encrypt_numeric(self, k, x): return x def decrypt_numeric(self, k, x): return x def _testing(): print "=== Testing " + __file__ known_answer_tests = [ (None, "helloo", "helloo"), (None, "abcd", "abcd") ] ed_tests = [ "testingxyzabcd" ] test_cipher(NullBlockCipher(2), known_answer_tests, ed_tests) test_cipher(NullNumericBlockCipher(2), known_answer_tests, ed_tests) _testing()
jacobi.py
- jacobi.py
import gcd _square_powers_of_minus_one = [ None, 1, None, -1, None, -1, None, 1 ] def _extract_powers_of_2(x, n, result): while x > 1 and x%4 == 0: x /= 4 if x%2 == 0: return (x/2,result*_square_powers_of_minus_one[n % 8]) return (x,result) def _reciprocity(x, n, result): if x%4 != 1 and n%4 != 1: return (n,x,-result) return (n,x,result) def symbol(x,n): assert(x > 0 and n > 1 and n%2 == 1) x = x%n if gcd.gcd(x,n) > 1: return 0 (x,result) = _extract_powers_of_2(x,n,1) while x > 1: (x,n,result) = _reciprocity(x,n,result) x = x%n (x,result) = _extract_powers_of_2(x,n,result) return result if __name__ == "__main__": def _testing(): print "=== Testing " + __file__ import rnd assert(symbol(17,23) == -1) assert(symbol(23,17) == -1) p = 41 x = rnd.sample_from_uniform(1,p) assert(symbol(x,p)%p == pow(x,(p-1)/2,p)) n = 2*rnd.sample_from_uniform(3,10**100)+1 x = rnd.sample_from_uniform(1,10**50)**2 if gcd.gcd(x,n) > 1: assert(symbol(x,n) == 0) else: assert(symbol(x,n) == 1) _testing()