[cryptography] A question about public keys

Trevor Perrin trevp at trevp.net
Mon Sep 30 00:55:56 EDT 2013


On Sun, Sep 29, 2013 at 9:29 PM, Trevor Perrin <trevp at trevp.net> wrote:
> On Sun, Sep 29, 2013 at 9:27 AM, Michael Rogers
> <michael at briarproject.org> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Sorry for making so much noise on the list today. I have a quick
>> question about public keys.
>>
>> The Curve25519 paper says that "every 32-byte string is accepted as a
>> Curve25519 public key". Yet Elligator doesn't use Curve25519. So I
>> guess there must be a way to distinguish a bunch of Curve25519 public
>> keys from a bunch of random 32-byte strings. What is it?
>
> "Elligator 2" works for Curve25519, see Section 4 of the Elligator paper:

Argh, I meant Section 5.


> http://eprint.iacr.org/2013/325.pdf
>
>
> To your question:  Interpreting the 32-byte value as "x", check that
> x^3 + 486662x^2 + x mod 2^255-19 has a square root.

Phrasing this better: check that x^3 + 486662x^2 + x is a square modulo 2^255-19


Trevor


More information about the cryptography mailing list