CrPT🔑: Applications of Cryptography

Welcome to my new blog series CrPT🔑 that discuss about applications of cryptography. In this first episode, I will explore current trends in cryptography and their impact on various applications. With significant developments in Artificial Intelligence (AI) and recent breakthroughs in quantum computing, it is a great time to discuss the future of cryptography. This episode aims to examine the factors that will and will not influence the future of applications that rely on cryptography.

AI Generated Image : credits to grok2

One-Time Pad

The one-time pad (OTP) is considered the only theoretically unbreakable cryptographic method when implemented correctly because it achieves perfect secrecy, meaning the ciphertext provides no information about the plaintext without the key, as proven by Claude Shannon. The key used in an OTP must be as long as the message, truly random, securely shared, and used only once.

To illustrate how a One-Time Pad (OTP) works, let’s consider a simple example involving two parties, Alice and Bob.

Step 1: Key Generation Alice and Bob agree on a random key that is as long as the message they wish to exchange. For this example, let’s use the message “HELLO”.

• Message: H E L L O
• Key: X M C K L

Step 2: Encryption Each character of the message is combined with the corresponding character of the key using a modular addition (for simplicity, we’ll use their ASCII values).

• Ciphertext: 160 146 143 151 155

Step 3: Decryption Bob, who possesses the same key, can decrypt the ciphertext by subtracting the key values from the ciphertext.

• Decrypted Message: H E L L O

Requirements of OTP:

• The key must be truly random, same size as the message and kept secret.
• The key is used only once; reusing keys compromises security.
• The security of OTP relies on the randomness and secrecy of the key.

However, if you carefully consider the first two requirements, you’ll notice a significant drawback of the OTP. The key must be as long as your message, which defeats its original purpose because transferring the key securely requires the same effort as transferring the message itself. Almost all cryptographic algorithms used today address this issue in various ways, such as through the use of asymmetric encryption, which allows secure key exchange without the need for pre-shared keys, or by employing key derivation functions and protocols like Diffie-Hellman to enable secure communication over insecure channels. Additionally, these algorithms utilize shorter keys by using complex mathematical problems and computational hardness assumptions. They help to implement robust security without the need for excessively long keys.

Artificial Intelligence (AI) and Cryptography?

Now that we understand the basics of the One-Time Pad, let’s examine whether AI will be able to take over modern cryptography. As mentioned earlier, cryptographic algorithms are designed based on hardness assumptions. For example, brute-forcing a message encrypted using AES-CTR-256 would take billions of years even for a supercomputer. The same applies to training an AI model to crack modern encryption algorithms. Let me explain why…

Cryptography removes Patterns in Data

Generative models, such as those in machine learning, cannot replicate the security of an OTP because they produce pseudo-random sequences rather than truly random ones, and they are designed to recognize and replicate patterns, which contradicts the OTP’s requirement for patternless keys. In otherwords, AI models are pre-trained on data, such that they can make a prediction on new data by understading the pattern of the data. However, the major controbution of cryptograohy is to remove the patterns from the data.

We can replicate this analogy with a simple illustration of a hash function. In the text box below we have a text string, the correspoding SHA-512 string is on the next message box. Try changing the value of the text string and observe how the hash value of the string changes with that.

As you oubserved, it a machine learning model needs to learn this using traning data, essentially it needs to learn all the patterns. At this point it becomes a table lookup rather than a prediction.

Secret Keys Add More Complexity

Making this relation more complex, the most common encryption, decryption, sign and verify mechanism uses various forms of secret keys. Unless the key is compromised, finding a non-existing pattern between plain text and cypher text has too much of complexity.

To understand this, lets look at the following illustration.

As you have seen in the above illustrations, AI is not in a position to impact modern cryptography. Someone might argue about what would happen if computing power increases to the point where AI can utilize vast resources. The answer is simple: in such situations, AI is not required, and brute force attacks can be conducted with the same effort. However, cryptographic algorithm parameters, such as key sizes, can be increased to account for potential computational power. An example of this is the deprecation of DES in favor of more secure algorithms like AES, due to the potential for brute-forcing with modern computers.

Quantum Computers and Cryptography?

Although we don’t have to worry about AI breaking cryptography, quantum computers have the potential to become a threat to some of the algorithms used to build the public key infrastructure (PKI). Cryptographic algorithms like RSA and Elliptic Curve-based Cryptography (ECC) are implemented based on assumptions about the hardness of prime factorization. Theoretically, with a quantum computer with enough qubits, Shor’s algorithm can solve the prime factorization problem.

When Quantum Computers Will Take Over?

So the next question arises: What happens to the current infrastructure that uses PKI, such as blockchain, network authentication, and secure communication systems? We don’t need to panic about this question at the moment. Current quantum computers do not have the capacity to break modern PKI yet. Even Google’s latest quantum computer, Willow, has 105 qubits, which is not capable of breaking RSA-1024, a standard that is already deprecated due to its low security strength. Quantum computers need to successfully solve the issue of “noise” in order to scale well enough to achieve this capability.

Post Quantum Cryptography

Although current quantum computers are not powerful enough yet, advancements in science may allow them to scale to a level capable of breaking PKI. As a precaution, researchers are proposing post-quantum cryptographic algorithms. The National Institute of Standards and Technology (NIST) has standardize post-quantum cryptographic algorithms. Aiming to deprecate vulnerable PKI algorithms like RSA and Elliptic Curve Cryptography (ECC) by 2030, NIST is evaluating and selecting new standards that can withstand quantum attacks. The selected algorithms include CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium for digital signatures.

The concepts of these algorithms are based on two main problems:

1. Lattice Problems
2. Learning with Errors

In the rest of this series, we will discuss these techniques with simplified examples and illustrations.

Conclusion

In this first episode of CrPT🔑, we have explored the fundamental principles of cryptography, the potential threats posed by advancements in artificial intelligence and quantum computing, and the proactive measures being taken to secure our digital future. While AI may not currently pose a significant threat to modern cryptographic systems, the rise of quantum computing necessitates the development of robust post-quantum algorithms. So in the subsequant articles, lets discuss more about the concepts behind these new algorithms, so that we can be familier with them before it is too late.