Mumbai university > Electronics and telecommunication Engineering > Sem 7 > Data compression and Encryption

Marks: 5

Years: Dec 2015

a. In public key encryption, schemes are secure only if authenticity of the public key is assured.

b. Diffie-Hellman key exchange is a simple public key algorithm.

c. The protocol enables two users to establish a secret key using a public key based on discrete algorithms.

d. The protocol is secure only if the authenticity of the two participants can be established.

e. For this scheme, there are two publicly known numbers:

• A prime number q

• An integer α that is primitive root of q

f. Suppose users A and B wish to exchange the key

User A selects a random integer XA< q and computes

$Y_A$ = $α^{XA}$ mod q

g. User B independently selects a random integer XB< q and compute

$Y_B$ = $α^{XB}$ mod q

h. Each side keeps X value private and makes Y value available publicly to the other side user.

i. A computes the key as

k = $({Y_B})^{XA}$ mod q

User B computes the key as

k = $({Y_A})^{XB}$ mod q

j. The calculations produce identical results:

k = $({Y_B})^{XA}$ mod q ----- calculated by user A

= $({α^{XB}} mod q)^{XA}$ mod q

= $({α^{XB}})^{ XA}$ mod q ------- By rules of modular arithmetic

= ${α^{XB}}^{ XA}$ mod q

= $({α^{XA}})^{ XB}$ mod q

k = $({α^{XA}} mod q)^{XB}$ mod q

k. Diffie-Hellman key exchange algorithm

1. k = $({Y_A})^{XB}$ mod q

2. Global public elements

Q: prime number

α: α < q and it is primitive root of q

1. User A key encryption

Select private key ${X_A}{X_A}$< q

Calculation of public key ${Y_A}{Y_A}$ = $α^{XA}$ mod q

1. User B key encryption

Select private key ${X_B}{X_B}$< q

Calculation of public key ${Y_B}{Y_B}$ = $α^{XB}$ mod q

1. Calculation of secret key by A

k = $({Y_B})^{XA}$ mod q

1. Calculation of secret key by B

k = $({Y_A})^{XB}$ mod q

1. The result is that two sides have exchanged a secret value.

2. Since $X_A$ and $X_B$ are private, an adversary only has the following ingredients to work with:

q, α, $Y_A$ and $Y_B$

For e.g. To determine the private key of user B, an adversary must compute

$Y_B$ = $α^{XB}$ mod q

$X_B$ = d logx,q ($Y_B$)

1. The security of the Diffie Hellman key exchange lies in the fact that it is easy to calculate exponential modulo a prime, it is very difficult to calculate discrete algorithm.