UNIT- III:

Asymmetric Encryption
Mathematics of Asymmetric Key Cryptography, Asymmetric Key Cryptography

Ch-9 – Mathematics of Asymmetric-Key Cryptography

9.1 Primes

Definition

The positive integers can be divided into three groups

1. The number 1
2. Primes
3. Composites
As shown in figure 9.1.

Figure 9.1 Three groups of positive integers

Example:
What is the smallest prime?

The smallest prime is 2, which is divisible by 2 (itself) and 1.

Example:
List the primes smaller than 10.

There are four primes less than 10: 2, 3, 5, and 7. It is interesting to note that the percentage of
primes in the range 1 to 10 is 40%. The percentage decreases as the range increases.

Coprime or relatively prime

Two positive integers, a and b, are relatively prime or coprime, if gcd (a, b) = 1.

9.2 Cardinality of Primes

Infinite number of primes the number of primes is infinite.

Number of primes
We can use infinite Number of Primes.

Number of Primes
π(n) is the number of primes less than or equal to n. π is not similar to mathematics π.

1/40
The primes under 25 are 2, 3, 5, 7, 11, 13, 17, 19 and 23 so π(3) = 2, π(10) = 4 and π(25) = 9.

Guass discovered the upper limit; Lagrange discovered the lower limit.

9.3 Euler’s Phi-Function

Euler’s phi-function, (n), which is sometimes called the Euler’s totient function, plays a very
important role in cryptography. The function finds the number of integers that are both smaller
than n and relatively prime to n.
The following helps to find (n)
1. (1) = 0
2. (p) = p - 1 if p is a prime
3. (m x n) = (m) x (n) if m and n are relatively prime.
4. (pe) = pe - pe-1 if p is a prime.

The difficulty of finding (n) depends on the difficulty of finding the factorization of n.

Example:
What is the value of (13)?

Because 13 is a prime, (13) = (13-1) = 12

Example:
What is the value of (10)?

We can use the third rule: (10) = (2) x (5) = 1 x 4 = 4, 2 and 5 are primes.

Example:
What is the value of (240)?

We can write 240 = 24 x 31 x 51. Then

(240) = (24 - 23) x (31 - 30) x (51 - 50) = 64

Example:
Can we say that (49) = (7) x (7) = 6 x 6 = 36?

No. the third rule applies when m and n are relatively prime. Here 49 = 72. We need to use the fourth
rule: (49) = 72 – 71 = 42.

Example:
What is the number of elements in Z14*?

The answer is (14) = (7) x (2) = 6 x 1 = 6. The members are 1, 3, 5, 9, 11, and 13.

The interesting point: if n > 2, the value of (n) is even.

2/40
Exercise: Find the value of (29), (32), (80), (100), (101).

9.4 Fermat’s little theorem

Fermat’s little theorem plays a very important role in number theory and cryptography. We
introduce two versions of the theorem here.

First version The first version says that if p is a prime and a is an integer such that p does
not divide a, then ap-1 ≡ 1 mod p.

Second version The second version removes the condition on a. it says that if p is prime and a
is an integer, then ap ≡ a mod p.

Example:
Find the result of 610 mod 11.

We have 610 mod 11 = 1. This is the first version of Fermat’s little theorem where
p = 11.

611 mod 11 = 1 mod 11 = 1

Example:
Find the result of 312 mod 11.

Here the exponent (12) and the modulus (11) are not the same. With substitution this can be solved
using Fermat’s little theorem.

312 mod 11 = (311 x 3) mod 11 = (311 mod 11) (3 mod 11) = (3 x 3) mod 11 = 9

Exercise:
Find the results of the following, using Fermat’s little theorem.
a. 515 mod 13 b. 1518 mod 17 c. 45617 mod 17 d. 145102 mod 101

Multiplicative Inverses
A very interesting application of Fermat’s theorem is in finding some multiplicative inverses quickly
if the modulus is a prime.

If p is a prime and a is an integer such that p does not divide a (p ∤ a) then a-1 mod p = ap-2 mod p.

Take Fermat’s little theorem first version and divide with a on both sides then,

(𝑎𝑝−1 𝑚𝑜𝑑 𝑝) 1 𝑚𝑜𝑑 𝑝

=
𝑎 𝑎

⇒ 𝑎𝑝−2 𝑚𝑜𝑑 𝑝 = 𝑎−1 𝑚𝑜𝑑 𝑝

This application eliminates the use of extended Euclidian algorithm for finding some multiplicative
inverses.

Example:
The answers to multiplicative inverses modulo a prime can be found without using the extended
Euclidean algorithm:

3/40
Example:
How to calculate multiplicative inverse of 5 modulo 23 that is 5-1 mod 23?

Solution:
5-1 mod 23 = 523-2 mod 23 (Ref: a-1 mod p= ap-2 mod p) 523-2 mod 23 = 521 mod 23
Calculate following to solve 521 mod 23:
51 mod 23 = 5
52 mod 23 = 25 mod 23=2
54 mod 23 = (52)2 mod 23= (2)2 mod 23 = 4
58 mod 23 = (54)2 mod 23 (4)2 mod 23 =16
516 mod 23 = (58)2 mod 23 (16)2 mod23 = 256 mod 23=3
521 mod 23 = (516 x 54 x 51) mod 23 = (3x4x5) mod 23 = 60 mod 23 = 14 mod 23.
Finally 5-1 mod 23 = 521 mod 23 = 14 mod 23

Exercise:
Find the results of the following, using Euler’s theorem:
a. 5-1 mod 13 b. 15-1 mod 17 c. 27-1 mod 41 d. 70-1 mod 101
(Note that all moduli are primes)

9.5 Euler’s theorem

First version if a and n are coprime, then a (n) ≡ 1 mod n

Second version if n = p x q, a < n, and k an integer, then ak x (n)+1 ≡ a mod n

The second version of Euler’s theorem is used in the RSA cryptosystem in chapter 10.

Exponentiation Euler’s theorem sometimes is helpful for quickly finding a solution to some
exponentiations. The following examples show the idea.

Example:
Find the result of 624 mod 35.

Solution:
We have 624 mod 35 = 6 (35) mod 35 = 1

Example:
Find the result of 2062 mod 77.

Solution:

4/40
If we let k=1 on the second version, we have 2062 mod 77 = [(20 mod 77) (20 (77)+1 mod 77)] mod
77 = (20)(20) mod 77 = 15.

Multiplicative Inverses
Fermat’s little theorem can be used to find multiplicative inverses modulo a prime. Euler’s theorem
can be used to find multiplicative inverses modulo a composite.

If n and a are coprime, take Euler’s first version

