20070910-1313

9 files changed, 453 insertions, 100 deletions

diff --git a/CHANGES b/CHANGES
index ddaa09f9..bfda5423 100644
--- a/CHANGES
+++ b/CHANGES
@@ -1,3 +1,5 @@
+20070910
+	update spki(2) [change handling of hashes, add signature functions] appl/lib/spki/spki.b module/spki.m, updated for GSoC
 20070906
 	add toreal to string(2)
 20070905
diff --git a/appl/lib/spki/spki.b b/appl/lib/spki/spki.b
index 5446b0ab..18a2d68a 100644
--- a/appl/lib/spki/spki.b
+++ b/appl/lib/spki/spki.b
@@ -7,7 +7,6 @@ implement SPKI;
 #	- diagnostics
 #	- support for dsa
 #	- finish the TO DO
-#	- might like a list of ref Hash for a Key
 
 include "sys.m";
 	sys: Sys;
@@ -331,7 +330,7 @@ parseprincipal(e: ref Sexp): ref Key
 		hash := parsehash(e);
 		if(hash == nil)
 			return nil;
-		return ref Key(nil, nil, 0, hash.alg, hash);
+		return ref Key(nil, nil, 0, nil, nil, hash::nil);
 	* =>
 		return nil;
 	}
@@ -354,9 +353,9 @@ parsekey(e: ref Sexp): ref Key
 	alg := hd fld;
 	if(nf > 1)
 		enc := hd tl fld;		# signature hash encoding
+	mha := "sha1";
 	if(nf > 2)
-		mha := hd tl tl fld;	# signature hash algorithm
-	kha := "md5";	# could be sha1 (TO DO)
+		mha = hd tl tl fld;	# signature hash algorithm
 	kl := (hd l).args();
 	if(kl == nil)
 		return nil;
@@ -386,8 +385,8 @@ parsekey(e: ref Sexp): ref Key
 			return nil;
 		}
 	}
-#(ref Key(pk,nil,kha,nil)).hashed(kha);		# TEST
-	return ref Key(pk, sk, nbits, kha, ref Hash(kha, nil));
+#(ref Key(pk,nil,"md5",nil,nil)).hashed("md5");		# TEST
+	return ref Key(pk, sk, nbits, mha, enc, nil);
 }
 
 parsehash(e: ref Sexp): ref Hash
@@ -437,6 +436,49 @@ ckdate(s: string): string
 	return s;
 }
 
+Toplev.sexp(top: self ref Toplev): ref Sexp
+{
+	pick t := top {
+	C =>
+		return t.v.sexp();
+	Sig =>
+		return t.v.sexp();
+	K =>
+		return t.v.sexp();
+	Seq =>
+		rels := rev(t.v);
+		els: list of ref Sexp;
+		for(; rels != nil; rels = tl rels)
+			els = (hd rels).sexp() :: els;
+		return ref Sexp.List(ref Sexp.String("sequence", nil) :: els);
+	* =>
+		raise "unexpected spki type";
+	}
+}
+
+Toplev.text(top: self ref Toplev): string
+{
+	return top.sexp().text();
+}
+
+Seqel.sexp(se: self ref Seqel): ref Sexp
+{
+	pick r := se {
+	C =>
+		return r.c.sexp();
+	K =>
+		return r.k.sexp();
+	O =>
+		return ref Sexp.List(ref Sexp.String("do",nil) :: ref Sexp.String(r.op,nil) :: r.args);
+	S =>
+		return r.sig.sexp();
+	E =>
+		return r.exp;
+	* =>
+		raise "unsupported value";
+	}
+}
+
 Seqel.text(se: self ref Seqel): string
 {
 	pick r := se {
@@ -445,14 +487,13 @@ Seqel.text(se: self ref Seqel): string
 	K =>
 		return r.k.text();
 	O =>
-		e := ref Sexp.List(ref Sexp.String("do",nil) :: ref Sexp.String(r.op,nil) :: r.args);
-		return e.text();
+		return se.sexp().text();
 	S =>
 		return r.sig.text();
 	E =>
 		return r.exp.text();
 	* =>
-		return "unsupported";
+		raise "unsupported value";
 	}
 }
 
@@ -513,22 +554,25 @@ checksig(c: ref Cert, sig: ref Signature): string
 		return "missing signature value";
 	pk := sig.key.pk;
 	if(pk == nil)
-		return "missing Keyring->PK for signature";	# TO DO
+		return "missing Keyring->PK for signature";	# TO DO (need a way to tell that key was just a hash)
 #rsacomp((hd sig.sig).t1, sig.key);
 #sys->print("nbits= %d\n", sig.key.nbits);
 	(alg, enc, hashalg) := sig.algs();
 	if(alg == nil)
 		return "unspecified signature algorithm";
 	if(hashalg == nil)
