Introduction to Cryptography with Open-Source Software

Chapter 6

Public-key cryptosystems based on

logarithms and knapsacks

This chapter will include discussions o f

• Primitive roots.

• The El Gamal cryptosystem.

• Methods of calculating discrete logar ithms.

• Cryptosystems ba sed on intege r knapsack problems.

• Methods of attacking knapsack cryptosystems.

6.1 El Gamal’s cryptosystem

Recall from Cha pter 2 that although it is very easy to compute a modular

exp onentiation:

b = a

x

(mod p)

it is in general very difficult to go in the other direction, that is, given integers

a, b and p, to find x satisfying the above equation. Finding the value of x

is c alled the discrete logarithm problem, and althoug h it can