[Nickle] nickle: Branch 'master'
Keith Packard
keithp at keithp.com
Wed Aug 18 17:13:48 PDT 2021
Makefile.am | 2
cha-cha.5c | 103 ++++++++++++++++++++++++++++++++++++
test/Makefile.am | 3 -
test/chacha_test.5c | 146 ++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 252 insertions(+), 2 deletions(-)
New commits:
commit 67adefce9eec965a180374c9ec68915918dcbaf9
Author: Keith Packard <keithp at keithp.com>
Date: Wed Aug 18 17:13:47 2021 -0700
Add ChaCha implementation
Signed-off-by: Keith Packard <keithp at keithp.com>
diff --git a/Makefile.am b/Makefile.am
index 26396b8..472b99f 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -14,7 +14,7 @@ NICKLEFILES = builtin.5c math.5c scanf.5c mutex.5c \
printf.5c history.5c ctype.5c string.5c socket.5c \
file.5c parse-args.5c svg.5c process.5c \
prime_sieve.5c factorial.5c gamma.5c sort.5c list.5c skiplist.5c \
- json.5c
+ json.5c cha-cha.5c
EXTRA_DIST = README.name README.release autogen.sh ChangeLog \
$(NICKLEFILES) nickle.1.in nickle.spec.in
diff --git a/cha-cha.5c b/cha-cha.5c
new file mode 100644
index 0000000..31e44c0
--- /dev/null
+++ b/cha-cha.5c
@@ -0,0 +1,103 @@
+/*
+ * Copyright © 2021 Keith Packard.
+ * All Rights Reserved. See the file COPYING in this directory
+ * for licensing information.
+ */
+
+/*
+ * Implementation of ChaCha20
+ */
+
+namespace ChaCha {
+
+ int rotl(int a, int b) = ((a << b) | (a >> (32 - b))) & 0xffffffff;
+ int plus(int a, int b) = (a + b) & 0xffffffff;
+ int xor(int a, int b) = (a ^ b) & 0xffffffff;
+
+ const int ROUNDS = 10;
+
+ public void qr(&int[16] x, int a, int b, int c, int d) {
+ x[a] = plus(x[a], x[b]); x[d] = xor(x[d], x[a]); x[d] = rotl(x[d],16);
+ x[c] = plus(x[c], x[d]); x[b] = xor(x[b], x[c]); x[b] = rotl(x[b],12);
+ x[a] = plus(x[a], x[b]); x[d] = xor(x[d], x[a]); x[d] = rotl(x[d], 8);
+ x[c] = plus(x[c], x[d]); x[b] = xor(x[b], x[c]); x[b] = rotl(x[b], 7);
+ }
+
+ /*
+ * Basic ChaCha20 operation
+ */
+ public void block(&int[16] out, &int[16] in)
+ {
+ int i;
+ int[16] x;
+
+ for (i = 0; i < 16; ++i)
+ x[i] = in[i];
+
+ /* 10 loops × 2 rounds/loop = 20 rounds */
+
+ for (i = 0; i < ROUNDS; i ++) {
+ /* Odd round */
+ qr(&x, 0, 4, 8, 12); /* column 0 */
+ qr(&x, 1, 5, 9, 13); /* column 1 */
+ qr(&x, 2, 6, 10, 14); /* column 2 */
+ qr(&x, 3, 7, 11, 15); /* column 3 */
+ /* Even round */
+ qr(&x, 0, 5, 10, 15); /* diagonal 1 (main diagonal) */
+ qr(&x, 1, 6, 11, 12); /* diagonal 2 */
+ qr(&x, 2, 7, 8, 13); /* diagonal 3 */
+ qr(&x, 3, 4, 9, 14); /* diagonal 4 */
+ }
+ for (i = 0; i < 16; ++i)
+ out[i] = plus(x[i],in[i]);
+ }
+
+ int lsb_word(&int[*] bytes, int i) {
+ return ((bytes[i]) | (bytes[i+1] << 8) |
+ (bytes[i+2] << 16) | (bytes[i+3] << 24));
+ }
+
+ /*
+ * Convert key, count and nonce into chacha state
+ */
+ public int[16] state(&int[32] key, int count, &int[12] nonce)
+ {
+ static int[4] chacha_const = {
+ 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574
+ };
+ return (int[16]) { [i] = (i < 4) ? chacha_const[i] :
+ ((i < 12) ? lsb_word(&key, (i-4)*4) :
+ ((i == 12) ? count : lsb_word(&nonce, (i-13) * 4))) };
+ }
+
+ /*
+ * Generate bytes from 32-bit units
+ */
+ void serialize(&int[64] bytes, &int[16] state)
+ {
+ for (int i = 0; i < 64; i++)
+ bytes[i] = (state[floor(i/4)] >> ((i % 4) * 8)) & 0xff;
+ }
+
+ /*
+ * Stream cypher.
+ */
+ public void encrypt(&int[16] state,
+ &int[*] plaintext, &int[*] cyphertext)
+ {
+ int[16] state_local = state;
+ int[16] state_cha;
+ int[64] bytes;
+ int l = dim(plaintext);
+
+ for (int i = 0; i < ceil(l / 64); i++) {
+ state_local[12] = state[12] + i;
+ block(&state_cha, &state_local);
+ serialize(&bytes, &state_cha);
+ int e = min(64, l - i * 64);
+ for (int k = 0; k < e; k++)
+ cyphertext[i*64 + k] = plaintext[i*64+k] ^ bytes[k];
+ }
+ }
+}
+
diff --git a/test/Makefile.am b/test/Makefile.am
index 39dc364..c514740 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -17,7 +17,8 @@ check_SCRIPTS=\
jsontest.5c \
datetest.5c \
string-file.5c \
- sorttest.5c
+ sorttest.5c \
+ chacha_test.5c
TABLES=math-tables.5c
diff --git a/test/chacha_test.5c b/test/chacha_test.5c
new file mode 100644
index 0000000..785517b
--- /dev/null
+++ b/test/chacha_test.5c
@@ -0,0 +1,146 @@
+/*
+ * Copyright © 2021 Keith Packard.
+ * All Rights Reserved. See the file COPYING in this directory
+ * for licensing information.
+ */
+
+autoload ChaCha;
+
+void
+dump_state(&int[16] state)
+{
+ for (int i = 0; i < 4; i++) {
+ for (int j = 0; j < 4; j++)
+ printf(" %08x", state[i*4+j]);
+ printf("\n");
+ }
+}
+
+void
+dump_bytes(&int[] bytes)
+{
+ for (int i = 0; i < dim(bytes); i++) {
+ if (i > 0 && (i % 16) == 0)
+ printf("\n");
+ printf(" %02x", bytes[i]);
+ }
+ printf("\n");
+}
+
+/*
+ * ChaCha quarter round test
+ */
+
+int[16] test_qr = { 0x11111111, 0x01020304, 0x9b8d6f43, 0x01234567, 0 ... };
+
+ChaCha::qr(&test_qr, 0, 1, 2, 3);
+
+int[16] test_qr_expect = { 0xea2a92f4, 0xcb1cf8ce, 0x4581472e, 0x5881c4bb, 0 ... };
+
+assert(test_qr == test_qr_expect, "single QR failure test 1 %v != %v\n", test_qr_expect, test_qr);
+
+/*
+ * ChaCha quarter round test 2
+ */
+
+int[16] test_qr2 = {
+ 0x879531e0, 0xc5ecf37d, 0x516461b1, 0xc9a62f8a,
+ 0x44c20ef3, 0x3390af7f, 0xd9fc690b, 0x2a5f714c,
+ 0x53372767, 0xb00a5631, 0x974c541a, 0x359e9963,
+ 0x5c971061, 0x3d631689, 0x2098d9d6, 0x91dbd320,
+};
+
+ChaCha::qr(&test_qr2, 2, 7, 8, 13);
+
+int[16] test_qr2_expect = {
+ 0x879531e0, 0xc5ecf37d, 0xbdb886dc, 0xc9a62f8a,
+ 0x44c20ef3, 0x3390af7f, 0xd9fc690b, 0xcfacafd2,
+ 0xe46bea80, 0xb00a5631, 0x974c541a, 0x359e9963,
+ 0x5c971061, 0xccc07c79, 0x2098d9d6, 0x91dbd320,
+};
+
+assert(test_qr == test_qr_expect, "single QR failure test 2 %v != %v\n", test_qr_expect, test_qr);
+
+int[32] test_key = {
+ 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+ 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f
+};
+
+int[12] test_nonce = {
+ 0x00, 0x00, 0x00, 0x09, 0x00, 0x00, 0x00, 0x4a, 0x00, 0x00, 0x00, 0x00
+};
+
+int[16] test_state = ChaCha::state(&test_key, 1, &test_nonce);
+
+int[16] test_state_expect = {
+ 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574,
+ 0x03020100, 0x07060504, 0x0b0a0908, 0x0f0e0d0c,
+ 0x13121110, 0x17161514, 0x1b1a1918, 0x1f1e1d1c,
+ 0x00000001, 0x09000000, 0x4a000000, 0x00000000,
+};
+
+assert(test_state == test_state_expect, "state setup test failure %v != %v\n", test_state, test_state_expect);
+
+int[16] test_cha;
+
+ChaCha::block(&test_cha, &test_state);
+
+int[16] test_cha_expect = {
+ 0xe4e7f110, 0x15593bd1, 0x1fdd0f50, 0xc47120a3,
+ 0xc7f4d1c7, 0x0368c033, 0x9aaa2204, 0x4e6cd4c3,
+ 0x466482d2, 0x09aa9f07, 0x05d7c214, 0xa2028bd9,
+ 0xd19c12b5, 0xb94e16de, 0xe883d0cb, 0x4e3c50a2,
+};
+
+assert(test_cha == test_cha_expect, "cha block test failure %v != %v\n", test_cha, test_cha_expect);
+
+string plaintext = "Ladies and Gentlemen of the class of '99: If I could offer you only one tip for the future, sunscreen would be it.";
+
+int[String::length(plaintext)] plainbytes = {[i] = plaintext[i] };
+int[dim(plainbytes)] cypherbytes;
+
+int[32] encrypt_key = {
+ 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+ 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f
+};
+
+int[12] encrypt_nonce = {
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4a, 0x00, 0x00, 0x00, 0x00
+};
+
+int[16] encrypt_state = ChaCha::state(&encrypt_key, 1, &encrypt_nonce);
+
+int[16] encrypt_state_expect = {
+ 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574,
+ 0x03020100, 0x07060504, 0x0b0a0908, 0x0f0e0d0c,
+ 0x13121110, 0x17161514, 0x1b1a1918, 0x1f1e1d1c,
+ 0x00000001, 0x00000000, 0x4a000000, 0x00000000,
+};
+
+assert(encrypt_state == encrypt_state_expect, "encrypt setup test failure %v != %v\n", encrypt_state, encrypt_state_expect);
+
+ChaCha::encrypt(&encrypt_state, &plainbytes, &cypherbytes);
+
+int[] cypherbytes_expect = {
+ 0x6e, 0x2e, 0x35, 0x9a, 0x25, 0x68, 0xf9, 0x80, 0x41, 0xba, 0x07, 0x28, 0xdd, 0x0d, 0x69, 0x81,
+ 0xe9, 0x7e, 0x7a, 0xec, 0x1d, 0x43, 0x60, 0xc2, 0x0a, 0x27, 0xaf, 0xcc, 0xfd, 0x9f, 0xae, 0x0b,
+ 0xf9, 0x1b, 0x65, 0xc5, 0x52, 0x47, 0x33, 0xab, 0x8f, 0x59, 0x3d, 0xab, 0xcd, 0x62, 0xb3, 0x57,
+ 0x16, 0x39, 0xd6, 0x24, 0xe6, 0x51, 0x52, 0xab, 0x8f, 0x53, 0x0c, 0x35, 0x9f, 0x08, 0x61, 0xd8,
+ 0x07, 0xca, 0x0d, 0xbf, 0x50, 0x0d, 0x6a, 0x61, 0x56, 0xa3, 0x8e, 0x08, 0x8a, 0x22, 0xb6, 0x5e,
+ 0x52, 0xbc, 0x51, 0x4d, 0x16, 0xcc, 0xf8, 0x06, 0x81, 0x8c, 0xe9, 0x1a, 0xb7, 0x79, 0x37, 0x36,
+ 0x5a, 0xf9, 0x0b, 0xbf, 0x74, 0xa3, 0x5b, 0xe6, 0xb4, 0x0b, 0x8e, 0xed, 0xf2, 0x78, 0x5e, 0x42,
+ 0x87, 0x4d,
+};
+
+assert(cypherbytes == cypherbytes_expect, "encrypt failure %v != %v\n", cypherbytes, cypherbytes_expect);
+
+int[dim(plainbytes)] recoverbytes;
+
+ChaCha::encrypt(&encrypt_state, &cypherbytes, &recoverbytes);
+
+string recovertext = String::new(recoverbytes);
+
+printf("%s\n", recovertext);
+
+assert(recovertext == plaintext, "decrypt failure %v != %v\n", recovertext, plaintext);
+
More information about the Nickle
mailing list