ref: 057c663622ca7a7b4cf8264ea86d73e7bb65b434
parent: 8e12e317c5694f86671fdb2068d8a99214d08e5a
author: Ori Bernstein <ori@eigenstate.org>
date: Sun Apr 15 14:37:27 EDT 2018
Add big-endian constructor for ctbig. It turns out that many places we use ctbig will want to create them from big endian byte buffers.
--- a/lib/crypto/bld.sub
+++ b/lib/crypto/bld.sub
@@ -12,7 +12,7 @@
# hmac
hmac.myr
- # ciphers
+ # symmetric ciphers
chacha20.myr
aes.myr
--- a/lib/crypto/ctbig.myr
+++ b/lib/crypto/ctbig.myr
@@ -11,9 +11,11 @@
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 ctbytes : (v : ctbig# -> byte[:])
pkglocal const mkctbigle : (v : byte[:], nbit : std.size -> ctbig#)
- //const mkctbigbe : (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#)
@@ -25,7 +27,6 @@
pkglocal const ctadd : (r : ctbig#, a : ctbig#, b : ctbig# -> void)
pkglocal const ctsub : (r : ctbig#, a : ctbig#, b : ctbig# -> void)
pkglocal const ctmul : (r : ctbig#, a : ctbig#, b : ctbig# -> void)
- //pkglocal const ctdivmod : (q : ctbig#, u : ctbig#, a : ctbig#, b : ctbig# -> void)
pkglocal const ctmodpow : (r : ctbig#, a : ctbig#, b : ctbig#, m : ctbig# -> void)
pkglocal const ctiszero : (v : ctbig# -> bool)
@@ -69,6 +70,24 @@
;;
}
+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 @avar a
var val
@@ -132,19 +151,66 @@
a = std.slzalloc(ndig(nbit))
for i = 0; i + 4 <= v.len; i += 4
a[o++] = \
- (v[i + 0] << 0 : uint32) | \
- (v[i + 1] << 8 : uint32) | \
- (v[i + 2] << 16 : uint32) | \
- (v[i + 3] << 24 : uint32)
+ ((v[i + 0] : uint32) << 0) | \
+ ((v[i + 1] : uint32) << 8) | \
+ ((v[i + 2] : uint32) << 16) | \
+ ((v[i + 3] : uint32) << 24)
;;
- last = 0
- for i; i < v.len; i++
- off = i & 0x3
- last |= (v[off] : uint32) << (8 *off)
+ if i != v.len
+ last = 0
+ for i; i < v.len; i++
+ off = i & 0x3
+ last |= (v[i] : uint32) << (8 *off)
+ ;;
+ a[o++] = last
;;
- a[o++] = last
-> clip(std.mk([.nbit=nbit, .dig=a]))
+}
+
+const mkctbigbe = {v, nbit+ var a, i, o, tail : byte[4]
+
+ /*
+ It's ok to depend on the length of v here: we can leak the
+ size of the numbers.
+ */
+ o = 0
+ a = std.slzalloc(ndig(nbit))
+ for i = v.len ; i >= 4; i -= 4
+ a[o++] = std.getbe32(v[i-4:i])
+ ;;
+
+ if i != 0
+ std.slfill(tail[:], 0)
+ std.slcp(tail[4-i:], v[:i])
+ a[o++] = std.getbe32(tail[:])
+ ;;
+ -> clip(std.mk([.nbit=nbit, .dig=a]))
+}
+
+const ctbytes = {v+ var d, i, n, o, ret
+
+ o = 0
+ n = (v.nbit + 7) / 8
+ ret = std.slalloc(n)
+ for i = 0; i * 4 < n; i++
+ d = v.dig[i]
+ ret[o++] = (d >> 0 : byte)
+ ret[o++] = (d >> 8 : byte)
+ ret[o++] = (d >> 16 : byte)
+ ret[o++] = (d >> 24 : byte)
+ ;;
+
+ if i * 4 != n
+ d = v.dig[i]
+ for ; i < n; i++
+ ret[o++] = (d : byte)
+ d >>= 8
+ ;;
+ ;;
+ -> ret
}
const ctlike = {v--- a/lib/crypto/test/ctbig.myr
+++ b/lib/crypto/test/ctbig.myr
@@ -21,6 +21,16 @@
crypto.clip(&v)
testr.eq(ctx, v.dig[0], 0x7fffffff)
}],
+ [.name="mkbig-le", .fn={ctx+ docvt(ctx, crypto.mkctbigle, Nbit,
+ "6618611909121",
+ "\x01\x02\x03\x04\x05\x06")
+ }],
+ [.name="mkbig-be", .fn={ctx+ docvt(ctx, crypto.mkctbigbe, Nbit,
+ "1108152157446",
+ "\x00\x01\x02\x03\x04\x05\x06")
+ }],
/* normal */
[.name="add", .fn={ctxdo2(ctx, crypto.ctadd, Nbit,
@@ -45,8 +55,7 @@
"259016584597313952181375284077740334036",
"137304361882109849168381018424069802644",
"279268927326277818181333274586733399084")
- }
- ],
+ }],
/* comparisons */
[.name="lt-less", .fn={ctxdobool(ctx, crypto.ctlt, Nbit,
@@ -53,51 +62,43 @@
true,
"137304361882109849168381018424069802644",
"279268927326277818181333274586733399084")
- }
- ],
+ }],
[.name="lt-equal", .fn={ctxdobool(ctx, crypto.ctlt, Nbit,
false,
"137304361882109849168381018424069802644",
"137304361882109849168381018424069802644")
- }
- ],
+ }],
[.name="lt-greater", .fn={ctxdobool(ctx, crypto.ctlt, Nbit,
false,
"279268927326277818181333274586733399084",
"137304361882109849168381018424069802644")
- }
- ],
+ }],
[.name="gt-less", .fn={ctxdobool(ctx, crypto.ctgt, Nbit,
false,
"137304361882109849168381018424069802644",
"279268927326277818181333274586733399084")
- }
- ],
+ }],
[.name="gt-equal", .fn={ctxdobool(ctx, crypto.ctgt, Nbit,
false,
"137304361882109849168381018424069802644",
"137304361882109849168381018424069802644")
- }
- ],
+ }],
[.name="gt-greater", .fn={ctxdobool(ctx, crypto.ctgt, Nbit,
true,
"279268927326277818181333274586733399084",
"137304361882109849168381018424069802644")
- }
- ],
-
+ }],
[.name="growmodsmall", .fn={ctxdo2(ctx, growmod0, Nbit,
"30064771072",
"7",
"279268927326277818181333274586733399084")
- }
- ],
+ }],
[.name="addfunky", .fn={ctxdo2(ctx, crypto.ctadd, Nfunky,
"75540728658750274549064",
@@ -159,6 +160,20 @@
crypto.ctfree(a)
crypto.ctfree(b)
+}
+
+const docvt = {ctx, op, nbit, estr, buf+ var v, e, ei
+
+ ei = std.get(std.bigparse(estr))
+ e = crypto.big2ct(ei, nbit)
+ std.bigfree(ei)
+
+ v = op(buf, nbit)
+ testr.eq(ctx, v, e)
+
+ crypto.ctfree(e)
+ crypto.ctfree(v)
}
const do2 = {ctx, op, nbit, estr, astr, bstr--- a/lib/std/fmt.myr
+++ b/lib/std/fmt.myr
@@ -492,7 +492,12 @@
| ("p", pad): p = decode(pad) | ("r", ""): raw = true | ("e", ""): esc = true- | _: std.die("unreachable\n")+ | (opt, arg):
+ std.write(2, "fmt: ")
+ std.write(2, opt)
+ std.write(2, "arg: ")
+ std.write(2, arg)
+ std.die("unreachable\n");;
;;
iassert(p >= 0, "pad must be >= 0")