a (n) ≡ 1 mod n

⇒ a (n) mod n = 1 mod n

divide with a on both sides
⇒ (a (n) mod n) / a = (1 mod n) / a

⇒ (a (n)-1 mod n) = (a-1 mod n)

Example:
The answers to multiplicative inverses modulo a composite can be found without using the extended
Euclidean algorithm if we know the factorization of the composite:

a. 8-1 mod 77 = 8 (77)-1 mod 77 = 859 mod 77 = 29 mod 77

b. 7-1 mod 15 = 7 (15)-1 mod 15 = 77 mod 15 = 13 mod 15
c. 60-1 mod 187 = 60 (187)-1 mod 187 = 60159 mod 187 = 53 mod 187
d. 71-1 mod 100 = 71 (100)-1 mod 100 = 7139 mod 100 = 31 mod 100

Exercise:
a. 12-1 mod 77 b. 16-1 mod 323 c. 20-1 mod 403 d. 44-1 mod 667

9.6 Factorization

Factorization plays a very important role in the security of several public-key cryptosystems.

9.6.1 Fundamental theorem of arithmetic

According to fundamental theorem of arithmetic, any positive integer greater than one can be written
uniquely in the following prime factorization form where p1, p2, …, pk are primes and e1, e2, …, ek
are positive integers.

n = p1e1 x p2e2 x … x pkek

Example: 24 = 2 x 2 x 2 x 3

9.6.2 Factorization Methods

In this section, we give a few simple algorithms that factor a composite number. The purpose is to
make clear that the process of factorization is time consuming.

[Link] Trail Division Method

By far, the simplest and least efficient algorithm is the trail division factorization method. We simply
try all the positive integers, starting with 2, to find one that divides n. we know that if n is composite,
then it will have a prime p <= √𝒏. Algorithm below shows the pseudocode for this method. The
algorithm has tow loops, one outer and one inner. The outer loop finds unique factors; the inner

5/40
loops finds duplicates of a factor. For example, 24 = 2 3 x 3. The outer loop finds the factors 2 and
3. The inner loop finds that 2 is a multiple factor.

Example:
Use the trail division algorithm to find the factors of 1233.

We run a program based on the algorithm and get the following result.

1233 = 32 x 137

Example:
Use the trail division algorithm to find the factors of 1523357784.

We run a program based on the algorithm and get the following result.

1523357784 = 23 x 32 x 13 x 37 x 43987

[Link] Fermat method

The Fermat factorization method (below algorithm) divides a number n into two positive integers a
and b (not necessarily a prime) so that n = a x b.

6/40
The Fermat method is based on the fact that if we can find x and y such that n = x 2 – y2, then we
have

N = x2 – y2 = a x b with a = (x + y) and b = (x – y)

[Link] Pollard p-1 method

The below algorithm shows the pseudocode for Pollard p-1 factorization method.

[Link] Pollard rho method

The below algorithm shows the pseudocode for Pollard rho factorization method.

7/40
9.7 Chinese remainder theorem
The Chinese remainder theorem (CRT) is used to solve a set of congruent equations with one variable
but different moduli, which are relatively prime, as shown below:

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
…
…
x ≡ ak (mod mk)

The Chinese remainder theorem states that the above equations have a unique solution if the moduli
are relatively prime.

Example:
The following is an example of a set of equations with different moduli:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
…
…
x ≡ 2 (mod 7)

the solution to this set of equations is given in the next example; for the movement, note that the
answer to this set of equations is x = 23. This value satisfies all equations: 23 ≡ 2 (mod 3), 23 ≡ 3
(mod 5), and 23 ≡ 2 (mod 7).

Solution steps:

The solution to the set of equations follow these steps:

1. Find M = m1 * m2 * … * mk. This is common modulus.

2. Find M1 = M/m1, M2 = M/m2, … Mk = M/mk.
3. Find the multiplicative inverse of M1, M2, … Mk using the corresponding moduli (m1, m2, …
mk).
Call the inverses M1-1, -1 M2-1, … Mk-1.
4. The solution to the simultaneous equation is

x = [ (a1 * M1 * M1-1) + (a2 * M2 * M2-1) + … + (ak * Mk * Mk-1) ] mod M

Note that the set of equations can have a solution even if the moduli are not relatively prime
but meet other conditions. However, in cryptography, we are only interested in solving equations
with coprime moduli.

Example:
Find the solution to the simultaneous equations:

x ≡ 3 (mod 7)
x ≡ 3 (mod 13)
…
…
x ≡ 0 (mod 12)

8/40
Solution:

Example:
Find an integer that has a remainder of 3 when divided by 7 and 13, but is divisible by 12.

Solution:
This is a CRT problem. We can form three equations and solve then to find the value of x.

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
…
…
x ≡ 2 (mod 7)

9/40
Applications:
1. The Chinese remainder theorem has several applications in cryptography. One is to solve
quadratic congruence as discussed in the next section.
2. The other is to represent a very large integer in terms of a list of small integers.

Exercise:
Find the value of x for the following sets of congruence using the Chinese remainder theorem.
a. x ≡ 2 mod 7, and x ≡ 3 mod 9
b. x ≡ 4 mod 5, and x ≡ 10 mod 11
c. x ≡ 7 mod 13, and x ≡ 11 mod 12

9.8 Primitive roots of a group

Definition
In the group G = <Zn*, x>, when the order of an element is the same as (n), the element is called
the primitive root of the group.

10/40
Example:
Find primitive roots of the group G = <Z5*, x>

In this group, (5) = 4

The following table shows all the powers of modulo 5 for all positive a<5. The length of the
sequence for each base value is indicated by shading.

a2 mod a3 mod a4 mod

a a mod 5
5 5 5
1 1 1 1 1
2 2 4 3 1
3 3 4 2 1
4 4 1 4 1

The above table shows that only two elements, 3 and 5, have the order (5) = 4. Therefore, this
group has only two primitive roots: 3 and 5.

Note:
It has been proved that the group G = <Zn*, x> has primitive roots only if n is 2, 4, pt, or 2pt, in
which p is an odd prime (not 2) and t is an integer.

Example:
Find primitive roots of the group G = <Z7*, x>

In this group, (7) = 6

a a mod 7 a2 mod 7 a3 mod 7 a4 mod 7 a5 mod 7 a6 mod 7

1 1 1 1 1 1 1
2 2 4 1 2 4 1
3 3 2 6 4 5 1
4 4 2 1 4 2 1
5 5 4 6 2 3 1
6 6 1 6 1 6 1

From the above table primitive roots are: 3 and 5 because they have the order (7) = 6.