-		hashalg = "md5";	# TO DO
+		hashalg = "md5";	# TO DO?
+	hash := hashbytes(c.e.pack(), hashalg);
+	if(hash == nil)
+		return "unknown hash algorithm "+hashalg;
 	if(enc == nil)
-		h := hashbytes(c.e.pack(), hashalg);
+		h := hash;
 	else if(enc == "pkcs" || enc == "pkcs1")
-		h = pkcs1_encode(hashalg, c.e.pack(), (sig.key.nbits+7)/8);
+		h = pkcs1_encode(hashalg, hash, (sig.key.nbits+7)/8);
 	else
 		return "unknown encoding algorithm "+enc;
-	if(h == nil)
-		return "unknown hash algorithm "+hashalg;
+#dump("check/hashed", hash);
+#dump("check/h", h);
 	ip := IPint.bebytestoip(h);
 	isig := sig2icert(sig, "sdsi", 0);
 	if(isig == nil)
@@ -538,14 +582,62 @@ checksig(c: ref Cert, sig: ref Signature): string
 	return nil;
 }
 
+signcert(c: ref Cert, sigalg: string, key: ref Key): (ref Signature, string)
+{
+	if(c.e == nil){
+		c.e = c.sexp();
+		if(c.e == nil)
+			return (nil, "bad input certificate");
+	}
+	return signbytes(c.e.pack(), sigalg, key);
+}
+
+#
+# might be useful to have a separate `signhash' for cases where the data was hashed elsewhere
+#
+signbytes(data: array of byte, sigalg: string, key: ref Key): (ref Signature, string)
+{
+	if(key.sk == nil)
+		return (nil, "missing Keyring->SK for signature");
+	pubkey := ref *key;
+	pubkey.sk = nil;
+	sig := ref Signature(nil, pubkey, sigalg, nil);	# ref Hash, key, alg, sig: list of (string, array of byte)
+	(alg, enc, hashalg) := sigalgs(sigalg);
+	if(alg == nil)
+		return (nil, "unspecified signature algorithm");
+	if(hashalg == nil)
+		hashalg = "md5";	# TO DO?
+	hash := hashbytes(data, hashalg);
+	if(hash == nil)
+		return (nil, "unknown hash algorithm "+hashalg);
+	if(enc == nil)
+		h := hash;
+	else if(enc == "pkcs" || enc == "pkcs1")
+		h = pkcs1_encode(hashalg, hash, (sig.key.nbits+7)/8);
+	else
+		return (nil, "unknown encoding algorithm "+enc);
+#dump("sign/hashed", hash);
+#dump("sign/h", h);
+	sig.hash = ref Hash(hashalg, hash);
+	ip := IPint.bebytestoip(h);
+	icert := kr->signm(key.sk, ip, hashalg);
+	if(icert == nil)
+		return (nil, "signature failed");	# can't happen?
+	(nil, nil, nil, vals) := icert2els(icert);
+	if(vals == nil)
+		return (nil, "couldn't extract values from Keyring Certificate");
+	l: list of (string, array of byte);
+	for(; vals != nil; vals = tl vals){
+		(n, v) := hd vals;
+		l = (f2s(n), v) :: l;
+	}
+	sig.sig = revt(l);
+	return (sig, nil);
+}
+
 hashexp(e: ref Sexp, alg: string): array of byte
 {
-	a := e.pack();
-#dump("inp a", a);
-	hash := hashbytes(a, alg);
-#dump(alg, hash);
-#sys->print("%s = |%s|\n", alg, base64->enc(hash));
-	return hash;
+	return hashbytes(e.pack(), alg);
 }
 
 hashbytes(a: array of byte, alg: string): array of byte
@@ -559,11 +651,12 @@ hashbytes(a: array of byte, alg: string): array of byte
 		hash = array[Keyring->SHA1dlen] of byte;
 		kr->sha1(a, len a, hash, nil);
 	* =>
-		return nil;
+		raise "Spki->hashbytes: unknown algorithm: "+alg;
 	}
 	return hash;
 }
 
