Category: cryptography

ciphertexts

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

Probability Review

Event: subset of outcomes from a probability space
Head = { H }
Valid = { H, T }
P(A) = ΣweA P(w)

1 – P(E) = P(Valid)

Complementary Event Prbability
VA: P(a) + p(A) = 1

Conditional probability
P(B|A) = P(Aub)/ p(A)

Perfect Cipher
the ciphertext provides an attacker with no additional information about the plaintext.
m -> enc -> c
m e M
m* e M

Eki(mi) = c
P(m=m*).P(k=k*) = 1/k

P(Ek(m)= c) = 1/|k|
P(m=m* Ek(m)=c) = P(m = m*)/|k|

Malleable
alice Ek(m)=c active attacker

Impratical |k| = |m|

Shamon’s Theorem: if a cipher is perfect, it must be impractical

Perfect cipher: P(m=m*|Ek(m)=c) = P(m=m*)

One Time Pad

Ek(m) = c0 c1 … Cn-1
m = ‘CS’ = 1010011 1000011
k = 11001000100110
c = 01101111100101

Proving Security
here is a mathematical proof, accepted by experts, that shows the cipher is secure.

Probability(Review)
Ω:set of all possible outcomes
probability space
Ω = {h, t}
uniform distribution each outcome is equally likely
p: outcome -> [0, 1]
p(h) = 1/2 p(t) = 1/2
Ω = {H, T, E}
p(h) = 0.49999
p(t) = 0.49999
ΣweΩ　p(w) = 1

Symmetric Crytosystems

plaintext -> encryption -> ciphertext -> insecure channel -> decryptron
VmeM:D(E(m))=m
Kerck hoff’s Principle CIS

meM ceC keK
E:MxK -> c D:c*k -> M
correctness property: Vm;k: Dk(Ek(m))

Security property:
Ideal: ciphertext reveals nothing about key or message

def convert_to_bits(n, pad):
	result = []
	while n > 0:
		if n % 2 == 0:
			result = [0] + result
		else:
			result = [1] + result
		n = n / 2
	while len(result) < pad:
		result = [0] + result
	return result