<div dir="ltr">Errata:<div><br></div><div>In problem 2, note that p is a large prime number, probably around 2048 bits.  Solving problem 2 for p = 31 does not count.</div><div><br></div><div>Are there any other goobers in my problem statements?<br><div><br></div><div><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Apr 23, 2016 at 3:30 AM, Bill Cox <span dir="ltr"><<a href="mailto:waywardgeek@gmail.com" target="_blank">waywardgeek@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Puzzle 1:</div><div><br></div><div>Can you find the backdoor in this ECC addition law?</div><div><br></div><div>    x3 = x1y1y2x2/(y1y2 - x1x2)</div><div>    y3 = x1y1y2x2/(x1y2 + y1x2)</div><div><br></div><div>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.</div><div><br></div><div><br></div><div>Puzzle 2:</div><div><br></div><div>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.</div><div><br></div><div><br></div><div>Puzzle 3:</div><div><br></div><div>Find functions X(x, y) and Y(x, y) such that:</div><div><br></div><div><div>  X(x, y)^2 - Y(x, y)^2 = X((x^2 - y^2)/(2 - x^2 - y^2), 2xy/(x^2 + y^2))</div><div>  2X(x, y)Y(x, y) = Y(x^2 - y^2)/(2 - x^2 - y^2), 2xy/(x^2 + y^2))</div></div><div><br></div><div>You can use addition, multiplication, subtraction, division, n-th roots, raising to n-th power, and any other modular arithmetic friendly buttons on your HP-41c calculator.  Avoid sin, cos, factorial, and other functions that we do not know how to efficiently compute mod p, where p is 256-bit prime number.<br></div><div><br></div><div>If you succeed, then you have implemented a crucial step in breaking elliptic curve crypto.  The MiB will almost certainly want to chat.</div><div><br></div><div><br></div><div>Have fun!</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>Bill</div></font></span></div>
</blockquote></div><br></div>