(5/5)

Hire Me
(5/5)

Hire Me
(5/5)

Hire Me
(5/5)

Hire Me

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

INSTRUCTIONS TO CANDIDATES

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..

## Related Questions

##### . The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

##### . 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

##### . The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

##### . Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

##### . The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme

Get Free Quote!

289 Experts Online