Asymmetric key cryptography

Introduction

In this lesson we will look at asymmetric key cryptography which forms the basis of many secure network interactions today.

By the end of the lesson we will have covered:

• What asymmetric key cryptography is
• Usage of asymmetric key cryptography, including key exchange and digital signatures
• Security of asymmetric key cryptography in general
• Further details on RSA, DSA & Elliptic Curves algorithms and security
• Some Python code examples showing how the algorithms work in practice
• Threats to these algorithms from both classical and quantum computers

Introduction to asymmetric key cryptography

As we learned in the last lesson, symmetric key cryptography is very fast and efficient for protecting information, but it has a few limitations:

1. As the number of parties wishing to exchange secure information increases, the numbers of keys required grows combinatorially. It provides no mechanism to securely distribute these keys between senders and receivers.
2. There is no provision for non-repudiation. Any party is able to decrypt, or encrypt, messages with no way to guarantee a message was received or where it originated

The solution to both these problems is provided by asymmetric key cryptography (AKC), also known as public key cryptography (PKC), which therefore forms a cornerstone of modern digital security.

Asymmetric key cryptography (AKC) involves the use of a pair of keys – one public, one private. The public and private keys are cryptographically linked and typically generated at the same time as a key pair using a specialized mathematical algorithm. The public key, as suggested by its name, is then meant to be freely distributed, while the private key is kept secret by the party generating the key pair. Security of communications employing asymmetric key pairs is assured as long as the private key remains confidential.

Figure 1. Asymmetric Key Encryption

AKC offers several useful functions, such as:

1. Encryption and decryption to enable confidentiality of communications.
2. Digital signatures to ensure authenticity, integrity, and non-repudiation.
3. Secure key exchange to facilitate subsequent use of symmetric cryptosystems.

In modern applications, AKC is primarily used for digital signatures and secure key exchange. In this lesson, we introduce these two key functions, and then we discuss several variations of cryptographic protocols for these functions.

Key exchange with asymmetric key cryptography

One of the fundamental problems in cryptography is securely exchanging keys. For example, if two parties want to use symmetric encryption, both parties need the same key to encrypt and decrypt messages. But how do they securely exchange the key? Asymmetric key cryptography addresses this through interactive and non-interactive key exchange mechanisms.

Interactive key exchange

An interactive key exchange protocol refers to a method where two parties collaborate to create a shared secret key over an insecure communication channel. This shared secret key can then be used for symmetric encryption and decryption tasks.

The most well known among such protocols is the Diffie-Hellman algorithm (DH), which was devised specifically to facilitate key exchange. In this protocol, each party generates a pair of keys (public and private) and broadcasts their public key. Then each party uses their own private key and the other party's public key to generate a shared secret key. DH employs the principles of modular arithmetic to ensure both parties end up with the same shared secret even though each party has access only to the other party's public key.

Modern cryptosystems based on elliptic curve cryptography (ECC) extend this concept with the elliptic curve Diffie-Hellman) (ECDH) key exchange. ECDH works similarly to DH but utilizes the properties of elliptic curves, resulting in a more secure and efficient system.

Figure 2. Key Exchange Protocol

Non-interactive key exchange

Unlike key exchange protocols like DH and ECDH, which are interactive, requiring back-and-forth communication to decide the symmetric key, AKC also provides for non-interactive ways to establish a shared secret key. In such schemes, one party generates a pair of keys (public and private) and shares the public key with the other party. This second party then generates a random symmetric key, encrypts it with the received public key, and sends it back to the first party. The first party uses their private key to decrypt the received message, thereby obtaining the shared symmetric key. This scheme is non-interactive in that the symmetric key is determined by one party and simply communicated securely to the other party in encrypted form.

An important consideration in non-interactive key exchange has to do with the length differential in bits between the symmetric key the parties wish to exchange and recommended message sizes in AKC. Typically, modern symmetric keys are in the range of 128-256 bits long, while asymmetric key cryptosystems such as RSA work with message sizes around 1024-4096 bits long. Therefore, when using AKC to transmit a symmetric key, for security it must nevertheless be encoded into a longer 1024-4096 bit message. This can be achieved via two approaches:

• Padding-based key exchange: In this approach, the shorter (128-256 bit) symmetric key is generated first and then an agreed-upon reversible padding scheme such as OAEP is used to embed it into a longer (1024-4096 bit) message. This longer message is encrypted using AKC and broadcasted as ciphertext. The recipient first decrypts the ciphertext and then removes the padding to extract the shorter symmetric key.

• Key encapsulation mechanisms (KEMs): With KEM-based key exchange, a random, long (1024-4096 bit) plain text message is first generated, from which a shorter (128-256 bit) symmetric key can be extracted using an agreed-upon key derivation function (KDF). The longer plain text is encrypted using AKC and broadcasted to the recipient as ciphertext. The recipient decodes the ciphertext using their private key and then uses the KDF to extract the shorter (128-256 bit) symmetric key. Popular cryptosystems such as RSA, with their ability to directly encrypt data, can be used to implement KEMs.

Figure 3. Key Encapsulation Mechanism

Digital signatures with asymmetric key cryptography

