Question about `Programming Challenges - 5 - RSA Encryption (Python)` - Githubissues

michaelg29 / yt-challenges

42 stars 20 forks source link

Question about `Programming Challenges - 5 - RSA Encryption (Python)` #12

Open joshiayush opened 2 years ago

joshiayush commented 2 years ago

@michaelg29 Got a couple of questions. Since last two days I've watched your video several times but couldn't understand the following:

What is s and __old_s__?
What is t and __old_t__?
Why to return old_r and old_t when they are never used?
Does the value of quotient always lies between [0, 1)? Because what is observed is value of r is always greater than value of old_r because r is holding the value of rsa modulus while old_r is holding the value of public key which is smaller than rsa modulus, correct me if I'm wrong.
In Rabin Miller test why to test the primality of the same value 128 times?

Inline with the 4th question it would be really helpful to me if you could just review my code here because in my program the value of r is always greater than the value of __old_r__, but surprisingly my program produces correct results.

Also, could you please consider opening Discussions here because for some reason my comment was not getting posted on youtube that's why I'm opening an issue here.

Please enlighten me.

michaelg29 commented 2 years ago

Sorry I just saw this here. Let me get back to you in a little bit.

michaelg29 commented 2 years ago

I'll start by answering the fifth question. The Rabin Miller test is repeated that number of times because each time, a number is randomly generated. There is no way for certain to know if a number is prime, it would take an astronomical amount of time if we iterated through all prime numbers from 2 to n/2. One iteration of the test returns true or false. False meaning if the test found a number which the potential prime is divisible by, hence the potential prime is not prime. True means that the test did not find a number that could divide the potential prime starting from the random number generated in that iteration. Therefore, it is not a certain result. So, we repeat the test some number of times (128 is usually a good number) to increase the likelihood that the potential prime is actually prime. The more tests you do, the higher chance the number is prime.

michaelg29 commented 2 years ago

To answer the other questions, I will explain how the egcd method works. egcd is the extended Euclidean algorithm, or the extended greatest common denominator algorithm. With RSA, we call it when calculating the modular inverse of e with respect to phiN in order to find the values d and y such that: e d + phiN y = gcd(e, phiN) = 1

Calling egcd(a, b) returns the triple {old_r, old_s, old_t}. Since this is a general algorithm not tailored specifically for RSA, we want to return all three values since they have significance.

old_r is the gcd of a and b. We do not need this value when calculating the modular inverse of e.
old_s is d in the above formula, which we return from modularInv as the decryption key
old_t is y in the above formula, which is also not needed

Check this link for more details.

michaelg29 commented 2 years ago

For your fourth question, your explanation and code are completely correct. If you print out the values of all the variables during each iteration of egcd, you will find that the quotient starts out as zero, because old_r < r as you stated. However, the values swap after the first iteration and you will get a nonzero quotient after that.

michaelg29 commented 2 years ago

Let me know if you have any other questions.

Hope this helps, Michael :)