commit b93bc49b99c75182e3281863d16e21d3c36a5f1c
parent a2447c471d352eae8fcd272bab37291e52644ff3
Author: Thomas Bracht Laumann Jespersen <t@laumann.xyz>
Date: Thu, 4 Nov 2021 12:39:28 +0100
crypto/curve25519: New module
This implementation is based on the Martin Kleppmann paper "Implementing
Curve25519/X25519: A Tutorial on Elliptic Curve Cryptography" [0] in
which the author outlines a C implementation that is both fast and
constant-time. The C implementation itself is based on TweetNaCl [1].
Different implementations were consulted for inputs on this
implementation, in particular the Go implementation [1] and the OpenSSL
implementation [2].
[0]: https://martin.kleppmann.com/papers/curve25519.pdf
[1]: https://tweetnacl.cr.yp.to/
[2]: https://github.com/golang/crypto/blob/master/curve25519/curve25519.go
[3]: https://github.com/openssl/openssl/blob/master/crypto/ec/curve25519.c
Diffstat:
5 files changed, 483 insertions(+), 0 deletions(-)
diff --git a/crypto/curve25519/+test.ha b/crypto/curve25519/+test.ha
@@ -0,0 +1,229 @@
+use bytes;
+use fmt;
+use io;
+use encoding::hex;
+use crypto::random;
+
+@test fn unpack25519() void = {
+ let in: [SCALARSZ]u8 = [1u8...];
+
+ let fe = unpack25519(&in);
+ let expected: elem = [257...];
+
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ assert(fe[i] == expected[i]);
+ };
+};
+
+@test fn subfe() void = {
+ let in: [SCALARSZ]u8 = [1u8...];
+ let in2: [SCALARSZ]u8 = [3u8...];
+
+ let fe = unpack25519(&in);
+ let fe2 = unpack25519(&in2);
+
+ let out: elem = [0...];
+
+ subfe(&out, &fe2, &fe);
+
+ let e2: elem = [514...];
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ assert(out[i] == e2[i]);
+ };
+};
+
+@test fn swap25519() void = {
+ let pin: [SCALARSZ]u8 = [1u8...];
+ let qin: [SCALARSZ]u8 = [3u8...];
+
+ let p = unpack25519(&pin);
+ let q = unpack25519(&qin);
+
+ swap25519(&p, &q, 1);
+
+ let expected = unpack25519(&qin);
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ assert(p[i] == expected[i]);
+ };
+
+ expected = unpack25519(&pin);
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ assert(q[i] == expected[i]);
+ };
+
+ swap25519(&p, &q, 0); // nop
+
+ let expected = unpack25519(&qin);
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ assert(p[i] == expected[i]);
+ };
+
+ expected = unpack25519(&pin);
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ assert(q[i] == expected[i]);
+ };
+};
+
+@test fn unpackpack() void = {
+ let in: [SCALARSZ]u8 = [1u8...];
+
+ let fe = unpack25519(&in);
+ let expected: elem = [257...];
+
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ assert(fe[i] == expected[i]);
+ };
+
+ let out: [SCALARSZ]u8 = [0u8...];
+ pack25519(&out, &fe);
+
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ assert(in[i] == out[i]);
+ };
+
+};
+
+@test fn x25519basepoint() void = {
+ let x: [SCALARSZ]u8 = [1, 0...];
+ let out: [SCALARSZ]u8 = [0...];
+
+ for (let i = 0z; i < 200; i += 1) {
+ x25519(&out, &x, &BASEPOINT);
+ x[..] = out[..];
+ };
+
+ let hex = hex::encodestr(out[..]);
+ const expectedhex = "89161fde887b2b53de549af483940106ecc114d6982daa98256de23bdf77661a";
+ if (hex != expectedhex) {
+ fmt::errorfln("\ngot {}, want {}", hex, expectedhex)!;
+ abort();
+ };
+
+};
+
+@test fn vectors() void = {
+ const vectors = [(
+ [0x66u8, 0x8f, 0xb9, 0xf7, 0x6a, 0xd9, 0x71, 0xc8, 0x1a, 0xc9, 0x0, 0x7, 0x1a, 0x15, 0x60, 0xbc, 0xe2, 0xca, 0x0, 0xca, 0xc7, 0xe6, 0x7a, 0xf9, 0x93, 0x48, 0x91, 0x37, 0x61, 0x43, 0x40, 0x14], // in
+ [0xdbu8, 0x5f, 0x32, 0xb7, 0xf8, 0x41, 0xe7, 0xa1, 0xa0, 0x9, 0x68, 0xef, 0xfd, 0xed, 0x12, 0x73, 0x5f, 0xc4, 0x7a, 0x3e, 0xb1, 0x3b, 0x57, 0x9a, 0xac, 0xad, 0xea, 0xe8, 0x9, 0x39, 0xa7, 0xdd], // base
+ [0x9u8, 0xd, 0x85, 0xe5, 0x99, 0xea, 0x8e, 0x2b, 0xee, 0xb6, 0x13, 0x4, 0xd3, 0x7b, 0xe1, 0xe, 0xc5, 0xc9, 0x5, 0xf9, 0x92, 0x7d, 0x32, 0xf4, 0x2a, 0x9a, 0xa, 0xfb, 0x3e, 0xb, 0x40, 0x74], // expect
+ ),
+ (
+ [0x63, 0x66, 0x95, 0xe3, 0x4f, 0x75, 0xb9, 0xa2, 0x79, 0xc8, 0x70, 0x6f, 0xad, 0x12, 0x89, 0xf2, 0xc0, 0xb1, 0xe2, 0x2e, 0x16, 0xf8, 0xb8, 0x86, 0x17, 0x29, 0xc1, 0xa, 0x58, 0x29, 0x58, 0xaf],
+ [0x9, 0xd, 0x7, 0x1, 0xf8, 0xfd, 0xe2, 0x8f, 0x70, 0x4, 0x3b, 0x83, 0xf2, 0x34, 0x62, 0x25, 0x41, 0x9b, 0x18, 0xa7, 0xf2, 0x7e, 0x9e, 0x3d, 0x2b, 0xfd, 0x4, 0xe1, 0xf, 0x3d, 0x21, 0x3e],
+ [0xbf, 0x26, 0xec, 0x7e, 0xc4, 0x13, 0x6, 0x17, 0x33, 0xd4, 0x40, 0x70, 0xea, 0x67, 0xca, 0xb0, 0x2a, 0x85, 0xdc, 0x1b, 0xe8, 0xcf, 0xe1, 0xff, 0x73, 0xd5, 0x41, 0xcc, 0x8, 0x32, 0x55, 0x6],
+ ),
+ (
+ [0x73, 0x41, 0x81, 0xcd, 0x1a, 0x94, 0x6, 0x52, 0x2a, 0x56, 0xfe, 0x25, 0xe4, 0x3e, 0xcb, 0xf0, 0x29, 0x5d, 0xb5, 0xdd, 0xd0, 0x60, 0x9b, 0x3c, 0x2b, 0x4e, 0x79, 0xc0, 0x6f, 0x8b, 0xd4, 0x6d],
+ [0xf8, 0xa8, 0x42, 0x1c, 0x7d, 0x21, 0xa9, 0x2d, 0xb3, 0xed, 0xe9, 0x79, 0xe1, 0xfa, 0x6a, 0xcb, 0x6, 0x2b, 0x56, 0xb1, 0x88, 0x5c, 0x71, 0xc5, 0x11, 0x53, 0xcc, 0xb8, 0x80, 0xac, 0x73, 0x15],
+ [0x11, 0x76, 0xd0, 0x16, 0x81, 0xf2, 0xcf, 0x92, 0x9d, 0xa2, 0xc7, 0xa3, 0xdf, 0x66, 0xb5, 0xd7, 0x72, 0x9f, 0xd4, 0x22, 0x22, 0x6f, 0xd6, 0x37, 0x42, 0x16, 0xbf, 0x7e, 0x2, 0xfd, 0xf, 0x62],
+ ),
+ (
+ [0x1f, 0x70, 0x39, 0x1f, 0x6b, 0xa8, 0x58, 0x12, 0x94, 0x13, 0xbd, 0x80, 0x1b, 0x12, 0xac, 0xbf, 0x66, 0x23, 0x62, 0x82, 0x5c, 0xa2, 0x50, 0x9c, 0x81, 0x87, 0x59, 0xa, 0x2b, 0xe, 0x61, 0x72],
+ [0xd3, 0xea, 0xd0, 0x7a, 0x0, 0x8, 0xf4, 0x45, 0x2, 0xd5, 0x80, 0x8b, 0xff, 0xc8, 0x97, 0x9f, 0x25, 0xa8, 0x59, 0xd5, 0xad, 0xf4, 0x31, 0x2e, 0xa4, 0x87, 0x48, 0x9c, 0x30, 0xe0, 0x1b, 0x3b],
+ [0xf8, 0x48, 0x2f, 0x2e, 0x9e, 0x58, 0xbb, 0x6, 0x7e, 0x86, 0xb2, 0x87, 0x24, 0xb3, 0xc0, 0xa3, 0xbb, 0xb5, 0x7, 0x3e, 0x4c, 0x6a, 0xcd, 0x93, 0xdf, 0x54, 0x5e, 0xff, 0xdb, 0xba, 0x50, 0x5f],
+ ),
+ (
+ [0x3a, 0x7a, 0xe6, 0xcf, 0x8b, 0x88, 0x9d, 0x2b, 0x7a, 0x60, 0xa4, 0x70, 0xad, 0x6a, 0xd9, 0x99, 0x20, 0x6b, 0xf5, 0x7d, 0x90, 0x30, 0xdd, 0xf7, 0xf8, 0x68, 0xc, 0x8b, 0x1a, 0x64, 0x5d, 0xaa],
+ [0x4d, 0x25, 0x4c, 0x80, 0x83, 0xd8, 0x7f, 0x1a, 0x9b, 0x3e, 0xa7, 0x31, 0xef, 0xcf, 0xf8, 0xa6, 0xf2, 0x31, 0x2d, 0x6f, 0xed, 0x68, 0xe, 0xf8, 0x29, 0x18, 0x51, 0x61, 0xc8, 0xfc, 0x50, 0x60],
+ [0x47, 0xb3, 0x56, 0xd5, 0x81, 0x8d, 0xe8, 0xef, 0xac, 0x77, 0x4b, 0x71, 0x4c, 0x42, 0xc4, 0x4b, 0xe6, 0x85, 0x23, 0xdd, 0x57, 0xdb, 0xd7, 0x39, 0x62, 0xd5, 0xa5, 0x26, 0x31, 0x87, 0x62, 0x37],
+ ),
+ (
+ [0x20, 0x31, 0x61, 0xc3, 0x15, 0x9a, 0x87, 0x6a, 0x2b, 0xea, 0xec, 0x29, 0xd2, 0x42, 0x7f, 0xb0, 0xc7, 0xc3, 0xd, 0x38, 0x2c, 0xd0, 0x13, 0xd2, 0x7c, 0xc3, 0xd3, 0x93, 0xdb, 0xd, 0xaf, 0x6f],
+ [0x6a, 0xb9, 0x5d, 0x1a, 0xbe, 0x68, 0xc0, 0x9b, 0x0, 0x5c, 0x3d, 0xb9, 0x4, 0x2c, 0xc9, 0x1a, 0xc8, 0x49, 0xf7, 0xe9, 0x4a, 0x2a, 0x4a, 0x9b, 0x89, 0x36, 0x78, 0x97, 0xb, 0x7b, 0x95, 0xbf],
+ [0x11, 0xed, 0xae, 0xdc, 0x95, 0xff, 0x78, 0xf5, 0x63, 0xa1, 0xc8, 0xf1, 0x55, 0x91, 0xc0, 0x71, 0xde, 0xa0, 0x92, 0xb4, 0xd7, 0xec, 0xaa, 0xc8, 0xe0, 0x38, 0x7b, 0x5a, 0x16, 0xc, 0x4e, 0x5d],
+ ),
+ (
+ [0x13, 0xd6, 0x54, 0x91, 0xfe, 0x75, 0xf2, 0x3, 0xa0, 0x8, 0xb4, 0x41, 0x5a, 0xbc, 0x60, 0xd5, 0x32, 0xe6, 0x95, 0xdb, 0xd2, 0xf1, 0xe8, 0x3, 0xac, 0xcb, 0x34, 0xb2, 0xb7, 0x2c, 0x3d, 0x70],
+ [0x2e, 0x78, 0x4e, 0x4, 0xca, 0x0, 0x73, 0x33, 0x62, 0x56, 0xa8, 0x39, 0x25, 0x5e, 0xd2, 0xf7, 0xd4, 0x79, 0x6a, 0x64, 0xcd, 0xc3, 0x7f, 0x1e, 0xb0, 0xe5, 0xc4, 0xc8, 0xd1, 0xd1, 0xe0, 0xf5],
+ [0x56, 0x3e, 0x8c, 0x9a, 0xda, 0xa7, 0xd7, 0x31, 0x1, 0xb0, 0xf2, 0xea, 0xd3, 0xca, 0xe1, 0xea, 0x5d, 0x8f, 0xcd, 0x5c, 0xd3, 0x60, 0x80, 0xbb, 0x8e, 0x6e, 0xc0, 0x3d, 0x61, 0x45, 0x9, 0x17],
+ ),
+ (
+ [0x68, 0x6f, 0x7d, 0xa9, 0x3b, 0xf2, 0x68, 0xe5, 0x88, 0x6, 0x98, 0x31, 0xf0, 0x47, 0x16, 0x3f, 0x33, 0x58, 0x99, 0x89, 0xd0, 0x82, 0x6e, 0x98, 0x8, 0xfb, 0x67, 0x8e, 0xd5, 0x7e, 0x67, 0x49],
+ [0x8b, 0x54, 0x9b, 0x2d, 0xf6, 0x42, 0xd3, 0xb2, 0x5f, 0xe8, 0x38, 0xf, 0x8c, 0xc4, 0x37, 0x5f, 0x99, 0xb7, 0xbb, 0x4d, 0x27, 0x5f, 0x77, 0x9f, 0x3b, 0x7c, 0x81, 0xb8, 0xa2, 0xbb, 0xc1, 0x29],
+ [0x1, 0x47, 0x69, 0x65, 0x42, 0x6b, 0x61, 0x71, 0x74, 0x9a, 0x8a, 0xdd, 0x92, 0x35, 0x2, 0x5c, 0xe5, 0xf5, 0x57, 0xfe, 0x40, 0x9, 0xf7, 0x39, 0x30, 0x44, 0xeb, 0xbb, 0x8a, 0xe9, 0x52, 0x79],
+ ),
+ (
+ [0x82, 0xd6, 0x1c, 0xce, 0xdc, 0x80, 0x6a, 0x60, 0x60, 0xa3, 0x34, 0x9a, 0x5e, 0x87, 0xcb, 0xc7, 0xac, 0x11, 0x5e, 0x4f, 0x87, 0x77, 0x62, 0x50, 0xae, 0x25, 0x60, 0x98, 0xa7, 0xc4, 0x49, 0x59],
+ [0x8b, 0x6b, 0x9d, 0x8, 0xf6, 0x1f, 0xc9, 0x1f, 0xe8, 0xb3, 0x29, 0x53, 0xc4, 0x23, 0x40, 0xf0, 0x7, 0xb5, 0x71, 0xdc, 0xb0, 0xa5, 0x6d, 0x10, 0x72, 0x4e, 0xce, 0xf9, 0x95, 0xc, 0xfb, 0x25],
+ [0x9c, 0x49, 0x94, 0x1f, 0x9c, 0x4f, 0x18, 0x71, 0xfa, 0x40, 0x91, 0xfe, 0xd7, 0x16, 0xd3, 0x49, 0x99, 0xc9, 0x52, 0x34, 0xed, 0xf2, 0xfd, 0xfb, 0xa6, 0xd1, 0x4a, 0x5a, 0xfe, 0x9e, 0x5, 0x58],
+ ),
+ (
+ [0x7d, 0xc7, 0x64, 0x4, 0x83, 0x13, 0x97, 0xd5, 0x88, 0x4f, 0xdf, 0x6f, 0x97, 0xe1, 0x74, 0x4c, 0x9e, 0xb1, 0x18, 0xa3, 0x1a, 0x7b, 0x23, 0xf8, 0xd7, 0x9f, 0x48, 0xce, 0x9c, 0xad, 0x15, 0x4b],
+ [0x1a, 0xcd, 0x29, 0x27, 0x84, 0xf4, 0x79, 0x19, 0xd4, 0x55, 0xf8, 0x87, 0x44, 0x83, 0x58, 0x61, 0xb, 0xb9, 0x45, 0x96, 0x70, 0xeb, 0x99, 0xde, 0xe4, 0x60, 0x5, 0xf6, 0x89, 0xca, 0x5f, 0xb6],
+ [0x0, 0xf4, 0x3c, 0x2, 0x2e, 0x94, 0xea, 0x38, 0x19, 0xb0, 0x36, 0xae, 0x2b, 0x36, 0xb2, 0xa7, 0x61, 0x36, 0xaf, 0x62, 0x8a, 0x75, 0x1f, 0xe5, 0xd0, 0x1e, 0x3, 0xd, 0x44, 0x25, 0x88, 0x59],
+ ),
+ (
+ [0xfb, 0xc4, 0x51, 0x1d, 0x23, 0xa6, 0x82, 0xae, 0x4e, 0xfd, 0x8, 0xc8, 0x17, 0x9c, 0x1c, 0x6, 0x7f, 0x9c, 0x8b, 0xe7, 0x9b, 0xbc, 0x4e, 0xff, 0x5c, 0xe2, 0x96, 0xc6, 0xbc, 0x1f, 0xf4, 0x45],
+ [0x55, 0xca, 0xff, 0x21, 0x81, 0xf2, 0x13, 0x6b, 0xe, 0xd0, 0xe1, 0xe2, 0x99, 0x44, 0x48, 0xe1, 0x6c, 0xc9, 0x70, 0x64, 0x6a, 0x98, 0x3d, 0x14, 0xd, 0xc4, 0xea, 0xb3, 0xd9, 0x4c, 0x28, 0x4e],
+ [0xae, 0x39, 0xd8, 0x16, 0x53, 0x23, 0x45, 0x79, 0x4d, 0x26, 0x91, 0xe0, 0x80, 0x1c, 0xaa, 0x52, 0x5f, 0xc3, 0x63, 0x4d, 0x40, 0x2c, 0xe9, 0x58, 0xb, 0x33, 0x38, 0xb4, 0x6f, 0x8b, 0xb9, 0x72],
+ ),
+ (
+ [0x4e, 0x6, 0xc, 0xe1, 0xc, 0xeb, 0xf0, 0x95, 0x9, 0x87, 0x16, 0xc8, 0x66, 0x19, 0xeb, 0x9f, 0x7d, 0xf6, 0x65, 0x24, 0x69, 0x8b, 0xa7, 0x98, 0x8c, 0x3b, 0x90, 0x95, 0xd9, 0xf5, 0x1, 0x34],
+ [0x57, 0x73, 0x3f, 0x2d, 0x86, 0x96, 0x90, 0xd0, 0xd2, 0xed, 0xae, 0xc9, 0x52, 0x3d, 0xaa, 0x2d, 0xa9, 0x54, 0x45, 0xf4, 0x4f, 0x57, 0x83, 0xc1, 0xfa, 0xec, 0x6c, 0x3a, 0x98, 0x28, 0x18, 0xf3],
+ [0xa6, 0x1e, 0x74, 0x55, 0x2c, 0xce, 0x75, 0xf5, 0xe9, 0x72, 0xe4, 0x24, 0xf2, 0xcc, 0xb0, 0x9c, 0x83, 0xbc, 0x1b, 0x67, 0x1, 0x47, 0x48, 0xf0, 0x2c, 0x37, 0x1a, 0x20, 0x9e, 0xf2, 0xfb, 0x2c],
+ ),
+ (
+ [0x5c, 0x49, 0x2c, 0xba, 0x2c, 0xc8, 0x92, 0x48, 0x8a, 0x9c, 0xeb, 0x91, 0x86, 0xc2, 0xaa, 0xc2, 0x2f, 0x1, 0x5b, 0xf3, 0xef, 0x8d, 0x3e, 0xcc, 0x9c, 0x41, 0x76, 0x97, 0x62, 0x61, 0xaa, 0xb1],
+ [0x67, 0x97, 0xc2, 0xe7, 0xdc, 0x92, 0xcc, 0xbe, 0x7c, 0x5, 0x6b, 0xec, 0x35, 0xa, 0xb6, 0xd3, 0xbd, 0x2a, 0x2c, 0x6b, 0xc5, 0xa8, 0x7, 0xbb, 0xca, 0xe1, 0xf6, 0xc2, 0xaf, 0x80, 0x36, 0x44],
+ [0xfc, 0xf3, 0x7, 0xdf, 0xbc, 0x19, 0x2, 0xb, 0x28, 0xa6, 0x61, 0x8c, 0x6c, 0x62, 0x2f, 0x31, 0x7e, 0x45, 0x96, 0x7d, 0xac, 0xf4, 0xae, 0x4a, 0xa, 0x69, 0x9a, 0x10, 0x76, 0x9f, 0xde, 0x14],
+ ),
+ (
+ [0xea, 0x33, 0x34, 0x92, 0x96, 0x5, 0x5a, 0x4e, 0x8b, 0x19, 0x2e, 0x3c, 0x23, 0xc5, 0xf4, 0xc8, 0x44, 0x28, 0x2a, 0x3b, 0xfc, 0x19, 0xec, 0xc9, 0xdc, 0x64, 0x6a, 0x42, 0xc3, 0x8d, 0xc2, 0x48],
+ [0x2c, 0x75, 0xd8, 0x51, 0x42, 0xec, 0xad, 0x3e, 0x69, 0x44, 0x70, 0x4, 0x54, 0xc, 0x1c, 0x23, 0x54, 0x8f, 0xc8, 0xf4, 0x86, 0x25, 0x1b, 0x8a, 0x19, 0x46, 0x3f, 0x3d, 0xf6, 0xf8, 0xac, 0x61],
+ [0x5d, 0xca, 0xb6, 0x89, 0x73, 0xf9, 0x5b, 0xd3, 0xae, 0x4b, 0x34, 0xfa, 0xb9, 0x49, 0xfb, 0x7f, 0xb1, 0x5a, 0xf1, 0xd8, 0xca, 0xe2, 0x8c, 0xd6, 0x99, 0xf9, 0xc1, 0xaa, 0x33, 0x37, 0x34, 0x2f],
+ ),
+ (
+ [0x4f, 0x29, 0x79, 0xb1, 0xec, 0x86, 0x19, 0xe4, 0x5c, 0xa, 0xb, 0x2b, 0x52, 0x9, 0x34, 0x54, 0x1a, 0xb9, 0x44, 0x7, 0xb6, 0x4d, 0x19, 0xa, 0x76, 0xf3, 0x23, 0x14, 0xef, 0xe1, 0x84, 0xe7],
+ [0xf7, 0xca, 0xe1, 0x8d, 0x8d, 0x36, 0xa7, 0xf5, 0x61, 0x17, 0xb8, 0xb7, 0xe, 0x25, 0x52, 0x27, 0x7f, 0xfc, 0x99, 0xdf, 0x87, 0x56, 0xb5, 0xe1, 0x38, 0xbf, 0x63, 0x68, 0xbc, 0x87, 0xf7, 0x4c],
+ [0xe4, 0xe6, 0x34, 0xeb, 0xb4, 0xfb, 0x66, 0x4f, 0xe8, 0xb2, 0xcf, 0xa1, 0x61, 0x5f, 0x0, 0xe6, 0x46, 0x6f, 0xff, 0x73, 0x2c, 0xe1, 0xf8, 0xa0, 0xc8, 0xd2, 0x72, 0x74, 0x31, 0xd1, 0x6f, 0x14],
+ ),
+ (
+ [0xf5, 0xd8, 0xa9, 0x27, 0x90, 0x1d, 0x4f, 0xa4, 0x24, 0x90, 0x86, 0xb7, 0xff, 0xec, 0x24, 0xf5, 0x29, 0x7d, 0x80, 0x11, 0x8e, 0x4a, 0xc9, 0xd3, 0xfc, 0x9a, 0x82, 0x37, 0x95, 0x1e, 0x3b, 0x7f],
+ [0x3c, 0x23, 0x5e, 0xdc, 0x2, 0xf9, 0x11, 0x56, 0x41, 0xdb, 0xf5, 0x16, 0xd5, 0xde, 0x8a, 0x73, 0x5d, 0x6e, 0x53, 0xe2, 0x2a, 0xa2, 0xac, 0x14, 0x36, 0x56, 0x4, 0x5f, 0xf2, 0xe9, 0x52, 0x49],
+ [0xab, 0x95, 0x15, 0xab, 0x14, 0xaf, 0x9d, 0x27, 0xe, 0x1d, 0xae, 0xc, 0x56, 0x80, 0xcb, 0xc8, 0x88, 0xb, 0xd8, 0xa8, 0xe7, 0xeb, 0x67, 0xb4, 0xda, 0x42, 0xa6, 0x61, 0x96, 0x1e, 0xfc, 0xb],
+ )];
+
+ for (let i = 0z; i < len(vectors); i += 1) {
+ let got: [SCALARSZ]u8 = [0...];
+ scalarmult(&got, &vectors[i].0, &vectors[i].1);
+ if (!bytes::equal(got[..], vectors[i].2[..])) {
+ fmt::errorfln("Case i={} failed", i)!;
+ printvector("in", &vectors[i].0);
+ printvector("base", &vectors[i].1);
+ printvector("got", &got);
+ printvector("expect", &vectors[i].2);
+ abort();
+ };
+ };
+};
+
+@test fn highbitignored() void = {
+ let s: [SCALARSZ]u8 = [0...];
+ let u: [POINTSZ]u8 = [0...];
+
+ // FIXME(laumann): check that enough was read
+ io::read(random::stream, s[..])!;
+ io::read(random::stream, u[..])!;
+
+ let hi0: [32]u8 = [0...];
+ let hi1: [32]u8 = [0...];
+
+ u[31] &= 0x7f;
+ scalarmult(&hi0, &s, &u);
+
+ u[31] |= 0x80;
+ scalarmult(&hi1, &s, &u);
+
+ if (!bytes::equal(hi0[..], hi1[..])) {
+ fmt::errorfln("high bit of group point should not affect result")!;
+ abort();
+ };
+};
+
+fn printvector(name: str, vec: const *[SCALARSZ]u8) void = {
+ fmt::errorf("{:6} = [", name)!;
+ for (let i = 0z; i < 31; i += 1) {
+ fmt::errorf("{:02x}, ", vec[i])!;
+ };
+ fmt::errorfln("{:02x}]", vec[31])!;
+};
diff --git a/crypto/curve25519/README b/crypto/curve25519/README
@@ -0,0 +1,5 @@
+The curve25519 module implements the x25519 function which performs scalar
+multiplication on the elliptic curve known as Curve25519. See RFC 7748.
+
+The implementation is based on the paper "Implementing Curve25519/X25519: A
+Tutorial on Elliptic Curve Cryptography" by Martin Kleppmann.
diff --git a/crypto/curve25519/curve25519.ha b/crypto/curve25519/curve25519.ha
@@ -0,0 +1,204 @@
+// Implements the curve25519 elliptic curve
+
+// Implementations used for reference
+//
+// Kleppmann: https://martin.kleppmann.com/papers/curve25519.pdf
+// OpenSSL: https://github.com/openssl/openssl/blob/master/crypto/ec/curve25519.c
+// Go: https://github.com/golang/crypto/blob/master/curve25519/curve25519.go
+// TweetNaCl: https://tweetnacl.cr.yp.to/
+
+// The size of the scalar input to X25519.
+export def SCALARSZ: size = 32;
+
+// The size of the point input to X25519.
+export def POINTSZ: size = 32;
+
+// The canonical Curve25519 generator
+export const BASEPOINT: [POINTSZ]u8 = [9, 0...];
+
+// Compute the result of the scalar multiplication (scalar * point) and put the
+// result in out.
+export fn x25519(
+ out: *[SCALARSZ]u8,
+ scalar: const *[SCALARSZ]u8,
+ point: const *[POINTSZ]u8
+) void = {
+ scalarmult(out, scalar, point);
+};
+
+// Compute the result of the scalar multiplication (scalar * point) where point
+// is BASEPOINT.
+export fn scalarmult_base(
+ out: *[SCALARSZ]u8,
+ scalar: const *[SCALARSZ]u8
+) void = {
+ scalarmult(out, scalar, &BASEPOINT);
+};
+
+// Set out to the product (scalar * point)
+export fn scalarmult(
+ out: *[SCALARSZ]u8,
+ scalar: const *[SCALARSZ]u8,
+ point: const *[POINTSZ]u8
+) void = {
+ let clamped: [32]u8 = *scalar;
+ clamped[0] &= 0xf8;
+ clamped[31] = (clamped[31] & 0x7f) | 0x40;
+ let x = unpack25519(point);
+ let b: elem = *&x;
+ let a: elem = [1, 0...];
+ let c: elem = [0...];
+ let d: elem = [1, 0...];
+ let e: elem = [0...];
+ let f: elem = [0...];
+
+ for (let i = 254i; i >= 0; i -= 1) {
+ let iz = i : size;
+ let bit = ((clamped[iz >> 3] >> (iz & 7)) & 1) : i64;
+ swap25519(&a, &b, bit);
+ swap25519(&c, &d, bit);
+ addfe(&e, &a, &c);
+ subfe(&a, &a, &c);
+ addfe(&c, &b, &d);
+ subfe(&b, &b, &d);
+ mulfe(&d, &e, &e);
+ mulfe(&f, &a, &a);
+ mulfe(&a, &c, &a);
+ mulfe(&c, &b, &e);
+ addfe(&e, &a, &c);
+ subfe(&a, &a, &c);
+ mulfe(&b, &a, &a);
+ subfe(&c, &d, &f);
+ mulfe(&a, &c, &_121665);
+ addfe(&a, &a, &d);
+ mulfe(&c, &c, &a);
+ mulfe(&a, &d, &f);
+ mulfe(&d, &b, &x);
+ mulfe(&b, &e, &e);
+ swap25519(&a, &b, bit);
+ swap25519(&c, &d, bit);
+ };
+
+ invfe(&c, &c);
+ mulfe(&a, &a, &c);
+ pack25519(out, &a);
+};
+
+// An internal representation used for arithmetic operations.
+def FIELDSZ: size = 16;
+type elem = [FIELDSZ]i64;
+
+// Constant used in scalar multiplication.
+const _121665: elem = [0xdb41, 1, 0...];
+
+fn unpack25519(in: *[SCALARSZ]u8) elem = {
+ let fe: elem = [0...];
+
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ fe[i] = in[2 * i] : i64 + ((in[2 * i + 1] : i64) << 8);
+ };
+ fe[15] &= 0x7fff;
+
+ return fe;
+};
+
+fn carry25519(fe: *elem) void = {
+ let carry = 0i64;
+
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ carry = fe[i] >> 16;
+ fe[i] -= (carry << 16);
+ if (i < 15) {
+ fe[i + 1] += carry;
+ } else {
+ fe[0] += (38 * carry);
+ };
+ };
+};
+
+// Set out = a + b
+fn addfe(out: *elem, a: const *elem, b: const *elem) void = {
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ out[i] = a[i] + b[i];
+ };
+};
+
+// Set out = a - b
+fn subfe(out: *elem, a: const *elem, b: const *elem) void = {
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ out[i] = a[i] - b[i];
+ };
+};
+
+// Set out = a * b
+fn mulfe(out: *elem, a: const *elem, b: const *elem) void = {
+ let product: [31]i64 = [0...];
+
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ for (let j = 0z; j < FIELDSZ; j += 1) {
+ product[i + j] += a[i] * b[j];
+ };
+ };
+
+ for (let i = 0z; i < 15; i += 1) {
+ product[i] += (38 * product[i + 16]);
+ };
+ out[0..FIELDSZ] = product[0..FIELDSZ];
+
+ carry25519(out);
+ carry25519(out);
+};
+
+// Compute the multiplicative inverse
+fn invfe(out: *elem, a: const *elem) void = {
+ let c: elem = *a;
+ for (let i = 253i; i >= 0; i -= 1) {
+ mulfe(&c, &c, &c);
+ if (i != 2 && i != 4) {
+ mulfe(&c, &c, a);
+ };
+ };
+ out[..] = c[..];
+};
+
+// Swap inputs p and q, if bit is 1, do nothing if bit is 0.
+//
+// If bit is 1, this function swaps the content of parameters p and q (both in
+// elem representation), and it does nothing if bit is 0. As bit may be
+// part of a secret value, this function cannot use a simple if statement,
+// because that would not be constant-time
+fn swap25519(p: *elem, q: *elem, bit: i64) void = {
+ let c = ~(bit : u64 - 1) : i64;
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ let t = c & (p[i] ^ q[i]);
+ p[i] ^= t;
+ q[i] ^= t;
+ };
+};
+
+fn pack25519(out: *[SCALARSZ]u8, a: const *elem) void = {
+ let m: elem = [0...];
+ let t: elem = *a;
+
+ carry25519(&t);
+ carry25519(&t);
+ carry25519(&t);
+
+ for (let _i = 0z; _i < 2; _i += 1) {
+ m[0] = t[0] - 0xffed;
+ for (let i = 1z; i < 15; i += 1) {
+ m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1);
+ m[i - 1] &= 0xffff;
+ };
+ m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1);
+ let carry = (m[15] >> 16) & 1;
+ m[14] &= 0xffff;
+ swap25519(&t, &m, 1 - carry);
+ };
+
+ for (let i = 0z; i < FIELDSZ; i += 1) {
+ out[2 * i] = (t[i] & 0xff) : u8;
+ out[2 * i + 1] = (t[i] >> 8) : u8;
+ };
+};
+
diff --git a/scripts/gen-stdlib b/scripts/gen-stdlib
@@ -279,6 +279,17 @@ crypto_md5() {
fi
}
+crypto_curve25519() {
+ if [ $testing -eq 0 ]
+ then
+ gen_srcs crypto::curve25519 curve25519.ha
+ gen_ssa crypto::curve25519
+ else
+ gen_srcs crypto::curve25519 curve25519.ha +test.ha
+ gen_ssa crypto::curve25519 bytes fmt io encoding::hex crypto::random
+ fi
+}
+
dirs() {
gen_srcs dirs \
xdg.ha
@@ -1040,6 +1051,7 @@ crypto::md5
crypto::sha1
crypto::sha256
crypto::sha512
+crypto::curve25519
dirs
encoding::base64
encoding::hex
diff --git a/stdlib.mk b/stdlib.mk
@@ -192,6 +192,12 @@ stdlib_deps_any+=$(stdlib_crypto_sha512_any)
stdlib_crypto_sha512_linux=$(stdlib_crypto_sha512_any)
stdlib_crypto_sha512_freebsd=$(stdlib_crypto_sha512_any)
+# gen_lib crypto::curve25519 (any)
+stdlib_crypto_curve25519_any=$(HARECACHE)/crypto/curve25519/crypto_curve25519-any.o
+stdlib_deps_any+=$(stdlib_crypto_curve25519_any)
+stdlib_crypto_curve25519_linux=$(stdlib_crypto_curve25519_any)
+stdlib_crypto_curve25519_freebsd=$(stdlib_crypto_curve25519_any)
+
# gen_lib dirs (any)
stdlib_dirs_any=$(HARECACHE)/dirs/dirs-any.o
stdlib_deps_any+=$(stdlib_dirs_any)
@@ -709,6 +715,16 @@ $(HARECACHE)/crypto/sha512/crypto_sha512-any.ssa: $(stdlib_crypto_sha512_any_src
@HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Ncrypto::sha512 \
-t$(HARECACHE)/crypto/sha512/crypto_sha512.td $(stdlib_crypto_sha512_any_srcs)
+# crypto::curve25519 (+any)
+stdlib_crypto_curve25519_any_srcs= \
+ $(STDLIB)/crypto/curve25519/curve25519.ha
+
+$(HARECACHE)/crypto/curve25519/crypto_curve25519-any.ssa: $(stdlib_crypto_curve25519_any_srcs) $(stdlib_rt)
+ @printf 'HAREC \t$@\n'
+ @mkdir -p $(HARECACHE)/crypto/curve25519
+ @HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Ncrypto::curve25519 \
+ -t$(HARECACHE)/crypto/curve25519/crypto_curve25519.td $(stdlib_crypto_curve25519_any_srcs)
+
# dirs (+any)
stdlib_dirs_any_srcs= \
$(STDLIB)/dirs/xdg.ha
@@ -1821,6 +1837,12 @@ testlib_deps_any+=$(testlib_crypto_sha512_any)
testlib_crypto_sha512_linux=$(testlib_crypto_sha512_any)
testlib_crypto_sha512_freebsd=$(testlib_crypto_sha512_any)
+# gen_lib crypto::curve25519 (any)
+testlib_crypto_curve25519_any=$(TESTCACHE)/crypto/curve25519/crypto_curve25519-any.o
+testlib_deps_any+=$(testlib_crypto_curve25519_any)
+testlib_crypto_curve25519_linux=$(testlib_crypto_curve25519_any)
+testlib_crypto_curve25519_freebsd=$(testlib_crypto_curve25519_any)
+
# gen_lib dirs (any)
testlib_dirs_any=$(TESTCACHE)/dirs/dirs-any.o
testlib_deps_any+=$(testlib_dirs_any)
@@ -2345,6 +2367,17 @@ $(TESTCACHE)/crypto/sha512/crypto_sha512-any.ssa: $(testlib_crypto_sha512_any_sr
@HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Ncrypto::sha512 \
-t$(TESTCACHE)/crypto/sha512/crypto_sha512.td $(testlib_crypto_sha512_any_srcs)
+# crypto::curve25519 (+any)
+testlib_crypto_curve25519_any_srcs= \
+ $(STDLIB)/crypto/curve25519/curve25519.ha \
+ $(STDLIB)/crypto/curve25519/+test.ha
+
+$(TESTCACHE)/crypto/curve25519/crypto_curve25519-any.ssa: $(testlib_crypto_curve25519_any_srcs) $(testlib_rt) $(testlib_bytes_$(PLATFORM)) $(testlib_fmt_$(PLATFORM)) $(testlib_io_$(PLATFORM)) $(testlib_encoding_hex_$(PLATFORM)) $(testlib_crypto_random_$(PLATFORM))
+ @printf 'HAREC \t$@\n'
+ @mkdir -p $(TESTCACHE)/crypto/curve25519
+ @HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Ncrypto::curve25519 \
+ -t$(TESTCACHE)/crypto/curve25519/crypto_curve25519.td $(testlib_crypto_curve25519_any_srcs)
+
# dirs (+any)
testlib_dirs_any_srcs= \
$(STDLIB)/dirs/xdg.ha
