Solve ax+by=GCD(a,b) for RSA Algorithm Cryptography

In summary, the conversation is about a technique used in the RSA algorithm for finding GCD and obtaining x and y in the process. The person is trying to learn this technique and is asking for any other simple methods to solve the equation. They mention Euclid's Algorithm and provide links to resources they have found but are still looking for clear examples and information.
  • #1
shivajikobardan
675
54
Homework Statement
What's the technique used by this teacher to solve ax+by=GCD(a,b) in RSA Algorithm-Cryptography?
Relevant Equations
RSA Algorithm CT= (PT)^e mod n and PT=(CT)^d mod n


It starts at 6:16
TbO_9XvqKKZSAidxFT5FhXIqcLz02P8DtBbZJSRxixIFEj0ESs.png

It's the part where he's pointing his hand in this picture. I didn't get it although it's pretty mechanical, so I'd like to learn that technique as this is really useful in RSA algorithm(rather than having to memorize some values). I've been searching for a method like that since I saw this problem(been months) but could not find a technique like that. And it was always about just do it rather having any mechanical method like this one. So, I want to learn this.
Or, if you have any other simple methods to solve this equation, please tell me
 
Physics news on Phys.org
  • #2
I believe this is Euclid's Algorithm. It is generally used to find GCD(a,b) but will obtain x and y in the process.
 
  • Like
Likes shivajikobardan
  • #3
pasmith said:
I believe this is Euclid's Algorithm. It is generally used to find GCD(a,b) but will obtain x and y in the process.
I'm trying to figure out a way to replicate his way. I found this
https://math.stackexchange.com/questions/691916/what-is-the-link-between-the-quotient-and-the-bézout-coefficients-in-the-extende

https://crypto.stackexchange.com/qu...lic-exponent-and-the-modulus-fact/54479#54479

But could not get it clearly with a table.

But I'm trying to find some examples around it. PS there are some cases of what happens when the number is greater or lesser than something, I want to know about it. Do share if you've any information regarding this thing.

Thanks for the information!
 
Last edited:

1. What is the purpose of solving ax+by=GCD(a,b) in RSA Algorithm Cryptography?

The equation ax+by=GCD(a,b) is used to find the greatest common divisor (GCD) of two numbers, which is a crucial step in the RSA Algorithm for cryptography. The GCD is used to generate the public and private keys that are used to encrypt and decrypt messages in the RSA algorithm.

2. How does solving ax+by=GCD(a,b) help in ensuring security in RSA Algorithm Cryptography?

By finding the GCD of two numbers, we can determine the values of a and b which are used to generate the public and private keys in the RSA algorithm. These keys are essential in ensuring the security of the encrypted messages, as only the holder of the private key can decrypt the message.

3. Can the GCD of two numbers be easily calculated without solving ax+by=GCD(a,b)?

No, the GCD of two numbers cannot be easily calculated without solving ax+by=GCD(a,b). The RSA algorithm relies on the difficulty of factoring large numbers, and finding the GCD is an essential step in generating the keys that make factoring difficult.

4. Is there a specific method for solving ax+by=GCD(a,b) in RSA Algorithm Cryptography?

Yes, there are several methods for solving ax+by=GCD(a,b) in RSA Algorithm Cryptography, such as the Extended Euclidean algorithm and the Bezout's identity method. These methods are efficient and widely used in cryptography for finding the GCD of two numbers.

5. Can solving ax+by=GCD(a,b) be used in other cryptographic algorithms besides RSA?

Yes, solving ax+by=GCD(a,b) can be used in other cryptographic algorithms besides RSA. The concept of finding the GCD of two numbers is crucial in many encryption and decryption techniques, making it a fundamental concept in cryptography.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
969
  • Programming and Computer Science
Replies
8
Views
971
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Replies
16
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Quantum Physics
Replies
3
Views
906
Replies
9
Views
942
Replies
20
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
12
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Back
Top