Introduction to Cryptography

Cryptography is the practice of secure communication through the use of codes and techniques to protect information from unauthorized access or tampering. It has been an essential aspect of human communication for centuries, with its roots dating back to ancient civilizations. Today, cryptography plays a crucial role in ensuring the confidentiality, integrity, and authenticity of data transmitted over various networks, including the internet.

Basic cryptography involves two fundamental concepts: encryption and decryption. Let's explore these concepts:

1. Encryption: Encryption is the process of converting plaintext (readable data) into ciphertext (encoded data) using an algorithm and a key. The algorithm is a set of mathematical operations that scramble the plaintext, and the key is a piece of information used to control the encryption process. Only those who possess the correct key can decipher the ciphertext back into its original plaintext.

In the example above, we are encrypting "HELLO" $\rightarrow$ "KHOOR", mathematically, we would represent this as $C(x) = (x + K) \mod 26$. This is the Caeser Cipher.

There are two main types of encryption:

• Symmetric Key Encryption: In this method, a single secret key is used for both encryption and decryption. Both the sender and the receiver must share this key beforehand. The biggest challenge in symmetric encryption is securely distributing the key to all parties involved. We will talk about this in key exchange algorithms. The cipher described above is a symmetric scheme.

• Asymmetric Key Encryption (Public Key Encryption): Asymmetric encryption uses a pair of mathematically related keys, known as the public key and the private key. The public key is openly distributed and used for encryption, while the private key is kept secret and used for decryption. Messages encrypted with the public key can only be decrypted using the corresponding private key. This eliminates the need for key distribution, making it a popular choice for secure communication.

2. Decryption: Decryption is the reverse process of encryption, where the ciphertext is transformed back into plaintext using the appropriate key. If the correct key is used, the original data can be recovered and read.

Cryptography serves various essential purposes, including:

• Confidentiality: Ensuring that only authorized parties can access and read the information.
• Integrity: Verifying that the data has not been altered or tampered with during transmission.
• Authentication: Verifying the identity of the sender or receiver.
• Non-repudiation: Preventing a sender from denying their actions or the authenticity of the information they sent.

Modern cryptography relies on complex algorithms and mathematical principles to provide robust security. Some widely used cryptographic algorithms include AES (Advanced Encryption Standard) for symmetric encryption and RSA (Rivest-Shamir-Adleman) for asymmetric encryption.

Ciphertext refers to the encrypted form of data or plaintext. It is the output of an encryption algorithm after processing the original data with a specific encryption key. Ciphertext is not easily readable or understandable without the corresponding decryption key.

Mathematically, $Gen()$ refers to generation of keys or the general scheme, $Enc()$ refers to encryption, $Dec()$ refers to decryption.

What is perfect secrecy?

Let $(Gen, Enc, Dec)$ be an encryption scheme with message space $M$ and ciphertext space $C$. For $m, m' \in M$ and $c\in C$, the following holds true.

In this, $Pr$ refers to probability. If this, if $(1)$ holds true, then the probability of a ciphertext $c$ being generated by encrypting $m$ is the same as the probability of $c$ being generated by encrypting $m'$. This is the definition of perfect secrecy.

A theoretical model of perfect secrecy assumes that the ciphertext produced by an encryption scheme provides absolutely no information about the original plaintext, even if the adversary has unlimited computational power and resources. This concept was introduced by Claude Shannon in his landmark paper "Communication Theory of Secrecy Systems" in 1949.

Examples: One time pad (The combination of a truly random and secret key with the plaintext using a bitwise operation, known as XOR. This operation creates an indistinguishable ciphertext that holds no clues about the original message, rendering it immune to any form of cryptanalysis).

One time pad

Encryption: [ C_i = P_i \oplus K_i \quad \text{for } i = 1, 2, \ldots, n ]

Decryption: [ P_i = C_i \oplus K_i \quad \text{for } i = 1, 2, \ldots, n ]

Where:

• ( C_i ) is the ( i )-th character in the ciphertext,
• ( P_i ) is the ( i )-th character in the plaintext,
• ( K_i ) is the ( i )-th character in the secret key,
• ( \oplus ) represents the bitwise XOR operation,
• ( n ) is the length of the plaintext, ciphertext, and secret key.

It is crucial to highlight that the secret key used in the One-time pad should be random, at least as long as the plaintext, and should be used only once. After a successful encryption and decryption process, the secret key must be destroyed, ensuring it is never reused for any other messages. This key destruction practice is essential to maintain the perfect secrecy property of the One-time pad. Reusing the same key or failing to protect it from unauthorized access would compromise the security of the encryption. This is perfectly secret. The practical challenges ($n**2$ problem, key exchange etc.) are discussed later.

Problem Set (opens in a new tab)