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 &#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

Hash Collision

from Crypto.Cipher import AES
from copy import copy

def find_collision(message):
	new_message = copy(message)

	return new message

def test():
	messages = ["Trust, but verify. -a signature phrase of President Ronald Reagan",
                "The best way to find out if you can trust somebody is to trust them. (Ernest Hemingway)",
                "If you reveal your secrets to the wind, you should not blame the wind for revealing them to the trees. (Khalil Gibran)",
                "I am not very good at keeping secrets at all! If you want your secret kept do not tell me! (Miley Cyrus)",
                "This message is exactly sixty four characters long and no longer"]
    for m in messages:
    	m = string_to_bits(m)
    	new_message = find_collision(m)
    	if not check(m, new_message):
    		print "Failed to find a collision for '%s'" % m
    		return False
    return True

from Crypto.Cipher import AES

BITS = ('0', '1')
ASCII_BITS = 8

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 &#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)])

def pad_bits_append(small, size):
    # as mentioned in lecture, simply padding with
    # zeros is not a robust way way of padding
    # as there is no way of knowing the actual length
    # of the file, but this is good enough
    # for the purpose of this exercise
    diff = max(0, size - len(small))
    return small + [0] * diff

def xor_bits(bits_a, bits_b):
    """returns a new bit array that is the xor of `bits_a` and `bits_b`"""
    return [a^b for a, b in zip(bits_a, bits_b)]

def bits_inc(bits):
    """modifies `bits` array in place to increment by one
    
    wraps back to zero if `bits` is at its maximum value (each bit is 1)
    """
    # start at the least significant bit and work towards
    # the most significant bit
    for i in range(len(bits) - 1, -1, -1):
        if bits[i] == 0:
            bits[i] = 1
            break
        else:
            bits[i] = 0

def aes_encoder(block, key):
    block = pad_bits_append(block, len(key))
    # the pycrypto library expects the key and block in 8 bit ascii 
    # encoded strings so we have to convert from the bit array
    block = bits_to_string(block)
    key = bits_to_string(key)
    ecb = AES.new(key, AES.MODE_ECB)
    return string_to_bits(ecb.encrypt(block))

def get_block(plaintext, i, block_size):
    """returns the ith block of `plaintext`"""
    start = i * block_size
    if start >= len(plaintext):
        return None
    end = min(len(plaintext), (i+1) * block_size)
    return pad_bits_append(plaintext[start:end], block_size)

def get_blocks(plaintext, block_size):
    """iterates through the blocks of blocksize"""
    i = 0
    while True:
        start = i * block_size
        if start >= len(plaintext):
            break
        end = (i+1) * block_size
        i += 1
        yield pad_bits_append(plaintext[start:end], block_size)

def _counter_mode_inner(plaintext, key, ctr, block_enc):
    eblock = block_enc(ctr, key)
    cblock = xor_bits(eblock, plaintext)
    bits_inc(ctr)
    return cblock

def counter_mode(plaintext, key, ctr, block_size, block_enc):
    """Return the counter mode encoding of `plaintext"""
    cipher = []
    # break the plaintext into blocks
    # and encode each one
    for block in get_blocks(plaintext, block_size):
        cblock = _counter_mode_inner(block, key, ctr, block_enc)
        cipher.extend(cblock)
    return cipher

def counter_mode_hash(plaintext):
    block_size, block_enc, key, ctr = hash_inputs()
    hash_ = None
    for block in get_blocks(plaintext, block_size):
        cblock = _counter_mode_inner(block, key, ctr, block_enc)
        if hash_ is None:
            hash_ = cblock
        else:
            hash_ = xor_bits(hash_, cblock)
    return hash_

def hash_inputs():
    block_size = 128
    block_enc = aes_encoder
    key = string_to_bits("Vs7mHNk8e39%CXeY")
    ctr = [0] * block_size
    return block_size, block_enc, key, ctr

def _is_same(bits_a, bits_b):
    if len(bits_a) != len(bits_b):
        return False
    for a, b in zip(bits_a, bits_b):
        if a != b:
            return False
    return True

def check(message_a, message_b):
    """return True if `message_a` and `message_b` are
    different but hash to the same value"""

    if _is_same(message_a, message_b):
        return False
    
    hash_a = counter_mode_hash(message_a)
    hash_b = counter_mode_hash(message_b)

    return _is_same(hash_a, hash_b)