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"]
Category: cryptography
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
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 [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)])
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)
Cbc Implementation
from Crypto.Cipher import AES
def non_encoder(block, key):
"""A basic encoder that doesn't actually do anything"""
return pad_bits_append(block, len(key))
def xor_encoder(block, key):
block = pad_bits_append(block, len(block, len(key))
cipher = [b ^ k for b, k in zip(block, key)]
return cipher
def aes_encoder(block, key):
block = pad_bits_append(block, len(key))
block = bit_to_string(block)
key = bits_to_string(key)
ecb = AES.new(key, AES.MODE_ECB)
return string_to_bits(ecb.encrypt(block))
def electronic_cookbook(plaintext, key, block_size, block_enc):
"""Return the ecb encoding of 'plaintext"""
cipher = []
for i in range(len(plaintext)/ block_size + 1):
start = i * block_size
if start >= len(plaintext):
break
end = min(len(plaintext), (i+1) * block_size)
block = plaintext[start:end]
cipher.extend(block_enc(block, key))
return cipher
def cipher_block_chaining(plaintext, key, init_vec, block_size, block_enc):
"""Return the cbc encoding of 'plain text'"""
def test():
key = string_to_bit('4h8f.093mJo:*9#$')
iv = string_to_bit('89JIlkj3$%0lkjdg')
plaintext = string_to_bits("one if by land; two if by sea")
BITS = ('0', '1')
ASCII_BITS = 8
def display_bits(b):
"""converts list of {0, 1}* to string"""
return ''.join([ITS[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_bit(convert_to_bits(ord(c)), ASCII_BITS)
return [b for group in
map(chr_to_bits, 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):
diff = max(0, size - len(small))
return small + [0] * diff
Physically Random Events
Quantum Mechanics
Thermal Noise
Key proceed mouse move
Peseudo-Random Number Generator
counter 0, 1, 2 -> Encrypt
Pool of Randomness seed-> key
Storing a file securely
Electronic Codebook Mode
Randomness
def generate_sequence(f, n): return map(f, range(n)) def generate_fake_random(n): repetition = 0 previous = None res = [] for i in range(n): x = random.choice([0, 1]) if x == previous: repetition += 1 if repetition > 2: x = (x + 1) % 2 repetition = 1 previous = x else: previous = x repetition = 1 res.append(x) return res length = 88 print display_bits(generate_sequence(lambda n: 0 if n % 3 == 0 else 1, length))
s i random if K(s) = |s| + c