Public Key Cryptography and Prime Number
Posted on March 27, 2022 — 3 Minutes Read
One needs not to be an expert in modern cryptography to know that at its core lies the number theory, and in which, prime numbers specifically. Being a natural number that is not a product of any two other, prime number can only be factorised as a product of itself, and for a number that is a product of two large primes, while the multiplication is rather effortless for a machine, the factorisation requires nonetheless more time or processing power for mainstream, non-quantum computer to perform than the time the answers would remain valuable. This distinctive quality is the bedrock of the RSA algorithm described by Ron Rivest, Adi Shamir and Leonard Adleman in 1977, a year after the seminal paper titled New Directions in Cryptography, by Whitfield Diffie and Martin Hellman which proposed a type of key exchange, aptly named Diffie-Hellman (DH) key exchange today, and founded the asymmetric public-private key cryptosystem. While allowing a shared secret to be securely communicated over an insecure network, by permitting the parties involved to openly transmit an agreed public key, a prime number and the associating fixed primitive element, with which the parties could then proceed to compute independently and non-interactively, a shared secret by applying their private keys on the openly-transmitted values, that would otherwise be difficult if not impossible to calculate; the DH key exchange left open a question for devising a one-way or so-called trapdoor function, to which the RSA algorithm answered.
Making use of the difficulty of prime factorisation of large number and the relative ease of their multiplication, the RSA algorithms encrypts a message with the trusted public key of the recipient which is based on a product of two large primes. Such an encrypted message may only be decrypted with ease with either the private key associated with the public key used in the encryption, which is nonetheless known only to the intended recipient, or the two prime numbers that constitute the well-known public key, which given two large enough primes e.g. of 2,048 bits in RSA-4096, would require more time or processing power to compute for mainstream, non-quantum apparatus than the time the primes would remain valid and valuable, or the time that the secure channel would remain in force, which is relatively short considering that it is often established to exchange a symmetric secret for bulk and rapid data encryption and decryption. RSA also describes the process in which the sender may attach a digital signature, generated in a similar fashion using its own private key, with the encrypted message, for the recipient to verify using the public key of the sender, that the attached signature was indeed generated using the associated private key known only to the sender, and may as such trust that the encrypted message to which the signature is attached has not been tampered with.
Notwithstanding the numerous enhancements and developments throughout the years, together, the DH key exchange and the RSA algorithms are at the heart of Transport Layer Security (TLS), the state-of-the-art cryptographic protocol that is widely used in applications that transmit data securely over IP networks e.g. HTTPS, email, instant messaging, voice over IP (VoIP) and video conferencing etc., and that at the core of it all are the peculiar primes.