CS260 Study Guide

6a. Solve problems involving cyclic groups

• What is a finite group?
• What is a cyclic group?
• What is the order of an element in a cyclic group?

A group is a mathematical concept that is central to many cryptographic systems. By definition, a group is a set G along with some operator that acts on pairs of elements from the G. A group must obey the closure property, must obey the associative property, must have an identity element for the group operator, and every element in the group must have an inverse. A finite group is a group where the set G contains a finite number of elements.

A generator is an element from which all other elements in a group can be generated by successively applying the group operator. A cyclic group is a group that contains a generator. Furthermore, every element in a finite cyclic group has an order which means that it will return to the identity element after successive applications of the group operator. The number of applications of the group operator to return an element to the identity element is called the order of an element. For example, in a congruence modulo p where p is a prime number (a finite cyclic group), a generator will have an order equal to p-1. You should understand generators and the order of an element within a finite cyclic group, such as a congruence modulo p.

To review, see:

• Introduction to Cyclic Groups

6b. Describe the discrete logarithm problem

• What is the discrete logarithm problem (DLP)?
• Why are finite cyclic groups relevant to the DLP?
• Why can cryptographic systems be built upon the DLP?

Given a prime number, p, a congruence modulo p, a generator 𝛼, and the equation

$y = 𝛼^x \text{ (mod p)}$

when the value y is given, the discrete logarithm problem (DLP) determines the value x. A congruence modulo p is a finite cyclic group when p is prime, so the theory of finite cyclic groups is quite relevant to the DLP. Logarithms are exponents, so conceptually, this problem is similar to what you may be used to from basic algebra. The main difference is that the DLP takes place over a congruence modulo p; hence, determining the value of the exponent x can be more challenging. This problem is considered to be computationally difficult to solve and is a good candidate for building cryptographic systems. You should be prepared to compute the value of x via a brute-force search. You should also be prepared to execute Python instructions, such as

alpha **x % p

when the numbers are small. When the numbers are large, you should be prepared to apply the repeated squaring algorithm whose code was developed and applied in previous units.

To review, see:

• The Discrete Logarithm Problem

6c. Apply Diffie-Hellman key exchange

• How can the DLP be applied in cryptographic systems?
• What is Diffie-Hellman (DH) key exchange?
• What information is needed to decrypt the DH key exchange?

Asymmetric cryptography is extremely useful for solving the key distribution problem. The Diffie-Hellman (DH) key exchange protocol is based on the DLP. It allows two parties (for example, Alice and Bob) to exchange information that will lead to computing a key that could be used, for example, in a symmetric cryptographic system.

Diffie-Hellman (DH) key exchange is as follows:

1. Given a prime number, p, a congruence modulo p, and generator 𝛼, Alice chooses a private random integer x from the congruence
2. Bob chooses a private random integer y from the congruence.
3. Alice sends Bob: YA (where YA = 𝛼^x (mod p) )
4. Bob sends Alice: YB (where YB = 𝛼^y (mod p) )
5. Alice computes K = (YB)^x
6. Bob computes K = (YA)^y

The value of K is guaranteed to be the same based upon the laws of exponents within a congruence so that Alice and Bob compute the same key. If YA and YB are intercepted, the DLP would have to be solved to compute the secret values of x and y. Once these values are known, they can readily be computed as $K = 𝛼{xy}\text{ (mod p)}$. Therefore, the security of the DH key exchange is based on the computational security of the DLP. You should be prepared to compute the solution to the DLP for small numbers via a brute force search, and you should be prepared to compute values of YA, YB, and K given a set of values.

To review, see:

• The Diffie-Hellman Algorithm

6d. Create programs to implement a Diffie-Hellman key exchange

• How is DH key exchange implemented in Python?
• What algorithms in this course would be applicable to the DH protocol?
• How are shared keys computed?

Implementing the DH key exchange requires finding a generator and exponentiation within a congruence. It is assumed at this point that you have code for the repeated squaring algorithm and for finding generators within a congruence. Additionally, you must have code to solve the discrete logarithm problem within a congruence modulo p using a brute force approach (for example, by using a loop). If these tools are in place, then you should be able to compute keys, compute secret values for the exponent, and exponentiate using large numbers. Make sure to practice applying your code with test values to ensure you can compute with values in the DH exchange problems.

To review, see:

• Python Implementation

Unit 6 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• cyclic group
• Diffie-Hellman (DH) key exchange
• discrete logarithm problem (DLP)
• finite group
• generator
• order of an element