CryptographyHistorical ciphersRail fence cipherEncryptionDecryptionAnalysisSubstitution cipherEncryptionDecryptionAnalysisVigenĂ¨re cipherEncryptionDecryptionSymmetric EncryptionSymmetric encryption schemesGood encryption schemesKerchoff's principleAttacker's capabilitiesPseudo-random number generatorsBrute-force attackPreventionPerfect secrecyOne-Time Pad (OTP)EncryptionDecryptionConsistencyProof that OTP satisfies perfect secrecyLimitations of OTPStream ciphersBenefits and drawbacks of stream ciphersRC4InitialisationKey-stream generationBlock ciphersBenefits and drawbacks of block ciphersDESEncryption algorithmDecryption algorithmProblems with DES3DESEncryption algorithmDecryption algorithmProblems with 3DESAES128-bit exampleCryptographic hash functions and MACsOne-way functions (OWFs)ExamplesCollision-resistant functions (CRFs)ExamplesCryptographic hash functionsApplicationsMessage authentication codes (MACs)FunctionalityBlock ciphers and message integrityInitialisation vectorModes of operationAsymmetric encryptionOnline Trusted Third Party (TTP)FunctionalityProblemsPublic-key cryptographyFunctionalityNumber theoryPrimesRelative primesModular inversionTheoremTheorem (Euler)Theorem (Euler)Intractable problemsInteger factorisation (into prime factors)RSAPDiscrete logarithmic problem (DLOG)Diffie-Hellman problem (DHP)Diffie-Hellman (DH) protocolFunctionalityProblemsRSA trapdoor permutationFunctionalityConsistencyProblemsISO standardElGamal (EG)FunctionalityKey generationEncryptionDecryptionConsistencyDigital signaturesFunctionalityPropertiesSecurityAdvantages over MACsRSA signaturesFunctionalityConsistencyProblemsPublic key infrastructureDistribution of public keysPublic key certificatesCryptographic protocolsExample of a logical attackAuthentication and key agreement protocolsForward secrecyStation-to-Station protocolFunctionalityResources

**Cryptography** refers to secure information and communication techniques derived from algorithms that transform messages through various means such as modular arithmetic or bitwise operations, in ways that are difficult to decipher.

**Note**: General cryptography may refer to other things, but modern cryptography is typically heavily based on mathematical theory, and most commonly refers to plain-text encryption and decryption.

- Shared secret: key

Plaintext written in columns of size . The cipher text is the concatenation of the resulting rows.

Example:

Ciphertext written in rows of size .

- Key space size :
**open to brute force attack**due to small key space.

- Shared secret: a permutation of the set of characters.

Apply to each character of the plaintext.

Apply to each character of the ciphertext.

- Key space size :
**brute force infeasible**!

- Shared secret: key - a word over the English alphabet

Break the plaintext in blocks, and encrypt each block as follows:

Concatenate the resulting blocks to obtain the ciphertext.

Break the ciphertext in blocks, and decrypt each block as follows:

A **symmetric cipher** consists of two algorithms:

**Encryption algorithm**:**Decryption algorithm**:

Such that , and :

That is, decrypting an encrypted message with the decryption algorithm , using the same key that was used to encrypt the original message, will produce the original message .

The key is intended to be kept secret, between the sender and receiver of the message .

An encryption scheme is secure against a given attacker if this attacker cannot:

- Recover the secret key .
- Recover the plaintext underlying a ciphertext .
- Recover any bits of the plaintext underlying a ciphertext .

**Kerchoff's principle** states that a cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

- The encryption and decryption algorithms are public.
- The security relies entirely on the secrecy of the key.

- A cryptographic scheme is secure under some assumptions, or against a certain type of attacker.
- A cryptographic scheme may be vulnerable to certain types of attacks, but not others.

An attacker might have access to:

**Known ciphertext attack**: Some ciphertexts , all of which were encrypted using the same key.The goal is to determine the plaintext for one or more of these ciphertexts or, better yet, to discover the key.

**Known plaintext attack**: Some plaintext/ciphertext pairs such that â€”each plaintext was encrypted using the same key .The goal is to determine the key .

