Problem 8 - An Introduction to Mathematical Cryptography

Question

Alice and Bob agree to use the prime \(p=1373\) and the base \(g=2\) for communications using the ElGamal public key cryptosystem. (a) Alice chooses \(a=947\) as her private key. What is the value of her public key \(A\) ? (b) Bob chooses \(b=716\) as his private key, so his public key is $$ B \equiv 2^{716} \equiv 469(\bmod 1373) $$ Alice encrypts the message \(m=583\) using the ephemeral key \(k=877\). What is the ciphertext \(\left(c_{1}, c_{2}\right)\) that Alice sends to Bob? (c) Alice decides to choose a new private key \(a=299\) with associated public key \(A \equiv 2^{299} \equiv 34(\bmod 1373)\). Bob encrypts a message using Alice's public key and sends her the ciphertext \(\left(c_{1}, c_{2}\right)=(661,1325)\). Decrypt the message. (d) Now Bob chooses a new private key and publishes the associated public key \(B=\) 893. Alice encrypts a message using this public key and sends the ciphertext \(\left(c_{1}, c_{2}\right)=(693,793)\) to Bob. Eve intercepts the transmission. Help Eve by solving the discrete logarithm problem \(2^{b} \equiv 893(\bmod 1373)\) and using the value of \(b\) to decrypt the message.

Step-by-Step Solution

Answer

(a) 229 (b) (774, 351) (c) 900 (d) 75

Step 1: Calculate Alice's Public Key (a)

Alice's public key \( A \) is calculated as \( A = g^a \mod p \). Given \( g = 2 \), \( a = 947 \), and \( p = 1373 \), we calculate:\[ A = 2^{947} \mod 1373 \]Using modular exponentiation, we find \( A = 229 \).

Step 2: Encrypt the Message with Alice's Public Key (b)

The ciphertext components are given by:1. \( c_1 = g^k \mod p \)2. \( c_2 = m \times B^k \mod p \)for ephemeral key \( k = 877 \), message \( m = 583 \), Bob's public key \( B = 469 \). So,\[ c_1 = 2^{877} \mod 1373 = 774 \]\[ c_2 = (583 \times 469^{877}) \mod 1373 \]Using modular arithmetic and calculations, we find \( c_2 = 351 \).The ciphertext is \((c_1, c_2) = (774, 351)\).

Step 3: Decrypt Bob's Encrypted Message (c)

Given \( c_1 = 661 \), \( c_2 = 1325 \), and Alice's new private key \( a = 299 \):1. Calculate \( s = c_1^a \mod p = 661^{299} \mod 1373 \).2. Use \( s \) to recover the message: \[ m = c_2 \times s^{-1} \mod p \]where \( s^{-1} \) is the modular inverse of \( s \).By calculation,\[ s = 144 \]\[ s^{-1} = 1190 \]\[ m = 1325 \times 1190 \mod 1373 = 900 \]The decrypted message is 900.

Step 4: Solve the Discrete Logarithm Problem (d)

Find \( b \) such that \( 2^b \equiv 893 \mod 1373 \). This involves calculating the discrete logarithm:Using trial methods or logarithm-solving tools, \( b \approx 1107 \) (discrete logarithm of 893).

Step 5: Decrypt the Ciphertext using Bob's New Private Key (d)

Bob received \((c_1, c_2) = (693, 793)\). Using found \( b = 1107 \):1. Calculate \( s = c_1^b \mod p = 693^{1107} \mod 1373 \).2. \[ m = c_2 \times s^{-1} \mod p \]By evaluating:\[ s = 488 \]\[ s^{-1} = 885 \]\[ m = 793 \times 885 \mod 1373 = 75 \]The decrypted message is 75.

Key Concepts

Modular Arithmetic

Modular arithmetic is a fundamental concept in cryptography and many areas of mathematics and computer science. It involves integers and a special kind of division that gives the remainder in the calculation. This concept is akin to the clock system where times wrap around after reaching a certain point, like 12 hours. For example, in modulo 12 arithmetic, 14 becomes 2 because after hitting 12, we start again from 0.

In the context of the ElGamal cryptosystem, modular arithmetic plays a crucial role. When Alice or Bob calculate powers like \(2^{947} \mod 1373\), they are using modular arithmetic to obtain results within a limited range. This prevents numbers from becoming too large for practical computations. By using modular arithmetic, calculations become feasible even with large exponents such as those seen in public key encryption.

Modular arithmetic allows the system to maintain secrecy while enabling efficient computations that are essential for cryptographic applications. This method ensures that despite the complexity and size of calculations in encryption processes, operations remain manageable and secure.

Public Key Encryption

Public key encryption is a security system used to protect sensitive data by allowing encryption to be executed using a public key, while decryption requires a private key. In a typical scenario, one party (say, Alice) publishes her public key for others to use and keeps the private key secret. This type of system is foundational in secure communications.

In ElGamal cryptography, a public key is derived from a chosen private key and some agreed-upon parameters, such as a base and a prime number. For example, if Alice chooses a private key \(a\), her public key is computed as \(A = g^a \mod p\), where \(g\) and \(p\) are publicly known. This means that Alice can share \(A\) with Bob, allowing him to encrypt messages for her without Alice having to expose her private key \(a\).

Public key encryption is vital because it allows secure communication without needing a prior secure exchange of secret keys. This way, even if an interceptor sees the public communications, they cannot easily deduce the private information needed to decrypt messages.

Discrete Logarithm Problem

The discrete logarithm problem is a critical concept underpinning the security of many cryptographic systems, including the ElGamal cryptosystem. It involves finding a power \(b\) such that a number \(g^b\) equals another number under modulus \(p\). Put simply, given a number \(y = g^b \mod p\), finding \(b\) is the discrete logarithm problem.

The difficulty in solving this problem makes it a secure foundation for cryptographic protocols. In the provided exercise, to help Eve, we solve for \(b\) in \(2^b \equiv 893 \mod 1373\). This challenge, under the mod of a large prime number, is computationally challenging and forms the backbone of the security by making the reverse calculation hard without substantial computation power.

The challenge and security arise because, while computing \(g^b \mod p\) is feasible with modern computers, reversing the process to find \(b\) without specific techniques or immense computation is considered infeasible. This is why the discrete logarithm problem stands as a robust means of securing cryptosystems like ElGamal.