Example:
For which value of n, does the group G = <Zn*, x> have primitive roots: 17, 20, 38, and 50?

a. G = <Z17*, x> has primitive roots, because 17 is a prime (pt where t is 1)

b. G = <Z20*, x> has no primitive roots.
c. G = <Z38*, x> has primitive roots, because 38 = 2 x 19 and 19 is a prime.
d. G = <Z50*, x> has primitive roots, because 50 = 2 x 52 and 5 is a prime.

Note:
If a group has a primitive root, then it normally has several of them. The number of primitive roots
can be calculated as ( (n)). For example, the number of primitive roots of G = <Z17*, x> is ( (17))
= (16) = 8. Note that we should first check to see if the group has any primitive root, before we find
the number of roots.

11/40
9.9 Discrete logarithms
Discrete logarithms are fundamental to a number of public-key algorithms, including Diffie–Hellman
key exchange and the digital signature algorithm (DSA). This section provides a brief overview of
discrete logarithms.

The Powers of an integer, Modulo n

Recall from Euler’s theorem that, for every a and n that are relatively prime,

a (n) ≡ 1 (mod n)

where (n), Euler’s totient function, is the number of positive integers less than n and relatively
prime to n. Now consider the more general expression:

am ≡ 1 (mod n) (1)

If a and n are relatively prime, then there is at least one integer m that satisfies Equation (1), namely,
m = (n). The least positive exponent m for which Equation (1) holds is referred to in several ways:

• The order of a (mod n)

• The exponent to which a belongs (mod n)
• The length of the period generated by a

To see this last point, consider the powers of 7, modulo 19:

71 ≡ 7 mod (19)
72 = 49 ≡ 11 mod (19)
73 = 343 ≡ 1 mod (19)
74 = 2401 ≡ 7 mod (19)
75 = 16807 ≡ 11 mod (19)

There is no point in continuing because the sequence is repeating. This can be proven by noting
that the sequence is periodic, and the length of the period is the smallest positive exponent m such
that 7m ≡ 1 mod 19.

Table below shows all the powers of a, modulo 19 for all positive a < 19. The length of the sequence
for each base value is indicated by shading. Note the following point:

Some of the sequences are of length 18. In this case, it is said that the base integer a generates (via
powers) the set of nonzero integers modulo 19. Each such integer is called a primitive root of the
modulus 19.

More generally, we can say that the highest possible exponent to which a number can belong (mod
n) is (n). If a number is of this order, it is referred to as a primitive root of n. The importance of
this notion is that if a is a primitive root of n, then its powers

a, a2, … a (n)

are distinct (mod n) and are all relatively prime to n. In particular, for a prime number p, if a is a
primitive root of p, then

a, a2, … ap-1

12/40
are distinct (mod p). For the prime number 19, its primitive roots are 2, 3, 10, 13, 14, and 15.

Table: Powers of Integers, Modulo 19

Logarithms for Modular Arithmetic

With ordinary positive real numbers, the logarithm function is the inverse of exponentiation. An
analogous function exists for modular arithmetic

Let us briefly review the properties of ordinary logarithms. The logarithm of a number is defined to
be the power to which some positive base (except 1) must be raised in order to equal the number.
That is, for base x and for a value y,

The properties of logarithms include

Consider a primitive root a for some prime number p (the argument can be developed for nonprimes
as well). Then we know that the powers of a from 1 through (p - 1) produce each integer from 1
through (p - 1) exactly once. We also know that any integer b satisfies

Discrete Logarithms
It follows that for any integer ‘b’ and a primitive root ‘a’ of prime number ‘p’, we can find a unique
exponent ‘i’, such that
b ≡ ai mod p where 0 <= i <= (p-1)
this exponent i is referred to as the discrete logarithm of the number ‘b’ for the base a mod p. we
denote this value as dlog a, p(b).

13/40
 Ch-10 – Asymmetric-Key Cryptography

1. Introduction to asymmetric-key cryptography

Public-key algorithms rely on one key for encryption and a different but related key for decryption.
These algorithms have the following important characteristic:

• It is computationally infeasible to determine the decryption key given only knowledge of the
cryptographic algorithm and the encryption key.
In addition, some algorithms, such as RSA, also exhibit the following characteristic:

• Either of the two related keys can be used for encryption, with the other used for decryption.
A public-key encryption scheme has six ingredients

• Plaintext: This is the readable message or data that is fed into the algorithm as input.
• Encryption algorithm: The encryption algorithm performs various transformations on the
plaintext.
• Public and Private Key: This is a pair of keys that have been selected so that if one is used for
encryption, the other is used for decryption. The exact transformations performed by the
encryption algorithm depend on the public or private key that is provided as input.
• Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and
the key. For a given message, two different keys will produce two different cipher texts.
• Decryption algorithm: This algorithm accepts the ciphertext and the matching key and
produces the original plaintext.

Figure 10.1: Public Key Cryptography (Secrecy)

14/40
The essential steps are the following:

1. Each user generates a pair of keys to be used for the encryption and decryption of messages.
2. Each user places one of the two keys in a public register or other accessible file. This is the
public key. The companion key is kept private. As Figure 10.1 suggests, each user maintains
a collection of public keys obtained from others.
3. If Bob wishes to send a confidential message to Alice, Bob encrypts the message using Alice’s
public key.
4. When Alice receives the message, she decrypts it using her private key. No other recipient can
decrypt the message because only Alice knows Alice’s private key.

With this approach, all participants have access to public keys, and private keys are
generated locally by each participant and therefore need never be distributed. As long as system
controls its private key, its incoming communication is secure. At any time, a system can change
its private key and publish the companion public key to replace its old public key.
Let us take a closer look at the essential elements of a public-key encryption scheme, using
Figure 10.2. There is some source A that produces a message in plaintext X. The message is intended
for destination B. B generates a related pair of keys: a public key, KUb, and a private key, KRb. KRb
is known only to B, whereas KUb is publicly available and therefore accessible by A.
With message X and the encryption key KUb as input, A forms the ciphertext Y.

Y = EKUb(X)
The intended receiver, in possession of the matching private key, is able to invert the
transformation:

X = DKRb(Y)

An opponent, observing Y having access to KUb and does have knowledge of encryption (E)
and decryption (D) algorithms. But he does not have access to KRb. so he can’t generate the
original message.
So, in this case secrecy is there but authentication fails. Anybody can send message using
B’s public key but receiver confuses that which one is the original A’s message.

Figure 10.2: Public Key Cryptosystem: Secrecy

15/40
 Figure 10.3: Public Key Cryptosystem: Authentication

