Introduction to Cryptography

1) Attacks Based on Security Goals They Impact

Each cryptographic attack is designed to target specific security goals, threatening the confidentiality, integrity, or availability of data.

1. Confidentiality Attacks

• Snooping: Unauthorized access to data without modifying it. The attacker reads or monitors the information.
  Example: Intercepting unencrypted emails to steal sensitive information like PINs.
• Traffic Analysis: Monitoring traffic patterns (e.g., size, frequency) to gather insights, even if data is encrypted.
  Example: Monitoring encrypted military communications to predict troop movements.

2. Integrity Attacks

• Modification: Altering the contents of a message or file. Unauthorized changes to data violate its integrity.
  Example: Modifying a bank transaction to transfer money to the attacker’s account.
• Masquerading (Spoofing): The attacker pretends to be someone else to gain unauthorized access.
  Example: An attacker impersonates a system administrator to steal sensitive data.
• Replay Attack: Re-transmitting a previously captured message to trick the system into accepting it as legitimate.
  Example: Re-sending a captured financial transaction to duplicate an authorized payment.
• Repudiation: Denying having performed an action in communication, often leading to disputes.
  Example: A person denies having made an online payment, even though the transaction was completed.

3. Availability Attacks

• Denial of Service (DoS): Preventing legitimate users from accessing services by overwhelming the system with excessive requests.
  Example: Overloading a server with traffic, making a website unavailable to users.

2) Attacks Based on the Type of Damage

Cryptographic attacks can also be classified based on whether they involve directly damaging data or simply stealing information without modification.

1. Active Attacks:
   • In active attacks, the attacker aims to modify or disrupt data and services, causing harm to the system.
   • Example: An attacker intercepting and altering a message in transit to change the meaning.
   • Security Goals Compromised: Integrity and Availability.
2. Passive Attacks:
   • In passive attacks, the attacker’s goal is to observe and collect information without altering or disrupting the data.
   • Example: Monitoring network traffic to capture unencrypted usernames and passwords.
   • Security Goal Compromised: Confidentiality.

3) Attacks Based on Mathematical Viewpoint (Cryptographic Attacks)

Cryptographic attacks can also exploit mathematical flaws in cryptographic algorithms. These types of attacks are more technical and focus on breaking the encryption itself.

1. Cryptoanalytic Attacks:
   • These attacks use mathematical techniques such as statistical analysis to find vulnerabilities in cryptographic algorithms and deduce the secret key.
   • Example: Factoring large prime numbers to break the RSA encryption algorithm.
2. Non-cryptoanalytic Attacks:
   • These attacks don’t target the mathematical weaknesses of cryptography but exploit other vulnerabilities, such as poor implementation or human error.
   • Example: Social engineering attacks where attackers trick users into revealing their passwords.

Cryptoanalytic Attacks

Cryptoanalytic attacks focus on analyzing the encrypted data (cipherli) to extract information or break the encryption without knowing the key.

1. Cipherli-only Attack:
   • In this attack, the attacker only has access to the cipherli and tries to deduce the encryption key or original message.
   • Example: Intercepting encrypted emails and trying to decrypt them using statistical methods.
2. Known-plainli Attack:
   • Here, the attacker has access to both the plainli and its corresponding cipherli, allowing them to analyze how the encryption process works.
   • Example: If an attacker knows a common word in a message, they can use that to decrypt other parts of the message.
3. Chosen-plainli Attack:
   • The attacker chooses specific plainlis and encrypts them to study how the algorithm works.
   • Example: Encrypting the word "password" using different encryption methods to study patterns in the cipherli.
4. Chosen-cipherli Attack:
   • The attacker can select specific cipherlis and attempt to decrypt them, using the results to understand the encryption system.
   • Example: Injecting fake cipherlis into a system to gather insights into its decryption process.

Non-cryptoanalytic Attacks

Non-cryptoanalytic attacks focus on vulnerabilities outside the cryptographic algorithms, such as poor security practices or flaws in the system setup.

Integer Arithmetic

Integer arithmetic refers to mathematical operations performed on integers (whole numbers), which include positive numbers, negative numbers, and zero. Unlike floating-point arithmetic, which can handle fractions and decimals, integer arithmetic only deals with whole numbers.

