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

[joshiayush]

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

1. What is s and old_s?
2. What is t and old_t?
3. Why to return old_r and old_t when they are never used?
4. 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.
5. 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]

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

[michaelg29]

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]

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]

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]

Let me know if you have any other questions.

Hope this helps,
Michael :)