Digital signatures are another powerful application of asymmetric key cryptography. They provide authentication, integrity, and nonrepudiation enabled by the fact that within AKC, entities possess unique private keys. The basic idea underlying signature protocols is that senders of secure messages will additionally digitally sign the messages using their unique private key. The receiver will then verify the digital signature using the public key of the sender. Within AKC, digital signatures can be implemented by using algorithms specifically designed for that purpose or by using generic cryptosystems.

Figure 4. Digital signatures with asymmetric key cryptography

Dedicated digital signature algorithms

Currently, the US Federal Information Processing Standard (FIPS) for digital signatures is a dedicated scheme simply titled the Digital Signature Algorithm (DSA). Somewhat similarly to the Diffie-Hellman protocol, the DSA uses the algebraic properties of the modular exponential and multiplicative inverses for signature generation and verification.

The elliptic curve digital signature algorithm (ECDSA) is an ECC variant of DSA, providing the same functionality but with significantly shorter keys. This results in improved efficiency, making it a popular choice for systems with resource constraints.

Both DSA and ECDSA will be illustrated in more detail later.

Digital signature schemes using generic cryptosystems

In addition to dedicated algorithms, digital signatures can also be generated using generic asymmetric cryptosystems, such as RSA.

RSA, which will be discussed in detail in a later section, also exploits modular multiplicative inverses and modular exponentiation as fundamental operations but combines them in a different sequence than DSA. In RSA, the signer typically creates a hash of the message and then encrypts the hash with their private key, creating the digital signature. Any party can then verify this signature by decrypting it with the signer's public key and comparing it with the hashed message.

Applications of asymmetric key cryptography

Asymmetric key cryptography is ubiquitous in modern digital technology applications. The basic functionalities of AKC described above form the building blocks of many higher-level application protocols, including:

1. Internet communication: Secure communication over the internet, such as HTTPS, relies heavily on asymmetric key cryptography. The Transport Layer Security (TLS) and its predecessor, Secure Sockets Layer (SSL), use asymmetric key cryptography during the initial handshake process to establish a symmetric key, which is then used for the rest of the communication session.

2. Authentication: Asymmetric key cryptography is used to create digital signatures, allowing an entity to authenticate a digital document or message as coming from a specific sender. This is used in many scenarios, from verifying software updates to legally binding digital contracts.

3. Email encryption: Email encryption protocols such as PGP (Pretty Good Privacy) and its open-source alternative GPG (GNU Privacy Guard) use asymmetric key cryptography to ensure that only the intended recipient can read the email content.

4. Secure shell (SSH): SSH is a protocol for secure remote login and other secure network services over an insecure network. It uses asymmetric key cryptography to authenticate the server to the client and, optionally, the client to the server.

5. VPN (virtual private network): Asymmetric key encryption is used to establish secure connections in VPNs, ensuring secure communication over public networks.

6. Blockchain and cryptocurrencies: Blockchain technologies, including Bitcoin and Ethereum, use asymmetric key cryptography. For example, the ownership of Bitcoin is established through digital signatures using asymmetric key cryptography.

7. Certificate authorities: Asymmetric key cryptography is used by certificate authorities (CAs) to issue and sign digital certificates, which are used in TLS communication, code signing, email encryption, and more. A digital certificate binds a public key to a specific entity (for example, a person or server).

Figure 5. Issuing and signing digital certificates using asymmetric key cryptography

Security of asymmetric key cryptography

Several cryptographic notions come together to enable secure asymmetric key cryptography, including:

Private key secrecy: The most basic security requirement of AKC is that the private key remains secret. However, since the private key must be mathematically linked to the public key, private key secrecy also requires that it be computationally infeasible to derive the private key from knowledge of the public key. Key generation schemes within AKC rely on computationally hard mathematical problems to facilitate this requirement.

Trapdoor functionality In AKC, the encryption and decryption operations involve different complementary keys from a single-key pair. Ciphertext generated by encryption using one of the keys (for example the public key) must be inscrutable to third parties while being easily decryptable by the holder of the complementary key (in this case the private key). In other words, encryption should resemble a trapdoor one-way function such that third parties cannot invert the operation and recover the plain text but the private key provides a secret trapdoor that enables easy inversion. Popular AKC algorithms use modular exponentiation to set up trapdoor one-way function behavior.

Randomness: The key generation process should also exploit randomness to ensure that keys are unpredictable, as any pattern or predictability in key generation could be exploited by an attacker. Randomness is also used for padding during encryption to generate semantically secure ciphertexts and within digital signature schemes to produce unique signatures even when the same message is signed multiple times. For this reason, the use of strong random number generators is an important part of AKC.

Large key size: As in the case of SKC, large key sizes ensure protection against brute force attacks. However, since large key sizes also increase the computational cost of the encryption and decryption process, an optimal solution needs to balance security and efficiency considerations. The following table shows typical key sizes for various asymmetric key cryptography protocols and applications:

Public key infrastructure: In AKC, the private keys must be kept secret by the owners while the public keys are shared. There needs to be a secure mechanism to manage and distribute these public keys between users. Public key infrastructure (PKI) provides a way to do this using digital certificates. A digital certificate provides proof of identity of the owner of the public key and is issued by a trusted authority like a certificate authority(which is part of a PKI). Hence, PKI plays an integral part in the security of modern application using AKC by enabling large-scale key management (by creating, managing, distributing and revoking digital certificates).

