12.6 Early Public-Key Systems
213
has to ensure that she is the genuine sender of an email with text ˆ
m. She first calculates
a hash value ˆ
c of ˆ
m using one of the hashes discussed before. Then she “signs” this
hash ˆ
c with her private key d by calculating s = ˆ
c
d
(mod n) and transmits s along
with the plaintext message ˆ
m to Bob. We assume that Bob receives this message
as ˆ
m
. It was not encrypted and he does not know whether someone tampered with
the message. To find out whether the received message ˆ
m
is really the one that
Alice had sent, he uses Alice’s public key (n, e) to unpack the signed hash s to
find s
e
(mod n) = ˆ
c
ed
(mod n) = ˆ
c, the hash of the message ˆ
m. He then verifies that
the received message ˆ
m
is genuine by calculating its hash ˆ
c
. If that equals ˆ
c, the
messages are the same. Note that here Alice uses her secret private key d to sign the
hash of the message and Bob uses the public key (n, e) to verify that the signature
can only come from Alice.
But how do we find the keys, or the numbers n, e, and d? Here we only sketch the
construction, which is based on Euler’s totient theorem. It states that if two numbers
m and n have no common factor except 1, then m
ϕ(n)
= 1(mod n), where ϕ(n) is
the totient function of n. It is equal to the number of integers that have no common
factors with n, which is called they are relatively prime or coprime with respect to
n. If we now choose two large prime numbers p and q and define n = pq then the
totient of n can be calculated as ϕ(n) = ( p − 1)(q − 1). First taking the kth power
and then taking the modulus on both sides of Euler’s theorem leads to
m
kϕ(n)+1
(mod n) = m
for an integer k,
(12.28)
which gives us the desired form m
ed , provided we choose a number e, which must be
coprime with ϕ(n) and then find a value of k such that d = (kϕ(n) + 1)/e is integer.
Either, we search for d that fulfills ed(mod ϕ(n)) = 1 or we rewrite this equation as
ed − kϕ(n) = 1 = gcd(e, ϕ(n))
(12.29)
where the greatest common denominator of e and ϕ(n) is unity, or gcd(e, ϕ(n)) = 1,
because e and ϕ(n) are coprime. This expression has the form of Bézout’s equation, which can be easily solved using the gcd() function in MATLAB, which
implements Euclid’s extended algorithm.
The following short MATLAB script visualizes this process.
p=5; q=11; e=3;
n=p*q; phin=(p-1)*(q-1);
[gcdval,d,kk]=gcd(e,phin);
if gcdval ˜= 1 disp(’Error: e and phin not coprime’); end
d=powermod(d,1,phin)
message=6
ciphertext=powermod(message,e,n)
decoded=powermod(ciphertext,d,n)
213
has to ensure that she is the genuine sender of an email with text ˆ
m. She first calculates
a hash value ˆ
c of ˆ
m using one of the hashes discussed before. Then she “signs” this
hash ˆ
c with her private key d by calculating s = ˆ
c
d
(mod n) and transmits s along
with the plaintext message ˆ
m to Bob. We assume that Bob receives this message
as ˆ
m
. It was not encrypted and he does not know whether someone tampered with
the message. To find out whether the received message ˆ
m
is really the one that
Alice had sent, he uses Alice’s public key (n, e) to unpack the signed hash s to
find s
e
(mod n) = ˆ
c
ed
(mod n) = ˆ
c, the hash of the message ˆ
m. He then verifies that
the received message ˆ
m
is genuine by calculating its hash ˆ
c
. If that equals ˆ
c, the
messages are the same. Note that here Alice uses her secret private key d to sign the
hash of the message and Bob uses the public key (n, e) to verify that the signature
can only come from Alice.
But how do we find the keys, or the numbers n, e, and d? Here we only sketch the
construction, which is based on Euler’s totient theorem. It states that if two numbers
m and n have no common factor except 1, then m
ϕ(n)
= 1(mod n), where ϕ(n) is
the totient function of n. It is equal to the number of integers that have no common
factors with n, which is called they are relatively prime or coprime with respect to
n. If we now choose two large prime numbers p and q and define n = pq then the
totient of n can be calculated as ϕ(n) = ( p − 1)(q − 1). First taking the kth power
and then taking the modulus on both sides of Euler’s theorem leads to
m
kϕ(n)+1
(mod n) = m
for an integer k,
(12.28)
which gives us the desired form m
ed , provided we choose a number e, which must be
coprime with ϕ(n) and then find a value of k such that d = (kϕ(n) + 1)/e is integer.
Either, we search for d that fulfills ed(mod ϕ(n)) = 1 or we rewrite this equation as
ed − kϕ(n) = 1 = gcd(e, ϕ(n))
(12.29)
where the greatest common denominator of e and ϕ(n) is unity, or gcd(e, ϕ(n)) = 1,
because e and ϕ(n) are coprime. This expression has the form of Bézout’s equation, which can be easily solved using the gcd() function in MATLAB, which
implements Euclid’s extended algorithm.
The following short MATLAB script visualizes this process.
p=5; q=11; e=3;
n=p*q; phin=(p-1)*(q-1);
[gcdval,d,kk]=gcd(e,phin);
if gcdval ˜= 1 disp(’Error: e and phin not coprime’); end
d=powermod(d,1,phin)
message=6
ciphertext=powermod(message,e,n)
decoded=powermod(ciphertext,d,n)