In this project we will implement BSGS to crack the discrete log problem when pp is 42 bits

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Suppose pp is prime and \alpha \in \mathbb{Z}_p^*α∈Zp∗?. The order of \alphaα is the least positive integer kk such that \alpha^k \equiv 1 \mod pαk≡1modp. Suppose that for some unknown integer xx,

\beta \equiv \alpha^x \mod p.β≡αxmodp.

We know \betaβ and want to know the secret value xx. This is called the discrete logarithm problem (in \mathbb{Z}_p^*Zp∗?).

One way to find xx is to simply try all powers x=0,1,\ldots,k-1x=0,1,…,k−1 where kk is the order of \alphaα. But in cryptographic situations this will be infeasible. There are ways of finding xx that are much faster than brute force, however. These are discussed in our textbook in Chapter 8, beginning on page 221.

The first method presented is called Shanks' Baby-Step Giant-Step Method. (If you haven't read that material, please take a break from reading this and give it a once-over--if you don't have your book handy the PDF of Understanding Cryptography is easy to find online.) The BSGS method can solve the discrete logarithm problem in \mathbb{Z}_p^*Zp∗? where pp is a nn bit prime in O(\sqrt{n})O(n?) time and O(\sqrt{n})O(n?) space.

In this project we will implement BSGS to crack the discrete log problem when pp is 42 bits. (This is long enough to resist brute force on Cocalc. ). Thus, with BSGS, we need about 21 bits of space and time to execute about 2^{21}221 steps, both of which are available even on Cocalc.

Our numbers will be \beta = 1682398169711β=1682398169711, p = 1799431327777p=1799431327777, and \alpha = 2α=2. In the notation used in the book, |G| = p-1?G?=p−1. In this directory you will find a skeleton solution in the file shanks.cpp. Please complete the code in this file to find a value xx such that \alpha^x \equiv \beta \mod pαx≡βmodp.

Notes on the code

In shanks.cpp notice that you already have fast modular exponentiation available in the function called power(). You might observe that we're not quite using normal integers in this code. We're using 128 bit integers, which I've type defined to be a number type. The point of doing it this way is we can work with larger integers (or even GMP integers) by changing only the line of code where number is typedef-ed. We can't quite use unsigned longs for our integer type because the square and multiply algorithm needs at least 2\cdot42 = 842⋅42=84 bit integers, and unsigned longs are 64 bits.

Another thing to notice is that for the table we're using the C++ type called map. Some of you may not have used map before. It's not that straightforward to use, but it's probably the easiest way of creating the necessary table. You can find a lot of tutorials online by Googling "C++ map example" and things like that. Here is one you might use..

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of