• Set of Integers: The set of integers is denoted by Z, and it includes all integral numbers from negative infinity to positive infinity. This set can be written as:
  Z = { ..., -2, -1, 0, 1, 2, ... }

Division in Integer Arithmetic

When dividing two integers, we may not always get a whole number. Instead, we can express the division in terms of quotient and remainder. For two integers a (the dividend) and n (the divisor), the operation can be described by the equation:

• a = q × n + r
• Where:
  • a = dividend
  • n = divisor
  • q = quotient
  • r = remainder
• The remainder r will always be less than the divisor n and greater than or equal to zero.

Example:

• 100 divided by 9:
  • a = 100, n = 9
  • The quotient q is 11, and the remainder r is 1.
  • 100 = 11 × 9 + 1
• 122 divided by 11:
  • a = 122, n = 11
  • The quotient q is 11, and the remainder r is 1.
  • 122 = 11 × 11 + 1

Restrictions in Integer Arithmetic Division

• The divisor n must be a positive integer: n > 0
• The remainder r must be non-negative: r ≥ 0

These restrictions ensure consistency in how we define quotient and remainder.

Greatest Common Divisor (GCD)

The greatest common divisor (GCD) of two integers a and b is the largest integer that divides both a and b without leaving a remainder. It helps in simplifying ratios or fractions and is essential in cryptography for algorithms like RSA.

• For example, the GCD of 24 and 18 is 6, because 6 is the largest integer that divides both numbers evenly.

Euclidean Algorithm

The Euclidean Algorithm is a method to compute the GCD of two integers. It is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number.

Steps:

• Divide a by b, and get the remainder r.
• Replace a with b, and b with r.
• Repeat the process until the remainder becomes zero.
• The last non-zero remainder is the GCD.

Example:

• Let’s compute the GCD of 252 and 105 using the Euclidean Algorithm:
  • 252 ÷ 105 = 2 (quotient) with a remainder of 42 (i.e., 252 = 2 × 105 + 42)
  • 105 ÷ 42 = 2, remainder 21
  • 42 ÷ 21 = 2, remainder 0
  • The GCD is 21.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value—the modulus. This is widely used in cryptography, computer science, and number theory.

In modular arithmetic, we work with the remainder of a division operation. If we divide a number by another (called the modulus), the remainder is the result of the modular operation. The notation is:

• a ≡ b (mod n)
• Where:
  • a is the dividend (the number we are dividing)
  • b is the remainder
  • n is the modulus (the number by which we are dividing)

Understanding Modular Arithmetic

• a ≡ b (mod n) means that when a is divided by n, the remainder is b.
• If two numbers have the same remainder when divided by a modulus n, they are considered congruent.

Example:

• 7 ≡ 3 (mod 4):
  • When you divide 7 by 4, the quotient is 1 and the remainder is 3.
• 10 ≡ 1 (mod 3):
  • When you divide 10 by 3, the quotient is 3 and the remainder is 1.
• 15 ≡ 0 (mod 5):
  • When you divide 15 by 5, there is no remainder, so it is congruent to 0 mod 5.

Applications in Cryptography

Modular arithmetic plays a crucial role in cryptography. It is used in algorithms like RSA, Diffie-Hellman, and elliptic curve cryptography, which rely on the difficulty of reversing modular exponentiation without knowing the private key.

Congruence

Congruence is a fundamental concept in modular arithmetic that deals with the relationship between two integers. Two numbers are said to be congruent modulo a number if they leave the same remainder when divided by that number.

The notation for congruence is:

• a ≡ b (mod n)
• Where:
  • a and b are integers
  • n is the modulus
  • If a ≡ b (mod n), it means that when both a and b are divided by n, they leave the same remainder.

Understanding Congruence

• If two numbers are congruent modulo n, their difference is divisible by n.
• a ≡ b (mod n) implies that (a - b) is divisible by n, meaning a - b = kn, where k is an integer.

Example of Congruence:

• 12 ≡ 5 (mod 7):
  • When you divide both 12 and 5 by 7, the remainder is the same (5).
  • Also, 12 - 5 = 7, which is divisible by 7.
• 20 ≡ 2 (mod 6):
  • When 20 and 2 are divided by 6, both give the same remainder (2).
  • Additionally, 20 - 2 = 18, which is divisible by 6.

Congruence and Cryptography:

