Cryptography Flashcards

Question

Proof that one-time pad is unconditionally secure

Answer 1

Suppose (P, C,K, Σ, D) is a cryptosystem where |K| = |C| = |P|. Then the cryptosystem provides perfect secrecy if and only if every key is used with equal probability 1/|K|, and for every x ∈ P and every y ∈ C, there is a unique key such that e_k(x) = y.

Answer 2

- According to Claude Shannon, an ideal cipher should satisfy: * Confusion: The relationship between the key and the ciphertext is as complex as possible * Diffusion: The structure of the plaintext is dissipated over the entire ciphertext

Answer 3

* Confusion: Flipping any fixed set of key bits causes the i^th bit of ciphertext to change with probability 0.5. * Diffusion: Flipping any fixed set of plaintext bits causes the ith bit of ciphertext to change with probability 0.5

Answer 4

* Substitution to provide confusion * Permutation to provide diffusion * Other components might include: x-or, linear transformations, arithmetic operations, modular multiplication

Answer 5

A product cipher combines two or more components with the intention of producing a cipher that is more secure than the basic parts of which it is made

Answer 6

_Cryptosystem_ Let l,m,Nr be positive integers * π_S : {0, 1}^l → {0, 1}^l is an S-box * π_P : {1, . . . , lm} → {1, . . . , lm} is a permutation * P = C = {0, 1}^lm * K ⊆ ({0, 1}^lm)^Nr+1 is the set of all key schedules that can be derived from an initial key k * For a key schedule (k¹, . . . , k^Nr+1) we encrypt using an iterated cipher composed of substitution, permutation and x-or operations

Answer 7

- Inputs: plaintext block, π_S, π_P , (k¹, . . . , k^Nr+1) - Output: ciphertext block - state = plaintext block - for round r = 1 to Nr − 1 do * x-or: state = state ⊕ k^r * substitutions: apply π_S to m strings of l bits of state * permutation: apply π_P to lm bits of state - end do - x-or: state = state ⊕ k^Nr - substitutions: apply πS to m strings of l bits of state - ciphertext block = state ⊕ k^Nr+1

Answer 8

Lecture 3, pp 32-56

Answer 9

- A fixed key size defines an upper bound on the security of the cipher - If the key k is a bitstring of length l_k then there are 2^l_k keys - Given a small number of plaintext-ciphertext pairs the attack has complexity of 2^l_k−1 operations

Answer 10

- Text dictionary attack: For block size m, if an attacker has collected 2m plaintext-ciphertext pairs then they have a complete dictionary of the cipher - Matching ciphertext attack: If you have collected 2m/2 blocks you expect to find matching ciphertext blocks within them

Answer 11

- Chosen plaintext attack - Plaintexts chosen in pairs x, x∗ such that x ⊕ x∗ = x′, a particular plaintext difference - x′ is chosen such that, with high probability during encryption, a particular state difference will occur at the input to the last round of S-boxes - Objective: Find targeted key bits - Basic idea: Exploit a situation whereby a particular difference between ciphertexts y′ occurs, given a particular difference between plaintexts x′, with a very much higher probability than is ideal

Answer 12

For each tuple (x, x∗, y, y∗): 1. For each candidate round key k^Nr+1 partially decrypt both ciphertexts producing state and state ∗ 2. Find the state difference state′ = state ⊕ state∗ 3. If state′ = expected difference then increment the counter for this candidate key The candidate key with the highest count should have the correct values for the targeted key bits

Answer 13

- Idea: Find the expected difference between statevand state∗ just before the final S-boxes - Steps: 1. For each S-box consider all possible differentials: (a′, b′) = (input difference, output difference) 2. 2 Find the propagation ratio, the probability b′ occurs given a′ 3. Combine high probability differentials to make a differential trail

Answer 14

Lecture 4, pp. 34-50

Answer 15

- Objective: Find targeted key bits. - Known plaintext attack: attacker has a set of plaintext-ciphertext pairs encrypted with the same key k - Using probabilistic analysis we find biased linear approximations for the S-boxes. We construct a linear approximation, with a large bias, of the SPN (excepting the final round) in terms of plaintext bits and state bits - For each candidate key partially decrypt each ciphertext and see if the linear approximation holds for state, incrementing a counter for the key if it does - The candidate key with largest bias (from |input pairs|/2) should contain the targeted key bits

Answer 16

If p is the propagation ratio of the differential trail then the attack is often successful if the number of tuples (x, x∗, y, y∗) is approximately c/p where c is some small constant