Security risks to asymmetric key cryptography

As outlined in the above table, modern asymmetric key algorithms such as RSA typically employ much larger key sizes than commonly used symmetric key counterparts such as AES-128. Even the ECC-based protocols (ECDH and ECDSA) that have smaller key sizes employ a minimum of at least 224 bits for keys. This in turn implies that a brute force attack involving an exhaustive search of the private key space to identify the correct key is computationally intractable in the foreseeable future. This remains true even if quantum computers were to be deployed for this task. Therefore, attacks against AKC usually focus on exploiting other potential weaknesses of specific cryptosystems. Some well-documented attack modes target:

1. Algorithmic weakness by using sophisticated mathematical and computational means to undermine the hardness assumptions used to formulate asymmetric key algorithms. For example, the security of RSA is predicated on the difficulty of factoring large prime numbers, and recent computational advances have enabled successful factoring of 829-bit RSA keys. Therefore, 1024-bit RSA is currently deprecated. As will be discussed later, the primary risk posed by quantum computers to AKC also falls into this category.

2. Imperfect randomness, which can lead to weakness in the key generation process. For example, if the random number generator used to create the keys is flawed and generates keys that are not truly random, an attacker might be able to predict the keys.

3. Implementation flaws such as errors in the implementation of cryptographic algorithms that inadvertently reveal information about the keys. For example, incorrect padding can potentially reveal details about keys.

4. Side channels that refer to information leakage from the physical system that performs the cryptography. Such leaks could be in the form of timing information, power consumption, or even sound, which can be exploited in a so-called side-channel attack. For example, analyzing how long cryptographic operations take to execute could reveal the number of '1's in a binary key. This seemingly innocent leakage significantly narrows the search space, unveiling potential solutions to problems that initially seemed insurmountable.

5. Key exchange by intercepting keys while they are being exchanged, such as within a man-in-the-middle attack (MITM). The DH protocol is susceptible to MITM attacks if additional authentication steps are not incorporated.

6. Key storage by aiming to steal keys from poorly secured storage. This includes physical attacks such as manipulation or theft of storage devices.

Securing asymmetric key cryptosystems against the variety of attacks that are possible is therefore a significant task involving mathematical, hardware, software, logistical, and legal considerations.

RSA

The RSA (Rivest-Shamir-Adleman) algorithm is one of the first public key cryptosystems and is widely used for secure data transmission. It is a versatile cryptosystem in that it provides the necessary operations to enable encryption, decryption, digital signatures, and key exchange within a common framework.

In this section, we will illustrate asymmetric key cryptography (AKC) using RSA through simple examples.

We will use the standard scenario of two parties, Alice and Bob, who wish to communicate securely using AKC.

The RSA algorithm

The basic RSA algorithm involves four operations: key generation, key distribution, encryption, and decryption:

1. Key generation:

   Public and private keys are generated based on mathematical principles around prime numbers, where calculating them is easy, but the reverse is hard.

   We'll refer to these:

   • Public key: $(e, n)$
   • Private key: $(d, n)$

   Note that $n$ is common to both public key and private key, and is known as the modulus. We will need to use this later.

   Mathematical detail

   • Choose two distinct prime numbers, $p$ and $q$.
     • chosen at random (for security).
     • They should be similar in magnitude, but differ in length by a few digits, to make factoring harder.
     • Prime numbers can be efficiently chosen using a primality test.
   • Compute $n = p*q$.
     • $n$ is the modulus for both the public and private keys.
   • Compute the totient $φ$$(n) = (p-1)*(q-1)$.
     • The totient is meant to be kept secret and typically discarded after key generation.
   • Choose an integer $e$ such that $1 < e <$$φ$$(n)$ and $gcd$$(e,$$φ$$(n)) = 1$.
     • i.e. $e$ and $φ$$(n)$ should be coprime.
     • This number $e$ forms the public key exponent and is typically chosen as a small number for computational efficiency.
     • The prime number $65537 = 2^{16} + 1$ is often used.
     • Compute $d$ to satisfy the congruence relation $d*e ≡ 1 ($$mod$$φ$$(n))$.
       • That is, $d$ is the multiplicative inverse of $e$ modulo $φ$$(n)$.
       • This is more efficiently computed using the extended Euclidean algorithm.
       • This number $d$ is the private key exponent.
   • The public key consists of $(e, n)$, and the private key is $(d, n)$.

2. Key distribution:

   • The public key $(e, n)$ is made public to those who may wish to send a message
   • The private key $(d, n)$ is kept secret.

3. Encryption:

   • Alice wishes to send a message $M$ to Bob. In this case a simple integer

   • Alice uses Bob's public key $(e, n)$ to encrypt the message into ciphertext $C$

   Mathematical detail

   • $M$ is an integer $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$, where $C$ is the ciphertext.

4. Decryption:

   • Bob receives the ciphertext $C$
   • Bob uses his private key $(d, n)$ to decrypt the message back into message $M$
   Mathematical detail

   • $M ≡ C^d (mod n)$.