• Congruence plays a key role in cryptographic algorithms, especially in public-key cryptography like RSA, where large integers and modular exponentiation are used.
• In RSA encryption, for instance, the message is encrypted using the equation C ≡ M^e (mod n), and the decryption follows a similar form with modular arithmetic.

Matrices

A matrix is a rectangular array of numbers or symbols arranged in rows and columns. It is a fundamental concept in mathematics used for various applications, including solving systems of linear equations, transformations in geometry, and cryptography.

Basic Terminology:

• Order of a Matrix: The size of a matrix is described by the number of rows and columns it has. A matrix with m rows and n columns is called an m x n matrix.
• Element of a Matrix: Each value in the matrix is called an element, usually denoted by a_ij, where i is the row number and j is the column number.

Types of Matrices:

• Square Matrix: A matrix with the same number of rows and columns (e.g., 3x3 matrix).
• Identity Matrix: A square matrix where all the diagonal elements are 1, and all other elements are 0.
• Zero Matrix: A matrix where all elements are 0.
• Diagonal Matrix: A matrix where all non-diagonal elements are 0.
• Transpose of a Matrix: The matrix obtained by switching the rows and columns of a given matrix.

Matrices in Cryptography:

• Matrices are often used in cryptography, particularly in algorithms like the Hill Cipher, where they are employed to encrypt and decrypt messages using matrix multiplication.

Symmetric Cryptography

Symmetric cryptography, also known as secret key cryptography or private key cryptography, is a straightforward encryption technique that uses a single key for both encryption and decryption. This means that the same key is used to transform plaintext into ciphertext and vice versa. The security of this method relies on keeping the key secret between the communicating parties.

The most popular symmetric key cryptography system is DES (Data Encryption Standard), which has been widely used for securing data. However, due to advancements in computational power, DES has been largely replaced by more secure algorithms like AES (Advanced Encryption Standard).

Asymmetric Cryptography

Asymmetric cryptography, also known as public key cryptography, utilizes two different keys for encryption and decryption. One key, known as the public key, is shared openly and can be used by anyone to encrypt data. The second key, known as the private key, is kept secret by the owner and is used to decrypt the data that was encrypted with the corresponding public key.

• Public Key: This key is widely distributed and available to anyone. It is used to encrypt data.
• Private Key: This key is kept confidential by the owner. It is used to decrypt data that was encrypted with the corresponding public key.

Note: A message encrypted using a public key can only be decrypted using the corresponding private key. Conversely, a message encrypted with a private key can only be decrypted using the corresponding public key.

Popular asymmetric key algorithms include RSA (Rivest–Shamir–Adleman), DSA (Digital Signature Algorithm), and elliptic curve cryptography (ECC).

Hash Functions

Hash functions are cryptographic algorithms that generate a fixed-size output (hash value) from variable-size input data. The primary purpose of a hash function is to ensure data integrity by producing a unique hash value for unique input data. Even a small change in the input data will result in a significantly different hash value, making hash functions useful for detecting alterations or corruption in data.

• Hash functions are one-way functions, meaning they cannot be reversed to retrieve the original data from the hash value.
• Common hash functions include MD5 (Message Digest Algorithm 5), SHA-1 (Secure Hash Algorithm 1), and SHA-256 (Secure Hash Algorithm 256).

Example: Password Storage and Verification

When a user creates a password for their account, it is not stored directly in the database. Instead, the password is processed through a hash function to produce a hash value. This hash value is then stored in the database.

Here's how it works in practice:

1. User Registration: When a user sets a password, the password is hashed using a hash function (e.g., SHA-256) to produce a hash value. For example, if the password is "mypassword", the hash function generates a hash value like "5e884898da28047151d0e56f8dc6292773603d0d" (this is just a sample hash).
2. Storing the Hash: The resulting hash value is stored in the database, not the actual password. This ensures that the plaintext password is not exposed even if the database is compromised.
3. User Login: When the user attempts to log in, they enter their password. This password is again processed through the same hash function to produce a hash value.
4. Verification: The hash value generated from the entered password is compared with the hash value stored in the database. If the two hash values match, the password is correct, and the user is granted access. If they do not match, access is denied.

By using hash functions, passwords are kept secure and confidential, as the original password cannot be directly retrieved from the hash value.