+# trim mpint and add leading zero byte if needed to ensure value is unsigned
 pre0(a: array of byte): array of byte
 {
 	for(i:=0; i<len a-1; i++)
@@ -589,7 +682,13 @@ dump(s: string, a: array of byte)
 
 Signature.algs(sg: self ref Signature): (string, string, string)
 {
-	(nf, flds) := sys->tokenize(sg.sa, "-");
+	return sigalgs(sg.sa);
+}
+
+# sig[-[enc-]hash]
+sigalgs(alg: string): (string, string, string)
+{
+	(nf, flds) := sys->tokenize(alg, "-");
 	if(nf >= 3)
 		return (hd flds, hd tl flds, hd tl tl flds);
 	if(nf >= 2)
@@ -613,7 +712,7 @@ Signature.sexp(sg: self ref Signature): ref Sexp
 		}
 		sv = ref Sexp.List(rev(l));
 	}else
-		sv = ref Sexp.Binary((hd sg.sig).t1, nil);
+		sv = ref Sexp.Binary((hd sg.sig).t1, nil);	# no list if signature has one component
 	if(sg.sa != nil)
 		sv = ref Sexp.List(ref Sexp.String(sg.sa,nil) :: sv :: nil);
 	return ref Sexp.List(ref Sexp.String("signature",nil) :: sg.hash.sexp() :: sg.key.sexp() ::
@@ -706,6 +805,8 @@ Cert.sexp(c: self ref Cert): ref Sexp
 {
 	if(c == nil)
 		return nil;
+	if(c.e != nil)
+		return c.e;
 	ds, tag: ref Sexp;
 	pick d := c {
 	N =>
@@ -733,8 +834,12 @@ Subject.principal(s: self ref Subject): ref Key
 		return r.key;
 	N =>
 		return r.name.principal;
+	KH =>
+		return r.holder.principal;
+	O =>
+		return nil;	# TO DO: need cache of hashed keys
 	* =>
-		return nil;	# TO DO
+		return nil;	# TO DO? (no particular principal for threshold)
 	}
 }
 
@@ -897,45 +1002,64 @@ Name.eq(a: self ref Name, b: ref Name): int
 	return nb == nil;
 }
 
