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

[Bill Cox]

Errata:

In problem 2, note that p is a large prime number, probably around 2048
bits.  Solving problem 2 for p = 31 does not count.

Are there any other goobers in my problem statements?



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.
>
>
> 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.
>
>
> 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))
>
> 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.
>
> If you succeed, then you have implemented a crucial step in breaking
> elliptic curve crypto.  The MiB will almost certainly want to chat.
>
>
> Have fun!
>
> Bill
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160423/b68cf432/attachment.html>