What to do with the results of extended Euclidean algorithm

Question

I am currently working on an essay about public key encryption, RSA specifically. I understand most of the algorithms involved in generation of public and private keys. But I am struggling to understand what do I do with Bézout's identity to get private key? And also I dont quite understand why Bézout's identity is used at all?

Assume that:

n=55
phi(n)=40    
e = 7

So that e*d mod phi(n) = 1

7*d mod 40 = 1
gcd(40,7) = 1

And so that Bézout's identity looks like this:

3(40)-17(7)=1

Where 40 and 7 are phi(n) and e respectively.

I know from example that d should be 23. So am I right that d = e - 17?

If not how do I get d?

Answer 1

In your example, d = -17 (since Bézout's identity says that there exist x and y such that x*a + y*b = gcd(a,b)).

You are looking for a d such that e*d = 1 mod phi(n), so you can convert this negative d into a positive value that still satisfies the equation by simply adding a multiple of phi(n). In this case we just need to add phi(n) once, which gives your expected value for d:

-17 + phi(n) = -17 + 40 = 23