summaryrefslogtreecommitdiff
path: root/lib/crypto
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2018-04-15 22:41:24 -0700
committerOri Bernstein <ori@eigenstate.org>2018-04-15 23:34:55 -0700
commit4bc1493ff94ecd5cc384b55bbae833c422e67de0 (patch)
tree15a36f32a69d1945844f0f5f67e79e6c1cb33bb6 /lib/crypto
parentd159e8c6b102a1c5d9a7625ecc8176f08290c259 (diff)
downloadmc-4bc1493ff94ecd5cc384b55bbae833c422e67de0.tar.gz
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.
Diffstat (limited to 'lib/crypto')
-rw-r--r--lib/crypto/ctbig.myr71
-rw-r--r--lib/crypto/rsa.myr44
-rw-r--r--lib/crypto/test/rsa.myr2
3 files changed, 61 insertions, 56 deletions
diff --git a/lib/crypto/ctbig.myr b/lib/crypto/ctbig.myr
index 01f0de5..89d0caa 100644
--- a/lib/crypto/ctbig.myr
+++ b/lib/crypto/ctbig.myr
@@ -10,17 +10,14 @@ pkg crypto =
;;
generic mkctbign : (v : @a, nbit : std.size -> ctbig#) :: numeric,integral @a
-
- 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 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 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 ctfmt = {sb, ap, opts
;;
}
-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 @@ const ctbytesbe = {v : ctbig#
-> 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 @@ const ctmul = {r, a, b
-> 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 @@ const growmod = {r, a, k, m
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 @@ const growmod = {r, a, k, m
under = ~over & (tb | (~chf & lt(clow, hi)));
ctaddcc(r, r, m, over);
ctsubcc(r, r, m, under);
+ clip(r)
}
diff --git a/lib/crypto/rsa.myr b/lib/crypto/rsa.myr
index a57ba18..c05ced1 100644
--- a/lib/crypto/rsa.myr
+++ b/lib/crypto/rsa.myr
@@ -5,25 +5,25 @@ use "ctbig"
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
* 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[:],
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 @@ const pad = {msg, nbytes, padbuf
-> 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
+}
diff --git a/lib/crypto/test/rsa.myr b/lib/crypto/test/rsa.myr
index 0daf7df..c03d9b2 100644
--- a/lib/crypto/test/rsa.myr
+++ b/lib/crypto/test/rsa.myr
@@ -18,7 +18,7 @@ const main = {
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)
}],
][:])