Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
ELEC6242
Cryptography
| Question | Answer |
|---|---|
| SYMMETRIC ENCRYPTION | TITLE CARD |
| How do you calculate entropy? | H(X)=sum(p_i * log_2(1/p_i)) |
| Give the equation for Shannon Perfect Secrecy. | if |m1|=|m2|, then Pr[E(k,m1)=c]=Pr[E(k,m2)=c] |
| What has Shannon Perfect Secrecy? | OneTime Pad (OTP) |
| What is Kirchhoff's principle? | The cipher must not depend on the secrecy of the mechanism, it must not matter if it falls into the hands of the enemy. |
| What must be true for a cipher to achieve the perfect secrecy? | |K|>=|M| |
| What is Computational Perfect Secrecy? | Pr[E(k,m1)=c]-P[E(k,m2)=c] is negligible" |
| What are the 3 requirements of Pseudo Random Permutation (PRP)? | 1. Exists “efficient” deterministic algorithm to evaluate E(k, x) 2. The function E( k, ) is one-to-one 3. Exists “efficient” inversion algorithm D(k, y) |
| Give examples of PRPs? | 3DES, AES |
| Define semantically secure. | E is semantically secure if for all “efficient” A Adv[A,E] is negligible. Where: Adv[A,E]=|EXP_A[E(k,m1)] - EXP_A[E(k,m2)]| |
| How many mappings are there is a block cipher? | (2^N)! |
| What is the required size of the key for an ideal block cipher? | log_2((2^N)!) |
| What 2 concepts did Shannon introduce that a cipher needs? | Diffusion: Dissipates the redundancy of the plaintext by spreading it out over the cipher text. (permutation) Confusion: Obscures the relationship between ciphertext and the plaintext in order to hide any statistical patterns. (i.e. substituation) |
| Draw the Feistel Cipher. | L_(i+1) = R_i R_(i+1) = F(R_i, K_i) xor L_i |
| What are the parameters of the Feistel Cipher? | Block size Key size Number of rounds Subkey generation Round function |
| What are the parameters of DES? | Type: Feistel Cipher Number of Rounds:16 Block Size: 64 Length of Key: 56 |
| What happens before and after the Feistel cipher in DES? | Initial permutation. Final permutation. |
| What is the steps of the round function in DES? | Expansion/Permutation Table (32 -> 48) XOR with Round Key (48). Substitution/Choice Table (48 -> 32) Permutation |
| What is the final permutation in DES? | An inverse of the initial permutation. IP(IP^(-1))=I |
| How does the substitution step in the round function work in DES? | Separate 48 bits into 8 6-bit words. Bits 1 and 6 define the row. Bits 2,3,4 and 5 define the column. Use a substitution table. |
| What is important for a substitution table? | Should not be close to a linear function. |
| What is the main problem with DES? | Inadequate key length |
| What are the advantage of DES? | Avalanche effect: - A small change in the plaintext or in the key results in a significant change in the ciphertext. - an evidence of high degree of diffusion and confusion |
| What is triple DES? | C=E_k1(D_k2(E_k1(P))) |
| Why does triple DES involve a decryption step? | To preserve compatibility with DES; a hardware circuit that implemented 3DES (with EDE) could also be used to do DES as well. |
| Explain the meet-in-the middle attack on 2DES. | Encrypt P with all 2^56 possible keys for K1. Decrypt C with all 2^56 possible keys for K2. If E K1’ (P) = DK2’ (C), try the keys on another (P’, C’). If works, (K1’, K2’) = (K1, K2) with high probability. |
| How many steps does a meet-in-the-middle attack take on 2DES? | O(2^57) |
| How many steps does a meet-in-the-middle attack take on 3DES? | O(2^2k) |
| What are the steps of each round in AES? | Byte substitution Shift row Mix column Add round key |
| What does AES operate in? | Galois field, GF(2^8) |
| What is addition in GF? | XOR |
| What is multiplication in GF? | Modular using prime polynomial. |
| Explain the byte substitution step of AES. | LOOK AT SLIDES |
| Explain the shift row step of AES. | LOOK AT SLIDES |
| Explain the mix column step of AES. | LOOK AT SLIDES |
| What are 3 implementations of AES? | Pre-compute round functions (use look up table) Pre-Compute S-box only. No Pre-Computation |
| What are the properties of AES? | Block size: 128 bit Key length: 128, 192, 256 bit Number of rounds: 10, 12, 14 |
| ELLIPTIC CURVE CRYPTOGRAPHY (ECC) | TITLE CARD |
| What is the main benefit of using ECC? | The key sizes are smaller compared to RSA and other systems |
| What the elliptic curve equation? | y^2 = x^3 + ax + b (includes a "point at infinity") |
| When can an elliptic curve not be used for cryptography, and what is the equation to check this? | When it has a double root (i.e. 4a^3 + 27b^2 is 0), as the curve needs 3 distinct roots |
| How do you add two points on an elliptic curve? | Draw a line between the two points, find where this line intersects the elliptic curve again, reflect this in the $x$-axis |
| What are the equations for adding two points $P$ and $Q$ on an elliptic curve? | - P = (x_1, y_1) - Q = (x_2, y_2) - $P + Q = R + (x_R, y_R)$, where - $x_R = \lambda^2 - x_1 - x_2$ - $y_R = -y_1 + \lambda(x_1 - x_R)$, where - $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$ |
| How do you add the points $P$ and $-P$ on an elliptic curve? | - Results in a vertical line which does not intersect at a third point - This means $P + -P$ is defined instead as $O$ (the point at infinity) |
| How do you double a point on an elliptic curve when its $y$ value isn't 0? | Draw a tangent to the curve at the point, find where this line intersects the curve again, reflect this point in the $x$-axis |
| What are the equations for doubling a point $P$ when $y_P \ne 0$? | - P = (x_1, y_1) - 2P = R = (x_R, y_R), where - x_R = \lambda^2 - 2x_1 - y_R = -y_1 + \lambda(x_1 - x_R), where - \lambda = (3x_1^2 + a)/(2y_1) |
| How do you double, triple, quadruple a point $P$ when its $y_P = 0$? | - By definition, 2P = 0 - 3P = 2P + P = O, 4P = 2P + 2P = O and so on |
| What is the definition for an elliptic curve abelian group? | - Any elliptic curve E over field F is an abelian group under the operation + defined above, where - E = E(F) = {(x,y) | x,y \in F, y^3 = x^2 + ax + b} U {\infty, \infty}, given 4a^3 + 27b^2 != 0 |
| What does it mean to compute an elliptic curve over a finite field? | All x-values are restricted to a given range, meaning all computations are done with regard to mod p, where p > 3 |
| What is the definition of an elliptic curve over $Z_p$? | - Consider a prime p > 3 - We define the elliptic curve E over Z_p as follows - E = E(F) = {(x,y) | x,y \in F, y^2 = x^3 + ax + b mod p} U {\infty, \infty} - 4a^3 + 27b^2 != 0 mod p |
| Find all points on the elliptic curve $y^2 = x^3 + 2x + 1$ over $Z_5$ | - Check validity: 4a^3 + 27b^2 = 4 * 2^3 + 27 * 1^2 = 59 = 4 mod 5 - Once valid, calculate points (TOO LONG TO WRITE) - The points are (0, 1), (0, 4), (1, 2), (1, 3), (3, 2), (3, 3), as well as the point at infinity O |
| What is the order of an elliptic curve $E$ over finite field $Z_P$ (denoted $|E|$)? | The number of points on the curve plus O |
| What is Hasse's theorem for the bounds of $|E|$, where $E$ is an elliptic curve in finite field $Z_p$? | p + 1 - 2 \sqrt{p} <= |E| \<= p + 1 + 2 \sqrt{p} |
| How many points does the elliptic curve $y^2 = x^3 + x + 6$ in $Z_{11}$ have? | - Make a table plotting the square of each element in Z_11 (which is 1, 2, ..., 10) - Work out the value of x^3 + x + 6 mod 11 for each element in Z_11 - Add all of the solutions, then add 1 for O, which gives |E| = 13 in this case |
| Given the elliptic curve $y^2 = x^3 + x + 6$ in $Z_{11}$ and the point $P = (2, 7)$, find $2P$ | 2P = (5, 2) (use the equations) |
| What is the Euler Theorem? | - (Z_p)* is a cyclic group, that is \exists g \in (Z_p)* such that {1, g, g^2, g^3, ..., g^{p-2}} = (Z_p)* - g is called a generator of (Z_p)* |
| Is 2 a generator of $(Z_5)^*$? | - Yes - {1, 2, 2^2, 2^3} = {1, 2, 4, 3} = (Z_5)* |
| Is 2 a generator of $(Z_7)^*$? | - No - {1, 2, 2^2, 2^3, 2^4, 2^5} = {1, 2, 4} |
| What is $<g>$? | The group generated by g ({1, g, g^2, g^3, ...}) |
| What is the order of $<g>$? | - The size of <g> - ord_p(g) = |<g>| = (smallest a s.t. g^a = 1 in Z_p) |
| What is $<P>$? | - The group generated by P ({O, P, 2P, 3P, ... (m-1)P}) - where mP = O |
| What is the order of $<P>$? | The size of <P> |
| What is the order of $P = (4,1)$ for elliptic curve $E: y^2 = x^3 + 2$ over $Z_5$? | - 2P = (3, 3), 3P = (2, 0), 4P = (3, 2), 5P = (4, 4), 6P = O - Means the order of P is 6 |
| What is the elliptic curve discrete logarithm problem (ECDLP)? | Given points P and Q in an elliptic curve E over a finite field Z_p, find an integer i satisfying Q = i.P |
| What are the steps for elliptic curve Diffie-Hellman key exchange? | See slides |
| Perform the elliptic Diffie-Hellman key exchange where $E: y^2 = x^3 + 7x + 3 \mod 37$ and $G = (2, 5)$ | See slides, results in key (22, 1) |
| How do you encrypt a message with Elagmal encryption? | - Bob wants to send a message m < n to Alice - Bob chooses a random 0 < k < n - Bob computes kQ{Alice} = kaG = Q{Shared} = (x, y) - Bob sends C1 = kG to Alice - Bob sends C2 = x*m mod p to Alice |
| How do you decrypt a message with Elgamal encryption? | - Alice computes a*C1 = akG = Q{Shared} = (x, y) - Alice computes the multiplicative inverse of x in Z_p (i.e. x^-1 mod p) - Alice computes $x^{-1} * C2 = x^{-1} * x * m \mod p = m$ |
| Perform Elgamal encryption with $E : y^2 = x^3 + 7x + 3 \mod 37$ and a generator $G = (2, 5)$ | See slides |
| How can you choose which curve is good for cryptography? | - Should be a cyclic group - If the order of an elliptic curve E over a finite field F_Q (denoted |E|) is a prime number, then the group is cyclic and every element is a generator |
| What are 5 mode of block ciphers? | Electronic Code Book (ECB) Cipher Block Chaining (CBC) Couter Mode (CTR) Cipher Feedback Mode (CFB) Output Feedback Mode (OFB) |
| How does Electronic Code Book (ECB) work? Draw diagram. | Each block is encrypted independently of the other blocks. |
| What is the problem with Electronic Code Book (ECB)? | Repetitive information contained in the plaintext may show in the ciphertext, if aligned with blocks. When the key is used to encrypt many block , the adversary can see many ciphertexts with same key. |
| When is Electronic Code Book secure? | You can only use ECB securely if the message length is equal to the data block length (e.g.128 bit for AES) and you change the key for each message. |
| What is chosen-plaintext attack (CPA)? | Where in the attacker can obtain the encryption of arbitrary messages of his choice and deduce the secret key (there are many variations of such an attack). In both DES and AES one pair of (c, m) is enough to find the key through exhaustive search. |
| Explain the structure of Cipher Block Chaining (CBC). | SEE SLIDES |
| What are the disadvantages of Cipher Block Chaining (CBC)? | The same key is used for all blocks, so it's prone to CPA (Chosen-Plaintext Attack). Error propagate. Initialisation vector (IV) must be known to both the sender and reciever. (must be secret) Serial processing is slow. |
| When is Cipher Block Chaining (CBC) secure against CPA? | q^2 * L^2 << |X| q: the number of messages encrypted using the same encryption key (K) L: the maximum length of message |
| How many block until we have to change the key for both AES and DES until CBC? | SLIDE 52 |
| How does Couter Mode (CTR) work? Draw diagram. | SEE SLIDES |
| What are the advantages of Counter Mode (CTR)? | Needs only the encryption algorithm Fast encryption/decryption; blocks can be processed (encrypted or decrypted) in parallel; good for high speed links. Error don't propagate. |
| What are the disadvantages of Counter Mode (CTR)? | The same key is used for all blocks (prone to CPA). IV should not be reused. |
| When is Counter Mode (CTR) secure against CPA? | q^2 * L << |X| |
| How does Cipher Feedback Mode (CFB) work? Draw diagram. | SEE SLIDES |
| When is Cipher Feedback Mode (CFB) appropriate to use? | When data arrives in bits/bytes (as a stream). |
| What is a problem with Cipher Feedback Mode (CFB)? | A corrupted ciphertext segment during transmission will affect the current and next several plaintext segments. |
| How does Output Feedback Mode (OFB) work? Draw diagram. | SEE SLIDES |
| What is a ciphertext-only attack? | Where the adversary tries to deduce the decryption key or plaintext by only observing ciphertext. Any encryption scheme vulnerable to this type of attack is considered to be completely insecure (e.g. frequency analysis on a shift cipher). |
| What is a known-plaintext attack? | Where the adversary has a quantity of plaintext and corresponding ciphertext. This type of attack is typically only marginally more difficult to mount.(e.g. meet in the middle attack on DES) |
| What is a chosen-plaintext attack? | Where the adversary chooses plaintext and is then given corresponding ciphertext. The adversary uses any information deduced in order to recover plaintext corresponding to previously unseen cipher text. |
| What is a side channel attack? | Analysis of information leaked from the physical implementation of the system such as electromagnetic radiation, power consumption, sounds, etc, to deduce the key. |
| What is the typically search time for Quantum attacks? | O( |X|^(1/2) ) |
| What is computational complexity? | Mathematics that focuses on classifying computational problems according to their inherent difficulty. |
| What is big O notation? | Used to classify algorithms by how they respond to changes in input size in terms of their processing time or working space requirements. |
| What is 113 in Z_24? | 17 |
| Compute 2/3 in Z_7. | 3 |
| When does x have an inverse in Z_N? | gcd(x, N) = 1 |
| What algorithm do we use to calculate a gcd? | Euclid’s Algorithm |
| Prove Euclid’s Algorithm. | SEE SLIDES |
| Calculate gcd(60,22). | 60 = 2 x 22 + 16 gcd(60, 22)=gcd (22, 60 mod 22) = gcd(22, 16) 22 = 1 x 16 + 6 ... 16 = 2 x 6 + 4 ... 6 = 1 x 4 + 2 ... 4 = 2 x 2 + 0 ... |
| Explain the steps of the Extended Euclidean Algorithm. | 1. Check if x has an inverse in Z_n (gcd(x, N) must be equal to 1). 2. Find a, b such that: a⋅x + b⋅N = 1. 3. a is the inverse of x in Z_n |
| Compute 10/8 in Z_11 with the Extended Euclidean Algorithm. | 4 |
| What is Fermat Little Theorem? | ∀ x ∈ (Z_p)* : x^(p-1) = 1 in Z_p |
| What is (Z_N)*? | Set of invertible elements in Z_N. |
| How can we use Fermat Little Theorem to compute the inverse? | ∀ x ∈ (Z_p)* x ∈ (Z_p ) * x⋅x^(p-2) = 1 in Z_p 1/x = x^(p-2) in Z_p |
| Is using Fermat Little Theorem to calculate the inverse more efficient than the Extended Euclidean Algorithm? | No |
| What is the time complexity of using Fermat Little Theorem to calculate the inverse? | O(n^3) |
| Compute 10/8 in Z_11 using Fermat Little Theorem. | 10/8 = 10 * 1/8 = 10* 8^(-1) 8^(-1) = 8^(11-2) = 8^9 = 134217728 = 7 in Z_11 10 * 7 = 70 = 4 |
| How do you computer x^(1/e) in Z_p if gcd(e, p-1)=1? | 1. Find the modular inverse of e inܼ Z_p-1 (let us call it d). 2. Computeܿ c^d in Z_p. |
| Compute 7^(1/11) in Z_17 | First we check if gcd(11, 16) = 1. Then we compute 1/11 in Z_16, which is 3. 7^3 = 3 in Z_17 |
| How do we check if x in (Z_p)* is a Q.R? | x^((p-1)/2) = 1 |
| How do you calculate the square root of a modular? | p = 3 (mod 4) if p = 3 (mod 4) and c∈(Z_p)* is Q.R, then sqrt(c) = c^((p+1)/4) |
| What are the Q.R of Z_11? | 1,4,9,5,3,0 |
| Compute sqrt(6) given 6 is a Q.R in Z_43. | 6^((43+1)/4)=6^11=36 |
| Explain the 4 properties of a group. | CLOSURE: ∀ a, b ∈ G then (a * b) ∈ G . ASSOCIATIVITY: ∀ a, b, c ∈ G then (a * b) * c = a *(b * c). IDENTITY: there exists e ∈ G such that a * e = a = e * a for all a ∈ G. INVERTABILITY: for every a ∈ G there exists ai ∈ G such that a * ai = e = ai * a |
| Prove that Z_N is a group under addition modulo N. | LECTURE number theory SLIDE 28 |
| What is a Alebian group? | A group G is said to be commutative (or abelian) if (a* b)= (b *a) for all a, b ∈ G. |
| What is a cyclic group? | A group G is said to be cyclic if it has a generator g, an element g ∈ G such that every element a ∈ G has the form a= g^i (or ig in additive notation) for some integer i. |
| Define Euler’s Totient ϕ(N) function in terms of Z_N. | ϕ(N) = |(Z_N)*| |
| Define Euler's Totient ϕ(N) function in terms of primes p and q. | For N= p (p prime) ϕ(N) = N-1 For N=p.q (p,q prime) ϕ(N) = (p-1)(q-1) |
| What is Euler's generalisation of Fermat's Theorem? Explain how this is the case. | forall x in (Z_N)*: x^(ϕ(N)) mod N = 1 |
| What is the Discrete Logarithm Problem? | The task of finding the exponent x in the equation g^x≡y(mod n), forming the basis of security for many cryptographic systems. It's a hard problem. |
| What is the best known algorithm to solve the Discrete Logarithm Problem? What's it's time complexity? | General number field sieve e^O(cuberoot(N)) |
| What is the difference between compression and encryption? | Compression: Extract the information from the data and encode as efficiently as possible with a public algorithm. Encryption: Diffuse a key into the information as much as possible & encode with a public algorithm. |
| What is the best way to practically transmit secure data safely? | 1. Compress the data 2. Encrypt 3. Add error detection & recovery |
| Cryptanalysis relies on what? | On exploiting redundancies in the plaintext (data). Compression removes these. |
| Should you encrypt on compress the data first? | Compressing first (which is fast) means that you can pipeline the information flow. Data is contracted by the compressor, so the volume of data into the encryption system is less. |
| What is Steganography? | Conceals the existence of the message. The message itself may or may not be encoded. |
| Cryptanalysis usually involves what techniques? | 1. Frequency analysis can indicate possible letters; enhanced by cribs. 2. A “crib” is a known sequence of letters or words. 3. We can also make guesses about common words based on the context of letters. |
| Give some Cryptoanalysis tips. | LECTURE Classic Cryptographic Systems SLIDE 13 |
| What is a Polyalphabetic Cipher? | A polyalphabetic cipher is a type of encryption that uses multiple substitution alphabets to encode the plaintext. |
| How does the Vigenère Cipher work? | Each letter of the key corresponds to a Caesar cipher shift based on that letters position in the alphabet. For example, c in the key shifts the corresponding plaintext letter by 3. |
| How do you crack the Vigenere Cipher using Cryptoanalysis? | 1. Find the length of the key. 2. Divide the message into that many simple substitution encryptions. 3. Use frequency analysis to solve the resulting simple substitutions. |
| State the 2 methods to get the key length of the Vigenere Cipher. | 1. Kasisky test 2. Index of coincidence (Friedman) |
| How does the Kasisky test work? | 1. Search for pairs of identical segments of length at least 3 2. Record distances between the two segments: ∆1, ∆2, … – 3. The key length (m) should divide the gcd( ∆1, ∆2, …) |
| How do you calculate the Index of Coincidence (IoC)? | LECTURE Classic Cryptographic Systems SLIDE 18 |
| What is the IoC of English? | 0.066 |
| Will a monoalphabetic Cipher have a IoC close to English? | Yes |
| Will a polyalphabetic Cipher have a IoC close to English? | No |
| How do we use the Index of Coincidence (IoC) to work out the key of the Vigenere cipher? | 1. Make a guess of the key length (e.g. m) 2. Arrange the text into a matrix 3. Calculate IC for each row (Y1 -Ym) 4. If the width of the matrix is a multiple of the actual key length than: IoC =0.065 5.. Repeat the process until you find correct key |
| How does the Enigma Machine work? | The Enigma machine worked by using a series of substitution ciphers where the connections were made electrically. • The idea behind the rotors was to shift each substitution alphabet in addition to making the connections. |
| What is a transposition cipher? | Rearrange the order of basic units (letters/bytes/bits) without altering their actual values. |
| Give 2 examples of transposition ciphers. | Rail Fence Cipher Columnar Transposition Cipher |
| How did the Scytale transposition cipher work? | The secret message was written on the ribbon while the ribbon was wrapped on the rod. The ribbon was then removed and transported to the other field commander who had an identical rod. If the ribbon was intercepted it look like jumble of letters. |
| Explain the Rail Fence Cipher. | The Letters of the message are written diagonally over a number of rows (rails)then read off cipher row by row. The key for the rail fence cipher is just the number of rails |
| Explain the Columnar Transposition Cipher. | The message is written out in rows of a fixed length and then read out again column by column. Both the width of the rows and the permutation of the columns are usually defined by a keyword. |
| Encrypt the message M below using the keyword Destiny M= {Attack postponed until two} | AODW TSUO COIX KNLN TTNF APTG PETU |
| What are the steps of the Columnar Transposition Cipher? | 1. The message is written out in rows of key length. The empty spaces at the end are filled with random letters. 2. The columns are read according to the alphabetical order of the letters in the keyword. |
| Decrypt the following message: Trsao rih oivo geetn tootn bfsafme cepcogep ihtetcen Was encrypted using the Columnar Transposition Cipher. | To improve is to change to be perfect is to change often. |
| How do you decrypt the Columnar Transposition Cipher? | 1. Calculate possible key lengths as divisors of the message length. 2. Arrange the ciphertext into columns based on key length. 3. Rearrange the columns in different orders to see if they form readable plaintext. 4. If not try another key length. |
| What are 3 automatic methods to crack the Columnar Transposition Cipher? | Brute force. Dictionary attack. Hill climbing. |
| Give steps to crack Columnar Transposition Cipher using hill climbing. | LECTURE Classic Cryptographic Systems SLIDE 33 |
| What Fitness Metric is a measure to determine how similar a piece of text is to English text? | 1. Single letters frequencies (not very relevant to the Hill Climbing method) 2. Diagram's statistics: the probability of a sequence of two letters 3. Trigrams statistics: the probability of a sequence of three letters 4. Quadgrams statistics: ... |
| What are product ciphers? | Using substitutions and transpositions cipher in sequence. |
| What is the difference between encryption and steganography? | Cryptography: Although encypted and unreadable, the existence of data is not hidden. Steganography: No knowledge of the existence of the data. |
| What does a Steganosystem consist of? | Cover-Object: Original, unaltered medium. Embedding: Sender hides a message in the cover-object using a key to create a stego-object. Stego-Object: Medium containing the hidden message. Recovering: Receiver extracts the hidden message using the key. |
| What is a security requirement of Steganosystems? | Stego-objects should be indistinguishable from cover-objects. |
| Give 3 examples of text based stenography. | 1. Every n-th character. 2. Distribute plaintext letters randomly in the cover-text and then use a mask to read it. 3. Using errors or stylistic features at predetermined points in the cover data. |
| Give an example of visual steganography. | Take a 24-bit full colour image = 3x8-bit RGB or CMY . Take the least significant bit of each plane and use for a secret message. |
| Which is typically faster symmetric or asymmetric encryption? | symmetric (i.e. public key) algorithms are generally 10^3 slower than symmetric algorithms. |
| What does public/asymmetric encryption rely on? | Trap door one way functions. |
| What is a trap door one way function? | Construct a pair of functions f, g=f^(-1) Given x, evaluation of f(x) is trivial Given only f and y, evaluation of f^(-1)(y) computationally difficult But, given g & y, evaluation of f^(-1)(y) = g(y) is trivial. |
| Give an example of a trap door one way function. | RSA |
| What is a one way function? | Given x, evaluation of f(x) is trivial. Given y, evaluation of f^(-1)(y) computationally difficult. |
| Give an example of a one way function. | discrete log |
| Cryptographic systems can be classified into what two distinct categories? | 1. Shared Key Systems 2. Public Key Systems |
| What are problem with Shared Key Systems? | 1. Compromised key means interceptors can decrypt any ciphertext they have acquired. Keys can be changed frequently to limit damage. 2. Distribution of keys is problematic: keys must be transmitted securely. |
| Explain public key systems. | Each user has a pair of keys: a public key and a private key. The public key is used for encryption. The key is known to the public(i.e. other users of the systems). The private key is used for decryption.The key is only known to the owner. |
| What is the definition of a trap door function? | X⟶Y is a triple of efficient algorithms (G, F, F -1 ): 1. Key generator (G): randomized algorithm outputs a key pair (pk, sk) 2. Encryption function (pk,⋅): deterministic algorithm X ⟶Y 3. Decryption Function: F -1 (sk,⋅): Y ⟶ X that inverts F(pk,⋅) |
| How not to use a trap door function? | Never encrypt by applying F directly to plaintext. |
| What are the step of key generation in RSA? | Choose random primes p,q 2. Set N=pq. 3. Choose integers e , d s.t. e⋅d = 1 (mod ϕ(N) ) 4. Output pk = (N, e) , sk = (p,q , d) |
| Generate RSA keys with p=17 and q=11 and encrypt M=90 | Publish public key : pk = (N, e) =(7,187) Keep secret private key : sk = (p,q , d)=(17,11,23) Encryption: C = 90^7 mod 187 = 95 Decryption: M = 95^23 mod 187 = 90 |
| Construct an RSA encryption scheme, based on the two primes 5, 11, and encrypt the message M=2. | Publish public key : pk = (N, e) =(55,3) Keep secret private key : sk = (p,q , d)=(5,11,27) |
| How many primes are <=sqrt(n)? | (2 sqrt(n))/ln(n) |
| Give a brute force approach for finding p and q (for RSA). | 1. Find sqrt(n). 2. It is clear that either p<=sqrt(n) or q<=sqrt(n). 3. Divide n by each of the primes until a factor is found. |
| What is important when choosing p and q for RSA? | They should not be too close together, for otherwise it might be possible to factorize n by Fermat factorization. |
| Explain the theory behind Fermat's Factorization. | LECTURE rsa SLIDE 19 |
| Give the steps for Fermat's Factorization. | 1. Choose integer i slightly larger than sqrt(n). 2. Test whether i^2-N is a perfect square j^2 for some integer j. 3. If i can found then: N=i^2-j^2=(i-j)(i+j)=p*q |
| Factorise N=11413 with Fermat's Factorization. | p=101 q=113 |
| Why isn't textbook RSA semantically secure? | Because it is deterministic, producing the same ciphertext for the same plaintext. Vulnerable to chosen-plaintext attacks. |
| How is RSA done in practice? | SEE SLIDES |
| What attack are there against RSA? | Timing attack. Power attack. |
| Explain the timing attack against RSA. | In an RSA based system, the time it takes to compute y^d (mod N) can expose d. |
| How do you counter timing attacks against RSA? | Countermeasures are based on masking the times taken by operations for example by adding random operation to a loop or random delays. |
| Explain the power attack against RSA. | It exploits the variation of power consumption of a cipher hardware under different input values to infer the key. For example by analyzing the power consumption of a smartcard while it is computing c^d (mod N) one can expose d. |
| How do you counter power attacks against RSA? | Countermeasures include masking the actual power consumption of the circuit during computation through the use of redundant operations. Other methods are based on the use of power balanced logic which consume the same amount of power regardless of input. |
| In a public-key system using RSA, you intercept the ciphertext y = 9 sent to a user whose public key is e = 5, n = 35. What is the plaintext x? | x = 4 |
| In a public-key system using RSA, you intercept the ciphertext y = 30 sent to a user whose public key is e = 13, n = 77. What is the plaintext x? | x = 2 |
| What is message integrity? | Ensures a received message has actually originated from the intended party and hasn't been modified |
| What are some applications of message integrity? | - Protecting operating systems from viruses - Ensuring the integrity of bank transactions |
| Does privacy imply authenticity? | No, secrecy and integrity are orthogonal concerns, one can exist without the other |
| What are the two algorithms which define a MAC? | Signing algorithm (tag generation): takes a message `m` and a key `k` and outputs tag `t`. Verification algorithm: takes key `k`, message `m` and tag `t` and outputs `1` (accept) or `0` (reject) |
| What is the formal definition of a MAC? | - MAC I = (S, V) defined over (K, M, T) is a pair of algorithms - S(k, m) outputs t in T - V(k, m, t) outputs 1 or 0 |
| What is the consistency condition in hashing? | Consistency condition: for all ms and corresponding ks, V(k, m, S(k, m)) = 1 |
| What are the steps for message integrity? | Sender generates a tag with the signing algorithm S(k,m) -> t Sender sends m and t Receiver uses the verification algorithm to get a result V(k, m, t) -> {1, 0} |
| How does a chosen message attack work in context of verification? | - Adversary sends chosen messages to the sender (authenticator) - Adversary receives valid tags back, corresponding to each chosen message - Adversary forwards on the messages and valid tags |
| What is the definition of forgery? | - If an attacker A is able to produce a pair (m', t') such that m' didn't originate from the sender, and V(k, m', t') = 1 - This pair (m', t') is called forgery |
| When is a MAC considered secure? | If and only if the MAC is able to detect any attempt by the adversary to modify the transmitted data. |
| What is a replay attack? | Attacker re-sends old messages that have valid tags/ Need to prevent replay attacks at a higher level, requires state. |
| What is a pseudo random function (PRF)? | F: K x X -> Y such that there exists an efficient algorithm to evaluate F(k, x) |
| What is a pseudo random permutation (PRP)? | E: K x X -> X such that there exists an efficient deterministic algorithm to evaluate E(k, x), the function E(k, .) is one-to-one, and there exists an efficient inversion algorithm D(k, y) |
| How can you construct a MAC (S, V) from a PRF F: K x X -> Y? | - S(k, m) := F(k, m) - V(k, m, t) outputs 1 if t = F(k, m) and 0 otherwise |
| How does ECBC-MAC work? | See the slides, broadly splits the message into segments, F takes an input of k1 and the XOR of the previous output and the current segment, for the final block it takes in the previous output and k2. |
| What is a hash function? | Maps arbitrary length inputs to a short fixed-length digest. H: {0, 1}^N -> {0, 1}^n where N is much larger than n. |
| What is a pre-image? | If y = H(x), x is a pre-image of y. Each hash value typically has multiple pre-images. |
| What is a collision? | A pair of distinct inputs x, x' such that H(x) = H(x') |
| What are the two requirements for hash functions used for secure applications? | Pre-image resistant: computationally infeasible to find a pre-image of a hash value Collision resistant: it is computationally infeasible to find a collision |
| What some are applications of hash functions? | Build MACs Create a one-way password file to store hashes of passwords Intrusion detection and virus detection by creating hashes of files on a system and monitoring them for changes |
| What are the principles of the Merkle-Damgard scheme? | See the slides, broadly breaks the message down into blocks of size K, appends padding to the last block if it is smaller than K, adds a padding block if the message is a multiple of K, padding contains a serious of 1000 to mark the end. |
| How is the Davies-Meyer compression function F constructed? | - Consider a block cipher E (K x {0, 1}^n) -> {0, 1}^n - The Davies-Meyer compression function is constructed as F(V, m) = E(m, H) ⊕ H |
| Explain the principles of rotor cipher machines. | Based on rotors whose movement producing ever-changing alphabetic substitutions. Produces a complex polyalphabetic substitution cipher which changes for every letter. |
| Explain the process of generating round keys for AES. | LECTURE Symmetric Cryptographic Systems SLIDE 42 |
| What versions of Secure Hash Algorithm (SHA) are mentioned? | SHA, SHA-1 (insecure, phased out), SHA-2 (SHA-256, SHA-384, SHA-512), SHA-3 |
| What is the equation for a keyed hash function as a MAC? | S(k, m) = H(k ll m) |
| What are the 5 HMAC design objectives? | - Use hash functions without modifications - Easy replaceability of the embedded hash function - Preserve the original performance of the hash function - Use and handle keys in a simple way - Well-understood cryptographic analysis of authentication |
| How is HMAC specified in RFC2104? | S(k, m) = H(k ⊕ opad ll H(k ⊕ ipad ll m)) |
| What is a brute force attack on hash functions? | - Hash function H: {0, 1}^* -> {0, 1}^n - Compute H(x_1), ..., H(x_{2^n+1}) - Attack guarantees finding a collision in time O(2^n) hashes |
| What is the birthday problem? | - For 23 people, the probability that at least two of them have the same birthday is over 50% - Calculated by finding the probability that nobody has the same birthday, and subtracting this from 1 |
| What is a birthday attack? | - Let H: M -> {0, 1}^n be a hash function, and |M| >> 2^n - Choose 2^{n/2} random messages in M: m_1, ..., m_{2^{n/2}} - For i = 1, ..., 2^{n/2}, compute t_i = H(m_i) \in {0, 1}^n - Look for a collision t_i = t_j - Finds a collision in O(2^{n/2}) |
| What does a digital signature provide? | - Data origin authentication of the sender - Non-repudiation |
| What are the 3 algorithms making up the digital signature systems (DSS) triple? | - Key generation algorithm, chooses a random private key from a set, returns this and its public key - Signing algorithm, given a message and private key it outputs a signature - V takes a message, public key and sig, either accepts or rejects the sig |
| How does RSA signing work? | Apply its signing function to the original message and the private key to get a signature. |
| How does RSA signature verification work? | Apply its verification function to the public key and the signature, outputs 1 if it is valid |
| What is a vulnerability of RSA signatures? | If two messages are received, a third can be forged - Protect against this by using collision-resistant hash functions before signing messages |
| What are the 3 types of authenticated encryption? | - Encrypt-then-MAC (EtM) - Encrypt-and-MAC (E&M) - MAC-then-Encrypt (MtE) |
| Explain the functionality of the plug-board used in the Enigma machines. | The plugboard significantly increased the machine's security by allowing additional scrambling of the letters before they were processed by the rotors. |
| Discuss how the number of pulgboard settings can be calculated, assuming it has 10 sockets and 4 cables. | SEE SLIDES |
| Draw the Merkle-Damgard scheme. | SEE SLIDES |
| Polarization of photons can be though of as ... | ... the direction of oscillation of the electric field associated to a light wave. |
| How do we polarize a photon? | Pass it through a filter. |
| What is BB84? | First quantum key distribution scheme. |
| Give the steps of BB84. | SEE SLIDES |
| Explain how Eavesdropping is detected in BB84. | SEE SLIDES |
| What fundamental Quantum Mechanism means that Eavesdropping can be detected? | The measurement of a state not only measures but actually transforms that state. |
| If the wrong basis is used to measure the polarization of photons, than we will get accurate measurement with a probability of ... | ... 50% |
| What is E_max in the context of BB84? | The maximum allowed error rate. If the error rate is higher, then Eavesdropping is detected. |
| What can Eve do to Eavesdrop in BB84 without being detected? | Still possible for Eve to eavesdrop just a few photons, and hope that this will not increase the error to an alarming rate. If so, Eve would have at least partial knowledge of the key. |
| What can Qubits be? | A single photon, a nucleus or an electron. |
| How do Qubits work? | Superposition lets one qubit perform two calculations at once, and if two qubits are linked through a quantum effect known as entanglement. Make a measurement of the result, you only get a single value of the superposition at random. |
| What is Shor's algorithm? Time complexity? | A Quantum algorithm that solves the RSA and Diffie-Hellman problems. Provides an efficient method for integer factorization. O(Ln(N)) |
| What is the security problem with quantum computers? | Decrypt data that has been encrypted in the past. Forge digital signatures in the future. |
| What is Gover's algorithm? Time complexity? | Let f: X ⟶ {0,1} be a function. Goal: find x∈X s.t. f(x)=1 O( |X|^(1/2) ) |
| What is the mitigation to Gover's algorithm? | Increase the key size. |
| How big does a Quantum computer need to be to break Public Key Cryptography? | We need around 10000 logical qubits, which requires billion quantum logic gates, because of the need for error correction. |
| What is the best Quantum computer today? | 54‐qubit Sycamore processor by Google |
| What is the algorithm selected for future key exchange? | CRYSTALS-KYBER |
| What are the algorithms selected for future digital signatures? | CRYSTALS-DILITHIUM FALCON SPHINCS+ |
| What is the shortest vector problem? | Given some basis for the lattice, find the shortest non-zero lattice point lattice. Easy to do if you have (v1, v2) But hard if you do not have the right vector basis. |
| What is the closest point problem? | Given some basis for the lattice and a target point (P) in the space, find the closest lattice point. Easy to do if you have (v1, v2). But hard if you do not have the right vector basis. |
| What is CRYSTALS-KYBER secure based on? | Lattice problems: - Shortest vector problem - Closest point problem |
| Explain how lattice cryptography works. | SEE SLIDES |
| How does McEliece Cryptosystem work? | Its basic concept is to introduce a number of errors in a data stream that cannot be detected and corrected unless you have the right decoding algorithm. |
| Is McEliece Cryptosystem faster or slower than RSA? | Faster |
| What is McEliece Cryptosystem? | It is a public key encryption algorithm developed in 1978 by Robert McEliece. Candidate for "post-quantum cryptography“ as it is not venerable to Shor's algorithm. |
| Explain the step of T in AES subkey generation. | SEE SLIDES |
Created by:
Highcano