Diffie Hellman key exchange algorithm

1. In Public key encryption schemes are secure only if authenticity of the public key is assured.
2. Diffie-Hellman key exchange is a simple public key algorithm.
3. The protocol enables 2 users to establish a secret key using a public key scheme based on discrete algorithms.
4. The protocol is secure only if the authenticity of the 2 participants can be established.
5. or this scheme, there are 2 publicly known numbers :
   • A prime number q
   • An integer α that is a primitive root of q.
   (Note: Premitive root of a prime number P is one, whose powers module P generate all the images from 1 to P-1)
6. Suppose users A and B wish to exchange the key.
   User A selects a random integer XA<q$X_A<q$ and computes
   YA=αXAmod q$Y_A={\alpha }^{XA}modq$
7. User B independently selects a random integer XB<q$X_B<q$ and compute
   YB=αXBmod q$Y_B={\alpha }^{XB}modq$
8. Each side keeps X value private and makes Y value available publicly to the other side user A computes the key as:
   k=(YB)XAmod q$k=(Y_B{)}^{XA}modq$
   User B computes the key as :
   k=(YA)XBmod q$k=(Y_A{)}^{XB}modq$
   The calculations produce identical results :
   k=(YB)XAmod q−>calculated by user A=(αXBmod q)XAmod q=(αXB)XA(mod q)−>By rules of modular arithmetic=αXB XAmod q=(αXA)XBmod q$$\begin{gathered} k=(Y_B{)}^{XA}modq->\text{calculated by user A} \\ =({\alpha }^{XB}modq{)}^{XA}modq \\ =({\alpha }^{XB}{)}^{XA}(modq)->\text{By rules of modular arithmetic} \\ ={\alpha }^{XBXA}modq \\ =({\alpha }^{XA}{)}^{XB}modq \end{gathered}$$
   k=(αXAmod q)XBmod q$k=({\alpha }^{XA}modq{)}^{XB}modq$
9. Diffie Hellman key Exchange Algorithm
   1. k=(YA)XBmodq$k=(Y_A{)}^{XB}modq$ -> same as calculated by B
   2. Global Public Elements
      q ; prime number
      α ; α < q and it is primitive root of q
   3. USER A KEY GENERATION
      Select Private key XAXA<q$X_A{X}_A<q$
      Calculation of Public key YAYA=αXAmod q$Y_A{Y}_A={\alpha }^{XA}modq$
   4. USER B KEY GENERATION
      Select Private key XBXB<q$X_B{X}_B<q$
      Calculation of Public key YBYB=αXBmod q$Y_B{Y}_B={\alpha }^{XB}modq$
   5. Calculation of Secret Key by A
      k=(YB)XAmod q$k=(Y_B{)}^{XA}modq$
   6. Calculation of Secret Key by B
      k=(YA)XBmod q$k=(Y_A{)}^{XB}modq$
10. The result is that two sides have exchanged a secret value.
11. Since XA$X_A$ and XB$X_B$ are private the other party can work only following ingredients:
    q,α,XA,XB$q,\alpha ,X_A,X_B$
    Note: YB=αXB$Y_B={\alpha }_{XB}$ mod a
    XB=dlogα,q(YB)$XB=d\log \alpha ,q(YB)$

↑$\uparrow$

$$ Discrete Logarithm

12. The algorithm security lies on the fact that it is easy to calculate exponential modulo a prime, last difficult to calculate to calculate discrete logarithm.

Figure 5.6 Diffie-Hellman Exchange Algorithm$$$$

RSA cryptosystem

RSA is an asymmetric system , which means that a key pair will be generated (we will see how soon) , a public key and a private key , obviously you keep your private key secure and pass around the public one.

The algorithm was published in the 70’s by Ron Rivest, Adi Shamir, and Leonard Adleman, hence RSA , and it sort of implement’s a trapdoor function such as Diffie’s one.

RSA is rather slow so it’s hardly used to encrypt data , more frequently it is used to encrypt and pass around symmetric keys which can actually deal with encryption at a faster speed.

We’ve got a message (“HELLO”) , and we’ve picked two tuples with two numbers each ( I will explain how these came about later). Obviously there’s no arithmetic operation we can perform with strings , so the message has to be convert it to something , so let’s say “HELLO” converts using some conversion algo to “2”

Normally , in production , a lot of different techniques are used to encode the message and padding is also used

The interesting bit is how we come about those numbers , and how (5,14) is related to (11,14), and this is the interesting part i believe , let’s start:

The details of the Decryption/Encryption pair:

1. Pick two prime numbers , I will pick 2 and 7 , lets call them p and q

P = 2 and Q = 7

2. Multiply P and Q , and that becomes the modulus

N = P * Q = 14

3. Make a list between 1 and 14 and remove the common factors:

Public Key Cryptography

Unlike symmetric key cryptography, we do not find historical use of public-key cryptography. It is a relatively new concept.

Symmetric cryptography was well suited for organizations such as governments, military, and big financial corporations were involved in the classified communication.

With the spread of more unsecure computer networks in last few decades, a genuine need was felt to use cryptography at larger scale. The symmetric key was found to be non-practical due to challenges it faced for key management. This gave rise to the public key cryptosystems.

The process of encryption and decryption is depicted in the following illustration −