### Blum Blum Shub PRNG and XOR encryption in Python

I'd like to talk about some code I wrote, but first I want to touch on something else that's indirectly related.

Last week I spent almost all of my free time writing solutions to three problems in hopes of getting an interview with a company. Unfortunately, the developers who reviewed my work told me that I had over-complicated things, in addition to what I thought were some rather contemptuous comments that I won't repeat.

I'm definitely okay with criticism. After all, that's what makes us think; it's humbling. By no means would I ever presume that I'm the greatest programmer or mathematician who's walked this Earth (that's just silly, we all know it was Gauss); heck, you'll most likely find an error or two scanning my posts in the next few minutes, if you haven't already.

Do I over-complicate things? Probably, yes. I enjoy going a step further, trying something new, or making a class or function more flexible for tools or types. I care both about the correctness of the underlying concept and algorithm, and the way in which my code is used/viewed at the same time.

Anyway, here's a class that implements the Blum Blum Shub pseudo random number generator and XORs those bytes with some data. I wrote and tested it using PyCharm.
#! /usr/bin/env python3.4
# -*- coding: utf-8 -*-

""" Blum Blum Shub & XOR encryption algorithm implementation """

from typing import List, Union

MODULUS = 0xe2089ea5  # if you compile sizing.c it will find the prime factors p = 61519 and
# q = 61643 (both of which are equivalent to 3 mod 4)

INITIAL = 0x12345678  # seed value (as in the example)

class Crypto:
""" A Blum Blum Shub & XOR algorithm that works byte by byte """
def __init__(self, data: Union[str, list, bytes] ='', data_length: int =0,
initial_value: int =INITIAL, modulus: int =MODULUS) -> None:
if type(data) is list:
self.data = data
elif type(data) is str:
self.data = list(data)
elif type(data) is bytes:
# I should probably give this preference, but if we don't change this to chr by
# crawling through it we'll have to catch errors since int doesn't have a __len__ method
self.data = [chr(c) for c in list(data)]
else:
raise ValueError('Encrypt expected data in form of list or string, got {0}'\
.format(type(data)))

if type(data_length) is int:
self.data_length = data_length
elif type(data_length) is None:
self.data_length = len(data)
else:

self.initial_value = initial_value
self.modulus = modulus

def encrypt(self) -> List[str]:
""" Encrypt data - class written so that it's an involutory function (it is its own
inverse)
"""
x = (self.initial_value * self.initial_value) % self.modulus

crypted = []
if len(self.data[0]) is 2:  # (length 2 string for one byte)
# decryption
for i in range(self.data_length):
crypted.append(hex(x & 0xff ^ int(self.data[i], base=16))[2:])
x = x * x % self.modulus
else:                       # we're dealing with a single character to encrypt
# encryption
for i in range(self.data_length):
crypted.append(hex(x & 0xff ^ ord(self.data[i]))[2:])
x = x * x % self.modulus

self.data = crypted
return crypted

def decrypt(self) -> List[str]:
return self.encrypt()

def main() -> None:
# example as in the document
word = 'apple'
X = Crypto(word, len(word), INITIAL, MODULUS)

# NOTE: X.encrypt() and X.decrypt, as suggested by the type annotations, return
# lists of strings

print('Starting data : ' + word)
print('Encrypted data: ' + '\\x' + '\\x'.join(X.encrypt()))
print('Decrypted data: ' + ''.join(chr(int(c, base=16)) for c in X.decrypt()))

if __name__ == '__main__': main()


And the output:
Starting data : apple
Encrypted data: \x4c\x88\x9e\xdf\xe8
Decrypted data: apple

The quick C program mentioned in the comments above just uses a naive method for determining the two primes (congruent to 3 mod 4) that multiply to 0xe2089ea5.
/* Find the 2 prime factors of 0xE2089EA5 for BBS PRNG */

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>

typedef int bool;
#define true 1
#define false 0

// upper bound of primes suspected (only 2)
#define NUMBER 2

bool
is_prime(uint64_t number)
{
/* A really horrible/naive check of primality */
uint64_t i;

for (i = 2; i < number / 2 + 1; ++i)
if (number % i == 0)
return false;

return true;
}

int
main(void)
{
uint64_t num = 0xE2089EA5;
uint64_t div = 2;
uint64_t i = 0;

// I happen to know there are only 2 primes
uint64_t * divisers = (uint64_t *)malloc(NUMBER * sizeof(uint64_t));

while (num != 0)
{
if (num % div != 0) {
++div;
} else {
num /= div;
divisers[i] = div;
++i;
if (num == 1) break;
}
}

for (i = 0; i < 2; ++i)
if (is_prime(divisers[i]))
printf("Prime factor: %d % 4 == %d\n",divisers[i],divisers[i] % 4);

return 1;
}

This latter block of code wasn't a part of the original problem, but I thought it would be interesting to solve for the two integers they had used to arrive at the modulus.

Sources

[1] Handbook of Applied Cryptography, by Menezes et. al., page 19.