**Chosen ciphertext attack**: Access to a decryption oracle (can maybe trick a user to decrypt ciphertexts of his choice)â€”can choose one or more ciphertext messages and get the plaintext that is associated with each one, based on the use of the same key .**Chosen plaintext attack**: Access to an encryption oracle (can maybe trick a user to encrypt messages of his choice)â€”can choose one or more plaintext messages and get the ciphertext that is associated with each one, based on the use of the same key .**Computational power**: Unlimited, polynomial, or realistic () computational power.

A **pseudo-random number generator** is a method for generating a sequence of numbers that approximates the properties of a random sequence.

A desired property of a random sequence is that the numbers it generates are uniformly distributed.

In a **brute-force** attack, the attacker tries all possible keys . This requires some knowledge about the structure of plaintext.

The main form of prevention for brute-force attacks is to make exhaustive searches infeasible:

- should be sufficiently large - keys should be sufficiently long.
- Keys should be sampled uniformly at random from

A cipher over satisfies **perfect secrecy** if for all messages of the same length , and for all ciphertexts :

Where:

- ( is a key sampled uniformly at random from the key-space )
- is some
negligible quantity

- Shared secret: key , where (bit-string of length )

Perform a logical XOR () operation with the key and the message:

Perform a logical XOR operation with the key and the ciphertext:

First note that and :

Where:

Thus, , and :

**Key length**: The key must be as long as the plaintext.**Getting true randomness**: The key should not be guessable from an attacker:**Example**:`00000000`

or`11111111`

would be bad keys in .Perfect secrecy does not capture all possible attacks.

Two-time pad attacks.

Malleable.

The motivation behind **stream ciphers** is to make the OTP practical.

In a **stream cipher**, each plaintext digit is encrypted one at a time with the corresponding digit of the key-stream, to give a digit of the ciphertext stream.

**Idea**: Use a**pseudo-random**key rather than a really random key.The key will not really be random, but will look random.

The key will be generated from a key seed using a

**Pseudo-Random Generator (PRG)**:**With**: ( much less than )

**Encryption**: Using a PRG:**Decryption**: Using a PRG:

Example: VigenĂ¨re cipher, RC4.

Benefits | Drawbacks |
---|---|

Speed of transformation: Stream cipher algorithms are linear in time. | Low diffusion: All information of a plaintext symbol is contained in a single ciphertext symbol. |

Low error propagation: An error in encrypting one symbol is likely not to affect subsequent symbols. | Susceptible to insertions: An active interceptor who breaks the algorithm might insert text that looks authentic. |

**RC4** is a stream cipher invented by Ron Rivest in 1987.

Consists of 2 phases:

**Initialisation**and**key-stream generation**Main data structure: Array of 256 bytes.

Used in HTTPS and WEP

**Weaknesses**:- First bytes are biased
**Solution**: Drop the first 256 generated bytes. - Subject to related keys attacks
**Solution**: Choose randomly generated keys as seeds.

- First bytes are biased

`â€‹x1``for i = 0 to 255 do`

2` S[i] = i `

3`end`

4`â€‹`

5`j = 0`

6`â€‹`

7`for i = 0 to 255 do`

8` j = j + S[i] + K[i (mod |K|)] (mod 256)`

9` swap(S[i], S[j])`

10`end`

`xxxxxxxxxx`

61`while generatingOutput`

2` i = i + 1 (mod 256)`

3` j = j + S[i] (mod 256)`

4` swap(S[i], S[j])`

5` output(S[S[i] + S[j] (mod 256)])`

6`end`

In a **block cipher**, the plaintext is divided into blocks, and each block (group of plaintext symbols) is encrypted one by one - rather than encrypting one symbol at a time like stream ciphers do.

- Most modern symmetric encryption algorithms are block ciphers.
- Block sizes vary (e.g. 64 bits for DES, 128 bits for AES).

A block cipher with parameters and is a pair of deterministic algorithms such that:

- Encryption
- Decryption

Example: 3DES () and AES ().

Benefits | Drawbacks |
---|---|

