Paper and Pencil RSA (starring the extended Euclidean algorithm) 

Its been 9 years since this comment . Just wondering how you are doing in the present ?

wait till you learn about asymmetrical cryptography

thank you a lot you saved my life :/

why not d = 1+(0*40)/7 =1 why we dont use 0?

@A Hassan m is calculated as (p-1) * (q-1). This is the same as φ(n) in the example. Using the letter n is confusing because n usually refers to p * q. Most examples will use the letter k instead. So it looks something like: d = ( 1 + (k * φ(n)) )/e As Firas said, you just need to find a value of k which makes d an integer.

Hi Cézar, your e must be relatively prime to 40 (the totient). This means that the only factor that e and 40 should share is 1. 4 and 40 share the following factors: 1, 2, and 4. So, 4 is not a valid selection for e. Here is a short website that explains it in a slightly different way: www.mathsisfun.com/definitions/relatively-prime.html

Jenn Janesko Thanks!

uumdi It's the same thing as adding the modulus to the negative to make it positive. -17 and 23 are congruent in mod 40 arithmetic.

Great tutorial btw :)

You and me both. :)

Hahaha hopefully not for ever! :D Besides joking i really appreciate your work

Yes dude! It'll work.

Sorry for the late response. For large primes: Dave Evans has a nice video that I used a long time ago to write a program determine relatively quickly whether or not a number is likely to be a prime www.udacity.com/course/viewer#!/c-cs387/l-48684829/e-48754066/m-48719221. There should be libraries out there as well that cover this. One thing, though... Be careful with the (pseudo)random functions that you use to generate numbers. You probably already know all this. There's a nice discussion here of random numbers here: blog.cryptographyengineering.com/2012/02/random-number-generation-illustrated.html.

You are absolutely correct. If I remember correctly, I picked 7 because it was small and in the Euclidean algorithm section, It made a better example.

+kurt giron So what I think is going on is this.. in the step just before we have 1 = 5 - 2(7 - 1(5)), if we multiply the 2 through.. then 1= 5 -2(7) + 2(5)... assuming that the 5 = 1(5).. she combined them to get 3(5) finally 1 = 3(5) - 2(7)

+Dennis M You are exactly right about what I did. Well explained!!

+Jenn Janesko Thank you

+Dennis M am Still confused at this stage, so you mean1=5 -2(7) and -2(-1(5) ? that is 1=5-2(7)+2(5) therefore 1=3(7)+2(5).

+siduduzo manqele 1=5 - 2(7) + 2(5) ---> 1= 1(5) - 2(7) + 2(5) then combine like terms.

Hi Cryophilic, if 17 were positive, then d would simply be 17.

Ok thank you

Hi Jonio, you are right. 9 is not a prime number. But, it is *relatively* prime to 40. *Relatively* is the key word here. A number is relatively prime to another number if the only factors that the two numbers share is 1. For example: NOT relatively prime: 2 because the factors of 2 are 2 and 1. And, 40/2=20 5 because the factors of 5 are 5 and 1. And, 40/5=8 15 because the factors of 15 are 5,3 and 1. And, 40/5=8 YES relatively prime: 3 has factors 3 and 1. Except for 1, there are no common factors that 3 shares with 40. 9 has factors 3, 3 and 1. Except for 1, there are no common factors that 9 shares with 40. 21 has factors 3, 7 and 1. Except for 1, there are no common factors that 21 shares with 40.

First find the other parameters: N = pq = 77 Phi (the totient) = (p-1)(q-1) = 60 e = … Well now, you need to choose some value of "e". It can't have any common factors with Phi (60), so you can't take 2, 3, 4, 5, 6, but you could take 7. If you plan on being able to decrypt, you'll need "d" too, but your question was how to encrypt. HOW ARE YOU transforms to 7, 14, 22, 0, 17, 4, 24, 14, 20 according to your scheme. The encryption formula for RSA is C = M^e mod N. So compute this formula for each number in the list. 7^7 mod 77 = 823 543 mod 77 = 28 14^7 mod 77 = 105 413 504 mod 77 = 42 22^7 mod 77 = 2 494 357 888 mod 77 = 22 0^7 mod 77 = 0 (duh) I'll leave the others to you. Your encrypted message is 28, 42, 22, 0, etc. Notice you can't convert back to letters because the answers are between 0 and 76. To decrypt you need to compute M = C^d mod N. For this you need "d", which is the inverse of "e" mod Phi. You get it by doing the Extended Euclidian Algorithm. Here is a shorthand version of it: Inverse of 7 mod 60: 60 0 (write 60 and 7 in first column, 0 and 1 in second column) 7 1 (because 7 goes 8 times into 60, do Line 1 - 8 x Line 2) 4 -8 (because 4 goes 1 time into 7, do Line 2 - 1 x Line 3) 3 9 (because 3 goes 1 time into 4, do Line 3 - 1 x Line 4) 1 -17 (because 1 goes 3 times into 3, do Line 4 - 3 x Line 5) 0 60 The last line being 0 and 60 proves that we did it right. The inverse you seek is on the previous line next to the 1. In this case it is -17. To get a positive number, add 60 (so 43). You can check that 7 x 43 mod 60 = 1. Voilà.

TheOiseau thank you so much .

You need the inverse of 3 mod 11 200. Here goes. Write 11 200 and 3 in a column. Write 0 and 1 in a second column: 11 200 0 3 1 Because 3 goes 3733 times into 11 200, do Line 1 - 3733 x Line 2 1 -3733 Because 1 goes 3 times into 3, do Line 2 - 3 x Line 3 0 11 200 The last line being 0 and 11 200 shows that we did it right. The inverse is actually on the previous line next to the 1. In this case it is -3733. To get a positive value, add the totient 11 200, so d = 7467. You can check that 3 x 7467 mod 11 200 = 1.

Hi Tom, encoding the letters is a bit beyond the scope of this video. But, there is a simple explanation RSA text encoding here: rosettacode.org/wiki/RSA_code in the first bit. Heed the warnings on the page. :) The code examples there may or may not be correct. Good luck!!

Jenn Janesko thanks very much,was sat here thinking that if I encoded plaintext by giving each letter a number then it would still be vulnerable to basic frequency analysis so much appreciated my learning continues,a really good introductory video by the way, and I now understand euclid alrogithm better as well :)

Hi Roopak Rajpal, that's a great question. If you have a positive result, then that is your answer. So, in your example the answer would be 17.

Thanks a ton!

she didn't say prime , she said RELATIVELY prime with 40 , which means it shares with 40 one common devisor : 1

Romel, this is a SUPER link. Thanks!

Thank you so much! Didn't really understand where the 17 came from, it's now obvious in hindsight :)