lab2_alt2.py

#! /bin/python3 -B

from fractions import Fraction
import pprint

class inputCase:
	deltaX = 0
	recursor = None
	def __init__(self, deltaX, recursor):
		self.deltaX = deltaX
		self.recursor = recursor

	def recurse(self):
		self.recursor.recurse()
		return self.recursor.ends


# the recursor needs access to the probability tables
class recursor:
	branches = []
	probabilityTables = None
	ends = []
	deltaX = 0

	def recurse(self):
		global maxNum
		global sBoxes
		for i,j in self.probabilityTables[1].items():
			for k in range(len(sBoxes)-1):
				for l in getOutputs(self.probabilityTables[1], i):
					newBranch = Branch(i, self.deltaX, self.probabilityTables, self, k, l[0], l[1])
					self.branches.append(newBranch)

		for i in self.branches:
			i.recurse()

	def __init__(self, probabilityTables, deltaX):
		self.probabilityTables = probabilityTables
		self.deltaX = deltaX





# the branch needs access to the probability tables
class Branch:
	outputDifference = 0
	inputDifference = 0
	subBranches = []
	round = 1
	maxRound = 4
	probabilityTables = None
	parent = None
	sBoxOffset = 0
	prob = 0

	def recurse(self):
		print("Round: {} Self.inputDifference: {}".format(self.round, self.inputDifference))
		if self.round == 5:
			print("%%%%%%%%%%%%%%%% IMPOSSIBLE CONDITION OCCURED!")
			return
		print("Table: {}".format(self.probabilityTables[self.round][self.inputDifference]))
		if self.round == self.maxRound or self.round == self.maxRound:
			dY,probability = findbestOutput(self.probabilityTables[self.round], self.inputDifference)
			print("Best output: {}".format(dY))
			self.outputDifference = dY
			nextBranch = self
			print("Parent round {} inputDifference {} outputDifference {}".format(nextBranch.round, nextBranch.inputDifference, nextBranch.outputDifference))
			inputs = []
			global paths
			probability = 1
			while True:
				if type(nextBranch) == recursor or type(nextBranch) == recursor:
					# get the probability of this event from the global table
					# inputs.insert(0, nextBranch.deltaX)
					print("prob: {}".format(probability))
					print("Inputs: {}".format(inputs))
					paths.append((probability, inputs))
					return
				print ("type nextBranch {}, check {}".format(type(nextBranch), type(nextBranch) == recursor))
				print("------------< Recursing from {} up ".format(nextBranch.round))
				print("Prob: {}".format(probability))
				print("Current up round {}".format(nextBranch.round))
				print("inputDifference {} outputDifference {}".format(nextBranch.inputDifference, nextBranch.outputDifference))
				print("Inputs: {}".format(inputs))
				# get our own probability by looking it up in the former round's output tablé
				print("Previous round data: {} {} {}".format(nextBranch.round, nextBranch.inputDifference, self.probabilityTables[nextBranch.round][nextBranch.inputDifference]))
				probability = probability * nextBranch.prob
				inputs.insert(0, nextBranch.inputDifference)
				nextBranch = nextBranch.parent

			
		else:
			possibleOutputs=getOutputs(self.probabilityTables[self.round], self.inputDifference)
			print("Round {} possible outputs {}".format(self.round, possibleOutputs))
			print("self.inputDifference: {}".format(self.inputDifference))
			satisfied = []
			for i,j in possibleOutputs:
				print ("i,j: {} {}".format(i, j))
				# transform the output
				transformed = transformOutputToInputs(self.sBoxOffset, i)
				print("Transformed to {}".format(transformed))
				if transformed != 0 and transformed not in satisfied:
					satisfied.append(transformed)
					print("!!!!! self.round: {} (+1 {})".format(self.round, self.round + 1))
					newBranch = Branch(transformed, self.round + 1, self.probabilityTables, self, self.sBoxOffset, i, j)
					self.subBranches.append(newBranch)
					print("------------> Recursing from {} down".format(self.round))
					if self.round + 1 > self.maxRound:
						print("%%%%%%%%%%%%%%%% IMPOSSIBLE CONDITION OCCURED!")
						return
					newBranch.recurse()
			return


	def __init__(self, inputDifference, round, probabilityTables, parent, sBoxOffset, outputDifference, prob):
		# print("##### Init branch with {} {} {} {} {} {} {}".format(inputDifference, round, probabilityTables, parent, sBoxOffset, outputDifference, prob))
		self.inputDifference = inputDifference
		self.round = round
		self.probabilityTables = probabilityTables
		self.parent = parent
		self.sBoxOffset = sBoxOffset
		self.outputDifference = outputDifference
		self.prob = prob


class sBox():
	# The substitution table this s-box uses
	table = []

	def __init__(self, table):
		self.table = table

	def forwards(self, x):
		return self.table[x]

class result:
	inputs = []
	probability = []

	def __init__(self, inputs, probability):
		self.inputs = inputs
		self.probability = probability

	def __repr__(self):
		return "probability {} inputs {}".format(self.probability, self.inputs)


# this function calculates the inputs to the next round
def transformOutputToInputs(sBoxOffset, output):
	return output & (0x8 >> sBoxOffset)


def generateTable(sBox, deltaX):
	table = {}
	for x in range(0, maxNum):
		x_ = x^deltaX
		y = sBox.forwards(x)
		y_ = sBox.forwards(x_)
		deltaY=y^y_
		if table.get(deltaY, False):
			table[deltaY] = table[deltaY] + Fraction (1,maxNum)
		else:
			table[deltaY] = Fraction(1, maxNum)
	return table

def findBestInput(table):
	bestInput=(0,0,Fraction(2,0))

	for dx, dy in table.items():
		for prob in dy:
			if prob > bestInput[2]:
				bestInput=(dx,dy,prob)
	return bestInput

def findbestOutput(table, dx):
	bestOutput=(0,Fraction(0,1))
	for dy, prob in table[dx].items():
		if prob > bestOutput[1]:
			bestOutput = (dy, prob)
	return bestOutput

def getOutputs(table, dx):
	outputs=[]
	for dy, prob in table[dx].items():
		outputs.append((dy,prob))
	return outputs

def getInputs(table):
	inputs=[]
	for dx in table.keys():
		inputs.append(dx)
	return inputs

maxNum=0xf
cases = []
differenceDistributionTable={}

s1=[10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8]
s2=[7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15]
s3=[2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9]
s4=[12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11]

paths = []
sBoxes = {
	1: sBox(s1),
	2: sBox(s2),
	3: sBox(s3),
	4: sBox(s4)
}

deltaXTestCases={}

for i,j in sBoxes.items():
	print("Building tables for sBox {}".format(i))
	differenceDistributionTable[i] = {}
	# skip deltaX == 0
	for k in range(1,maxNum):
		print("Building table for deltaX {}".format(k))
		differenceDistributionTable[i][k] = generateTable(j,k)

for i in differenceDistributionTable[1].keys():
	deltaXTestCases[i] = inputCase(i, recursor(differenceDistributionTable, i))

for i in deltaXTestCases.values():
	print("Recursing with dX {}".format(i.deltaX))
	i.recurse()

print("Paths: {}".format(paths))