RSA algorithm step by step example
Vložit
- čas přidán 2. 06. 2024
- Go to StudyCoding.org to subscribe to the full list of courses and get source code for projects.
RSA example step by step shows how RSA encryption works mathematically as well as with data encryption tools such as GPG. RSA encryption is used in many public and private key encryption systems. This video will show public and private key examples and then the mechanics of using the RSA algorithm.
Information Security playlist • Information Security 1...
Web Development Security playlist • 00 Web and Database Se...
Index
0:00 What is RSA Encryption?
0:17 Who are Ronald Rivest Adi Shamir and Adelman?
0:35 Public and Private Keys
0:50 GPG encryption example
2:10 Example of factors of numbers
2:45 William Stanley Jevons prime number challenge
3:15 Examples of finding prime factors
4:25 How to make a public RSA key
5:50 Simple example of a public and private key
11:20 How to encrypt a letter with the public key
13:45 Decrypt a letter using the private key
15:50 What are RSA number challenges? - Věda a technologie
Finally. A good explanation on this topic with no skipped steps nor assumption about the viewers' previous knowledge. Amazing professor!
Minus the use of excel to complete mod and the explanation of figuring out mod.
I've watched and looked at so much for someone to finally break it down for a smooth brain like myself. Thanks for actually breaking things down into simple steps, with a simple example.
This guy is super easy to understand and teaches clearly with no skipped steps. Thanks Shad. If there was no covid and you lived close by I'd take you to lunch
Euler Totient ...... why every thing name after Euler in Math arena ..... 😝
@Elias , By the way, if you really have lunch with Professor, make sure you pay cash, no credit card. You know that he keep both the public and private key 😂😂😂
@@gagadaddy8713 stop talking please
@@vengeance3102 WTF you are doing here ....
this is the way to teach !!!!!!!!!! lovely system of visuals ,clear speech ,clear reppresentation etc etc this is paradise after watching loads of other videos that are messy, jumbled up and only fit as a reminder for people that already know the stuff!
This one so far is the best explanation on RSA I have come across. Thank you, Prof!
This video is so underrated, but the best on this topic I've seen. And I've seen A LOT. Thank you so much for this.
Sir, my hat off to you. Nor my book or my professor was able to explain this with such simplicity!
Now that's a good explanation. Unless one is able to encrypt and decrypt (with pen and paper) they will not really understand it. And this example doesn't skip any steps. Best explanation so far!
The best tutorial on this encryption method. Thank you
THANK YOU!!....went to 5 other sources and they were crap! You are a life saver!
Hands down the best video and explanation I’ve seen thus far! Thank you!!!! 🥲
Very informative and useful. Also explained in simple terms. Thank you very much Sir.
I simply loved the explanation, this was great. Your way of explaining the algo was quite smooth and smile. Thank you.
Nice video.
FYI Rivest, Sharmir & Adelman only patented RSA, they were not the first to discover it
Brilliant, so easy to understand. Amazing. Thank you so much!
Awesone explanation, Thanks so much! I'm not sure what I would've done without this tutorial
Great job explaining this!!! I would take a class under this professor anytime.
What a clear presentation of RSA. THANKS so much.
It's very easy to understand, thank you very much for your work!
Very simple to understand! Keep up the great job!
Glad it helped!
thank you! helping me study for my cryptography final
Thank you for the thorough explanation of RSA. Very helpful.
You are such a genius creature on the planet earth Prof Sluiter. Hats off!
great teacher, now I can solve my assignment after watching your video
Thanks for your video Professor Sluiter! I'am a brazilian student, and yours videos helpe me study!!
omg so simple and comprehensive explanation
great job!
Great Work Shad!!
Professional as usual! Thanks!
Your walkthrough in excell was very helpful. Thank you for the effort!
Best explanation on the internet 🎉
Great explanation, thanks a lot!
Brilliant explanation !!
Very good explanation, thanks!
How come these smart people not have millions of views. Thank you so much , very clear an precise explaination
Great stuff Professor!
Step by Step makes sense!!
Thank you sir! Comprehensible lecture!
Amazing! Thank you very much
Illuminating! Thank you
best video till now
Great lecture, thanks!
thanks for teaching, very clear now.
teacher thank's very much for having explained them carefully and well-deatiled, everything was clear ! , break a leg with your videos !
really helpful man thank you
Thank you very much. You help me solve the issue bothering me for a long time
You are most welcome
Amazing... keep it up
Fantastic!
Thank you so much. I'm taking a class for this same topic and you break it down so easily.
THANK YOU SO MUCH YOU ARE A LIFE SAVER
Great explanation
Best teacher 🙌
Thanks very much for posting very helpful , I have a few questions please as there are a few things about the video I do not quite grasp.
Can you please explain the follows: In Column 'A' of the spreadsheet the rule is 'must be a coprime of 6 and 14' when I look up the definition of coprime it says "Co-prime numbers are the numbers whose common factor is only 1"
You rules out the number 2 and 4,
I can see why you rule out 2 because 6 / 2 = 3 and 14 / 2 = 7 (so their only factor is not 1).
However taking the 4, 6 /4 = 1.5 and 14 /4 = 3.5 (in other words not pure integers, and I though the result had to be a pure integer i.e. not remainder)? or do you always remove even numbers before starting the maths?
Can you please explain/clarify the above for me.
One a related note, I did not realise the private / public keys are actually 2 numbers (e.g. two numbers each key) working together. Given a public key do not know of a script (preferably using PoweShell) where I can split the representation of a public key (e.g. byte array) into the two distant values to see that they are ?
Thank you very much again for posting :)
I was stuck on this too and had to do some googling. When he mentioned the rule that the numbers must be a coprime of 6 AND 14, he meant that 2,3,4,5 has to be coprime with BOTH 6 and 14, or they must share a greatest common factor of only 1.
In the case of 4, it will never have a greatest common factor of only 1 because 2 is a factor of 4. It is not asking if 4 is a factor of 6 and 14, which is where I think you were confused about.
In the case of 3, its only factor is 1 and itself, but 3 is a factor of 6, which is ruled out.
5 is the only coprime of both 6 and 14, where they all share a greatest common factor of only 1.
For your second question, it is extremely hard to find the private key based on the public key because you would need to find two large prime numbers just like he mentioned in the beginning of the video. Modern computers today are not capable of finding those primes but maybe someday when we reach quantum computing.
Hope this helped.
Thank you so much, now everythig become clear)
Thanks for thr nice explanation. One of the best and easy to understand
Glad it was helpful!
Great video
A great video.
I love you Professor Sluiter
Nice video. Must e and d be integers? Are there special rules that these two numbers need to follow?
In Excel you said that e < T and e must be coprime with T and N. But you didn't say that in the beginning.
This is for entertainment. Not a msth course.
So I get that we are calling message "B" as 2, but what's the typical way of converting a longer message to a numeric value ? If I wanted the send the message "Hi" how would I get an "m" to feed into the algorithm
Nice video dude
Hi, do the primes you encrypt with have to be much larger than the values you are encrypting? I am trying to encrypt the number 77 with your cipher:
m = 77
77^5 mod14 = 7 (encrypting)
C = 7
7^11 mod14 = 7 (decrypting)
M = 7
hello felix I feel your pain!! I don't know for sure, however this should always work. My theory is that the larger the number you used the more accurate that your calculator or whatever you are using has to be before rounding.
Hello, m can not be bigger than n
I don't get one thing, the decrypt number "d" can be 5, 11 and 17. And 5 is the same as the encryption key.
What stops an attacker from using 5 instead of 11 to decrypt the message, since all of these 3 values can decrypt it?
I have the same question, using the public key(5,14) can also decrypt the letter "D" out to "B", looking forward to an answer too.
confused during the explanation of the decryption where does the 32 mod 14 come from?
So as far as I understand there can be more than 1 private keys d that work the exact same way to decrypt a message.Isn't that a vulnerability?
Really good.
Glad you think so!
Can anyone explain why the decrypt step works or where to find that information? I understand the steps but what rules in modular arithmetic lead to the original data being the result of the equation.
Hi, question. How would you encrypted a message that is a word or even a sentence e.g. "hello"?
Very well explained sir, but if you use the encoding as A=1 , it will not get encrypted since 1^e mod N = 1 ... so i guess just using normal ascii code is a better way of doing things?
it IS encrypted, it just happens to be encrypted to the same value but that is unknown to the public, next letters will be encoded to something different
good explanation, however from your example you could have chosen multiple keys. This means that for each public key there are multiple private keys?
Amazing
Great video - Could some one explain - at 8.08 he mentions you can't use 4 because it is even, leaving us with 5. In my head though the factors of 6 and 14 are 1,2,7,14 and 1,2,3,6. Why not even?
Bit late but the requirement is they need to be Coprime, so they cannot share factors, as 4 has factors 1,2,4 they all share a factor of 2 which is why
@@Jamie-ef9dl Much appreciated.
1. for the part of choosing e and d, we got the 6 is T and the 14 is N. Is this correct?
2. how was 5 coprime with 6 and 14? Can you elaborate this 2, 3, 4 removal process and reasons?
1. N=14 and T=6, that is correct, yes
2. Two numbers are co prime if they have no positive integer that can divide both, except for 1.
- we remove 2 because the factors of 2 are: 1, 2 , the factors of 6 are: 1, 2, 3 and the factors of 14 are: 1, 2, 7, 14. We can see that 2 and 6 are not co prime, since the have two common factors (1 and 2). For the same reason 2 and 14 are not co prime.
- we remove 3 because the factors of 3 are: 1, 3. We can see that 3 and 6 are not co prime, since the have two common factors (1 and 3). Even though 3 is co prime with 14, we need a number that is co prime with both 6 and 14.
- we remove 4 because the factors of 4 are: 1, 2, 4. We can see that 4 and 6 are co prime, since the only common factor is 1 and the same thing goes for 14. But 4 is an even number and if we choose even numbers there is a possibility that (e x d) mod T will not be 1. (the same logic could be applied to 2)
- we are left with 5 and we keep it, because 5 has no common factors with either 6 or 14, except 1, so 5 and 6 are co prime and 5 and 14 are co prime.
I hope this cleared things out for you!
Thanks, i was also this question in my mind. Now it clear to me
This was so easy to understand. Can you do one for elliptical curves primarily for Bitcoin?
Thank you. Not planning on the elliptical curves. However, can you suggest a resource?
yoo does someone know how would u do it with actual text? I've read that you must convert it into numbers and in the video he says that u must use ASCII but how? I would appreciate if u had some material about how to do it without the B=2 thing ( min 11:30 ) .
There are countless text to ascii converters on the internet. But rsa can only encrypt up to the size of the key, so you would have to generate huge primes to encrypt any meaningful message.
(What you can do is encrypt the text with AES and then encrypt the AES key with rsa)
Also, you dont have to use ASCII.
If you really want to encrypt with only rsa then convert every letter of the text to ascii and encrypt each one and maybe store them in an array or something.
I tried some different messages using the keys you used here and found any message that exceeds n(14 in this case) will not decrypt correctly. Is this an error on my part or is this a normal limitation of rsa?
Thats a limitation
but when the message is encrypted using the public key and once we have the encrypted message, one can always reverse engineer to breakdown the message. This method of encryption is only useful when the public key generates different encryption text even after giving it the same input message.
for finding e, whyd you choose 14?? and how is 4 coprime for 6 and 14???
i am still lost on how to find the e and d. at the part where you choose a co-prime, and the entire process for d.
why does "de (modN) =1" - what's the basis of this?
Thanks!
You bet! Are you studying computer science?
encypting o with (5,14) give a, and decrypting a with (11,14) gives a.
how to get o instead of a after decryption?
thanks mn
In the real world, don't you need to make sure that N is large enough to cover the symbol range you wish to encrypt?
E.g. for alpha text, 1.. 26 --> T >= 27. And then you need two primes whose multiple is >= 27, say (3,11), (5,7). Of course it'll be (Yuge prime, Bigly prime), but I'm just asking about the "min" value for p, q.
Would 0.. 25 be allowed? It would handle the number of symbols, but I'm not sure if 0 would break any of the math.
I understand what's happening here, however nobody encrypts anything just to decrypt it again afterwards. You want to send the encrypted message to someone who can decrypt it. And you certainly don't send them your private key. And the receiver has their own private key, which is most probably based on different prime numbers. So, how does that work together with the public key?
Can you explain why decrypting RSA without knowing the privately held prime factor is difficult?
Without that prime factor you can not decrypt. Find that factor is not at all simple, there isn't a simple and efficient way of doing that. While it may not be apparent when working with small numbers it becomes very difficult with numbers that are hundreds digits long. There is a section in the video starting from 15:37 which is related to that. For example a 232 decimal digits number was factored in 2009 and an "only" 8 digits longer (240 digits) were factored in 2019. Adding 8 digits took another 10 years to solve. Now, the most recent RSA numbers have hundreds more digits. Unless something revolutionary happens (e.g. success of quantum computers) I think we are safe.
Does anyone know how to get the d variable as fast as possible in python?
Great content sir,
but let me try coding the letter m by its code ASCII=109
Coding RSA gives 109^5(mod 14) = 9
Decoding RSA gives 9^11(mod 14) = 11
We know that 109 (mod 14) = 11
Decoding gives multiple solutions, so we cannot retreive only original number that is 109
Could you clarify ?
Regards
Hey i might be late but you cant encrypt where n < message
@@gd44481 in my experience, when implementing any hash function, the mod value must be > than the length of the array holding the data.
@@ryklin1 encypting o with (5,14) give a, and decrypting a with (11,14) gives a.
how to get o instead of a after decryption?
very interesting. I wonder how many 'secret' documents from the 1990's are now unsecure?
Probably most of them by now.
Is it a problem the decrypted “2” is not exactly integer?
32 mod 4 is exactly 2. In the video what you see is a an approximation since the calculator can not be that precise.
Another way of calculating that is that 299,593 x 14 = 4,194,302 which is exactly 2 less than the number in question (4,194,304).
Im lost how on how 5 is a number co prime with 6 and 14?
For I = 2 to (amount - 1): if (( amount mod I) = 0) then print I :next i
I presume this video explains RSA simple way but this method crypts letters always into same number, which makes it valuable to letter frequency decryption (extremely easy to solve). How is it sorted?
Can any one please reply me..?
I've got d value as 0 , what to do if we get as such... Please reply faster no time... 😭
bilale anlatır gibi anlatmış. helal olsun!
buy how does an computer decides which two huge prime numbers to chose? How does he know they are prime?
I think there is a mistake in your example. (czcams.com/video/j2NBya6ADSY/video.html) When I send an encrypted message (encrypted with his public key) to a friend, he doesn't need my public key to decrypt it. Because he can only decrypt it with his private key. So there is not any relation between my public key and the message which I send to him. What do you think about it?
I think you are right. If I send a message to you I would need your public key so I can encrypt the message and you will need your own private key to decrypt that.
You’re right, he mixed up examples in his explanation. He was referring to a cryptographic signature. The signature process is a way of proving the message came from you.
To sign a message, you encrypt it with your private key. That encrypted message can be decrypted by your public key, which everyone should have. The point of that encryption isn't to hide the contents, it's to prove that it was written by you. If the message gets decrypted properly with your public key, then it must've come from you because only you (should) have the private key it was encrypted with.
Getting back to this mixup. When you send someone a message, you want to encrypt it with their public key but you ALSO want to sign it with your private key, so your friend knows it really came from you and not an imposter.
That's why your friend would need their private key and your public key. Their private key would be used to decrypt and your public key would be used to authenticate the encrypted signature you included.
@@MichaelApproved for digital signature is not about the encryption of the whole document, is about obtaining a hash (a short string of the document) and that is signature and is obtained with the use of the private key (the sender uses his private key to create the digital signature hash). Then the receiver use sender's public key to verify that the hash is autentic, to confirm the signature was created with the real private key.
How it's not breakable... We can calculate 'd'(private key) with the help of e(public key) as we did in first time to genrate 'd' and totient of n also we can calculate cause we know n is the multiplication of two prime number so first we will break n into those two prime number and will calculate toient of n easily... So now we have everything to calculate d then why it's not breakable?
In order to guess d you would need e and t. T consist of (p-1)*(q-1) and although we now n which is the result of p*q we can not derive the original prime numbers p and q from just knowing n. The RSA Algorithm is easily breakable when you use fairly small numbers p and q, but when you use numbers with over 100 digits, brute forcing would take years to guess the correct factors. The security of RSA lies in the fact, that although you can easily multiple two very large prime numbers, you can't guess those originally used numbers by just looking at the result.
"...
@@entityone0x193 This point raise another question if its so difficult to calculate pq from N then how we generate keys for first time, as to generate public and private at some point we have to do all these calculation at once to generate these keys. How we did at first time??
where the 14 came from ? minute 7.58
N = 2 * 7.. See 6:10
tankes pro
why dislike?