ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

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が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

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

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"]

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)

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

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

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"

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