[Cryptography] Fun crypto puzzles, one easy, two impossible

[Bill Cox]

Answer to 1st one and explanation of other 2 below.

On Sat, Apr 23, 2016 at 3:30 AM, Bill Cox <waywardgeek at gmail.com> wrote:

Puzzle 1:

Can you find the backdoor in this ECC addition law?

   x3 = x1y1y2x2/(y1y2 - x1x2)

   y3 = x1y1y2x2/(x1y2 + y1x2)

I attached a simple Python program that does Diffie-Hellman key agreement
using this.  If you publish a public key using this, I can reveal your
secret for short keys, say < 300 bits, because this group is equivalent to
regular DLP.

Let's attack this cryptosystem and break it.  This formula should look
familiar.  Here's the Edwards curve equation used in curve25519 (modified
to go counter-clockwise from (1, 0), like all the rest of our mathematics):

   x3 = (x1x2 - y1y2)/(1 - d*x1y1x2y2)

   y3 = (x1y2 + x2y1)/(1 + d*x1y1x2y2)

Breaking the Edwards curve equation appears very hard, but the same attacks
can be used against both sets of equations.  Let's attack the first set.

Both of these equations look similar to the circle group addition law:

   x3 = x1x2 - y1y2

   y3 = x1y2 + x2y1

The circle group is well known to be equivalent to regular DLP.  In
particular, the position of m*G, where m is a scalar and G is the generator
point, is simply:

   P = G^m mod p

where G is represented as a complex number x + i*y rather than as a point
(x, y).  This is simply DLP when using complex variables, which has been
shown to be equivalent to regular DLP in complexity.

Here's the attack: Let's see if there is any variable substitution that can
convert the circle-group-like addition laws into the regular circle-group
addition laws.  To simplify our attack, let's focus on the point doubling
equations.  If we find a substitution that turns one point doubling
equation into another, it will likely also work for the addition
equations.  The point doubling equations are:

Circle doubling:

   x2 = x^2 - y^2

   y2 = 2xy

Puzzle doubling:

   x2 = x^2y^2/(y^2 - x^2)

   y2 = x^2y^2/(2xy) = xy/2

Edwards doubling:

   x2 = (x^2 - y^2)/(1 - d*x^2y^2)

   y2 = 2xy/(1 + d*x^2y^2)

To convert one set of doubling equations into another, we can try a
variable substitution.  That’s where we find a function F(x, y) = (X(x, y),
Y(x, y)) which is invertible at least a significant fraction of the time.
We use F to modify the doubling equation for the circle group like this:

   x2 = Xinv(X(x, y)^2 - Y(x, y)^2, 2*X(x, y)*Y(x, y))

   y2 = Yinv(X(x, y)^2 - Y(x, y)^2, 2*X(x, y)*Y(x, y))

If we assume that X is a function of only x, and Y is a function of only y,
then this simplifies to:

   x2 = Xinv(X(x)^2 - Y(y)^2))

   Y2 = Yinv(2*X(x)^Y(y))

For example, we can let X(x) = x^2, and Y(y) = y^2.  This leads to:

   x2 = sqrt((x^2)^2 - (y^2)^2) = sqrt(x^4 - y^4)

   y2 = sqrt(2*(x^2)*(y^2)) = xy*sqrt(2)

These are perfectly valid addition equations, which create a group that is
trivially isomorphic to the circle group, which is why we don’t bother to
do this to in real cryptosystems.

To convert the puzzle doubling to regular circle doubling, we need the
equations to satisfy:

   x^2 - y^2 = Xinv(X(x, y)^2*Y(x, y)^2/(Y(x, y)^2 - X(x, y)^2), X(x,
y)*Y(x, y)/2)

   2xy = Yinv(X(x, y)^2*Y(x, y)^2/(Y(x, y)^2 - X(x, y)^2), X(x, y)*Y(x,
y)/2)

Assuming X depends only on x, and Y depends only on y (a poor assumption
generally), then we need:

   x^2 - y^2 = Xinv(X(x)^2*Y(y)^2/(Y(y)^2 - X(x)^2))

   2xy = Yinv(X(x)*Y(y)/2)


For example, letting X(x) = x and Y(x) = y is close.  The second equation
becomes xy/2, only off by a factor of 4, which can be fixed by letting X(x)
= 4x, but then the first equation is not satisfied.

