Ralph Merkle, Martin Hellman
and Whitfield Diffie, 1977

Exercises in Discrete Logs

by: burt rosenberg
at: university of miami
date: apr 2018

Overview

Copy the template code from class/proj5/dlog-tasks.py as well as the Makefile found in that folder, to your [username]/proj5 folder. Complete the code as necessary so that the test function, defined in the bottom of section of dlog-tasks.py, run successfully.

Remember that the tests are called basic tests, because they only test basic functionality. Your code may be tested on reasonably more general inputs.

Reuse the code MyMod class and extended gcd from the previous project. Code is provided to create primes p for which p-1 are factored in k primes. The point of this is provide a favorable situation for the Pohlig-Helman algorithm for discrete logs.

There are 5 tests and a challenge,

  1. Generator finding
  2. Chinese Remainder
  3. Pohlig-Hellman algorithm for discrete logs
  4. Schnorr Identification Transcripts
  5. Schnorr Identification Protocol Run

Generator finding

Suppose p-1 is the produce of distinct primes qi,,

p = Πi qi, qi ≠ qj for i ≠ j where one of the primes 2 (because p is even). We want to check that g is a generator. It is clear that gp-1=1 (p), but is it unity for any smaller exponent?

We only need check that g (p-1)/qi ≠ 1, for all qi.

Use these observations to find a generator for ℤp.

Hint: Check for a generator 2, 3, 4, etc.

Chinese Remainder

Given a dictionary { ni : ji } where ji = x mod ni, and all the ni are relatively prime, calculate x. The number x is unique only up to modulo Πi ni. Return an x reduced to the usual range.

To help break the problem down, chinese_remainder uses chinese_remainder_aux to solve the restriction of the problem to only two moduli with their two residues. Solving for more than two simultaneous congruences can be done iteratively, beginning with the first two congruences, and adding additional congruences one by one.

Method of solution

Consider a system of two congruences over relatively prime numbers n and m, Construct the value,

z = x × m × α + y × n × β This is almost x mod n, and almost y mod m — it just needs a bit of correction as m × α reduces mod n, etc. We adjust α and β as necessary, z mod n = ( x × m × α + y × n × β ) mod n = ( x × m × α + 0 ) mod n = x mod n if α were chosen such that ( m × α = 1 ) mod n.

Pohlig-Hellman algorithm for discrete logs

Implement the Pohlig-Hellman algorithm for discrete logs. First implement pohlig_hellman_aux, which returns a dictionary of partials. Then use the chinese remainder theorem to glue together all the partials into a full solution. 

    For each qi dividing (p-1):
        calculate a generator gi for the subgroup ℤqi
             gi = g(p-1)/qi
        for the given x, place it into the  ℤqi
             xi = x(p-1)/qi
        Find the ji such that xi = giji
    return the Python dictionary { qi : ji }.

Discussion:

We are looking for the j such that x = gj. Rising both sides to (p-1)/qi, gives xi = gij, however now the value of j is only known mod qi, hence ji = j mod qi.

Schnorr Identification Transcripts

There are two steps to this problem. Implement verify_schnorr_ident which encodes the verification equation. And implement gen_schnorr_transcript which returns a triple (I,r,s) which passes the verification. It should also be, as required for the theory, a random sampling over all transcripts of the protocol.

Note that the secret is not available to these functions. The transcript is generated without reference to the secret, proving that eavesdropping gives no advantage for a forgery.

Schnorr Identification Protocol Run

We simulate a run of the Schnorr Identification Protocol by a sequence of calls, see gen_schnorr_run. You implmenent gen_schnorr_run_P1 and gen_schnorr_run_P2, the two algorithms run by the genuine prover, to complete the problem. 

PRIVATE/PUBLIC KEY GENERATION

Generate Discrete log system ---> (g,p)
    where prime p and g a generator of ℤp*

Generate private/public key pair ----> (x,y)
    where x  in  ℤp-1 and y = gx mod p



SCHNORR PROTOCOL

    Prover                     Verifier
    ------                     --------
    
k chosen in  ℤp-1 
I := P1(k,x)
              ------- I ------->
                               r chosen in  ℤp-1
              <------ r --------
s := P2(k,I,r,x)
              ------- s ------->
                                Verify(I,r,s,y)

Note: We should work in a strong subgroup of ℤp*, but p has been chosen deliberately weakened.

The Challenge

Complete the Schnorr Identification protocol successfully, thereby identifying as the holder of the x with public key y. You are given y, g, p, I and r. Find s.

Hint: Assuming the protocol secure, you will need to recover x.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 15 apr 2018
update: 15 apr 2018