CS计算机代考程序代写 algorithm CM30173: Cryptography\reserved@d =[@let@token art IV

CM30173: Cryptography\reserved@d =[@let@token art IV

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Part V

Public-key cryptography

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

The discrete logarithm problem

Discrete logarithm problem (DLog problem)

Given p prime, ! a primitive element modulo p and
” ! Z!p find an element a, 0 ” a ” p # 2 such that

!a $ ” (mod p)

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Generalised discrete logarithm problem

Generalized discrete logarithm problem

Given a finite cyclic group G of order n, ! a generator
of G and ” ! G find an element a, 0 ” a ” n # 1 such
that

!a = ”

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Algorithms for computing discrete logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus method

A lower bound on complexity?

Discrete logarithms in other groups

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Types of algorithms

Algorithms which work in arbitrary groups
Exhaustive search

Shanks’ algorithm

Pollard’s rho algorithm

Algorithms which work in arbitrary groups but
require the order of the group to have only small
prime factors

Pohlig-Hellman algorithm

Algorithms which only work in certain groups
Index-calculus method

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Algorithms for computing discrete logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus method

A lower bound on complexity?

Discrete logarithms in other groups

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Exhaustive search

Compute
!, !2, !3, . . . (1)

until ” = !a is found.

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Exhaustive search

Compute
!, !2, !3, . . . (1)

until ” = !a is found.

We compute a new term in the list by multiplying
the previous term by !

We only store the current element of the list

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Exhaustive search

Compute
!, !2, !3, . . . (1)

until ” = !a is found.

We compute a new term in the list by multiplying
the previous term by !

We only store the current element of the list

Total time: O(n)

Total space: O(1)

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Algorithms for computing discrete logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus method

A lower bound on complexity?

Discrete logarithms in other groups

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Shanks’ algorithm

It is a time-memory trade-o!

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Shanks’ algorithm

It is a time-memory trade-o!

Let m = %
&

n’

CM30173:
Cryptography

Part IV

Algorithms for
computing discrete
logarithms

Exhaustive search

Shanks’ algorithm

Pohlig-Hellman

The index calculus
method

A lower bound on
complexity?

Discrete logarithms
in other groups

Shanks’ algorithm

It is a time-memory trade-o!

Let m = %
&

n’
If !a = ” then we can write

” = !a = !mj+i

for 0 ” j, i < m CM30173: Cryptography Part IV Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups Shanks’ algorithm It is a time-memory trade-o! Let m = % & n' If !a = " then we can write " = !a = !mj+i for 0 " j, i < m We can now write !mj+i = !mj!i and hence " = !mj!i ( "!"i = !mj CM30173: Cryptography Part IV Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups Shanks’ algorithm Algorithm (Shanks(G, n, !, ")) 1 m = % & n' 2 Compute list L1: (0, !0), (1, !m), (2, !2m), . . . , (m # 1, !(m"1)m) 3 Sort list L1 of pairs (j, !mj) on the value of !mj 4 Compute list L2: (0, "!0), (1, "!"1), (2, "!"2), . . . , (m#1, "!"(m"1)) 5 Sort list L2 of pairs (i, "!"i) on the value of "!"i 6 Find (j, y) ! L1 and (i, y) ! L2 7 log! " = (mj + i) (mod n) CM30173: Cryptography Part IV Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups CM30173: Cryptography Part IV Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups Pohlig-Hellman Key point: The run time of Pohlig-Hellman depends on the size of the prime factors of the group order n The implication is that when selecting a group for cryptographic purposes we should ensure that n has at least one large prime factor Public-key cryptography Algorithms for computing discrete logarithms Exhaustive search Shanks' algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups