Public-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 164

Using a modulus,

n = pq = 8179 · 9547 = 78084913 ,

with public key e =7 , and private key d = 22304911 , Alice then enciphers k as

k = E e ( k )= k e = 3476512 7

≡

62221916 (mod 78084913) ,

and sends the pair ( k ,c )=( k e ,c ) to Bob.Bob receives the pair and makes the
following calculations. 4.1
He computes

D d ( k )=( k ) d 62221916 22304911

≡ ≡ 3476512 ≡ k (mod n ) .

Bob then converts this back to its original format via (4.1) , and is able to easily
deduce the deciphering key
k − 1 = 1234567
6712543

,

which he applies to c to get

D k − 1 ( E k ( m )) = D k − 1 (0 , 21 , 18 , 11 , 4 , 19 , 17) = (19 , 17 , 0 , 21 , 4 , 11 , 18) = travels .

Now we are ready to look at the various PKCs. The ideas behind the most
famous PKC, namely, RSA, about which we will learn the details in the next
section, is based upon the simple mathematical idea of exponentiation and re-
lated matters. The first of the related matters is a notion that we need to set up
the first exponentiation cipher. The security of many cryptosystems depends
upon the di8culty of solving certain problems such as the following.
If we are dealing with real numbers then finding e from α e is called the
logarithm function. In F p (or more generally in any finite group) this is called

the discrete logarithm problem (DLP). Thus, we present the problem formally
as follows.

Discrete Log Problem (DLP):

F p , and an element c ∈ F p , find the unique Given a prime p , a generator m of

integer e with 0 ≤ e ≤ p − 2 such that

m e (mod p ) .

c ≡ (4.2)

4.1 What Bob does is to employ Euler's theorem (see Theorem A.14 on page 479). This
motivates what we will study in the next section.