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:
   = data
        elif type(data) is str:
   = 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
   = [chr(c) for c in list(data)]
            raise ValueError('Encrypt expected data in form of list or string, got {0}'\

        if type(data_length) is int:
            self.data_length = data_length
        elif type(data_length) is None:
            self.data_length = len(data)
            raise ValueError('Expected data_length, received'.format(type(data_length)))

        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
        x = (self.initial_value * self.initial_value) % self.modulus

        crypted = []
        if len([0]) is 2:  # (length 2 string for one byte)
            # decryption
            for i in range(self.data_length):
                crypted.append(hex(x & 0xff ^ int([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([i]))[2:])
                x = x * x % self.modulus = 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

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;

    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) {
        } else {
            num /= div;
            divisers[i] = div;
            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.


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