From 423e9e5dff7d2dc76816912afdc9f6846c7d2438 Mon Sep 17 00:00:00 2001 From: Matthew Endsley Date: Fri, 18 Dec 2020 17:59:52 -0800 Subject: [PATCH] Add x25519 primitive --- Hazel.UnitTests/Crypto/X25519Tests.cs | 297 +++++++++ Hazel.UnitTests/Hazel.UnitTests.csproj | 1 + Hazel/Crypto/X25519.cs | 844 +++++++++++++++++++++++++ Hazel/Hazel.csproj | 1 + 4 files changed, 1143 insertions(+) create mode 100644 Hazel.UnitTests/Crypto/X25519Tests.cs create mode 100644 Hazel/Crypto/X25519.cs diff --git a/Hazel.UnitTests/Crypto/X25519Tests.cs b/Hazel.UnitTests/Crypto/X25519Tests.cs new file mode 100644 index 0000000..8d9a583 --- /dev/null +++ b/Hazel.UnitTests/Crypto/X25519Tests.cs @@ -0,0 +1,297 @@ +// Copyright 2012 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +using Hazel.Crypto; +using Microsoft.VisualStudio.TestTools.UnitTesting; +using System.Security.Cryptography; + +namespace Hazel.UnitTests.Crypto +{ + [TestClass] + public class X25519Tests + { + private static readonly byte[][] LowOrderPoints = new byte[][] + { + new byte[]{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}, + new byte[]{0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}, + new byte[]{0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae, 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a, 0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd, 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00}, + new byte[]{0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24, 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b, 0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86, 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57}, + new byte[]{0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f}, + new byte[]{0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f}, + new byte[]{0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f}, + }; + + [TestMethod] + public void TestLowOrderPoints() + { + using (RandomNumberGenerator random = RandomNumberGenerator.Create()) + { + byte[] scalar = new byte[X25519.KeySize]; + random.GetBytes(scalar); + + for (int ii = 0, nn = LowOrderPoints.Length; ii != nn; ++ii) + { + ByteSpan output = new byte[X25519.KeySize]; + bool result = X25519.Func(output, scalar, LowOrderPoints[ii]); + Assert.IsFalse(result, $"Multiplication by low order point {ii} succeeded: should have failed"); + } + } + } + + [TestMethod] + public void TestVectors() + { + for (int ii = 0, nn = TestVectorData.Length; ii != nn; ++ii) + { + byte[] actual = new byte[32]; + bool result = X25519.Func(actual, TestVectorData[ii].In, TestVectorData[ii].Base); + Assert.IsTrue(result); + CollectionAssert.AreEqual(TestVectorData[ii].Expect, actual, $"Test vector {ii} mismatch"); + } + } + + [TestMethod] + public void TestAgreement() + { + using (RandomNumberGenerator random = RandomNumberGenerator.Create()) + { + byte[] clientPrivateKey = new byte[X25519.KeySize]; + random.GetBytes(clientPrivateKey); + + byte[] clientPublicKey = new byte[X25519.KeySize]; + X25519.Func(clientPublicKey, clientPrivateKey); + + byte[] serverPrivateKey = new byte[X25519.KeySize]; + random.GetBytes(serverPrivateKey); + + byte[] serverPublickey = new byte[X25519.KeySize]; + X25519.Func(serverPublickey, serverPrivateKey); + + // client key aggreement + byte[] clientSharedSecret = new byte[X25519.KeySize]; + Assert.IsTrue(X25519.Func(clientSharedSecret, clientPrivateKey, serverPublickey)); + + // server key agreement + byte[] serverSharedSecret = new byte[X25519.KeySize]; + Assert.IsTrue(X25519.Func(serverSharedSecret, serverPrivateKey, clientPublicKey)); + + CollectionAssert.AreEqual(clientSharedSecret, serverSharedSecret); + } + } + + private struct TestVector + { + public byte[] In; + public byte[] Base; + public byte[] Expect; + } + + private static readonly TestVector[] TestVectorData = + { + new TestVector { + In = new byte[]{0x66, 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}, + Base = new byte[]{0xdb, 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}, + Expect = new byte[]{0x9, 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + new TestVector { + In = new byte[]{ 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}, + Base = new byte[]{ 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}, + Expect = new byte[]{ 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}, + }, + }; + } + + [TestClass] + public class X25519FieldTests + { + private readonly byte[] A = {0x21, 0xDD, 0xB0, 0x43, 0xCF, 0xB2, 0xB3, 0xFE, 0xC4, 0xCC, 0xA3, 0x8B, 0xBA, 0x3D, 0xE1, 0x92, 0xDF, 0xEA, 0x85, 0xCE, 0x2B, 0x4A, 0xD8, 0x44, 0x95, 0xAA, 0xB1, 0x3A, 0x5B, 0x62, 0x87, 0x8E}; + private readonly byte[] B = {0x22, 0x8B, 0x2F, 0x48, 0x4B, 0x86, 0xAC, 0x9C, 0xA4, 0x7B, 0x64, 0xC4, 0x62, 0x76, 0x34, 0x7C, 0x67, 0xBD, 0x59, 0x6F, 0x8D, 0x18, 0x41, 0x4D, 0x96, 0x31, 0xA5, 0x5B, 0x3B, 0xA5, 0x7E, 0xC7}; + + [TestMethod] + public void Zero() + { + byte[] actual = new byte[X25519.KeySize]; + X25519.FieldElement fe = X25519.FieldElement.Zero(); + fe.CopyTo(actual); + + byte[] expected = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; + CollectionAssert.AreEqual(expected, actual); + } + + [TestMethod] + public void One() + { + byte[] actual = new byte[X25519.KeySize]; + X25519.FieldElement fe = X25519.FieldElement.One(); + fe.CopyTo(actual); + + byte[] expected = {0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; + CollectionAssert.AreEqual(expected, actual); + } + + [TestMethod] + public void Add() + { + X25519.FieldElement a = X25519.FieldElement.FromBytes(A); + X25519.FieldElement b = X25519.FieldElement.FromBytes(B); + + byte[] actual = new byte[X25519.KeySize]; + X25519.FieldElement c = new X25519.FieldElement(); + X25519.FieldElement.Add(ref c, ref a, ref b); + c.CopyTo(actual); + + byte[] expected = {0x43, 0x68, 0xE0, 0x8B, 0x1A, 0x39, 0x60, 0x9B, 0x69, 0x48, 0x08, 0x50, 0x1D, 0xB4, 0x15, 0x0F, 0x47, 0xA8, 0xDF, 0x3D, 0xB9, 0x62, 0x19, 0x92, 0x2B, 0xDC, 0x56, 0x96, 0x96, 0x07, 0x06, 0x56}; + CollectionAssert.AreEqual(expected, actual); + } + + [TestMethod] + public void Sub() + { + X25519.FieldElement a = X25519.FieldElement.FromBytes(A); + X25519.FieldElement b = X25519.FieldElement.FromBytes(B); + + byte[] actual = new byte[X25519.KeySize]; + X25519.FieldElement c = new X25519.FieldElement(); + X25519.FieldElement.Sub(ref c, ref a, ref b); + c.CopyTo(actual); + + byte[] expected = {0xEC, 0x51, 0x81, 0xFB, 0x83, 0x2C, 0x07, 0x62, 0x20, 0x51, 0x3F, 0xC7, 0x57, 0xC7, 0xAC, 0x16, 0x78, 0x2D, 0x2C, 0x5F, 0x9E, 0x31, 0x97, 0xF7, 0xFE, 0x78, 0x0C, 0xDF, 0x1F, 0xBD, 0x08, 0x47}; + CollectionAssert.AreEqual(expected, actual); + } + + [TestMethod] + public void Multiply() + { + X25519.FieldElement a = X25519.FieldElement.FromBytes(A); + X25519.FieldElement b = X25519.FieldElement.FromBytes(B); + + byte[] actual = new byte[X25519.KeySize]; + X25519.FieldElement c = new X25519.FieldElement(); + X25519.FieldElement.Multiply(ref c, ref a, ref b); + c.CopyTo(actual); + + byte[] expected = {0x1E, 0xBE, 0xBD, 0xE0, 0xEC, 0xB1, 0x3C, 0xDB, 0x50, 0x6E, 0xD6, 0x50, 0x02, 0x1A, 0x59, 0x99, 0xC1, 0xC0, 0xFC, 0xE0, 0xBF, 0xDB, 0x64, 0xB0, 0x3E, 0xB3, 0x2D, 0x43, 0x8B, 0x66, 0x43, 0x3C}; + CollectionAssert.AreEqual(expected, actual); + } + + [TestMethod] + public void Square() + { + X25519.FieldElement a = X25519.FieldElement.FromBytes(A); + + byte[] actual = new byte[X25519.KeySize]; + X25519.FieldElement c = new X25519.FieldElement(); + X25519.FieldElement.Square(ref c, ref a); + c.CopyTo(actual); + + byte[] expected = {0xAE, 0xB2, 0x22, 0xD4, 0x72, 0xF7, 0xF4, 0x09, 0xBB, 0x9A, 0xA9, 0x99, 0xEB, 0x7F, 0xC4, 0xE1, 0x4C, 0x0A, 0x53, 0xEB, 0x3C, 0xFF, 0x5C, 0xE2, 0xF6, 0x92, 0x46, 0x53, 0x29, 0xE1, 0x5D, 0x7A}; + CollectionAssert.AreEqual(expected, actual); + + + a = X25519.FieldElement.FromBytes(A); + X25519.FieldElement.Square(ref a, ref a); + a.CopyTo(actual); + + CollectionAssert.AreEqual(expected, actual); + } + + [TestMethod] + public void Multiply121666() + { + X25519.FieldElement a = X25519.FieldElement.FromBytes(A); + + byte[] actual = new byte[X25519.KeySize]; + X25519.FieldElement c = new X25519.FieldElement(); + X25519.FieldElement.Multiply121666(ref c, ref a); + c.CopyTo(actual); + + byte[] expected = {0x65, 0x3E, 0xE9, 0x9D, 0x08, 0xAC, 0x1A, 0x17, 0x61, 0x4F, 0x2C, 0xED, 0x30, 0x0B, 0x9B, 0xCB, 0x2B, 0x63, 0x53, 0xB9, 0x7D, 0x67, 0x62, 0x11, 0x39, 0xF1, 0x50, 0xC9, 0x6C, 0xA1, 0x66, 0x72}; + CollectionAssert.AreEqual(expected, actual); + } + + [TestMethod] + public void Invert() + { + X25519.FieldElement a = X25519.FieldElement.FromBytes(A); + + byte[] actual = new byte[X25519.KeySize]; + X25519.FieldElement c = new X25519.FieldElement(); + X25519.FieldElement.Invert(ref c, ref a); + c.CopyTo(actual); + + byte[] expected = {0x8E, 0x66, 0x2F, 0x60, 0xFC, 0xCD, 0x3A, 0x11, 0x36, 0xF5, 0xD9, 0xE6, 0x94, 0x28, 0x04, 0x2A, 0x6B, 0x5D, 0xC4, 0x72, 0x82, 0x30, 0xF3, 0x09, 0xC0, 0x24, 0xDE, 0xCD, 0x60, 0x3F, 0x5D, 0x17}; + CollectionAssert.AreEqual(expected, actual); + } + } +} diff --git a/Hazel.UnitTests/Hazel.UnitTests.csproj b/Hazel.UnitTests/Hazel.UnitTests.csproj index 4b14efc..89e20cf 100644 --- a/Hazel.UnitTests/Hazel.UnitTests.csproj +++ b/Hazel.UnitTests/Hazel.UnitTests.csproj @@ -57,6 +57,7 @@ + diff --git a/Hazel/Crypto/X25519.cs b/Hazel/Crypto/X25519.cs new file mode 100644 index 0000000..3f4624b --- /dev/null +++ b/Hazel/Crypto/X25519.cs @@ -0,0 +1,844 @@ +using System; +using System.Diagnostics; + +namespace Hazel.Crypto +{ + /// + /// The x25519 key agreement algorithm + /// + public static class X25519 + { + public const int KeySize = 32; + + /// + /// Element in the GF(2^255 - 19) field + /// + public partial struct FieldElement + { + public int x0, x1, x2, x3, x4; + public int x5, x6, x7, x8, x9; + }; + + private static readonly byte[] BasePoint = {9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + + /// + /// Performs the core x25519 function: Multiplying an EC point by a scalar value + /// + public static bool Func(ByteSpan output, ByteSpan scalar, ByteSpan point) + { + InternalFunc(output, scalar, point); + if (Const.ConstantCompareZeroSpan(output) == 1) + { + return false; + } + + return true; + } + + /// + /// Multiplies the base x25519 point by the provided scalar value + /// + public static void Func(ByteSpan output, ByteSpan scalar) + { + InternalFunc(output, scalar, BasePoint); + } + + // The FieldElement code below is ported from the original + // public domain reference implemtation of X25519 + // by D. J. Bernstien + // + // See: https://cr.yp.to/ecdh.html + + private static void InternalFunc(ByteSpan output, ByteSpan scalar, ByteSpan point) + { + if (output.Length != KeySize) + { + throw new ArgumentException("Invalid output size", nameof(output)); + } + else if (scalar.Length != KeySize) + { + throw new ArgumentException("Invalid scalar size", nameof(scalar)); + } + else if (point.Length != KeySize) + { + throw new ArgumentException("Invalid point size", nameof(point)); + } + + // copy the scalar so we can properly mask it + ByteSpan maskedScalar = new byte[32]; + scalar.CopyTo(maskedScalar); + maskedScalar[0] &= 248; + maskedScalar[31] &= 127; + maskedScalar[31] |= 64; + + FieldElement x1 = FieldElement.FromBytes(point); + FieldElement x2 = FieldElement.One(); + FieldElement x3 = x1; + FieldElement z2 = FieldElement.Zero(); + FieldElement z3 = FieldElement.One(); + + FieldElement tmp0 = new FieldElement(); + FieldElement tmp1 = new FieldElement(); + + int swap = 0; + for (int pos = 254; pos >= 0; --pos) + { + int b = (int)maskedScalar[pos / 8] >> (int)(pos % 8); + b &= 1; + swap ^= b; + + FieldElement.ConditionalSwap(ref x2, ref x3, swap); + FieldElement.ConditionalSwap(ref z2, ref z3, swap); + swap = b; + + FieldElement.Sub(ref tmp0, ref x3, ref z3); + FieldElement.Sub(ref tmp1, ref x2, ref z2); + FieldElement.Add(ref x2, ref x2, ref z2); + FieldElement.Add(ref z2, ref x3, ref z3); + FieldElement.Multiply(ref z3, ref tmp0, ref x2); + FieldElement.Multiply(ref z2, ref z2, ref tmp1); + FieldElement.Square(ref tmp0, ref tmp1); + FieldElement.Square(ref tmp1, ref x2); + FieldElement.Add(ref x3, ref z3, ref z2); + FieldElement.Sub(ref z2, ref z3, ref z2); + FieldElement.Multiply(ref x2, ref tmp1, ref tmp0); + FieldElement.Sub(ref tmp1, ref tmp1, ref tmp0); + FieldElement.Square(ref z2, ref z2); + FieldElement.Multiply121666(ref z3, ref tmp1); + FieldElement.Square(ref x3, ref x3); + FieldElement.Add(ref tmp0, ref tmp0, ref z3); + FieldElement.Multiply(ref z3, ref x1, ref z2); + FieldElement.Multiply(ref z2, ref tmp1, ref tmp0); + } + + FieldElement.ConditionalSwap(ref x2, ref x3, swap); + FieldElement.ConditionalSwap(ref z2, ref z3, swap); + + FieldElement.Invert(ref z2, ref z2); + FieldElement.Multiply(ref x2, ref x2, ref z2); + x2.CopyTo(output); + } + + + /// + /// Mathematical operators over GF(2^255 - 19) + /// + partial struct FieldElement + { + /// + /// Convert a byte array to a field element + /// + public static FieldElement FromBytes(ByteSpan bytes) + { + Debug.Assert(bytes.Length >= KeySize); + + long tmp0 = (long)bytes.ReadLittleEndian32(); + long tmp1 = (long)bytes.ReadLittleEndian24(4) << 6; + long tmp2 = (long)bytes.ReadLittleEndian24(7) << 5; + long tmp3 = (long)bytes.ReadLittleEndian24(10) << 3; + long tmp4 = (long)bytes.ReadLittleEndian24(13) << 2; + long tmp5 = (long)bytes.ReadLittleEndian32(16); + long tmp6 = (long)bytes.ReadLittleEndian24(20) << 7; + long tmp7 = (long)bytes.ReadLittleEndian24(23) << 5; + long tmp8 = (long)bytes.ReadLittleEndian24(26) << 4; + long tmp9 = (long)(bytes.ReadLittleEndian24(29) & 0x007FFFFF) << 2; + + long carry9 = (tmp9 + (1L<<24)) >> 25; + tmp0 += carry9 * 19; + tmp9 -= carry9 << 25; + long carry1 = (tmp1 + (1L<<24)) >> 25; + tmp2 += carry1; + tmp1 -= carry1 << 25; + long carry3 = (tmp3 + (1L<<24)) >> 25; + tmp4 += carry3; + tmp3 -= carry3 << 25; + long carry5 = (tmp5 + (1L<<24)) >> 25; + tmp6 += carry5; + tmp5 -= carry5 << 25; + long carry7 = (tmp7 + (1L<<24)) >> 25; + tmp8 += carry7; + tmp7 -= carry7 << 25; + + long carry0 = (tmp0 + (1L<<25)) >> 26; + tmp1 += carry0; + tmp0 -= carry0 << 26; + long carry2 = (tmp2 + (1L<<25)) >> 26; + tmp3 += carry2; + tmp2 -= carry2 << 26; + long carry4 = (tmp4 + (1L<<25)) >> 26; + tmp5 += carry4; + tmp4 -= carry4 << 26; + long carry6 = (tmp6 + (1L<<25)) >> 26; + tmp7 += carry6; + tmp6 -= carry6 << 26; + long carry8 = (tmp8 + (1L<<25)) >> 26; + tmp9 += carry8; + tmp8 -= carry8 << 26; + + return new FieldElement + { + x0 = (int)tmp0, + x1 = (int)tmp1, + x2 = (int)tmp2, + x3 = (int)tmp3, + x4 = (int)tmp4, + x5 = (int)tmp5, + x6 = (int)tmp6, + x7 = (int)tmp7, + x8 = (int)tmp8, + x9 = (int)tmp9, + }; + } + + /// + /// Convert the field element to a byte array + /// + public void CopyTo(ByteSpan output) + { + Debug.Assert(output.Length >= 32); + + long q = (19 * this.x9 + (1L << 24)) >> 25; + q = ((long)this.x0 + q) >> 26; + q = ((long)this.x1 + q) >> 25; + q = ((long)this.x2 + q) >> 26; + q = ((long)this.x3 + q) >> 25; + q = ((long)this.x4 + q) >> 26; + q = ((long)this.x5 + q) >> 25; + q = ((long)this.x6 + q) >> 26; + q = ((long)this.x7 + q) >> 25; + q = ((long)this.x8 + q) >> 26; + q = ((long)this.x9 + q) >> 25; + + this.x0 = (int)((long)this.x0 + (19L * q)); + + int carry0 = (int)(this.x0 >> 26); + this.x1 = (int)((int)this.x1 + carry0); + this.x0 = (int)((int)this.x0 - (carry0 << 26)); + int carry1 = (int)(this.x1 >> 25); + this.x2 = (int)((int)this.x2 + carry1); + this.x1 = (int)((int)this.x1 - (carry1 << 25)); + int carry2 = (int)(this.x2 >> 26); + this.x3 = (int)((int)this.x3 + carry2); + this.x2 = (int)((int)this.x2 - (carry2 << 26)); + int carry3 = (int)(this.x3 >> 25); + this.x4 = (int)((int)this.x4 + carry3); + this.x3 = (int)((int)this.x3 - (carry3 << 25)); + int carry4 = (int)(this.x4 >> 26); + this.x5 = (int)((int)this.x5 + carry4); + this.x4 = (int)((int)this.x4 - (carry4 << 26)); + int carry5 = (int)(this.x5 >> 25); + this.x6 = (int)((int)this.x6 + carry5); + this.x5 = (int)((int)this.x5 - (carry5 << 25)); + int carry6 = (int)(this.x6 >> 26); + this.x7 = (int)((int)this.x7 + carry6); + this.x6 = (int)((int)this.x6 - (carry6 << 26)); + int carry7 = (int)(this.x7 >> 25); + this.x8 = (int)((int)this.x8 + carry7); + this.x7 = (int)((int)this.x7 - (carry7 << 25)); + int carry8 = (int)(this.x8 >> 26); + this.x9 = (int)((int)this.x9 + carry8); + this.x8 = (int)((int)this.x8 - (carry8 << 26)); + int carry9 = (int)(this.x9 >> 25); + this.x9 = (int)((int)this.x9 - (carry9 << 25)); + + output[ 0] = (byte)(this.x0 >> 0); + output[ 1] = (byte)(this.x0 >> 8); + output[ 2] = (byte)(this.x0 >> 16); + output[ 3] = (byte)((this.x0 >> 24) | (this.x1 << 2)); + output[ 4] = (byte)(this.x1 >> 6); + output[ 5] = (byte)(this.x1 >> 14); + output[ 6] = (byte)((this.x1 >> 22) | (this.x2 << 3)); + output[ 7] = (byte)(this.x2 >> 5); + output[ 8] = (byte)(this.x2 >> 13); + output[ 9] = (byte)((this.x2 >> 21) | (this.x3 << 5)); + output[10] = (byte)(this.x3 >> 3); + output[11] = (byte)(this.x3 >> 11); + output[12] = (byte)((this.x3 >> 19) | (this.x4 << 6)); + output[13] = (byte)(this.x4 >> 2); + output[14] = (byte)(this.x4 >> 10); + output[15] = (byte)(this.x4 >> 18); + output[16] = (byte)(this.x5 >> 0); + output[17] = (byte)(this.x5 >> 8); + output[18] = (byte)(this.x5 >> 16); + output[19] = (byte)((this.x5 >> 24) | (this.x6 << 1)); + output[20] = (byte)(this.x6 >> 7); + output[21] = (byte)(this.x6 >> 15); + output[22] = (byte)((this.x6 >> 23) | (this.x7 << 3)); + output[23] = (byte)(this.x7 >> 5); + output[24] = (byte)(this.x7 >> 13); + output[25] = (byte)((this.x7 >> 21) | (this.x8 << 4)); + output[26] = (byte)(this.x8 >> 4); + output[27] = (byte)(this.x8 >> 12); + output[28] = (byte)((this.x8 >> 20) | (this.x9 << 6)); + output[29] = (byte)(this.x9 >> 2); + output[30] = (byte)(this.x9 >> 10); + output[31] = (byte)(this.x9 >> 18); + } + + /// + /// Set the field element to `0` + /// + public static FieldElement Zero() + { + return new FieldElement(); + } + + /// + /// Set the field element to `1` + /// + public static FieldElement One() + { + FieldElement result = Zero(); + result.x0 = 1; + return result; + } + + /// + /// Add two field elements + /// + public static void Add(ref FieldElement output, ref FieldElement a, ref FieldElement b) + { + output.x0 = a.x0 + b.x0; + output.x1 = a.x1 + b.x1; + output.x2 = a.x2 + b.x2; + output.x3 = a.x3 + b.x3; + output.x4 = a.x4 + b.x4; + output.x5 = a.x5 + b.x5; + output.x6 = a.x6 + b.x6; + output.x7 = a.x7 + b.x7; + output.x8 = a.x8 + b.x8; + output.x9 = a.x9 + b.x9; + } + + /// + /// Subtract two field elements + /// + public static void Sub(ref FieldElement output, ref FieldElement a, ref FieldElement b) + { + output.x0 = a.x0 - b.x0; + output.x1 = a.x1 - b.x1; + output.x2 = a.x2 - b.x2; + output.x3 = a.x3 - b.x3; + output.x4 = a.x4 - b.x4; + output.x5 = a.x5 - b.x5; + output.x6 = a.x6 - b.x6; + output.x7 = a.x7 - b.x7; + output.x8 = a.x8 - b.x8; + output.x9 = a.x9 - b.x9; + } + + /// + /// Multiply two field elements + /// + public static void Multiply(ref FieldElement output, ref FieldElement a, ref FieldElement b) + { + int b1_19 = 19 * b.x1; + int b2_19 = 19 * b.x2; + int b3_19 = 19 * b.x3; + int b4_19 = 19 * b.x4; + int b5_19 = 19 * b.x5; + int b6_19 = 19 * b.x6; + int b7_19 = 19 * b.x7; + int b8_19 = 19 * b.x8; + int b9_19 = 19 * b.x9; + + int a1_2 = 2 * a.x1; + int a3_2 = 2 * a.x3; + int a5_2 = 2 * a.x5; + int a7_2 = 2 * a.x7; + int a9_2 = 2 * a.x9; + + long a0b0 = (long)a.x0 * (long)b.x0; + long a0b1 = (long)a.x0 * (long)b.x1; + long a0b2 = (long)a.x0 * (long)b.x2; + long a0b3 = (long)a.x0 * (long)b.x3; + long a0b4 = (long)a.x0 * (long)b.x4; + long a0b5 = (long)a.x0 * (long)b.x5; + long a0b6 = (long)a.x0 * (long)b.x6; + long a0b7 = (long)a.x0 * (long)b.x7; + long a0b8 = (long)a.x0 * (long)b.x8; + long a0b9 = (long)a.x0 * (long)b.x9; + long a1b0 = (long)a.x1 * (long)b.x0; + long a1b1_2 = (long)a1_2 * (long)b.x1; + long a1b2 = (long)a.x1 * (long)b.x2; + long a1b3_2 = (long)a1_2 * (long)b.x3; + long a1b4 = (long)a.x1 * (long)b.x4; + long a1b5_2 = (long)a1_2 * (long)b.x5; + long a1b6 = (long)a.x1 * (long)b.x6; + long a1b7_2 = (long)a1_2 * (long)b.x7; + long a1b8 = (long)a.x1 * (long)b.x8; + long a1b9_38 = (long)a1_2 * (long)b9_19; + long a2b0 = (long)a.x2 * (long)b.x0; + long a2b1 = (long)a.x2 * (long)b.x1; + long a2b2 = (long)a.x2 * (long)b.x2; + long a2b3 = (long)a.x2 * (long)b.x3; + long a2b4 = (long)a.x2 * (long)b.x4; + long a2b5 = (long)a.x2 * (long)b.x5; + long a2b6 = (long)a.x2 * (long)b.x6; + long a2b7 = (long)a.x2 * (long)b.x7; + long a2b8_19 = (long)a.x2 * (long)b8_19; + long a2b9_19 = (long)a.x2 * (long)b9_19; + long a3b0 = (long)a.x3 * (long)b.x0; + long a3b1_2 = (long)a3_2 * (long)b.x1; + long a3b2 = (long)a.x3 * (long)b.x2; + long a3b3_2 = (long)a3_2 * (long)b.x3; + long a3b4 = (long)a.x3 * (long)b.x4; + long a3b5_2 = (long)a3_2 * (long)b.x5; + long a3b6 = (long)a.x3 * (long)b.x6; + long a3b7_38 = (long)a3_2 * (long)b7_19; + long a3b8_19 = (long)a.x3 * (long)b8_19; + long a3b9_38 = (long)a3_2 * (long)b9_19; + long a4b0 = (long)a.x4 * (long)b.x0; + long a4b1 = (long)a.x4 * (long)b.x1; + long a4b2 = (long)a.x4 * (long)b.x2; + long a4b3 = (long)a.x4 * (long)b.x3; + long a4b4 = (long)a.x4 * (long)b.x4; + long a4b5 = (long)a.x4 * (long)b.x5; + long a4b6_19 = (long)a.x4 * (long)b6_19; + long a4b7_19 = (long)a.x4 * (long)b7_19; + long a4b8_19 = (long)a.x4 * (long)b8_19; + long a4b9_19 = (long)a.x4 * (long)b9_19; + long a5b0 = (long)a.x5 * (long)b.x0; + long a5b1_2 = (long)a5_2 * (long)b.x1; + long a5b2 = (long)a.x5 * (long)b.x2; + long a5b3_2 = (long)a5_2 * (long)b.x3; + long a5b4 = (long)a.x5 * (long)b.x4; + long a5b5_38 = (long)a5_2 * (long)b5_19; + long a5b6_19 = (long)a.x5 * (long)b6_19; + long a5b7_38 = (long)a5_2 * (long)b7_19; + long a5b8_19 = (long)a.x5 * (long)b8_19; + long a5b9_38 = (long)a5_2 * (long)b9_19; + long a6b0 = (long)a.x6 * (long)b.x0; + long a6b1 = (long)a.x6 * (long)b.x1; + long a6b2 = (long)a.x6 * (long)b.x2; + long a6b3 = (long)a.x6 * (long)b.x3; + long a6b4_19 = (long)a.x6 * (long)b4_19; + long a6b5_19 = (long)a.x6 * (long)b5_19; + long a6b6_19 = (long)a.x6 * (long)b6_19; + long a6b7_19 = (long)a.x6 * (long)b7_19; + long a6b8_19 = (long)a.x6 * (long)b8_19; + long a6b9_19 = (long)a.x6 * (long)b9_19; + long a7b0 = (long)a.x7 * (long)b.x0; + long a7b1_2 = (long)a7_2 * (long)b.x1; + long a7b2 = (long)a.x7 * (long)b.x2; + long a7b3_38 = (long)a7_2 * (long)b3_19; + long a7b4_19 = (long)a.x7 * (long)b4_19; + long a7b5_38 = (long)a7_2 * (long)b5_19; + long a7b6_19 = (long)a.x7 * (long)b6_19; + long a7b7_38 = (long)a7_2 * (long)b7_19; + long a7b8_19 = (long)a.x7 * (long)b8_19; + long a7b9_38 = (long)a7_2 * (long)b9_19; + long a8b0 = (long)a.x8 * (long)b.x0; + long a8b1 = (long)a.x8 * (long)b.x1; + long a8b2_19 = (long)a.x8 * (long)b2_19; + long a8b3_19 = (long)a.x8 * (long)b3_19; + long a8b4_19 = (long)a.x8 * (long)b4_19; + long a8b5_19 = (long)a.x8 * (long)b5_19; + long a8b6_19 = (long)a.x8 * (long)b6_19; + long a8b7_19 = (long)a.x8 * (long)b7_19; + long a8b8_19 = (long)a.x8 * (long)b8_19; + long a8b9_19 = (long)a.x8 * (long)b9_19; + long a9b0 = (long)a.x9 * (long)b.x0; + long a9b1_38 = (long)a9_2 * (long)b1_19; + long a9b2_19 = (long)a.x9 * (long)b2_19; + long a9b3_38 = (long)a9_2 * (long)b3_19; + long a9b4_19 = (long)a.x9 * (long)b4_19; + long a9b5_38 = (long)a9_2 * (long)b5_19; + long a9b6_19 = (long)a.x9 * (long)b6_19; + long a9b7_38 = (long)a9_2 * (long)b7_19; + long a9b8_19 = (long)a.x9 * (long)b8_19; + long a9b9_38 = (long)a9_2 * (long)b9_19; + + long h0 = a0b0 + a1b9_38 + a2b8_19 + a3b7_38 + a4b6_19 + a5b5_38 + a6b4_19 + a7b3_38 + a8b2_19 + a9b1_38; + long h1 = a0b1 + a1b0 + a2b9_19 + a3b8_19 + a4b7_19 + a5b6_19 + a6b5_19 + a7b4_19 + a8b3_19 + a9b2_19; + long h2 = a0b2 + a1b1_2 + a2b0 + a3b9_38 + a4b8_19 + a5b7_38 + a6b6_19 + a7b5_38 + a8b4_19 + a9b3_38; + long h3 = a0b3 + a1b2 + a2b1 + a3b0 + a4b9_19 + a5b8_19 + a6b7_19 + a7b6_19 + a8b5_19 + a9b4_19; + long h4 = a0b4 + a1b3_2 + a2b2 + a3b1_2 + a4b0 + a5b9_38 + a6b8_19 + a7b7_38 + a8b6_19 + a9b5_38; + long h5 = a0b5 + a1b4 + a2b3 + a3b2 + a4b1 + a5b0 + a6b9_19 + a7b8_19 + a8b7_19 + a9b6_19; + long h6 = a0b6 + a1b5_2 + a2b4 + a3b3_2 + a4b2 + a5b1_2 + a6b0 + a7b9_38 + a8b8_19 + a9b7_38; + long h7 = a0b7 + a1b6 + a2b5 + a3b4 + a4b3 + a5b2 + a6b1 + a7b0 + a8b9_19 + a9b8_19; + long h8 = a0b8 + a1b7_2 + a2b6 + a3b5_2 + a4b4 + a5b3_2 + a6b2 + a7b1_2 + a8b0 + a9b9_38; + long h9 = a0b9 + a1b8 + a2b7 + a3b6 + a4b5 + a5b4 + a6b3 + a7b2 + a8b1 + a9b0; + + long carry0 = (h0 + (1L << 25)) >> 26; + h1 += carry0; + h0 -= carry0 << 26; + long carry4 = (h4 + (1L << 25)) >> 26; + h5 += carry4; + h4 -= carry4 << 26; + + long carry1 = (h1 + (1L << 24)) >> 25; + h2 += carry1; + h1 -= carry1 << 25; + long carry5 = (h5 + (1L << 24)) >> 25; + h6 += carry5; + h5 -= carry5 << 25; + + long carry2 = (h2 + (1L << 25)) >> 26; + h3 += carry2; + h2 -= carry2 << 26; + long carry6 = (h6 + (1L << 25)) >> 26; + h7 += carry6; + h6 -= carry6 << 26; + + long carry3 = (h3 + (1L << 24)) >> 25; + h4 += carry3; + h3 -= carry3 << 25; + long carry7 = (h7 + (1L << 24)) >> 25; + h8 += carry7; + h7 -= carry7 << 25; + + carry4 = (h4 + (1L << 25)) >> 26; + h5 += carry4; + h4 -= carry4 << 26; + long carry8 = (h8 + (1L << 25)) >> 26; + h9 += carry8; + h8 -= carry8 << 26; + + long carry9 = (h9 + (1L << 24)) >> 25; + h0 += carry9 * 19; + h9 -= carry9 << 25; + + carry0 = (h0 + (1L << 25)) >> 26; + h1 += carry0; + h0 -= carry0 << 26; + + output.x0 = (int)h0; + output.x1 = (int)h1; + output.x2 = (int)h2; + output.x3 = (int)h3; + output.x4 = (int)h4; + output.x5 = (int)h5; + output.x6 = (int)h6; + output.x7 = (int)h7; + output.x8 = (int)h8; + output.x9 = (int)h9; + } + + /// + /// Square a field element + /// + public static void Square(ref FieldElement output, ref FieldElement a) + { + int a0_2 = a.x0 * 2; + int a1_2 = a.x1 * 2; + int a2_2 = a.x2 * 2; + int a3_2 = a.x3 * 2; + int a4_2 = a.x4 * 2; + int a5_2 = a.x5 * 2; + int a6_2 = a.x6 * 2; + int a7_2 = a.x7 * 2; + + int a5_38 = a.x5 * 38; + int a6_19 = a.x6 * 19; + int a7_38 = a.x7 * 38; + int a8_19 = a.x8 * 19; + int a9_38 = a.x9 * 38; + + long a0a0 = (long)a.x0 * (long)a.x0; + long a0a1_2 = (long)a0_2 * (long)a.x1; + long a0a2_2 = (long)a0_2 * (long)a.x2; + long a0a3_2 = (long)a0_2 * (long)a.x3; + long a0a4_2 = (long)a0_2 * (long)a.x4; + long a0a5_2 = (long)a0_2 * (long)a.x5; + long a0a6_2 = (long)a0_2 * (long)a.x6; + long a0a7_2 = (long)a0_2 * (long)a.x7; + long a0a8_2 = (long)a0_2 * (long)a.x8; + long a0a9_2 = (long)a0_2 * (long)a.x9; + long a1a1_2 = (long)a1_2 * (long)a.x1; + long a1a2_2 = (long)a1_2 * (long)a.x2; + long a1a3_4 = (long)a1_2 * (long)a3_2; + long a1a4_2 = (long)a1_2 * (long)a.x4; + long a1a5_4 = (long)a1_2 * (long)a5_2; + long a1a6_2 = (long)a1_2 * (long)a.x6; + long a1a7_4 = (long)a1_2 * (long)a7_2; + long a1a8_2 = (long)a1_2 * (long)a.x8; + long a1a9_76 = (long)a1_2 * (long)a9_38; + long a2a2 = (long)a.x2 * (long)a.x2; + long a2a3_2 = (long)a2_2 * (long)a.x3; + long a2a4_2 = (long)a2_2 * (long)a.x4; + long a2a5_2 = (long)a2_2 * (long)a.x5; + long a2a6_2 = (long)a2_2 * (long)a.x6; + long a2a7_2 = (long)a2_2 * (long)a.x7; + long a2a8_38 = (long)a2_2 * (long)a8_19; + long a2a9_38 = (long)a.x2 * (long)a9_38; + long a3a3_2 = (long)a3_2 * (long)a.x3; + long a3a4_2 = (long)a3_2 * (long)a.x4; + long a3a5_4 = (long)a3_2 * (long)a5_2; + long a3a6_2 = (long)a3_2 * (long)a.x6; + long a3a7_76 = (long)a3_2 * (long)a7_38; + long a3a8_38 = (long)a3_2 * (long)a8_19; + long a3a9_76 = (long)a3_2 * (long)a9_38; + long a4a4 = (long)a.x4 * (long)a.x4; + long a4a5_2 = (long)a4_2 * (long)a.x5; + long a4a6_38 = (long)a4_2 * (long)a6_19; + long a4a7_38 = (long)a.x4 * (long)a7_38; + long a4a8_38 = (long)a4_2 * (long)a8_19; + long a4a9_38 = (long)a.x4 * (long)a9_38; + long a5a5_38 = (long)a.x5 * (long)a5_38; + long a5a6_38 = (long)a5_2 * (long)a6_19; + long a5a7_76 = (long)a5_2 * (long)a7_38; + long a5a8_38 = (long)a5_2 * (long)a8_19; + long a5a9_76 = (long)a5_2 * (long)a9_38; + long a6a6_19 = (long)a.x6 * (long)a6_19; + long a6a7_38 = (long)a.x6 * (long)a7_38; + long a6a8_38 = (long)a6_2 * (long)a8_19; + long a6a9_38 = (long)a.x6 * (long)a9_38; + long a7a7_38 = (long)a.x7 * (long)a7_38; + long a7a8_38 = (long)a7_2 * (long)a8_19; + long a7a9_76 = (long)a7_2 * (long)a9_38; + long a8a8_19 = (long)a.x8 * (long)a8_19; + long a8a9_38 = (long)a.x8 * (long)a9_38; + long a9a9_38 = (long)a.x9 * (long)a9_38; + + long h0 = a0a0 + a1a9_76 + a2a8_38 + a3a7_76 + a4a6_38 + a5a5_38; + long h1 = a0a1_2 + a2a9_38 + a3a8_38 + a4a7_38 + a5a6_38; + long h2 = a0a2_2 + a1a1_2 + a3a9_76 + a4a8_38 + a5a7_76 + a6a6_19; + long h3 = a0a3_2 + a1a2_2 + a4a9_38 + a5a8_38 + a6a7_38; + long h4 = a0a4_2 + a1a3_4 + a2a2 + a5a9_76 + a6a8_38 + a7a7_38; + long h5 = a0a5_2 + a1a4_2 + a2a3_2 + a6a9_38 + a7a8_38; + long h6 = a0a6_2 + a1a5_4 + a2a4_2 + a3a3_2 + a7a9_76 + a8a8_19; + long h7 = a0a7_2 + a1a6_2 + a2a5_2 + a3a4_2 + a8a9_38; + long h8 = a0a8_2 + a1a7_4 + a2a6_2 + a3a5_4 + a4a4 + a9a9_38; + long h9 = a0a9_2 + a1a8_2 + a2a7_2 + a3a6_2 + a4a5_2; + + long carry0 = (h0 + (1L << 25)) >> 26; + h1 += carry0; + h0 -= carry0 << 26; + long carry4 = (h4 + (1L << 25)) >> 26; + h5 += carry4; + h4 -= carry4 << 26; + + long carry1 = (h1 + (1L << 24)) >> 25; + h2 += carry1; + h1 -= carry1 << 25; + long carry5 = (h5 + (1L << 24)) >> 25; + h6 += carry5; + h5 -= carry5 << 25; + + long carry2 = (h2 + (1L << 25)) >> 26; + h3 += carry2; + h2 -= carry2 << 26; + long carry6 = (h6 + (1L << 25)) >> 26; + h7 += carry6; + h6 -= carry6 << 26; + + long carry3 = (h3 + (1L << 24)) >> 25; + h4 += carry3; + h3 -= carry3 << 25; + long carry7 = (h7 + (1L << 24)) >> 25; + h8 += carry7; + h7 -= carry7 << 25; + + carry4 = (h4 + (1L << 25)) >> 26; + h5 += carry4; + h4 -= carry4 << 26; + long carry8 = (h8 + (1L << 25)) >> 26; + h9 += carry8; + h8 -= carry8 << 26; + + long carry9 = (h9 + (1L << 24)) >> 25; + h0 += carry9 * 19; + h9 -= carry9 << 25; + + carry0 = (h0 + (1L << 25)) >> 26; + h1 += carry0; + h0 -= carry0 << 26; + + output.x0 = (int)h0; + output.x1 = (int)h1; + output.x2 = (int)h2; + output.x3 = (int)h3; + output.x4 = (int)h4; + output.x5 = (int)h5; + output.x6 = (int)h6; + output.x7 = (int)h7; + output.x8 = (int)h8; + output.x9 = (int)h9; + } + + /// + /// Multiplay a field element by 121666 + /// + public static void Multiply121666(ref FieldElement output, ref FieldElement a) + { + long h0 = (long)a.x0 * 121666L; + long h1 = (long)a.x1 * 121666L; + long h2 = (long)a.x2 * 121666L; + long h3 = (long)a.x3 * 121666L; + long h4 = (long)a.x4 * 121666L; + long h5 = (long)a.x5 * 121666L; + long h6 = (long)a.x6 * 121666L; + long h7 = (long)a.x7 * 121666L; + long h8 = (long)a.x8 * 121666L; + long h9 = (long)a.x9 * 121666L; + + long carry9 = (h9 + (1L<<24)) >> 25; + h0 += carry9 * 19; + h9 -= carry9 << 25; + long carry1 = (h1 + (1L<<24)) >> 25; + h2 += carry1; + h1 -= carry1 << 25; + long carry3 = (h3 + (1L<<24)) >> 25; + h4 += carry3; + h3 -= carry3 << 25; + long carry5 = (h5 + (1L<<24)) >> 25; + h6 += carry5; + h5 -= carry5 << 25; + long carry7 = (h7 + (1L<<24)) >> 25; + h8 += carry7; + h7 -= carry7 << 25; + + long carry0 = (h0 + (1L << 25)) >> 26; + h1 += carry0; + h0 -= carry0 << 26; + long carry2 = (h2 + (1L << 25)) >> 26; + h3 += carry2; + h2 -= carry2 << 26; + long carry4 = (h4 + (1L << 25)) >> 26; + h5 += carry4; + h4 -= carry4 << 26; + long carry6 = (h6 + (1L << 25)) >> 26; + h7 += carry6; + h6 -= carry6 << 26; + long carry8 = (h8 + (1L << 25)) >> 26; + h9 += carry8; + h8 -= carry8 << 26; + + output.x0 = (int)h0; + output.x1 = (int)h1; + output.x2 = (int)h2; + output.x3 = (int)h3; + output.x4 = (int)h4; + output.x5 = (int)h5; + output.x6 = (int)h6; + output.x7 = (int)h7; + output.x8 = (int)h8; + output.x9 = (int)h9; + } + + /// + /// Invert a field element + /// + public static void Invert(ref FieldElement output, ref FieldElement a) + { + FieldElement t0 = new FieldElement(); + Square(ref t0, ref a); + + FieldElement t1 = new FieldElement(); + Square(ref t1, ref t0); + Square(ref t1, ref t1); + + FieldElement t2= new FieldElement(); + Multiply(ref t1, ref a, ref t1); + Multiply(ref t0, ref t0, ref t1); + Square(ref t2, ref t0); + //Square(ref t2, ref t2); + + Multiply(ref t1, ref t1, ref t2); + Square(ref t2, ref t1); + for (int ii = 1; ii < 5; ++ii) + { + Square(ref t2, ref t2); + } + + Multiply(ref t1, ref t2, ref t1); + Square(ref t2, ref t1); + for (int ii = 1; ii < 10; ++ii) + { + Square(ref t2, ref t2); + } + + FieldElement t3 = new FieldElement(); + Multiply(ref t2, ref t2, ref t1); + Square(ref t3, ref t2); + for (int ii = 1; ii < 20; ++ii) + { + Square(ref t3, ref t3); + } + + Multiply(ref t2, ref t3, ref t2); + Square(ref t2, ref t2); + for (int ii = 1; ii < 10; ++ii) + { + Square(ref t2, ref t2); + } + + Multiply(ref t1, ref t2, ref t1); + Square(ref t2, ref t1); + for (int ii = 1; ii < 50; ++ii) + { + Square(ref t2, ref t2); + } + + Multiply(ref t2, ref t2, ref t1); + Square(ref t3, ref t2); + for (int ii = 1; ii < 100; ++ii) + { + Square(ref t3, ref t3); + } + + Multiply(ref t2, ref t3, ref t2); + Square(ref t2, ref t2); + for (int ii = 1; ii < 50; ++ii) + { + Square(ref t2, ref t2); + } + + Multiply(ref t1, ref t2, ref t1); + Square(ref t1, ref t1); + for (int ii = 1; ii < 5; ++ii) + { + Square(ref t1, ref t1); + } + + Multiply(ref output, ref t1, ref t0); + } + + /// + /// Swaps `a` and `b` if `swap` is 1 + /// + public static void ConditionalSwap(ref FieldElement a, ref FieldElement b, int swap) + { + Debug.Assert(swap == 0 || swap == 1); + swap = -swap; + + FieldElement temp = new FieldElement + { + x0 = swap & (a.x0 ^ b.x0), + x1 = swap & (a.x1 ^ b.x1), + x2 = swap & (a.x2 ^ b.x2), + x3 = swap & (a.x3 ^ b.x3), + x4 = swap & (a.x4 ^ b.x4), + x5 = swap & (a.x5 ^ b.x5), + x6 = swap & (a.x6 ^ b.x6), + x7 = swap & (a.x7 ^ b.x7), + x8 = swap & (a.x8 ^ b.x8), + x9 = swap & (a.x9 ^ b.x9), + }; + + a.x0 ^= temp.x0; + a.x1 ^= temp.x1; + a.x2 ^= temp.x2; + a.x3 ^= temp.x3; + a.x4 ^= temp.x4; + a.x5 ^= temp.x5; + a.x6 ^= temp.x6; + a.x7 ^= temp.x7; + a.x8 ^= temp.x8; + a.x9 ^= temp.x9; + + b.x0 ^= temp.x0; + b.x1 ^= temp.x1; + b.x2 ^= temp.x2; + b.x3 ^= temp.x3; + b.x4 ^= temp.x4; + b.x5 ^= temp.x5; + b.x6 ^= temp.x6; + b.x7 ^= temp.x7; + b.x8 ^= temp.x8; + b.x9 ^= temp.x9; + } + } + } +} diff --git a/Hazel/Hazel.csproj b/Hazel/Hazel.csproj index 9c49e96..a1d4c0c 100644 --- a/Hazel/Hazel.csproj +++ b/Hazel/Hazel.csproj @@ -74,6 +74,7 @@ + -- 2.39.5