High diffusion: Information from one plaintext symbol is diffused into several ciphertext symbols. | Slowness of encryption: An entire block must be accumulated before encryption or decryption can begin. |

Immune to tampering: Difficult to insert symbols without detection. | Error propagation: An error in one symbol may corrupt the entire block. |

The **Data Encryption Standard (DES)** is a symmetric-key block cipher

- 64 bit key (8 bits parity, 56 bits actual data - every 8th bit is a parity bit)
- 64 bit plaintext, 64 bit ciphertext
- 16 rounds, each accepting a 64-bit input and giving a 64-bit output.

Construct the key by inserting a parity bit after every 7th bit of the actual data.

This expands from 56-bit to 64-bit.Generate 16 48-bit sub-keys, from this new 64-bit key.

Read here for more information about generating sub-keys.Permute the plaintext.

Divide the plaintext into two 32-bit halves, and .

For each of the 16 rounds, starting from :

**Round**- : The left half of the input for the next round, , becomes the right half of the input for the current round, .
- : The right half of the input for the next round, , becomes the result of taking the logical XOR between the left half of the input for the current round, , and the output of the mangler function accepting the sub-key for the current round, , and the right half of the input for the current round, .

The**mangler**function scrambles half a block together with the 48-bit sub-key, .

Swap the left and right halves of the output from the final round.

Permute the resulting text, which produces the ciphertext.

Perform the encryption algorithm again, but using the sub-keys in reverse.

- Vulnerable to exhaustive key search (brute-force) attacks.
- 3DES solves this by increasing key space to 168 bits.

**3DES** encryption chains 3 DES operations with 3 different DES keys, .

- 3 different 64-bit (56-bit data + 8-bit parity) DES keys.
- 64 bit plaintext , 64 bit ciphertext

**Note**: If , then 3DES works the same as single DES.

Where and are the encryption and decryption algorithms for DES.

- 3 times as slow as DES.

**Advanced Encryption Standard (AES)** is a symmetric-key block cipher that operates on:

- 128-bit blocks (128-bit plaintext and ciphertext)
- 128, 192 or 256 bit keys (AES-128, AES-192 or AES-256)

AES is **stronger** and **faster** than 3DES.

AES-128 proceeds in **ten** rounds. Each round performs an invertible transformation on a 128-bit array, called **state**.

The initial state is the XOR of the plaintext with the key .

Round (where ) receives state as input and produces state .

The ciphertext is the output of the final round.

Where each round is built from four basic steps:

**SubBytes**step: An S-box substitution step.**ShiftRows**step: A permutation step.**MixColumns**step: A matrix multiplication (Hill cipher) step.**AddRoundKey**step: An XOR step with a**round key**derived from the 128-bit encryption key.

A function is a **one-way function** if for all , there is no efficient algorithm which can compute such that .

- Constant functions
**are not**OWFs,

since any is such that . - The successor function in
**is not**a OWF,

given , it is easy to retrieve . - Multiplication of large primes
**is**a OWF:

integer factorisation is a hard problem - given where and are primes, it is hard to retrieve and .

A function is **collision-resistant** if there is no efficient algorithm that can find two messages and such that .

- Constant functions
**are not**CRFs,

for all and , . - The successor function in
**is**a CRF,

the predecessor of a positive integer is unique. - Multiplication of large primes
**is**a CRF:

every positive integer has a unique prime factorisation.

A **cryptographic hash function** is a function that satisfies the following four properties:

- it is easy to compute the hash value for any given message
- it is hard to retrieve a message from its hashed value (OWF)
- it is hard to find two different messages with the same hash value (CRF)

Examples of cryptographic hash functions include `MD5`

, `SHA-256`

, `Whirlpool`

and `bcrypt`

.

**File integrity**: Hashes are sometimes posted along with files on read-only spaces to allow verification of integrity of the files.**Password verification**: Instead of storing passwords in cleartext, only the hash digest of each password is stored. To authenticate a user, the password presented by the user is hashed and compared with the stored hash.

A **message authentication code (MAC)** is a short piece of information used to authenticate a messageâ€”in other words, to confirm that the message came from the stated sender and has not been changed.

