### 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.

And the output:

Sources

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

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: 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 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:

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.Starting data : apple Encrypted data: \x4c\x88\x9e\xdf\xe8 Decrypted data: apple

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./* 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; }

Sources

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