<div dir="ltr"><div class="gmail_extra"><span id="docs-internal-guid-c2bf5cdf-66b3-03fa-9cb3-b6059d93cbf3"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap">Answer to 1st one and explanation of other 2 below.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">On Sat, Apr 23, 2016 at 3:30 AM, Bill Cox <</span><span style="font-size:14.6667px;font-family:Arial;color:rgb(17,85,204);vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><a href="mailto:waywardgeek@gmail.com">waywardgeek@gmail.com</a></span><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">> wrote:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Puzzle 1:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Can you find the backdoor in this ECC addition law?</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x3 = x1y1y2x2/(y1y2 - x1x2)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    y3 = x1y1y2x2/(x1y2 + y1x2)</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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):</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x3 = (x1x2 - y1y2)/(1 - d*x1y1x2y2)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    y3 = (x1y2 + x2y1)/(1 + d*x1y1x2y2)</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Both of these equations look similar to the circle group addition law:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x3 = x1x2 - y1y2</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    y3 = x1y2 + x2y1</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    P = G^m mod p</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Circle doubling:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x2 = x^2 - y^2</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    y2 = 2xy</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Puzzle doubling:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x2 = x^2y^2/(y^2 - x^2)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    y2 = x^2y^2/(2xy) = xy/2</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Edwards doubling:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x2 = (x^2 - y^2)/(1 - d*x^2y^2)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    y2 = 2xy/(1 + d*x^2y^2)</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x2 = Xinv(X(x, y)^2 - Y(x, y)^2, 2*X(x, y)*Y(x, y))</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    y2 = Yinv(X(x, y)^2 - Y(x, y)^2, 2*X(x, y)*Y(x, y))</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">If we assume that X is a function of only x, and Y is a function of only y, then this simplifies to:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x2 = Xinv(X(x)^2 - Y(y)^2))</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    Y2 = Yinv(2*X(x)^Y(y))</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">For example, we can let X(x) = x^2, and Y(y) = y^2.  This leads to:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x2 = sqrt((x^2)^2 - (y^2)^2) = sqrt(x^4 - y^4)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    y2 = sqrt(2*(x^2)*(y^2)) = xy*sqrt(2)</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">To convert the puzzle doubling to regular circle doubling, we need the equations to satisfy:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    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)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    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)</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Assuming X depends only on x, and Y depends only on y (a poor assumption generally), then we need:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    x^2 - y^2 = Xinv(X(x)^2*Y(y)^2/(Y(y)^2 - X(x)^2))</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    2xy = Yinv(X(x)*Y(y)/2)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    F(x*y) =(x*y)^n = x^n*y^n = F(x)*F(y)</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    Yinv(X(x)*Y(y)/2) = 1/((1/x)*(1/y)/2) = 2xy</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">which is what we want, so it’s worth checking the other equation:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    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))</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">        = ((1/y)^2 - (1/x)^2))/((1/x)^2*(1/y)^2)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">        = x^2 - y^2</span></p><div class="gmail_extra"><br></div><div class="gmail_extra">which is also what we want.</div><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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 :)</span></p><br><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Puzzle 2:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">    2^1, 2^2, 2^3, 2^4, …, 2^(p-1)</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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 :)</span></p><br><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Puzzle 3:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Find functions X(x, y) and Y(x, y) such that:</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">  X(x, y)^2 - Y(x, y)^2 = X((x^2 - y^2)/(2 - x^2 - y^2), 2xy/(x^2 + y^2))</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:4pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">  2X(x, y)Y(x, y) = Y(x^2 - y^2)/(2 - x^2 - y^2), 2xy/(x^2 + y^2))</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Bill</span></p><div><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><br></span></div></span></div></div>