This is the basic outline of RSA. In practice, more sophisticated padding schemes are applied to the plain text $M$ before encryption to ensure that equal plain texts result in different ciphertexts. This prevents a range of possible attacks against naive implementations of RSA and enables semantic security.

Illustration of RSA in Python

In the following code cells, we illustrate a simple example of the RSA algorithm using small integers and then demonstrate practical key distribution and digital signature applications using Python libraries implementing RSA.

Note: In this section we will show the math calculations in detail as part of the Python code

RSA key generation

Let's step through a simple instance of the RSA algorithm employing small prime numbers.

We will need to be able to compute the greatest common divisor of two integers, as it will be needed to test whether two integers are coprime.

We will explain one simple way to calculate this, but it is much more efficient with larger integers to use the math.gcd python function.

gcd(50,10) = 10
gcd(99,1033) = 33
gcd(59,9) = 1

The first phase of the RSA workflow is key generation. This is initiated by choosing two prime numbers, which are meant to be kept secret by the entity generating the keys.

The secret prime numbers p and q are: 13 19

Next, the modulus $n$, which is simply the product of the two chosen primes, is computed. This modulus will be published as part of the public key.

modulus n (p*q)= 247

The Euler totient function $\varphi(n)$ is computed next, as it is needed for the modular multiplicative inverse operation used to determine the keys in RSA. $phi$ is also kept secret and typically discarded after key generation.

The secret Euler's function (totient) [phi(n)]: 216

We are now ready to calculate the public and private keys. In RSA, each of these is specified by a tuple of two integers. The first entry in each tuple is a distinct integer, and the second entry is the modulus $n$ that is common to both keys.

The first entry in the public key can be any integer greater than 1 that is coprime to $phi$. Two integers are coprime if their greatest common divisor is 1. So we use the math.gcd function find an integer $e$ coprime to $phi$.

Public Key (e): 5

The private key requires an integer $d$, which is the multiplicative inverse of $e$ modulo $phi$; that is, it satisfies the congruency relation $d*e\equiv 1 \pmod{\varphi(n)}$. For this simple illustration where we are dealing with small integers, we can just loop over the positive integers to locate a suitable $d$. In realistic settings, the computationally efficient extended Euclidean algorithm is used for this purpose.

Private Key (d): 173

We now form the tuples $(e, n), (d, n)$, which form the public and private keys respectively. The public key is then published, while the private key is kept secret.

The Public key is (5, 247) and Private Key is (173, 247)

Encryption and decryption in RSA use the modular exponentiation operation. Further, the public and private keys are complementary in that either can be used to encrypt a message that the other can then decrypt.

Here we illustrate the case where the public key $(e,n)$ is used for encryption and the private key $(d, n)$ is used for decryption by defining a Python function for each operation.

We then encrypt and decrypt an integer message $msg$.

Original Message: 9
Encrypted Message: 16
Decrypted Message: 9

While the small integers used above are useful to easily outline the core ideas in the RSA algorithm, in real applications RSA requires the use of very large integers. For example, 2048-bit RSA involves the use of a modulus $n$ that is 2048 bits long, the decimal integer equivalents of which are around 10$^616$. These truly enormous numbers are necessary for the practical security of RSA.

Symmetric key exchange with RSA

As discussed previously, AKC enables two parties who wish to communicate to securely establish a shared secret, which can be used, for instance, as the secret key for subsequent symmetric encryption of bulk plain text.

Let us consider the following scenario. Alice and Bob want to use SKC to encrypt and decrypt messages. However, before this process can be initialized, they need to agree on a common secret key. One option is for one party — say, Alice — to generate a secret key and then securely transmit it to Bob. To achieve this secure transfer, Alice decides to use RSA as the key encapsulation mechanism (KEM).

This involves the following steps:

• First, Alice generates a random symmetric key, which she intends to share with Bob.
• Then, Bob generates an asymmetric key pair and makes his public key available on a suitable channel.
• Next, Alice uses Bob's public key to encrypt the symmetric key, thus encapsulating it in a ciphertext.
• Then, Alice broadcasts the ciphertext over a reliable but not necessarily secure channel.
• Finally, Bob receives the ciphertext and decrypts it using his private key. He now has access to the symmetric key generated by Alice.

Figure 1. Symmetric key exchange with RSA

Padding-based key-exchange example in Python

A practical workflow utilizing RSA for padding-based non-interactive key exchange is now illustrated using the cryptography Python library.

Import necessary modules from the cryptography Python library. If needed, this library can be installed using the command pip install cryptography.

Alice then generates a random secret key, which she intends to transmit to Bob.

Requirement already satisfied: cryptography in /home/travis/virtualenv/python3.11.0/lib/python3.11/site-packages (42.0.0)
Requirement already satisfied: cffi>=1.12 in /home/travis/virtualenv/python3.11.0/lib/python3.11/site-packages (from cryptography) (1.16.0)
Requirement already satisfied: pycparser in /home/travis/virtualenv/python3.11.0/lib/python3.11/site-packages (from cffi>=1.12->cryptography) (2.21)

Symmetric key generated by Alice: b'n7499EbS36iUOehWm_XTgiT_RgRhKPe8tbD6QEHps7U='

