HTSEFP
Under construction
1Pseudorandom functions¶
1.1Examples¶
1.1.1Winter 2011, question 1¶
Is it a PRF
i) $f_k$ and $f_{\overline k}$ are always the same
ii) $f_k(0^n) = 0^n$ for all $k$
iii) $f_k(0^n) = k$ for all $k$
iv) $f_k(k) = k$ for all $k$
i) no
ii) no
iii) no, you can figure out $k$ from $f_k(0^n)$ and then just check $f_k(0^n)$...
iv) yes, because you would have to check a superpoly number of inputs $n$ to figure that out
2Extracting square roots¶
2.1Examples¶
2.1.1Winter 2011, question 2¶
Calculate the square roots of 1 mod 143.
1 and -1, obviously. Also, 12 cuz 144, yeah. So -12 too. No others, though I'm not sure how to know that for certain. Then $r_0 = 1$, $r_1 = 12$, and $\gcd(11, 143) = 11$ and $\gcd(13, 143) =13$ (so $r_0 \pm r_1$ gives us the factors of $N$).
3Calculate a modular exponent¶
Compute $a^x \pmod N$ by hand.
3.1Examples¶
3.1.1Winter 2010, question 3¶
Compute $3^{1000} \pmod{100}$ (last two digits)
$\varphi(100) = (2^2-2^1)(5^2-5^1) = 2\cdot 20 = 40$. Euler's theorem tells us that $a^{\varphi(N)} \pmod N = 1$, so $3^{40} = 1 \pmod{100}$. But $3^{1000} = (3^{40})^{25} = 1^{25} = 1 \pmod 100$. So the last two digits are 01.
Source: Exercise 7.5.
3.1.2Winter 2009, question 3¶
Compute $101^{4,800,000,023} \pmod 35$
$\varphi(35) = (7-1)(5-1) = 6\cdot 4 = 24$. Now, $4,800,000,023 = 4,800,000,000 + 24 - 1 = 24 \cdot 200,000,001 - 1$. Thus $101^{4,800,000,023} = 101^{24\cdot 200,000,001 - 1} = 101^{-1} \cdot (101^{24})^{200,000,000} = 101^{-1} \cdot 1 = 101^{-1}$. Now, $101 \pmod 35 = 31$. The inverse of 31 in $\pmod 35$ is 26 (determined through brute force; is there a better way?) so that is the answer.
Source: Exercise 7.6.
4Negligible functions¶
Definition page 56.
4.1Examples¶
4.1.1Winter 2011, question 3¶
A: $n^{-\log n}$. Proof: Show that $n^{\log n} > p(n)$. Etc
B: $2^n$?
C: $f(n) = 1$? Not sure
5Enigma¶
Doubt there will be any questions about it this year
5.1Examples¶
5.1.1Winter 2000, question 2¶
Enigma can't encrypt any letters to the same place. I think the OCR got messed up though, it looks weird.
6Double RSA¶
6.1Examples¶
6.1.1Winter 1999, question 3¶
Why double-encryption is a bad idea
So there are two main ways to break RSA. Either you factor $N$, or bruteforce $d_1$ and $d_2$. This change does NOT make it harder to factor $N$ (in fact it might make it easier since you're supplying more information). Also, instead of bruteforcing $d_1$ or $d_2$, you have to bruteforce $d_1\cdot d_2$ (so find an $e$ that is an inverse). Or, you can compute the inverse of $d_1$, which lets you factor $N$, which lets you compute $d_2$. So it's useless.
7Short and sweet¶
7.1Examples¶
7.1.1Winter 1999, question 5¶
a) Properties of Enigma that made it vulnerable to KPA?
b) Entropy and authentication codes?
c) Weakly/strongly collision free
a) Property as in, techniques? Either gardening (e.g., planting mines), or just guessing (eins catalogue, WETTER, ANX). If mechanical property, then, idk, the fact that cillies could be guessed, or a letter can't be encrypted to itself, a whole bunch of things
b)
c) Weak = second pre-image resistance, strong = collision-resistance
d) Get a function, compute $f(0^n)$, return the first bit
e) EG: based on hardness of DDH; DSS: based on hardness of discrete log
8Computational hardness¶
8.1Examples¶
8.1.1Winter 1999, question 2¶
What things are hard/easy
a) factoring a product of two primes
b) deciding quad res mod a prime
c) quad res mod $pq$
d) sqrts mod a prime
e) sqrts mod $pq$
f) discrete log mod prime
g) discrete log mod $pq$
h) legendre symbols
i) jacobi symbols
a) is hard (and if this is easy, RSA is easy to break), f) is hard (and if this is easy DSS is easy to break), g) is hard (and if this is easy DH is easy to break).
9Three-way Diffie-Hellman¶
9.1Examples¶
9.1.1Winter 1999, question 6¶
How do you do 3-way Diffie-Hellman
Answer from StackExchange:
The standard Diffie-Hellman key exchange algorithm (or family of algorithms) works in an cyclic group with generator $g$, and relies on
$$ {y_A}^{x_B} = (g^{x_A})^{x_B} = (g^{x_B})^{x_A} = {y_B}^{x_A}, $$
where $y_A$ and $y_B$ are publicly transmitted, while $x_A$ and $x_B$ remain private.
With three parties, we still have
$$((g^{x_A})^{x_B})^{x_C} = ((g^{x_A})^{x_C})^{x_B} = ((g^{x_B})^{x_A})^{x_C} = ((g^{x_B})^{x_C})^{x_A} = ((g^{x_C})^{x_B})^{x_A} = ((g^{x_C})^{x_A})^{x_B}. $$
As each party wants to let its own key private, each exponentiation needs to be done at different locations, which means some parties have to send their second-step results to the other parties.
One possible protocol could be the following:
- A, B, C each generate their private keys $x_A$, $x_B$, $x_C$.
- A, B, C each calculate $y_A = g^{x_A}$, $y_B = g^{x_B}$, $y_C = g^{x_C}$.
- A sends $y_A$ to B, B sends $y_B$ to C, C sends $y_C$ to A.
- A calculates $z_{CA} = {y_C}^{x_A}$, B calculates $z_{AB} = {y_A}^{x_B}$, C calculates $z_{BC} = {y_B}^{x_C}$.
- A sends $z_{CA}$ to B, B sends $z_{AB}$ to C, C sends $z_{BC}$ to A.
- A calculates $k_{BCA} = {z_{BC}}^{x_A}$, B calculates $k_{CAB} = {z_{CA}}^{x_B}$, C calculates $k_{ABC} = {z_{AB}}^{x_C}$.
The above equality means that the three parties now know a common secret $k_{ABC} = k_{CAB} = k_{BCA}$.
This obviously generalizes to more than three parties, but it needs one additional group exponentiation per participant more for each additional participant (i.e. in total $n^2$ exponentiations).
All of this works in all groups, so also in the elliptic curve groups (where this is usually written as point multiplication instead of exponentiation).
In practice it might be easier to exchange secret keys with some "hub" node, which then creates a common secret and sends it to each participant, like Dennis proposed in his answer.
10MACs and signatures¶
10.1Examples¶
10.1.1Winter 2011, question 4¶
1) Why is the term signature only used for public keys
2) Why is textbook RSA shitty
3) Why do signatures need assumptions
1) Because with MACs, you can't really tell who signed it because of the shared key, plus it's not publicly verifiable
2) No-message and arbitrary-message attacks
3) Because public keys, thus one-way functions