Follow these simple steps to get the encryption and decryption keys:
P
and Q
.
E
such that it is less than
P
times Q
(ie PQ
),
and that it shares no factors with (P-1)(Q-1)
.E
must be odd (as (P-1)(Q-1)
will be even) but does not necessarily have to be a prime number.
D
, so that
DE-1
is divisible by (P-1)(Q-1)
.D
is the
multiplicative inverse of E
,
so can be written:
DE mod ((P-1)(Q-1)) = 1
X
into Y
:Y=(X^E) mod (PQ)
X
and Y
will have values
0..PQ-1
Y
back to X
:X=(Y^D) mod (PQ)
PQ
and E
.
The private key is simply D
.P
and Q
as they
make it all too easy to work out the private key.
It is very difficult to factor PQ
to get the two primes,
so much so, that it is often reported that such a computation would
take billions of years using todays fastest machines.
Of course, that is until someone finds out an algorithm to do it,
in a reasonable amount of time. And there are a few methods that
are getting close, such as
MPQS (multiple polynomial quadratic sieve),
ECM (elliptic curve method),
and NFS (number field sieve).
Close enough that 25% of the brute force time can be reportedly circumvented.
P = 17 Q = 19 PQ = 323 (P-1)(Q-1) = 288 Then choosing: E = 43 we get: D = 67 as 43*67 = 2881 and 2881 mod 288 = 1. To encrypt the "message" 99, it is calculated as: 99^43 mod 323 = 64910262836840243299385600408064315507269747285819167695867408486826194559651331974299 mod 323 = 44 To decrypt this "44", the calculation is: 44^67 mod 323 = 129219877375000481226629921485716742694854635591566961372271643321956224151273763684202739354062946891269668864 mod 323 = 99 |
99^43 mod 323
,
some code to do this could be:
N=1; repeat 43 times: N=(N*99) mod 323 |
0..PQ-1
becomes massive!
This encryption method also allows a message encrypted using the
private key to be decrypted with the public key.
Which means it can be used to allow secure communication between
one place and another, by each place having its own key pairs,
and each message is encrypted using its own private key, THEN
encrypted with the others public key. At the receiving end, the
message is decrypted with the private key, THEN decrypted with
the public key of the sender.
It ensures the receiver knows the sender MUST have been the sender,
and knows nobody else could decrypt the message without the private key
of the receiver.
Although in practise you only need to show the checksum of use of
your private key on the message (encrypted or not) to prove it was
really you who sent the message.
This is referred to as a "PGP signed" message.
Now all you have to do is trust the sender and/or the receiver to
not give away their private key, and to trust the public key you are
given IS definately the key to whom you think it belongs!
One way to ensure this is to use a simple one-way hashing algorithm (eg MD5),
so that the massive key is reduced to (say) 32 or 128 bits.
Then when the key is received, use another method of communication
to the key owner (eg the phone, or meet in secret cafe) to confirm
the hash value matches.
As the hash is one-way, there is no way to reverse the hashed value
to get the key, and you can trust the key was sent correctly, and
nobody altered it in transit.
There are plenty of books on all of this and more, such as digital signatures, shared secrets, computer security, firewalls, etc. Visit your local bookstore or any number of online retailers.