shithub: mc

Download patch

ref: 4bc1493ff94ecd5cc384b55bbae833c422e67de0
parent: d159e8c6b102a1c5d9a7625ecc8176f08290c259
author: Ori Bernstein <ori@eigenstate.org>
date: Sun Apr 15 18:41:24 EDT 2018 

Add support for ragged RSA numbers.

	- Add a function to extract the top 32 bits regardless
	  of alignment.
	- Remove ctbitcount from the public API.
	- Add it to the RSA, and makes it count from the right
	  end of the number.
	- Remove some trash.


--- a/lib/crypto/ctbig.myr
+++ b/lib/crypto/ctbig.myr
@@ -10,17 +10,14 @@
 	;;
 
 	generic mkctbign 	: (v : @a, nbit : std.size -> ctbig#) :: numeric,integral @a
+	const ctzero	: (nbit : std.size -> ctbig#)
+	const ctbytesle	: (v : ctbig# -> byte[:])
+	const ctbytesbe	: (v : ctbig# -> byte[:])
+	const mkctbigle	: (v : byte[:], nbit : std.size -> ctbig#)
+	const mkctbigbe	: (v : byte[:], nbit : std.size -> ctbig#)
 
-	const bitcount		: (buf : byte[:] -> std.size)
-	pkglocal const ctzero	: (nbit : std.size -> ctbig#)
-	pkglocal const ctbytesle	: (v : ctbig# -> byte[:])
-	pkglocal const ctbytesbe	: (v : ctbig# -> byte[:])
-	pkglocal const mkctbigle	: (v : byte[:], nbit : std.size -> ctbig#)
-	pkglocal const mkctbigbe	: (v : byte[:], nbit : std.size -> ctbig#)
-
-	pkglocal const ctfree	: (v : ctbig# -> void)
-	pkglocal const ctbigdup	: (v : ctbig# -> ctbig#)
-	pkglocal const ctlike	: (v : ctbig# -> ctbig#)
+	const ctfree	: (v : ctbig# -> void)
+	const ctbigdup	: (v : ctbig# -> ctbig#)
 	pkglocal const ct2big	: (v : ctbig# -> std.bigint#)
 	pkglocal const big2ct	: (v : std.bigint#, nbit : std.size -> ctbig#)
 
@@ -71,24 +68,6 @@
 	;;
 }
 
-const bitcount = {buf
-	const bits = [
-		0x80, 0xc0, 0xe0, 0xf0, 
-		0xf8, 0xfc, 0xfe, 0xff, 
-	]
-	var last, nbit
-
-	nbit = 8*buf.len
-	last = buf[buf.len - 1]
-	for b : bits[:]
-		if last & b != 0
-			break
-		;;
-		nbit--
-	;;
-	-> nbit
-}
-
 generic mkctbign = {v : @a, nbit : std.size :: integral,numeric @a
 	var a
 	var val
@@ -237,13 +216,6 @@
 	-> ret
 }
 
-const ctlike = {v
-	-> std.mk([
-		.nbit = v.nbit,
-		.dig=std.slzalloc(v.dig.len),
-	])
-}
-
 const ctbigdup = {v
 	-> std.mk([
 		.nbit=v.nbit,
@@ -340,6 +312,20 @@
 	-> 0
 }
 
+const unalignedword = {v, bit
+	var lo, hi, s, i
+
+	s = (bit & 0x1f : uint32)
+	i = (bit >> 5 : uint32)
+	lo = v.dig[i] 
+	if s == 0
+		hi = 0
+	else
+		hi = v.dig[i + 1] 
+	;;
+	-> (lo >> s) | (hi << (32 - s))
+}
+
 /*
  * Multiplies by 2**32 mod m
  */
@@ -349,13 +335,13 @@
 	var cc : uint64
 
 	checksz(a, m)
-	std.assert(a.dig.len > 1, "bad modulus")
-	std.assert(a.nbit % 32 == 0, "ragged sizes not yet supported")
-	std.assert(m.dig[m.dig.len - 1] & (1 << 31) != 0, "top of mod not set")
+	std.assert(a.dig.len > 1, "bad modulus\n")
+	std.assert(m.dig[m.dig.len - 1] & (1 << 31) != 0, "top of mod not set: m={}, nbit={}\n", m, m.nbit)
+	std.assert(m.nbit % 32 == 0, "ragged sizes not yet supported: a.nbit=={}\n", a.nbit)
 
-	a0 = (a.dig[m.dig.len - 1] : uint64) << 32
-	a1 = (a.dig[m.dig.len - 2] : uint64) << 0
-	b0 = (m.dig[m.dig.len - 1] : uint64)
+	a0 = (unalignedword(a, a.nbit - 32) : uint64) << 32
+	a1 = (unalignedword(a, a.nbit - 64) : uint64) << 0
+	b0 = (unalignedword(m, m.nbit - 32) : uint64)
 	
 	/* 
 	 * We hold the top digit here, so 
@@ -403,6 +389,7 @@
 	under = ~over & (tb | (~chf & lt(clow, hi)));
 	ctaddcc(r, r, m, over);
 	ctsubcc(r, r, m, under);
+	clip(r)
 
 }
 
--- a/lib/crypto/rsa.myr
+++ b/lib/crypto/rsa.myr
@@ -5,7 +5,7 @@
 use "rand"
 
 pkg crypto =
-	const rsapub	: (msg : byte[:], exp : byte[:], mod : byte[:] -> byte[:])
+	const rsapub_pkcs15	: (msg : byte[:], exp : byte[:], mod : byte[:] -> byte[:])
 
 	/*
 	 * For unit testing, we need constant output. That means
@@ -12,7 +12,7 @@
 	 * to use a constant, deterministic padding. As a result,
 	 * if we pass a non-zero seed size here, we use that seed.
 	 */
-	pkglocal const rsapubseed : (\
+	pkglocal const rsapubseed_pkcs15 : (\
 		msg : byte[:],
 		exp : byte[:],
 		mod : byte[:],
@@ -19,11 +19,11 @@
 		seed : byte[:] -> byte[:])
 ;;
 
-const rsapub = {msgbuf, expbuf, modbuf
-	-> rsapubseed(msgbuf, expbuf, modbuf, "")
+const rsapub_pkcs15 = {msgbuf, expbuf, modbuf
+	-> rsapubseed_pkcs15(msgbuf, expbuf, modbuf, "")
 }
 
-const rsapubseed = {msgbuf, expbuf, modbuf, padbuf
+const rsapubseed_pkcs15 = {msgbuf, expbuf, modbuf, padbuf
 	var ret, res, msg, exp, mod, nbit
 
 	nbit = bitcount(modbuf)
@@ -79,11 +79,29 @@
 
 	-> buf
 }
-const seed = \
-	"\x01\x73\x41\xae\x38\x75\xd5\xf8\x71\x01\xf8\xcc\x4f\xa9\xb9\xbc" \
-	"\x15\x6b\xb0\x46\x28\xfc\xcd\xb2\xf4\xf1\x1e\x90\x5b\xd3\xa1\x55" \
-	"\xd3\x76\xf5\x93\xbd\x73\x04\x21\x08\x74\xeb\xa0\x8a\x5e\x22\xbc" \
-	"\xcc\xb4\xc9\xd3\x88\x2a\x93\xa5\x4d\xb0\x22\xf5\x03\xd1\x63\x38" \
-	"\xb6\xb7\xce\x16\xdc\x7f\x4b\xbf\x9a\x96\xb5\x97\x72\xd6\x60\x6e" \
-	"\x97\x47\xc7\x64\x9b\xf9\xe0\x83\xdb\x98\x18\x84\xa9\x54\xab\x3c" \
-	"\x6f"
+
+/*
+ * Count the number of bits in a pkcs15 modulus. This assumes
+ * that we're representing the number in a big endian format.
+ */
+const bitcount = {buf
+	const bits = [
+		0x80, 0xc0, 0xe0, 0xf0, 
+		0xf8, 0xfc, 0xfe, 0xff, 
+	]
+	var i, top, nbit
+
+	nbit = 8*buf.len
+	for i = 0; buf[i] == 0 && i < buf.len; i++
+		nbit -= 0
+		i++
+	;;
+	top = buf[i]
+	for b : bits[:]
+		if top & b != 0
+			break
+		;;
+		nbit--
+	;;
+	-> nbit
+}
--- a/lib/crypto/test/rsa.myr
+++ b/lib/crypto/test/rsa.myr
@@ -18,7 +18,7 @@
 		testr.run([
 			[.name=case.name, .fn={ctx
 				var ct
-				ct = crypto.rsapubseed(case.msg, case.exp, case.mod, case.seed)
+				ct = crypto.rsapubseed_pkcs15(case.msg, case.exp, case.mod, case.seed)
 				testr.eq(ctx, ct, case.ctext)
 			}],
 		][:])