readme.md

Chapter 8: Public key cryptography based on Discrete Logarithm Problem

This section requires knowledge of group theory before hand.

DLP: Discrete Logarithm Problem

• this is the one way function based on which many cryptography schemes are made including but not limited to the ones mentioned here.

Problem statment

• It's easy to compute β given ∝ and x, but computing the logarithm x = log∝(β) is the hard problem.

• DLP is based on group theory, the difficulty of the DLP is that you can't mathematically solve it, you need to examine all the possible numbers that can be generated by element ∝ while counting the steps needed to reach β which is x. so the security of DLP depends on the number of elements that can be generated from ∝, as minimum number required depends on the nature of the group.

• DLP is solved for groups using simple addition operation in mod m, it can be reduced to computing the inverse problem, as long as the chosen generator coprimes with m, we can solve it directly as

  x = ∝^-1 β mod m

Deffie-Hellman key exchange algorithm

• Deffie-Hellman is based on Group ℤ*_p

Attacks against Deffie Hellman

Generic Methods

Attack the generalized DLP not specific to certain groups

1 - Brute Force

• Apply the operation to ∝ repeatedly until β is reached, the number of iterations needed is x.
• Its complexity is 𝕆(ord(∝)), using a primitive element this is essentially 𝕆(|G|).
• So this attack fails if |G| is >= 2⁸⁰.

2 - Shank's method (Baby step Giant Step)

• A divide and Conquer approach Let m = √(|G|).
  we can define x as x = x_g m + x_b
  now the DLP can be written as
  ∝^x_b ≡ β ∝^{-m x_g}

1. Generate all possible values of x_b ∈ [0 .. m-1].
2. compute values of β ∝^{-m x_g} ∈ [0 .. m], for each value check if it exists in the generated values in previous step, and stop once found.

• Complexity = 𝕆(√|G|)
• to safeguard against this attack |G| should be >= 2¹⁶⁰.

3 - Pollard Rho Method

• Based on Brithday Paradox

• Randomly generate numbers of the form ∝ⁱβ^j given that β = ∝ ^x, then the previous form can be written as ∝ⁱβ^xj

• Wait until a collision is found, then
  ∝^{i₁ + x j₁} = ∝ ^{i₂ + x j₂}    mod |G|
  i₁ + x j₁ = i₂ + x j₂    mod φ(|G|)
  x = (i₂ - i₁ ). (j₁ - j₂)^-1    mod φ(|G|)

• It's the best known attack for elliptic curve cryptosystems.

• Complexity = 𝕆(√|G|).

• to safeguard against this attack |G| should be >= 2¹⁶⁰.

4 - Polhig Hellman method

• Based on chinease remainder method.

• Used as a preprocessing step for other methods to make them faster.

• It's a divide and Conquer algorithm, it defines |G| as
  |G| = p₁^e₁ p₂^e₂ p₃^e₃ p₄^e₄ ... p_n^e_n

• Use any of the above methods to solve DLP in smaller sub groups G(p_i^e_i).

• Then combine the results to compute x using chinease remainder method.

Non-Generic Algorithms

Attacks that are specific to certain groups or under certain conditions

Index Calculus Method

• It targets groups Z*_p and GF(2^m).
• It works in groups where large elements can be represented as a product of small elements.
• This is a very strong attack, but doesn't work on elliptic curve cryptosystems.
• to safeguard against this attack |G| should be >= 2¹⁰²⁴.

Security of DHKE

• Group size must be >= 2¹⁰²⁴ for DHKE to be secure
• IT'S NOT SECURE AGAINST ACTIVE ATTACKS like: replay, generating false messages, and message modification.

Elgammal Encryption scheme

The above is a simple representation of the algorithm, that uses DHKE to exchange the key, then encrypt the message with simple multiplication then.

The actual scheme is as follows:

• Since K _m is multiplied with x, it's called a Masking key.
• it's a probablisitic scheme, running the algorithm multiple times should have different result, depending on the chosen value for i, the private key of alice, which is changed every time a message is sent.
• The protocol is used to transfer messages in one direction, you need to have a different process for the other direction to send messages as well.
• This method needs to send double the amount of data since the K _E needs to be sent with y to the other side.
• Unlike DHKE, the parameters p and ∝ are generated by one of the two involved parties and not a trusted thrid party.