Skip to content

Instantly share code, notes, and snippets.

@bitraft
Forked from tarcieri/semiprivate.md
Created April 25, 2016 04:05
Show Gist options
  • Save bitraft/a9caa641820fa0f9e5e5af1531eb6404 to your computer and use it in GitHub Desktop.
Save bitraft/a9caa641820fa0f9e5e5af1531eb6404 to your computer and use it in GitHub Desktop.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment