Created 2004-11-30 Modified 2009-04-11
Chelton Evans
RSA
Intro
RSA Mathematics
Dependencies
Source
Packet Screwup
Use
Key Length
Incorporating Software Licensing in Applications
Binary Files
TODO
References
Public-key algorithm. See RSA .
TODO update doc. RSA Factoring Challenge
RSA is a public key algorithm. This is a variable key length implementation. RSA has a fascinating history.
RSA was the first no-alphabetical cryptographic algorithm. All other algorithms before were arrangements or permutations and substitutions. This was mathematical with trapdoor functions.
Actually DES with the S-boxes could also be viewed as a trapdoor function where the key effects the substitutions in letters.[1]
This code uses Victor Shoup's NTL library for integer arithmetic. See NTL for info with respect to this workspace.
RSA encryption/decryption program.
You can take full control as seen in example 2 or work with files and let the application generate the key. This is the easiest way, but you should manage the key length through nbits. Two files "encrypt.txt" and "decrypt.txt" are generated. Keep "decrypt.txt" secret. Because the algorithm is public key it does not matter if someone has both the encrypted and decrypted files they will not be able to use this to find your key. Its safe to have the encrypted file public.
Example 1
$./main generate=true nbits=1000
To encrypt a file:
$./main read=encrypt.txt file=msg.txt
To decrypt a file:
$./main read=decrypt.txt file=msg.txt
Example 2
To encrypt a file:
$./main encrypt=true file=msg.txt n=3337 e=79 blocksize=3
To decrypt a file:
$./main decrypt=true p=47 q=71 file=msg.txt e=79
Paranoid: Imagine that there is a back door in this system. Even if you think I am an honest person and would not do this to you, the random library number generator could have been tampered with, so the primes you think are difficult for another to generate could be found by a superior enemy. Whatever your condition there is another way to generate the primes. generate2 takes two numbers p and q and sequentially searches for the first prime after that number. Set numbits to be large which just adds this large number to p and q.
Example 3
On my P3 it takes less than 10 minutes to generate the key.
$./main generate2=true nbits=4000 p=84982438458382834841 q=83839388477473777221
This is an extreme example. Let the file being encrypted
and decrypted be 14K in size.
Example 4
Con
$./main generate=true nbits=5000
took 14 minutes and 19s on my old P4. To encrypt the file
takes around 6 minutes 20s. To decrypt took 12 minutes and 20s.
A more practical example
$./main generate=true nbits=2000
took 1 minute 50s. To encrypt took 1 minute 7s. To decrypt 2 minutes 12s.
For real time 30K/s at 2000 bit key length I would need a 300 fold improvement. This would require an 8 fold doubling of the machine speed. While this is significant it is not unrealistic. Probably optimizing the code may gain a few factors. The encrypting and decrypting are parallel in nature so a poor man's supercomputer such as PVM could be used to do this in real time.
The point is that this is practical for 2000 bit key length with to days computers. Because it is parallel it is also practical with a 5000 bit key length - with NO dedicated hardware! (by this I mean encryption/decryption chips).
nbits the number of bits in a power of 2. The blocksize is the length
in a power of 10. read simply reads the file and passes the strings as if they
were input at the command line, so what you see in the file gives the same result if you
had passed the text at the command line.
If the message is a multiple of p or q there was previously a problem with data corruption. I implemented this before I analyzed RSA mathematically. The solution was to have the message less that p and q to guarantee that this event never happens. i.e. blocksize=nbits-1. This reduced the encryption decryption speed by half but ensures security.
The packet screw up is an example where I made a mistake implementing the algorithm. I worked this out after-wards. It was a security risk because if the enemy got the plain text and the encrypted text and compared them they could have found out which packet was corrupted. The security of the algorithm is that the enemy should not be able find the prime factors p and q from the data short of factoring pq.
I heard a rumor from my friend that the Israels and Americans have a black box that can crack a 2000-bit key-length algorithm (say RSA) in less than a day (these rumors always come up and it is known that the governments have built machines to work in parallel to crack the algorithms). My friend is in the IT industry so I said to him that you can always increase the key length - to which he replied that the Americans could crack anything I did.
While this is just gossip it does illustrate the difference between what someone thinks and what is reality. Each increase by one in the key length doubles the amount of work needed to crack (factor) n=pq. This is an exponential increase. So if they can factor a problem with a key of 1000-bit key it is twice as much work(cost) to factor 1001-bit key.
But let me quote someone else. "The universe is only 10^10 years old, so 10^25 years is a long time. With a 2048-bit key, a million million attempts per second computers working in parallel will spend 10^597 years finding the key. By that time the universe will have long collapsed or expanded into nothingness."[2]
I guess if I really had a secret to keep (which I don't) then I would use a 5000-bit key.
Quoting from livinginternet rsa.
In 1982, RSA formed the company RSA to market their PKC algorithm in
electronic security products. They obtained patent number 4405829 on the RSA
algorithm in the US, but could not obtain a patent internationally because
they had already published the idea and most other countries bar retroactive
patenting of open source concepts.
...
In September 2000, the US patent for the RSA algorithm expired, for the first time enabling software developers everywhere to freely include this PKC standard in their products.
Convert the files to ASCII before encoding. The following
does not preserver execution bit.
Binary to text file
$ base64 <binary file> > <text file>
Text to binary file
$ base64 -d <text file> > <binary file>
How to convert binary file to ascii file?
When you initially install a program you are asked for the key. For example installing MS windows, or any commercial programs. I am going to discuss how RSA could be used for these purposes.
For stand alone applications that do not access any resource other than the computer you can use RSA to have the application have its own identity. For example many keys can run the application. Here is a primitive(yet effective) way to implement this.
Have a simple protocol to encrypt a message with noise into a string. For example the letter is either interpreted as a jump forward to the next letter or an actual letter in the message. 43 71 94 12 ... jump 43 characters forward after adding character 71 to the message, jump 94 places forward after adding character 12 to the message. Fill the space in between the message and jumps with random characters. This gives a simple protocol to embed a message in some noise.
Now have a key generated that when interpreted say the message "I LOVE APPLICATION X". This is encrypted using the applications public RSA key. When a user runs the program the key issued to them is read in and the application uses RSA to convert the message. If the message is "I LOVE APPLICATION X" the program is allowed to run.
For keys specific to the computer system the Internet is necessary. A server generates a key which contains information about the computer it is generating a key for. eg the mac address. When the program is run by the application if the key does not yield the mac address the same as the program running the application then the application has detected an improper use of the program (and presumably it does not allow it to run). Not that if this policy is implemented changing the hardware of the computer the application resides on requires a new password to be generated. The beauty with this strategy is that while it is easy to copy the program around it will not run on other computers.
In reality software liciencing is easily circumvented by an assembly language programmer. After meeting such a programmer I was shocked by how easily they take apart an excecutable, editing it like a cook making a meal. Menus can be inserted, options turned on or off, so a feature that you released as disabled can be enabled!