CS 4803 Computer and Network SecurityAlexandra (Sasha) BoldyrevaVery basic number theory1Let Z = {. . . , "2, "1, 0, 1, 2, . . .} denote the set of integers. Let Z+ = {1, 2, . . .} denote the set of positive integers and N = {0, 1, 2, . . .} the set of non-negative integers.If a, N are integers with N > 0 then there are unique integers r, q such that a = Nq + r and 0 # r < N. We associate to any positive integer N the following two sets: ZN ={0, 1, . . . , N " 1}, ZN={ i!Z : 1#i#N"1 and gcd(i,N)=1 (relatively prime to N)} "2Groups•Def. Let G be a non-empty set and let ! denote a binary operation on G. We say that G is a group if it has the following properties: 1. Closure: For every a, b G it is the case that a ! b is also in G. 2. Associativity: For every a, b, c G it is the case that (a ! b) ! c = a ! (b ! c). 3. Identity: There exists an element 1 G such that a ! 1 = 1 ! a = a for all a G. 4. Invertibility: For every a G there exists a unique b G such that a ! b = b ! a = 1. inverse, denoted a-13•Fact. Let N be a positive integer. Then ZN is a group under addition modulo N, and ZN is a group under multiplication modulo N. •In any group, we can define an exponentiation operation: if i = 0 then ai is defined to be 1, if i > 0 then ai = a ! a ! ! ! a (i times) if i < 0 then ai = a-1 ! a-1 ! ! ! a-1 (j=-i times)•For all a G and all i,j Z: •ai+j = ai ! aj •(ai)j = aij •a-i = (ai)-1= (a-1)i *4•The order of a group is its size•Fact. Let G be a group and let m = |G| be its order. Then am = 1 for all a G •Fact. Let G be a group and let m = |G| be its order. Then ai = ai mod m for all a G and all i Z.•Example. Let us work in the group Z21 ={1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} under the operation of multiplication modulo 21. m=12. 586 mod 21 = 586 mod 12 mod 21 = 52 mod 12 mod 21 = 25 mod 21 = 4 *5•If G is a group, a set S G is called a subgroup if it is a group in its own right, under the same operation as that under which G is a group. •Fact. Let G be a group and let S be a subgroup of G. Then the order of S divides the order of G.6Algorithms and their running times•Since in cryptography we will be working with BIG numbers, the complexity of algorithms taking numbers as inputs is measured as a function of the bit-length of the numbers.•E.g. PrintinBinary (A), where A=2k takes k operations7Some basic algorithms4 COMPUTATIONAL NUMBER THEORYAlgorithm Input Output Running TimeINT-DIV a, N (N > 0) (q, r) with a = Nq + r and 0 ≤ r < N O(|a| · |N |)MOD a, N (N > 0) a mod N O(|a| · |N |)EXT-GCD a, b ((a, b) "= (0, 0)) (d, a, b) with d = gcd(a, b) = aa + bb O(|a| · |b|)MOD-ADD a, b, N (a, b ∈ ZN) (a + b) mod N O(|N |)MOD-MULT a, b, N (a, b ∈ ZN) ab mod N O(|N |2)MOD-INV a, N (a ∈ Z∗N) b ∈ Z∗Nwith ab ≡ 1 (mod N ) O(|N |2)MOD-EXP a, n, N (a ∈ ZN) anmod N O(|n| · |N |2)EXPGa, n (a ∈ G) an∈ G 2|n| G-operationsFigure 9.1: Some basic algorithms and their running time. Unless otherwise indicated, aninput value is an integer and the running time is the number of bit operations. G denotes a group.9.2.2 Integer division and mod algorithmsWe define the integer division function as taking input two integers a, N, with N > 0, and returningthe quotient and remainder obtained by dividing a by N. That is, the function returns (q, r) such8Cyclic groups and generators•If g G is any member of the group, the order of g is defined to be the least positive integer n such that gn = 1. We let <g> = { gi : i Zn } = {g0,g1,..., gn-1} denote the set of group elements generated by g. This is a subgroup of order n. •Def. An element g of the group is called a generator of G if <g>=G, or, equivalently, if its order is m=|G|.•Def. A group is cyclic if it contains a generator.•If g is a generator of G, then for every a G there is a unique integer i Zm such that gi = a. This i is called the discrete logarithm of a to base g, and we denote it by DLogG,g(a). •DLogG,g(a) is a function that maps G to Zm, and moreover this function is a bijection.•The function of Zm to G defined by i ! gi is called the discrete exponentiation function9•Example. Let p = 11. Then Z11 = {1,2,3,4,5,6,7,8,9,10} has order p # 1 = 10. We find the subgroups generated by group elements 2 and 5. We raise them to the powers 0,...,9. •••<2> = {1,2,3,4,5,6,7,8,9,10}=Z11 <5> = {1,3,4,5,9}2 is a generator and thus Z11 is cyclic.*8 COMPUTATIONAL NUMBER THEORYFig. 9.1. (The input a is not required to be relatively prime to N even though it usually will be, sois listed as coming from ZN.) In that case, each group operation is implemented via MOD-MULTand takes O(|N|2) time, so the running time of the algorithm is O(|n| · |N|2). Since n is usuallyin ZN, this comes to O(|N |3). The salient fact to remember is that modular exponentiation is acubic time algorithm.9.3 Cyclic groups and generatorsLet G be a group, let 1 denote its identity element, and let m = |G| be the order of G. If g ∈ Gis any member of the group, the order of g is defined to be the least positive integer n such thatgn= 1. We let"g# = { gi: i ∈ Zn} = {g0, g1, . . . , gn−1}denote the set of group elements generated by g. A fact we do not prove, but is easy to verify, isthat this set is a subgroup of G. The order of this subgroup (which, by definition, is its size) is justthe order of g. Fact 9.6 tells us that the order n of g divides the order m of the group. An elementg of the group is called a generator of G if "g# = G, or, equivalently, if its order is m. If g is agenerator of G then for every a ∈ G there is a unique integer i ∈ Zmsuch …
View Full Document