Using the rsa module from the cryptography library, Bob generates a key pair and then broadcasts his public key. Any one can intercept the public key and read off the public numbers $(e,n)$ that form the key.

Public key broadcast by Bob: <cryptography.hazmat.bindings._rust.openssl.rsa.RSAPublicKey object at 0x7fa7a4570290>

Public numbers in Bobs' public key: <RSAPublicNumbers(e=65537, n=28318586403474141406763564385551842567768357338303384331554692142040905569740933730177623451298221852890131171760569011411834419533062644264362237798713112012903562636899238690956445516763597222426451385820917153594982717835682879126504394700949486697366215656026171908759444098766648941648259553434147485142815729100352503479814708778130638335262520147401525661707978920617274148896293533924735012550867833159183955058383484476603763220505596309250511798152283696550616275594731528859541566726709785752736960726169358661677802248535004836852848635989762250159175787401257757712790765363612944909468318337956683930129)>

At this point, we assume Alice has received the public key broadcast by Bob. Alice's symmetric_key above can now be encrypted using Bob's public key to produce the ciphertext. In a realistic setting, Alice will also use additional padding methods such as OAEP to ensure semantic security for her communications with Bob.

Ciphertext: b'G*\xcfe\xd0\xe00\x8a\xa82\x05\xaa\xad\xb7\xecS\x14\x98\xa7H\xa6dlPl*\x88\xec\x99)\t%\xee\x8f\xcb\xf8\xba\x11\x97\x17j\xc3\x9e\xc7^\x86\x92p0\xfc\x1e\xb8M\x94\x99\xf4J\xf1\x8e\xda\xf2\x9d\x11<\xc5\x80\xe1+\x1b\xd9N\x1e0t9\xb65\x08Dg\xa0\xfd|/A\x80g\x85?\xa1\xfdDu\xf7\x02!n\xb5\x9d\xa15\x8dW\xbc\xa2\xd8E\x1b\x16\xf9\x8f<wK@#\x83N\xf9\x07\xd6t\xccT\x87\xdda\x86\xf5gw\x8e\xae\x9c\xc3\xa3\xb8\xb3Q\xe2!|E\x91\xe7z\xe33\xd7\x00\x88:^\x9b\x7fK\xad\xb5\xf8\x97\x0e\xec\xae\xbb\xbb8\xe8\xd5\xd74\x84\xb5\x19\xf1\x010 \x15\xcc6\x91K\x04\xa0\x9f\x81\xaa\x9aN\x19\x1b\xf0\xa5\x98B\xe7\x1d\x15\xf0\xa2\x0b\xa4\xb4\x9c\x83\xe2q\x95:\xe8\x95}\xc3\xcb\x9a\x1b\xef\xa8f\xa7y/\xb1\x18\x98\x8e\x0b\xb1gnw.\xb0\x00<\xe3\x9cXH)\xc3#_S~JA\x14o\\\xe7LK=>v'

Alice then broadcasts the ciphertext over an open channel, confident that only Bob with the corresponding private key will be able to decrypt it. We assume Bob has received the ciphertext and can now decrypt it using his confidential private key.

Decrypted key: b'n7499EbS36iUOehWm_XTgiT_RgRhKPe8tbD6QEHps7U='

At this point, Alice and Bob both have access to the secret symmetric key, which they can use for SKC applications.

Simulating a Key Encapsulation Mechanism with RSA in Python

In the following workflow, we illustrate the use of RSA to simulate a Key Encapsulation Mechanism (KEM) whereby a sufficiently long random secret message is securely exchanged and subsequently converted into a shared-secret of the appropriate length using a KDF.

Once again Alice and Bob want to establish a shared secret non-interactively and Alice is the party that decides which secret to use.

We start by importing some necessary Python libraries.

Bob then generates his RSA key pair and broadcasts his public key.

Bob's private and public keys created

Alice first generates a long random secret from which the shared secret will be eventually derived. In a pure KEM, the long secret will be a random element from the algebraic structure underlying the cryptosystem. In the case of 2048-bit RSA, this would be a random integer modulo the 2048-bit RSA modulus. As such a pure KEM does not require additional padding but in this example we are only simulating a KEM using RSA and the cryptography library requires the use of padding when encrypting with RSA. So we will use a somewhat shorter long secret which nevertheless is much longer than a standard 256-bit AES key.

Alice's secret created

Next Alice encrypts the long secret using Bob's public key and the encrypted secret is communicated to Bob.

Alice's secret encrypted

Bob decrypt's the encrypted secret received from Alice using his private key.

Secrets match

Finally both Alice and Bob separately apply an agreed upon Key Derivation Function (KDF) on the long secret to derive the symmetric key.

Note that the process involves a hashing protocol and the use of a random salt which ensures uniqueness and unpredictability of the shared symmetric key in case the long secret is ever reused (not recommended). However the salt itself does not have to be secret and once it is randomly generated, say by Alice in this example, it can be broadcasted to Bob alongside the encrypted long secret.

We will assume therefore that both Alice and Bob have access to the same random salt.

A symmetric key of length 256 bits was successfully derived by both Alice and Bob!

Digital signatures with RSA

