What is a public key?

/ / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, Introduction to public-key cryptography, Number theory for PKC – Euclidean Algorithm, Euler’s Phi Function and Euler’s Theorem

A public key is a fundamental concept in public-key cryptography, which is an essential branch of cybersecurity. Public-key cryptography, also known as asymmetric cryptography, involves the use of two distinct but mathematically related keys: a public key and a private key. These keys are used for encryption and decryption, as well as for digital signatures and verification processes. The public key is intended to be widely distributed and accessible, while the private key remains confidential to the owner.

The public key is used in various cryptographic protocols and algorithms, such as RSA (Rivest-Shamir-Adleman), ECC (Elliptic Curve Cryptography), and DSA (Digital Signature Algorithm). Its primary purpose is to enable secure communication and authentication over insecure channels, such as the internet. The security of public-key cryptography relies on the computational difficulty of certain mathematical problems, such as integer factorization and discrete logarithms.

Mathematical Foundations

To understand public keys, it is essential to consider the mathematical foundations that underpin public-key cryptography. Key concepts include the Euclidean Algorithm, Euler's Phi Function, and Euler's Theorem.

Euclidean Algorithm

The Euclidean Algorithm is a method for finding the greatest common divisor (GCD) of two integers. It is based on the principle that the GCD of two numbers also divides their difference. This algorithm is important for key generation in public-key cryptography, particularly in the RSA algorithm.

For two integers a and b where a > b, the Euclidean Algorithm proceeds as follows:

1. Compute the remainder r of a divided by b (i.e., a = bq + r, where q is the quotient and r is the remainder).
2. Replace a with b and b with r.
3. Repeat the process until r = 0. The non-zero remainder at this stage is the GCD of a and b.

Euler’s Phi Function

Euler's Phi Function, denoted as \phi(n), counts the number of integers up to n that are coprime with n. Two numbers are coprime if their GCD is 1. Euler's Phi Function is fundamental in the RSA algorithm for determining the totient of a product of two prime numbers.

For a prime number p, \phi(p) = p - 1. For two distinct prime numbers p and q, \phi(pq) = (p - 1)(q - 1).

Euler’s Theorem

Euler's Theorem states that for any integer a and n that are coprime, the following congruence holds:

    \[ a^{\phi(n)} \equiv 1 \ (\text{mod} \ n) \]

This theorem is a generalization of Fermat's Little Theorem and is instrumental in the RSA encryption and decryption processes. In RSA, Euler's Theorem is used to ensure that the encryption and decryption functions are inverses of each other.

Public-Key Cryptography Algorithms

RSA Algorithm

The RSA algorithm, named after its inventors Rivest, Shamir, and Adleman, is one of the most widely used public-key cryptosystems. It involves the following steps:

1. Key Generation:
– Choose two large prime numbers p and q.
– Compute n = pq.
– Compute \phi(n) = (p - 1)(q - 1).
– Choose an integer e such that 1 < e < \phi(n) and \text{GCD}(e, \phi(n)) = 1.
– Compute d as the modular multiplicative inverse of e modulo \phi(n), i.e., de \equiv 1 \ (\text{mod} \ \phi(n)).

The public key is (n, e), and the private key is (n, d).

2. Encryption:
– Given a plaintext message M, convert it to an integer m such that 0 \leq m < n.
– Compute the ciphertext c using the public key: c = m^e \ (\text{mod} \ n).

3. Decryption:
– Compute the plaintext message m using the private key: m = c^d \ (\text{mod} \ n).
– Convert the integer m back to the original message M.

Elliptic Curve Cryptography (ECC)

Elliptic Curve Cryptography (ECC) is based on the algebraic structure of elliptic curves over finite fields. ECC offers comparable security to RSA but with smaller key sizes, making it more efficient in terms of computation and storage.

In ECC, the public key is a point on the elliptic curve, and the private key is a randomly chosen integer. The security of ECC relies on the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP).

Digital Signature Algorithm (DSA)

The Digital Signature Algorithm (DSA) is used for digital signatures, ensuring the authenticity and integrity of a message. It involves the following steps:

1. Key Generation:
– Choose a prime number p.
– Choose a prime divisor q of p - 1.
– Choose a generator g of the subgroup of order q in the multiplicative group of integers modulo p.
– Choose a private key x such that 0 < x < q.
– Compute the public key y = g^x \ (\text{mod} \ p).

2. Signature Generation:
– Compute a hash of the message H(M).
– Choose a random integer k such that 0 < k < q.
– Compute r = (g^k \ (\text{mod} \ p)) \ (\text{mod} \ q).
– Compute s = (k^{-1}(H(M) + xr)) \ (\text{mod} \ q).
– The signature is (r, s).

3. Signature Verification:
– Compute w = s^{-1} \ (\text{mod} \ q).
– Compute u_1 = (H(M)w) \ (\text{mod} \ q) and u_2 = (rw) \ (\text{mod} \ q).
– Compute v = ((g^{u_1} y^{u_2}) \ (\text{mod} \ p)) \ (\text{mod} \ q).
– The signature is valid if v = r.

Practical Applications

Public keys are used in various practical applications, including:

1. Secure Communication:
– Public keys enable secure communication over the internet through protocols such as SSL/TLS. In these protocols, public keys are used to establish encrypted connections between clients and servers.

2. Digital Signatures:
– Public keys are used to verify digital signatures, ensuring the authenticity and integrity of electronic documents and messages. This is important in legal, financial, and governmental transactions.

3. Key Exchange:
– Public keys facilitate secure key exchange protocols, such as Diffie-Hellman, allowing parties to securely agree on a shared secret key for symmetric encryption.

4. Cryptographic Authentication:
– Public keys are used in authentication protocols, such as SSH (Secure Shell) and digital certificates, to verify the identity of users and devices.

Example of RSA Key Generation

To illustrate the RSA key generation process, consider the following example:

1. Choose two large prime numbers p = 61 and q = 53.
2. Compute n = pq = 61 \times 53 = 3233.
3. Compute \phi(n) = (p - 1)(q - 1) = 60 \times 52 = 3120.
4. Choose e = 17, which is coprime with 3120.
5. Compute d such that de \equiv 1 \ (\text{mod} \ 3120). Using the Extended Euclidean Algorithm, we find d = 2753.

The public key is (n, e) = (3233, 17), and the private key is (n, d) = (3233, 2753).

Example of RSA Encryption and Decryption

Given the public key (3233, 17) and a plaintext message M = 42:

1. Convert M to an integer m = 42.
2. Compute the ciphertext c = 42^{17} \ (\text{mod} \ 3233) = 2557.

To decrypt the ciphertext c = 2557 using the private key (3233, 2753):

1. Compute the plaintext message m = 2557^{2753} \ (\text{mod} \ 3233) = 42.
2. Convert the integer m = 42 back to the original message M = 42.

This example demonstrates the use of public and private keys in the RSA algorithm for secure communication.

Other recent questions and answers regarding Number theory for PKC – Euclidean Algorithm, Euler’s Phi Function and Euler’s Theorem:

View more questions and answers in Number theory for PKC – Euclidean Algorithm, Euler’s Phi Function and Euler’s Theorem

More questions and answers:

Tagged under: , , , , ,