Introduction to Cryptography

Cryptography is the area of study that involves secure communication between parties, especially over insecure channels. The fundamental objective of cryptography is to enable two individuals to communicate securely, regardless of the vulnerabilities of the communication medium. This is commonly illustrated with two characters, Alice and Bob, who are often used to represent the communicating parties. Cryptography aims to provide confidence in secure communication even on platforms that can be accessed by third parties, often referred to as adversaries or attackers. These channels include telephone lines, the Internet, email, social media like Facebook, and messaging applications such as WhatsApp.

The Communication Scenario

For instance, consider a scenario where Alice is in Delhi, India, and Bob is in New York, USA. Alice wants to send Bob a confidential message—her age, for example. Suppose Alice's age is 24. If Alice sends a message stating her age over a public communication medium, a third party, humorously named Oscar in this example, may intercept this message. Oscar represents a malicious actor who can monitor the communication channel and access Alice's information. To illustrate, if Alice openly says, "Hey, my age is 24," Oscar will know her age, which violates Alice's intention to maintain her privacy.

The Role of Cryptography

Alice then employs cryptographic techniques to protect her communication. She can modify the plaintext (the original message, which in this case is 24) to disguise it before transmission. For example, Alice may create a simple transformation by reversing the digits of her age, where 24 becomes 42. Alice then sends this altered information to Bob. However, if Oscar understands the reversing mechanism, he will still uncover Alice's real age.

Alternatively, Alice can take a different approach, such as adding a number to her age; let’s say she adds 26 to 24, resulting in 50, and sends this number to Bob. To Oscar, who intercepts the message, it appears that Alice has sent the number 50, which could lead Oscar to the wrong conclusion about Alice's age. Bob, however, knows the key (the number 26 in this case) and can subtract it from 50 to retrieve the original plaintext of 24. The original message (24) is referred to as the plaintext, the number Alice sends (50) is called the ciphertext, and the operation of transforming plaintext into ciphertext is known as encryption. Conversely, Bob's process of converting ciphertext back to plaintext is termed decryption.

Key Concepts

The key (in this case, 26) plays a crucial role in secure communication. It is a shared secret between Alice and Bob that is not disclosed to Oscar. If Alice and Bob were to communicate via telephone to discuss what their key would be, that information would also be overheard by Oscar, thus defeating the purpose of their secure communication. Therefore, sharing the key securely is an essential challenge in cryptographic exchanges.

In summary, Alice’s process of modification is called encryption, and Bob's retrieval process is called decryption. The plaintext is the original information (Alice’s age), and the ciphertext is the modified information delivered over the public channel.

The Implications of Cryptographic Security

Oscar, who has access to the ciphertext (50) but lacks the key (26), cannot easily deduce the original message (24). Although the encryption mechanism (adding 26) is public knowledge, the exact amount added—i.e., the key—remains a secret. Thus, Oscar's objective as a cryptanalyst is to determine both the key and the plaintext.

Components of Cryptography

Cryptography is characterized by several key components:

1. Plaintext: The initial message that Alice intends to send to Bob.
2. Ciphertext: The outcome of the encryption process that is sent over the communication channel.
3. Key: The secret shared between Alice and Bob, which is critical for encryption and decryption.
4. Encryption Algorithm: The procedure used to transform plaintext into ciphertext.
5. Decryption Algorithm: The procedure used to convert ciphertext back into plaintext.

The method illustrated above, where Alice adds a fixed number (the key) to her message, is a simple example of a cryptographic algorithm known as a shift cipher (also referred to later in the lecture).

Symmetric Key vs. Public Key Cryptography

Cryptographic methods can generally be categorized into two main types:

1. Symmetric Key Cryptography: In this method, Alice and Bob share the same secret key (k). The encryption function can be expressed as $c = e_k(m)$, where

   • $m$ is the plaintext,
   • $c$ is the resulting ciphertext,
   • $e<em>k$ is the encryption algorithm. Upon receiving the ciphertext, Bob can retrieve the original message using the decryption function: $m = d</em>k(c)$, where $d_k$ is the decryption algorithm.

2. Public Key Cryptography: This method introduces a system where every participant has a pair of keys (public and private keys), which simplifies the issue of key sharing. Public key cryptography emerged after the development of the Diffie-Hellman key exchange protocol, allowing Alice and Bob to establish a shared key without needing to communicate it directly.

Conventional cryptography techniques, such as the shift cipher, Caesar cipher, and Playfair cipher, fall under symmetric key systems, where a single key is used for both encryption and decryption.

Cryptosystem Definition

A cryptosystem can be formally defined as a five-tuple, represented as:

1. P: The set of all possible plaintexts (plaintext space).
2. C: The set of all possible ciphertexts (ciphertext space).
3. K: The key space, which includes all possible keys.
4. E: The set of encryption algorithms.
5. D: The set of decryption algorithms.
   The functions can be mathematically expressed as follows:

• For the encryption function: $E: P \times K \rightarrow C$ or $c = e_k(m)$ where $m$ is plaintext.
• For the decryption function: $D: C \times K \rightarrow P$ or $m = d<em>k(c)$. The critical condition for a secure cryptosystem is that there must exist encryption and decryption algorithms that adhere to the criteria $d</em>k(c) = m$ if and only if $e_k(m) = c$. Both the encryption and decryption functions should be computationally efficient (ideally polynomial time) to facilitate practical use.

In the upcoming lectures, discussions will delve deeper into classical cryptosystems, including techniques like the shift cipher, Caesar cipher, and substitution cipher.