I am trying to create a program for the RSA algorithm. I have managed to get the public keys, but I hit a brick wall trying to figure out how to generate the secret key. I have tried, but the output is either incorrect or doesn't output at all. my program for the secret key is
where d is the secret key, e is the relatively prime number to phi, phi being (p-1)*(q-1), where p and q are the two primes.
When I insert this into the rest of my algorithm and run the program, the result is this:
First prime: 5
Second Prime: 7
the public key is [17,35]
The secret key is 1
phi is 24.
I used 5 and 7 just for simplicity. here the public key is in the form [e,m], where m is p*q, e the same as above, and the secret key is d. One can see that d doesn't solve the equation e*x-phi*y=1, where y is an arbitrary number assigned "i" in the above code.
which is not an integer solution.
You need to find the value of d such that d*e (mod 24) == 1
for ( ; ((d*e)%24) != 1; d++)
This will start with d equal to one, and will begin by calculating:
1*17 mod 24, which is 17, which is not equal to one, so the loop continues...
2*17 mod 24, which is 10, which is not equal to one, so the loop continues...
17*17 mod 24, which is 1, which is equal to one, so the loop stops with d set to 17.