Another scheme illustrated in Figure 10.3 show the use of public key encryption to provide
authentication.
Y = EKRa(X)
X = DKUa(Y)

In this case, A prepares a message to B and encrypts it using A’s private key before
transmitting it. B can decrypt the message using A’s public key. Because the message was encrypted
using A’s private key, only A could have prepared the message.
It is impossible to alter the message without access to A’s private key, so the message is
authenticated both in terms of source and in terms of data integrity.
In this scheme authentication is there but no secrecy. Anybody can decrypt the message and
obtain the plaintext using A’s public key.

Figure 10.4: Public key cryptosystem: Secrecy and Authentication

16/40
 It is, however, possible to provide both the authentication function and confidentiality by a
double use of the public-key scheme: (Figure 10.4)
Z = EKUb[EKRa(X)]
X = DKUa[DKRb(Z)]

In this case, we begin as before by encryption a message, using the sender’s private key. Next, we
encrypt again, using the receiver’s public key. The final ciphertext can be decrypted only by the
intended receiver, who alone has the matching private key. Thus, confidentiality is provided. The
disadvantage of this approach is that the public-key algorithm, which is complex, must be exercised
four times rather than two in each communication.

Difference between symmetric-key and asymmetric-key cryptosystems

• The conceptual difference between the two systems are based on how these systems keep a
secret. In symmetric-key cryptography, the secret must be shared between two persons. In
asymmetric-key cryptography, the secret is personal (unshared); each person creates and
keeps his or her own secret.
• In a community of n people, n(n-1)/2 shared secrets are needed for symmetric-key
cryptography; only n personal secrets are needed in asymmetric-key cryptography. For a
community with a population of 1 million, symmetric-key cryptography would require half a
billion shared secrets; asymmetric-key cryptography would require 1 million personal secrets.
• Symmetric-key cryptography is based on substitution and permutation of symbols
(characters or bits), asymmetric-key cryptography is based on applying mathematical
functions to numbers.
• In symmetric key cryptography, the plaintext and ciphertext are thought of as a combination
of symbols. Encryption and decryption permute these symbols or substitute a symbol for
another. In asymmetric-key cryptography, the plaintext and ciphertext are numbers;
encryption and decryption are mathematical functions that are applied to numbers to create
other numbers.

Symmetric-key cryptography is based on shared secrecy;

Asymmetric-key cryptography is based on personal secrecy.

In symmetric-key cryptography, symbols are permuted or substituted;

In asymmetric-key cryptography, numbers are manipulated.

Need for both

There is a very important fact that is sometimes misunderstood: The advent of asymmetric-key
(public-key) cryptography does not eliminate the need for symmetric-key cryptography. The reason
is that asymmetric-key cryptography, which uses mathematical functions for encryption and
decryption, is much slower than symmetric-key cryptography. For encipherment of large messages,
symmetric-key cryptography is still needed. On the other hand, the speed of symmetric-key
cryptography does not eliminate the need for asymmetric-key cryptography. Asymmetric-key
cryptography is still needed for authentication, digital signatures, and secret-key exchanges. This
means that, to be able to use all aspects of security today, we need both symmetric-key and
asymmetric-key cryptography.

Trapdoor One-Way Function

The main idea behind asymmetric-key cryptography is the concept of the trapdoor one-way function.

17/40
A function is a rule that associates (maps) one element in set A, called the domain, to one element
in set B, called the range, as shown in the below figure 10.5.

Figure 10.5: A function as rule mapping a domain to a range

One-way function A one-way function (OWF) is a function that satisfies the following two properties:

1. f is easy to compute. In other words, given x, y = f(x) can be easily computed.

2. f-1 is difficult to compute. In other words, given y, it is computationally infeasible to calculate
x = f-1(y)

A trapdoor one-way function (TOWF) is a one-way function with a third property:

3. Given y and a trapdoor (secret), x can be computed easily.

Knapsack Cryptosystem

Suppose we are given two k-tuples, a = [a1, a2, …., ak] and x = [x1, x2, …., xk].
The first tuple is the predefined set; the second tuple, in which x i is only 0 or 1, defines which
elements of a are to be dropped in the knapsack. The sum of elements in the knapsack is

s = knapsackSum(a, x) = a1x1 + a2x2 + …… + akxk

Given a and x, it is easy to calculate s. however, given s and a it is difficult to find x. in other
words,
s = knapsackSum(x, a) is easy to calculate, but
x = inv_knapsackSum(s, a) is difficult.

Superincreasing Tuple It is easy to compute knapsackSum and inv_knapsackSum if the k-tuple

a is superincreasing.

In a superincreasing tuple, ai ≥ a1 + a2 + … + ai−1.

In other words, each element (except a1) is greater than or equal to the sum of all previous
elements.

18/40
 Algorithm: knapsackSum and inv_knapsackSum for a superincreasing k-tuple

Example:
Assume that a = [17, 25, 46, 94, 201,400] and s = 272 are given. Show that the tuple x is found
using inv_knapsackSum routine.

Solution:

In this case x = [0, 1, 1, 0, 1, 0], which means that 25, 46, and 201 are in the knapsack.

Secret Communication with Knapsacks

Let us see how Alice can send a secret message to Bob using a knapsack cryptosystem. The idea is
shown in Figure 10.6.

Key Generation
a. Create a superincreasing k-tuple b = [b1, b2, …, bk].
b. Choose a modulus n, such that n > b1 + b2 + … + bk.
c. Select a random integer r that is relatively prime with n and 1 <= r <= n-1.
d. Create temporary k-tuple t = [t1, t2, … tk] in which ti = r x bi nod n.
e. Select a permutation of k objects and find a new tuple a = permute (t).
f. The public key is the k-tuple a. the private key is n, r, and the k-tuple b.

19/40
 Figure 10.6: Secret Communication with Knapsack cryptosystem

Encryption
Suppose Alice needs to send a message to Bob.
a. Alice converts her message to a k-tuple x = [x1, x2, …, xk] in which xi is either 0 or 1. The tuple
x is the plaintext.
b. Alice uses the knapsackSum routine to calculate s. She then sends the value of s as the
ciphertext.

Decryption
Bob receives the ciphertext s.
a. Bob calculates s' = r-1 x s mod n.
b. Bob uses inv_knapsackSum to create x'.
c. Bob permutes x' to find x. the tuple x is the recovered plaintext.

This is a trivial (very insecure) example just to show the procedure.

20/40
2. RSA Cryptosystem

