Can you crack Diffie-Hellman?

You could check for an explanation of the full algorithm in the Baby step Giant step wiki .

We want $b$ such that $g^b \equiv B \pmod{p}$ .

We choose a base $\beta$ roughly the size of $\sqrt{p}$ .

For some $b_0, b_1$ , we have $b = b_0 \beta + b_1$

We have, $B \equiv g^b \equiv g^{b_0 \beta + b_1} \equiv (g^\beta)^{b_0} \cdot g^{b_1} \pmod{p}$ $\implies B g^{- b_1} \equiv (g^\beta)^{b_0} \pmod{p}$

Now, we can reduce our work to roughly the square root of the size of $p$ .

Here's the algorithm:

1. Build a hash table for all possible values of $b_1$ from 0 to $\beta$ inclusive.

2. For each value of $b_0 = 1, 2, \cdots \beta$ , check if $(g^\beta)^{b_0}$ is in the hash table.

3. Terminate when you've found $b_0$ . Output $b = b_0 \beta + b_1$

Here is a Sage implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

p = 20992321342930071437617535054294082600409305694823917901103517516849439468932230646876254462856426279068085286595868000559162159946064999915305764788212947;
R = Integers(p);
h = R(13261683723811565199480160483723583184154281997005060032137595421236239575828461774398757507049515905188090075911486594228158952115852574793046073896571395);
g = R(4567316637081665907977181518889182113445441987446007457733573698022127469439135656733423482251931597580003871195410610463070846363265764446085651841441485);

B = R(2**20);

L = {}

for x1 in xrange(B+1):
    L[h*(g**(-x1))] = x1

temp = g**B

for x0 in xrange(B+1):
    if temp**x0 in L:
        print x0*B + L[temp**x0] 
        break

I have also implemented the Baby-step giant-step algorithm (cf. solution by Agnishom Chattopadhyay ). You will find my C++ code below. The part Giant-step part is parallel.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196

#include <iostream>
#include <unordered_map>
#include <mutex>
#include <thread>
#include <vector>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>
#include <chrono>
#include <sstream>
template<typename ValueType>
ValueType binPowMod(const ValueType& aVal, const ValueType& expVal, const ValueType& modVal)
{
    //returns (aVal**expVal)%modVal
    ValueType resVal = ValueType(1);
    ValueType curExp = expVal;
    ValueType curMultip = aVal;
    while(curExp > 0)
    {
        if(curExp%ValueType(2) == ValueType(1))
        {
            resVal *= curMultip;
            resVal %= modVal;
        }
        curMultip *= curMultip;
        curMultip %= modVal;
        curExp /= ValueType(2);
    }
    return resVal;
}

template<typename ValueType>
std::unordered_map<ValueType, std::size_t> generatePowData(const ValueType& aVal,
                                                           const ValueType& modVal,
                                                           const std::size_t powDataSize)
{
    std::unordered_map<ValueType, size_t> resData;
    ValueType curVal = ValueType(1);
    for(std::size_t curPow = 0; curPow < powDataSize; ++curPow)
    {
        resData.insert(std::make_pair(curVal, curPow));
        curVal *= aVal;
        curVal %= modVal;
    }
    return resData;
}

template<typename ValueType>
void giantStepFun(const ValueType& bVal, const ValueType& pVal,
                  const ValueType& aPowMInvVal,
                  const std::unordered_map<ValueType, std::size_t>& powData,
                  const ValueType& iStart, const ValueType& iLimit,
                  bool& continueWork,
                  std::mutex& continueWorkMutex,
                  bool& hasSolution, ValueType& solVal)
{
    ValueType yVal = (bVal*binPowMod(aPowMInvVal, ValueType(iStart), pVal))%pVal;
    for(ValueType iCur = iStart; continueWork && iCur < iLimit; ++iCur)
    {
        const typename std::unordered_map<ValueType, std::size_t>::const_iterator findIt = powData.find(yVal);
        if(findIt == powData.end())
        {
            yVal *= aPowMInvVal;
            yVal %= pVal;
        }
        else
        {
            std::lock_guard<std::mutex> guard(continueWorkMutex);
            continueWork = false;
            hasSolution = true;
            ValueType jInd = ValueType(findIt->second);
            solVal = ValueType(iCur)*ValueType(powData.size())+jInd;
        }
    }
    return;
}

template<typename ValueType>
ValueType getTotalIter(const ValueType& pVal, const std::size_t powDataSize)
{
    ValueType res = pVal/powDataSize;
    while(res*powDataSize < pVal)
    {
        ++res;
    }
    return res;
}

template<typename ValueType>
ValueType getIDelta(const ValueType& totalIter, const std::size_t numberOfThreads)
{
    ValueType res = totalIter/numberOfThreads;
    if(totalIter%numberOfThreads != 0)
    {
        ++res;
    }
    return res;
}

template<typename ValueType>
void findLogMulti(const ValueType& aVal, const ValueType& bVal, const ValueType& pVal,
                  const std::unordered_map<ValueType, std::size_t>& powData,
                  bool& hasSolution, ValueType& solVal)
{
    const unsigned numberOfThreads = std::thread::hardware_concurrency();
    std::vector<std::thread> threadVector;
    threadVector.reserve(numberOfThreads);
    const std::size_t powDataSize = powData.size();
    const ValueType totalIter = getTotalIter(pVal, powDataSize);
    const ValueType iDelta = getIDelta(totalIter, numberOfThreads);
    ValueType iStart = 0;
    ValueType iLimit = iDelta;
    bool continueWork = true;
    std::mutex continueWorkMutex;
    const ValueType invExp = pVal-ValueType(2);
    const ValueType aInv = binPowMod(aVal, invExp, pVal);
    const ValueType aPowMInvVal = binPowMod(aInv, ValueType(powDataSize), pVal);
    for(std::size_t curThreadNum = 0; curThreadNum < numberOfThreads; ++curThreadNum)
    {
        threadVector.push_back(std::thread(giantStepFun<ValueType>,
                                           std::cref(bVal), std::cref(pVal),
                                           std::cref(aPowMInvVal),
                                           std::cref(powData),
                                           iStart, iLimit,
                                           std::ref(continueWork),
                                           std::ref(continueWorkMutex),
                                           std::ref(hasSolution),
                                           std::ref(solVal)));

        iStart = iLimit;
        iLimit +=iDelta;
        if(iLimit > totalIter)
        {
            iLimit = totalIter;
        }
        if(iStart == totalIter)
        {
            break;
        }
    }
    for(auto & th : threadVector)
    {
        th.join();
    }
    return;
}

template <typename TimeType>
std::string toDurationStr(TimeType& startTime)
{
    const auto endTime = std::chrono::steady_clock::now();
    std::chrono::duration<double> runTime = endTime-startTime;
    std::stringstream ss;
    ss<<runTime.count()<<" [s]";
    return ss.str();
}

template<typename ValueType, std::size_t powDataSize>
void solveBrillPuzzle()
{
    //solves https://brilliant.org/practice/cryptography-level-3-4-challenges/?p=2
    bool hasSolution = false;
    ValueType solVal = 0;
    ValueType aVal("4567316637081665907977181518889182113445441987446007457733573698022127469439135656733423482251931597580003871195410610463070846363265764446085651841441485");
    ValueType bVal("13261683723811565199480160483723583184154281997005060032137595421236239575828461774398757507049515905188090075911486594228158952115852574793046073896571395");
    ValueType pVal("20992321342930071437617535054294082600409305694823917901103517516849439468932230646876254462856426279068085286595868000559162159946064999915305764788212947");
    const auto startTime = std::chrono::steady_clock::now();
    std::cout<<"Baby step (generating powData)..."<<std::endl;
    const auto powData = generatePowData<ValueType>(aVal, pVal, powDataSize);
    std::cout<<"Baby step runtime: "<<toDurationStr(startTime)<<std::endl;
    std::cout<<"Giant step (finding collision)..."<<std::endl;
    findLogMulti(aVal, bVal, pVal, powData, hasSolution, solVal);
    std::cout<<"total runtime: "<<toDurationStr(startTime)<<std::endl;
    if(hasSolution)
    {
        std::cout<<"Solution: "<<solVal<<std::endl;
        auto checkVal = binPowMod(aVal, solVal, pVal);
        if(checkVal != bVal)
        {
            std::cout<<"error!";
        }
    }
    else
    {
        std::cout<<"no solution!";
    }
}


int main()
{
    using namespace boost::multiprecision;
    //solveBrillPuzzle<cpp_int, 32ULL*1024ULL*1024ULL>();
    solveBrillPuzzle<cpp_int, 1024ULL*1024ULL>();

    return 0;
}