- Prime Number
- A prime number is a positive ingeger not divisible (without a remainder) by any positive integer other than itself and 1.
- A positive integer can be written uniquely (up to reordering) as a product of prime numbers.
- Example
- 60 = 2 x 2 x 3 x 5 = 2^2 x 3 x 5.
- Coprime
- Two integers a and b are said to be coprime if the only positive integer that evenly divides both of them is 1. That is, the only common positive factor of the two numbers is 1.
- For example, gcd(14,15) = 1 are coprime but gcd(14,21) = 7 are not coprime.
- 1 and -1 are coprimes to all numbers.
- Zm and Z*m
- Let m be a positive interger, then
- Z*m = {a in Zm | gcd(a,m) = 1}
- That is, Z*m is the coprimes to Zm
- Euclid's Algorithm
- Input: integers a and b
- Output: gcd(a,b)
- Euclid's Extended Algorithm
- Input: integers a and b
- Output: integers r,s,t such that sa + tb = r = gcd(a,b)
- GCD (greatest common divisor) of two non-zero integers, is the largest positive integer that divides both numbers without any remainders.
- Example,
- gcd(34,4) = 2
- gcd(17,25) = 1
- Modular Multiplicative Inverse
- The modular multiplicative inverse of an integer a modulo m is an integer x such that
- ax ≡ 1 (mod m)
- The multiplicative inverse of a modulo m exists if and only if a and m are coprime (i.e. gcd(a,m) = 1).
- Example:
- Suppose we wish to find modular multiplicative inverse x of 3 modulo 11
- x ≡ 3^(-1) (mod 11)
- This is the same as finding x such that
- 3x ≡ 1 (mod 11)
- Working in Z11 we find one value of x that satisfies this congruence is 4 because
- 3(4) = 12 ≡ 1 (mod 11)
- Can be computed using the extended euclidian algorithm
- Cryptosystems (P, C, K, E, D)
- P: set of plaintexts
- C: set of ciphertexts
- K: set of keys
- E: for k in K, ek(x) is the encryption rule
- D: for k in K, dk(x) is the decryption rule
- For every k in K, it holds for all m that dk(ek(m)) = m. That is, the decryption of an encryption is the original message, m
- Symmetric-key
- Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both encryption of plaintext and decryption of ciphertext. The keys may be identical or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. This requirement that both parties have access to the secret key is one of the main drawbacks of symmetric key encryption, in comparison to public-key encryption.
- Loosely derived from one-time pads, but with a smaller key. This also means that the proof associated with one-time pads no longer holds
- Encryption and decryption uses the same key
- In a network with n users there are ≈ n^2/2 keys needed
- Classical (symmetric, secret-key) encryption
- Monoalphabetic substitution:
- Shift cipher (or caesar cipher): the alphabet is shifted n number of times down the alphabet. More formally,
- P = C = K = Z26
- Ek(x) = x + k mod 26
- Dk(y) = y - k mod 26
- Affine cipher: each letter is mapped to a numeric equivalent. Each letter is enciphered with the function E(x) = (ax + b) mod (26), where b is the magnitude of the shift and m is the size of the alphabet. More formally,
- P = C = Z26
- K = Z*26 x Z26
- Ek(x) = ax + b mod 26, where k = (a,b)
- Dk(y) = a^(-1)(y-b) mod 26
- Substitution cipher: Letters or blocks of letters are simply substituted with other letters/blocks. The deciphering just reverses the process. More formally,
- P = C = Z26
- K = {pi | pi a permutation of {0,1,2,...,25}}
- Ek(x) = pi(x)
- Dk(y) = pi^(-1)(y)
- Shift cipher (or caesar cipher): the alphabet is shifted n number of times down the alphabet. More formally,
- Polyalphabetic substitution:
- Vigenere cipher: Uses a series of different Caesar ciphers based on the letters of a keyword. For more, see point 3. about vigenere encryption.
- Hill cipher: A polygraphic substitution cipher based on linear algebra. Each letter is represented by a number modulo 26. To encrypt a message, each block of n letters (considered as an n-component vector) is multiplied by an invertible n × n matrix, again modulus 26. To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption. More formally,
- P = C = Zj26
- K = {j x j invertible matrices over Z26}
- Ek(m1,...,mj) = mK, where m = (m1,...,mj)
- Dk(c1,...,cj) = cK^(-1), where c = (c1,...,cj)
- Names used today:
- Stream cipher: A symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream.
- Block cipher: A deterministic algorithm operating on fixed-length groups of bits, called blocks, with an unvarying transformation that is specified by a symmetric key.
- Public-key
- Public-key cryptography, also known as asymmetric cryptography, is a class of cryptographic protocols based on algorithms that require two separate keys, one of which is secret (or private) and one of which is public.
- The message is encrypted using the public key, and can only be decrypted using the private key
- If bob has Alice's public key, he can encrypt a message that only Alice can decrypt via her private key
- Keys cannot be derived from one another
- In a network with n users there needs to be 2n keys
- Needs functions that are easy to compute in one direction (encryption) but difficult in the oppsosite direction (decryption)
- Most systems today are based on either:
- The factoring problem: given n = pq where p and q are large primes, find p and q
- The discrete-logarithm problem: given alpha, m and beta = alpha^3 mod m, find alpha
- When the involved integers are ≈ 1000 bits (~2^1000) the two problems are considered hard to solve
- Common ones are
- RSA
- El-Gamal
- Shannon's theory of perfect secrecy (One-time pad)
- Uses a keystream of completely random digits (all keys are equally likely)
- Key is as long as the plaintext
- One key only used once
- The length of the key makes it very not super usable
- Symmetric-key
- Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both encryption of plaintext and decryption of ciphertext. The keys may be identical or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. This requirement that both parties have access to the secret key is one of the main drawbacks of symmetric key encryption, in comparison to public-key encryption.
- Loosely derived from one-time pads, but with a smaller key. This also means that the proof associated with one-time pads no longer holds
- Authentication can be done with the MAC (message authentication code), for example with CBC-MAC
- MAC = hash function with secret key
- Description of system is public
- x arbitrary length -> fixed length MAC (32...160 bits)
- Computation of MACk(x) "easy" given x and K
- Computation of MACk(x) "hard" given only x, even if a large number of pairs {xi,MACk(xi)}
- MAC attacks:
- Key recovery: find the secret key K
- Forgery: Find of MACk(x) without knowing the secret key K
- Existential forgery: Compute the MAc of some message
- Selective forgery: Compute the MAc of a given message
- HMAC is keyed-hash + MAC, popular with H=SHA-1
- HMAC secure if, SHA-1 is collision resistant for secret initial value, and H is a secure MAC for one-block messages
- Public-key
- Public-key cryptography, also known as asymmetric cryptography, is a class of cryptographic protocols based on algorithms that require two separate keys, one of which is secret (or private) and one of which is public.
- Authentication happens by a user signing content with his private key, and then it is verified using the public key. That is, the full message is sent, and the encrypted message is also sent
- Vigenere encryption
- P = C = K = Z^j26
- Ek(x1,...,xj) = (x1 + k1,...,xj + kj)
- Dk(y1,...,yj) = (y1 - k1,...,yj - kj)
- Suppose a plaintext is chosen to be "ATTACKATDAWN".
- The key is chosen to be LEMON. The key is now repeated to fit the length of the plaintext word that is to be encrypted, like so
- "ATTACKATDAWN"
- "LEMONLEMONLE"
- Each row in now starts with the key letter spelled going downwards. The rest of the rows holds the letters A-Z in shifted order, i.e.
- ABCDEFGHIJKLMNOPQRSTUVWXYZ <-- header alphabet
- LMNOPQRSTUVWXYZABCEDFGHIJK <-- first key letter alphabet shift
- EFGHIJKLMNOPQRSTUVWXYZABCD <-- second key letter alphabet shift, etc...
- Now the plaintext is encrypted by mathcing the letter in the header, and going down to the row that the encryption is at.
- Finally, yielding "LXFOPVEFRNHR"
- Descryption is then the reverse process, that is going from the rows and up to the header.
- Cryptanalysis
- Kerckhoff's principle: Everything is known about the cryptosystem except the value of the secret key
- Attacks:
- Ciphertext-only attack: A ciphertext-only attack (COA) or known ciphertext attack is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts.
- Shift-cipher: try all keys
- Substitution cipher: frequency analysis
- Affine cipher: frequency analysis
- Vigenere cipher: find the period of j, attack j monoalphabetic substitution ciphers
- Hill cipher: do frequency analysis on tuples of j consecutive letters, find like j-tuples, guess the plaintexts, do as in known plaintext attack. If j > 3 then it is difficult to break in ciphertext-only attacks
- Known plaintext attack: The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has access to both the plaintext (called a crib), and its encrypted version (ciphertext).
- Hill-cipher: Assum period j of secret key is known, construct jxj matrices. If M is invertible, calculate K = M^(-1)C, else repeat for other texts. If j is unknown, do as before for j = 1,2,3,... until success.
- Chosen plaintext attack: A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts.
- Chosen ciphertext attack: A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis in which the cryptanalyst gathers information, at least in part, by choosing a ciphertext and obtaining its decryption under an unknown key.
- Ciphertext-only attack: A ciphertext-only attack (COA) or known ciphertext attack is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts.
- Shift-cipher:
- Assume you are given a ciphertext
- For all keys do: decrypt ciphertext
- The key for which the decryption gives a meaningful plaintext is likely to be the correct one.
- It is quite easy to break
- Redundancy:
- Repetiotion in plaintexts, that is some letters occur more often than others
- English: 'E' is the most frequent letter, occurs with probability of ~1/8
- Digrams: sequence of two letters, TH, HE, IN are common examples
- Trigrams: sequence of three letters, THE, ING are common examples
- Attacking:
- Using a table of probabilities of occurences of 26 letters in a typical English text
- First identify the letters that appear the most, these are most likely 'E's
- Now, identify the next most frequent letter and so on
- Repeat until the text is decrypted
- Affine-cipher:
- Count frequencies in the ciphertext
- Make guesses for encryptions of likely letters (e.g. 'E' and 'T')
- With 2 correct guesses, one gets 2 equations in 2 unknowns
- Test correct guesses by decrypting all ciphertext characters
- Vigenere
- Find the period j (index of coincidence). The index of coincidence of x, lc(x) is the probability that two randomly chosen elements from x are equal
- Attack j monoalphabetic shift ciphers
- Attacking:
- Assume symbols are from the English alphabet. Let f0,...,f25 be the frequencies of a,...,z in x. Then
- lc(x) = ∑25,i=0(fi 2) / (n 2) = ∑25,i=0 fi(fi-1) / n(n-1)
- lc(x) ≈ 0.065 if x consists of a English text
- lc(x) ≈ 0.038 if x consists of random letters
- After calculating the index of coincidence for a number of periods, it can be seen which period is the most likely one, by looking at which is closest to a English text
- Block ciphers
- Exhaustive key search: Known plaintext attack, 2^l encryptions
- Dictionary attack: Known plaintext attack, collect encryptions
- Likely message attack: Chosen/known plaintext attack, encrypt likely message m0 under all possible keys, save in table, if/when m0 is encrypted look up key in table
- Block ciphers
-
A deterministic algorithm operating on fixed-length groups of bits, called blocks, with an unvarying transformation that is specified by a symmetric key.
-
Goal is to have high security against known/chose plaintext attacks
-
Usually computed in layers/rounds, one round being:
- Key is added to input
- Input is split into small(er) blocks
- Each block is processed through a substitution box
- All blocks are then mixed
-
With n input bits, there are n output bits, and the key has l bits.
-
2^n possible plaintexts and ciphertexts, 2^l possible keys
-
Ek(m) = c
-
Dk(c) = e^(-1)(c) = m
-
It must hold for all m and k that ek^(-1)(ek(m)) = m
-
Iterated ciphers (which the important block ciphers usually are)
-
Key schedule
- Input: user selected key k of l bits
- Output: r round keys k1,k2,...,kr
-
Message/plaintext: c0 = m, ci = F(ki, ci-1)
-
Ciphertext: cr
-
Modes of operation
-
Electronic Codebook (ECB):
- The simplest of the encryption modes is the Electronic Codebook (ECB) mode. The message is divided into blocks, and each block is encrypted separately.
- The disadvantage of this method is that identical plaintext blocks are encrypted into identical ciphertext blocks; thus, it does not hide data patterns well.
┌────────────────────────────┐ ┌────────────────────────────┐
│ Plaintext │ │ Plaintext │
└──────────────┬─────────────┘ └──────────────┬─────────────┘
│ │
│ │
▼ ▼
┌──────────────┐ ┌──────────────┐
│ block cipher │ │ block cipher │
Key ────▶│ encryption │ Key ────▶│ encryption │
│ │ │ │
└──────┬───────┘ └──────┬───────┘
│ │
▼ ▼
┌────────────────────────────┐ ┌────────────────────────────┐
│ Ciphertext │ │ Ciphertext │
└────────────────────────────┘ └────────────────────────────┘
- Cipher Block Chaining (CBC):
- In CBC mode, each block of plaintext is XORed with the previous ciphertext block before being encrypted. This way, each ciphertext block depends on all plaintext blocks processed up to that point. To make each message unique, an initialization vector must be used in the first block.
- Its main drawbacks are that encryption is sequential (i.e., it cannot be parallelized), and that the message must be padded to a multiple of the cipher block size.
┌────────────────────────────┐ ┌────────────────────────────┐
│ Plaintext │ │ Plaintext │
└──────────────┬─────────────┘ └──────────────┬─────────────┘
┌────────────────────────────┐ │ │
│ Initialization Vector (IV) ├────────▶ X ┌──────────────▶ X
└────────────────────────────┘ ▼ │ ▼
┌──────────────┐ │ ┌──────────────┐
│ block cipher │ │ │ block cipher │
Key ────▶│ encryption │ │Key ────▶│ encryption │
│ │ │ │ │
└──────┬───────┘ │ └──────┬───────┘
├──────────────┘ ├──────────────
▼ ▼
┌────────────────────────────┐ ┌────────────────────────────┐
│ Ciphertext │ │ Ciphertext │
└────────────────────────────┘ └────────────────────────────┘
- Cipher Feedback (CFB)
- The Cipher Feedback (CFB) mode, a close relative of CBC, makes a block cipher into a self-synchronizing stream cipher. Operation is very similar; in particular, CFB decryption is almost identical to CBC encryption performed in reverse.
┌────────────────────────────┐
│ Initialization Vector (IV) │
└────────────────────────────┘
│ ┌───────────────────────────────────────┐
▼ │ ▼
┌──────────────┐ │ ┌──────────────┐
│ block cipher │ │ │ block cipher │
Key ───▶│ encryption │ │ Key ───▶│ encryption │
│ │ │ │ │
└──────────────┘ │ └──────────────┘
┌───▶X │ ┌───▶X
┌────────────────────────────┐ │ │ │┌────────────────────────────┐ │ │
│ Plaintext │────┘ ├───────────────┘│ Plaintext │────┘ ├───────────
└────────────────────────────┘ │ └────────────────────────────┘ │
▼ ▼
┌────────────────────────────┐ ┌────────────────────────────┐
│ Ciphertext │ │ Ciphertext │
└────────────────────────────┘ └────────────────────────────┘
- The Output Feedback (OFB):
- OFB mode makes a block cipher into a synchronous stream cipher. It generates keystream blocks, which are then XORed with the plaintext blocks to get the ciphertext. Just as with other stream ciphers, flipping a bit in the ciphertext produces a flipped bit in the plaintext at the same location. This property allows many error correcting codes to function normally even when applied before encryption.
┌────────────────────────────┐
│ Initialization Vector (IV) │
└────────────────────────────┘
│ ┌───────────────────────────────────────┐
▼ │ ▼
┌──────────────┐ │ ┌──────────────┐
│ block cipher │ │ │ block cipher │
Key ───▶│ encryption │ │ Key ───▶│ encryption │
│ │ │ │ │
└──────────────┘ │ └──────────────┘
│ │ │
┌────────────────────────────┐ ├───────────────┘┌────────────────────────────┐ ├────────
│ Plaintext │────────▶X │ Plaintext │────────▶X
└────────────────────────────┘ │ └────────────────────────────┘ │
▼ ▼
┌────────────────────────────┐ ┌────────────────────────────┐
│ Ciphertext │ │ Ciphertext │
└────────────────────────────┘ └────────────────────────────┘
- Counter (CTR):
- Like OFB, Counter mode turns a block cipher into a stream cipher. It generates the next keystream block by encrypting successive values of a "counter". The counter can be any function which produces a sequence which is guaranteed not to repeat for a long time, although an actual increment-by-one counter is the simplest and most popular.
┌────────────────────────────┐ ┌────────────────────────────┐
│ Nonce Counter │ │ Nonce Counter │
│ c59bcf35... 00000000 │ │ c59bcf35... 00000001 │
└────────────────────────────┘ └────────────────────────────┘
│ │
▼ ▼
┌──────────────┐ ┌──────────────┐
│ block cipher │ │ block cipher │
Key ───▶│ encryption │ Key ───▶│ encryption │
│ │ │ │
└──────────────┘ └──────────────┘
┌────────────────────────────┐ │ ┌────────────────────────────┐ │
│ Plaintext │─────▶X │ Plaintext │─────▶X
└────────────────────────────┘ │ └────────────────────────────┘ │
│ │
▼ ▼
┌────────────────────────────┐ ┌────────────────────────────┐
│ Ciphertext │ │ Ciphertext │
└────────────────────────────┘ └────────────────────────────┘
- CBC-MAC:
- Modification or tampering can be detected with a separate message authentication code such as CBC-MAC, or a digital signature.
- A cipher block chaining message authentication code (CBC-MAC) is a technique for constructing a message authentication code from a block cipher. The message is encrypted with some block cipher algorithm in CBC mode to create a chain of blocks such that each block depends on the proper encryption of the previous block. This interdependence ensures that a change to any of the plaintext bits will cause the final encrypted block to change in a way that cannot be predicted or counteracted without knowing the key to the block cipher.
- The IV is a fixed value, usually zeros
┌────────────────────────────┐ ┌────────────────────────────┐
│ Plaintext │ │ Plaintext │
└──────────────┬─────────────┘ └──────────────┬─────────────┘
┌────────────────────────────┐ │ │
│ Zero IV ├─────────▶│ ┌──────────────▶ │
└────────────────────────────┘ ▼ │ ▼
┌──────────────┐ │ ┌──────────────┐
│ block cipher │ │ │ block cipher │
Key ────▶│ encryption │ │Key ────▶│ encryption │
│ │ │ │ │
└──────┬───────┘ │ └──────┬───────┘
└──────────────┘ │
▼
┌────────────────────────────┐
│ Result │
└────────────────────────────┘
- Only the result of the last block is used.
- RSA
- RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret.
- A user of RSA creates and then publishes a public key based on the two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime numbers can feasibly decode the message.
- Public key: (n, e) where n = pq for distinct primes p,q and e in Z*phi(n)
- Private key: (p, q, d) where d in Z*phi(n), such that ed ≡ 1 mod phi(n)
- Encryption of m in Zn: E(m) = m^e mod n
- Decryption of c in Zn: D(c) = c^d mod n
- Key generation:
- Choose two distinct primes p and q
- Compute n = pq
- Compute phi(n) = phi(p)phi(q) = (p-1)(q-1) = n - (p+q-1)
- Choose an integer such that 1 < e < phi(n) and gcd(e,phi(n)) = 1 (i.e. e and phi(n) are coprime)
- Determine d as d = e^(-1) (mod phi(n)) (i.e. d is the modular multiplicative inverse of e modulo phi(n))
- Encryption in steps:
- Alice transmits her public key (n,e) to Bob and keeps her private key d secret
- Bob wants to send a message M
- He first turs M into an integer m such that 0 ≤ m ≤ n and gcd(m,n) = 1 via a padding scheme
- He then computes the ciphertext c corresponding to, c ≡ m^e (mod n)
- Bob transmits the message to Alice
- Decryption in steps:
- Alice can decrypt the ciphertext c by using her private key d:
- m ≡ c^d (mod n)
- Given m she can recover M using the original padding scheme
- Alice can decrypt the ciphertext c by using her private key d:
- Digital signature in general:
- Electronic equivalent to a handwritten signature. Requirements are,
- Easy to compute signature on a given message
- Possible for anybody to verify the signature
- Hard to forge a signature of somebody else
- Provides authentication but not secrecy
- RSA signature system:
- n = pq, p ≠ q odd primes
- (e,d) satisfy ed = 1 mod phi(n)
- Public key: (n,e)
- Private key: (p,q,d)
- Signature on x: sig(x) = s = x^d mod n
- Verification of s: ver(x,s) = true <=> x = s^e mod n
- No secrecy, but can be combined with RSA-encryption
- Forgery:
- 1
- Choose signature s'
- Compute message x' = s'^e mod n
- Problem: Attacker has no control over the message
- 2
- RSA has multiplicative property, that is sig(x1) x sig(x2) = sig(x1x2)
- Get signatures on x1 and x2, sig(x1) and sig(x2)
- Compute sig(x1x2) on message x1x2
- Combined with hash functions:
- Hash functions
- takes an arbitrary long message as input
- returns hash-code of short length
- "destroys" the structure of the input
- much faster than public-key systems
- Hash the message and then sign the hash-code
- Trial division
- For all primes r ≤ sqrt(m) check if r divides m
- if none of them divide m, m is a prime
- Fermat's theorem
- Is a probabilistic algorithm
- If m is a prime, then for all b in Z*m, b^(m-1) ≡ 1 mod m
- Repeat k times
- Choose random b in Z*m
- if not b^(m-1) ≡ 1 mod m, then m is 100% not a prime
- if b^(m-1) ≡ 1 mod m, then m may be a prime
- If "m may be a prime" k times, then we might believe it
- Choose random b in Z*m
- Fails on integers which are Carmichael numbers, also known as fermat pseudoprimes. These are numbers that pass the test, but are composite numbers (i.e. not primes)
- Miller-Rabin
- Another probalistic algorithm
- Let m be the integer to be tested for primality
- Write m-1 = 2^s t, where t is odd
- Compute y := b^t mod m, for a random b where 1 ≤ b ≤ m-1
- If y = 1 mod m then "m is a prime"; stop
- Else: for i := 0 to s-1 do
- if y = -1 mod m then "m is a prime"; stop
- else y := y^2 mod m
- if it hasn't stopped, "m is a composite"
- Can be repeated with j iterations to be more sure, usually around 3 iterations is pretty preciese
- The discrete logarithm:
- Let p be a prime, alpha an element in Zp and beta in Zp
- Given (p, alpha, beta), find a unique integer a, such that
- alpha^a ≡ beta mod p, where 0 < a ≤ p-1
- When is dlp(p) difficult?
- p must be a large prime (recommended to be at least 768 bits, popular is 1024 bits)
- p-1 must have at least on big prime factor
- the order of alpha mod p must be large
- Let p be an odd prime and alpha in Z*p. The smallest positive integer m, such that
- alpha^m ≡ 1 mod p
- m is called the order of alpha mod p
- Satisfies the goal of quick one way, difficult the other way (without special information)
- El-Gamal encryption:
- Public-key cipher
- Can be defined over any cyclic group G, and its security depends on dlp(p) being hard
- Generating a key:
- Alice generates an efficient description of a cyclic group G of order q with generator g
- Alice chooses a random x from {1,...,q-1}
- Alice computes h = g^x
- Alice publishes (G, q, g, h) as her public key, and retains x as her private key
- Encryption:
- Bob chooses a random y from {1,...,q-1} and calculates c1 = g^y
- Bob then calculates the shared secret s = h^y
- Bob converts his secret message m into an element m' of G
- Bob calculates c2 = m'·s
- Bob sends the ciphertext (c1,c2) = (g^y, m' h^y) = (g^y, m'·(g^x)^y) to Alice
- Decryption:
- Alice calculates the shared secret s = c1^x
- and then computes m' = c2·s^(-1) which she then converts back to the plaintext message m where s^(-1) is the inverse s in the group G
- The decryption algorithm produces the inteded message, since
- c2 · s^(-1) = m' · h^y · (g^(xy))^-1 = m' · g^(xy) · g^(-xy) = m'
- Or, in the word of the slides:
- p,alpha,beta = alpha^a mod p where p is a prime such that dlp(p) is difficult, alpha in Z*p primitive element
- Private key is a in Zp-1
- Choose random k, 1 ≤ k < p-1, E(m,k) = (y1,y2) where
- y1 = alpha^k mod p
- y2 = m beta^k mod p
- D(y) = m = y2(y1^a)^(-1) mod p
- El-gamal is a randomized encryption, where k is a randomizer. K should not be revealed nor repeated!
-
El-Gamal signature system:
- Let p be an odd prime such that dlp(p) is difficult
- alpha a primitive element
- Public key: p, alpha, beta = alpha^a mod p
- Private key: a
- Signature of x in Zp-1: sig(x,k) = (gamma, delta), where k in Z*p-1
- gamma = alpha^k mod p
- delta = (x - a·gamma)k^(-1) mod (p-1)
- Verification: verk(x,gamma,delta) = true <=> beta^gamma gamma^delta = alpha^x mod p
-
Forgery:
- Compute gamma, delta and x simultaneously
- gamma = alpha^i beta^j mod p
- delta = -gamma·j^(-1) mod (p-1)
- x = -gamma·i·j^(-1) mod (p-1)
- where gcd(j,p-1) = 1, then
- beta^gamma · gamma^delta = alpha^x mod p
- So, signatures can be forged but on "random" messages
- If k is revealed a can be computed from,
- delta = (x - a·gamma)k^(-1) mod (p-1)
- Once a is known, one can forge any signature
- To avoid forgery on random messages
- Introduce redundancy to message before signing
- Hash message before signing
- To avoid replay attack, include time stamps in messages
- RSV vs El-Gamal
- Signature size
- RSA: log2(n)
- El-Gamal: 2log2(p)
- Working in
- RSA: Zn
- El-Gamal: Zp
- With b small (e.g. 3), RSA verification is much faster than signing
- In El-Gamal signing and verifying have similar complexities
- Hash
- A hashing function is a one-way function that cannot be reversed, unlike encryption systems
- Application in many authentication schemes
- Digital signatures
- Password protection, Unix
- Message authentication codes, HMAC
- If we have a table of passwords, it the bruteforcing of a hash can easily be parralelized
- Salts can prevent this (unique salts on each item), since all other results than the correct cannot be used for other passwords than the current
- A hashing function must make it as close to impossible to
- Have collisions: Two items result in the same hash
- Preimage: given the output h, it is hard to find the input x such that H(x) = h
- 2nd preimage: given a message x1, it is hard to find a second message x2 ≠ x1, but H(x1) = H(x2)
- Probability of success for a preimage attack (bruteforcing) is 1-(1-2^(-n))^q, with q=2^n probability of success 1-(1-2^(-n))^(2^n) ≈ 0.63
- It is recommended to have n >= 160, with the aim of there being no better attacks than generic attacks
- Iterated hash functions:
- Iterated hash functions split the input into smaller bits of a fixed size n
- It is then padded to fit into blocks of n, via padding
- Padding rule
- Let x in {0,1}^v be a v-bit string to be hashed
- Append a 1-bit to x, so x:= x|'1'. Now |x| = v+1-bit
- s is the least positive integer such that v+1+s+lm is a multiple of n-component
- Append s zero-bits to x
- Append to x, block of lm bits with binary representation of v
- Now the length of x is multiple of n-component
- Merkle-Damgård is often used. Construct H from h:
- Let x in {0,1}^v be the message
- Apply collision-free padding rule such that x = x1 | x2 | ... | xt-1 | xt-1, where xt is a full block which contains the integer v as a string
- Define h0 = IV and hi = h(xi, hi-1) for 1 <= i <= - [ ]
- Define H(x) = ht
- Birtday paradox
- The birthday paradox concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday.
- By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are 366 possible birthdays, including February 29). However, 99.9% probability is reached with just 70 people, and 50% probability with 23 people.
- The 1st person can match with 22 other people
- The 2nd person can match with 21 other people
- The 3rd person can match with 20 other people, and so on...
- From the slides:
- Choose q elements at random (with replacements) from a set of S random elements, where q << S
- Let p be the probability of at least one collision
- 1-p = 1 · (S-1)/S · (S-2)/S · (S-q-1)/S
-
= ∏q-1,k=1 (1 - k/S) -
= ∏q-1,k=1 exp(-k/S) = exp(-(q·(q-1))/2S)
- The goal of a birthday attack is to find collisions in the hashing function.
- Choose q = 2^((n+1)/2) = sqrt(2) · 2^(n/2) randomly chosen inputs each of at least (n+1)/2 bits
- Compute the hash values for all k inputs
- The probability of at least one collision is: p ≈ 1 - exp(-(q(q-1))/ (2·2^n)) ≈ 1-e^(-1)
- DLP
- Look at section 8.
- Key distribution
- Types of key exchange
- Key distribution - one party chooses and distributes key(s)
- Key agreement - establish key based on input from several parties
- Types of keys
- Long-life keys, typically used to encrypt/exchange session keys
- Session keys, typically used to encrypt data in 1 session only
- TA (trusted authority) based system
- Network of n users
- TA chooses long-life keys and distributes
- Advantage: only n secure channels needed, users can exchange session keys
- Disadvantage: use of TA, (n 2) long-life keys
- Attacks on key distribution/agreement
- Passive: Only eavesdropping
- Active: Alter message, replay message, impersonation
- Goals
- Make legitimate parties falsely believe the key protocol was successful
- Trick legitimate parties into accepting "wrong" key
- Get information about the exchanged key
- Diffie-Hellman key agreement
- Example:
- Alice and Bob agree to use a prime number p = 23 and base g = 5
- Alice chooses a secret integer a = 6, then sends Bob A = g^a mod p
- A = 5^6 mod 23 = 8
- Bob chooses a secret integer b = 15, then sends Alice B = g^b mod p
- B = 5^15 mod 23 = 19
- Alice computes s = B^a mod p
- s = 19^6 mod 23 = 2
- Bob computes s = A^b mod p
- s = 18^5 mod 23 = 2
- Alice and Bob now share the same secret number, 2
- Solving DLP implies solving Diffie-Hellman
- If the Diffie-Hellman problem is regarded to be hard to solve, can the Diffie-Hellman key agreement then be regarded secure?
- Yes, but security is only against passive adversaries.
- It is not secure against a man-in-the-middle attack
- Secret sharing
- Secret sharing (also called secret splitting) refers to methods for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret.
- How to share a secret
- How do we split a secret k between w persons, such that
- k can be determined if all w persons collaborate
- k cannot be determined if less than w persons participate
- Assume k in Zp
- Choose random integers si in Zp for i = 1...,w-1
- Compute sw = k - ∑w-1,i=1 (si mod p)
- Give si to participant i
- To use the keys:
- w persons collaborate, compute: k = ∑w,i=1 (si mod p)
- (w-1) persons collaborate, compute: ∑w,i=1,i≠j si = k-sj mod p
- Hence less than w persons learn nothing about the secret key
- How do we split a secret k between w persons, such that
- k can be determined if t <= w persons collaborate
- k cannot be determined if less than t persons collaborate
- Solution to this is called a (t,w)-threshold secret sharing system
- Paticipants: keyholders H, shareholders S1,...,Sw
- Secret key: k
- H chooses
- a prime p, such that p >= w+1
- a polynomial of degree t-1
- f(x) = k + ∑t-1,j=1 (cj·x^j mod p)
- w public, distinct values xi, 0 < xi < p
- H computes yi = f(xi) for i=1,...,w
- H gives (xi,yi) to Si for i=1,...,w
- To use the keys:
- Input: t shares (xi,yi) for i=1,...,t
- The key is computed as follows
- k = f(0) = ∑t,i=1 yi ∏ 1<=j<=t, j≠i (xj/(xj-xi))
- t points determine f(x) uniquely
- s >= t participants can find f(x) and k=f(0)
- s < t participants don't get info about k