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:
- 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.
- There is no provision for . 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 (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:
- Encryption and decryption to enable confidentiality of communications.
- Digital signatures to ensure authenticity, integrity, and non-repudiation.
- 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 . 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 (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 (ECC) extend this concept with the (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 is used to embed it into a longer (1024-4096 bit) message. This longer message is encrypted using AKC and broadcasted as . The recipient first decrypts the ciphertext and then removes the padding to extract the shorter symmetric key.
- Key mechanisms (KEMs): With 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 (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 , with their ability to directly encrypt data, can be used to implement KEMs.
Figure 3. Key Encapsulation Mechanism
Digital signatures with asymmetric key cryptography
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 (DSA). Somewhat similarly to the Diffie-Hellman protocol, the DSA uses the algebraic properties of the and for signature generation and verification.
The (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 .
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, which will be discussed in detail in a later section, also exploits modular multiplicative inverses and 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
is in modern digital technology applications. The basic functionalities of AKC described above form the building blocks of many higher-level application protocols, including:
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.
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.
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.
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.
VPN (virtual private network): Asymmetric key encryption is used to establish secure connections in VPNs, ensuring secure communication over public networks.
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.
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 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:
Protocol | Typical Key Sizes (in bits) | Application |
---|---|---|
RSA | 1024 (deprecated), 2048, 3072, 4096 | Encryption, digital signatures |
DSA | 1024 (deprecated), 2048, 3072 | Digital signatures |
DH | 2048, 3072, 4096 | Key exchange |
ECDH | 224, 256, 384, 521 | Key exchange |
ECDSA | 224, 256, 384, 521 | Digital signatures |
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:
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 . 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.
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.
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.
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 . 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.
Key exchange by intercepting keys while they are being exchanged, such as within a (MITM). The DH protocol is susceptible to MITM attacks if additional authentication steps are not incorporated.
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 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:
Key generation:
Public and private keys are generated based on mathematical principles around , where calculating them is easy, but the reverse is hard.
We'll refer to these:
- Public key:
- Private key:
Note that 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, and .
- 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 .
- Compute .
- is the modulus for both the public and private keys.
- Compute the .
- The totient is meant to be kept secret and typically discarded after key generation.
- Choose an integer such that and .
- i.e. and should be .
- This number forms the public key and is typically chosen as a small number for computational efficiency.
- The prime number is often used.
- Compute to satisfy the .
- That is, is the of modulo .
- This is more efficiently computed using the .
- This number is the private key .
- The public key consists of , and the private key is .
Key distribution:
- The public key is made public to those who may wish to send a message
- The private key is kept secret.
Encryption:
Alice wishes to send a message to Bob. In this case a simple integer
Alice uses Bob's public key to encrypt the message into ciphertext
Mathematical detail
- is an .
- , where is the ciphertext.
Decryption:
- Bob receives the ciphertext
- Bob uses his private key to decrypt the message back into message
Mathematical detail
- .
This is the basic outline of RSA. In practice, are applied to the plain text 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 .
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 of two integers, as it will be needed to test whether two integers are .
We will explain one simple way to calculate this, but it is much more efficient with larger integers to use the
Output:
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.
Output:
The secret prime numbers p and q are: 13 19
Next, the , which is simply the product of the two chosen primes, is computed. This modulus will be published as part of the public key.
Output:
modulus n (p*q)= 247
The Euler function is computed next, as it is needed for the operation used to determine the keys in RSA. is also kept secret and typically discarded after key generation.
Output:
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 that is common to both keys.
The first entry in the public key can be any integer greater than 1 that is coprime to . Two integers are coprime if their is 1. So we use the
Output:
Public Key (e): 5
The private key requires an integer , which is the of modulo ; that is, it satisfies the . For this simple illustration where we are dealing with small integers, we can just loop over the positive integers to locate a suitable . In realistic settings, the computationally efficient is used for this purpose.
Output:
Private Key (d): 173
We now form the tuples , which form the public and private keys respectively. The public key is then published, while the private key is kept secret.
Output:
The Public key is (5, 247) and Private Key is (173, 247)
Encryption and decryption in RSA use the . 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 is used for encryption and the private key is used for decryption by defining a Python function for each operation.
We then encrypt and decrypt an integer message .
Output:
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 that is 2048 bits long, the decimal integer equivalents of which are around 10. These truly enormous numbers are necessary for the practical security of RSA.
Symmetric key exchange with RSA
As discussed previously, 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 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 (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
Import necessary modules from the
Alice then generates a random secret key, which she intends to transmit to Bob.
Output:
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
Output:
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
Output:
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.
Output:
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 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.
Output:
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 , 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
Output:
Alice's secret created
Next Alice encrypts the long secret using Bob's public key and the encrypted secret is communicated to Bob.
Output:
Alice's secret encrypted
Bob decrypt's the encrypted secret received from Alice using his private key.
Output:
Secrets match
Finally both Alice and Bob separately apply an agreed upon (KDF) on the long secret to derive the symmetric key.
Note that the process involves a hashing protocol and the use of a random 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.
Output:
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
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 , , 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
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.
Output:
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.
Output:
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:
- Create a hash of the ciphertext using a hashing algorithm.
- Encrypt the hash using Alice's private key, which amounts to a signature.
Output:
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.
Output:
Sending ciphertext and signature.....
On Bob's side, the first task is to verify the and of the ciphertext. To do this, Bob creates a hash of the received ciphertext using the same hashing algorithm used by Alice.
Output:
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
Output:
The signature is valid.
Having verified the and of the received ciphertext, Bob can then decrypt it using his private key because Alice created the ciphertext using Bob's public key.
Output:
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 .
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 algorithm outlined above rests on two mathematical assumptions:
Finding the given that access only to is computationally infeasible.
In the RSA setting, the modular exponentiation operation behaves like a . 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 algorithm aims to undermine assumption 1 by efficiently recovering the private key number via factorizing the . As will be illustrated below, it is easy to recover if one has access to either the and of or the totient . Recall that , , and 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 or scaling on classical computers. The best-known classical algorithm for factoring integers larger than is the .
Mathematical detail
as a function of the integer to be factorized.
This scaling is super-polynomial in the number of bits required to represent .
Therefore, prime factorization is considered inefficient on classical computers.
At present, the 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 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 for finding the prime factors of integers. When , it was recognized as the first quantum algorithm that offered a relative to classical algorithms on a problem of great practical importance, namely prime factorization.
Shor's algorithm can factor primes with where is the number of bits.
Mathematical explanation of Shor's algorithm
In the context of , works by exploiting the of the and provides a quantum -finding primitive that enables efficient prime factorization of the .
A simplified high-level outline of Shor's overall scheme for breaking RSA is as follows:
Given the modulus , which is published as part of the public key, choose a number coprime to i.e., . Since we know that has exactly two prime factors , almost any number less than that we pick at random is likely to be coprime to .
Having chosen , find the exponent such that . This implies . The existence of an such that the above holds is guaranteed by the of .
If is even, for some integer . The left-hand side of this latter equality must contain and as two of its prime factors since the right-hand side does. If is odd, go back to step 1 and try a different choice for .
Use the for finding or . The computed is very likely to identify one of the prime factors or . Divide with this prime factor to recover the other.
Once are known, use the steps from the original RSA algorithm for reconstructing the totient and generating the private key number as the of the known public key number .
In August 2023 Oded Regev on Shor's original using a multi-dimensional approach resulting in . There continues to be further research including by 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 , 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.
Output:
Checked 247 and 6 are coprime
Step 2: Next we need to find the such that . In this example, we compute classically using brute force, but we could also use Shor's algorithm on a quantum computer using .
Output:
period r is: 36
Checked 6^36 mod 247 is 1
Step 3: Since the is even, we can compute .
Output:
f1 = 101559956668415
f2 = 101559956668417
Step 4: Find the of either of those factors with . Simply divide with the prime factor already found to obtain the second prime factor.
Output:
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 as and , we compute the totient .
The private key is the of the public key number .
Output:
The totient is: 216
Private Key number: 173
In the above scheme, step 2 is the crucial -finding operation for which uses two fundamental quantum primitives, namely the and . 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 as favorable as in terms of the modulus , or in terms of the number of bits needed to represent . This is a compared to the classical .
indicate that based on certain assumptions made regarding the hardware configuration, a few tens of thousands to several million 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, (DH) and the (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 given only ,,
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 (DLP).
Mathematical details of the discrete logarithm problem
The DLP is typically framed in the context of and is stated as follows.
Consider a generated by a group element and given an arbitrary element , find an integer such that .
Here the integer is the discrete logarithm. The cyclic property of guarantees that for every , a valid integer exists.
For cryptography, the DLP on the of integers modulo a prime number denoted turns out to be useful. The elements of are congruence classes labeled by integers modulo that are coprime to .
For example:
The operation of multiplication on these groups is simply ordinary integer multiplication followed by reduction modulo and exponentiation by an integer is just repeated multiplication times and reduction modulo .
Let's illustrate an instance of the DLP on .
This multiplicative group has two generators also known as primitive roots. We will use as the generator; that is, generate every element of using successive integer powers of 5.
No output produced
Output:
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
We see that in modulo 7 arithmetic, raising 5 to successive integer powers yields every element of exactly once before the cycle repeats indefinitely with a period .
So the DLP on with generator 5 is:
.
From the above Python cell output we see that:
In ordinary real number arithmetic, exponentiation is a , function and finding the logarithm of any number to any base is computationally easy. In contrast, as is apparent from the simple example above, modular exponentiation is non-monotonic, and even though it is periodic with period , it is otherwise highly nontrivial. So computing its inverse, the discrete logarithm turns out to be inefficient for large on classical computers.
This observation underpins both Diffie-Hellman (DH) key exchange and the Digital Signature Algorithm (DSA), which are discussed in the next section.
The DLP can be extended to cyclic subgroups as follows:
- Consider defined above and an element of prime order i.e., .
- The set of integer powers of : is a cyclic subgroup of with group order .
- A DLP can be specified on by choosing a and asking for such that
Diffie-Hellman key exchange
In 1976, 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
Mathematical details of Diffie-Hellman key exchange
With Alice and Bob being the two parties communicating, the protocol works as follows:- First, Alice and Bob agree on a large prime number and a primitive root or generator .
- Then, Alice chooses a secret exponent randomly with and calculates . are Alice's private and public keys respectively.
- Next, Bob chooses a secret exponent randomly with and calculates . are Bob's private and public keys respectively.
- Then, Alice sends Bob and Bob sends Alice over a reliable but not necessarily secure channel.
- Then, Alice then uses the she received to compute the shared secret key .
- Finally, Bob meanwhile uses the he received to compute the shared secret key .
With this protocol,
- Alice and Bob are guaranteed to end up with the same secret key because .
- A third party that intercepts or cannot construct the secret key because they do not have access to or respectively.
- Extracting or using the public information , , and is computationally hard as it is equivalent to solving the DLP on .
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 and a primitive root . Let's choose .
Output:
prime: 11
primitive root: 7
Steps 2, 3: Alice chooses a secret exponent and calculates . Similarly, Bob chooses a secret exponent and calculates .
Output:
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 and .
Steps 5, 6: Each party combines their private key with the other party's public key to create the shared secret key.
Output:
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 . 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.
Mathematical details of DH security and MITM attacks
In this scenario, a third party — say, Eve — intercepts the public keys during transmission and substitutes her own public key for each of and