RSA algorithm ppt help

[dragonstar57]

i did a ppt about how to do a Vigenère cipher and a caesars shift cipher and i asked someone YA the next method to try and they said RSA.

so i was hoping someone could explain how to use the RSA algorithm without the use of a computer?

I have been showing the class ciphers that can be used with just a pen and paper.

I guess if you have a better idea for the method than i guess that's ok to

ps i want to do this one because i have an interest in the subject (it's one of my few interests) and haven't been able to learn any thing new about it because of the mathematics is a little beyond me (i'm about to finish an algebra one class for my high school)

Edited May 23, 2011 by dragonstar57

[imatfaal]

I would have to think a lot before attempt RSA encryption with a pen and paper. I would also think of the next step up from Caesar to Vigenere to... would be Playfair (historical note this was used on active service in WWII- JFK used playfair to transmit a message to Allied command when his minesweeper was sunk by the Japanese navy). this nova site has a really nice amateur explanations of breaking a real playfair cipher used in the Telemark Heavy water raid - I still have most of the goody bag they sent as a prize

 

You could always try dropping Jim Gillogy an email - he is a mine of information and really friendly; when the CIA made a code devised for some artwork it was Jim that cracked the first section. And i believe he led a team that cracked a low grade RSA algorithm due to inconsistencies and short cuts used by the operators.

 

Anyway not long after WWII computers were able to crack normal codes - and generate codes no human alone could get close to. Undercover messages needed other ways to be sent - one time pads etc. If you are interested get a copy of hte Code Book by Simon Singh - its a great starter to ciphers and gets progressively more complicated.

[DJBruce]

You can work through the simplified basics of RSA with pen and paper, however, the level of mathematics required to full understand it may be beyond a high school student, but I'll see if I can explain it to you.

 

So RSA is a public key encryption system. This means that there are two keys, one which is public, and one which is private. The idea behind this method that the public key is used to encrypt a message, and then the private key is used to decrypt the message. So for example, if I wished to send you the message "BuyBuyBuy" I would use your public key to encrypt the message, and send the cyphertext to you, and you would then use your private key to decrypt it.

 

So the first thing that must be done for RSA is that a key must be select.

First select two prime numbers [math] p, q[/math] where [math]p\neq q[/math]. Normally these primes are quite large, however to make things easier lets pick [math]p=7, q=11[/math].

 

Now we calculate [math]n=pq[/math] so in this example [math]n=7*11=77[/math]

 

Now we calculate [math]\phi(n)=(p-1)(q-1)[/math]. If you don't know what this is it's Euler's Toitent function, which calculates the number of positive integers coprime to [math]n[/math]. So since [math]p, q[/math] are prime there is only one number that is not coprime to them ie: 1, and so [math]\phi(p)=(p-1)[/math] and math]\phi(q)=(q-1)[/math]. So for our example math]\phi(77)=(7-1)(11-1)=6*10=60.[/math].

 

Now an integer [math]a[/math] is select such that [math]1<a<\phi(n)[/math] and [math]gcd(a,\phi(n))=1[/math]. So we just need to select a integer between 1 and [math]\phi(n)[/math] such that it does not divide [math]\phi(n)[/math]. So for our example we need an integer between 1 and 60, which does not divide 60. To make this easy lets pick 13 since it does not divide 60.

 

We now have the public key! The public key we release to the public is (a,n), which in our case would be (13,77).

 

Now we need to find the private key. To do this we simply want to find the multiplicative inverse of [math]amod(\phi(n)[/math]. This means you want to find the number [math]x[/math] such that [math]ax\equiv 1mod(\phi(n))[/math]. So for our problem we want to find [math]x[/math] such that [math]13x\equiv 1mod(60)[/math], and in this case [math]x=37[/math]. If you have never seen modular arithmetic you might want to read a little about it just so you understand the basics of what we are doing here. So now the private key that is kept secret is (x,n), which in our case is (37,77).

 

So now we have almost everything we need to encrypt messages. The only thing left is to create a agreed upon way of converting text into numbers. This is called a padding scheme, and using a good padding scheme can increase the security of the encryption, but really the only required thing is that the scheme is agreed upon, ie: both parties know how the scheme works, and that each integer we select must be between 1 and n. So for example, we could agree that we will simply say that A=2, B=3, C=4....Z=27.

 

Now that we have a public key, a private key, and a padding scheme we can send messages. So lets say I wanted to sent you the message "BUY". So first I would use the padding scheme to convert this to numbers ie: BUY= 3 22 26. Now I am going to use your public key to encrypt the message. To encrypt an integer, [math]m[/math] we evaluate [math]m^{a}mod(n)=t[/math]. So for this example I would do:

 

[math]3^{13}mod(77)=38[/math]

[math]22^{13}mod(77)=22[/math]

[math]26^{13}mod(77)=75[/math]

So now I would send you the encrypted message 38 22 75.

 

Now you need to decrypt the message. To decrypt [math]t[/math] we would use our public key to do [math]t^{x}mod(77)[/math]. So for our example you would do:

 

[math]38^{37}mod(77)=3[/math]

[math]22^{37}mod(77)=22[/math]

[math]75^{37}mod(77)=26[/math]

So know you would use the padding scheme to evaluate 3 22 26 to mean B U Y.

 

So thats basically how RSA encryption works. Of course there is a lot of mathematics behind this showing why it will always work, and why it is so secure, but my guess is that it might be beyond high school. However, the example above can be done with basically only a little knowledge of modular arithmetic. Hope this helped!

[imatfaal]

Brilliant explanation