What else can we try?  From the 2xy equation, it looks like equations where
Y x*y) = Y(x)*Y(y) are promising.  What variable substitutions have this
property?  It turns out that F(x*y) = F(x)*F(y) when F(x) = x^n:

   F(x*y) =(x*y)^n = x^n*y^n = F(x)*F(y)

To solve this puzzle, it is enough to try a few values of n.  In
particular, if we use X(x) = 1/x and Y(y) = 1/y, we get:

   Yinv(X(x)*Y(y)/2) = 1/((1/x)*(1/y)/2) = 2xy

which is what we want, so it’s worth checking the other equation:

   Xinv(X(x)^2*Y(y)^2/(Y(y)^2 - X(x)^2)) = 1/((1/x)^2*(1/y)^2/((1/y)^2 -
(1/x)^2))

       = ((1/y)^2 - (1/x)^2))/((1/x)^2*(1/y)^2)

       = x^2 - y^2

which is also what we want.

So, the puzzle is simply the circle group morphed with the variable
substitution X = 1/x and Y = 1/y.  Applying this technique to attack
Edwards curves is actually Puzzle 3.  Good luck :)


Puzzle 2:

You are given a prime p and as many digits of 1/p as you want, starting at
digit n.  Find n.  If you can do this, you have solved the discrete log
problem, and the MiB (Men in Black) have a ton of data in Utah they would
like you to help decrypt.

I should have made it clear that someone else gives you digits starting at
digit n without telling you what the value of n is.  Anyway, this is simply
a restatement of the discrete log problem.  If you solve it, it would be
huge.

The conversion is simple.  The DLP problem is typically stated as finding
n, given 2^n mod p, where p is a large prime.  Other generators than 2 can
be used, but it does not matter, so let’s use 2.  Imaging we compute this
sequence, all mod p:

   2^1, 2^2, 2^3, 2^4, …, 2^(p-1)

Let's print a binary number between 0 and 1. Start by printing “.”.  To
compute the list, we multiply the prior value by 2, and if it is larger
than p, we subtract p. If we subtracted p, then print “1”.  Otherwise,
print “0”.  The resulting string is the binary representation of 1/p.  If
we were able to find a matching subsequence in the digits of 1/p, given at
least log2(p) digits, then we would find n, solving the DLP problem.
Again, good luck :)


Puzzle 3:

Find functions X(x, y) and Y(x, y) such that:

 X(x, y)^2 - Y(x, y)^2 = X((x^2 - y^2)/(2 - x^2 - y^2), 2xy/(x^2 + y^2))

 2X(x, y)Y(x, y) = Y(x^2 - y^2)/(2 - x^2 - y^2), 2xy/(x^2 + y^2))

See the description of puzzle 1.  Note that I did not assume X and Y depend
on only x and y as I did in puzzle 1.  This form covers all possible
variable substitutions.  Does a solution exist?  Yes! Mathematically, we
know we can map Edwards curve ECC groups onto the circle group with a
continuous differentiable function in such a way that every point in the
Edwards curve group land directly on top of corresponding points in the
circle group.  However, no one knows what that function could possibly be,
and it is conjectured that we cannot compute it in any realistic time on
realistic classical computers when the group has on the order of 2^200
elements or more.

Trying to find a solution to this puzzle is leading me in some cool
directions.  I’m sure it is all well understood mathematics.  I’ll ask if
anyone can point me to the relevant field of mathematics in another post.
So far I have only found out about the study of equivalence classes of
functions given “birational” variable substitutions. It has to do with
"algebraic varieties" and a lot of Jacobi's work, which I have not yet
read.  However, it looks like Jacobi's results are enough to solve puzzle 1
without having to guess X(x) = 1/x and Y(y) = 1/y like I did above.
Instead, we simply guess that the substitution has the form P(x, y)/Q(x,
y), where P and Q are polynomials.  However, birational mappings do not
cover all possible variable substitutions. For example, I can create a
simple group equivalent to the circle group using X(x) = sqrt(x + y), and
Y(x) = y, which is not birational.


Have we proven that no birational substitution can convert an Edwards group
into the circle group? I have not seen how to solve this problem for more
general substitutions.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160430/c20479c6/attachment.html>