The pioneering paper by Diffie and Hellman introduced a new approach to cryptography and, in effect,
challenged cryptologists to come up with a cryptographic algorithm that met the requirements for public-key
systems. One of the first of the responses to the challenge was developed in 1977 by Ron Rivest, Adi Shamir,
and Len Adleman at MIT and first published in 1978. The Rivest-Shamir-Adleman (RSA) scheme has since
that time reigned supreme as the most widely accepted and implemented general-purpose approach to public-
key encryption.
The RSA scheme is a block cipher in which the plaintext and ciphertext are integers between 0 and n-1
for some n. A typical size for n is 1024 bits, or 309 decimal digits.

In RSA, p and q must be at least 512 bits; n must be at least 1024 bits.

Assume:
C- Ciphertext, M-Plaintext, e-encryption key, d-decryption key.
Both sender and receiver must know the value of n. The sender knows the value of e, and only the
receiver knows the value of d. thus, this is a public-key encryption algorithm with a public key of KU = {e, n}
and a private key of KR = {d, n}.

1. Take two large Prim numbers p & q.

2. Calculate n = p * q.
3. Calculate Φ(n) = (p-1) (q-1) from Euler’s totient function. e = 7; d = 3; Φ(n) = 20
4. Select e from Φ(n). [ therefore gcd(Φ(n), e) = 1; 1<e< Φ(n)]
5. Take plaintext M. ed = Φ(n) +1
6. Calculate ciphertext C = Me mod n.
7*3 = 1+20
7. Calculate plaintext M = Cd mod n, where d = e-1 mod Φ(n).

To find d value:
C = Me mod n ed ≡ 1 mod Φ(n)
M = Cd mod n.
Substitute C value then, 7*3 ≡ 1 mod 20
(Me mod n)d mod n
≡ [(Me)d mod n] mod n 21 ≡ 1 mod 20
M ≡ Med mod n
(or) Med ≡ M mod n …(1)
From Euler’s theorem
MΦ (n) +1 ≡ M mod n … (2)

// M value is below 255 and n, p, q values are very large so m is relatively prime with n.
// M and n are relatively prime then from Euler’s theorem MΦ(n)+1 ≡ M mod n

From (1) and (2) we can write

21/40
 Med = MΦ(n)+1
 ed = Φ(n) + 1
 ed ≡ 1 mod Φ(n)
 d = e-1 mod Φ(n)

Example 1: Perform encryption and decryption using the RSA algorithm, for the following
a) p=17; q=11; e=7; M=88;

M = 88
1. p = 17, q = 11
2. n = 17 * 11 = 187
3. Φ(n) = 16 * 10 = 160
4. Select e = 7
5. C = Me mod n = (88)7 mod 187

From the third property of modular arithmetic

[(a mod n) * (b mod n) ] mod n = (a * b) mod n
[(a mod n) * (a mod n) ] mod n = (a * a) mod n
[(a mod n) * (a mod n) ] mod n = a2 mod n

from the above formula

(88)7 mod 187 = [ (884 mod 187) * (882 mod 187) * (881 mod 187)] mod 187

881 mod 187 = 88

882 mod 187 = 88 mod 187 * 88 mod 187
= 77
884 mod 187 = 882 mod 187 * 882 mod 187
= 77 * 77 mod 187
= 132
7
88 mod 187 = (132 * 77 * 88) mod 187
= 11.

1. Calculating d:
The formula is ed ≡ 1 mod Φ(n)
7 * d ≡ 1 mod 160
7 * 23 ≡ 1 mod 160 [Since 7*23=161]
d = 23
2. for decryption, we calculate M = Cd mod n

M = 1123 mod 187

= [(111 mod 187) * (112 mod 187) * (114mod 187) * (118 mod 187) * (118 mod 187)]
mod 187
1
11 mod 187 = 11
112 mod 187 = 121
114 mod 187 = 55
118 mod 187 = 33
1123 mod 187 = (11 * 121 * 55 * 33 * 33) mod 187
= 88.

22/40
 Public key KU ={7, 187}
Private key KR = {23, 187}

Example 2: Perform encryption and decryption using the RSA algorithm, for the following

a) p=3; q=11; e=7; M=5.

b) p=5; q=11; e=3; M=9.
c) p=11; q=13; e=11; M=7.

Solution:
a) p=3; q=11; e=7; M=5.
n = p*q = 3 * 11 = 33
Φ(n) = (p-1) (q-1) = (3-1) (11-1) = 2*10 = 20
ed ≡ 1 mod Φ(n)
7*d ≡ 1 mod 20  (7 * d) mod 20 = 1 mod 20
 (7 * 3) mod 20 = 1 mod 20
 21 mod 20 = 1 mod 20
d=3
For Encryption:
C = Me mod n
= 57 mod 33
= 78125 mod 33
= 14
For Decryption
M = Cd mod n
= 143 mod 33
= 2744 mod 33
=5
b) p=5; q=11; e=3; M=9.
n = p*q = 5 * 11 = 55
Φ(n) = (p-1)*(q-1) = (5-1) * (11-1) = 4*10 = 40
ed ≡ 1 mod Φ(n)
3*d ≡ 1 mod 40  (3 * d) mod 40 = 1 mod 40
 (3 * 27) mod 40 = 1 mod 40
 81 mod 40 = 1 mod 40
 d = 27
For Encryption:
C = Me mod n
= 93 mod 55

23/40
 = 729 mod 55
= 14
For Decryption
M = Cd mod n
= 1427 mod 55
=5
c) p=11; q=13; e=11; M=7.
n = p*q = 11 * 13 = 143
Φ(n) = (p-1)*(q-1) = (11-1) * (13-1) = 10*12 = 120
ed ≡ 1 mod Φ(n)
11*d ≡ 1 mod 120  (11 * d) mod 120 = 1 mod 120
 (11 * 11) mod 120 = 1 mod 120
 121 mod 120 = 1 mod 120
 d = 11
For Encryption:
C = Me mod n
= 711 mod 143
72 mod 143 = 49 mod 143
74 mod 143 = (49*49) mod 143
= 113
8
7 mod 143 = (113*113) mod 143
= 12769 mod 143
= 42
7 mod 143 = (72*7) mod 143
3

= 343 mod 143

= 57
711 mod 143 = (42*57) mod 143
= 2394 mod 143
= 106
For Decryption
M = Cd mod n
= 10611 mod 143
=7
Exercise: Perform encryption and decryption using the RSA algorithm, for the following
a) p=7; q=11; e=17; M=8.
b) p=17; q=31; e=7; M=2.

Example:
Bob chooses 7 and 11 as p and q and calculates n = 77. The value of (n) = (7 − 1)(11 − 1) or 60.
Now he chooses two exponents, e and d, from Z60∗. If he chooses e to be 13, then d is 37. Note that