Answer 17

If p is the “bias” of the linear approximation then the attack is often successful if the number of plaintext-ciphertext pairs is approximately c/(p²) where c is some small constant

Answer 18

- A Feistel cipher is an iterated cipher in which the state on round i is divided into two halves of equal length: Lⁱ and Rⁱ - The round function g has the form g(L^i−1, Rⁱ⁻¹, kⁱ) = (Lⁱ, Rⁱ) and for some function f, is computed: * Lⁱ = Rⁱ⁻¹ * Rⁱ = Lⁱ⁻¹ ⊕ f(Rⁱ⁻¹, kⁱ)

Answer 19

- Inputs: plaintext block (length m), (k¹, . . . , k^Nr) - Output: ciphertext block Initialise state: L⁰ = left m/2 bits of plaintext block R⁰ = right m/2 bits of plaintext block for round i = 1 to Nr do * Call the round function: * Lⁱ = Rⁱ⁻¹ * Rⁱ = Lⁱ⁻¹ ⊕ f(Rⁱ⁻¹, kⁱ) end do Notice the output order of the state pair: ciphertext block = R^NrL^Nr

Answer 20

DES (Data Encryption Standard) is a 16 round Feistel cipher where: - m = 64, Lⁱ and Rⁱ are bitstrings of length 32 - k is 56 bits long, from this sixteen 48 bit round keys are produced consisting of a selection of bits of k, permuted - There is a fixed initial permutation L⁰R⁰ = IP(x) before the first round - The inverse permutation IP−1(R16L16) is applied after the last round - f : {0, 1}³² × {0, 1}⁴⁸ → {0, 1}³² - f consists of a substitution (S-box) followed by a fixed permutation.

Answer 21

- Expand Rⁱ⁻¹ to 48 bits and x-or with kⁱ: state = E(Rⁱ⁻¹) ⊕ kⁱ - Apply substitutions to state: map 6-bit substrings to 4-bit substrings - Permute state: state = P(state)

Answer 22

1. Electronic codebook mode (ECB) 2. Cipher block chaining mode (CBC) 3. Output feedback mode (OFB) 4. Cipher feedback mode (CFB)

Answer 23

- For a key k in the DES keyspace DES encryption defines a permutation of 64 bits - There are 256 possible keys and hence up to 256 different permutations - The set of 2⁵⁶ permutations defined by the 2⁵⁶ DES keys is not closed under function composition

Answer 24

- Attack model: known plaintext - Naive exhaustive key search would then take 2¹¹² operations - However, since it's a product cipher, DES's structure can be attacked

Answer 25

- The standard for DES, replacing Double DES in 1999 - AES will replace 3DES but they currently coexist as FIPS approved algorithms

Answer 26

- Naive exhaustive search: 2¹⁶⁸ operations - Meet in the middle attack: 2¹¹² operations - Differential and linear cryptanalysis become more difficult

Answer 27

- Naive exhaustive search: 2¹¹² operations - Differential and linear cryptanalysis become more difficult

Answer 28

Necessary criteria: * Block length: 128 bit * Support key lengths of 128, 192 and 256 bits * Should be available worldwide on a royalty free basis Evaluated according to: * Security * Cost * Algorithm and implementation characteristics

Answer 29

- Iterated cipher with structure similar to an SPN - Number of round depends on key size: * Key size = 128, Nr = 10 * Key size = 192, Nr = 12 * Key size = 256, Nr = 14

Answer 30

- There are known side-channel attacks on AES, exploiting timing properties of its implementation on known - In July 2009, researchers described di↵erent related key attacks on AES. These are (variously): 1. Feasible for reduced-round versions of 256-bit AES (2⁴⁵ complexity for a 10-round version) 2. Theoretically better than brute force but not feasible (2¹¹⁹ complexity) for the full 14-round version - In 2011, a theoretical key-recovery attack on full AES was published which is better than brute force by a factor of about 4.

Answer 31

- Informally, a hash function h is a function which has the following properties: 1. Compression: h maps an input x to an output y = h(x) of fixed length 2. Computability: given h and x, h(x) is “easy” to compute

Answer 32

- An unkeyed hash function is a function h :X !Y where: * X is the set of possible messages * Y is a finite set of possible message digests - A pair (x, y), x ∈ X, y ∈ Y is valid if h(x) = y

Answer 33

