Encryption Pseudorandomness Explorer




Encryption Pseudorandomness Explorer


(Summary of the Original Written Report) 

Exploratory Object Designer: Neil Marshall
Date: April 2007

Introduction

There are many encryption methods students can implement with the programming skills learned from the first year MICA course. In class we have implemented encrypting numbers with RSA using a simple case of 3 digit primes. The question then becomes, “How good is this encryption we have implemented?” Obviously a mathematician with a computer could break such encryption using brute force methods, but what if that mathematician didn’t have a computer or knowledge of the cryptosystem?

In the early days of code breaking, mathematicians used the distributions of alphabetical (and other) characters in text as a means of breaking the code. The uneven distribution of letters in any language gives mathematicians a tool to tease a signal out of what is apparently noise. Thus it is appropriate to ask, “How random would encrypted texts appear using methods we can be expected to implement having taken the course?”

 

Objectives

I selected three ciphers: RSA, Hill Cipher and Substitution Cipher. In the case of RSA, I implemented the ability to vary the size of the primes used to create the public (and private) encryption key (2-digit, 3-digit or 4-digit). I predicted that as you increase the size of the primes, the apparent “randomness” will increase. For Hill Cipher I implemented a choice of either a 2x2 Matrix or a 3x3 Matrix as part of the private encryption key, and I again predicted that the larger 3x3 will be more “random” than the 2x2. In the case of Substitution Cipher, I expect it will not seem random at all. I predict that RSA, being a “modern” encryption system will seem more “random” than Hill Cipher.

I predict that changing the text encrypted will have no impact on the results of the study as long as the text is sufficiently long (say about 40 words).

 

Results

RSA encryption using 2-digit primes is “more random” than plain English text but only marginally so. Increasing the size of the primes does increase the “randomness” of the ciphertext.

Hill Cipher in a 2x2 matrix already appears quite “random.” Though in some cases a 3x3 matrix does appear more “random,” other times using the tool it is simply too difficult to determine if this is the case. This is certainly a limitation of this approach.

Changing the encrypted text between different excerpts of several paragraphs of written English, as expected, did not influence the results.

As expected, Substitution Cipher appears to have the same distribution as plain English text. Surprisingly though, RSA encryption (at least in the form we implement in class) is less “random” than Hill Cipher. However this may be due to the fact that RSA is a public key encryption system whereas Hill cipher is a private key encryption system based on matrices. Perhaps there is a trade-off in terms of accessibility versus security. 

 

 

Written by Neil Marshall, July 2012

Return to Student Learning Objects

Visit the Project