Cryptography refers to the practice of creating and using codes and ciphers to secure communication and information [2]. The encryption algorithm is a cryptographic algorithm that takes as input a plaintext and an encryption key, and outputs a ciphertext. The decryption algorithm is a cryptographic algorithm that takes as input a ciphertext and a decryption key, and outputs a plaintext [1].
The encryption key is a value known to the sender while the decryption key is a value known to the receiver. The decryption key is related to the encryption key but is not always identical to it. In public-key cryptosystems, the encryption key and the decryption key are fundamentally different. For this reason, public-key cryptosystems are sometimes referred to as asymmetric cryptosystems. In such cryptosystems, it has been considered computationally infeasible to determine the decryption key from the encryption key [1].
This is because public-key cryptosystems like RSA, involve exponentiation. However, if the interceptor knows the algorithm used, in the case of secure communication over the internet, where RSA is commonly used. The interceptor can attempt to determine the plaintext by cracking the RSA encryption algorithm [1]. The RSA encryption formula is as follows:
C = M^e mod n
Where:
- C is the ciphertext
- M is the plaintext message
- e is the public key exponent, typically 65537.
- n is the product of two large prime numbers, known as the modulus.
The RSA decryption formula is:
M = C^d mod n
Where:
- d is the private key exponent
“The RSA encryption formula involves computing the ciphertext by raising plaintext to the public key exponent modulo a product of two large prime numbers. The RSA decryption formula involves computing the plaintext by raising ciphertext to the private key exponent modulo the same product of prime numbers. To determine the length of the private key in RSA, we must consider the specifics of the public-key cryptosystem. In RSA the decryption key d is a number modulo n. This means the decryption key can be any number less than n. Hence, the maximum number of bits we need to represent an RSA private key is the smallest number k such that:
2^k ≥ n” [1].
“Public-key cryptosystems tend to be referred to directly in terms of their maximum private key lengths. When someone refers to 3072-bit RSA, they mean the modulus n is 3072 bits long when written in binary, and thus the maximum private key length is also 3072 bits” [1].
The process of cracking the RSA encryption algorithm involves the exhaustive key searches for private keys. An ‘informed’ exhaustive key search would consist of only trying private keys having the necessary mathematical properties. For example, not all 3072-bit numbers are possible values of d for RSA. To perform such a search, we need a means of determining which keys are valid candidates for private keys. The catch is that finding this means of determining candidates tends to be related to solving the underlying hard problem. In the case of RSA, to determine whether a number is a candidate for d, we first need to know the factors of n [1].
A recent study by Chinese scientists claims that combining classical and quantum computing could enable the cracking of the RSA algorithm with a key length of 2048 bits, which is fundamental for the operation of internet protocols [3]. While it has been widely accepted that a quantum computer has the theoretical ability to perform ultra-fast factorization of larger integers such as the modulus necessary for RSA encryption. It was assumed that a quantum computer complex enough to crack RSA would not be built for several more decades.
However, this research displays a breakthrough made by optimizing the Schnorr algorithm. The researchers were able to factor a 48-bit key on a 10-qubit quantum computer and even claim that their algorithm can be scaled for use with 2048-bit keys using a quantum computer with only 372 qubits [3].
“It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA” [3].
While increasing the size of the prime numbers used in RSA can help make it more resistant to quantum computers. This is not enough to make RSA completely secure against quantum attacks. The existence of a quantum computer capable of breaking RSA highlights the need for a transition to post-quantum cryptography.
Red Sky Alliance is a Cyber Threat Analysis and Intelligence Service organization. For questions, comments or assistance, please contact the office directly at 1-844-492-7225, or feedback@wapacklabs.com
Weekly Cyber Intelligence Briefings:
- Reporting: https://www. redskyalliance. org/
- Website: https://www. wapacklabs. com/
- LinkedIn: https://www. linkedin. com/company/64265941
Weekly Cyber Intelligence Briefings:
REDSHORTS - Weekly Cyber Intelligence Briefings
https://attendee.gotowebinar.com/register/5504229295967742989
[1] Martin, K. M. (2011). Everyday cryptography: Fundamental principles and applications. Oxford University Press.
[2] Vacca, J. R. (2017). Computer and Information Security Handbook. Morgan Kaufmann Publishers.
[3] Yan, B., et al. (2022). Factoring integers with sublinear resources on a superconducting quantum processor. Retrieved from https://doi.org/10.48550/arXiv.2212.12372.
Comments