The name may be wrong, I did not know how to talk about my question.
I'm trying to program with Python3.6 an asymmetric cipher similar to, I suppose, used with RSA-encrypted communication
My logical understanding of this is as follows:
Person1 (p1) picks two prime numbers say 17 and 19
let p = 17 and q = 19
the product of these two numbers will be called n (n = p * q)
n = 323
p1 will then make public n
P1 will then make public another prime called e, e = 7
Person2(p2) wants to send p1 the letter H (72 in Ascii)
To do this p2 does the following ((72 ^ e) % n) and calls this value M
M = 13
p2 sends M to p1
p1 receives M and now needs to decrypt it
p1 can do this by calculating D where (e^D) % ((p-1)*(q-1)) = 1
In this example i know D = 247
With D p1 can calculate p2 message using M^D % n
which successfully gives 72 ('H' in ASCII)
The following rules should apply:
GCD(e,m) = 1
Where m = ((p-1)*(q-1))
otherwise (e^D) % ((p-1)*(q-1)) = 1does not exist.
Now comes the question! :)
Computing D where numbers are not easy to work with.
Now tell me if there is an easier way to calculate D, but this is where I got access to online help.
(the example I used on the Internet used different values to look like this:
p = 47
d = 71
n = p * q = 3337
(p-1) * (q-1) = 3220
e = 79
D. (e ^ D)% ((p-1) * (q-1)) = 1
D = 79 ^ -1% 3220
79 * d = 1 mod 3220
gcd (79,3220) ( ?)
3220 = 40*79 + 60 (79 goes into 3220 40 times with remainder 60)
79 = 1*60 + 19 (The last remainder 60 goes into 79 once with r 19)
60 = 3*19 + 3 (The last remainder 19 goes into 60 three times with r 3)
19 = 6*3 + 1 (The last remainder 3 goes into 19 6 times with r 1)
3 = 3*1 + 0 (The last remainder 1 goes into 3 three times with r 0)
- gcd. , gcd (79,3220) = 1 ( )
,
gcd (one) 19 3220, ...
1 = 19-6*3
= 19-6*(60-3*19)
= 19*19 - 6*60
= 19*(79-60) - 6*60
= 19*79 - 25*60
= 19*79 - 25*(3220-40*79)
= 1019*79 - 25*3220
1019*79 - 25*3220 = 1, mod 3220 , 1019 * 79 = 1 mod 3220
(, 3220, , 3220 = 0 mod 3220).
, d = 1019.