Pohlig-Hellman private -key. Rivest-Shamir-Adelman public-key.
For PH one needs:
1. a 'large' prime
p
2. An integer '
e
' (the encryption power) such that gcd(
e
,
) = 1.
3. An integer '
d
' (the decryption power) such that
ed
leaves remainder 1
on division by
(
).
In PH, (
e
,
p
) and (
d
,
p
) constitute the
shared
'private-keys' (anyone who knows one of those keys may quickly calculate the other one, using the extended Euclidean algorithm).
Brief comments.
For a given '
p
' and
'e
' there is ONLY ONE such '
d
' between 1 and (
).
That '
d
' is quickly found by using the so-called extended Euclidean algorithm.
Requirement #3 is dictated by the mathematics of Fermat's so-called
little
theorem (that's what I mean by hand waving...).
Without requirement #2, #3 could not even come into play...
For RSA one needs:
1. Two 'large' primes
p
and
q
(in the
real world
, 'large' is not good enough, as I will demonstrate in a later section), and then '
n
' - Alice's public modulus - is
defined
by
n = pq
.
2. An integer '
e
' (the
e
ncryption power) such that gcd(
e
,
) = 1.
That '
' is '
', the so called (Euler)
phi-value of n
, plays a
fundamental
role...
3. An integer '
d
' (the
d
ecryption power) such that
ed
leaves remainder 1 on division by
.
In RSA, (
e
,
n
) is the
public
-key, while (
d
,
n
) is the
private
-key (and here the
absolute crux
of the matter, the entire rock on which the whole system stands, is that someone who knows the public-key may NOT quickly quickly calculate the private one,
providing
the constructor of the
public modulus
, '
n
', has done so with
due
caution
(e.g., it is NOT enough merely to choose
p
and
q
to be 'large', as I will later demonstrate)
Brief comments.
For a given '
p
', '
q
', and
'e
' there is ONLY ONE such '
d
' between 1 and
.
That '
d
' is quickly found -
knowing
p
and
q
(that '
knowing
' is a
fundamental
point, and is the
entire basis
for the security of the public-key method...) - by using the so-called extended Euclidean algorithm.
Requirement #3 is dictated by the mathematics of 2-prime case of Euler's generalization of Fermat's
little
theorem (more hand waving...).
Again, without requirement #2, #3 could not even come into play...