24/40
e × d mod 60 = 1 (they are inverses of each Now imagine that Alice wants to send the plaintext 5 to
Bob. She uses the public exponent 13 to encrypt 5.

Plaintext: 5 C = 513 mod 77 = 26 mod 77 Ciphertext: 26

Bob receives the ciphertext 26 and uses the private key 37 to decipher the ciphertext:

Ciphertext: 26 P = 2637 mod 77 = 5 mod 77 Plaintext: 5

Example:
Now assume that another person, John, wants to send a message to Bob. John can use the same
public key announced by Bob (probably on his website), 13; John’s plaintext is 63. John calculates
the following:

Plaintext: 63 C = 6313 mod 77 = 28 mod 77 Ciphertext: 28

Bob receives the ciphertext 28 and uses his private key 37 to decipher the ciphertext:

Ciphertext: 28 P = 2837 mod 77 = 63 mod 77 Plaintext: 63

Example:
Jennifer creates a pair of keys for herself. She chooses p = 397 and q = 401. She calculates
n = 159197. She then calculates (n) = 158400. She then chooses e = 343 and d = 12007. Show
how Ted can send a message to Jennifer if he knows e and n.

Suppose Ted wants to send the message “NO” to Jennifer. He changes each character to a number
(from 00 to 25), with each character coded as two digits. He then concatenates the two coded
characters and gets a four-digit number. The plaintext is 1314. Figure 10.7 shows the process.

Figure 10.7 Encryption and decryption for the above example

Attacks on RSA

Security of RSA:-
These are explained as following below.

1. Plain text attacks:

It is classified into 3 subcategories:-

• (i) Short message attack:

In this we assume that attacker knows some blocks of plain text and tries to decode cipher
text with the help of that. So, to prevent this pad the plain text before encrypting.
• (ii) Cycling attack:
In this attacker will think that plain text is converted into cipher text using permutation and

25/40
 he will apply right for conversion. But attacker does not right plain text. Hence will keep
doing it.
• (iii) Unconcealed Message attack:
Sometimes happened that plain text is same as cipher text after encryption. So it must be
checked it cannot be attacked.

2. Choosen cipher attack:

In this attacker is able to find out plain text based on cipher text using Extended Euclidian
Algorithm.

3. Factorization attack:
If attacker will able to know P and Q using N, then he could find out value of private key. This
can be failed when N contains at least 300 longer digits in decimal terms, attacker will not able
to find. Hence it fails.

4. Attacks on Encryption key:

If we take smaller value of E in RSA this may occur so to avoid this take value of E = 2^16+1 (at
least).

5. Attacks on Decryption key:

• (i) Revealed decryption exponent attack:

If attacker somehow guess decryption key D, not only the cipher text generated by encryption
the plain text with corresponding encryption key is in danger, but even future messages are
also in danger. So, it is advised to take fresh values of two prime numbers (i.e; P and Q), N
and E.
• (ii) Low decryption exponent attack:
If we take smaller value of D in RSA this may occur so to avoid this take value of D =
2^16+1(at least).

3. RABIN Cryptosystem

The Rabin cryptosystem, devised by M. Rabin, is a variation of the RSA cryptosystem.

Figure 10.8 Rabin cryptosystem

26/40
The Rabin cryptosystem can be thought of as an RSA cryptosystem in which the value of e and d
are fixed; e = 2 and d = ½. The encryption is C ≡ P2 (mod n) and the decryption is P ≡ C1/2 (mod
n).

The public key in the Rabin cryptosystem is n; the private key is the tuple (p, q). Everyone can
encrypt a message using n; only Bob can decrypt the message using p and q. decryption of the
message is infeasible for Eve because she does not know the values of p and q. Figure 10.8 shows
the encryption and decryption.

Algorithm: Key generation for Rabin cryptosystem

Algorithm: Encryption in Rabin cryptosystem

Algorithm: Decryption in Rabin cryptosystem

27/40
The most important point about the Rabin system is that it is to deterministic. The decryption has
four answers. The receiver chooses one among the four plaintexts that is meaningful/suitable for
the situation.

The Robin cryptosystem is not deterministic; Decryption creates four equally probable
plaintexts.

Example:
Using the Robin cryptosystem with p = 7, q = 11:
a. Encrypt P = 10 to find the ciphertext.
b. Use the Chinese Remainder theorem to find four possible plaintexts

Solution:

p = 7, q = 11 Note that both are congruent to 3 mod 4.

n = p * q = 7 * 11 = 77
Note that 77 and 10 are relatively prime.

Encryption:
C = p2 mod n
= 102 mod 77
= 100 mod 77
= 23

Decryption:
a1 = + (C(p+1)/4) mod p
a2 = - (C(p+1)/4) mod p
b1 = + (C(q+1)/4) mod q
b2 = - (C(q+1)/4) mod q

a1 = + 23(7+1)/4 mod 7
= 232 mod 7
= 529 mod 7
= 4 mod 7
=4
a2 = -4 mod 7
= (-4+7) mod 7
= 3 mod 7
=3
b1 = + 23(11+1)/4 mod 11
= 233 mod 11
= 12167 mod 11

28/40
 = 1 mod 11
=1
b2 = - 1 mod 11
= (-1+11) mod 11
= 10 mod 11
= 10
Now Chinese Remainder Theorem will be called for 4 times to produce four plaintexts.
P1  Chinese_Remainder(a1, b1, p, q)
P2  Chinese_Remainder(a1, b2, p, q)
P3  Chinese_Remainder(a2, b1, p, q)
P4  Chinese_Remainder(a2, b2, p, q)

P1  Chinese_Remainder (a1, b1, p, q)

P1  Chinese_Remainder (4, 1, 7, 11)

x ≡ a1 mod p
x ≡ b1 mod q

M = p * q = 7 * 11 = 77  M = 77
𝑀 77
M1 = = = 11  M1 = 11
𝑚1 7
𝑀 77
M2 = 𝑚2
= 11
=7  M2 = 7

(M1 * M1-1) mod p = 1

(11 * 2) mod 7 = 1  M1-1 = 2
(M2 * M2-1) mod q = 1
(7 * 8) mod 11 = 1  M2-1 = 8

P1 = [(a1 * M1 * M1-1) + (b1 * M2 * M2-1)] mod M

= [(4 * 11 * 2) + (1 * 7 * 8)] mod 77
= (88 + 56) mod 77
= 144 mod 77
= 67
P2  Chinese_Remainder(a1, b2, p, q)
P2  Chinese_Remainder(4, 10, 7, 11)

x ≡ 4 mod 7
x ≡ 10 mod 11

As moduli p and q are common for all above four cases, M, M1, M2, M1-1 and M2-1 also common.

29/40
P2 = [(a1 * M1 * M1-1) + (b2 * M2 * M2-1)] mod M
= [(4 * 11 * 2) + (10 * 7 * 8)] mod 77
= (88 + 560) mod 77
= 144 mod 77
= 32

P3  Chinese_Remainder(a2, b1, p, q)
P3  Chinese_Remainder(3, 1, 7, 11)

x ≡ 3 mod 7
x ≡ 1 mod 11

P3 = [(a2 * M1 * M1-1) + (b1 * M2 * M2-1)] mod M

= [(3 * 11 * 2) + (1 * 7 * 8)] mod 77
= (66 + 56) mod 77
= 122 mod 77
= 45
P4  Chinese_Remainder(a2, b2, p, q)
P4  Chinese_Remainder(3, 10, 7, 11)

x ≡ 3 mod 7
x ≡ 10 mod 11

P4 = [(a2 * M1 * M1-1) + (b2 * M2 * M2-1)] mod M

= [(3 * 11 * 2) + (10 * 7 * 8)] mod 77
= (66 + 560) mod 77
= 626 mod 77
= 10
Therefore, the four possible plaintexts are P1 = 67, P2 = 32, P3 = 45, P4 = 10. Among these, P4 = 10
is the original plaintext.

Example:

Here is a very trivial example to show the idea.

1. Bob selects p = 23 and q = 7. Note that both are congruent to 3 mod 4.

2. Bob calculates n = p × q = 161.
3. Bob announces n publicly; he keeps p and q private.
4. Alice wants to send the plaintext P = 24. Note that 161 and 24 are relatively prime; 24 is in
Z161*. She calculates C = 242 mod 161 = 93, and sends the ciphertext 93 to Bob.

30/40
 5. Bob receives 93 and calculates four values:
a1 = +(93 (23+1)/4) mod 23 = 1 mod 23
a2 = −(93 (23+1)/4) mod 23 = 22 mod 23
b1 = +(93 (7+1)/4) mod 7 = 4 mod 7
b2 = −(93 (7+1)/4) mod 7 = 3 mod 7

Bob takes four possible answers, (a1, b1), (a1, b2), (a2, b1), and (a2, b2), and uses the Chinese
remainder theorem to find four possible plaintexts: 116, 24, 137, and 45. Note that only the second
answer is Alice’s plaintext.

Calculations are shown below:

P1  Chinese_Remainder (a1, b1, p, q)

P1  Chinese_Remainder (1, 4, 23, 7)

x ≡ a1 mod p
x ≡ b1 mod q

M = p * q = 23 * 7 = 161  M = 161
𝑀 161
M1 = = =7  M1 = 7
𝑚1 23
𝑀 161
M2 = = = 23  M2 = 23
𝑚2 7

(M1 * M1-1) mod p = 1

(7 * 10) mod 23 = 1  M1-1 = 10
(M2 * M2-1) mod q = 1
(23 * 4) mod 7 = 1  M2-1 = 4

P1 = [(a1 * M1 * M1-1) + (b1 * M2 * M2-1)] mod M

= [(1 * 7 * 10) + (4 * 23 * 4)] mod 161
= (70 + 368) mod 161
= 438 mod 161
= 116
P2  Chinese_Remainder(a1, b2, p, q)
P2  Chinese_Remainder(1, 3, 23, 7)

x ≡ 1 mod 23
x ≡ 3 mod 7

As moduli p and q are common for all above four cases, M, M1, M2, M1-1 and M2-1 also common.

P2 = [(a1 * M1 * M1-1) + (b2 * M2 * M2-1)] mod M

= [(1 * 7 * 10) + (3 * 23 * 4)] mod 161
= (70 + 276) mod 161

31/40
 = 346 mod 161
= 24

P3  Chinese_Remainder(a2, b1, p, q)
P3  Chinese_Remainder(22, 4, 23, 7)

x ≡ 22 mod 23
x ≡ 4 mod 7

P3 = [(a2 * M1 * M1-1) + (b1 * M2 * M2-1)] mod M

= [(22 * 7 * 10) + (4 * 23 * 4)] mod 161
= (1540 + 368) mod 161
= 1908 mod 161
= 137
P4  Chinese_Remainder(a2, b2, p, q)
P4  Chinese_Remainder(22, 3, 23, 7)

x ≡ 22 mod 23
x ≡ 3 mod 7

P4 = [(a2 * M1 * M1-1) + (b2 * M2 * M2-1)] mod M

= [(22 * 7 * 10) + (3 * 23 * 4)] mod 161
= (1540 + 276) mod 161
= 1816 mod 161
= 45
Therefore, the four possible plaintexts are P1 = 116, P2 = 24, P3 = 137, P4 = 45. Among these, P2 =
24 is the original plaintext.

Exercise:
Using the Robin cryptosystem with p = 47, q = 11:
a. Encrypt P = 17 to find the ciphertext.
b. Use the Chinese Remainder theorem to find four possible plaintexts

4. ElGamal Cryptosystem

Besides RSA and Rabin, another public-key cryptosystem is ElGamal, named after its inventor,
Taher ElGamal. ElGamal is based on the discrete logarithm problem discussed in the previous
chapter.

Figure 10.9 shows key generation, encryption, and decryption in ElGamal.

32/40
Figure 10.9 Key generation, encryption, and decryption in ElGamal

Algorithm: ElGamal key generation

Algorithm: ElGamal encryption

33/40
 Algorithm: ElGamal decryption

Example:

Here is a trivial example. Bob chooses p = 11 and e 1 = 2 and d = 3; e2 = e1d mod 11 = 8. So the public
keys are (2, 8, 11) and the private key is 3. Alice chooses r = 4 and calculates C1 and C2 for the
plaintext 7.

Encryption
C1 = e1r mod 11 = 24 mod 11 = 5 mod 11
C2 = P x e2r mod 11 = 7 x 84 mod 11 = 7 x 4096 mod 11 = 6 mod 11
Ciphertext: (5, 6)

Bob receives the ciphertext (5 and 6) and calculates the plaintext.

P = C2 x (C1d)-1 mod p
= C2 x (C1)p-1-d mod p [according to Fermat’s little theorem]
= 6 x 511-1-3 mod 11
=7

For the ElGamal cryptosystem, p must be at least 300 digits and r must be new for each
encipherment.

5. Elliptic Curve Cryptosystems

Although RSA and ElGamal are secure asymmetric-key cryptosystems, their security comes with
their large keys. Elliptic curve cryptosystem (ECC) gives the same level of security with smaller key
sizes.

Comparable key sizes for equivalent security

Symmetric scheme ECC-based scheme RSA/DSA

(key size in bits) (size of n in bits) (modulus size in bits)
56 112 512

: : :

34/40
 : : :

128 256 3072

: : :
: : :

256 512 15360

The elliptic curves over real numbers is of the form

y2 = x3 + ax + b [for some fixed values for the parameters a and b]

The curve is non-singular which means that the curve has no self-intersections.

Since the curve is symmetrical about the x-axis, given any point P, we can take −P to be the point
opposite it. We take −O to be just O.

The example elliptic curves are given here

Expressing the elliptic curve in the form Ep(a, b) means that we have an elliptic curve with
parameters a and b and we need to operate over mod p where p is a prime number.

Example:
Find points on the elliptic curve E13(1, 6)

Solution:

In the above problem a = 1, b = 6, p = 11

The general elliptic curve form is y2 = x3 + ax + b

Substitute a and b values the equation changed to y 2 = x3 + x + 6

The calculation should be done over mod 11.

So x and y values should only vary from 0 to 10 - because Z11 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

We need to find the values of x and y such that LHS equals RHS. When LHS = RHS that point will
lie on the elliptic curve.

35/40
 RHS LHS
x x3 + x + 6 (mod 11) y y2 (mod 11)
0 6 0 0
1 8 1 1
2 5 2 4
3 3 3 9
4 8 4 5
5 4 5 3
6 8 6 3
7 4 7 5
8 9 8 9
9 7 9 4
10 4 10 1

The points on the elliptic curve are

(2, 4) (2, 7)
(3, 5) (3, 6)
(5, 2) (5, 9)
(7, 2) (7, 9)
(8, 3) (8, 8)
(10, 2) (10, 9)

Exercise:
Find the points on the elliptic curve y2 = x3 + x + 1 calculation should be done over modulo 13.

Finding an inverse The inverse of a point (x, y) is (x, -y), where –y is the additive inverse of
y. for example, if p = 13, the inverse of (4, 2) is (4, -2 mod 13) = (4, 11).

Elliptic Curve Cryptography (ECC)

( [Link] )

− It is asymmetric | public key cryptosystem

− It provides equal security with smaller key size (ex: as compared to RSA) as compared to non-
ECC algorithms. i.e. small key size and high security

36/40
− It makes use of Elliptic curves
− Elliptic curves are symmetric about x-axis and both ends of the curve goes to infinity but we are
limiting it to n
− Elliptic curves are defined by some mathematical functions – cubic function
− Ex: y2 = x3 + ax + b //a and b are constants, and it is equation of degree 3
− Symmetric to x – axis
− If we draw a line it will touch a maximum of three points
A trapdoor function
A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute
in the opposite direction (finding its inverse) without a special information, called the trapdoor.

− Let Ep(a, b) be the elliptic curve

− Consider the equation Q = kP where Q and P are points on curve and k < n.
− If k and P given, it should be easy to find Q but if we know Q and P, it should be extremely
difficult to find k. This is called the discrete logarithm problem for elliptic curves. i.e. it is a one-
way function or trap door junction. A → B is very easy but coming B → A is very difficult.

Elliptic Curve Cryptography (ECC) Algorithm

Global public elements

− Eq(a, b): Elliptic curve with parameters a, b and q where q is prime number or of the form 2m
− G: point on the elliptic curve whose order is greater than value of n (>n).
(Let us assume A is sender and B is receiver)

User A key generation

− Select private key nA such that nA < n
− Calculate public key of A PA = nA * G
User B key generation
− Select private key nB such that nB < n
− Calculate public key PB = nB * G
Calculation of secret key by user A
− k = n A * PB
Calculation of secret key by user B
− k = nB * P A
ECC Encryption
Let the message be M

37/40
First encode this message M into a point on elliptic curve
Let this point be Pm, now this point is encrypted
For encryption, choose a random positive integer k then the cipher point will be
Cm = {kG, Pm + kPB }
This point will be sent to the receiver.

ECC Decryption
For decryption, multiply 1st coordinate in the point with receiver’s secret key
i.e. kG * nB (for decryption private key of B is used)

then subtract it from 2nd coordinate in the pair

i.e Pm + kPB – ( kG * nB)
but we know PB = nB*G
so, = Pm, - kPB - kPB
= Pm (Original Point)

So, receiver gets the same point

Security of Elliptic Curve Cryptography

Table 1: Comparable Key Sizes in Terms of Computational Effort for Cryptanalysis

The security of ECC depends on how difficult it is to determine k given kP and P. This is referred to
as the elliptic curve logarithm problem. Table 1, compares various algorithms by showing
comparable key sizes in terms of computational effort for cryptanalysis. As can be seen, a
considerably smaller key size can be used for ECC compared to RSA.

Analysis indicates that for equal key lengths, the computational effort required for ECC and RSA is
comparable. Thus, there is a computational advantage to using ECC with a shorter key length than
a comparably secure RSA.

38/40
Elliptic Curve Cryptography Simulating ElGamal

Several methods have been used to encrypt and decrypt using elliptic curves. The common one is
to simulate the ElGamal cryptosystem using an elliptic curve over GF(p) or GF(2 n), as shown in
figure 10.10.

Figure 10.10 ElGamal cryptosystem using the elliptic curve

Generating Public and Private Keys

1. Bob chooses E(a, b) with an elliptic curve over FG(p) or GF(2n).

2. Bob chooses a point on the curve, e1(x1, y1)
3. Bob chooses an integer d.
4. Bob calculates e2(x2, y2) = d × e1(x1, y1)
5. Bob announces E(a, b), e1(x1, y1), and e2(x2, y2) as his public key; he keeps d as his private
key

Encryption
Alice selects P, a point on the curve, as her plaintext, P. She then calculates a pair of points on the
text as ciphertexts:

Decryption
Bob, after receiving C1 and C2, calculates P, the plaintext using the following formula.

Example:

1. Bob selects E67(2, 3) as the elliptic curve over GF(p).

39/40
 2. Bob selects e1 = (2, 22) and d = 4.
3. Bob calculates e2 = (13, 45), where e2 = d × e1.
4. Bob publicly announces the tuple (E, e1, e2).
5. Alice sends the plaintext P = (24, 26) to Bob. She selects r = 2.
6. Alice finds the point C1 = (35, 1), C2 = (21, 44).
7. Bob receives C1, C2. He uses 4 x C1(35,1) to get (23, 25), inverts the points (23, 25) to get
the points (23, 42).
8. Bob adds (23, 42) with C2 = (21, 44) to get the original one P = (24, 26).

CJR 40/40