Saturday, July 30, 2011

RSA encryption algorithm example C# with keys up to 2048 bits (with multiple threads)

Hi,
At the end of december 2010 I started to do some research on the RSA implementation with big encryption/decryption keys. There were many reasons why I wanted to do this:

  1. At university, in 2009, I had the task to implement the RSA algorithm. This was not so hard, but a little challenging for the one that never did any kind of encryption. So I implemented this algorithm, and encrypted every byte using it. The enc/dec key had several bits, no more. This was enough for the practice lessons, the single problem was that the key was very small, and I wanted to know how to encrypt with bigger keys. Anyway, I didn't do anything in this direction al all.
  2. In 2010, when I was doing my master degree at another university, there were some requests from my fellow students at the original University to provide them my RSA project as an example, so for them to be easier to understand how to implement it. The harder part was that we were supposed to calculate the approximate time of encryption and the decryption at runtime, like in the case when Windows explorer calculates how many minutes you have to wait until all the files are copied. It was then that I thought to create an RSA example, more close to that what is used in practice, and to provide it for all that want to understand how it works. I thought about encrypting with bigger keys (because currently the safe RSA key is considered to be 2048 bits), and to encrypt the file on multi-core machines.
  3. The third reason was to better understand all the operations on bits, bytes etc. in C#. Believe me, it was worth the effort :D.
So, I started in december 2010, worked on the project for some months, but when I started my professional training, I stopped working on it. My time was completely allocated to it, and even now it is allocated for other things and the project remains unfinished. I thought that maybe it's worth posting it as it is, because anyway I did some good job (I think), and I learned a lot in creating this app. Maybe others will want to see what I did, and to try to understand themselves how to do what I did. I don't claim that I did something extraordinary, but at the time when I started, there wasn't any project with such features in C#, at least I didn't found, and anyway, I wanted to do all this myself (just 4 fun). 

I shall describe right now my app., what it does and what it doesn't do.

The main window:


The settings window:

So, what my program does can be deduced from the images above. Now the problems:

  1. A key with the length of 2048 bits cannot be always generated, I don't know the reason right now, some test must be done. I wasn't able to generate a key bigger than 2048 bits, even though the BigInteger class used in this application (from codeproject) can generate such a key.
  2. Even if a big key is used to encrypt the data, it's a very simple method used here. I encrypt every byte, and as you may guess, the encrypted file can be easily cracked, if we know that some 2048 bits in the file represent a byte (and in my encrypted file every line is an encrypted byte :) ), and if the encrypted text was in English, then we can find, using statistical methods and knowing the probability of English characters in an average text, what the text is.
  3. I tried to correct the problem stated in point 2, by encrypting not every byte, but a block of bytes. In such case, it will be more difficult to crack the file. But here I ran in some problems. Firstly, if we choose a block of 3 bytes to be encrypted together, then the simple equality must be satisfied, to assure that we will be able to decrypt the file: file.length % blockSize == 0; . Well, this wasn't so difficult to achieve, I simply added some zeros at the end of the file, and I remove them after decryption. But, a bigger problem here arises at decryption. For example, if we had to encrypt together the bytes: 1 20 255, then our string to encrypt will be 120255. OK, we can encrypt it, but how we will be able to find what were the numbers that we encrypted at decryption, i.e. 1 has the length 1, 20 has 2 and 255 has 3. Even if we decrypt our string, we will not know what the encrypted bytes were. In such a case, we must add some redundancy, or prior to encryption, to transform, using a dictionary in which any byte will be represented by a number with a fixed length, for example: 1 to be 1001, 20 to be 1020, 255 to be 1255. In such case, we will be able to find the original bytes. Anyway, this is just an idea :)
  4. I think you noticed that all the labels are in brackets. This is because I wanted to add language support for my app, but I haven't done it yet.

So, this is it. Because I cannot allocate time right now to do some research how in practice RSA works (and it's not easy to find such information) and to develop my app. (maybe in future, just for fun), I posted my source code on this blog.

Any suggestions and help are welcome!

I hope this project will be useful for those who want to understand a little more on RSA, but because I never worked on official encryption projects, I cannot provide more information on RSA encryption in practice.

Here's the link to the project's source code:

;)