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.
Plaintext written in columns of size . The cipher text is the concatenation of the resulting rows.
Ciphertext written in rows of size .
Apply to each character of the plaintext.
Apply to each character of the ciphertext.
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:
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:
Kerchoff's principle states that a cryptosystem should be secure even if everything about the system, except the key, is public knowledge.
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:
A cipher over satisfies perfect secrecy if for all messages of the same length , and for all ciphertexts :
- ( is a key sampled uniformly at random from the key-space )
- is some negligible quantity
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 :
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:
11111111would be bad keys in .
Perfect secrecy does not capture all possible attacks.
Two-time pad attacks.
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.
|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
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 ().
|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
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 :
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.
3DES encryption chains 3 DES operations with 3 different DES keys, .
Note: If , then 3DES works the same as single DES.
Where and are the encryption and decryption algorithms for DES.
Advanced Encryption Standard (AES) is a symmetric-key block cipher that operates on:
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:
A function is a one-way function if for all , there is no efficient algorithm which can compute such that .
A function is collision-resistant if there is no efficient algorithm that can find two messages and such that .
A cryptographic hash function is a function that satisfies the following four properties:
Examples of cryptographic hash functions include
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.
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:
To acquire the shared secret key ,
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:
Such that and , .
Suppose user wishes to send a message to .
It is important that is never shared, and that .
are relative primes if they have no common factors
Euler's totient function is the number of integers that are relatively prime with :
- 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 .
- in :
- in : has no inverse in
Let , . has an inverse in iff .
Let . We define .
For all prime, is a cyclic group, i.e.
Where is a generator of . See here.
Output: such that