We will now extend the above confidential communication scenario with Alice and Bob to one that also includes validation with the help of a digital signature

As before, Alice will confidentially send a message encapsulating a symmetric key to Bob, but she will also digitally sign the message so that Bob, upon receiving the message, can verify that it was Alice who originated it and that the contents of the message were not tampered with during transmission.

More generally, it is desirable to enable validation without compromising confidentiality whereby any interested party is able to verify the integrity, authenticity, and establish non-repudiation with respect to a given communication, even if that party does not have access to the actual plain text message.

We will consider this general setting which then involves the following steps:

• First, both Bob and Alice make their public keys available over an open channel.
• Then, Alice encrypts the plain text using Bob's public key, creating a ciphertext.
• Next, Alice creates a hash of the ciphertext with a hash function and further encrypts the resulting hashed ciphertext using her private key. This encrypted hash is the signature.
• Then, Alice then transmits both the ciphertext and the signature over an open channel.
• Then, Bob uses Alice's public key to decrypt the signature, revealing the hashed ciphertext.
• Next, since Bob also has access to the ciphertext itself, he uses the same hash function used by Alice to recreate a second instance of the hashed ciphertext. If the latter matches the one obtained by decrypting Alice's signature, then the message is validated, even though the ciphertext itself has not yet been decrypted.
• Finally, Bob, having validated the message, decrypts the ciphertext using his own private key.

Figure 2. Digital signatures with RSA

This workflow for a digital signature is illustrated next.

We once again import some useful modules from the cryptography library.

As before, Alice intends to securely send a symmetric key to Bob, but she also wishes to digitally sign it. In this case, we need public keys for both Alice and Bob. Therefore, the first step is for both Alice and Bob to create their own key pair using RSA and broadcast their own public key to the world.

Private and Public keys generated for Bob and Alice.

In the next step, as before, Alice uses Bob's public key to encrypt the symmetric key and prepares the ciphertext.

ciphertext of symmetric key:  b'b$\x1cQ\r.\x93\xc5=\xde\x1cg\xe4X\x8f\xf7\xecic\x06F\n\x8ao\xc7X\x9c\x12\xef{9r8\xb5A\x95Ma6\x90\xf4\xc2\xf8\xcd\xe7%\xa8\xcd+\x18\xcb\x9cC7\xd9_s\x07\xb4\xd8\x11O\x99\xa1Q\xdd/\xc8p\xbb\xb5R\xdc\xe4n$?\x84\xcb\x8a\x16\xc1 \x84\\\x9c\xa9\xc7\xdbOu/\x16t\xe8C\xce\x94 \x7f\x92\x80\x85\xefn7\x0e_\xb6Y\xbb\xdcQD8\xee\xecG9N\xd5G\x97@\x89\x9e^.\x04~\x8bC!@G\x88\x0f\xba\x1ciY\xea\xd3M\x04h\xfd\xb0\x06\xc3\x8b]f!J\x84\xc9\xb8t_\xf1o\x9cB:\\Yu0\xa1\x8b\xd3C<\x02\xc8$\xfa\x96\xf7g\xae\xbb\xb2\xd2-\xdbTk\xb3R\xe1\x90\x00E\xdd}2\xb5S$Cx8\x15>\xc6mu]\x8e\xd8z\xa0\xab\x06+\xc9T=\x87\xcf{\x8e\x8e\xe3\x80\xb2\xc4\x15\xdb\xed\x16,\x86\x12\xf5\xe9upb\xe2#z\xe6pX3\xc4\x12$\x0f\xd2\xee\xf4\x11'

At this stage, instead of just broadcasting the ciphertext, Alice intends to attach a digital signature to it so that she can prove to Bob that she was the sender of the message. This is done in two steps:

1. Create a hash of the ciphertext using a hashing algorithm.
2. Encrypt the hash using Alice's private key, which amounts to a signature.

signature:  b'\x940\xa1\x0302\xda*\xc6\xf4\xbbC\x1d\x85U\'\xceL\x92\x18\xdc\xce\x81NK\xf8\xab~\xc4\xd0\x96\x14\x04\x8dL\x7f\x1aHr*\xde\xfdEt\xe9&YZ:\xd7\xcde\x1a\x8d\xc4\x8a^\xfd\x9c\x89\x8d\x1c\xdem\xb2 U1\xc3\x1ev\xe3\xf7\xb7\xb8\xc7Ya\xc9\xa5\x9b\xbf,\xad|\xc0\xf7\x98\xc4\xec>h\xa5.\x8c\x81L\xed\x81\xf3<r$1\xcctd\xa7xbZi\x05\xc7\xb6\x92z \x03"\xb62j\x0eE\x06\x0f\xdeO\x84\xf1\xd0m\x89\x9f\xaa\x8d\xae\xee\xe44?\x98\xdf\xbb\x9a\xd5\xe2%FWW\xdb\xd9=\xac&/q\x8d\x9bY\xcf60\x94\xad\xdbX\xdfq\x85\x0f\xb7\x08\x10.\xdc^0\xf3PG\xa9\xcf\x88\xc6\x05\x11\x1b\x89\xb8\x962\n\xb1\x8aC\xde{\x83l\x94\'\xd8\x98vD\xc5\xb0\xc7\x93\x7f\x11\n\x1dp\x7f\x94\xb6f\xb0\xbf\x97-o\xc1tQ*k\x9fSe\xc5i_4p\rL\xed\x85j@\xb6\x03\xb6\xf2\x13Bl\xda\xff\x15*'

