diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
commit | 162df3190c4e179ef968b0a467ddd4951faba336 (patch) | |
tree | 3c9628cf1abf259e1b897ac14b006e2b448cff27 /ss2017/cryptography/Notes12.txt | |
parent | 92ed41381f40c97b52b0e96f0eaeaa9025091411 (diff) | |
download | uni-162df3190c4e179ef968b0a467ddd4951faba336.tar uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.gz uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.bz2 uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.xz uni-162df3190c4e179ef968b0a467ddd4951faba336.zip |
Notes on cryptography
Diffstat (limited to 'ss2017/cryptography/Notes12.txt')
-rw-r--r-- | ss2017/cryptography/Notes12.txt | 274 |
1 files changed, 274 insertions, 0 deletions
diff --git a/ss2017/cryptography/Notes12.txt b/ss2017/cryptography/Notes12.txt new file mode 100644 index 0000000..a1299d7 --- /dev/null +++ b/ss2017/cryptography/Notes12.txt | |||
@@ -0,0 +1,274 @@ | |||
1 | 12 Number theory and hardness assumptions | ||
2 | ----------------------------------------- | ||
3 | |||
4 | The next few sections are about *public-key cryptography* (different | ||
5 | keys for encryption and decryption, one public, the other | ||
6 | private). This area makes heavy use of number theory, in particular | ||
7 | arithmetic. In this section we review the necessary mathematics and | ||
8 | formulate hardness assumptions on which the security of public key | ||
9 | cryptography is based. | ||
10 | |||
11 | We assume standard knowledge about | ||
12 | |||
13 | - arithmetic: division with remainder, gcd, extended Euclidean | ||
14 | algorithm, i.e. for all integers u,v, there exists integers s, t such | ||
15 | that gcd(u,v)=su+tv, Chinese remainder theorem, modular arithmetic, in | ||
16 | particular inverses modulo. | ||
17 | |||
18 | - groups: additive and multiplicative notation; exponentiation; the | ||
19 | additive group Z_N (addition modulo N); the multiplicative group | ||
20 | (Z_N)^* of order phi(N) (Euler's phi function); the consequence | ||
21 | x^(phi(N)) = 1 (mod N) and the special case x^{p-1}=1 (mod p); the | ||
22 | group isomorphisms derived from the Chinese remainder theorem (Z_pq | ||
23 | =~= Z_p x Z_q, Z_pq^* =~= Z_p^* x Z_q^*), primitive elements in | ||
24 | Z_p^* (cyclicity of Z_p^*). | ||
25 | |||
26 | The required knowledge is part of "Logik und Diskrete Strukturen" and | ||
27 | can also be looked up in KL. | ||
28 | |||
29 | Next, we discuss the computational complexity of various arithmetic | ||
30 | operations. We always measure runtimes in terms of the *sizes* | ||
31 | (lengths in binary representation) of the numbers in question. Notice | ||
32 | that the size of a number n is O(log(n)). The basic arithmetic | ||
33 | operations +,-,*,/ can be performed in polynomial time (in terms of | ||
34 | the sizes) with the standard algorithms taught at school. The same is | ||
35 | true for gcd-computations using Euclid's algorithm. Furthermore, | ||
36 | computing modular powers, i.e. a^b mod N can also be done in | ||
37 | polynomial time using repeated squaring based on the binary expansion | ||
38 | of N. Note though that a^b cannot be computed in polynomial time | ||
39 | simply because the result is too long. | ||
40 | |||
41 | Testing whether a given number n is prime can also be done in | ||
42 | polynomial time; the most efficient algorithms for this use | ||
43 | probabilistic polynomial time computation, however. This means that | ||
44 | one has randomised algorithms which given a number n answer either | ||
45 | "composite" in which case n is definitely composite or "prime" in | ||
46 | which case n is prime except for a negligible error probability. The | ||
47 | simplest of these tests is the Miller-Rabin test (KL 7.2.2). | ||
48 | |||
49 | Using such a primality test it is also possible to generate a random | ||
50 | prime number of a given size s. To that end one chooses random n of | ||
51 | size s and then tests n,n+1,n+2,n+3,... for primality until a prime | ||
52 | number has been found. Theorems about the distribution of prime | ||
53 | numbers assert that this search is successful after a small (in any | ||
54 | case expected polynomial) time. | ||
55 | |||
56 | |||
57 | Factoring | ||
58 | - - - - - | ||
59 | |||
60 | The factoring problem asks the following question. Given a natural | ||
61 | number N find a non-trivial factor of N unless N is prime (as usual | ||
62 | the trivial factors are 1 and N). | ||
63 | |||
64 | If N is even or has some other small divisor then this question is | ||
65 | easily solved by trial division (the factoring method taught at | ||
66 | school). If, however, N has only large factors, e.g. is the product of | ||
67 | two primes of roughly equal size then factoring is believed to be a | ||
68 | very hard problem and at any rate no efficient algorithm is | ||
69 | known. Notice that trial division is linear in sqrt(N) hence | ||
70 | exponential in the size of N. (sqrt(N)=2^{1/2*log(N)}). There do exist | ||
71 | better algorithms for factoring, but with today's technology finding | ||
72 | out the factors of a product of two ~512bit primes must be considered | ||
73 | infeasible with a broad security margin. | ||
74 | |||
75 | |||
76 | RSA Cryptosystem | ||
77 | - - - - - - - - - | ||
78 | It is believed to be hard to reconstruct x from x^e knowing merely N | ||
79 | and e so this procedure is used as the basis of a public key | ||
80 | cryptosystem: RSA. Intuitively, Enc_e(x)=x^e mod N and Dec_d(y)=y^d | ||
81 | mod N. The encryption key e can be publicized whereas the decryption | ||
82 | key d must be kept private. | ||
83 | |||
84 | Consider the situation where N=pq for primes p,q. The ring Z_N of | ||
85 | integers mod N contains phi(N)=(p-1)(q-1) invertible elements. Recall | ||
86 | that x:Z_N is invertible if gcd(x,N)=1. The elements with a gcd > 1 | ||
87 | are the multiples of p and of q of which there are (q-1) + (p-1) + 1 | ||
88 | with the last summand corresponding to 0=pq. Thus, the number of | ||
89 | invertible elements is pq-q-p+1 = (p-1)(q-1). Equivalently, with the | ||
90 | Chinese Remainder Theorem we have Z_N =~= Z_p x Z_q and the invertible | ||
91 | elements correspond to those pairs (x,y):Z_p x Z_q where x=/=0 and | ||
92 | y=/=0. | ||
93 | |||
94 | The (multiplicative) group Z^*_N of invertible elements (mod N) thus | ||
95 | has order /* number of elements */ phi(N)=(p-1)(q-1). For each element | ||
96 | x:Z^*_N it holds that x^phi(N) = 1 (mod N) (general result about | ||
97 | groups). | ||
98 | |||
99 | Now suppose that we have e such that gcd(e,phi(N))=1 and ed=1 | ||
100 | (mod phi(N)). Then we can solve the RSA problem, | ||
101 | i.e. determine x such that x^e = y mod N for given y, N, e. | ||
102 | More precisely, if x:Z^*_N we can recover x from y:=x^e as y^d | ||
103 | (all computations done mod N). Indeed, (x^e)^d = x^{ed} = | ||
104 | x^{t*phi(N)+1} = x (for any t). | ||
105 | |||
106 | |||
107 | Security of RSA relative to factoring | ||
108 | - - - - - - - - - - - - - - - - - - - | ||
109 | |||
110 | If given e we are able to find d such that x^{ed}=x holds for all | ||
111 | invertible (mod N) x then we can find the factors of N as follows: | ||
112 | Namely, in this case, we have a value a (=ed-1) such that x^a=1 (mod | ||
113 | N) holds for all x:Z^*_N. Such value must necessarily be even as can | ||
114 | be seen by taking x=-1. Now we can successively divide a by two until | ||
115 | we have found a value b such that x^{2b} = 1 (mod N) holds for all x | ||
116 | but x^b =/= 1 for some x. The crucial observation is that once x^b =/= | ||
117 | 1 for some x then x^b =/= 1 for at least 50% of all x so we can find | ||
118 | such a witness value x by repeated guesses. The reason for the 50% | ||
119 | bound is that {x | x^b=1} is a proper subgroup of Z^*_N and its order | ||
120 | must therefore be a proper divisor of |Z^*_N|=phi(N). | ||
121 | |||
122 | So, summing up, we are in possession of a value b such that x^{2b}=1 | ||
123 | for all x, but x^b=1 not for all x. Let us consider u := x^b mod p and | ||
124 | v := x^b mod q. Since u^2=v^2=1 we have u,v:{-1,1}. Moreover, by the | ||
125 | Chinese Remainder Theorem, we have Z_N^* =~= Z_p^* x Z_q^* so that if | ||
126 | x is chosen uniformly at random then u and v are also uniformly at | ||
127 | random and independent. As before, if one of them *may* be =/=1 then | ||
128 | this happens for at least 50% of them. As a result, under the | ||
129 | assumptions, the event u*v=-1 has a a likelihood of at least 50% and | ||
130 | in this event gcd(x^b-1,N) yields a nontrivial divisor of N. | ||
131 | |||
132 | |||
133 | Unfortunately, there is no known reduction from RSA to factoring in | ||
134 | the sense that we would be able to prove that RSA is semantically | ||
135 | secure on condition that factoring is hard. Namely, notwithstanding | ||
136 | the above, it might be possible to break RSA without actually | ||
137 | producing an exponent d such that x^ed=1 mod N. To date, it is not | ||
138 | known whether RSA is sec ure relative to factoring, let alone in | ||
139 | itself. | ||
140 | |||
141 | |||
142 | RSA hardness assumption | ||
143 | - - - - - - - - - - - - | ||
144 | |||
145 | The computational hardness of RSA is thus not proven and not reducible | ||
146 | to factoring but at least to some extent plausible. It is thus | ||
147 | justified to formulate the following RSA hardness assumption. | ||
148 | |||
149 | There exists a randomised polynomial time algorithm GenRSA() which | ||
150 | given security parameter n produces (N,e,d) such that N is the product | ||
151 | of two primes N=pq and d = e^{-1} mod phi(N) and such that the following | ||
152 | experiment has negligible success property for all probabilistic polynomial time adversaries A: | ||
153 | |||
154 | RSA-inv_A(n): | ||
155 | |||
156 | 1. Run GenRSA(n) to obtain (N,e,d) | ||
157 | 2. Choose x<-Z^*_N | ||
158 | 3. A is given N,e, and x^e mod N and outputs x' | ||
159 | 4. The output of the experiment is 1 if x=x' and 0 otherwise. | ||
160 | |||
161 | |||
162 | It is believed that the RSA assumption holds with GenRSA(n) selecting | ||
163 | two random primes of length n, choosing e at random and outputting | ||
164 | (pq,e,e^{-1} mod phi(N)). | ||
165 | |||
166 | |||
167 | Groups for cryptography | ||
168 | - - - - - - - - - - - - | ||
169 | |||
170 | A *group generating* algorithm G(n) is a probabilistic polynomial time | ||
171 | algorithm which given security parameter n produces a description of a | ||
172 | group G_n whose order is polynomial in n. The description of the group | ||
173 | comprises generators, a well-formedness test, testing whether a given | ||
174 | bitstring encodes a group element or not and algorithms implementing | ||
175 | multiplication and inverses on these representations. | ||
176 | |||
177 | For example, G(n) might determine a random prime p of length n and | ||
178 | then return an algorithmic description of the group Z_p^*. As for a | ||
179 | generator, it could produce a primitive element. | ||
180 | |||
181 | For some applications, groups of prime order are preferred. One | ||
182 | example of those is the following: If q is a prime such that p=2q+1 is | ||
183 | also prime (p is then called a "strong prime") then the subgroup of | ||
184 | Z^*_p consisting of the elements of the form y^2 for y:Z_^*p (the | ||
185 | quadratic residues mod p) form a subgroup of Z^*_p of order q which by | ||
186 | assumption is prime. | ||
187 | |||
188 | Further examples are furnished by groups of points on an elliptic | ||
189 | curve. The elements of such a group are pairs (x,y) of elements of | ||
190 | a finite field GF(q) (q prime) such that | ||
191 | |||
192 | y^2 = x^3 + Ax + B | ||
193 | |||
194 | holds for fixed parameters A, B which thus determine the elliptic | ||
195 | groups. In addition to these pairs (x,y) the group contains a special | ||
196 | element O. | ||
197 | |||
198 | For example, if the field is GF(7) = Z_7 and A=B=3 then the group (the | ||
199 | elliptic curve) has elements (1,0), (3,2), (3,5), (4,3), (4,4), | ||
200 | O. Indeed, whenever x^3+3x+3 is (zero or) a quadratic residue mod 7 we find (one | ||
201 | or) two points and otherwise not. | ||
202 | |||
203 | The group operation, i.e. how elements of the group are added (or | ||
204 | multiplied, depending on notation), is omitted for now. | ||
205 | We come back to it later. | ||
206 | |||
207 | |||
208 | |||
209 | |||
210 | |||
211 | Discrete logarithm and Diffie Hellman | ||
212 | - - - - - - - - - - - - - - - - - - - | ||
213 | |||
214 | Given a cyclic group G with generator g the discrete logarithm problem | ||
215 | is the following: given h:G determine e such that h=g^e. Formally, | ||
216 | suppose that we are given a group generating algorithm G(n) outputting | ||
217 | for each n a cyclic group G_n and a generator g. | ||
218 | |||
219 | For adversary A the experiment DLog_{A,G}(n) then is the following: | ||
220 | |||
221 | 1. Run G(n) to obtain (G,q,g) where G is a cyclic group of order q | ||
222 | with generator g. | ||
223 | |||
224 | 2. Choose h<-G /* e.g. by putting h=g^d for d<-Z_q */ | ||
225 | 3. A is given G,q,g,h and outputs e:Z_q | ||
226 | 4. The output of the experiment is 1 if g^e = h | ||
227 | |||
228 | By definition, the discrete logarithm problem is hard for G() if for | ||
229 | all adversaries A one has Pr(DLog_{A,G}(n)=1) = negl(n). | ||
230 | |||
231 | It is generally believed that discrete logarithm is hard for the | ||
232 | aforementioned example groups. | ||
233 | |||
234 | Related problems are computational Diffie-Hellman (CDH) and decisional | ||
235 | Diffie-Hellman (DDH). | ||
236 | |||
237 | Computational Diffie-Hellman: given a cyclic group G of order q and | ||
238 | generator g as above and h=g^x, h'=g^y determine (without knowing x,y !) | ||
239 | the value g^{xy}. | ||
240 | |||
241 | Decisional Diffie-Hellman: given a cyclic group G of order q and | ||
242 | generator g as above and h=g^x, h'=g^y and h''=g^z determine (without | ||
243 | knowing x,y,z !) whether or not g^{xy}=g^z. | ||
244 | |||
245 | Clearly, a solution to the discrete logarithm problem implies a | ||
246 | solution to Diffie-Hellman, but the converse is not known. As a | ||
247 | result, hardness of discrete log is a weaker assumption than hardness | ||
248 | of DDH (and CDH) | ||
249 | |||
250 | Diffie-Hellman is important for the eponymous Diffie-Hellman | ||
251 | key-exchange protocol: In order to share a common secret key Alice may | ||
252 | choose random x:Z_q and send u=g^x to Bob. Bob does the same and thus | ||
253 | sends v=g^y to Alice. Now, Alice and Bob can both compute the shared | ||
254 | key g^{xy} as u^x (Alice) and v^y (Bob). We will show later that | ||
255 | assuming DDH is hard this scheme is secure in a precise sense. | ||
256 | |||
257 | Formal definition of hardness of DDH: | ||
258 | |||
259 | Given a group-generating algorithm G() producing cyclic groups as | ||
260 | above, we say that the decisional Diffie Hellman problem is hard for | ||
261 | G() if for all probabilistic polynomial-time adversaries A and all n we have | ||
262 | |||
263 | |Pr(A(G,q,g,g^x,g^y,g^z)=1) - Pr(A(G,q,g,g^x,g^y,g^{xy}))| = negl(n) | ||
264 | |||
265 | where G(n)=(G,q,g) and x,y,z <- Z_q. | ||
266 | |||
267 | Thus, DDH is hard, if g^{xy} looks like a random element of G even if | ||
268 | g^x and g^y are known. | ||
269 | |||
270 | We close this chapter by remarking that under the assumption that RSA | ||
271 | is hard thre exist pseudo random generators, pseudorandom functions, | ||
272 | and permutations (see KL6 and 7.4.1). Under the assumption that | ||
273 | discrete logarithm is hard for some group then there exist collision | ||
274 | resistant hash functions. (KL7.4.2). | ||