Essentially, a MAC is an encrypted checksum generated on the underlying message that is sent along with a message to ensure message authentication.

**Figure 1**: The process of MAC authentication.

*Note: This example assumes a cleartext message.* (source)

As shown in Figure 1:

The sender uses some publicly known MAC algorithmâ€”an algorithm which accepts the input message and the secret key and produces a MAC value.

Similarly to a hash function, a MAC function also compresses an arbitrary long input into a fixed length output.

**The major difference between hash and MAC is that MAC uses a secret key during the compression.**The sender forwards the message along with the MAC.

**Note**: In Figure 1 this is simply a cleartext message, but in reality (if confidentiality) is necessary, this would be encrypted. If this is the case, then the MAC should always be computed on the ciphertext (two different keys should be used in this case).Once the message and MAC is received, the receiver feeds the received message and the shared secret key into the same MAC algorithm that was used by the sender, and re-computes the MAC value.

The receiver now checks equality of the freshly-computed MAC with the MAC received from the sender.

If they match, then the receiver accepts the message and assures themself that the message has been sent by the intended sender.

If the computed MAC does not match the MAC sent by the sender, the receiver cannot determine whether it is the message that has been altered, or the origin that has been falsified.

As a bottom-line, a receiver safely assumes that the message is not genuine.

Let be a block cipher. We build a MAC using as follows:

However, block ciphers can usually only process 128 or 256 bits. To overcome this limitation, it is possible to split plaintext and chain encryption operations together, often by using logical operators such as XOR.

**Figure 14**: Construction of a MAC with CBC mode encryption (ECBC-MAC).

*Note: A zero initialisation vector is always used in this mode of operation.* (source)

An **initialisation vector (IV)** is a block of bits that is used by several modes to randomise the encryption and hence produce distinct ciphertexts even if the same plaintext is encrypted multiple times.

A **mode of operation** is an algorithm that uses a block cipher to provide information security such as **confidentiality** or **authenticity**.

Example: CBC, ECB and CTR.

**Asymmetric encryption**, also known as **public-key cryptography**, is a cryptographic system that encrypts and decrypts data using two separate yet mathematically connected cryptographic keysâ€”these keys are known as a **public key** and a **private key**.

**Online Trusted Third Party (TTP)** is a method of establishing keys through the use of a **trusted third party**.

- Users
- TTP,
- Encryption and decryption algorithms and
- Each user has a shared secret key with
- and can establish a key with the help of

Suppose wishes to communicate with securely, but needs to establish a key first.

sends a message to , saying that they wish to communicate with .

generates a new secret key .

sends the new key to:

- in the form of an encrypted message .
- in the form of an encrypted message .

To acquire the shared secret key ,

- decrypts the message using :
- decrypts the message using :

and can now communicate using .

The TTP can read all messages between and .

Since TTP generated , it can intercept and read any messages went between and , since they are also using .

The TTP can impersonate any user.

Since TTP has a key shared with every user, it can generate a fake channel between and .

Key generation algorithm:

Generates where:

- is a secret (
**private**) key for decryption - is a shared public key for encryption

- is a secret (
Encryption algorithm

Decryption algorithm

Such that and , .

Suppose user wishes to send a message to .

- encrypts the message , using a shared public key from , and sends the resulting ciphertext to .
- uses their own secret private key to decrypt the ciphertext .

It is important that is never shared, and that .

- is a
**prime**if its only divisors are and - Every has a
**unique factorisation**as a product of prime numbers (prime factors)

are

**relative primes**if they have no common factors**Euler's totient function**is the number of integers that are relatively prime with :**Example**:- For prime:
- For and primes:

**Note**: Euler's totient function is multiplicativeâ€”if , then

Let . We define .

The inverse of is s.t. . We denote the inverse of .

Example:

- in :
- in : has no inverse in

Let , . has an inverse in iff .

Let . We define .

Example:

**Note**:

For all prime, is a cyclic group, i.e.

Where is a **generator** of . See here.

**Input**:**Output**: such that

**Input**:- such that with prime
- such that

**Output**:

**Input**:- prime
- generator of

**Output**: such that

**Input**:prime

generator of