Alice then broadcasts the ciphertext and the signature over a network so that Bob is able to intercept both of them.

Sending ciphertext and signature.....

On Bob's side, the first task is to verify the integrity and authenticity of the ciphertext. To do this, Bob creates a hash of the received ciphertext using the same hashing algorithm used by Alice.

hash to verify:  b'/Iy\x91\xf8\xc7\x9d\xb0\xe0,1{\x99\xb7EM\x96\xcb\xf4\xf7\xaf<A\xdc3\x10\xf1\xb2;T\x84\xef'

Then, Bob decrypts the received signature using Alice's public key. Because Alice used her private key to create the signature, Bob is able to decrypt it using Alice's public key. The decrypted signature is nothing but a hash of the ciphertext created on Alice's end. If the hash created by Bob matches the decrypted signature, then Bob has verified that the ciphertext he received has not been tampered with and that it was Alice who signed the ciphertext.

In the Python code below, these operations are combined into a useful utility function called verify provided by an object associated with Alice's public key.

The signature is valid.

Having verified the integrity and authenticity of the received ciphertext, Bob can then decrypt it using his private key because Alice created the ciphertext using Bob's public key.

Decrypted message: n7499EbS36iUOehWm_XTgiT_RgRhKPe8tbD6QEHps7U=

In the above digital signature scenario, any party — not just Bob — can verify that Alice is the sender of the ciphertext because everyone can access Alice's public key, the ciphertext, and the digital signature. Furthermore, after sending the ciphertext and the signature, Alice cannot later deny having done so because the signature can be decrypted to a meaningful hash using only her public key. This establishes non-repudiation.

By enabling secure key distribution and supporting non-repudiation, public key cryptography establishes a strong foundation for secure digital communication.

Breaking RSA

The utility and security of the RSA algorithm outlined above rests on two mathematical assumptions:

1. Finding the modular multiplicative inverse $d$ given that access only to $(e, n)$ is computationally infeasible.

2. In the RSA setting, the modular exponentiation operation behaves like a one-way trapdoor function. When used for encryption, it yields ciphertext that is inscrutable, and without access to the private key, inverting the operation to recover the plain text from the ciphertext is not feasible. However, with access to the private key, which acts as a trapdoor, the ciphertext can be easily decrypted.

The most prominent attack on the RSA algorithm aims to undermine assumption 1 by efficiently recovering the private key number $d$ via factorizing the modulus $n$. As will be illustrated below, it is easy to recover $d$ if one has access to either the prime factors $p$ and $q$ of $n$ or the totient $φ$$(n)$. Recall that $p$, $q$, and $φ$$(n)$ are kept secret during key generation and discarded after. A third party that recovers this information using a classical or quantum computer essentially uncovers the private key, breaking RSA. Thus, prime factorization is the key computational primitive necessary for breaking RSA.

Classical computing and RSA

Prime factorization of large integers is known to exhibit super-polynomial or subexponential scaling on classical computers. The best-known classical algorithm for factoring integers larger than $10^{100}$ is the general number field sieve (GNFS).

At present, the largest integers factored on classical hardware are in the range of 829 bits or 250 decimal digits. Given the exponential growth in classical computing power that has been witnessed over the last several decades, 1024-bit RSA is no longer considered secure in the near term and is now deprecated. Nevertheless, in the foreseeable future, factoring 2048-bit integers whose magnitude are in the range of $10^{617}$ is at present considered infeasible on classical systems, suggesting continued viability. The advent of quantum computers, however, voids this assessment.

Shor's quantum algorithm and RSA

Probably the most well-known quantum algorithm today is Shor's algorithm for finding the prime factors of integers. When introduced by Peter Shor in 1994, it was recognized as the first quantum algorithm that offered a super-polynomial speedup relative to classical algorithms on a problem of great practical importance, namely prime factorization.

Shor's algorithm can factor primes with $O(n^2)$ where $n$ is the number of bits.

In August 2023 Oded Regev published an improvement on Shor's original using a multi-dimensional approach resulting in $O(n^{1.5})$. There continues to be further research including by Ragavan and Vaikuntanathan in this area which may improve time, cost, or number of qubits needed. Whilst we cannot say when running such algorithms against real-world RSA encryption truly becomes viable, it is becoming closer all the time.

Python example demonstrating breaking RSA encryption

In the following code cells, we illustrate an example of finding a private key given only the public key. This will use brute-force classical computation, but shows how Shor's algorithm could be used - including large keys.

Note: In this section we will show the math calculations in detail as part of the Python code

In the example, we have a public key $(5, 247)$, and we will recover the private key.

Step 1: The first step is to pick a number coprime to 247. Almost any number we guess will do the job. Let's pick 6.

Checked 247 and 6 are coprime

Step 2: Next we need to find the period $r$ such that $6^r \equiv 1 (mod~247)$. In this example, we compute $r$ classically using brute force, but we could also use Shor's algorithm on a quantum computer using Qiskit.