-Key.hashed(key: self ref Key, alg: string): array of byte
+Key.public(key: self ref Key): ref Key
 {
-	if(key.hash != nil && key.halg == alg && key.hash.hash != nil)
-		return key.hash.hash;
-	krp := Keyrep.pk(key.pk);
-	if(krp == nil)
+	if(key.sk != nil){
+		pk := ref *key;
+		if(pk.pk == nil)
+			pk.pk = kr->sktopk(pk.sk);
+		pk.sk = nil;
+		return pk;
+	}
+	if(key.pk == nil)
 		return nil;
-	n := krp.getb("n");
-	e := krp.getb("e");
-	if(n == nil || e == nil)
+	return key;
+}
+
+Key.ishash(k: self ref Key): int
+{
+	return k.hash != nil && k.sk == nil && k.pk == nil;
+}
+
+Key.hashed(key: self ref Key, alg: string): array of byte
+{
+	e := key.sexp();
+	if(e == nil)
 		return nil;
-	ex := ref Sexp.List(
-			ref Sexp.String("public-key", nil) ::
-			ref Sexp.List(
-				ref Sexp.String("rsa-pkcs1-"+alg, nil) ::
-				ref Sexp.List(ref Sexp.String("e", nil) :: ref Sexp.Binary(e, nil) :: nil) ::
-				ref Sexp.List(ref Sexp.String("n", nil) :: ref Sexp.Binary(n, nil) :: nil)
-				:: nil)
-			:: nil);
-#	sys->print("=> %q %s\n", hd tl tl flds, ex.text());
-	hash := hashexp(ex, alg);
-	if((key.hash == nil || key.hash.hash == nil) && (key.halg == alg || key.halg == nil)){
-		key.halg = alg;
-		key.hash = ref Hash(alg, hash);
+	return hashexp(key.sexp(), alg);
+}
+
+Key.hashexp(key: self ref Key, alg: string): ref Hash
+{
+	if(key.hash != nil){
+		for(l := key.hash; l != nil; l = tl l){
+			h := hd l;
+			if(h.alg == alg && h.hash != nil)
+				return h;
+		}
 	}
-	return hash;
+	hash := key.hashed(alg);
+	if(hash == nil)
+		return nil;
+	h := ref Hash(alg, hash);
+	key.hash = h :: key.hash;
+	return h;
 }
 
 Key.sigalg(k: self ref Key): string
 {
-	if(k.pk == nil || k.pk.sa == nil)
+	if(k.pk != nil)
+		alg := k.pk.sa.name;
+	else if(k.sk != nil)
+		alg = k.sk.sa.name;
+	else
 		return nil;
-	halg := "";
-	if(k.halg != nil)
-		halg = "-"+k.halg;
-	n := k.pk.sa.name;
-	if(n == "rsa" || n == "dsa")
-		return n+"-pkcs1"+halg;
-	return n+halg;
+	if(k.halg != nil){
+		if(k.henc != nil)
+			alg += "-"+k.henc;
+		alg += "-"+k.halg;
+	}
+	return alg;
 }
 
 Key.text(k: self ref Key): string
@@ -948,8 +1072,11 @@ Key.text(k: self ref Key): string
 
 Key.sexp(k: self ref Key): ref Sexp
 {
-	if(k.hash != nil && k.hash.hash != nil)
-		return k.hash.sexp();
+	if(k.sk == nil && k.pk == nil){
+		if(k.hash != nil)
+			return (hd k.hash).sexp();
+		return nil;
+	}
 	sort := "public-key";
 	els: list of (string, ref IPint);
 	if(k.sk != nil){
@@ -980,8 +1107,14 @@ Key.eq(k1: self ref Key, k2: ref Key): int
 		return 1;
 	if(k1 == nil || k2 == nil)
 		return 0;
-	if(k1.hash != nil && k2.hash != nil && k1.hash.eq(k2.hash))
-		return 1;
+	for(hl1 := k1.hash; hl1 != nil; hl1 = tl hl1){
+		h1 := hd hl1;
+		for(hl2 := k2.hash; hl2 != nil; hl2 = tl hl2){
+			h2 := hd hl2;
+			if(h1.hash != nil && h1.eq(h2))
+				return 1;
+		}
+	}
 	if(k1.pk != nil && k2.pk != nil)
 		return kr->pktostr(k1.pk) == kr->pktostr(k2.pk);	# TO DO
 	return 0;
@@ -1000,11 +1133,13 @@ dec(s: string, i: int, l: int): (int, int)
 	return (n, l);
 }
 
-# TO DO: any valid prefix of a date
-
+# accepts at least any valid prefix of a date
 date2epoch(t: string): int
 {
-	if(len t != 19)
+	# yyyy-mm-dd_hh:mm:ss
+	if(len t >= 4 && len t < 19)
+		t += "-01-01_00:00:00"[len t-4:];	# extend non-standard short forms
+	else if(len t != 19)
 		return -1;
 	tm := ref Daytime->Tm;
 	i: int;
@@ -1043,7 +1178,10 @@ epoch2date(t: int): string
 
 time2secs(s: string): int
 {
-	if(len s != 8)	# HH:MM:SS
+	# HH:MM:SS
+	if(len s >= 2 && len s < 8)
+		s += ":00:00"[len s-2:];	# extend non-standard short forms
+	else if(len s != 8)
 		return -1;
 	hh, mm, ss, i: int;
 	(hh, i) = dec(s, 0, 2);
@@ -1903,7 +2041,8 @@ revt[S,T](l: list of (S,T)): list of (S,T)
 }
 
 #
-# the following should probably be in a separate Limbo library module
+# the following should probably be in a separate Limbo library module,
+# or provided in some way directly by Keyring
 #
 
 Keyrep: adt {
@@ -1953,7 +2092,7 @@ Keyrep.pk(pk: ref Keyring->PK): ref Keyrep.PK
 	case hd flds {
 	"rsa" =>
 		return ref Keyrep.PK(hd flds, hd tl flds,
-			keyextract(tl tl flds, list of {("e",1), ("n",0)}));
+			keyextract(tl tl flds, list of {("ek",1), ("n",0)}));
 	"elgamal" or "dsa" =>
 		return ref Keyrep.PK(hd flds, hd tl flds,
 			keyextract(tl tl flds, list of {("p",0), ("alpha",1), ("key",2)}));
@@ -1968,10 +2107,11 @@ Keyrep.sk(pk: ref Keyring->SK): ref Keyrep.SK
 	(nf, flds) := sys->tokenize(s, "\n");
 	if((nf -= 2) < 0)
 		return nil;
+	# the ordering of components below should match the one defined in the spki spec
 	case hd flds {
 	"rsa" =>
 		return ref Keyrep.SK(hd flds, hd tl flds,
-			keyextract(tl tl flds,list of {("e",1), ("n",0), ("!dk",2), ("!p",3), ("!q",4), ("!kp",5), ("!kq",6), ("!c2",7)}));
+			keyextract(tl tl flds,list of {("ek",1), ("n",0), ("!dk",2), ("!q",4), ("!p",3), ("!kq",6), ("!kp",5), ("!c2",7)}));	# see comment elsewhere about p, q
 	"elgamal" or "dsa" =>
 		return ref Keyrep.SK(hd flds, hd tl flds,
 			keyextract(tl tl flds, list of {("p",0), ("alpha",1), ("key",2), ("!secret",3)}));
@@ -2001,7 +2141,7 @@ Keyrep.mkpk(k: self ref Keyrep): (ref Keyring->PK, int)
 {
 	case k.alg {
 	"rsa" =>
-		e := k.get("e");
+		e := k.get("ek");
 		n := k.get("n");
 		if(e == nil || n == nil)
 			return (nil, 0);
@@ -2015,7 +2155,7 @@ Keyrep.mksk(k: self ref Keyrep): ref Keyring->SK
 {
 	case k.alg {
 	"rsa" =>
-		e := k.get("e");
+		e := k.get("ek");
 		n := k.get("n");
 		dk := k.get("!dk");
 		p := k.get("!p");
@@ -2040,11 +2180,12 @@ Keyrep.mksk(k: self ref Keyrep): ref Keyring->SK
 s2f(s: string): string
 {
 	case s {
+	"e" => return "ek";
 	"d" => return "!dk";
-	"p" => return "!p";
-	"q" => return "!q";
-	"a" => return "!kp";
-	"b" => return "!kq";
+	"p" => return "!q";		# NB: p and q (kp and kq) roles are reversed between libsec and pkcs
+	"q" => return "!p";
+	"a" => return "!kq";
+	"b" => return "!kp";
 	"c" => return "!c2";
 	* =>	return s;
 	}
@@ -2053,9 +2194,12 @@ s2f(s: string): string
 f2s(s: string): string
 {
 	case s {
+	"ek" =>	return "e";
+	"!p" =>	return "q";	# see above
+	"!q" =>	return "p";
 	"!dk" =>	return "d";
-	"!kp" =>	return "a";
-	"!kq" =>	return "b";
+	"!kp" =>	return "b";
+	"!kq" =>	return "a";
 	"!c2" =>	return "c";
 	* =>
 		if(s != nil && s[0] == '!')
@@ -2088,6 +2232,36 @@ sig2icert(sig: ref Signature, signer: string, exp: int): ref Keyring->Certificat
 	return kr->strtocert(s);
 }
 
+icert2els(cert: ref Keyring->Certificate): (string, string, string, list of (string, array of byte))
+{
+	s := kr->certtoattr(cert);
+	if(s == nil)
+		return (nil, nil, nil, nil);
+	(nil, l) := sys->tokenize(s, " ");	# really need parseattr, and a better interface
+	vals: list of (string, array of byte);
+	alg, hashalg, signer: string;
+	for(; l != nil; l = tl l){
+		(nf, fld) := sys->tokenize(hd l, "=");
+		if(nf != 2)
+			continue;
+		case hd fld {
+		"sigalg" =>
+			(nf, fld) = sys->tokenize(hd tl fld, "-");
+			if(nf != 2)
+				continue;
+			alg = hd fld;
+			hashalg = hd tl fld;
+		"signer" =>
+			signer = hd tl fld;
+		"expires" =>
+			;	# don't care
+		* =>
+			vals = (hd fld, base16->dec(hd tl fld)) :: vals;
+		}
+	}
+	return (alg, hashalg, signer, revt(vals));
+}
+
 #
 # pkcs1 asn.1 DER encodings
 #
@@ -2121,20 +2295,15 @@ pkcs1_sha1_pfx := array[] of {
 #
 # mlen should be key length in bytes
 #
-pkcs1_encode(ha: string, msg: array of byte, mlen: int): array of byte
+pkcs1_encode(ha: string, hash: array of byte, mlen: int): array of byte
 {
 	# apply hash function to message
-	hash: array of byte;
 	prefix: array of byte;
 	case ha {
 	"md5" =>
 		prefix = pkcs1_md5_pfx;
-		hash = array[Keyring->MD5dlen] of byte;
-		kr->md5(msg, len msg, hash, nil);
 	"sha" or "sha1" =>
 		prefix = pkcs1_sha1_pfx;
-		hash = array[Keyring->SHA1dlen] of byte;
-		kr->sha1(msg, len msg, hash, nil);
 	* =>
 		return nil;
 	}
diff --git a/appl/lib/spki/verifier.b b/appl/lib/spki/verifier.b
index d712fd2a..ffcdfcad 100644
--- a/appl/lib/spki/verifier.b
+++ b/appl/lib/spki/verifier.b
@@ -50,16 +50,27 @@ putkey(keys: list of ref Key, k: ref Key): list of ref Key
 	return k :: keys;
 }
 
-keybyhash(h: ref Hash, keys: list of ref Key): ref Key
+keybyhash(hl: list of ref Hash, keys: list of ref Key): ref Key
 {
 	for(kl := keys; kl != nil; kl = tl kl){
 		k := hd kl;
-		if(k.hash != nil && h.eq(k.hash))
+		if(k.hash != nil && anyhashmatch(hl, k.hash))
 			return k;
 	}
 	return nil;
 }
 
+anyhashmatch(hl1, hl2: list of ref Hash): int
+{
+	for(; hl1 != nil; hl1 = tl hl1){
+		h1 := hd hl1;
+		for(; hl2 != nil; hl2 = tl hl2)
+			if(h1.eq(hd hl2))
+				return 1;
+	}
+	return 0;
+}
+
 verify(seq: list of ref Seqel): (ref Speaksfor, list of ref Seqel, string)
 {
 	stack: list of ref Seqel;
@@ -184,5 +195,6 @@ verify(seq: list of ref Seqel): (ref Speaksfor, list of ref Seqel, string)
 
 checkcert(c: ref Cert): string
 {
+	# TO DO?
 	return nil;
 }
diff --git a/dis/lib/spki/spki.dis b/dis/lib/spki/spki.dis
index a3c10e7f..07f9f4a8 100644
--- a/dis/lib/spki/spki.dis
+++ b/dis/lib/spki/spki.dis
diff --git a/dis/lib/spki/verifier.dis b/dis/lib/spki/verifier.dis
index e6e03b8f..daab55f7 100644
--- a/dis/lib/spki/verifier.dis
+++ b/dis/lib/spki/verifier.dis
diff --git a/include/version.h b/include/version.h
index 1ad54c03..10f771c8 100644
--- a/include/version.h
+++ b/include/version.h
@@ -1 +1 @@
-#define VERSION	"Fourth Edition (20070907)"
+#define VERSION	"Fourth Edition (20070910)"
diff --git a/man/2/spki b/man/2/spki
index dc7badb3..0c7fb884 100644
--- a/man/2/spki
+++ b/man/2/spki
@@ -21,14 +21,18 @@ Hash: adt {
 Key: adt {
     pk:     ref Keyring->PK;    # either pk/sk or hash might be nil
     sk:     ref Keyring->SK;
-    halg:   string;
-    hash:   ref Hash;
+    nbits:  int;
+    halg:   string;             # basic signature hash algorithm
+    henc:   string;             # pre-signature encoding
+    hash:   list of ref Hash;
 
-    hashed: fn(k: self ref Key, alg: string): array of byte;
-    sigalg: fn(k: self ref Key): string;
-    text:   fn(k: self ref Key): string;
-    sexp:   fn(k: self ref Key): ref Sexprs->Sexp;
-    eq:     fn(k1: self ref Key, k2: ref Key): int;
+    hashed:  fn(k: self ref Key, alg: string): array of byte;
+    hashexp: fn(k: self ref Key, alg: string): ref Hash;
+    public:  fn(k: self ref Key): ref Key;
+    sigalg:  fn(k: self ref Key): string;
+    text:    fn(k: self ref Key): string;
+    sexp:    fn(k: self ref Key): ref Sexprs->Sexp;
+    eq:      fn(k1: self ref Key, k2: ref Key): int;
 };
 
 Name: adt {
@@ -84,9 +88,10 @@ Subject: adt {
 Signature: adt {
     hash:   ref Hash;
     key:    ref Key;    # find by hash if necessary
-    sa:     string;
+    sa:     string;     # alg[-[encoding-]hash
     sig:    list of (string, array of byte);
 
+    algs:   fn(s: self ref Signature): (string, string, string);
     sexp:   fn(s: self ref Signature): ref Sexprs->Sexp;
     text:   fn(s: self ref Signature): string;
 };
@@ -106,12 +111,13 @@ Seqel: adt {
         exp:    ref Sexprs->Sexp;
     }
 
+    sexp:   fn(se: self ref Seqeql): ref Sexprs->Sexp;
     text:   fn(se: self ref Seqel): string;
 };
 
 Valid: adt {
-    notbefore:  int;
-    notafter:   int;
+    notbefore:  string;
+    notafter:   string;
 
     intersect:  fn(a: self Valid, b: Valid): (int, Valid);
     text:   fn(a: self Valid): string;
@@ -129,6 +135,9 @@ Toplev: adt {
     Seq =>
         v:  list of ref Seqel;
     }
+
+    sexp:   fn(t: self ref Toplev): ref Sexprs->Sexp;
+    text:   fn(t: self ref Toplev): string;
 };
 
 init:   fn();
@@ -136,6 +145,7 @@ date2epoch: fn(s: string): int; # YYYY-MM-DD_HH:MM:SS
 epoch2date: fn(t: int): string;
 time2secs:  fn(s: string): int; # HH:MM:SS
 secs2time:  fn(t: int): string;
+sigalgs:    fn(spec: string): (string, string, string);
 
 # parse structures
 parse:      fn(s: ref Sexprs->Sexp): (ref Toplev, string);
@@ -146,6 +156,17 @@ parsename:  fn(s: ref Sexprs->Sexp): ref Name;
 parsekey:   fn(s: ref Sexprs->Sexp): ref Key;
 parsehash:  fn(s: ref Sexprs->Sexp): ref Hash;
 parsecompound:  fn(s: ref Sexprs->Sexp): ref Name;
+parsevalid: fn(s: ref Sexprs->Sexp): ref Valid;
+
+# signature checking
+checksig:   fn(c: ref Cert, sig: ref Signature): string;
+sig2icert:  fn(sig: ref Signature, signer: string, exp: int): ref Keyring->Certificate;
+
+# signature making
+signcert:   fn(c: ref Cert, sigalg: string, key: ref Key):
+                 (ref Signature, string);
+signbytes:  fn(a: array of byte, sigalg: string, key: ref Key):
+                 (ref Signature, string);
 
 # tags
 maketag:    fn(e: ref Sexprs->Sexp): ref Sexprs->Sexp;
@@ -204,9 +225,20 @@ is the internal representation of hash values,
 containing an
 algorithm name
 .B alg
-and the 
+and then the
 .B hash
 itself as an array of bytes.
+SPKI entities such as the public key of a principal or a signed certificate are often represented by the hash
+values of their corresponding S-expressions, where the hash value is later used as a compact way to refer
+to the original entity.
+For example, a
+.B <principal>
+is either a
+.B <public-key>
+or a
+.BR <hash-of-key> ,
+where the latter refers to some instance of the former.
+Current hash algorithms are \f5"sha1"\fP and \f5"md5\fP.
 A
 .B Hash
 value can be created from an S-expression representing a SPKI
@@ -218,8 +250,12 @@ It returns nil if the S-expression was ill-formed.
 .PP
 .B Key
 represents public and private keys,
-with an optional associated hash algorithm when signing, and
-an optional hash of the key itself.
+with an optional associated pre-hash encoding
+.BR henc ,
+the hash algorithm
+.B halg
+to be used when signing, and an optional list of
+currently known hashes of the public component of the key itself.
 SPKI identifies principals and public keys, thus each instance of a principal
 in the other data structures is represented by a
 .B Key
@@ -233,6 +269,49 @@ value can be created from an S-expression representing a SPKI
 element by
 .BR parsekey .
 It returns nil if the S-expression was ill-formed.
+For a given
+.B Key
+.IR k :
+.TP
+.IB k .ishash()
+Returns true if
+.I k
+is just a hash of a key, with no public or private components.
+.TP
+.IB k .public()
+Returns the public key for
+.IR k ,
+which is simply
+.I k
+if it is already a public key, but if it
+is a private key, then a new key is returned
+that has only public components.
+.B Public
+returns a nil value if
+.I k
+is just a hash of a key value.
+.TP
+.IB k .sigalg()
+Returns the SPKI signature algorithm for the key.
+.TP
+.IB k .hashed( alg )
+Return an array of bytes giving the hash of the Key
+.I k
+using algorithm
+.IR alg .
+It returns nil if
+.IB k .ishash()
+is true, and
+.I k
+has no associated hash value for
+.IR alg .
+.TP
+.IB k .hashexp( alg )
+Similar to
+.BR hashed ,
+but returns a
+.B Hash
+value instead of the raw data.
 .PP
 .B Name
 represents both local and extended names, and simple principals consisting of just a key.
@@ -438,6 +517,82 @@ returns an array of bytes containing the hash of the canonical form of expressio
 .I e
 using hash algorithm
 .IR alg .
+.PP
+.B Signature
+associates
+.B hash ,
+the
+.B Hash
+value of something (eg, a public key) with the result of applying a public-key signature
+algorithm
+.B sa
+ to that hash value.
+The name of the algorithm has the form
+.IP
+.EX
+\fIalg\fP\fR[-[\fP\fIencoding\fP\fR-]\fP\fIhash\fP\fR]\fP
+.EE
+with up to three subcomponents (separated by dashes),
+where
+.I alg
+is a public key algorithm such as
+.B rsa
+or
+.BR dsa ,
+.I encoding
+is an optional encoding to apply to the value before signing,
+and
+.I hash
+is the secure hash algorithm to apply to the encoded value before signing.
+For example, the usual algorithms for RSA keys are
+.B rsa-pkcs1-sha1
+and
+.BR rsa-pkcs1-md5 .
+.PP
+Signatures are created by
+.BR signcert ,
+which signs a SPKI certificate represented by
+.I c
+with
+.I key
+using the signature algorithm
+.IR sigalg .
+.I Key
+must contain both public and secret (private) components.
+Any other binary data can be signed by
+.BR signbytes ,
+which signs arbitrary data represented by an array of bytes
+.IR a .
+Both functions apply any encoding and hash algorithms mentioned by
+.IR sigalg ,
+and return a tuple
+.BI ( sig , err ).
+On success,
+.I sig
+refers to a
+.B Signature
+value that can be converted to an S-expression using
+.IB sig .sexp()
+and
+.I err
+is nil.
+On an error,
+.I sig
+is nil and
+.I err
+contains a diagnostic.
+.PP
+A certificate's signature can be checked by
+.BR checksig .
+If
+.I sig
+is a valid signature for certificate
+.IR c ,
+.B checksig
+returns nil.
+If the signature is invalid,
+.I checksig
+returns a diagnostic.
 .SH SOURCE
 .B /appl/lib/spki.b
 .SH SEE ALSO
diff --git a/man/2/spki-verifier b/man/2/spki-verifier
index 0218c75a..880eaf42 100644
--- a/man/2/spki-verifier
+++ b/man/2/spki-verifier
@@ -47,7 +47,7 @@ speaks for (on behalf of) a given
 regarding a set of statements, with validity optionally limited to a given period.
 That is, when during the agreed time,
 .I subject
-makes a statement that is in the agreed sete, it is treated
+makes a statement that is in the agreed set, it is treated
 as if
 .I name
 had said it directly.
diff --git a/module/spki.m b/module/spki.m
index bb922a3c..fbb82ba7 100644
--- a/module/spki.m
+++ b/module/spki.m
@@ -40,10 +40,14 @@ SPKI: module
 		pk:	ref Keyring->PK;	# either pk/sk or hash might be nil
 		sk:	ref Keyring->SK;
 		nbits:	int;
-		halg:	string;
-		hash:	ref Hash;
+		halg:	string;	# basic signature hash algorithm
+		henc:	string;	# pre-signature encoding
+		hash:	list of ref Hash;
 
 		hashed:	fn(k: self ref Key, alg: string): array of byte;
+		hashexp:	fn(k: self ref Key, alg: string): ref Hash;
+		ishash:	fn(k: self ref Key): int;
+		public:	fn(k: self ref Key): ref Key;
 		sigalg:	fn(k: self ref Key): string;
 		text:	fn(k: self ref Key): string;
 		sexp:	fn(k: self ref Key): ref Sexprs->Sexp;
@@ -115,7 +119,7 @@ SPKI: module
 	Signature: adt {
 		hash:	ref Hash;
 		key:	ref Key;	# find by hash if necessary
-		sa:	string;
+		sa:	string;	# alg[-[encoding-]hash]
 		sig:	list of (string, array of byte);
 
 		algs:	fn(s: self ref Signature): (string, string, string);
@@ -149,6 +153,7 @@ SPKI: module
 			exp:	ref Sexprs->Sexp;
 		}
 
+		sexp:	fn(se: self ref Seqel): ref Sexprs->Sexp;
 		text:	fn(se: self ref Seqel): string;
 	};
 
@@ -172,6 +177,9 @@ SPKI: module
 		Seq =>
 			v:	list of ref Seqel;
 		}
+
+		sexp:	fn(t: self ref Toplev): ref Sexprs->Sexp;
+		text:	fn(t: self ref Toplev): string;
 	};
 
 	init:	fn();
@@ -191,6 +199,10 @@ SPKI: module
 	checksig:	fn(c: ref Cert, sig: ref Signature): string;
 	sig2icert:	fn(sig: ref Signature, signer: string, exp: int): ref Keyring->Certificate;
 
+	# signature making
+	signcert:	fn(c: ref Cert, sigalg: string, key: ref Key): (ref Signature, string);
+	signbytes:	fn(a: array of byte, sigalg: string, key: ref Key): (ref Signature, string);
+
 	# tags
 	maketag:	fn(e: ref Sexprs->Sexp): ref Sexprs->Sexp;
 	tagintersect:	fn(t1: ref Sexprs->Sexp, t2: ref Sexprs->Sexp): ref Sexprs->Sexp;
@@ -206,6 +218,9 @@ SPKI: module
 	time2secs:	fn(s: string): int;	# HH:MM:SS
 	secs2time:	fn(t: int): string;
 
+	# misc
+	sigalgs:	fn(algs: string): (string, string, string);
+
 	# debugging
 	dump:	fn(s: string, a: array of byte);
 };