>/posts/learn with me - public-key cryptography $

cd ..

Estimated reading time: 16 minutes

The Discrete Logarithm Problem

Now that you understand modular arithmetic, we can move on to its applications. In the previous post, we discussed how to perform modular computations. Now, it's time to learn how these computations are used in cryptography. Calculating the remainder in an equation like this might be easy:

$$ 5^{13}\bmod{17} = 3 $$

However, finding the exponent in an equation like the following is much more challenging:

$$ 5^{x}\bmod{17} = 7 $$

For small values of \( p \), like \( 17 \), an iterative approach might work, but for 2048-bit long prime numbers, it would take an impractical amount of time and computing power to obtain the answer. Try finding the value of \( x \) in the equation above. For larger values of \( p \), you might consider using the Baby-step giant-step algorithm. However, even this algorithm struggles significantly with very large values.

So, what's the hardest part of this problem? You can think of it as similar to mixing water and salt. Creating a saline solution with an exact ratio is easy, but extracting the salt from the water is much harder, even if it's possible.

With that understanding, let's move on to some practical applications.

RSA Algorithm

The security of this algorithm is based on the difficulty of the discrete logarithm problem and the size of the private key. In this case study, we will consider two scenarios: sending an encrypted message to someone, knowing their public key, and decrypting a message we have received.

Encryption

For simplicity, let's say we want to send a single letter 'A'. The encryption process itself isn't too complicated. The exact encryption formula looks like this:

$$ Ct = Pt^{e}\bmod{n} $$

Where \( e \) is the public exponent and \( n \) is the public modulus. In our example, \( e = 7 \) and \( n = 187 \). Most common used public exponent is \(e = 65537\).

But wait, \( n \) is not a prime number.

Exactly! And that's the key to asymmetric encryption. However, to obtain the private key, you need to find the modular inverse of \( e \) with respect to \( \varphi(n) \), where \( \varphi \) is Euler’s Totient Function.

When \( p \) is a prime number, \( \varphi(p) = p-1 \) since all numbers less than \( p \) are coprime to it. Therefore, \( \varphi(n) = (p-1) \times (q-1) \), where \( p \) and \( q \) should be large prime numbers. In our case, we use a small \( n \) for simplicity, but even with this, the calculations won't be trivial.

Here’s the full formula that must be satisfied for the encryption and decryption process:

$$ (M^{e})^{x}(\bmod{n}) = M $$

As mentioned earlier, \( e \) and \( n \) are public, and knowing them, you shouldn't be able to find \( x \) easily. By "easily," I mean that it shouldn't be possible within a reasonable time frame, which is why large primes are required. To demonstrate why this is necessary, we'll attempt to break an encryption scheme using non-prime numbers, small primes, and other cases. But first, let’s see how the entire process generally works.

Let’s move to the calculations. The plaintext is 65 because this number represents 'A' in the ASCII table.

$$ Ct = 65^{7}\bmod{187} $$ $$ Ct = 4902227890625\bmod{187} $$ $$ Ct = 142 $$

Our encrypted message is 142. If we needed to decrypt it without knowing the private key, we would need to satisfy the following equation:

$$ (142^{7})^{x}\bmod{187} = 142 $$

At first glance, this doesn’t seem too difficult. Due to Fermat’s Little Theorem:

$$ a^{p}\bmod{p} = a $$

Simple, right? Just find \( x \) such that \( 7 \times x = 187 \). Unfortunately, 187 cannot be evenly divided by 7, so our plan doesn't work. There must be another way. Indeed, we would need to iterate through all integers such that \( 7 \times x < 187 \). This might seem feasible for now, as \( 187/7 = 26.71 \), meaning there are at most 26 possible values for \( x \). We’ll try to find the exact value in a moment. But even though this method might seem manageable now, don't even think of applying it to numbers like \( 2^{2048} \approx 10^{616} \), which are typical key values.

Ok so:

require 'openssl'

resultsHash = Hash.new(0)

for i in 1..26 do
   result = 142.to_bn.mod_exp((i*7), 187)
   resultsHash[result] += 1
end

puts resultsHash

resultsHash.keys.each {|key| puts "#{key.to_i}: #{resultsHash[key]}" }

65: 2
111: 2
109: 2
166: 2
131: 2
100: 2
142: 2
67: 2
54: 2
144: 2
10: 1
89: 1
175: 1
155: 1
164: 1
1: 1

Wait are those results are repeating even tho range of exponent is smaller than module? Yes, we expected to number 142 appear once there and beeing answer for the x we are looking for. And this is another problem, even if it's "correct" for this specific value it won't works with others. For now number 7 as x looks ok, but check it on whole alphabet.

for i in 'A'..'Z' do
   result = i.ord.to_bn.mod_exp((7*7), 187)
   puts "i: #{i}, result: #{result}(#{result.to_i.chr})"
end

