Saturday, December 04, 2021

[bekvhdwz] ECC signature QR code

elliptic curve cryptography (ECC) offers signatures considerably shorter than RSA or integer Diffie-Hellman.  we examine the signature size of Ed25519.  (constructing an Ed25519 collision requires 2^128 work.)

an Ed25519 signature is 64 bytes, 512 bits, or 155 digits.  this fits within a version 4 (size) QR code at ECC (error correcting code, an unfortunate collision of acronyms) level L, or version 8 at level H.  note: the QR code examples below do not encode real signatures or public keys.  instead, they merely encode digit strings with the right lengths (future post duartbli).  although QR codes can encode raw binary data, we've chosen base-10 digit strings with the same amount of information because many QR code readers don't do so well with binary data.  (imagine that radix conversion has been done.)

QR code 155 digits, level L   QR code 155 digits, level H

it's helpful to identify the public key corresponding to the signature.  rather than a key identifier (as usually done with RSA or DSA, discussed below), public keys for ECC are short enough to be included in their entirety.  Ed25519 public keys are 32 bytes, 256 bits, or 78 digits.  here are QR codes encoding a string consisting of "ED25519:", 78 digits (representing a public key), a separator ":", and 155 digits (representing a signature).  it is version 6 at ECC L, version 10 at H.  (we use colon as a separator for maximum efficiency, though it turns out not to matter.)

QR code 71 digits :ED25519: 155 digits, level L   QR code 71 digits :ED25519: 155 digits, level H

note that the payload, i.e., the message which was signed, is not included in the above examples.  given the payload and the public key, the signature can be verified in place; no additional information is required.

the problem of establishing that an included public key can be trusted is the giant open problem of PKI.  (additional information is required.)

here is a nice illustration of what Ed25519 private and public keys and signatures contain: https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/

for reference, here are possible sizes of public key identifiers in PGP (gnupg, gpg, openpgp).  all of these could be applied to Ed25519 but would require standardization.  (one attempt: RFC 7638 JSON Web Key (JWK) Thumbprint.  using SHA256 results in a 256-bit key identifier, same length as an entire Ed25519 public key.)

32-bit key ID (4 bytes, 10 digits)
64-bit key ID (8 bytes, 20 digits)
MD5 key fingerprint (128 bits, 16 bytes, 39 digits)
SHA-1 key fingerprint (160 bits, 20 bytes, 49 digits)

No comments :