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/Notes14.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/Notes14.txt')
-rw-r--r-- | ss2017/cryptography/Notes14.txt | 208 |
1 files changed, 208 insertions, 0 deletions
diff --git a/ss2017/cryptography/Notes14.txt b/ss2017/cryptography/Notes14.txt new file mode 100644 index 0000000..e6075ff --- /dev/null +++ b/ss2017/cryptography/Notes14.txt | |||
@@ -0,0 +1,208 @@ | |||
1 | 14 El Gamal and elliptic curve cryptography | ||
2 | ------------------------------------------- | ||
3 | |||
4 | The El Gamal cryptosystem is based on the DDH assumption and is | ||
5 | provably secure under the assumption of the latter. Just like DH-key | ||
6 | exchange it is parametrised by a group (generating algorithm) G(n) and | ||
7 | works as follows: | ||
8 | |||
9 | Gen(n) : | ||
10 | (G,q,g) = G(n) | ||
11 | x <- Z_q | ||
12 | h <- g^x | ||
13 | pk = (G,q,g,h) | ||
14 | sk = (G,q,g,x) | ||
15 | output (pk,sk) | ||
16 | |||
17 | Enc_(G,q,g,h)(m) : | ||
18 | check that m:G | ||
19 | y <- Z_q | ||
20 | c = (g^y,h^y*m) | ||
21 | output c | ||
22 | |||
23 | Dec_(G,q,g,g,x)(c1,c2) : | ||
24 | m = c2 / c1^x | ||
25 | output m | ||
26 | |||
27 | |||
28 | Let us first see that this scheme is correct: If c1=g^y and c2=h^y*m | ||
29 | where h=g^x then c2 / c1^x= g^(xy) * m / g^(xy) = m | ||
30 | |||
31 | We also notice that messages and ciphertexts are actually elements of | ||
32 | the group G which must therefore by somehow encoded as binary | ||
33 | strings. This can be done in various ways for the various groups, see | ||
34 | KL for details. | ||
35 | |||
36 | Theorem: If the DDH assumptions holds for a group (generating | ||
37 | algorithm) G() then the El Gamal cryptosystem basd on G() is | ||
38 | semantically secure. | ||
39 | |||
40 | Proof: Let A be an adversary against the El Gamal system and let its | ||
41 | success probability be 1/2+eps(n). We must show that eps(n) is | ||
42 | negligible. We construct from A an adversary A' as in the DDH | ||
43 | assumption. | ||
44 | |||
45 | Suppose that A' receives g^x, g^y, u where u is either g^(xy) or g^z | ||
46 | for random z and A' is to decide which of the two. | ||
47 | |||
48 | We forward (G,q,g,g^x) as "public key" to A and wait for it to output | ||
49 | m0,m1:G. We choose a random bit b and build c = (g^y,u*m_b) and let b' | ||
50 | be the bit that A returns. | ||
51 | |||
52 | If u=g^(xy) then A is played with according to the rules of the El | ||
53 | Gamal cryptosystem and therefore b'=b with probability 1/2+eps(n). If | ||
54 | u=g^z for random z then u*m0 is also uniformly random (since x|->x*m0 | ||
55 | is a bijection G->G) and therefore the probability that b'=b is | ||
56 | exactly 1/2. The difference between the two probabilities is precisely | ||
57 | eps(n) which under the DDH assumption will be negligible. QED | ||
58 | |||
59 | |||
60 | Elliptic curve cryptography | ||
61 | - - - - - - - - - - - - - - | ||
62 | |||
63 | As already mentioned, elliptic curves furnish a large reservoir of | ||
64 | cyclic groups for which taking discrete logarithms, CDH, and DDH are | ||
65 | believed to be hard. With existing algorithms, solving these problems | ||
66 | on elliptic curve groups is consistently harder than doing so for | ||
67 | groups of invertible elements mod p or in a finite field. | ||
68 | |||
69 | Recall that an elliptic curve over some field F of characteristic =/= | ||
70 | 2,3 is defined by two constants a, b and comprises the points (x,y) | ||
71 | that solve the equation | ||
72 | |||
73 | y^2 = x^3 + ax + b | ||
74 | |||
75 | Here, one assumes that the *discriminant* 4a^3+27b^2 =/= 0 for | ||
76 | otherwise the curve might be *singular*, i.e. contain anomalies like | ||
77 | isolated points, sharp bends ("cusps") or similar. When viewed over | ||
78 | the reals such a curve looks roughly as follows: | ||
79 | |||
80 | | | | ||
81 | | / | ||
82 | - | - / | ||
83 | / | \ _ - | ||
84 | | | | ||
85 | --------------------------------------------------------------------- | ||
86 | | | - _ | ||
87 | \ | / \ | ||
88 | -| - \ | ||
89 | | | | ||
90 | |||
91 | Depending on the parameters the knob to the left may also become | ||
92 | detached and form a closed loop sitting to the right. In either case | ||
93 | whenever a line intersects the curve in two points it meets it again | ||
94 | in a third point except when the line is parallel to the y-axis in | ||
95 | which case we say that the third point of intersection is at infinity, | ||
96 | here denoted O. | ||
97 | |||
98 | This property also holds for curves over other fields, in particular | ||
99 | finite ones which are of interest for cryptography. There is an | ||
100 | explicit formula for obtaining the third point of intersection. To | ||
101 | wit, if (x1,y1) and (x2,y2) lie on the curve then the line through | ||
102 | them is y=m(x-x1)+y1 where m=(y2-y1)/(x2-x1). Plugging this into the | ||
103 | curve yields | ||
104 | |||
105 | (m(x-x1)+y1)^2 = x^3+ax+b | ||
106 | |||
107 | The three solutions of this equation are x=x1, x=x2, x=m^2-x1-x2, so | ||
108 | the last one is the desired third point of intersection. | ||
109 | |||
110 | Now, it is a remarkable fact that the points on the curve together | ||
111 | with O form an abelian group, traditionally written additively, where | ||
112 | the sum of points P and Q is obtained by first taking the third curve | ||
113 | point on the line through P and Q, call it R=(x_R,y_R), and then | ||
114 | reflecting R on the x-axis, i.e. P+Q=(x_R,-y_R). | ||
115 | |||
116 | This, however, only applies when P=/=Q and when P and Q do not have | ||
117 | the same x-coordinate. In the latter case, one has P+Q=O, the special | ||
118 | point at infinity. In the former case, i.e. when P=Q, one must take | ||
119 | the tangent through P and intersect it with the curve. | ||
120 | |||
121 | One can show using implicit differentiation that the coordinates of | ||
122 | that point are given by | ||
123 | |||
124 | (((3x_1^2+a)/2y_1)^2 - 2x1, -y1+((3x_1^2+a)/2y_1)^2(x1-x2)) | ||
125 | |||
126 | and this formula, just as the one above for the general case, also | ||
127 | makes sense for finite fields where there are no "tangents". Yet | ||
128 | another special case is when P or Q is O. One simply puts O+P=P+O=P. | ||
129 | |||
130 | Curves over fields of characteristic 2 or 3 are also possible, but | ||
131 | then both the defining equations and the formulas for addition of | ||
132 | points become slightly different (notice e.g. that in the formula | ||
133 | above we divide by 2). We refer to the literature, but stress that it | ||
134 | is very important not to make mistakes with the implementation of the | ||
135 | addition formulas and that doing so has lead to security flaws. | ||
136 | |||
137 | We have already seen that addition of points is well-defined and | ||
138 | commutative. It is also clear that the inverse of a point (x,y) is | ||
139 | given by (x,-y), i.e. reflection on the x-axis. Associativity of | ||
140 | addition follows from nontrivial results, e.g. the Weierstrass | ||
141 | p-function, but can in principle also be validated "by hand" on the | ||
142 | basis of the above formulas. | ||
143 | |||
144 | For integer n and point P on a curve we use the notation n.P for | ||
145 | P+P+...+P with summands. This is the same as the exponent notation in | ||
146 | multiplicatively written groups. Therefore, the "repeated squaring" | ||
147 | method can be used here as well: | ||
148 | |||
149 | 100.P = 4.P+32.P+64.P = 2.(2.(P + 2.(2.(2.(P+2.P))))) | ||
150 | |||
151 | Now, the plan is to use the groups coming from elliptic curves for | ||
152 | cryptosystems like Diffie-Hellman key exchange or El Gamal. For this | ||
153 | to work, a couple more considerations are in order: we need to encode | ||
154 | plaintexts as points on the group and we need to ascertain that the | ||
155 | group is cyclic or else move to a cyclic subgroup. | ||
156 | |||
157 | In order to find a cyclic group one can rely on one of the publicly | ||
158 | available and recommended curves. Many of them have a prime number of | ||
159 | points and hence are cyclic with any element other than O being a | ||
160 | generator. Alternatively, one can try out random coefficients a and b | ||
161 | until one finds a curve with a prime number of points. To do this, one | ||
162 | needs to invoke Schoof's algorithm which allows one to determine the | ||
163 | number of points on a given elliptic curve. | ||
164 | |||
165 | If one would like to use a curve with a nonprime number, say N, of | ||
166 | points, then one must factor N and it is then important that N has a | ||
167 | large prime factor p, i.e. p>sqrt(N). In this case, by the | ||
168 | representation theorem for finite(ly generated) abelian groups there | ||
169 | is a subgroup of order p and any of its nonzero elements are | ||
170 | generators. Moreover, the remaining subgroups have smaller order. To | ||
171 | check whether a point P is in the subgroup of order p it suffices to | ||
172 | check that p.P = O. To obtain a point in that subgroup one can pick a | ||
173 | random point P and if Q := N/p.P =/= O then p.Q is in the subgroup, | ||
174 | hence Q can serve as a generator. | ||
175 | |||
176 | For the most, however, one uses one of the already publicised elliptic | ||
177 | curves such as those recommended by the NIST "for government use". | ||
178 | See http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf | ||
179 | There is no need to choose a "fresh" curve for every application and | ||
180 | on the other hand, some curves are "weak" and should be avoided. | ||
181 | |||
182 | In order to encode plaintexts as points we can proceed as | ||
183 | follows. First, we note that it suffices to store the x-coordinate of | ||
184 | a point and a single bit telling whether the y-coordinate is above or | ||
185 | below the x-axis, i.e., which of the two square roots of x^3 +ax+b are | ||
186 | meant. This is known as point compression. As for the x-coordinates | ||
187 | one fixes a bijection alpha between bitstrings of length l=log(q) and | ||
188 | field elements. Now one puts t=l-k where k is chosen sufficiently | ||
189 | large. Then, to encode message x of length t one searches for a string | ||
190 | z of length k so that alpha(x||z) has a square root y over GF(q), | ||
191 | i.e., is a quadratic residue. At that point, (alpha(x||z),y) can be | ||
192 | taken as the desired encoding of x as a curve point. For random | ||
193 | padding z the chance for alpha(x||z) to be a quadratic residue is | ||
194 | about 1/2, so after a short number of iterations one is almost sure to | ||
195 | find an appropriate encoding. We also remark that there exist | ||
196 | efficient algorithms for testing whether a given field element is a | ||
197 | quadratic residue and if so to compute its square root. | ||
198 | |||
199 | With all this machinery in place, the Diffie-Hellman and El Gamal | ||
200 | cryptosystems can be used with elliptic curve groups without any | ||
201 | change, bearing in mind, of course, that instead of exponentiation | ||
202 | g^x, we now use multiplication x.P and instead of multiplication we | ||
203 | use addition, so that, e.g. the encryption of message m encoded as a | ||
204 | point M becomes (y.P,y.Q+M) where P is the generator and Q=x.P | ||
205 | |||
206 | We close by remarking that since the early 2000 elliptic curve | ||
207 | cryptography (ECC) has become more and more common. Also the bitcoin | ||
208 | cryptocurrency uses it. | ||