Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Ed25519-based semi-private keys

Semiprivate Keys

Semi-private keys are an expansion of the traditional idea of asymmetric keys, which have a public/private keypair, to N keys which can each represent a different capability level. In the degenerate case, a semi-private key system has 3 different types of keys. These are, to use the Tahoe terminology:

  • writecap: can publish new ciphertexts
  • readcap: can read/authenticate ciphertexts
  • verifycap: can authenticate ciphertexts

One of the goals of Tahoe is to keep the capability tokens for each of these short. Tahoe goes to pretty extreme lengths to do this, like symmetrically encrypting an RSA key and storing it along with a file.

I definitely applaud what they've done there and also believe that short capabilities are more useful. The real goal of a semi-private key system is to produce short capability tokens which are more convenient for users to distribute (potentially in non-digital forms)

The problem is Tahoe's description of semi-private keys is intended for DSA, however I would like to implement semi-private keys for use with NaCl. NaCl uses elliptic curve cryptography, so the implementation is slightly different.

This is, as best I understand it, how to implement it in terms of NaCl:

Constants:

  • P = NaCl base point (standard group element)
  • l = Order(P)

Functions:

  • H(): SHA512 truncated to 256-bits + set/clear bits

Variables:

  • k = random Ed25519 seed
  • x = H(k)
  • Q = x*P (semiprivate key)
  • y = H(Q) mod l
  • z = x*y mod l (computed Ed25519 private scalar)
  • R = y*Q (Ed25519 public key)

Test:

assert(R == z*P)

Figure 1: Semiprivate Key Generation

NaCl Semiprivate Keys

Figure 2: Ed25519 (unmodified)

Ed25519

Credits

Semiprivate keys were originally Zooko's idea. The basic idea is described in section 6.1 of the Tahoe-LAFS paper.

SAGE code courtesy Samuel Neves

import hashlib
p = 2^255 - 19;
E = EllipticCurve(GF(p), [0,486662,0,1,0]);
P = E.lift_x(9);
l = P.order();
x = ZZ.random_element(l);
Q = x*P;
y = int(hashlib.sha512(str(Q)).hexdigest(), 16) % l;
z = x*y % l;
R = y*Q;
assert(R == z*P)
@sa2ajj

This comment has been minimized.

Copy link

sa2ajj commented Nov 1, 2014

Do you think you could provide an example using NaCl primitives?

@tarcieri

This comment has been minimized.

Copy link
Owner Author

tarcieri commented Jan 20, 2015

Unfortunately neither NaCl or libsodium provide Ed25519 scalar multiplication APIs at the moment (also the above SAGE is using Montgomery)

@tarcieri

This comment has been minimized.

Copy link
Owner Author

tarcieri commented May 29, 2015

libsodium issue here: jedisct1/libsodium#236 (comment)

@franslundberg

This comment has been minimized.

Copy link

franslundberg commented Feb 19, 2018

As mention, the Sage code seems to be the x25519 (Montgomery) curve, not the ed25519 curve. Anyone that managed to represent the ed25519 curve in Sage. Sage seems to mandate curve creation in the long Weierstrass equation. So how to represent ed25519 (Edwards curve) is certainly not obvious to me.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.