Integer factorization problem and Discrete logarithm problem, key management issues Symmetric key cryptosystems formation of shared secret key (Diffie Hellman)

Discrete Logarithm Problem

Given y, g, and p, it is difficult to find x where y = g^xmodp

Integer Factorisation Problem

Given a large n, find prime factors p and q such that n = p * q

Requires exponential time to find the prime factors of a number

Diffie Hellman Key Exchange Algorithm

The Diffie-Hellman algorithm is being used to establish a shared secret that can be used for secret communications while exchanging data over a public network

Diffie-Hellman is an asymmetric algorithm used to establish a symmetric key.

• Good generator that maximises search space must be chosen
• A large prime p must be chosen
• Works on the difficulty of Discrete Logarithm Problem

Step 1: Alice and Bob get public numbers P = 23, G = 5  
Step 2: Alice selected a private key a = 4 and  
        Bob selected a private key b = 3  
Step 3: Alice and Bob compute public values  
Alice:    x =(5^4 mod 23) = (625 mod 23) = 4  
        Bob:    y = (5^3 mod 23) = (125 mod 23)  = 10  
Step 4: Alice and Bob exchange public numbers  
Step 5: Alice receives public key y =10 and  
        Bob receives public key x = 4  
Step 6: Alice and Bob compute symmetric keys  
        Alice:  ka = y^a mod p = 10000 mod 23 = 18  
        Bob:    kb = x^b mod p = 64 mod 23 = 18  
Step 7: 18 is the shared secret.

Key Management

Four Methods of Public Key Distribution

• Manual Delivery - Awkward
• Trusted Third Party Delivery - N(N-1)/2 keys required to be shared
• Encrypted Transmission of new key using old key - If attacker gets hold of old key, every new key is compromised
• Third Party Encrypted Delivery (KDC) - Widely adopted, works on Master key and Session key

Key Distribution Scenario (Symmetric Exchange Using Symmetric Encryption)

Symmetric Key Exchange Using Asymmetric Encryption

**Susceptible to Man-In-The-Middle attacks **

The Handshake Protocol

The exchange typically follows a five-step process between two parties, A and B:

1. Initiation: User A sends a message to B containing their identity (IDA​) and a nonce (N1​), which is a unique random number used to identify this specific transaction. This is encrypted with B’s public key (PUb​).

2. Challenge/Response: B decrypts the message and responds by sending A’s nonce (N1​) back, along with a new nonce (N2​) generated by B. This is encrypted with A’s public key (PUa​). The presence of N1​ assures A that the respondent is truly B.

3. Confirmation: A returns B's nonce (N2​), encrypted using B’s public key, to prove to B that the correspondent is indeed A.

4. Key Generation & Double Encryption: A selects a secret session key (Ks​) and sends it to B. To ensure security, it is encrypted twice:

   • Inner Layer (Authentication): Encrypted with A’s private key (PRa​). This acts as a digital signature; since only A has this key, it proves A sent it.

   • Outer Layer (Confidentiality): Encrypted with B’s public key (PUb​). This ensures that only B can open the message.

5. Recovery: B uses their own private key (PRb​) to remove the outer layer and A’s public key (PUa​) to remove the inner layer and recover the secret key (Ks​).

Public Key Distribution

• Public Announcement
• Public Directory
• Public-Key Authority

• Certificates (Safe)