- A family of keyed hash functions is a four-tuple (X,Y,K,H) where: * X is the set of possible messages * Y is a finite set of possible authentication tags * For each k ∈ K, the finite set of possible keys, there is a hash function h_k ∈ H such that h_k: X → Y - A pair (x, y), x ∈ X, y ∈ Y is valid under key k if h_k(x) = y

Answer 34

- Message digest code = unkeyed hash function - Applications: * Integrity checking: Alice sends Bob the pair (x, h(x)) ∈ X x Y. Bob receives (x', y) x Y, and checks that h(x') = y * Passwords: Alice chooses a password x 2 X for Bob.com, which stores h(x) 2 Y wth her username. At login, her attempt is hashed to y 2 Y and sent to Bob.com, who compare it to h(x) * Message authenticity: Alice combines her message m with a secret key k (shared with Bob), and sends him (m, h(k,m)). * Digital signature: Alice hashes her message, and signs the hash with her private key

Answer 35

If a hash function is to be considered secure three problems are required to be difficult to solve: * Preimage problem * Second preimage problem * Collision problem

Answer 36

- Inputs: h: X → Y, y ∈ Y - Find: x ∈ X such that h(x) = y

Answer 37

- Message digests are also used to obscure passwords. - There is a natural first preimage attack in this case: 1. Alice sets a new password p, the password isn’t stored on the system, the hash h(p) is stored. 2. If Alice wants to log in then her password is requested, the password she gives is hashed and compared with the stored value. 3. If Oscar had h(p) but not p then he has the input for a first preimage attack. 4. If Oscar can find some p' for which h(p') = h(p) then he can use p' as a password for Alice’s account and log in to the system as Alice.

Answer 38

- Inputs: h: X → Y, x ∈ X - Find: x' ∈ X such that h(x') = h(x)

Answer 39

Consider a digital signature scheme where the signatory signs the hash h(x) rather than x itself. 1. Alice prepares x, some agreement she has with Oscar, she calculates h(x) and signs it, sending x and the signed hash to Oscar. 2. Oscar has x and h(x). 3. If h is not second preimage resistant Oscar may be able to find x' such that h(x) = h(x'). 4. He can now claim that Alice signed x'.

Answer 40

- Inputs: h: X → Y - Find: x, x' ∈ X such that x ≠ x' and h(x) = h(x')

Answer 41

Now assume that Oscar is preparing the documents for Alice to sign. 1. Oscar produces x and x', h(x) = h(x'). x is the agreement Alice expects and x' is some other agreement more favourable to Oscar. 2. Alice receives x, calculates h(x) and sends the signed hash to Oscar. 3. Oscar can now claim that Alice signed x'.

Answer 42

- h produces hashes of length n bits. - Let y = h(x) for some message x. - For random bitstrings x0 of bounded bitlength, calculate h(x') and check if h(x') = y

Answer 43

* Over K elements, there are K²−K / 2 distinct, unordered pairs * If h: X → Y is uniformly distributed, the probability that any one pair is a collision is 1 / |Y| * So a collision can be expected if K ≥ √(2|Y|) + 1 — i.e. (K − 1)² ≥ 2|Y|, so (K²−K / 2|Y|) ≥ 1 * Let h: X → Y produce hashes y of length n bits and hence |Y| = 2ⁿ * A collision is expected to be found by brute force in around 2^n/2 operations

Answer 44

A n-bit unkeyed hash function is considered to be: * Preimage resistant if producing a preimage or a second preimage requires approximately 2ⁿ operations * Collision Resistant if producing a collision requires approximately 2^n/2 operations

Answer 45

- Theorem: Any collision resistant compression function can be extended to a collision resistant hash function which takes arbitrary length inputs - This can be done efficiently by the Merkle-Damgard construction

Answer 46

- Construct y = y₁ || y₂ || . . . || y_r+1 - z₀ = 0ⁿ for i = 1 to r + 1 do * z_i = compress(z_i−1 || y_i) * end do - return h(x) = z_r+1

Answer 47

- MD is also known as Message Digest - April 1992: Described by Rivest in RFC 1321 - Mid-1990s: Collisions found in compression function - 2004: Wang et al. produced a collision for MD5 - 2008: Chosen prefix collision attacks. - 2012: Flame Malware attack uses a chosen prefix attack on MD5 to forge a Microsoft Terminal Server licensing certificate.and authenticate itself

Answer 48

- SHA (referred to as SHA-0), is considered insecure - 2005: Wang et al. showed collisions can be found in SHA-1 in less than 263 steps. Collision published by Google/CWI Amsterdam — Feb 23 2017. - Members of the SHA-2 family (SHA-256, SHA-384, SHA-512) are more complex than SHA-1. They are currently considered secure -

