RSA Algorithm – Simple Demo

I put together a simple interactive demo to illustrate the principles behind RSA asymmetric public-private key encryption.

rsa.demo.2

Click on the image above or [here] to go to the javascript demo.

Note that this demo setup is for pedagogical use only. In order for the method to be of any use in a real encryption scenario we would need to use initial prime numbers more than 100 digits long.

For example, we could use these two prime numbers of 116 digits each:

p = 33 478 071 698 956 898 786 044 169 848 212 690 817 704 794 983 713 768 568 912 431 388 982 883 793 878 002 287 614 711 652 531 743 087 737 814 467 999 489

q = 36 746 043 666 799 590 428 244 633 799 627 952 632 279 158 164 343 087 642 676 032 283 815 739 666 511 279 233 373 417 143 396 810 270 092 798 736 308 917

Multiplied together you’ll get this 232 digits long public key n:

n =  1 230 186 684 530 117 755 130 494 958 384 962 720 772 853 569 595 334 792 197 322 452 151 726 400 507 263 657 518 745 202 199 786 469 389 956 474 942 774 063 845 925 192 557 326 303 453 731 548 268 507 917 026 122 142 913 461 670 429 214 311 602 221 240 479 274 737 794 080 665 351 419 597 459 856 902 143 413

One thing that is truly fascinating and that constitutes the very foundation for the whole RSA concept is the asymmetry in required work between multiplying these two numbers and doing the opposite thing – finding the factors p and q knowing only n.

I programmed a javascript function for big integer multiplication. It can multiply these two 116-digit numbers in 2 miliseconds.

But doing the opposite, doing the reverse operation – factoring – how long time does that take?

In this particular case, it has actually been done. It’s the largest integer hitherto factorized. It took two years of computer processing and was accompliced on December 12, 2009. The CPU time spent on finding these factors by a collection of parallel computers amounted approximately to the equivalent of more than 2000 years of computing on a single-core 2.2 GHz AMD Opteron-based computer.

Professional RSA encryption today uses public keys n of at least the magnitude of 2048 bits. That’s a number with 616 decimal digits and that means we use prime numbers p and q with 308 digits each.

My homemade javascript function multiplies two such primes to form a 616 digit integer in 20 miliseconds.

For the above mentioned Opteron-based computer, the task of factoring a 616 digit integer is estimated to require 6.4 quadrillion years of CPU time. That’s like the age of the universe multiplied by half a million.

The second obvious weakness in the simple javascript demo apart from the prime numbers being too small is the fact that only one character at a time is encrypted with the algorithm.

Let’s look at the scenario shown in the initial screen dump.

n = 323
e = 139 (public encryption key)
d = 259 (private decryption key)

Now we’re going to encrypt the word ”hello” where each letter is represented by its ”ascii-code”

h = 104
e = 101
l = 108
l = 108
o = 111

 

So we RSA-encrypt them with the public key (139) like this:

”h”: 104^139 (mod 323) = 25
”e”: 101^139 (mod 323) = 118
”l”: 108^139 (mod 323) = 243
”l”: 108^139 (mod 323) = 243
”o”: 111^139 (mod 323) = 100

And we can decrypt them using the private key (259) like this:

25^259 (mod 323) = 104 (”h”)
118^259 (mod 323) = 101 (”e”)
243^259 (mod 323) = 108 (”l”)
243^259 (mod 323) = 108 (”l”)
100^259 (mod 323) = 111 (”o”)

The glaring weakness here is of course that anyone having only the public key (139) can produce a translation table relating each non-encrypted letter of the alphabet with an encrypted value. So, even without access to the private key, an unauthorized person can, using this translation table, discover the word ”hello” in the encrypted sequence 25, 118, 243, 243, 100.

The fix for this weakness is to encrypt larger chunks of text at each powermod-operation. The textual chunk size should correspond to the size of n. If n is a 2048 bit value, then you can encrypt the text in chunks of 2048 bits (corresponding to 256 8-bit ascii characters).

But what if a prosecutor for example gets hold of a suspects RSA-encrypted file and he thinks that it contains a certain known compromising document? Wouldn’t he be able to prove  that? If he himself encrypts that known document using the public key he can then look for the same encrypted chunks of 256 charaters in the suspects encrypted file. The solution to this weakness lies in letting a certain portion of each chunk consist of completely random bits of information. The consequence of that system will be that identical files will never result in identical encrypted files.

 

 

Annonser