Final Project: Pohlig-Hellman

by: burt rosenberg
at: university of miami
date: dec 2021

Overview

You are to implement the Pohlig-Hellman Algorithm and apply it to the case of the group of points on an elliptic curve.

The starting point with by your code from Project 5.

The discrete log problem for an elliptic curve looks different then for modulo intergers. In the modulo integers, the notation is multiplication,

g, g², ... , gⁱ, ... , gⁿ = 1

For the elliptic curve the notation is addition,

P, 2P, ...., iP, ... , nP = 0

Code Requirements

You must create the class PohligHellman, with initializer that takes the elliptic curve object, a point P, the order n of the subgroup of P in the elliptic curve and a factorization of that order. The factorization is a list of pairs,

[ (n₁, e₁), (n₂, e₂), ... , (n_k, e_k) ], 

given:
− gcd(n_in_j) = 1 for i ≠ j
− and ∏_i n_i^e_i = n

The ph_solve method takes a point Q and returns an n such that nP=Q, or None using the Pohlig-Hellman assuming e_i=1 for all i.

The ph_solve_plus method does the same, without the assumption on the exponents.

Note therefore that you do not have to factor the group order. The factors are given as input.

Functions in the class that implement clear steps in the algorithm will aid in finding partial credit, if appropriate. For instance, separate functions inside your class for the Chinese Remainder Theorem and its inverse, and for the writing of a number in base n are good candidates for such functions.

While the three day lateness forgiveness is still in effect, points will be not be awarded for more than three days late.

Part 1

The basic description is section 9.2.1 in the class text.

You will need to implement the Chinese Remainder Theory code described in section 8.1.5 of the text; generalized to the case of more than two factors.

Starting off with a simple example, suppose the order of the curve (the number of points) is n = pq for p and q relatively prime. Given an point dP for an unknown d, we can write

d = kp + i, i = d mod p

And calculate,

q(dP) = q(kp+i)P = qkpP + qiP  = knP + iqP = k0 + i(qP) = i(qP)

We calculate Q = qP and then by trial and error solve,

iQ ?= 0Q, 1Q, 2Q, ... , (p-1)Q

We do the same for j = d mod q, then use chinese remainder to get the unique number mod n that is i mod p and j mod q. This is d.

This method quickly gives the discrete log when the order of the curve is the product of small numbers.

Part 2

Implement Exercise 9.5. Note that this means implementing Exercise 9.4.

In the previous method, we had to solve for factors of pⁱ but trial end error from 0 up to pⁱ-1. It can be done faster by working mod p and then dividing down.

As an example, suppose n=p³q. Then the previous reasoning gives a trial and error solution for,

iQ ?= 0Q, 1Q, 2Q, ... , (p³-1)Q

with Q = qP, as before. Writing i base p,

i = i₀ + i₁ p + i₂ p²

then,

p²iQ = i₀ p²Q + i₁ p³Q + i₂ p⁴Q = i₀ p²Q + i₁ 0 + i₂ p 0 = i₀ p²Q

Set R = p²Q, then solve by trial and error,

i₀R ?= 0R, 1R, 2R, ...., (p-1)R

Subtract off i₀Q from iQ, multiply by p and repeat to find i₁. And so on.

The Challenge

Find good elliptic curves to test your code. You will want curves of fairly high order, but with an order that factors into medium size primes.

Among those curves, you will want some that the order includes primes to a power greater than 1.

Specific challenges will be announced here on this page.

Interesting Elliptic Curves

Here are some interesting Elliptic Curves, with their order, factored, and a generator.
A curves is given as (p,A,B) for the equation y² = x³ + Ax + B mod p.
The factoring is given as a list of prime-exponent pairs (p,e) = p^e. 

curve: (79,1,6)
	order: 97 = [(97, 1)]
	gen: (1, 18, 1)

curve: (79,2,5)
	order: 71 = [(71, 1)]
	gen: (0, 20, 1)

---

curve: (787,3,9)
	order: 797 = [(797, 1)]
	gen: (0, 784, 1)

curve: (787,7,4)
	order: 792 = [(2, 3), (3, 2), (11, 1)]
	gen: (0, 785, 1)

curve: (787,5,2)
	order: 841 = [(29, 2)]
	gen: (3, 455, 1)

curve: (787,7,7)
	order: 793 = [(13, 1), (61, 1)]
	gen: (0, 105, 1)
	
---

curve: (7207,2,2)
	order: 7168 = [(2, 10), (7, 1)]
	gen: (0, 4833, 1)

curve: (7207,2,7)
	order: 7183 = [(11, 1), (653, 1)]
	gen: (6, 6533, 1)
	
curve: (7207,3,8)
	order: 7283 = [(7283, 1)]
	gen: (0, 2459, 1)
	
curve: (7207,6,2)
	order: 7261 = [(53, 1), (137, 1)]
	gen: (0, 4833, 1)

---

curve: (50207,1,5)
	order: 50235 = [(3, 1), (5, 1), (17, 1), (197, 1)]
	gen: (7, 4408, 1)
	
curve: (50207,5,3)
	order: 50531 = [(13, 3), (23, 1)]
	gen: (0, 9978, 1)

curve: (50207,9,8)
	order: 50568 = [(2, 3), (3, 1), (7, 2), (43, 1)]
	gen: (1, 15240, 1)

---

curve: (104107,1,9)
	order: 104477 = [(191, 1), (547, 1)]
	gen: (0, 104104, 1)

curve: (104107,5,8)
	order: 103883 = [(13, 1), (61, 1), (131, 1)]
	gen: (5, 24473, 1)
	
curve: (104107,4,4)
	order: 103819 = [(17, 1), (31, 1), (197, 1)]
	gen: (0, 104105, 1)

curve: (104107,5,4)
	order: 104247 = [(3, 6), (11, 1), (13, 1)]
	gen: (1, 25887, 1)
	
curve: (104107,9,2)
	order: 103483 = [(103483, 1)]
	gen: (2, 58027, 1)

---

curve: (1040891,1,3)
	order: 1041397 = [(7, 2), (53, 1), (401, 1)]
	gen: (0, 97874, 1)

curve: (1040891,3,3)
	order: 1040569 = [(181, 1), (5749, 1)]
	gen: (0, 97874, 1)

curve: (1040891,4,7)
	order: 1040813 = [(1040813, 1)]
	gen: (0, 510673, 1)

curve: (1040891,5,2)
	order: 1041277 = [(41, 1), (109, 1), (233, 1)]
	gen: (2, 655960, 1)

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

author: burton rosenberg
created: 2 dec 2021
update: 3 dec 2021