perfectcipher.py

import os
from math import factorial
from random import seed, randrange

class PerfectCipher(object):
	"""
	Each byte (0-255) of a message is replaced using a translation table which is a permutation of [0..255].
	After each replacement a new translation table is used using a Linear Congruential Generator to act as a PRNG:
		Next N = (a * N + c) % m
	Where m is 256! (total count of [0..255] permutations) and a and c carefully chosen so that the period of the PRNG is equal to m.
	"""
	def __init__(self, key, iv_size=16):
		"""
		Set up a new cipher with key=<key> and initialisation vector's size is <iv_size> bytes.
		Any values will be OK, recommended values are a 32 bytes key and 16 bytes IV.
		"""
		if type(key) == str:
			key = key.encode()
		self.key = key.hex()
		self.iv_size = iv_size
		self.table = range(256)
		self.a, self.c, self.m = self._getParams()
		# 1 and any prime number greater than 256 will be a good value for c
		self.cvalues = [1,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039]
		self.fact = {}
		for i in range(256):
			self.fact[i] = factorial(i)

	def _getParams(self):
		"""
		When c≠0, correctly chosen parameters allow a period equal to m, for all seed values. This will occur if and only if:

		m and the offset c are relatively prime,
		a-1 is divisible by all prime factors of m,
		a-1 is divisible by 4 if m is divisible by 4.
		These three requirements are referred to as the Hull–Dobell Theorem.
		(https://en.wikipedia.org/wiki/Linear_congruential_generator#c%E2%89%A00)
		"""
		primes = [2,3,4,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251]
		c = 1
		a = 1
		d = set()
		for n in range(2, 257):
			for p in primes:
				if p > n:
					break
				r = n % p
				if r == 0:
					if p in d:
						continue
					d.add(p)
					a *= p
		a += 1
		return a, c, factorial(256)

	def _next(self, n):
		"""
		Return a pseudo random number between 0 and 857817775342842654119082271681232625157781520279485619859655650377269452553147589377440291360451408450375885342336584306157196834693696475322289288497426025679637332563368786442675207626794560187968867971521143307702077526646451464709187326100832876325702818980773671781454170250523018608495319068138257481070252817559459476987034665712738139286205234756808218860701203611083152093501947437109101726968262861606263662435022840944191408424615936000000000000000000000000000000000000000000000000000000000000000 (256!)
		"""
		return (self.a * n + self.c) % self.m

	def _init(self, iv):
		"""
		Seed the PRNG by mixing the initialisation vector and the key
		"""
		self.c = 1
		return self._next(int(iv.hex() + self.key, 16))

	def _getElt(self, n, i):
		"""
		Returns the <i>th element of the <n>th permutaion of 0..255
		"""
		table = list(self.table)
		if n == 0:
			return table[i]
		j = 0
		f = 255
		while 1:
			r = n // self.fact[f]
			if n % self.fact[f] == 0:
				r -= 1
			n -= r * self.fact[f]
			r = table.pop(r)
			if i == j:
				return r
			j += 1
			f -= 1

	def _getReverseElt(self, n, c):
		"""
		Returns the index of <c> in the <n>th permutation of 0..255
		"""
		table = list(self.table)
		if n == 0:
			return table.index(c)
		j = 0
		f = 255
		while 1:
			r = n // self.fact[f]
			if n % self.fact[f] == 0:
				r -= 1
			n -= r * self.fact[f]
			r= table.pop(r)
			if r == c:
				return j
			j += 1
			f -= 1

	def encrypt(self, data):
		"""
		Encrypt a message (<data>)
		"""
		iv = os.urandom(self.iv_size)
		n = self._init(iv)
		r = []
		for c in data:
			r.append(self._getElt(n, c))
			# the offset c vary according to the last byte encrypted
			self.c = self.cvalues[c]
			n = self._next(n)
		return iv + bytes(r)

	def decrypt(self, data):
		"""
		Decrypt a message (<data>)
		"""
		# first <self.iv_size> bytes are the initialisation vector, remaining bytes are the message to decrypt
		iv, data = data[:self.iv_size], data[self.iv_size:]
		n = self._init(iv)
		r = []
		for c in data:
			r.append((self._getReverseElt(n, c)))
			# the offset c vary according to the last byte encrypted
			self.c = self.cvalues[r[-1]]
			n = self._next(n)
		return bytes(r)

class PerfectCipher2(object):
	"""
	Each byte (0-255) of a message is combined using XOR with a pseudo random byte from python PRNG.
	"""
	def __init__(self, key, iv_size=16):
		"""
		Set up a new cipher with key=<key> and initialisation vector's size is <iv_size> bytes.
		Any values will be OK, recommended values are a 32 bytes key and 16 bytes IV.
		"""
		if type(key) == str:
			key = key.encode()
		self.key = key
		self.iv_size = iv_size

	def _init(self, iv):
		"""
		Seed the PRNG by mixing the initialisation vector and the key
		"""
		seed(self.key + iv)

	def encrypt(self, data):
		"""
		Encrypt a message (<data>)
		"""
		iv = os.urandom(self.iv_size)
		self._init(iv)
		r, prev = [], randrange(256)
		for c in data:
			n = c ^ randrange(256)
			r.append(prev ^ n)
			prev = c
		return iv + bytes(r)

	def decrypt(self, data):
		"""
		Decrypt a message (<data>)
		"""
		# first <self.iv_size> bytes are the initialisation vector, remaining bytes are the message to decrypt
		iv, data = data[:self.iv_size], data[self.iv_size:]
		self._init(iv)
		r, prev = [], randrange(256)
		for c in data:
			n = (c ^ prev)  ^ randrange(256)
			r.append(n)
			prev = n
		return bytes(r)

if __name__ == '__main__':
	from time import time

	key = os.urandom(32)
	C1 = PerfectCipher(key=key, iv_size=16)
	C2 = PerfectCipher2(key=key, iv_size=16)
	msg = os.urandom(10000)
	# start = time()
	# ct = C1.encrypt(msg)
	# print(msg==C1.decrypt(ct), time() - start)
	start = time()
	ct = C2.encrypt(msg)
	print(ct)
	print(msg==C2.decrypt(ct), time() - start)