Problem 6 - An Introduction to Mathematical Cryptography

Question

Alice and Bob agree to use the prime \(p=1373\) and the base \(g=2\) for a Diffie- Hellman key exchange. Alice sends Bob the value \(A=974\). Bob asks your assistance, so you tell him to use the secret exponent \(b=871\). What value \(B\) should Bob send to Alice, and what is their secret shared value? Can you figure out Alice's secret exponent?

Step-by-Step Solution

Answer

Bob sends 642 to Alice. Their shared secret is 1177; Alice's secret exponent is not feasible to determine.

Step 1: Calculate Bob's Public Value

To find the value that Bob should send to Alice, calculate \(B = g^b \mod p\). Here, \(g = 2\), \(b = 871\), and \(p = 1373\). Start by computing \(2^{871} \mod 1373\). This can be efficiently done using the method of exponentiation by squaring or a calculator that handles modular arithmetic. After calculating, we find that \(B = 642\).

Step 2: Compute the Shared Secret

Bob will use Alice's public value to find the shared secret. Compute the shared secret using \(s = A^b \mod p\), where \(A = 974\), \(b = 871\), and \(p = 1373\). Again, use modular exponentiation: calculate \(974^{871} \mod 1373\). After calculation, the shared secret \(s = 1177\).

Step 3: Attempt to Determine Alice's Secret Exponent

Alice's public value \(A = g^a \mod p\) is 974, so \(2^a \equiv 974 \mod 1373\). To find Alice's secret exponent \(a\), one would generally need to perform a discrete logarithm, which is computationally infeasible for large numbers like these using elementary methods. Without more sophisticated number-theoretic tools, calculating \(a\) directly is impractical.

Key Concepts

Modular Arithmetic

Modular arithmetic is like the clock arithmetic you might use in everyday life. It focuses on what the remainder is when you divide by a number, known as the modulus. For example, in a 12-hour clock, 13 o'clock is the same as 1 o'clock; similarly, in modular arithmetic, 13 mod 12 equals 1. This concept helps in simplifying calculations, especially with large numbers.
In the context of the Diffie-Hellman key exchange, modular arithmetic allows two parties to agree on a shared secret without transmitting the secret itself. They use a public prime number, like the 1373 in our exercise, to act as the modulus.

• This ensures that all calculations "wrap around" after they reach 1373, making results more manageable and adding a layer of security.
• Calculations like these prevent eavesdroppers from easily deducing the secret shared value.

Modular arithmetic is crucial for operations involved in encryption systems, ensuring that even when numbers get very large, they can be reduced to a small, manageable size.

Exponentiation by Squaring

Exponentiation by squaring is an efficient method for computing large powers of numbers, which is particularly useful in situations where you also apply modular arithmetic. Normally, calculating something like \(2^{871}\) would be computationally overwhelming, but exponentiation by squaring simplifies the process.
This technique breaks down the exponentiation into a series of squaring and multiplication steps, effectively reducing the number of calculations to its logarithmic counterpart.

• For example, instead of multiplying 2 by itself 871 times, it handles powers as 2^2, 2^4, 2^8, etc.
• This method significantly speeds up calculations, especially when combined with modular reduction at each step.

The combination of squaring and modular reduction after every step ensures that the numbers remain manageable, preventing overflow errors in computation and maintaining efficiency even on computers with less processing power.

Discrete Logarithm Problem

The discrete logarithm problem is a cornerstone of modern cryptography because it is computationally challenging to solve, especially with large numbers. In simple terms, given \(g^a \equiv A \mod p\), the goal is to find the exponent \(a\).
Unlike ordinary logarithms, where we can easily find \(x\) if we know \(b^x = y\), discrete logarithms offer no straightforward way to recover \(a\) from \(g^a\).

• In the earlier step of the exercise, calculating Alice's secret exponent would involve finding \(a\) such that \(2^a \equiv 974 \mod 1373\).
• This task is similar to finding a needle in a haystack when numbers are large and random enough.

This intrinsic difficulty makes cryptographic protocols like Diffie-Hellman secure; even if an attacker knows \(g\), \(p\), and \(A\), calculating \(a\) is almost impossible without significant computational resources. The impracticality of solving the discrete logarithm problem is what underpins the security of the communication.