Re: [Cfrg] Elliptic Curves - curve form and coordinate systems

[Rene Struik <[e-mail]>]

Hi Jakob:

This confuses different discussions:

a) use of public key in computations.
Here, Andrey Jivsov's point was that receipt of a full point (x,y) on a 
curve, rather than a compressed point or simply the x-coordinate, does 
not artificially impose a performance penalty on all implementations 
except x-coordinate-only ones (Montgomery).
b) representation of public key in white list.
Here, one can use many methods to map a public key Q to a condensed 
(perhaps, even human-recognizable) format f(Q).
This condensed format could take the form affine format curve point, 
compressed format, hash, leftmost n-octets, hash value, etc.

My own take:

Ad a):
I fully agree with Andrey Jivsov's point and think using x-coordinate 
only representations imposes a "moat" around ECC implementations, by 
imposing a levy on all implementations that, for whatever reason, may 
want to use something else than Montgomery arithmetic. {Please note that 
this levy is incurred (in the context of ECDH) during *online* 
computations.} Such fully specified points are particularly useful in 
settings, including multiple-point multiplication, combined key 
computations and signature verifications, batch computations, since may 
allow significant performance advantages in those settings.

Ad b):
This is a non-issue in representation discussions with CFRG with ECC, 
since dealing with protocol issues, not user interfaces.
Nevertheless, here is a comparison that illustrates some condensed 
representations that are possibly in a completely standardized way, 
resp. "cooked up" for user interfaces:

Comparison example:
example P-256 public key, with affine coordinates (x,y),
x-coord = 6b 17 d1 f2 e1 2c 42 47 f8 bc e6 e5 63 a4 40 f2 77 03 7d 81 2d 
eb 33 a0 f4 a1 39 45 d8 98 c2 96
y-coord = 4f e3 42 e2 fe 1a 7f 9b 8e e7 eb 4a 7c 0f 9e 16 2b ce 33 57 6b 
31 5e ce cb b6 40 68 37 bf 51 f5
a) standardized affine format: (0x04 || x-coord || y-coord) {65 octets}
b) standardized compressed format: (0x03 || x-coordinate) {33 octets}
c) non-standard, x-coordinate-only: x-coordinate {32 octets}
d) non-standard, truncated x-coordinate (x-coordinate mod 2^128): 77 03 
7d 81 2d eb 33 a0 f4 a1 39 45 d8 98 c2 96 {16 octets}

example Curve25519, Alice's public key (source: 
draft-irtf-agl-cfrgcurve-00):
x-coord = 85 20 f0 09 89 30 a7 54 74 8b 7d dc b4 3e f7 5a 0d bf 3a 0d 26 
38 1a f4 eb a4 a9 8e aa 9b 4e 6a
c) non-standard, x-coordinate-only: x-coordinate {32 octets}

On 3/13/2015 8:18 AM, Jakob Breier wrote:
> On 12.03.2015 20:19, Andrey Jivsov wrote:
>> * This proposal incurs 32 additional bytes of storage overhead for 
>> the public key, for the total of 64 bytes (compare this with 260+ 
>> bytes for RSA 2048). 
>
> The storage costs and transmission costs might be insignificant for 
> machines, but I'd like to point out the human storage and transmission 
> costs. Take a look at SSH keys for example. Compare how well you can 
> visually parse several lines of keys in an authorized_keys file in 
> these three formats:
>
> ssh-rsa 
> AAAAB3NzaC1yc2EAAAADAQABAAABAQDRTSfbRohGanse3u4gnu8wOId85f5KKyEzo/l
> MabVM4J92n6r4NPgN46pQ3bTc8XzLO5zHXY/mPSwQru3Ks+6Mcut7bDo0ohPcLcdIYGTbqXkfz3 
>
> KNDbdXwPMcaPamLmugNnj9UK2cPe8Q7F9DGSLaQc1eiC0JS/Qm0gG3ULqX3DEDFQbLBzH326Lov 
>
> 9gplu/U7D0bBiM7q7VQs32sz11L4KWY3RzUhuy6bQ7GGrkGvp78l7f+56AvQNeIV8fDOWKNE73s 
>
> Q3NybxWxQ771c5c+AZGYzkERlHWjxaxGA6V8ZUiE2VftHZMY4k6z4DC9hiadxwmr85qWriC7RrT 
>
> OjmN9 Alice-HomePc
>
> ecdsa-sha2-nistp256 
> AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBLB
> RUKndAEfMluniDolf8eJIdhh1l9C2iXKtnbvbM9vFbBMQ+l47i7wusn4G2RMYsFPbwlV4XQt4TT 
>
> sEwkrcLss= Alice-HomePc
>
> ssh-ed25519 
> AAAAC3NzaC1lZDI1NTE5AAAAICxtv8s7nwLqhkhryoY+w/u9ZrY7dr0ZPZhYuOS
> bxTIb Alice-HomePc
>
> They are in turn: RSA (2048 bit), 65 byte long nistp256 key and 32 
> byte long ed25519 key (apparently, openssh already uses point 
> compression for this format). The difference would be even more 
> pronounced, if the SSH key storage format was more efficient, but the 
> result of factor two decrease from 64 byte to 32 byte keys is still 
> significant. And these are keys that you often copy and paste as plain 
> text instead of sending pubkey files, e.g. when you add one to GitHub 
> or instant message it to a friend.
>
> Another example is TextSecure, the end-to-end encrypted messenger app, 
> that allows you to verify the 33 byte "identity" (32 byte Curve25519 
> key + 0x05 prefix) by comparing them manually as 66 hex characters (or 
> scanning a QR-code). Threema, another encrypted messenger app, also 
> directly compares the public key (32 byte Curve25519) in the QR-code. 
> (Threema does also feature a 128bit fingerprint, though, that can be 
> compared by reading it aloud.)
>
> As all three examples feature interactive protocols anyway, they could 
> use fingerprints instead, but for various reasons don't and thus 
> profit from short key sizes.
>
> An example that does not have the alternative of using fingerprints 
> are key revocation certificates. I have a few of these printed out for 
> RSA keys and I fear the day I actually have to type them in.
> Also, if we'll ever have a chance to bring strong end-to-end 
> cryptography to the masses, then we need inexperienced users to backup 
> their private key. And I trust my parents far more to securely store, 
> and later on use, a slip of paper - which means writing down and later 
> typing back in the key - than a USB stick / a memory card / a CD / …, 
> all which have to be periodically checked whether they are still 
> readable. And while this would be totally impractical with RSA keys, 
> with EC keys this becomes borderline usable. And here the difference 
> between 64 and 32 bytes is enormous.
>
> Best regards,
> Jakob Breier
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]