Caesar Cipher

The Caesar cipher is one of the oldest and simplest encryption techniques, named after Julius Caesar, who reportedly used it to protect his messages. This cipher operates by shifting each letter in the plaintext a fixed number of places down the alphabet. For example, with a shift of 3:

• A becomes D
• B becomes E
• C becomes F

This means that a message like "HELLO" would be encrypted as "KHOOR" with a shift of 3. The process is reversible: the same key can be used to decrypt the ciphertext back to the original plaintext.

The simplicity of the Caesar cipher makes it an excellent introduction to the concepts of encryption and decryption, but it also highlights vulnerabilities associated with classical ciphers, such as the ease of frequency analysis. Despite its weaknesses, the Caesar cipher remains a fundamental educational tool in the study of cryptography.

Below is a visual representation of the Caesar cipher with a shift of 3:

Confusion and Diffusion

Encryption algorithms rely heavily on two important properties to ensure the security of data: confusion and diffusion. These concepts were introduced by Claude Shannon and play a key role in making encryption more secure by hiding patterns between plaintext and ciphertext.

• Confusion: This property focuses on making the relationship between the encryption key and the ciphertext as complex as possible. In other words, confusion aims to obscure the connection between the plaintext and the resulting ciphertext. Even if a third party has access to the ciphertext, they should be unable to determine the plaintext or the key used for encryption. A cipher that relies heavily on confusion makes it difficult to trace how specific keys relate to the ciphertext, protecting the data from being decrypted easily.
• Diffusion: The diffusion property ensures that any small change in the plaintext leads to significant and unpredictable changes in the ciphertext. This is achieved by making each bit of the plaintext affect multiple bits of the ciphertext. If even a single bit of the plaintext is altered, the corresponding ciphertext should differ drastically, enhancing the security of the encryption.

Both confusion and diffusion are essential for building a strong encryption system. While confusion hides the relationship between the key and the ciphertext, diffusion spreads out the influence of each bit across the ciphertext to protect against pattern recognition.

Stream Ciphers

Stream ciphers encrypt data one bit or one byte at a time, processing the input continuously as it is fed into the encryption algorithm. This method makes stream ciphers efficient for real-time applications, where data is transmitted in a steady stream, such as in network communications or streaming services.

• In a stream cipher, each plaintext digit is encrypted individually, using a corresponding digit from a keystream. The key is often combined with the plaintext using the XOR (exclusive OR) operation, resulting in a ciphertext stream.
• The process is simple and fast, making stream ciphers ideal for environments where speed is critical.
• Stream ciphers typically use confusion as their primary security property, ensuring that the relationship between the key and ciphertext is as obscured as possible.

Stream Cipher Example

A classic example of a stream cipher is the Vernam cipher. In this method, each bit of the plaintext is XORed with a corresponding bit of the key stream to produce the ciphertext.

Block Ciphers

Unlike stream ciphers, block ciphers work by dividing the plaintext into fixed-size blocks and encrypting each block individually. These blocks can vary in size, with common block sizes being 64 bits or 128 bits, depending on the algorithm used.

• A block cipher encrypts entire blocks of data at once, rather than processing the data bit by bit or byte by byte as stream ciphers do.
• Block ciphers utilize both confusion and diffusion properties, making them highly secure by obscuring both the relationship between the key and the ciphertext, and ensuring that even minor changes in the plaintext result in drastic changes in the ciphertext.

Comparing Stream and Block Ciphers

Both stream and block ciphers are widely used in cryptography, but they differ in how they process data and the encryption methods they use. The choice between the two depends on the specific requirements of the application, such as speed, security, and the nature of the data being encrypted.

• Input Size: Stream ciphers process data bit by bit or byte by byte, whereas block ciphers process data in fixed-size blocks.
• Design Complexity: Stream ciphers tend to have a more complex design due to the need for continuous encryption, while block ciphers use more structured designs based on predefined block sizes.
• Encryption Principle: Stream ciphers primarily use confusion, while block ciphers rely on both confusion and diffusion.
• Speed: Stream ciphers are generally faster than block ciphers because they encrypt data continuously without needing to wait for a full block of data.
• Decryption: Stream ciphers often use simple XOR operations for decryption, while block ciphers use more complex decryption algorithms that reverse the encryption process.