This function is an extensive block algorithm such as CBC, OFB, CFB, ECB cipher modes DES, TripleDES, Blowfish (default), 3-WAY, SAFER-SK64, SAFER-SK128, TWOFISH, TEA, RC2 and GOST. Interface to the mcrypt library to support. In addition, it supports RC6 and IDEA, which are described as “not free”.
Category: cryptography
Alice and Bob
from urllib import urlopen, urlencode import json base = "http://hgehoge.com" Alice = base + "/alice" Bob = base + "bob" def check_output(output): data = output.read() if output.getcode() != 200: raise Exception(data) data = json.loads(data) return data def get_pg(): output = urlopen(base) data = check_output(output) return data def initialize(person): data = {'type':'init'} output = urlopen(person, urlencode(data)) data = check_output(output) return data def send_key(person, token, public, name): data = {'type':'key', 'token':token, 'public': public, 'name':name} output = urlopen(person, urlencode(data)) data = check_output(output) return data daf recieve_msg(person, token): data = {'type':'msg', 'token':token} output = urlopen(person, urlencode(data)) data = check_output(output) return data def send_msg(person, token, cipher, iv): data = {'type':'msg', 'token':token, 'message':cipher, 'iv':iv} output = urlopen(person, urlencode(data)) data = check_output(output) return data
a≡b (mod c)
a≡b (mod c) は a-bがcで割り切れること。
10≡0 (mod 5)
14≡5 (mod 3)
13≡-3 (mod 2)
from Crypto.Util.number import inverse def message_value(message): message = bits_to_string(pad_to_block(convert_to_bits(message), 8)) return cutchoose.bill_value(message) def remove_nonce(bill, nonce): big_nonce = pow(nonce, cutchoose.BANK_PUBLIC_KEY[0], cutchoose.BANK_PUBLIC_KEY[1]) nonce_inverse = inverse(big_nonce, cutchoose.BANK_PUBLIC_KEY[1]) message = (bill * nonce_inverse) % cutchoose.BANK_PUBLIC_KEY[1] return message def _verify(bills, nonces, value): for bill, nonce in zip(bills, nonces): message = remove_nonce(Bill, nonce) test_value = message_value(message) if test_value != value: return False
Cut and choose
import cutchoose from unit6_util import string_to_bits, bits_to_int, pad_to_block, bits_to_string, convert_to_bit def _verify(bills, nonces, value): return False cutchoose.verify = _verify def test(): bills = cutchoose.generate_bills(50) i = cutchoose.pick_and_sign_bills(bills) nonces = cutchoose.send_nonces(i) signed = cutchoose.verify_bills_and_return_signed(nonces, 50) assert signed is not None assert bills[i] == pow(signed, cutchoose.BANK_PUBLIC_KEY[0], cutchoose.BANK_PUBLIC_KEY[1]) bills = cutchoose.cheat_generate_bills(50, 100) i = cutchoose.pick_and_sign_bills(bills) nonces = cutchoose.send_nonces(i) signed = cutchoose.verify_bills_and_return_signed(nonces, 50) assert signed is None
beast attack
import urllib import json import base64 BLOCK_SIZE = 128 site = "http://cs387.udacity-extras.appspot.com/beast" def unencode_json(txt): d = json.loads(txt) return dict((str(k), base64.urlsafe_b64decode(str(v))) for k, v in d.iteritems()) def _send(attack=None, token=None): data = {} if attack is not None: data["attack"] = base64.urlsafe_b64encode(attack) if token is not None: data["token"] = base64.urlsafe_b64encode(token) json = urllib.urlopen(site, urllib.urlencode(data)).read() json = unencode_json(json) return json _TOKEN = None def send(attack=None): global _TOKEN json = _send(attack, _TOKEN) _TOKEN = json["token"] return json["message"]
Asymmetric Cryptosystems
e = 65537 n = 132177882185373774813945506243321607011510930684897434818595314234725602493934515403833460241072842788085178405842019124354553719616350676051289956113618487539608319422698056216887276531560386229271076862408823338669795520077783060068491144890490733649000321192437210365603856143989888494731654785043992278251 m1 = 387 s1 = 104694095966994423550399840405679271451689287439740118881968798612714798360187905616965324945306116261186514828745033919423253353071142760352995900515279740753864505327750319034602409274084867637277266750899735986681083836544151016817569622466120342654469777762743360212628271549581658814852850038900877029382 m2 = 2 s2 = 18269259493999292542402899855086766469838750310113238685472900147571691729574239379292239589580462883199555239659513821547589498977376834615709314449943085101697266417531578751311966354219681199183298006299399765358783274424349074040973733214578342738572625956971005052398172213596798751992841512724116639637 m3 = 774 s3 = 0 def mod_exp(a, b, q): val = 1 mult = a while b > 0: odd = b & 1 if odd == 1: val = (val * mult) % q b -= 1 if b == 0: break mult = (mult * mult) % q b = b >> 1 return val def verify_signature(e, n, m, s): assert m == mod_exp(s, e, n)
Diffie-Hellman key exchange
import string P = 1267650600228229401496703205223 g = 3 g_a = 142621255265782287951127214876 g_b = 609743693736442153553407144551 n_multiplications = 26 def mod_exp(a, b, q): """return a**b % q""" val = 1 mult = a while b > 0 add = b & 1 if odd == 1: val = (val * mult) % q b -= 1 if b == 0: break mult = (mult * mult) % q b = b >> 1 return val def count_multiplications(exponent): """return the number of multiplications necessary to raise a number to 'exponent'""" bits = convert_to_bits(exponent) return len(bits) + sum(b for b in bits) -2 def encode(plaintext, key): assert len(plaintext) <= len(key) return [m^k for m, k in zip(plaintext, key)] def decode(ciphertext, key): assert len(ciphertext) <= len(key) return [c^k for c, k in zip(ciphertext, key)] valid_chars = set(c for c in string.printable[:62]) valid_chars.add('') def is_valid(decode_guess): return (len(decode_guess) == 14 and all(d in valid_chars for d in decode_guess)) BITS = ('0', '1') ASCII_BITS = 7 def display_bits(b): """converts list of {0, 1}* to string""" return ''.join([BITS[e] for e in b]) def seq_to_bits(seq): return [0 if b == '0' else 1 for b in seq] def pad_bits(bits, pad): """pads seq with leading 0s up to length pad""" assert len(bits) <= pad return [0] * (pad - len(bits)) + bits def convert_to_bits(n): """converts an integer `n` to bit array""" result = [] if n == 0: return [0] while n > 0: result = [(n % 2)] + result n = n / 2 return result def string_to_bits(s): def chr_to_bit(c): return pad_bits(convert_to_bits(ord(c)), ASCII_BITS) return [b for group in map(chr_to_bit, s) for b in group] def bits_to_char(b): assert len(b) == ASCII_BITS value = 0 for e in b: value = (value * 2) + e return chr(value) def list_to_string(p): return ''.join(p) def bits_to_string(b): return ''.join([bits_to_char(b[i:i + ASCII_BITS]) for i in range(0, len(b), ASCII_BITS)])
Rabin Miller Primality Theory
from hw3_4_util import mod_exp from random import randrange def rabin_miller(n, target=128): """returns True if prob(^n' is prime) <= 2**(-'target')""" def calculate_t(n): n = n - 1 t = 0 while n % 2 == 0: n = n / 2 t += 1 return t if n % 2 == 0: return False t = calculate_t(n) s = (n - 1)/(2 ** t) n_tests = target / 2 tried = set() if n_tests > n: raise Exception("n i s too small") for i in range(n_tests): while True: a = randrange(1, n) if a not in tried: break tried.add(a) if mod_exp(a, s, n) == 1: continue found = False for j in range(0, t): if mod_exp(a, 2**j*s, n) == (n - 1): found = True break if not found: return False return True
Primitive Roots
from hw3_t_util import mod_exp def primitive_roots(n): """Returns all the primitive_roots of n""" roots = [] def is_primitive_root(r): s = set() for i in range(1, n): t = mod_exp(r, i, n) if t in s: return False s.add(t) return True for i in range(2, n): if is_primitive_root(i): roots.append(i) return roots def test(): assert primitive_roots(3) == [2] assert primitive_roots(5) == [2, 3] print "test pass"
finding a large prime
def find_prime_near(x):
while True:
if is_prime(x):
return x
x = x + 1
Naive primality test
def is_prime(x):
for i in range(2, x):
if x % i == 0: return False
return True
Faster Primality Testing
probabalistic test
passes the test, p(x is composite) <= 2 -k
Fermat's Little Theorem:
if p is prime, 1 <= a < p => ap-1 = 1 mod p