中国矿业大学：《密码学》课程教学资源（PPT讲稿）认证协议（Authentication Protocol）NTHEORY 2 Group Theory and Number

Group Theory and Number Theory for Cryptology Irene gassko and Peter gemmell

Group Theory and Number Theory for Cryptology Irene Gassko and Peter Gemmell

Definition:Gro叩p A set g of elements and operator@ form a group if for ally in g,x@y is also ing(inclusion) there is an identity element e such that for all x in g, e(ax=X for all x in G, there is an inverse element such that x.@x=e for allx,y, z in G, (x@y@z=x@(yaz)(associativity) abelian groups have the property: for all x,y inG, x@y=y@x Note: sometimes the group operator may be denoted“*”or“+”, the identity denoted 0or“1 and the inverse ofx“-x” Note 2: unless stated otherwise, we consider only abelian roups

Definition: Group A set G of elements and operator @ form a group if: • for all x,y in G, x @ y is also in G (inclusion) • there is an identity element e such that for all x in G, e@x = x • for all x in G, there is an inverse element x -1 such that x-1@x = e • for all x,y,z in G, (x@y)@z = x@(y@z) (associativity) • abelian groups have the property: for all x,y in G, x@y = y@x Note: sometimes the group operator may be denoted “*” or “+”, the identity denoted “0” or “1” and the inverse of x “-x”. Note 2: unless stated otherwise, we consider only abelian groups

E xamples o of Groups The integers under addition G=Z= the integers={….-3,-2,-1,0,1,2….} the group operator is "+ ordinary addition the integers are closed under addition the identity is 0 the inverse of x is-x the integers are associative the integers are commutative(so the group is abelian

Examples of Groups The integers under addition G = Z = the integers = { … -3, -2, -1, 0 , 1 , 2 …} the group operator is “+”, ordinary addition • the integers are closed under addition • the identity is 0 • the inverse of x is -x • the integers are associative • the integers are commutative (so the group is abelian)

Examples of groups The non-zero rationals under multiplication G=Q-0}={ab} a b non-zero integers the group operator is ">> ordinary multiplication If a/b, c/d are in Q-0f thena/b*c/d=(ac/bd)is in Q-10) the identity is 1 the inverse of a/b is b/a the rationals are associative the rationals are commutative(so the group is abelian

Examples of Groups The non-zero rationals under multiplication G = Q -{0} = {a/b} a,b non-zero integers the group operator is “*”, ordinary multiplication • If a/b, c/d are in Q-{0}, then a/b * c/d = (ac/bd) is in Q-{0} • the identity is 1 • the inverse of a/b is b/a • the rationals are associative • the rationals are commutative (so the group is abelian)

Examples of groups The non-zero reals under multiplication G=R-{0 the group operator is ">> ordinary multiplication If a, b are inR-0f, then ab is inr-10) the identity is 1 the inverse of a is 1/a the reals are associative the reals are commutative(so the group is abelian)

Examples of Groups The non-zero reals under multiplication G = R -{0} the group operator is “*”, ordinary multiplication • If a, b are in R-{0}, then ab is in R-{0} • the identity is 1 • the inverse of a is 1/a • the reals are associative • the reals are commutative (so the group is abelian)

E xamples o of Groups The integers mod n under addition G=LN= the integers modulo N=(0.N-1) the group operator is"+ modular addition the integers modulo n are closed under addition the identity is 0 the inverse of x is-x addition is associative addition is commutative(so the group is abelian

Examples of Groups The integers mod N under addition G = Z+ N = the integers modulo N = {0 … N-1} the group operator is “+”, modular addition • the integers modulo N are closed under addition • the identity is 0 • the inverse of x is -x • addition is associative • addition is commutative (so the group is abelian)

E xamples o of Groups The integers mod p under multiplication G=Z'n=the non-zero integers modulo p=(1.p-1) the group operator is "*>, modular multiplication the integers modulo p are closed under multiplication this is so because if GCD(x, p)=l and gCd(y p)=1 then gCd(xy,p)=1 the identity is 1 the inverse of x is from euclids algorithm ux+ vp=1=GCD(x,p) SOX=u alsoxl=u=xp-2 multiplication is associative multiplication is commutative(so the group is abelian)

Examples of Groups The integers mod p under multiplication G = Z* p = the non-zero integers modulo p = {1 … p-1} the group operator is “*”, modular multiplication • the integers modulo p are closed under multiplication: this is so because if GCD(x, p) =1 and GCD(y,p) = 1 then GCD(xy,p) = 1 • the identity is 1 • the inverse of x is from Euclid’s algorithm: ux + vp = 1 = GCD(x,p) so x-1 = u also x-1 = u = xp-2 • multiplication is associative • multiplication is commutative (so the group is abelian)

Examples of groups ZN: the multiplicative group mod N G=Z n the positive integers modulo n relatively prime to N the group operator is"x>, modular multiplication the integers modulo n are closed under multiplication this is so because if GCD(x, n)=l and GCD( n)=1 then gCd(xy, n)=1 · the identity is the inverse of x is from Euclids algorithm Ux+VN=1=GCD(X, N) So X=uX(N-) multiplication is associative multiplication is commutative(so the group is abelian)

Examples of Groups Z* N : the multiplicative group mod N G = Z* N = the positive integers modulo N relatively prime to N the group operator is “*”, modular multiplication • the integers modulo N are closed under multiplication: this is so because if GCD(x, N) =1 and GCD(y,N) = 1 then GCD(xy,N) = 1 • the identity is 1 • the inverse of x is from Euclid’s algorithm: ux + vN = 1 = GCD(x,N) so x-1 = u (= x f(N)-1 ) • multiplication is associative • multiplication is commutative (so the group is abelian)

Examples of a non-abelian group GL(2), 2 by 2 non-singular real matrices under matrix multiplication a b GL(2)= ad-bC=0 if a and b are non-singular so is aB the identity is I=o1] a c al/(ad-bc) matrIx multiplication is associative matrix multiplication is not commutative

Examples of a non-abelian group GL(2), 2 by 2 non-singular real matrices under matrix multiplication • if A and B are non-singular, so is AB • the identity is I = [ ] • = /(ad-bc) • matrix multiplication is associative • matrix multiplication is not commutative GL(2) = {[ ], ad-bc = 0} a b c d 1 0 0 1 [ ] a b c d -1 [ ] d -b -c a

S subgroups (H, @) is a subgroup of(G, @)if H is a subset of g (H, @ is a group

Subgroups (H,@) is a subgroup of (G,@) if: • H is a subset of G • (H,@) is a group