period r is: 36
Checked 6^36 mod 247 is 1

Step 3: Since the period $r = 36$ is even, we can compute $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

f1 = 101559956668415
f2 = 101559956668417

Step 4: Find the GCD of either of those factors with $n$. Simply divide $n$ with the prime factor already found to obtain the second prime factor.

One possible prime factor of n (247) is: 19
The second prime factor of n (247) is: 13

Step 5: Having recovered the prime factors of $n = 247$ as $p_{found}=13$ and $q_{found}=19$, we compute the totient $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

The private key is the modular inverse of the public key number $e=5$.

The totient is: 216
Private Key number: 173

In the above scheme, step 2 is the crucial period-finding operation for which Shor's algorithm uses two fundamental quantum primitives, namely the quantum Fourier transform and quantum phase estimation. For a detailed explanation of the quantum aspects of Shor's algorithm, see the Phase estimation and factoring lesson in the Fundamentals of Quantum Algorithms. Steps 1 and 3 through 5 involve relatively inexpensive operations that can be easily carried out on classical computers.

Optionally, here's a detailed visual walkthrough of implementing Shor's algorithm.

On quantum computers, Shor's algorithm can exhibit polylogarithmic scaling as favorable as $O((log~n)^2 (log~log~n))$ in terms of the modulus $n$, or polynomial scaling in terms of the number of bits needed to represent $n$. This is a super-polynomial speedup compared to the classical GNFS algorithm.

Recent resource estimates indicate that based on certain assumptions made regarding the hardware configuration, a few tens of thousands to several million qubits will be necessary to break 2048-bit RSA using Shor's algorithm. It is not inconceivable that quantum computers with several tens of thousands of qubits will become available over the next several years, making the lower end of the resource estimate accessible.

Diffie-Hellman key exchange and the Digital Signature Algorithm

In the previous section, we discussed the RSA cryptosystem, whose security is based on the computational hardness of prime factorization. Here, we will discuss two popular asymmetric key cryptographic protocols, Diffie-Hellman key exchange (DH) and the Digital Signature Algorithm (DSA), both of which are based on a different mathematical problem, namely the discrete logarithm problem (DLP).

The discrete logarithm problem

In the following equation we need to find $a$ given only $e$,$M$,$c$

$a^e$ $mod$ $M = c$

This is believed to be difficult with classic computers due to the use of modulo arithmetic, and therefore is a good mathematical basis for an encryption algorithm.

This is known as the discrete logarithm problem (DLP).

Using generator 5
5**0 mod 7 ≡ 1
5**1 mod 7 ≡ 5
5**2 mod 7 ≡ 4
5**3 mod 7 ≡ 6
5**4 mod 7 ≡ 2
5**5 mod 7 ≡ 3
5**6 mod 7 ≡ 1
5**7 mod 7 ≡ 5
5**8 mod 7 ≡ 4
5**9 mod 7 ≡ 6
5**10 mod 7 ≡ 2
5**11 mod 7 ≡ 3
5**12 mod 7 ≡ 1
5**13 mod 7 ≡ 5
5**14 mod 7 ≡ 4
5**15 mod 7 ≡ 6
5**16 mod 7 ≡ 2
5**17 mod 7 ≡ 3
5**18 mod 7 ≡ 1
5**19 mod 7 ≡ 5
5**20 mod 7 ≡ 4

Diffie-Hellman key exchange

In 1976, Whitfield Diffie and Martin Hellman proposed a key exchange protocol to enable the creation of a shared secret key over insecure communication channels. The secret key could then be used by parties sharing it for symmetric encryption. The algorithm relies on the DLP.

Figure 1. Diffie-Hellman key exchange

Illustration of the Diffie-Hellman protocol in Python

Let's look at a simple example of the DH protocol in Python using small prime numbers:

Note: In this section we will show the math calculations in detail as part of the Python code

Step 1: Alice and Bob agree on a prime $p$ and a primitive root $a$. Let's choose $p=11, a=7$.

prime: 11
primitive root: 7

Steps 2, 3: Alice chooses a secret exponent $k_A$ and calculates $h_A = a^{k_A}~(mod~p)$. Similarly, Bob chooses a secret exponent $k_B$ and calculates $h_B = a^{k_B}~(mod~p)$.

Alice's private key is 4 and public key is 3
Bob's private key is 8 and public key is 9

Step 4: The two parties broadcast their public keys $h_A$ and $h_B$.

Steps 5, 6: Each party combines their private key with the other party's public key to create the shared secret key.

The shared secret key is: 5

Alice and Bob can now use the shared secret key for symmetric encryption.

Security of Diffie-Hellman key exchange

As noted above, the security of DH is predicated on the computational difficulty of solving the DLP with large primes $p$. In typical applications, NIST recommends 2048- or 3072-bit prime integers for DH key exchange, which is considered sufficiently secure against attempts to solve the DLP using classical computers.

Man-in-the-middle (MITM) attacks: The fact that DH is an interactive scheme where the shared secret depends on combining one party's private key with the other party's public key makes it vulnerable to a so-called Man-in-the-middle (MITM) attack.