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

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.

Historical ciphers

Rail fence cipher

Encryption

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

Example:

Decryption

Ciphertext written in rows of size .

Analysis

Substitution cipher

Encryption

Apply to each character of the plaintext.

Decryption

Apply to each character of the ciphertext.

Analysis

Vigenère cipher

Encryption

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

Concatenate the resulting blocks to obtain the ciphertext.

Decryption

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

Symmetric Encryption

Symmetric encryption schemes

A symmetric cipher consists of two algorithms:

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 .

Good encryption schemes

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

Kerchoff's principle

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

Attacker's capabilities

An attacker might have access to:

Pseudo-random number generators

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.

Brute-force attack

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

Prevention

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

Perfect secrecy

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

Where:

One-Time Pad (OTP)

Encryption

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

Decryption

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

Consistency

Proof that OTP satisfies perfect secrecy

First note that and :

Where:

Thus, , and :

Limitations of OTP

Stream ciphers

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.

Example: Vigenère cipher, RC4.

Benefits and drawbacks of stream ciphers

BenefitsDrawbacks
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

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

Initialisation
Key-stream generation

Block ciphers

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.


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

Example: 3DES () and AES ().

Benefits and drawbacks of block ciphers

BenefitsDrawbacks
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.

DES

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

Encryption algorithm
  1. Construct the key by inserting a parity bit after every 7th bit of the actual data.
    This expands from 56-bit to 64-bit.

  2. Generate 16 48-bit sub-keys, from this new 64-bit key.
    Read here for more information about generating sub-keys.

  3. Permute the plaintext.

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

  5. 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, .
  6. Swap the left and right halves of the output from the final round.

  7. Permute the resulting text, which produces the ciphertext.

Decryption algorithm

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

Problems with DES

3DES

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

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

Encryption algorithm

Where and are the encryption and decryption algorithms for DES.

Decryption algorithm
Problems with 3DES

AES

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

AES is stronger and faster than 3DES.

128-bit example

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

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

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

  3. The ciphertext is the output of the final round.

Where each round is built from four basic steps:

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

Cryptographic hash functions and MACs

One-way functions (OWFs)

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

Examples

Collision-resistant functions (CRFs)

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

Examples

Cryptographic hash functions

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

Examples of cryptographic hash functions include MD5, SHA-256, Whirlpool and bcrypt.

Applications

Message authentication codes (MACs)

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.

Functionality


Figure 1: The process of MAC authentication.
Note: This example assumes a cleartext message. (source)

 

As shown in Figure 1:

  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.

  2. 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.

  3. 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).

  4. 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.

  5. 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.

Block ciphers and message integrity

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)

Initialisation vector

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.

Modes of operation

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

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)

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

Functionality

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

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

  2. generates a new secret key .

  3. sends the new key to:

    • in the form of an encrypted message .
    • in the form of an encrypted message .
  4. To acquire the shared secret key ,

    • decrypts the message using :
    • decrypts the message using :
  5. and can now communicate using .

Problems

Public-key cryptography

Such that and , .

Functionality

Suppose user wishes to send a message to .

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

It is important that is never shared, and that .

Number theory

Primes

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

Relative primes

  1. are relative primes if they have no common factors

  2. 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 .

Modular inversion

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

Example:

Theorem

Let , . has an inverse in iff .

Let . We define .

Example:

Note:

Theorem (Euler)
Theorem (Euler)

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

Where is a generator of . See here.

Intractable problems

Integer factorisation (into prime factors)
RSAP
Discrete logarithmic problem (DLOG)
Diffie-Hellman problem (DHP)