From 162df3190c4e179ef968b0a467ddd4951faba336 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Tue, 24 Oct 2017 15:33:07 +0200 Subject: Notes on cryptography --- ss2017/cryptography/Notes12.txt | 274 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 274 insertions(+) create mode 100644 ss2017/cryptography/Notes12.txt (limited to 'ss2017/cryptography/Notes12.txt') 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 @@ +12 Number theory and hardness assumptions +----------------------------------------- + +The next few sections are about *public-key cryptography* (different +keys for encryption and decryption, one public, the other +private). This area makes heavy use of number theory, in particular +arithmetic. In this section we review the necessary mathematics and +formulate hardness assumptions on which the security of public key +cryptography is based. + +We assume standard knowledge about + +- arithmetic: division with remainder, gcd, extended Euclidean +algorithm, i.e. for all integers u,v, there exists integers s, t such +that gcd(u,v)=su+tv, Chinese remainder theorem, modular arithmetic, in +particular inverses modulo. + +- groups: additive and multiplicative notation; exponentiation; the + additive group Z_N (addition modulo N); the multiplicative group + (Z_N)^* of order phi(N) (Euler's phi function); the consequence + x^(phi(N)) = 1 (mod N) and the special case x^{p-1}=1 (mod p); the + group isomorphisms derived from the Chinese remainder theorem (Z_pq + =~= Z_p x Z_q, Z_pq^* =~= Z_p^* x Z_q^*), primitive elements in + Z_p^* (cyclicity of Z_p^*). + +The required knowledge is part of "Logik und Diskrete Strukturen" and +can also be looked up in KL. + +Next, we discuss the computational complexity of various arithmetic +operations. We always measure runtimes in terms of the *sizes* +(lengths in binary representation) of the numbers in question. Notice +that the size of a number n is O(log(n)). The basic arithmetic +operations +,-,*,/ can be performed in polynomial time (in terms of +the sizes) with the standard algorithms taught at school. The same is +true for gcd-computations using Euclid's algorithm. Furthermore, +computing modular powers, i.e. a^b mod N can also be done in +polynomial time using repeated squaring based on the binary expansion +of N. Note though that a^b cannot be computed in polynomial time +simply because the result is too long. + +Testing whether a given number n is prime can also be done in +polynomial time; the most efficient algorithms for this use +probabilistic polynomial time computation, however. This means that +one has randomised algorithms which given a number n answer either +"composite" in which case n is definitely composite or "prime" in +which case n is prime except for a negligible error probability. The +simplest of these tests is the Miller-Rabin test (KL 7.2.2). + +Using such a primality test it is also possible to generate a random +prime number of a given size s. To that end one chooses random n of +size s and then tests n,n+1,n+2,n+3,... for primality until a prime +number has been found. Theorems about the distribution of prime +numbers assert that this search is successful after a small (in any +case expected polynomial) time. + + +Factoring +- - - - - + +The factoring problem asks the following question. Given a natural +number N find a non-trivial factor of N unless N is prime (as usual +the trivial factors are 1 and N). + +If N is even or has some other small divisor then this question is +easily solved by trial division (the factoring method taught at +school). If, however, N has only large factors, e.g. is the product of +two primes of roughly equal size then factoring is believed to be a +very hard problem and at any rate no efficient algorithm is +known. Notice that trial division is linear in sqrt(N) hence +exponential in the size of N. (sqrt(N)=2^{1/2*log(N)}). There do exist +better algorithms for factoring, but with today's technology finding +out the factors of a product of two ~512bit primes must be considered +infeasible with a broad security margin. + + +RSA Cryptosystem +- - - - - - - - - +It is believed to be hard to reconstruct x from x^e knowing merely N +and e so this procedure is used as the basis of a public key +cryptosystem: RSA. Intuitively, Enc_e(x)=x^e mod N and Dec_d(y)=y^d +mod N. The encryption key e can be publicized whereas the decryption +key d must be kept private. + +Consider the situation where N=pq for primes p,q. The ring Z_N of +integers mod N contains phi(N)=(p-1)(q-1) invertible elements. Recall +that x:Z_N is invertible if gcd(x,N)=1. The elements with a gcd > 1 +are the multiples of p and of q of which there are (q-1) + (p-1) + 1 +with the last summand corresponding to 0=pq. Thus, the number of +invertible elements is pq-q-p+1 = (p-1)(q-1). Equivalently, with the +Chinese Remainder Theorem we have Z_N =~= Z_p x Z_q and the invertible +elements correspond to those pairs (x,y):Z_p x Z_q where x=/=0 and +y=/=0. + +The (multiplicative) group Z^*_N of invertible elements (mod N) thus +has order /* number of elements */ phi(N)=(p-1)(q-1). For each element +x:Z^*_N it holds that x^phi(N) = 1 (mod N) (general result about +groups). + +Now suppose that we have e such that gcd(e,phi(N))=1 and ed=1 +(mod phi(N)). Then we can solve the RSA problem, + i.e. determine x such that x^e = y mod N for given y, N, e. +More precisely, if x:Z^*_N we can recover x from y:=x^e as y^d +(all computations done mod N). Indeed, (x^e)^d = x^{ed} = +x^{t*phi(N)+1} = x (for any t). + + +Security of RSA relative to factoring +- - - - - - - - - - - - - - - - - - - + +If given e we are able to find d such that x^{ed}=x holds for all +invertible (mod N) x then we can find the factors of N as follows: +Namely, in this case, we have a value a (=ed-1) such that x^a=1 (mod +N) holds for all x:Z^*_N. Such value must necessarily be even as can +be seen by taking x=-1. Now we can successively divide a by two until +we have found a value b such that x^{2b} = 1 (mod N) holds for all x +but x^b =/= 1 for some x. The crucial observation is that once x^b =/= +1 for some x then x^b =/= 1 for at least 50% of all x so we can find +such a witness value x by repeated guesses. The reason for the 50% +bound is that {x | x^b=1} is a proper subgroup of Z^*_N and its order +must therefore be a proper divisor of |Z^*_N|=phi(N). + +So, summing up, we are in possession of a value b such that x^{2b}=1 +for all x, but x^b=1 not for all x. Let us consider u := x^b mod p and +v := x^b mod q. Since u^2=v^2=1 we have u,v:{-1,1}. Moreover, by the +Chinese Remainder Theorem, we have Z_N^* =~= Z_p^* x Z_q^* so that if +x is chosen uniformly at random then u and v are also uniformly at +random and independent. As before, if one of them *may* be =/=1 then +this happens for at least 50% of them. As a result, under the +assumptions, the event u*v=-1 has a a likelihood of at least 50% and +in this event gcd(x^b-1,N) yields a nontrivial divisor of N. + + +Unfortunately, there is no known reduction from RSA to factoring in +the sense that we would be able to prove that RSA is semantically +secure on condition that factoring is hard. Namely, notwithstanding +the above, it might be possible to break RSA without actually +producing an exponent d such that x^ed=1 mod N. To date, it is not +known whether RSA is sec ure relative to factoring, let alone in +itself. + + +RSA hardness assumption +- - - - - - - - - - - - + +The computational hardness of RSA is thus not proven and not reducible +to factoring but at least to some extent plausible. It is thus +justified to formulate the following RSA hardness assumption. + +There exists a randomised polynomial time algorithm GenRSA() which +given security parameter n produces (N,e,d) such that N is the product +of two primes N=pq and d = e^{-1} mod phi(N) and such that the following +experiment has negligible success property for all probabilistic polynomial time adversaries A: + +RSA-inv_A(n): + +1. Run GenRSA(n) to obtain (N,e,d) +2. Choose x<-Z^*_N +3. A is given N,e, and x^e mod N and outputs x' +4. The output of the experiment is 1 if x=x' and 0 otherwise. + + +It is believed that the RSA assumption holds with GenRSA(n) selecting +two random primes of length n, choosing e at random and outputting +(pq,e,e^{-1} mod phi(N)). + + +Groups for cryptography +- - - - - - - - - - - - + +A *group generating* algorithm G(n) is a probabilistic polynomial time +algorithm which given security parameter n produces a description of a +group G_n whose order is polynomial in n. The description of the group +comprises generators, a well-formedness test, testing whether a given +bitstring encodes a group element or not and algorithms implementing +multiplication and inverses on these representations. + +For example, G(n) might determine a random prime p of length n and +then return an algorithmic description of the group Z_p^*. As for a +generator, it could produce a primitive element. + +For some applications, groups of prime order are preferred. One +example of those is the following: If q is a prime such that p=2q+1 is +also prime (p is then called a "strong prime") then the subgroup of +Z^*_p consisting of the elements of the form y^2 for y:Z_^*p (the +quadratic residues mod p) form a subgroup of Z^*_p of order q which by +assumption is prime. + +Further examples are furnished by groups of points on an elliptic +curve. The elements of such a group are pairs (x,y) of elements of +a finite field GF(q) (q prime) such that + + y^2 = x^3 + Ax + B + +holds for fixed parameters A, B which thus determine the elliptic +groups. In addition to these pairs (x,y) the group contains a special +element O. + +For example, if the field is GF(7) = Z_7 and A=B=3 then the group (the +elliptic curve) has elements (1,0), (3,2), (3,5), (4,3), (4,4), +O. Indeed, whenever x^3+3x+3 is (zero or) a quadratic residue mod 7 we find (one +or) two points and otherwise not. + +The group operation, i.e. how elements of the group are added (or +multiplied, depending on notation), is omitted for now. +We come back to it later. + + + + + +Discrete logarithm and Diffie Hellman +- - - - - - - - - - - - - - - - - - - + +Given a cyclic group G with generator g the discrete logarithm problem +is the following: given h:G determine e such that h=g^e. Formally, +suppose that we are given a group generating algorithm G(n) outputting +for each n a cyclic group G_n and a generator g. + +For adversary A the experiment DLog_{A,G}(n) then is the following: + +1. Run G(n) to obtain (G,q,g) where G is a cyclic group of order q +with generator g. + +2. Choose h<-G /* e.g. by putting h=g^d for d<-Z_q */ +3. A is given G,q,g,h and outputs e:Z_q +4. The output of the experiment is 1 if g^e = h + +By definition, the discrete logarithm problem is hard for G() if for +all adversaries A one has Pr(DLog_{A,G}(n)=1) = negl(n). + +It is generally believed that discrete logarithm is hard for the +aforementioned example groups. + +Related problems are computational Diffie-Hellman (CDH) and decisional +Diffie-Hellman (DDH). + +Computational Diffie-Hellman: given a cyclic group G of order q and +generator g as above and h=g^x, h'=g^y determine (without knowing x,y !) +the value g^{xy}. + +Decisional Diffie-Hellman: given a cyclic group G of order q and +generator g as above and h=g^x, h'=g^y and h''=g^z determine (without +knowing x,y,z !) whether or not g^{xy}=g^z. + +Clearly, a solution to the discrete logarithm problem implies a +solution to Diffie-Hellman, but the converse is not known. As a +result, hardness of discrete log is a weaker assumption than hardness +of DDH (and CDH) + +Diffie-Hellman is important for the eponymous Diffie-Hellman +key-exchange protocol: In order to share a common secret key Alice may +choose random x:Z_q and send u=g^x to Bob. Bob does the same and thus +sends v=g^y to Alice. Now, Alice and Bob can both compute the shared +key g^{xy} as u^x (Alice) and v^y (Bob). We will show later that +assuming DDH is hard this scheme is secure in a precise sense. + +Formal definition of hardness of DDH: + +Given a group-generating algorithm G() producing cyclic groups as +above, we say that the decisional Diffie Hellman problem is hard for +G() if for all probabilistic polynomial-time adversaries A and all n we have + + |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) + +where G(n)=(G,q,g) and x,y,z <- Z_q. + +Thus, DDH is hard, if g^{xy} looks like a random element of G even if +g^x and g^y are known. + +We close this chapter by remarking that under the assumption that RSA +is hard thre exist pseudo random generators, pseudorandom functions, +and permutations (see KL6 and 7.4.1). Under the assumption that +discrete logarithm is hard for some group then there exist collision +resistant hash functions. (KL7.4.2). -- cgit v1.2.3