i: A, result: 65(A)
i: B, result: 66(B)
i: C, result: 67(C)
i: D, result: 17(◄)
i: E, result: 103(g)
i: F, result: 36($)
i: G, result: 20(¶)
i: H, result: 123({)
i: I, result: 107(k)
i: J, result: 40(()
i: K, result: 126(~)
i: L, result: 76(L)
i: M, result: 77(M)
i: N, result: 78(N)
i: O, result: 28(∟)
i: P, result: 114(r)
i: Q, result: 47(/)
i: R, result: 31(▼)
i: S, result: 134(�)
i: T, result: 118(v)
i: U, result: 51(3)
i: V, result: 137(�)
i: W, result: 87(W)
i: X, result: 88(X)
i: Y, result: 89(Y)
i: Z, result: 39(')

Some of the results are correct, while others are not. About 35% of them are accurate, which isn't too bad—you might even be able to read some words with text that has 35% correctness. However, this approach won't work with large numbers, and it's not what we're looking for. We need to step back and examine the math more closely.

According to Euler's Theorem and the properties of modular arithmetic:

$$ M^{\varphi(n)} \equiv 1 \pmod{n} $$

Therefore:

$$ M^{\varphi(n) + 1} \equiv M \pmod{n} $$

If we multiply both sides by \( M^{\varphi(n)} \), we get:

$$ M^{2\varphi(n) + 1} \equiv M^{\varphi(n) + 1} \pmod{n} $$

And by generalizing this, we have:

$$ M^{k\varphi(n) + 1} \equiv M \pmod{n} $$

Decryption

So, to proceed, we need to find \( \varphi(n) \). To do this, we have to factorize \( n \). Since we know that \( n \) was computed using two prime numbers, the equation looks like this: \( \varphi(n) = (p-1) \times (q-1) \).

If you don't find any divisors in the range from 1 to \( \sqrt{n} \), it's certain that larger numbers won't divide \( n \) either. Knowing this, we can write a code snippet like the one below:

def find_divisors(n)
  divisors = []

  (1..Math.sqrt(n).to_i).each do |i|
    if n % i == 0
      divisors << i
      divisors << n / i if i != n / i
    end
  end

  divisors.sort
end

n = 187
puts "Divisors of #{n}: #{find_divisors(n).join(', ')}"

Divisors of 187: 1, 11, 17, 187

Now we know that \( p = 11 \) and \( q = 17 \). That's essentially all we need to recover the original message. However, this example is based on small numbers. It's important to note that \( \sqrt{10^{616}} \) is still \( 10^{308} \). Therefore, iterating through all numbers up to a value with 308 zeros is not a feasible approach.

Are you curious how to revert to the original message value from the number \(142\)? Let's calculate \( \varphi(n) = (11-1)(17-1) = 160 \).

To satisfy the equation \( (M^{e})^{x} \bmod{n} = M \), we already have \( M^e \bmod{187} \), which is \(142\). So the last part is to find \( x \) such that:

$$ 7 \times x \equiv 1 \pmod{160} $$

We use the number \(7\) because it's the public exponent, which is \( e \) in the previous equation. The \( x \) we are looking for is \( 23 \).

Let's check our calculation:

for i in 'A'..'Z' do
   result = i.ord.to_bn.mod_exp((7*23), 187)
   puts "i: #{i}, result: #{result}(#{result.to_i.chr})"
end

i: A, result: 65(A)
i: B, result: 66(B)
i: C, result: 67(C)
i: D, result: 68(D)
i: E, result: 69(E)
i: F, result: 70(F)
i: G, result: 71(G)
i: H, result: 72(H)
i: I, result: 73(I)
i: J, result: 74(J)
i: K, result: 75(K)
i: L, result: 76(L)
i: M, result: 77(M)
i: N, result: 78(N)
i: O, result: 79(O)
i: P, result: 80(P)
i: Q, result: 81(Q)
i: R, result: 82(R)
i: S, result: 83(S)
i: T, result: 84(T)
i: U, result: 85(U)
i: V, result: 86(V)
i: W, result: 87(W)
i: X, result: 88(X)
i: Y, result: 89(Y)
i: Z, result: 90(Z)

Indeed, \(23\) is the correct value for the private key. In this example, we were able to compute everything using basic math, but even in a simplified case with small primes (both less than 20) and a small public exponent, we ended up with values like \(4902227890625\). Now, imagine the security level of the same encryption algorithm with keys as large as \(2^{2048}\). In future posts, we will discuss several different attacks on this encryption method, but first, let's get familiar with the next public key algorithm, the Diffie–Hellman key exchange.

Diffie-Hellman Key Exchange

The Diffie-Hellman key exchange is an algorithm for establishing a secure communication channel between two parties, even if a third party is eavesdropping on the communication. This algorithm ensures that the eavesdropper cannot obtain either party's private key. The Diffie-Hellman algorithm is based on the same mathematical problem as RSA, but it includes additional steps that result in both users having different private keys.

The Example

As in every cryptography example, we will discuss the communication between Alice and Bob.

  • First step: Both parties agree on some arbitrary public values that will be used in the subsequent steps. These values can be known to everyone. For instance, let's choose \( p = 23 \) and \( q = 5 \).

  • Second step: Both Alice and Bob choose their private (secret) keys. For example, Alice chooses 4, and Bob chooses 3.

  • Next, they calculate their public keys using the formula:

$$ \text{pub_key} = q^{\text{priv_key}} \bmod{p}$$

For Alice:

$$ A = 5^4 \bmod{23} = 4 $$

For Bob:

$$ B = 5^3 \bmod{23} = 10 $$

  • Then, they share their public keys and calculate their shared secret key:

$$ s = \text{pub_key}^{\text{priv_key}} \bmod{p} $$

For Alice:

$$ s = 10^4 \bmod{23} = 18 $$

For Bob:

$$ s = 4^3 \bmod{23} = 18 $$

As you can see, both parties now have the same shared secret key, which they can use to decrypt their messages. This is based on the mathematical principle:

$$ (g^a \bmod{p})^b \bmod{p} = (g^b \bmod{p})^a \bmod{p} $$

Now, both Alice and Bob can use their shared secret as a key for a symmetric algorithm, such as AES, to encrypt and decrypt their messages. However, an eavesdropping user will not be able to decrypt these messages, as they do not possess the shared secret key.