Skip to content

Instantly share code, notes, and snippets.

@fbparis
Last active January 2, 2019 06:31
Show Gist options
  • Save fbparis/a5749da7efa88183976ff8ebb1174faf to your computer and use it in GitHub Desktop.
Save fbparis/a5749da7efa88183976ff8ebb1174faf to your computer and use it in GitHub Desktop.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment