c58.py

"""

// ------------------------------------------------------------

58. Pollard's Method for Catching Kangaroos

The last problem was a little contrived. It only worked because I
helpfully foisted those broken group parameters on Alice and
Bob. While real-world groups may include some small subgroups, it's
improbable to find this many in a randomly generated group.

So what if we can only recover some fraction of the Bob's secret key?
It feels like there should be some way to use that knowledge to
recover the rest. And there is: Pollard's kangaroo algorithm.

This is a generic attack for computing a discrete logarithm (or
"index") known to lie within a certain contiguous range [a, b]. It has
a work factor approximately the square root of the size of the range.

The basic strategy is to try to find a collision between two
pseudorandom sequences of elements. One will start from an element of
known index, and the other will start from the element y whose index
we want to find.

It's important to understand how these sequences are
generated. Basically, we just define some function f mapping group
elements (like the generator g, or a public key y) to scalars (a
secret exponent, like x), i.e.:

    f(y) = <some x>

Don't worry about how f is implemented for now. Just know that it's a
function mapping where we are (some y) to the next jump we're going to
take (some x). And it's deterministic: for a given y, it should always
return the same x.

Then we do a loop like this:

    y := y * g^f(y)

The key thing here is that the next step we take is a function whose
sole input is the current element. This means that if our two
sequences ever happen to visit the same element y, they'll proceed in
lockstep from there.

Okay, let's get a bit more specific. I mentioned we're going to
generate two sequences this way. The first is our control
sequence. This is the tame kangaroo in Pollard's example. We do
something like this:

    xT := 0
    yT := g^b

    for i in 1..N:
        xT := xT + f(yT)
        yT := yT * g^f(yT)

Recall that b is the upper bound on the index of y. So we're starting
the tame kangaroo's run at the very end of that range. Then we just
take N leaps and accumulate our total distance traveled in xT. At the
end of the loop, yT = g^(b + xT). This will be important later.

Note that this algorithm doesn't require us to build a big look-up
table a la Shanks' baby-step giant-step, so its space complexity is
constant. That's kinda neat.

Now: let's catch that wild kangaroo. We'll do a similar loop, this
time starting from y. Our hope is that at some point we'll collide
with the tame kangaroo's path. If we do, we'll eventually end up at
the same place. So on each iteration, we'll check if we're there.

    xW := 0
    yW := y

    while xW < b - a + xT:
        xW := xW + f(yW)
        yW := yW * g^f(yW)

        if yW = yT:
            return b + xT - xW

Take a moment to puzzle out the loop condition. What that relation is
checking is whether we've gone past yT and missed it. In other words,
that we didn't collide. This is a probabilistic algorithm, so it's not
guaranteed to work.

Make sure also that you understand the return statement. If you think
through how we came to the final values for yW and yT, it should be
clear that this value is the index of the input y.

There are a couple implementation details we've glossed over -
specifically the function f and the iteration count N. I do something
like this:

    f(y) = 2^(y mod k)

For some k, which you can play around with. Making k bigger will allow
you to take bigger leaps in each loop iteration.

N is then derived from f - take the mean of all possible outputs of f
and multiply it by a small constant, e.g. 4. You can make the constant
bigger to better your chances of finding a collision at the (obvious)
cost of extra computation. The reason N needs to depend on f is that f
governs the size of the jumps we can make. If the jumps are bigger, we
need a bigger runway to land on, or else we risk leaping past it.

Implement Pollard's kangaroo algorithm. Here are some (less
accommodating) group parameters:

    p = 11470374874925275658116663507232161402086650258453896274534991676898999262641581519101074740642369848233294239851519212341844337347119899874391456329785623
    q = 335062023296420808191071248367701059461
    j = 34233586850807404623475048381328686211071196701374230492615844865929237417097514638999377942356150481334217896204702
    g = 622952335333961296978159266084741085889881358738459939978290179936063635566740258555167783009058567397963466103140082647486611657350811560630587013183357

And here's a sample y:

    y = 7760073848032689505395005705677365876654629189298052775754597607446617558600394076764814236081991643094239886772481052254010323780165093955236429914607119

The index of y is in the range [0, 2^20]. Find it with the kangaroo
algorithm.

Wait, that's small enough to brute force. Here's one whose index is in
[0, 2^40]:

    y = 9388897478013399550694114614498790691034187453089355259602614074132918843899833277397448144245883225611726912025846772975325932794909655215329941809013733

Find that one, too. It might take a couple minutes.

    ~~ later ~~

Enough about kangaroos, let's get back to Bob. Suppose we know Bob's
secret key x = n mod r for some r < q. It's actually not totally
obvious how to apply this algorithm to get the rest! Because we only
have:

    x = n mod r

Which means:

    x = n + m*r

For some unknown m. This relation defines a set of values that are
spread out at intervals of r, but Pollard's kangaroo requires a
continuous range!

Actually, this isn't a big deal. Because check it out - we can just
apply the following transformations:

    x = n + m*r
    y = g^x = g^(n + m*r)
    y = g^n * g^(m*r)
    y' = y * g^-n = g^(m*r)
    g' = g^r
    y' = (g')^m

Now simply search for the index m of y' to the base element g'. Notice
that we have a rough bound for m: [0, (q-1)/r]. After you find m, you
can plug it into your existing knowledge of x to recover the rest of
the secret.

Take the above group parameters and generate a key pair for Bob. Use
your subgroup-confinement attack from the last problem to recover as
much of Bob's secret as you can. You'll be able to get a good chunk of
it, but not the whole thing. Then use the kangaroo algorithm to run
down the remaining bits.
"""