Mcrypt

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”.

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 &#91;m^k for m, k in zip(plaintext, key)&#93;

def decode(ciphertext, key):
	assert len(ciphertext) <= len(key)
	return &#91;c^k for c, k in zip(ciphertext, key)&#93;

valid_chars = set(c for c in string.printable&#91;:62&#93;)
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(&#91;BITS&#91;e&#93; for e in b&#93;)

def seq_to_bits(seq):
    return &#91;0 if b == '0' else 1 for b in seq&#93;

def pad_bits(bits, pad):
    """pads seq with leading 0s up to length pad"""
    assert len(bits) <= pad
    return &#91;0&#93; * (pad - len(bits)) + bits
        
def convert_to_bits(n):
    """converts an integer `n` to bit array"""
    result = &#91;&#93;
    if n == 0:
        return &#91;0&#93;
    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