CYG Chapter 7 The Discrete Logarithm

1. Let n in N\{1} and a in Z_n*

2. ord_n(a)=min{k in {1,…,phi(n)}| a^k equiv 1 (mod n)}

3. If ord_n(a)=phi(n) then a is called “pem n”

1. There exists no 1<=i<j<=phi(n) with aⁱ equiv a^j (mod n) and thus a^j-i equiv 1 (mod n)

2. Hence <a> is a cyclic group

1. <a>={a,a²,…,a^phi(n)}=Z_n* // Consists just of powers of a

2. a is called generator

Is for given n the group Z_n* cyclic or not?

1. Let n in N

2. pem n exists iff n in {2,4,p^k,2p^k|p>=3 prime and k in N}

3. If pem n exists then there exist phi(phi(n)) many

1. Let n=7, phi(n)=6

2. Test a=2 … a³=1 → Not a pem 7

3. Test a=3 … a⁶=1 → Is a pem 7

4. Test a=5 … a⁶=1 → Is a pem 7

5. Because phi(phi(7))=phi(6)=|{1,5}|=2 we know we found all

1. Let a be pem n and y in Z_n*

2. There exists the unique dl x in {0,…,phi(n)-1} with a^x equiv y (mod n) // x=log_ay

1. Function y=a^x mod n can be considered a one-way function

2. Exponentiation can be efficiently computed using “square and multiply algorithm”

1. Input is x=(x_t,…,x₀) in N and a in N

2. Output is a^x mod n

3. Init y←a

4. For(i=t-1; i>=0; --i) compute y←y² mod n and if x_i=1 then y←y*a mod n

5. Return y

rounddown(log₂x)+v(x)-1 many multiplications with v(x) number of bits with value “one” in the binary representation of x

1. Based on dl one-way function

2. (Unauthenticated) key agreement protocol allowing two parties to establish a shared secret key over an open channel

1. Primes p<=N with 2p+1 also prime

2. |{p|p<=N and p SG-prime}|~ 2C₂N/log²N many with C₂~0.66

1. Prime p and a pem p are selected and published // Initial setup

2. A chooses a random secret x in {2,…,p-2} and sends u=a^x mod p to B

3. B chooses a random secret y in {2,…,p-2} and sends v=a^y mod p to A

4. B receives u and computes shared key u^y=(a^x)^y mod p

5. A receives v and computes shared key v^x=(a^y)^x mod p

Test if a is pem p

1. Let p>=3 prime and p-1=Prod_i=1^kp_i^t_i

2. a is pem p iff a^(p-1)/p_i notequiv 1 (mod p) fa i in [1,k]

1. Find appropriate p and a by choosing a SG-prime q

2. Randomly choose a in {2,…,p-1} until a² and a^q notequiv 1 (mod p)

3. There are phi(phi(p))=phi(p-1)=phi(2)phi(q)=q-1 many // Probability to select pem p is q-1/p-2=q-1/2q-1~1/2

1. Given prime p, a pem p , a^x mod p and a^y mod p

2. Calculate a^xy mod p

Open questions if an efficient algorithm for the DHP is one for dl

1. Active intruder O

2. Use a^q=a^(p-1)/2 has order 2 since (a^(p-1)/2)² equiv a^p-1 equiv 1 (mod p) // Fermat’s little theorem

1. O intercepts key exchange by a^xq and a^yq thus A and B share a^xyq

2. O knows that a^xyq=(a^q)^xy equiv a^q equiv ±1 (mod p) // Try out both possibilities

Avoid by checking that received messages are both different from ±1 mod p

1. O computes x₀ and y₀

2. Decrypt and encrypt before sending further

Avoid by use of digital signatures

1. No-key protocol

2. Princess and knight with box locked by two different padlocks

1. Let p prime and a,b in Z_p-1*

2. Fa m in Z_p it holds that m^aba’b’ equiv m (mod p)

1. Use fact that bb’=t(p-1)+1 with c^t(p-1) equiv 1 (mod p)

2. m^aba’b’ mod p = (m^a mod p)^bb’a’ mod p = c^bb’a’ mod p = c^a’ mod p = m mod p

1. Publish prime p // Initial setup

2. A and B choose secret random numbers a,b in Z_p-1* with a’,b’

3. A sends c₁=m^a mod p to B

4. B sends c₂=c₁^b mod p to A

5. A sends c₃=c₂^a’ mod p to B

6. B computes m=c₃^b’ mod p

Protocol does not include authentication, hence offers protection from passive adversaries only