I had an exam today where the extended Euclidean algorithm played a key role. I watched your video about 2 hours before the exam. Thanks to you I am 100% sure I got all the questions concerning the algorithm correct, and probably passed the exam.
Wow, thanks so much! I've been trying to understand it for weeks and the TA and professors kept telling me it's super simple and wouldn't help me. They were right, it's super simple! But you actually helped me, thanks!
e has to be relatively prime to our totient. I have added a link above in my video description to a website that gives a quick instruction on how to find a relative prime. Our example totient is 40. And, we have to find a relative prime for our totient with the numbers from 1 to 40. Here is a list of all of these relative primes: 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39 I can pick any of these numbers. For our example, I chose 7 because it was easy to calculate.
God bless you. I had a homework, and they did not show us how to handle a negative private key. Thank you very much. If I could give you hundreds of likes, I swear I would do.
we have a math project that is due today but we were stuck in the RSA question for hoursss and you have saved our life at the last second for REALL thanks😭😭😭😭
Nice job. The only thing I would have added is how messages are actually encrypted with the public key and decrypted with the private key, only for the purposes of completeness.
if I choose an e (1 < e < φ(n)) but when doing the euclidean algorithm at the end I get 4 = 2*2 so there is no 1 there, there's no remainder, that means that my e is invalid?
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
Great video. I'm in computer science but I've never liked doing theoretical math and proofs. I'll do it if there's a practical application in an algorithm I need to understand, but I usually try to avoid it. This was a great explanation because you got to the point and explained everything very clearly.
I also got confused with this step but I get what happened now. So when we multiply the -2 into the brackets, we will get -2(7) and +2(5). Now we also have the 5 in the front which is basically 1(5), so +2(5) and 1(5) are like terms (the 5 is common) so we add the numbers in front and get 3(5). So that will give us 3(5) and -2(7) Hope this helps
to find d another way easier than this d=1+(n*m)/e So that n start 0 to infinity number 0,1,2,3,4,5,6,7,8,9,10,11,12,13,..... The result of the previous equation =just int number but not double for example : 1+(3*40)/7=17.2 Do not take because 17.2 is double 1+(4*40)/7=161/7=23 then d=is 23 this is take because is int note: n in previous equation different from n=(p-1)*(q-1) .....Greetings
@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.
I also got confused with this step but I get what happened now. So when we multiply the -2 into the brackets, we will get -2(7) and +2(5). Now we also have the 5 in the front which is basically 1(5), so +2(5) and 1(5) are like terms (the 5 is common) so we add the numbers in front and get 3(5). So that will give us 3(5) and -2(7) Hope this helps
Thank you sincerely for this; I've been doing a research paper on RSA / cryptology stuff, and this has been a huge help. Just a challenge question -- when we get x = -17, how do we know to subtract that from the totient? I'm already at 30 pages, I'm just going to wave my hands and say "because", but it would be cool to know. 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.
Hi Jdiddy1792, I apologize for the late response. I just got notice of your question. I think that the easiest way to describe the pattern here it is that I am only substituting the numbers that are in between the parentheses. So, in this example, I only care about the 2 inside of the parenthesis. With other example numbers the numbers may be different inside and outside of the parentheses.
Yes and no. For small numbers you could probably use trial and error. But, in real life, in general, the key sizes are so large that this is not manually possible within a lifetime. There are some side channel attacks that would help you to reduce the range of numbers so that you could possibly brute force keys with the help of a computer.
+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)
Jenn, thank you so much for this video. I am taking a class that involves cryptography and I had no clue how RSA worked after reading the teacher's slides but your example cleared it up. You are awesome! Please do an AES and DES video next! ;)
Suppose, using RSA for two prime numbers resulted in encryption and decryption keys having the same values. (Decryption key solved as in video). Is it alright? If not, how to proceed further?
You said at the end that if 17 was positive and not negative, that we would be done. If that were the case and it was 1 = 3(40)+17(7) what would d equal?
if you have questions about the second part, you can find good information in here: math.stackexchange.com/questions/67171/calculating-the-modular-multiplicative-inverse-without-all-those-strange-looking
is there a method to get somewhere near what the value of the private key (d) will be and then use trial and error to get the actual answer ? Also you should have shown why the 32 was right by using the formula for more clarity
What is p? What is q? What is n? What is up with teachers always saying "This is what p is!" and just equate it to some other equation. I mean WHAT IS THE MEANING OF IT? What function does it serve? Why do we need it?
p is a placeholder that is equal to a prime number that you choose. q is a placeholder that is equal to a prime number that you choose. "p" and "q" can be any prime numbers. The second that you choose them, they have to remain fixed for the remainder of the calculations for the public and private keys.
you said if the number infront of 7 was positive we would be done. then in that case, what is d????, you only explained how to get d if the number infront of 7 was negative
Hello, i think there is some issue with your calculations.. (M^7|55)^23|55 == (M^7|55)^3|55 == (M^7|55)^43|55 .. i think that hacker should not be able to use other private key to decode the staff other then the one..
for e why did you choose 7? 3 and 9 also leave a gcd where +1 is at the end. But if you use 3 or 9, d turns out as a different number. So does it matter which relative prime number you use or can d be a different number than what you have??
Hi there, I'm writing a program in rexx that should encrypt files using rsa. However I'm not able to find proper algorythm for large random prime. Although i can use random function to find any random digit. How insecure this would be this any random number (large ones). My lecturer may not even note this if program will work, but I'd like to know for myself.
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.
Does this method work with larger numbers? I'm trying an example where p = 13, q = 31 and d = 7 but I'm getting stuck when doing step 2 of Euclid's Extended Algorithm
Hi Joel, here is how I did it: 1 = 5 - 2( 7 - 1(5) ) This is like saying: 1 = 5 + -2( 7 - 1(5) ) I distributed the -2 over ( 7 - 1(5) ) like this: 1 = 5 + (-2*7) - (-2 * 1(5)) Which is then equal to: 1 = 5 + (- 2(7)) - (-2(5)) Then, if we combine our negatives and positives, we get: 1 = 5 - 2(7) + 2(5) Then we can add together 5 and 2(5), and we get: 1 = 3(5) - 2(7)
Jenn Janesko I don't understand how you got 3(5). You mention that we can add together 5 and 2(5), and we get:1 = 3(5) - 2(7). Can you explain that more? Thank you.
Matthew Luong Never mind. I got it. So you do 5+2(5) = 15. Then you would have to convert it to something like a(b). I would guess that two number that multiply 15 is 3(5). Thank you! Your video is a life saver!
Hi LadyLuck zaan, here is how I got this: It starts with the line before: 1 = 5 - 2( 7 - 1(5) ) I want to simplify my equation. So, first, I multiple -2 by the 7 and the -1(5) in the parenthesis . This results in: 1= 5 - 2(7) + 2(5) From here, I combine the 5 and the 2(5) by adding them together which results in: 1 = 3(5) - 2(7)
Jenn Janesko is this normal algebric maths or is this a special maths for RSA because I thought that 5-2 you cant separate the -2 just like that. 5-2(7-1(5)) can also be written as, (5-2)(7-1(5))and 5 has to be multiplied with the other bracket and so does -2 as well. so I still dont get how u simpliefied that step, I hope Im clear.
Jenn Janesko "From here, I combine the 5 and the 2(5) by adding them together which results in:1 = 3(5) - 2(7)" How is this possible, combining 5 and 2(5) should have given 7(5) because a positive sign is in between. Can you Please explain??
Sanjok Gurung Hi Sanjok Gurung, thank you for the question. I am performing an action here called "combining like terms". It goes like this: When I have 1 = 5 - 2(7) + 2(5) , I can rewrite it is the following: 1= 1(5) - 2(7) + 2(5) I can add the 1 to the 5 in this equation because 1 multiplied by 5 is equal to 5. You can do this for any number. From here, I can see that I have "like terms" with 1(5) and 2(5). My like term is 5. There is a rule in maths that allows you to combine like terms by adding the values together that are on the outside of the parenthesis. So, in this case I can add the 1 in 1(5) and the 2 in 2(5), and this gives me 3(5). Khan Academy has a great video that gives more information about like terms here: ua-cam.com/video/CLWpkv6ccpA/v-deo.html .
so how do I number each letter to then encode using RSA? I tried the basic a=1,b=2 etc, but t=20 gives a result of 0, which is obviously not what I want, bit confused,hope someone can help
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 :)
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.
In the step before I got to the line with -17, I had the following equation: 1= 3(40 -5(7)) -2(7) If I distrubte the 3 over 40 and -5(7), I get: 1 = 3(40) -3*5(7) - 2(7) This simplifies to: 1= 3(40) - 15(7) - 2(7) This simplifies to: 1= 3(40) - 17(7) When using the extended euclidean algorithm for RSA, you want to find the final number from the algorithm that sits in front of the number that you selected for e. In this case, the number is -17.
+siva ram Mallela The short answer here is no. I don't want to release an insecure implementation of this. There are already libraries out there that have been coded to do this. You can see some suggestions here: stackoverflow.com/questions/8539441/private-public-encryption-in-python-with-standard-library . Those suggestions are for Python. You will need to do a search for your target programming language.
I came here for the decription of Euclidean Algorithm. The steps were heavily glossed over. Step 1 was absolutely fine, but Step 2 -- I don't understand half the stuff she did. She doesn't describe where she gets the number replacements from. Why replace 2 with 7-1(5)? She doesn't say why 7, or why 5. Why not replace 2 with 4-1(2)? I don't know, that step wasn't explained. And the other steps in Step 2 are equally obscure. Good try, and I could tell you were trying to be as clear as possible, but I need to implement this algorithm in a program, and so I need to know the specifics about why you're replacing 2 with 7-1(5), and I think your video could be improved if you went into more detail in Step 2 of this tutorial (keep step1 as it is, that's perfectly clear).
I want to add that it was this video, regardless of the poor explaining of Step 2, that ended up getting my program right. Using this video along with wikipedia's Extended Euclidian Algorithm page, I was able to implement the algorithm just fine. For anybody wondering, in the Euclidian Algorithm page use the pseudocode to create a function, and put in t for n and a for e, and have the return value become d
You assume that e has to be prime. You're wrong. It has to be COPRIME to phi(n). (Yes, I do understand that prime numbers are subset to coprime numbers to any given X)
Pragmatic Ways The chosen value for e CAN be prime, but it isn't required. What IS required is that e has to be less than the totient and share no common factors with it other than 1 (E and the totient must be co-prime or relatively prime to each other).
I had an exam today where the extended Euclidean algorithm played a key role. I watched your video about 2 hours before the exam. Thanks to you I am 100% sure I got all the questions concerning the algorithm correct, and probably passed the exam.
I procrastinated on an assignment that I shouldn't have procrastinated on, and this actually saved my life.
Fastest and clearest video of this algorithm -- perfect, thanks!
Wow, thanks so much! I've been trying to understand it for weeks and the TA and professors kept telling me it's super simple and wouldn't help me. They were right, it's super simple! But you actually helped me, thanks!
I'm glad you found it to be helpful. I actually made this so that I could remember the steps for an exam. :)
This was so helpful - couldn't find that last step (40-17) anywhere on the internet, so thank you so much!!
e has to be relatively prime to our totient. I have added a link above in my video description to a website that gives a quick instruction on how to find a relative prime.
Our example totient is 40. And, we have to find a relative prime for our totient with the numbers from 1 to 40. Here is a list of all of these relative primes:
3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39
I can pick any of these numbers. For our example, I chose 7 because it was easy to calculate.
God bless you. I had a homework, and they did not show us how to handle a negative private key. Thank you very much. If I could give you hundreds of likes, I swear I would do.
we have a math project that is due today but we were stuck in the RSA question for hoursss and you have saved our life at the last second for REALL thanks😭😭😭😭
Oh my gosh thank you! I've been looking everywhere for someone who actually explains this. Thank you so much.
Nice job. The only thing I would have added is how messages are actually encrypted with the public key and decrypted with the private key, only for the purposes of completeness.
if I choose an e (1 < e < φ(n)) but when doing the euclidean algorithm at the end I get 4 = 2*2 so there is no 1 there, there's no remainder, that means that my e is invalid?
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!
Great video. I'm in computer science but I've never liked doing theoretical math and proofs. I'll do it if there's a practical application in an algorithm I need to understand, but I usually try to avoid it. This was a great explanation because you got to the point and explained everything very clearly.
The third step of the back substitution makes no sense. How did you get 3(5) - 2(7)?????????
I also got confused with this step but I get what happened now. So when we multiply the -2 into the brackets, we will get -2(7) and +2(5). Now we also have the 5 in the front which is basically 1(5), so +2(5) and 1(5) are like terms (the 5 is common) so we add the numbers in front and get 3(5). So that will give us 3(5) and -2(7)
Hope this helps
to find d another way easier than this
d=1+(n*m)/e
So that n start 0 to infinity number
0,1,2,3,4,5,6,7,8,9,10,11,12,13,.....
The result of the previous equation =just int number but not double
for example :
1+(3*40)/7=17.2
Do not take because 17.2 is double
1+(4*40)/7=161/7=23
then d=is 23
this is take because is int
note: n in previous equation different from n=(p-1)*(q-1) .....Greetings
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.
how the hell do you get from 1 = 5-2(7-1(5)) to 1 = 3(5)-2(3)
I also got confused with this step but I get what happened now. So when we multiply the -2 into the brackets, we will get -2(7) and +2(5). Now we also have the 5 in the front which is basically 1(5), so +2(5) and 1(5) are like terms (the 5 is common) so we add the numbers in front and get 3(5). So that will give us 3(5) and -2(7)
Hope this helps
@@lushenmoodley771 I was also confused .....thank you for the explanation
I just want you to know that I appreciate your video. This certainly helped.
Thank you so much for explaining this! If only my professor knew how to explain it as simple as you did! I cannot thank you enough!
Its been 9 years since this comment . Just wondering how you are doing in the present ?
Every damn exam period I come back to this video.
Great tutorial btw :)
You and me both. :)
Hahaha hopefully not for ever! :D Besides joking i really appreciate your work
Thank you sincerely for this; I've been doing a research paper on RSA / cryptology stuff, and this has been a huge help.
Just a challenge question -- when we get x = -17, how do we know to subtract that from the totient? I'm already at 30 pages, I'm just going to wave my hands and say "because", but it would be cool to know. Thank you!
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.
9 is not prime @ 1:55? It can be divided by three..
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.
this deserves the noble peace prize
In Euclidean algorithm if you make m steps, you will have to make m steps
in substitution to reach the answer. Hope this helps to clear things out.
Hi Jdiddy1792, I apologize for the late response. I just got notice of your question. I think that the easiest way to describe the pattern here it is that I am only substituting the numbers that are in between the parentheses. So, in this example, I only care about the 2 inside of the parenthesis. With other example numbers the numbers may be different inside and outside of the parentheses.
Thank uuuuuuuuuu!! For 3 hrs I was trying to figure out how to calculate d and now I know. I think I'll pass in the externals now.
Thank you so much (: I had such a hard time figuring out how Extended Euclidean Algorithm works but after your explanation, it is so clear!
Yes and no. For small numbers you could probably use trial and error. But, in real life, in general, the key sizes are so large that this is not manually possible within a lifetime. There are some side channel attacks that would help you to reduce the range of numbers so that you could possibly brute force keys with the help of a computer.
You are the best! 7 hours I was trying to understand how to get d number and now I know. THANKS!
Life saver! Watching this and another video on basic euclidean algorithm has made me understand it
hi in back substitution
how did you find
i got confused?
1=3(5)-2(7)
+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.
Thank you - I was able to use your explanation to write a couple of functions to perform the same procedure.
Thank you for this video. I've looked at a number of other sources and your video makes the most sense to me :).
Jenn, thank you so much for this video. I am taking a class that involves cryptography and I had no clue how RSA worked after reading the teacher's slides but your example cleared it up. You are awesome!
Please do an AES and DES video next! ;)
wait till you learn about asymmetrical cryptography
Suppose, using RSA for two prime numbers resulted in encryption and decryption keys having the same values. (Decryption key solved as in video). Is it alright? If not, how to proceed further?
You said at the end that if 17 was positive and not negative, that we would be done. If that were the case and it was 1 = 3(40)+17(7) what would d equal?
Hi Cryophilic, if 17 were positive, then d would simply be 17.
Ok thank you
where did you get -17 in the last list of step 2?
Great Video. But Can Someone Say How did we get 1= 3 (5) - 2 (7)??
if you have questions about the second part, you can find good information in here: math.stackexchange.com/questions/67171/calculating-the-modular-multiplicative-inverse-without-all-those-strange-looking
Romel, this is a SUPER link. Thanks!
Please post more on discrete math topics! You are a great explainer!
@AvidLearner11 Sorry for the late response. I'm not very familiar with the Reed-Solomon encoding algorithm, so I won't be able to help.
is there a method to get somewhere near what the value of the private key (d) will be and then use trial and error to get the actual answer ?
Also you should have shown why the 32 was right by using the formula for more clarity
What is p? What is q? What is n? What is up with teachers always saying "This is what p is!" and just equate it to some other equation. I mean WHAT IS THE MEANING OF IT? What function does it serve? Why do we need it?
p is a placeholder that is equal to a prime number that you choose. q is a placeholder that is equal to a prime number that you choose. "p" and "q" can be any prime numbers. The second that you choose them, they have to remain fixed for the remainder of the calculations for the public and private keys.
you said if the number infront of 7 was positive we would be done. then in that case, what is d????, you only explained how to get d if the number infront of 7 was negative
Hello, i think there is some issue with your calculations..
(M^7|55)^23|55 == (M^7|55)^3|55 == (M^7|55)^43|55 .. i think that hacker should not be able to use other private key to decode the staff other then the one..
how choose e=7 ?
so in the e of the first example can be 3 also?
for e why did you choose 7?
3 and 9 also leave a gcd where +1 is at the end.
But if you use 3 or 9, d turns out as a different number.
So does it matter which relative prime number you use or can d be a different number than what you have??
Hi there, I'm writing a program in rexx that should encrypt files using rsa. However I'm not able to find proper algorythm for large random prime. Although i can use random function to find any random digit. How insecure this would be this any random number (large ones). My lecturer may not even note this if program will work, but I'd like to know for myself.
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.
Could you possibly do Reed-Solomon encoding examples as well?
in the select a number that is relatively prime, could you not choose 3 instead of 7?
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.
Equation in step 1 is called a Diophantine equation.
Great video!
2:20 - 9 is not a prime number? Because 3x3?
Good explanation for RSA though. Help me understand a bit more. Thanks.
she didn't say prime , she said RELATIVELY prime with 40 , which means it shares with 40 one common devisor : 1
how did you came up with the 3 at the end
private keys are (11,5,23)
Does this method work with larger numbers? I'm trying an example where p = 13, q = 31 and d = 7 but I'm getting stuck when doing step 2 of Euclid's Extended Algorithm
Yes dude! It'll work.
If we got 17 instead of -17 in the last step then what would the value of d be?
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!
modular multiplicative inverse{d = ee−1(mode φ(n) ) } where : e=27 and n=55 please help me calculate 'd' and the pseudo RSA algo is
Can show encryption and decryption for the same if M = 88
Why are we taking e=7 and not e=3??
whey you chose e=7 you can chose e=3?
In the 3rd part where you chose e, you included the number 9 which is not a prime number.
Otherwise, Great video and very helpful!
In the back substitution, how did you get 1 = 3(5) - 2(7). Thats where i got lost
Hi Joel, here is how I did it:
1 = 5 - 2( 7 - 1(5) )
This is like saying:
1 = 5 + -2( 7 - 1(5) )
I distributed the -2 over ( 7 - 1(5) ) like this:
1 = 5 + (-2*7) - (-2 * 1(5))
Which is then equal to:
1 = 5 + (- 2(7)) - (-2(5))
Then, if we combine our negatives and positives, we get:
1 = 5 - 2(7) + 2(5)
Then we can add together 5 and 2(5), and we get:
1 = 3(5) - 2(7)
Jenn Janesko Thanks
Jenn Janesko I don't understand how you got 3(5). You mention that we can add together 5 and 2(5), and we get:1 = 3(5) - 2(7). Can you explain that more? Thank you.
Matthew Luong
Never mind. I got it. So you do 5+2(5) = 15. Then you would have to convert it to something like a(b). I would guess that two number that multiply 15 is 3(5). Thank you! Your video is a life saver!
Matthew Luong Good job!
can anyone explain in more details how did she get 3=(5) -2 (7)
Hi LadyLuck zaan, here is how I got this:
It starts with the line before:
1 = 5 - 2( 7 - 1(5) )
I want to simplify my equation. So, first, I multiple -2 by the 7 and the -1(5) in the parenthesis . This results in:
1= 5 - 2(7) + 2(5)
From here, I combine the 5 and the 2(5) by adding them together which results in:
1 = 3(5) - 2(7)
Jenn Janesko
great thanks!
Jenn Janesko is this normal algebric maths or is this a special maths for RSA because I thought that 5-2 you cant separate the -2 just like that. 5-2(7-1(5)) can also be written as, (5-2)(7-1(5))and 5 has to be multiplied with the other bracket and so does -2 as well. so I still dont get how u simpliefied that step, I hope Im clear.
Jenn Janesko "From here, I combine the 5 and the 2(5) by adding them together which results in:1 = 3(5) - 2(7)" How is this possible, combining 5 and 2(5) should have given 7(5) because a positive sign is in between. Can you Please explain??
Sanjok Gurung Hi Sanjok Gurung, thank you for the question. I am performing an action here called "combining like terms". It goes like this:
When I have 1 = 5 - 2(7) + 2(5) , I can rewrite it is the following:
1= 1(5) - 2(7) + 2(5)
I can add the 1 to the 5 in this equation because 1 multiplied by 5 is equal to 5. You can do this for any number.
From here, I can see that I have "like terms" with 1(5) and 2(5). My like term is 5. There is a rule in maths that allows you to combine like terms by adding the values together that are on the outside of the parenthesis. So, in this case I can add the 1 in 1(5) and the 2 in 2(5), and this gives me 3(5). Khan Academy has a great video that gives more information about like terms here: ua-cam.com/video/CLWpkv6ccpA/v-deo.html .
Why in 1=5-2(2), do you substitute in for only one of the 2s? I tried with substituting in for both 2s, and it didnt work.
so how do I number each letter to then encode using RSA? I tried the basic a=1,b=2 etc, but t=20 gives a result of 0, which is obviously not what I want, bit confused,hope someone can help
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 :)
Honestly you just save me! great explanation! I was a bit lost
i got stuck while trying it with this equation
20 x + 3 y = 1
Can someone help me do the Euclidean Algorithm with e=3 and 11,200 as the totient of n? I'd need this for a math project. Thank you
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.
Beautiful explanation! Was stummped by the book and this is the clearest source on th etopic for beginners out there!
Not getting the back substitution at all here
+michael 0184 See the explanation from Gian Franco Dy in the comments below. It goes through step by step. I hope this helps you.
+Jenn Janesko yea that doesnt make much sene to me either! I cnt understand the pattern to finding out what number goes where when rearranging them.
In the step before I got to the line with -17, I had the following equation:
1= 3(40 -5(7)) -2(7)
If I distrubte the 3 over 40 and -5(7), I get:
1 = 3(40) -3*5(7) - 2(7)
This simplifies to:
1= 3(40) - 15(7) - 2(7)
This simplifies to:
1= 3(40) - 17(7)
When using the extended euclidean algorithm for RSA, you want to find the final number from the algorithm that sits in front of the number that you selected for e. In this case, the number is -17.
Thank you so much! Didn't really understand where the 17 came from, it's now obvious in hindsight :)
can you please give the code to implement this ??
+siva ram Mallela The short answer here is no. I don't want to release an insecure implementation of this. There are already libraries out there that have been coded to do this. You can see some suggestions here: stackoverflow.com/questions/8539441/private-public-encryption-in-python-with-standard-library . Those suggestions are for Python. You will need to do a search for your target programming language.
I came here for the decription of Euclidean Algorithm. The steps were heavily glossed over. Step 1 was absolutely fine, but Step 2 -- I don't understand half the stuff she did. She doesn't describe where she gets the number replacements from. Why replace 2 with 7-1(5)? She doesn't say why 7, or why 5. Why not replace 2 with 4-1(2)? I don't know, that step wasn't explained.
And the other steps in Step 2 are equally obscure.
Good try, and I could tell you were trying to be as clear as possible, but I need to implement this algorithm in a program, and so I need to know the specifics about why you're replacing 2 with 7-1(5), and I think your video could be improved if you went into more detail in Step 2 of this tutorial (keep step1 as it is, that's perfectly clear).
I want to add that it was this video, regardless of the poor explaining of Step 2, that ended up getting my program right. Using this video along with wikipedia's Extended Euclidian Algorithm page, I was able to implement the algorithm just fine. For anybody wondering, in the Euclidian Algorithm page use the pseudocode to create a function, and put in t for n and a for e, and have the return value become d
Runn Overdrive Good job, Runn Overdrive!
Helpful in understanding the concept of key generation
why are u taking 7, 3 is also thee
Oh thank you so much. I learn about RSA but stuck in step calculate d many hours =)))
This is a very cool tip. I looked this up and learned more about how these equations work. Thanks!
how we get 7 explain plz
5 is also prime....
You assume that e has to be prime. You're wrong. It has to be COPRIME to phi(n). (Yes, I do understand that prime numbers are subset to coprime numbers to any given X)
Can you please explain more?
Pragmatic Ways The chosen value for e CAN be prime, but it isn't required. What IS required is that e has to be less than the totient and share no common factors with it other than 1 (E and the totient must be co-prime or relatively prime to each other).
Thanks so much, this was great in understanding how to do this.
amazing video! finally I understand all the concepts! Thanks!
Literally saving me rn!
I like your voice. So nice to hear..
Thanx @Jenn...
Thank you so much...best video on RSA
THANK YOU!!
MERCIE!!
CHOKRAN!!
ARIGATO!!
Great explanation
Thank You very much for the lucid explanation. Its a big help . Cheers !!
Amazing! i'm so grateful, nice video.
Excellent Video. Thanks a lot!
Perfection. Great example
Thanks! Great explanation.
I'm greatful.
this video really helped me . Thank you
really god work here, liked
Great example, thank you.
thanks a lot, your explanation is clear and simple... you are awesome :)
Beautiful. Thank you very much.