(Reposted and edited from my old blog)
RSA is an asymmetric cryptosystem which uses two different keys – a public key that’s distributed to anyone wanting to encrypt and send information, and a secret key (also known as the private key) that’s used for decrypting the information. It means anyone can encrypt a message and only the recipient can decrypt it. As no secret key is being communicated, this solves the problem of how to communicate securely without a third party being able to decrypt anything. Interestingly, it would also mean a person couldn’t be later forced to reveal whatever they encrypted, since they only have the public key of the recipient. In theory, once something’s encrypted with RSA, it’s unrecoverable by the sender. In practice an plaintext copy is usually recoverable. RSA itself is normally used for safely communicating keys a symmetric key cryptographic system that requires less computing resources, such as AES and Triple-DES.
This post is my attempt to break RSA this down into simple terms, and explain how the RSA Cryptography module for the XeroCrypt software will function when I finally get it working (hopefully sometime next week).
The basic algorithm is:
The algorithm itself is very straightforward, but writing the program that does this is turning out to be easier said than done. The first problem was in finding a method of generating the first two prime numbers, since in real-life they’re at least 60 digits in length and the user can’t be expected to readily choose them. To solve this, I’m attempting to add a Random Number Generator that produces random primes up to 99999, because the program works with much shorter numbers just to demonstrate the principle. This would also provide a solution for selecting an encryption exponent (E). I should point out the RNG used in the current version of XeroCrypt isn’t actually random enough for commercial encryption, but that’s a subject to be covered in future.
The second problem is finding the right value for the decryption exponent (D). This could also be solved using a loop that tests different values for D until the calculation produces 1 as the output.
So the key generation part of the program will do something like the following:
The other two parts of the program are for encrypting and decrypting a number, using mathematical functions and some of the values (the public and private keys) produced by the key generation code.
So far the program should encrypt a number using the RSA algorithm, and some people might be wondering how this applies to the real world in which we encrypt text, images, audio, video files, etc. There are two answers to this. The first is that, as with my earlier post on XOR encryption, the content can be converted into a very long binary string – in other words, a very long number that can be used as value M in this system.