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

Bill Cox waywardgeek at gmail.com
Sat Apr 23 06:30:41 EDT 2016


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/df7803fe/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: backdoor.py
Type: text/x-python
Size: 1723 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160423/df7803fe/attachment.py>


More information about the cryptography mailing list