Answer 49

- The hash function Keccak was chosen by NIST as the basis for a new standard - SHA-3 (2014). - SHA-3 does not replace SHA-2 (which is still considered secure) but has some operational advantages - It is based on an iterated sponge construction (not Merkle-Damgard): at each iteration, a block of the message is XORed into the current state, and then substitution and permutation operations are performed

Answer 50

- Compression and computability - In addition, given a description of the hash family and a secret key k, computational resistance is required

Answer 51

- Without prior knowledge of k, given zero or more pairs (x_i, h_k(x_i)) it is computationally infeasible to compute (x_i, h_k(x)) for a new input x ≠ x_i

Answer 52

- If a MAC is not computation-resistant it is subject to MAC forgery - Computation-resistance ⇒ key non-recovery - key non-recovery ⇏ computation-resistance

Answer 53

- The attacker is able to produce a new valid pair (x, h_k(x)): * Existential Forgery for some message x. * Selective Forgery for a predetermined message x. * Universal Forgery For any message x. for his choice (or partial choice) of x but has no control over the value of x

Answer 54

- Input: (x, h_k(x)), key of length l - Output: k - Compute n-bit MAC using all possible keys * This requires 2^l MAC operations. * In an ideal MAC, 2l−n keys will remain as candidates * Further valid pairs can test the remaining candidates - A MAC key should not be recoverable in fewer than 2^l operations

Answer 55

- For an n-bit MAC we expect to guess a correct MAC with probability 2⁻ⁿ. - But we cannot check guesses without either the key or an (adaptive) chosen-text scenario. - We should not be able to produce MAC forgeries with probability higher than max(2^−l, 2⁻ⁿ)

Answer 56

- The MAC key could be used as both a suffix and a postfix: h_k(x) = h(k∥p∥x∥k), with padding to ensure that there is at least two iterations in the computation of h

Answer 57

