Thank you so much for this. Looking back, my professor explained it without explicitly stating what you emphasized at 4:19. You're saving my Discrete Math grade, can't thank you enough!
Okay, so everyone can explain the basic concept of how the keys are made, but I can't find out how the "keys" are applied to the message without being able to compare several messages for patterns. If I was to encrypt the letter "a" and then encrypt "b" or "aa", the encrypted messages differ greatly. Also, a simple single letter encryption, still has a very long encrypted cipher and it doesn't appear to be padding, because then the padding would repeat for all short messages. Is a hash of the message, added to the encryption algorithm?
Jay H I think the simple answer to your first question is that you encrypt large amounts of data in one go. So if the public modulo has 150 digits then your message can have roughly up to 150 digits. So you could probably encrypt the first line of your comment in one go, rather than word for word ( you can regard a space and a full stop as letters to prevent all the words blending together). If you you want to encode something short like the letter `a' and use it once then the encrypted message will be large and you don't need to worry that it will be decoded. If you were going to encrypt word by word and were worried that there would be a pattern then I suppose you could add a random word before or after your message to hide the pattern. Someone who works on cryptography in business or defense might be able to explain what is done in day to day use. Hope that helps.
I am not matematicien and i mostly understand that if you don have the private key you can calculate it. I am wrong? And if i am right... Does it not means that rsa is unusefull for criptographic goals?
RSA is useful for cryptography because everyone can encode using the publicly available key and everyone knows how the encoding is carried out but only some know the private key that decodes messages.
Yes but in this demo... You get the secret decription code by yourself. By cracking!! I thought that reverse engineering the encoding was allmost imposible but if you can "crack" to get the private key... Well maybe i just don't understand.
+martiarenax3 The video you watched is a solution to a typical exam question to test whether a student understands how RSA works. Try watching one of my other videos ruclips.net/video/IBocnou79yI/видео.html which explains how RSA code can make public key encryption possible. Hope that helps.
ok, it's done. Now i am curious about the algorithm to generate huge prime numbers. About the main question, i still think i have to trust that the computerized capability would not crack the code, as you did in the manual example but with simple numbers, due to the fact that the real world works with huge primes but computerized calculations.
Every other video: "Don't worry if you don't understand this now, we'll explain it more as we continue with the video" This video: "If you don't understand this first part then just quit." LMFAO
If I would implement your code to digital data I would be able to convert blocks of say 11 bits. If for practical reasons would limit it to messages of a byte. I would not have a very efficient code. I would map 256 messages on a space of 3131 codewords. Would in this case a data reduction be usefull In general if through datareduction techniques can compress a message, would it then also be possible to compress the coded message?
+Randell Heyman Hi, here's the problem: 107592, 90097, 56315, 106274, 100077, 82313, 92563, 66060, 110984, 100077, 125000, 38982, 125281, 59515, 107250, 110309, 27000, 52934, 92948, 85456, 59515, 111113, 42959, 27575, 6711, 28518, 76945, where n= 133897 and e=3. In the same text file write down the two prime numbers that are used, p and q, the private key, d, and the final phrase that you get. Coding: 00=A, 01=B, 02=C etc The process of decryption needs repeating more than once and makes a 'phrase'. I can't get anything out of it. Ideas please. Thanks! Apprecaited
+Paul Abraham 133897 is the product of 2 primes, p and q. you need to work out what p and q are. this requires a bit of commonsense and trial and error. once you have p and q you can follow my video to work out phi of n, then the decode key and then the decoded message.
+Randell Heyman thanks for your help. I've found my d, however I'm not 100% sure its right as there is nothing to back substitute in the Euclidean and its negative. so d= m - my value. once I put it in the equation my values come out but no phrase even after processing twice or more. where could I be going wrong. thanks for your help.
At the top right I have 1=6-1 (5 ). I want to get rid of the 5. The second bottom on the left has 11=1 (6)+5. This means that 5=11-1 (6). So I substitute this into the top right equation and I get 1=2 (6)-1 (11).
Hi Randell, Could you please point me in the right direction. I'm trying to solve an encryption challenge. There is a ciphertext (128 bytes) encrypted with The Rabin Cryptosystem. I have a public key N (128 bytes). I can factor the N to get the p and q, but the p = q (i.e. N is a perfect square). And that breaks all my attempts to decrypt the ciphertext. Any Ideas how to proceed here?
if i try to Find the multiplicative inverse of each nonzero element in Z5. using you method i get one as the answer. the correct answer is 1,3,2,4 for 1,2,3,4 respectively. my question is why do i get one when i try to use your method? i hope you get back to me, thanks
Exponents are used twice. Firstly, we raise our message to a power to encode it. Then the party that knows the decoding key can raise the encoded message to the correct power to get back the original message.
Don't drop quite yet! See my video Euler's theorem made easy. If you have trouble with that video you might need to have a look at modular arithmetic made easy, Euler totient function made easy and greatest common divisor made easy as well. Hope that helps.
Hi, you have a severe error there.. not only 533 is valid decoder, but also numbers 233,833,1133,1433,1733,2033,2633 and 2933.. for example 3051^233|3131 = 2318 in rsa only one decoder should be valid, no?
There is nothing in the standard RSA code explanation that says that the decoding key is unique. See no. 6 of Practical Applications at www.di-mgt.com.au/rsa_alg.html What is happening in my example is that x^300 =1 mod 3131 for all x not multiples of 31 or 101.
am i not mistaken that you are trying to explain how RSA works in real world? Does it mean that every RSA generated public/private key used for example in ssl has one or more other keys to decrypt data that might be used by NSA or Chinese gov? :) in your example there is even 8 possible private keys.. so the brute force may return value quite easy if the same mechanism is used in ssl..
This video was about the mathematics of RSA code. To understand how RSA code is used in the real world try to find some videos by working cryptographers or academics who specialise in cryptography. To respond a bit more directly you have found that there are some numbers below (p-1)*(q-1) that have the same property that a^((p-1)*(q-1))=1 mod 3131. Generally there are not that many divisors of (p-1)*(q-1) that will have that property. By using prime numbers with say 150 digits it is still too hard to find these special numbers that enable decoding. Well done on spotting this extra aspect to RSA code.
You are correct and there are actually infinitely many decoding keys. If you search a bit more, you'll find that any decoding key in the form 233+t*300, t=0,1,2,3,4,...,infinity can be used by this example. But In the real world the (p-1)*(q-1) number is 4096 bits. That's a HUGE number of possible combinations - that huge that we don't have a word for so large number. And it happens that the larger the (p-1)*(q-1) is, the longer the repeating interval is. For example with p=2, q=7 if I recall correctly the interval is just 5. The larger product of p-1 and q-1, the larger the interval. With a gigantically HUGE number like the 4096 bits one the interval is so big that... good luck trying out to find the decoding key in it. So basically - yes, there are infinitely many decoding keys, but the probability of finding just one is really really really small, even with modern supercomputer working non stop for many years.
It's a good video...but can you explain me any program of RSA in MVC used in encryption & decryption.....Please upload or send me on my email if you can......thanku so much...
Hi Anisha, there are commercial RSA encryption/decryption programmes that you can probably buy. Alternatively you can write, or have someone write, a RSA coding program using Maple or freeware programs like Pari or Sage. Hope that helps.
i think 3000t + 1 , the ( plus 1 ) makes the remainder of 3000t+1 divided by 3000 always = 1 , just like the result of 1 (mod 3000) . So, 3000t +1 becomes 1(mod 3000). isn't make sense?
Thanks for your feedback. If there is something you don't understand let me know. If you just want a gentle introduction to RSA have a look at my video How encryption works.
Wow, the first time that a 7 min Video took me 40 min to watch.
Thank you, great explanation!
Thank you so much for this. Looking back, my professor explained it without explicitly stating what you emphasized at 4:19.
You're saving my Discrete Math grade, can't thank you enough!
Half of your 13,900 views is me trying to get it :) With the wikipedia pages and your video, I am almost there. Thank you very much for uploading.
Thanks for the feedback. If there is anything you still don't understand let me know and I will try to explain.
Randell Heyman Thank you. I solved my last doubts today!
do more man, you are amazing!
Very good explanation. Thanks.
Glad it was helpful!
That was good explanation , mate
Okay, so everyone can explain the basic concept of how the keys are made, but I can't find out how the "keys" are applied to the message without being able to compare several messages for patterns. If I was to encrypt the letter "a" and then encrypt "b" or "aa", the encrypted messages differ greatly. Also, a simple single letter encryption, still has a very long encrypted cipher and it doesn't appear to be padding, because then the padding would repeat for all short messages. Is a hash of the message, added to the encryption algorithm?
Jay H I think the simple answer to your first question is that you encrypt large amounts of data in one go. So if the public modulo has 150 digits then your message can have roughly up to 150 digits. So you could probably encrypt the first line of your comment in one go, rather than word for word ( you can regard a space and a full stop as letters to prevent all the words blending together). If you you want to encode something short like the letter `a' and use it once then the encrypted message will be large and you don't need to worry that it will be decoded. If you were going to encrypt word by word and were worried that there would be a pattern then I suppose you could add a random word before or after your message to hide the pattern. Someone who works on cryptography in business or defense might be able to explain what is done in day to day use. Hope that helps.
I am not matematicien and i mostly understand that if you don have the private key you can calculate it. I am wrong? And if i am right... Does it not means that rsa is unusefull for criptographic goals?
RSA is useful for cryptography because everyone can encode using the publicly available key and everyone knows how the encoding is carried out but only some know the private key that decodes messages.
Yes but in this demo... You get the secret decription code by yourself. By cracking!! I thought that reverse engineering the encoding was allmost imposible but if you can "crack" to get the private key... Well maybe i just don't understand.
+martiarenax3 The video you watched is a solution to a typical exam question to test whether a student understands how RSA works. Try watching one of my other videos ruclips.net/video/IBocnou79yI/видео.html
which explains how RSA code can make public key encryption possible. Hope that helps.
ok
ok, it's done. Now i am curious about the algorithm to generate huge prime numbers. About the main question, i still think i have to trust that the computerized capability would not crack the code, as you did in the manual example but with simple numbers, due to the fact that the real world works with huge primes but computerized calculations.
Every other video:
"Don't worry if you don't understand this now, we'll explain it more as we continue with the video"
This video:
"If you don't understand this first part then just quit."
LMFAO
Yeah. I was pretty direct.
I do now have videos that can help. Modular arithmetic made easy, modular inverse made easy etc.
Thank you so much. This helped a lot.
Great.
best teacher evah
Thanks for the feedback. It's great when people understand public key encryption like RSA; such a clever idea.
If I would implement your code to digital data I would be able to convert blocks of say 11 bits. If for practical reasons would limit it to messages of a byte. I would not have a very efficient code. I would map 256 messages on a space of 3131 codewords.
Would in this case a data reduction be usefull
In general if through datareduction techniques can compress a message, would it then also be possible to compress the coded message?
I don't see why you can't compress then code or code then compress. But I don't consider myself an expert on practical day to day coding.
Hi Randell, i'm stuck with a piece of coursework - video is great. Could you help me out please?
+Paul Abraham Hi. What are you stuck on ?
+Randell Heyman
Hi, here's the problem:
107592, 90097, 56315, 106274, 100077, 82313, 92563, 66060, 110984, 100077, 125000,
38982, 125281, 59515, 107250, 110309, 27000, 52934, 92948, 85456, 59515, 111113,
42959, 27575, 6711, 28518, 76945,
where n= 133897 and e=3.
In the same text file write down the two prime numbers that are used, p and q, the private key, d,
and the final phrase that you get.
Coding: 00=A, 01=B, 02=C etc
The process of decryption needs repeating more than once and makes a 'phrase'. I can't get anything out of it.
Ideas please.
Thanks! Apprecaited
+Paul Abraham 133897 is the product of 2 primes, p and q. you need to work out what p and q are. this requires a bit of commonsense and trial and error. once you have p and q you can follow my video to work out phi of n, then the decode key and then the decoded message.
Great. Thank you. Is there a logical approach to finding the primes? Thanks
+Randell Heyman
thanks for your help.
I've found my d, however I'm not 100% sure its right as there is nothing to back substitute in the Euclidean and its negative. so d= m - my value.
once I put it in the equation my values come out but no phrase even after processing twice or more.
where could I be going wrong. thanks for your help.
@5:50 How did you get the 2 though?
At the top right I have 1=6-1 (5 ). I want to get rid of the 5. The second bottom on the left has 11=1 (6)+5. This means that 5=11-1 (6). So I substitute this into the top right equation and I get 1=2 (6)-1 (11).
@@RandellHeyman I think I get it. Is it that the 2 represents how many 6's you have from the result of the substitution? I appreciate your response :)
At 03:56 , I think on the left of the equation it should be (x^197 mod 3131)^d. How it become (x^197)^d?
Hi Randell,
Could you please point me in the right direction.
I'm trying to solve an encryption challenge. There is a ciphertext (128 bytes) encrypted with The Rabin Cryptosystem. I have a public key N (128 bytes). I can factor the N to get the p and q, but the p = q (i.e. N is a perfect square). And that breaks all my attempts to decrypt the ciphertext. Any Ideas how to proceed here?
I think Rabin needs distinct primes. I don't see how it would work with p=q.
I am lost from 3:40. Why did you write x^(197d) = x (mod 3131)? When did you come to this conclusion? I am having trouble figuring that out.
I have uploaded a video that explains.
@@RandellHeyman > Thank you!
This is so helpful thank you very very much!
if i try to Find the multiplicative inverse of each nonzero element in Z5. using you method i get one as the answer. the correct answer is 1,3,2,4 for 1,2,3,4 respectively. my question is why do i get one when i try to use your method? i hope you get back to me, thanks
Hi. I am not sure what you are asking. The inverse of 3 is 2 since 3x2=6=1 in Z5. Similarly the inverse of 4 is 4.
+Randell Heyman thanks for replying so fast. my question is how did u find that the answer for inverse of 4 is 4. or inverse of 2 is 3?
+HARERIMANA Radjab is it like try and error ?
Now I understand your question. Have a look at my video `Modular inverse made easy'. Here's a link ruclips.net/video/mgvA3z-vOzc/видео.html
This was so easy to follow
But if the input character is 31 or 101 the system of encryption is erroneous because they are not coprime with the modulus correct?
FreemonSandlewould If you use two 150 digit prime numbers, say p and q, then any message less than 150 digits must be coprime tp p and q.
Randell, you made an error at the end of the video with your encryption, you used the modulus of 3131 in the encryption and decryption.
Why do you think that I made an error? RSA uses the same modulus for encryption and decryption as I describe in the video.
Thanks Sir.
Epic
Thx for the comment.
Can’t get intuition on why exponents used in RSA?
Exponents are used twice. Firstly, we raise our message to a power to encode it. Then the party that knows the decoding key can raise the encoded message to the correct power to get back the original message.
That's just what my maths teacher used to yell when I got lost....
I do so between 2:12 and 3:26.
Should I drop back a class...?
Don't drop quite yet! See my video Euler's theorem made easy. If you have trouble with that video you might need to have a look at modular arithmetic made easy, Euler totient function made easy and greatest common divisor made easy as well. Hope that helps.
Show your working boy !! Show your working !!!!
Thanks for the feedback. If you tell me where you first get stuck I am happy to try t o explain.
Hi, you have a severe error there.. not only 533 is valid decoder, but also numbers 233,833,1133,1433,1733,2033,2633 and 2933..
for example 3051^233|3131 = 2318
in rsa only one decoder should be valid, no?
There is nothing in the standard RSA code explanation that says that the decoding key is unique. See no. 6 of Practical Applications at www.di-mgt.com.au/rsa_alg.html
What is happening in my example is that x^300 =1 mod 3131 for all x not multiples of 31 or 101.
am i not mistaken that you are trying to explain how RSA works in real world? Does it mean that every RSA generated public/private key used for example in ssl has one or more other keys to decrypt data that might be used by NSA or Chinese gov? :)
in your example there is even 8 possible private keys.. so the brute force may return value quite easy if the same mechanism is used in ssl..
This video was about the mathematics of RSA code. To understand how RSA code is used in the real world try to find some videos by working cryptographers or academics who specialise in cryptography.
To respond a bit more directly you have found that there are some numbers below (p-1)*(q-1) that have the same property that a^((p-1)*(q-1))=1 mod 3131. Generally there are not that many divisors of (p-1)*(q-1) that will have that property. By using prime numbers with say 150 digits it is still too hard to find these special numbers that enable decoding. Well done on spotting this extra aspect to RSA code.
You are correct and there are actually infinitely many decoding keys. If you search a bit more, you'll find that any decoding key in the form 233+t*300, t=0,1,2,3,4,...,infinity can be used by this example.
But
In the real world the (p-1)*(q-1) number is 4096 bits. That's a HUGE number of possible combinations - that huge that we don't have a word for so large number.
And it happens that the larger the (p-1)*(q-1) is, the longer the repeating interval is. For example with p=2, q=7 if I recall correctly the interval is just 5. The larger product of p-1 and q-1, the larger the interval. With a gigantically HUGE number like the 4096 bits one the interval is so big that... good luck trying out to find the decoding key in it.
So basically - yes, there are infinitely many decoding keys, but the probability of finding just one is really really really small, even with modern supercomputer working non stop for many years.
It's a good video...but can you explain me any program of RSA in MVC used in encryption & decryption.....Please upload or send me on my email if you can......thanku so much...
Hi Anisha, there are commercial RSA encryption/decryption programmes that you can probably buy. Alternatively you can write, or have someone write, a RSA coding program using Maple or freeware programs like Pari or Sage. Hope that helps.
i dont know why 3000t+1 would become 1 (mod 3000) at 3:00
i think 3000t + 1 , the ( plus 1 ) makes the remainder of 3000t+1 divided by 3000 always = 1 , just like the result of 1 (mod 3000) . So, 3000t +1 becomes 1(mod 3000). isn't make sense?
@@ziilam7472 Hi Zii, see a video I just uploaded to explain in more detail what I did in RSA code made easy.
rsa code made confusing
Thanks for your feedback. If there is something you don't understand let me know. If you just want a gentle introduction to RSA have a look at my video How encryption works.
Sorry, I cant speak Australian..:D
+ArMageDDon But can you understand it?
+Randell Heyman I can, no worries. I'm just joking!
Good video, though!