ref: d159e8c6b102a1c5d9a7625ecc8176f08290c259
parent: 057c663622ca7a7b4cf8264ea86d73e7bb65b434
author: Ori Bernstein <ori@eigenstate.org>
date: Sun Apr 15 15:50:24 EDT 2018
Add first tested RSA implementation.
--- a/lib/crypto/bld.sub
+++ b/lib/crypto/bld.sub
@@ -16,6 +16,9 @@
chacha20.myr
aes.myr
+ # public key ciphers
+ rsa.myr
+
# randomness
entropy.myr # currently assumes a /dev/random
rand.myr
--- a/lib/crypto/ctbig.myr
+++ b/lib/crypto/ctbig.myr
@@ -13,7 +13,8 @@
const bitcount : (buf : byte[:] -> std.size)
pkglocal const ctzero : (nbit : std.size -> ctbig#)
- pkglocal const ctbytes : (v : ctbig# -> byte[:])
+ 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#)
@@ -189,7 +190,7 @@
-> clip(std.mk([.nbit=nbit, .dig=a]))
}
-const ctbytes = {v+const ctbytesle = {vvar d, i, n, o, ret
o = 0
@@ -209,6 +210,29 @@
ret[o++] = (d : byte)
d >>= 8
;;
+ ;;
+ -> ret
+}
+
+const ctbytesbe = {v : ctbig#+ var d : uint32, i, n, o, ret
+
+ i = v.dig.len - 1
+ o = 0
+ n = (v.nbit + 7) / 8
+ ret = std.slalloc(n)
+ if n & 0x3 != 0
+ d = v.dig[i--]
+ for var j = n & 0x3 + 1; j > 0; j--
+ ret[o++] = (d >> 8*(j - 1 : uint32): byte)
+ ;;
+ ;;
+ for ; i >= 0 ; i--
+ d = v.dig[i]
+ ret[o++] = (d >> 24 : byte)
+ ret[o++] = (d >> 16 : byte)
+ ret[o++] = (d >> 8 : byte)
+ ret[o++] = (d >> 0 : byte)
;;
-> ret
}
--- /dev/null
+++ b/lib/crypto/rsa.myr
@@ -1,0 +1,89 @@
+use std
+
+use "ct"
+use "ctbig"
+use "rand"
+
+pkg crypto =
+ const rsapub : (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 : (\
+ msg : byte[:],
+ exp : byte[:],
+ mod : byte[:],
+ seed : byte[:] -> byte[:])
+;;
+
+const rsapub = {msgbuf, expbuf, modbuf+ -> rsapubseed(msgbuf, expbuf, modbuf, "")
+}
+
+const rsapubseed = {msgbuf, expbuf, modbuf, padbuf+ var ret, res, msg, exp, mod, nbit
+
+ nbit = bitcount(modbuf)
+ res = ctzero(nbit)
+ msg = decodepad(msgbuf, nbit, padbuf)
+ exp = decode(expbuf, nbit)
+ mod = decode(modbuf, nbit)
+
+ ctmodpow(res, msg, exp, mod)
+ ret = ctbytesbe(res)
+
+ ctfree(res)
+ ctfree(msg)
+ ctfree(exp)
+ ctfree(mod)
+ -> ret
+}
+
+const decodepad = {msg, len, padbuf+ var mpad, m
+
+ mpad = pad(msg, (len + 7) / 8, padbuf)
+ m = mkctbigbe(mpad, len)
+ std.slfree(mpad)
+ -> m
+}
+
+const decode = {msg, len+ -> mkctbigbe(msg, len)
+}
+
+const pad = {msg, nbytes, padbuf+ var buf, pslen
+
+ std.assert(msg.len < nbytes - 11, "overlong message")
+ buf = std.slalloc(nbytes)
+
+ buf[0] = 0
+ buf[1] = 2
+ pslen = nbytes - msg.len - 3
+ if padbuf.len > 0
+ std.slcp(buf[2:pslen+2], padbuf)
+ else
+ randbytes(buf[2:pslen+2])
+ for var i = 0; i < pslen; i++
+ while buf[i + 2] == 0
+ randbytes(buf[i+2:i+3])
+ ;;
+ ;;
+ ;;
+ buf[pslen + 2] = 0
+ std.slcp(buf[pslen+3:], msg)
+
+ -> 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"
--- /dev/null
+++ b/lib/crypto/test/rsa.myr
@@ -1,0 +1,65 @@
+use std
+use crypto
+use iter
+use testr
+
+type pubcase = struct
+ name : byte[:]
+ nbit : std.size
+ msg : byte[:]
+ exp : byte[:]
+ mod : byte[:]
+ seed : byte[:]
+ ctext : byte[:]
+;;
+
+const main = {+ for case : iter.byref(pubcases)
+ testr.run([
+ [.name=case.name, .fn={ctx+ var ct
+ ct = crypto.rsapubseed(case.msg, case.exp, case.mod, case.seed)
+ testr.eq(ctx, ct, case.ctext)
+ }],
+ ][:])
+ ;;
+}
+
+const pubcases : pubcase[:] = [
+ [
+ .name="basic",
+ .nbit=1024,
+ .mod=\
+ "\xa8\xb3\xb2\x84\xaf\x8e\xb5\x0b\x38\x70\x34\xa8\x60\xf1\x46\xc4" \
+ "\x91\x9f\x31\x87\x63\xcd\x6c\x55\x98\xc8\xae\x48\x11\xa1\xe0\xab" \
+ "\xc4\xc7\xe0\xb0\x82\xd6\x93\xa5\xe7\xfc\xed\x67\x5c\xf4\x66\x85" \
+ "\x12\x77\x2c\x0c\xbc\x64\xa7\x42\xc6\xc6\x30\xf5\x33\xc8\xcc\x72" \
+ "\xf6\x2a\xe8\x33\xc4\x0b\xf2\x58\x42\xe9\x84\xbb\x78\xbd\xbf\x97" \
+ "\xc0\x10\x7d\x55\xbd\xb6\x62\xf5\xc4\xe0\xfa\xb9\x84\x5c\xb5\x14" \
+ "\x8e\xf7\x39\x2d\xd3\xaa\xff\x93\xae\x1e\x6b\x66\x7b\xb3\xd4\x24" \
+ "\x76\x16\xd4\xf5\xba\x10\xd4\xcf\xd2\x26\xde\x88\xd3\x9f\x16\xfb",
+ .exp="\x01\x00\x01",
+ .msg=\
+ "\x66\x28\x19\x4e\x12\x07\x3d\xb0\x3b\xa9\x4c\xda\x9e\xf9\x53\x23" \
+ "\x97\xd5\x0d\xba\x79\xb9\x87\x00\x4a\xfe\xfe\x34",
+ .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",
+
+ .ctext=\
+ "\x50\xb4\xc1\x41\x36\xbd\x19\x8c\x2f\x3c\x3e\xd2\x43\xfc\xe0\x36" \
+ "\xe1\x68\xd5\x65\x17\x98\x4a\x26\x3c\xd6\x64\x92\xb8\x08\x04\xf1" \
+ "\x69\xd2\x10\xf2\xb9\xbd\xfb\x48\xb1\x2f\x9e\xa0\x50\x09\xc7\x7d" \
+ "\xa2\x57\xcc\x60\x0c\xce\xfe\x3a\x62\x83\x78\x9d\x8e\xa0\xe6\x07" \
+ "\xac\x58\xe2\x69\x0e\xc4\xeb\xc1\x01\x46\xe8\xcb\xaa\x5e\xd4\xd5" \
+ "\xcc\xe6\xfe\x7b\x0f\xf9\xef\xc1\xea\xbb\x56\x4d\xbf\x49\x82\x85" \
+ "\xf4\x49\xee\x61\xdd\x7b\x42\xee\x5b\x58\x92\xcb\x90\x60\x1f\x30" \
+ "\xcd\xa0\x7b\xf2\x64\x89\x31\x0b\xcd\x23\xb5\x28\xce\xab\x3c\x31",
+ ]
+][:]
+