- Known as a keyed-hash message authentication code - Algorithm: * Inputs: key k, MDC h * Define ipad and opad each of length 512 bits: * ipad = 3636. . . 36 * opad = 5C5C .. . 5C * HMAC_k(x) = h(k ⊕ opad" || h((k ⊕ ipad) || x)" - Keyed-Hash Message Authentication Code, FIPS standard 198, 2002 - h can be any approved unkeyed hash.

Answer 58

- A public-key cryptosystem is a cryptosystem (P,C,K,E,D) where: * For every k ∈ K, e_k is the inverse of dk * For every k ∈ K and for every x ∈ P or y ∈ C, e_k(x) and d_k(y) are easy to compute * It is computationally infeasible (for almost all k ∈ K) to derive dk from e_k * For every k ∈ K it is feasible to compute e_k and d_k from k

Answer 59

- A one-way function is a function f : X → Y such that for all x ∈ X it is easy to compute f(x) but for (almost) all y ∈ Y it is computationally infeasible to find an x such that f(x) = y

Answer 60

- A trap-door one-way function is a one-way function f : X → Y such that given some additional trap-door information it becomes feasible, for all y ∈ Y to find x ∈ X such that y = f(x).

Answer 61

- The number of integers less than n and relatively prime to n is denoted φ(n). This function is called the Euler phi-function - Properties: * If p is prime then φ(p) = p − 1 * The Euler phi-function is multiplicative, that is, if gcd(m, n) = 1 then φ(n · m) = φ(n) · φ(m) * If n = p₁^e₁, p₂^e₂,..., p_k^e_k, k is the prime factorisation of n then:

Answer 62

- The set of residues modulo n denoted Z_n is a commutative ring - b ∈ **Z**_n has a multiplicative inverse if and only if gcd(n, b) = 1 - The number of positive integers b \< n relatively prime to n is φ(n) - The set of residues modulo n which are relatively prime to n is denoted **Z**^∗_n - This is an Abelian group under multiplication, b ∈ **Z**^∗_n have a multiplicative inverse b⁻¹ ∈ **Z**^∗_n

Answer 63

- Inputs: a, b ∈ N, a ≥ b - Output: gcd(a, b) - r₀ = a, r₁ = b, m = 1 - while r_m ≠ 0 do * qm = ⌊r_m−1 / r_m ⌋ * r_m+1 = r_m−1 − q_mr_m * m = m + 1 - end do - m = m − 1 - return rm

Answer 64

- In the Euclidean algorithm there was: r_m−2 = q_m−1r_m−1 + r_m and gcd(r₀, r₁) = r_m - Unwind the steps writing each in terms of the inputs a and b: * r₂ = r₀ − q₁r₁ = a − q1b * r₃=r₁ − q₂r₂=b − q₂(a − q₁b)=b−q₂a+q₁q₂b = −q₂a+(1+q₁q₂)b * ... * r_i−2 = s_i−2a + t_i−2b * r_i−1 = s_i−1a + t_i−1b * r_i = _ri−2 − q_i−1ri−1 = s_i−2a + t_i−2b − q_i−1(s_i−1a + t_i−1b) * = (s_i−2 − q_i−1s_i−1)a + (t_i−2 − q_i−1t_i−1)b = s_ia + t_ib * ... * r_m = s_ma + t_mb * Hence s_m, t_m ∈ **Z** such that gcd(a,b) = s_ma + t_mb can now be found

Answer 65

- Inputs: a, b ∈ **N**, a ≥ b - Output: gcd(a, b) and s, t ∈ **Z** such that * sa + tb = gcd(a, b) * s_old = 1, s = 0, t_old = 0, t = 1 * q = ⌊a/b⌋, r = a − qb * while r \> 0 do * t_new = t_old − qt, t_old = t, t = t_new * s_new = s_old − qs, s_old = s, s = s_new * a = b, b = r, q = ⌊a/b⌋, r = a − qb * end do * return (b, s, t)

Answer 66

- Used to solve certain congruent systems - Let m₁,m₂, ...,m_r be pairwise relatively prime positive integers. Suppose a₁, a₂, . . . , a_r ∈ **Z** and consider: * x ≡ a₁ (mod m₁) * x ≡ a₂ (mod m₂) * ... * x ≡ a_r (mod m_r) - The Chinese remainder theorem states that this system has a unique solution modulo M = m_1,m₂···, m_r

Answer 67

- Suppose p is prime and b ∈ Z^∗_n then b^p ≡ b (mod p) - Euler generalises this theorem by stating: For all b ∈ Z^∗_n, b^φ(n) ≡ 1 (mod n)

Answer 68

- RSA = Rivest, Shamir and Adleman - Cryptosystem: * Let n = pq, p, q prime * P = C = **Z**_n * K = {(n, p, q, a, b) | ba ≡ 1 (mod φ(n))} * For k = (n, p, q, a, b) ∈ K we have e_k(x) = x^b (mod n) and d_k(y) = y^a (mod n) for x, y ∈ **Z**_n * (n, b) is called the public key and (p, q, a) is called the private key

Answer 69

_Context_ - Alice sent a message x ∈ P encrypted with Bob’s public key (n, b): e_k(x) ≡ x^b(mod n) - Bob decrypts with his private key (p, q, a): d_k(e_k(x)) ≡ (x^_b)^a (mod n) ≡ x^ba (mod n) - Prove that x^ba ≡ x(mod n)

Answer 70

- Show that x^ba ≡ x (mod n) - ba is defined by ba ≡ 1 (modφ(n)) - This can be rewritten as: ba = kφ(n) + 1 for some k ∈ **N** = k(p − 1)(q − 1) + 1 - If gcd(x, p) = 1 we have x^p−1 ≡1 (mod p) by Fermat’s little theorem - Raise both sides to the power k(q − 1), s.t. x^{k(p−1)(q−1)} ≡ 1 (mod p), and multiplying both sides by x to get, for gcd(x, p) = 1, that: x^{k(p−1)(q−1)}+ 1 ≡ x (mod p) * But if gcd(x, p) = p then this holds as both sides are congruent to 0 (mod p) * Hence for all x ∈ P * x^{k(p−1)(q−1)+1} ≡ x (mod p) ⇒ x^ba ≡ x (mod p) - By argument,we have x^ba ≡ x (mod q) - Now, p and q are relatively prime and a system of congruences exists: * x^ba ≡ x (mod p) * x^ba ≡ x (mod q) - Therefore, by Chinese remainder theorem and recalling that n = pq: xba ≡ x (mod n)

Answer 71

* Generate two large primes p, q such that p ̸= q * Calculate n = pq, φ(n) = (p − 1)(q − 1) * Choose a random 1 \< b \< φ(n) such that gcd(b, φ(n)) = 1 * Calculate a = b⁻¹ (mod φ(n)) * Set the public key to (n, b) and the private key to (p, q, a)

Answer 72

- Basic method: generate a large random number, test this for primality - The large cost involved in the parameter generation is the calculation of a = b⁻¹ (mod φ(n)) - However, the extended Euclidean algorithm can be used since it calculates in time O((log k)²)

Answer 73

- Can be used in generation of large primes - To calculate x^b (mod n) can be: * Very slow: b − 1 modular multiplications * Faster: use the square and multiply algorithm * Faster again: use Chinese remainder theorem

Answer 74

- The integer factorisation problem (FACTORING) states: given a positive integer n find its prime factorisation n = p^e₁₁ p^e₂₂··· p^e_k_k, where p_i are distinct primes and e_i ≥ 1

Answer 75

- p' is strong if: * p − 1 has a large prime factor (denoted r) * p + 1 has a large prime factor * r − 1 has a large prime factor - However, strong primes offer no protection against the Elliptic Curve Method

Answer 76

- A generalisation of Pollard’s p − 1 method - Depends on an integer “close to” p having only “small” prime factors. - This is more likely than the situation required by Pollard’s p − 1 method - Pollard’s method depends on a relation which holds in the group Z^∗_p - ECM depends on a relation which involves groups defined on elliptic curves modulo p - Tends to find smaller factors first

Answer 77

- An idea proposed due to Fermat - To factor n look for x, y ∈ Z such that x² − y² = n - If such x, y can be found then d = gcd(x − y, n) is a non trivial factor of n

Answer 78

- A modification of the idea of difference of two squares - Congruent squares = to factor n look for x, y ∈ Z such that x² ≡ y² (mod n) ``` - Proposition: If we also have x ̸≡ ±y (mod n) then gcd(x − y, n) and gcd(x + y, n) are non trivial factors of n ``` - Proof: * x² ≡ y² (mod n) ⇒ x² − y² ≡ 0 (mod n) ⇒ n|(x² − y²) ⇒ n|(x − y)(x + y) * x ̸≡ ±y (mod n) ⇒ x − y ̸≡ 0 (mod n) and x + y ̸≡ 0 (mod n) ⇒ n ̸|(x − y), n ̸|(x + y)

Answer 79

- Imagine Oscar has Bob’s public key (n, b) and his decryption exponent a. Oscar can factor n. - By definition ba ≡ 1 (mod φ(n)) and so ba − 1 = kφ(n) for some k ∈ N - Hence, for all x ∈ Z^∗_n: x^ba−1 ≡ 1 (mod n) - Take the square root: y1 = √(x^ba−1) = x^(ba−1)/2 and then use y^₂₁ ≡ 1 (mod n) to try to recover a factor from n - If y₁ ≡ 1 (mod n) then we take the square root of y₁: y₂ = √y₁ = x^(ba−1)/4 - It's already known that y₂² ≡ y₁ ≡ 1 (mod n) so it's again possible to attempt to factor n - Continue the process until either: * A non trivial factor of n is found * (ba − 1)/2^s is not divisible by 2 - Factor n with probability 1/2 -

Answer 80

- Proposition: If there is also a x ̸≡ ±y (mod n) then gcd(x − y, n) and gcd(x + y, n) are non trivial factors of n - Proof: * x₂ ≡ y₂ (mod n) ⇒ x² − y² ≡ 0 (mod n) ⇒ n|(x² − y²) ⇒ n|(x − y)(x + y) * x ̸≡ ±y (mod n) ⇒ x − y ̸≡ 0 (mod n) and x + y ̸≡ 0 (mod n) ⇒ n ̸|(x − y), n ̸|(x + y)

Answer 81

- x ∈ N is said to be B-smooth if all prime factors of x are ≤ B - Use a factor base, a set B of the primes below some bound B - Find a collection of z ∈ Z such that each z^₂ (mod n) is B-smooth - Find a subset of the z² (mod n) such that each prime in the factor base is used an even number of times - This will give a congruence of the type x² ≡ y² (mod n) as required.

Answer 82

* Select the factor base of primes p ≤ B. * Collect relations between elements of the factor base producing squares * z₂^j ≡ Π p_i^v_ij(mod n), where p is the factor base * Write each relation as a vector v_j = (v_1j, . . . , v_ij, . . .) * Find dependencies: reduce v_j modulo 2 and use linear algebra to find a dependency modulo 2 * The dependency will give a subset S of relations whose vectors added together produce a vector with even coordinates, hence: * Πz_j² ≡ Π p_i^v_ij ≡ y² (mod n)

Answer 83

- In Dixon’s random squares algorithm, simply select z at random - Although, it can be useful to look at integers of the form j + |√kn| which tend to be small when squared and reduced mod n

Answer 84

- Basic RSA is not semantically secure because the encryption function is deterministic - The attacker can distinguish ciphertexts - Example: * Imagine all messages are either “Buy” or “Sell”. Call these x1 and x2. * Attacker sees a new message c being sent to Bob Ltd. with public RSA key (n, b) * Attacker computes c₁ = x^b₁ (mod n) and compares this with c. * If they match then he knows I sent the message “Buy”.

Answer 85

- Let x1, x2 be two plaintext messages. Notice that: * e_k(x₁x₂) ≡ (x₁x₂)^b ≡ x₁^_bx₂^_b ≡ e_k(x₁)e_k(x₂) (mod n) - The encryption of x = x₁x₂ is y = e_k(x₁)e_k(x₂) - RSA is malleable: known plaintext can be altered without decryption - This can be used to run an adaptive chosen ciphertext attack

Answer 86

- Trusted authority produces RSA key pairs (n, b), (n, a) for all users of a network - Alice, Bob and Oscar are all legitimate users of the network and so receive keys - The TA fixes n = pq and provides each user i with with unique b_i and a_i - Alice encrypts x using Bob’s public key (n, b₁) and sends y on the insecure network

Answer 87

- A small private exponent can be used to increase the speed of decryption - Wiener presented an attack that computes a from the public key if 3a \< n^1/4 and q \< p \< 2q

Answer 88

- To reduce encryption time a small public exponent b is often used - However, very small exponents, such as b = 3, are not secure

Answer 89

- Alice wants to broadcast a message x: * y₁ ≡ x³ (mod n₁) * y₂ ≡ x³ (mod n₂) * y₃ ≡ x³ (mod n₃) - Attacker can use the Chinese remainder theorem to compute solution to: * Y ≡ y₁ (mod n₁) * Y ≡ y₂ (mod n₂) * Y ≡ y₃ (mod n₃) - Say the solution is Y (mod n₁n₂n₃) * But x³ \< n₁n₂n₃ so there must be a Y = x³ and hence x = Y^1/3

Answer 90

- Example: n₁ = 319, n₂ = 299, n₃ = 323 - Let b = 3, broadcasting x = 7 leads to: * y₁ ≡ 7³ ≡ 343 ≡ 24 (mod 319) * y₂ ≡ 7³ ≡ 343 ≡ 44 (mod 299) * y₃ ≡ 7³ ≡ 343 ≡ 20 (mod 323) - The Chinese Remainder Theorem will give: M = 30808063 * 299 x 323 = 96577, 96577^-1 ≡ 315 (mod 319) * 319 x 323 = 103037, 103037^-1 ≡ 38 (mod 299) * 319 x 299 = 95381, 95381^-1 ≡ 286 (mod 323) - (24 x 96577 x 315 + 44 x 103037 x 38 + 20 x 95381 x 286) ≡ 343 (mod 30808063)

Answer 91

- Ways to avoid the attack: * Use larger RSA exponents * Increase the amount of padding * Make padding depend on the message e.g. hash the message and append this * Spread random padding throughout message (some methods can still be attacked)

Answer 92

- There is a cryptographic primitive, that is, the “raw” or “basic” RSA - In practice protocols built of many primitives to achieve secure communication are used, perhaps with data integrity build in - The most important of these protocols is OAEP, a padding scheme due to Bellare and Rogaway - OAEP is used in Public Key Cryptography Standards (PKCS) and hence most Internet protocols - Assuming that the RSA problem of computing b^th roots modulo n is computationally infeasible RSA-OAEP is semantically secure against adaptive chosen ciphertext attacks

Answer 93

- The order of a group is the number of elements in the group * If the order of a group is finite it is called a finite group - Let G be a finite group. The order of an element g ∈ G is the smallest positive integer m such that g_m = 1

Answer 94

- Let G be a finite group of order m. G is said to be a cyclic group if there exists an element α ∈ G having order equal to m. α is called a generator of G. - Z^*_p is a cyclic group

Answer 95

- An element α ∈ **Z**^*_p with order p − 1 modulo p is called a primitive element modulo p - It immediately follows that ↵ is a primitive element modulo p if and only if {αⁱ | 0 ≤ i ≤ p − 2} = Z^*_p

Answer 96

- Let p = 7. * We have φ(6) = φ(2 x 3) = φ(2) x φ(3) = 2 primitive elements modulo 7 - How to find? * Lets see if 2 is a primitive element modulo 7: * 2⁰ (mod 7) = 1 * 2¹ (mod 7) = 2 * 2² (mod 7) = 4 * 2³ (mod 7) = 1 * 2 has order 3

Answer 97

- What about 3, with p = 7: * 3⁰ (mod 7) = 1 * 3¹ (mod 7) = 3 * 3² (mod 7) = 2 * 3³ (mod 7) = 6 * 3⁴ (mod 7) = 4 * 3⁵ (mod 7) = 5 * And just to check: 3⁶ (mod 7) = 1 - Since 3 is primitive we know that 3ⁱ is primitive if and only if gcd(i, 6) = 1 - Hence the primitive elements are 3 and 3⁵ (mod 7) = 5

Answer 98

- Suppose that p \> 2 is prime and α ∈ Z^*_p. Then α is a primitive element modulo p if and only if, for all primes q|(p - 1): * α^(p-1)/q= 1 (mod p)

Answer 99

- Let p be prime and let α ∈ **Z**^*_p be a primitive element modulo p - If β ∈ **Z**^*_p such that: * α^a ≡ β (mod p) , then a is called the discrete logarithm of β and is denoted log_αβ

Answer 100

- Given p prime, α a primitive element modulo p and β ∈ **Z**^*_p find an element a, 0 ≤ a ≤ p − 2 such that α^a ≡ β (mod p)

Answer 101

- Public parameters: p prime, and ↵, a primitive element modulo p which has order p − 1. 1. Alice chooses 1 ≤ a ≤ p − 1 at random and computes A = α^a (mod p) and sends A to Bob. 2. Bob chooses 1 ≤ b ≤ p − 1 at random and computes B = α^b (mod p) and sends B to Alice. 3. Alice receives B and computes B^a = α^ab (mod p) 4. Bob received A and computes A^b = α^ab (mod p) 5. k = A^b = B^a = α^ab (mod p)

Answer 102

- Also known as CDH - Given p prime, α a primitive element modulo p and two elements β, γ ∈ Z^*_p find δ ∈ Z^*_p such that log_αδ ≡ log_αβ x log_αγ (mod p) - That is, given α^a and α^b, find α^ab

Answer 103

- Given a finite cyclic group G of order n, α a generator of G and β ∈ G find an element a, 0 ≤ a ≤ n − 1 such that α^a = β

Answer 104

- Compute α, α²,α³, . . . until β = α^a is found - Compute a new term in the list by multiplying the previous term by α - Only store the current element of the list - Total time: O(n) - Total space: O(1)

Answer 105

- It is a time-memory trade-off - Let m = ⌈√n⌉ - If α^a = β then we can write: * β = α^a = α^mj+i for 0 ≤ j, i \< m - It's now possible to write α^mj+i = α^mjαⁱ, and hence β = α^mjαⁱ⇒ βα⁻ⁱ = α^mj

Answer 106

1. m = ⌈√n⌉ 2. Compute list L1: (0,α⁰), (1,α^m), (2,α^2m),...,(m − 1,α^(m−1)m) 3. Sort list L1 of pairs (j, α^mj) on the value of α^mj 4. Compute list L2: (0,βα⁰), (1,βα⁻¹), (2,βα⁻²), ...,(m−1,βα−(m−1)) 5. Sort list L2 of pairs (i, βα⁻ⁱ) on the value of βα⁻ⁱ 6. Find (j, y) ∈ L1 and (i, y) ∈ L2 7. log_αβ = (mj + i) (mod n)

Answer 107

- Can not be used in all groups - Faster than exhaustive search and Shanks - Resembles a factoring algorithm such as Dixon’s random squares - Under various “reasonable” assumptions the pre-computation phase has asymptotic running time: O(e^{(1+o(1))√(ln p ln ln p)}) * And then to find a particular discrete logarithm: O(e^{(1/2+o(1))√(ln p ln ln p)})

Answer 108

1. Select the factor base of primes B = {p₁, p₂,..., p_B} 2. Collect congruences modulo p of the form: α^x_j ≡ p₁^a_1j, p₂^a_2j, p_B^a_Bj (mod p) for 1 ≤ j ≤ C * These can be written as relations among discrete logarithms of the factor base elements: * x_j ≡ a_1j log_αp₁ +...+ a_Bjlog_αp_B (mod p − 1) *

Cryptography Flashcards

(148 cards)