diff options
Diffstat (limited to 'crypto/src')
25 files changed, 1925 insertions, 0 deletions
diff --git a/crypto/src/pqc/crypto/ntru/NtruEncapsulation.cs b/crypto/src/pqc/crypto/ntru/NtruEncapsulation.cs new file mode 100644 index 000000000..b00fbef31 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruEncapsulation.cs @@ -0,0 +1,57 @@ +using System; +using Org.BouncyCastle.Crypto; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + /// <summary> + /// Encapsulated secret encapsulated by NTRU. + /// </summary> + internal class NtruEncapsulation : ISecretWithEncapsulation + { + private readonly byte[] _sharedKey; + private readonly byte[] _ciphertext; + + private bool _hasBeenDestroyed; + + internal NtruEncapsulation(byte[] sharedKey, byte[] ciphertext) + { + _sharedKey = sharedKey; + _ciphertext = ciphertext; + } + + public void Dispose() + { + if (!_hasBeenDestroyed) + { + Array.Clear(_sharedKey, 0, _sharedKey.Length); + Array.Clear(_ciphertext, 0, _ciphertext.Length); + _hasBeenDestroyed = true; + } + } + + public byte[] GetSecret() + { + CheckDestroyed(); + return _sharedKey; + } + + public byte[] GetEncapsulation() + { + CheckDestroyed(); + return _ciphertext; + } + + void CheckDestroyed() + { + if (IsDestroyed()) + { + throw new InvalidOperationException("Object has been destroyed"); + } + } + + public bool IsDestroyed() + { + return _hasBeenDestroyed; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/NtruKemExtractor.cs b/crypto/src/pqc/crypto/ntru/NtruKemExtractor.cs new file mode 100644 index 000000000..4d730a3f1 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruKemExtractor.cs @@ -0,0 +1,87 @@ +using System; +using System.Diagnostics; +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Crypto.Digests; +using Org.BouncyCastle.Pqc.Crypto.Ntru.Owcpa; +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + /// <summary> + /// NTRU secret encapsulation extractor. + /// </summary> + public class NtruKemExtractor : IEncapsulatedSecretExtractor + { + private readonly NtruParameters _parameters; + private readonly NtruPrivateKeyParameters _ntruPrivateKey; + + public NtruKemExtractor(NtruPrivateKeyParameters ntruPrivateKey) + { + _parameters = ntruPrivateKey.Parameters; + _ntruPrivateKey = ntruPrivateKey; + } + + + public byte[] ExtractSecret(byte[] encapsulation) + { + Debug.Assert(_ntruPrivateKey != null); + + NtruParameterSet parameterSet = _parameters.ParameterSet; + + byte[] sk = _ntruPrivateKey.PrivateKey; + int i, fail; + byte[] rm; + byte[] buf = new byte[parameterSet.PrfKeyBytes + parameterSet.NtruCiphertextBytes()]; + + NtruOwcpa owcpa = new NtruOwcpa(parameterSet); + OwcpaDecryptResult owcpaResult = owcpa.Decrypt(encapsulation, _ntruPrivateKey.PrivateKey); + rm = owcpaResult.Rm; + fail = owcpaResult.Fail; + + Sha3Digest sha3256 = new Sha3Digest(256); + + byte[] k = new byte[sha3256.GetDigestSize()]; + + sha3256.BlockUpdate(rm, 0, rm.Length); + sha3256.DoFinal(k, 0); + + /* shake(secret PRF key || input ciphertext) */ + for (i = 0; i < parameterSet.PrfKeyBytes; i++) + { + buf[i] = sk[i + parameterSet.OwcpaSecretKeyBytes()]; + } + + for (i = 0; i < parameterSet.NtruCiphertextBytes(); i++) + { + buf[parameterSet.PrfKeyBytes + i] = encapsulation[i]; + } + + sha3256.Reset(); + sha3256.BlockUpdate(buf, 0, buf.Length); + sha3256.DoFinal(rm, 0); + + Cmov(k, rm, (byte)fail); + + byte[] sharedKey = new byte[parameterSet.SharedKeyBytes]; + Array.Copy(k, 0, sharedKey, 0, parameterSet.SharedKeyBytes); + + Array.Clear(k, 0, k.Length); + + return sharedKey; + } + + private static void Cmov(byte[] r, byte[] x, byte b) + { + b = (byte)(~b + 1); + for (int i = 0; i < r.Length; i++) + { + r[i] ^= (byte)(b & (x[i] ^ r[i])); + } + } + + public int GetInputSize() + { + return _parameters.ParameterSet.NtruCiphertextBytes(); + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/NtruKemGenerator.cs b/crypto/src/pqc/crypto/ntru/NtruKemGenerator.cs new file mode 100644 index 000000000..e579c898d --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruKemGenerator.cs @@ -0,0 +1,70 @@ +using System; +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Crypto.Digests; +using Org.BouncyCastle.Pqc.Crypto.Ntru.Owcpa; +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; +using Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials; +using Org.BouncyCastle.Security; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + /// <summary> + /// Encapsulate a secret using NTRU. Returns an <see cref="NtruEncapsulation"/> as encapsulation. + /// </summary> + /// + /// <seealso cref="NtruKemExtractor"/> + /// <seealso href="https://ntru.org/">NTRU website</seealso> + public class NtruKemGenerator : IEncapsulatedSecretGenerator + { + private readonly SecureRandom _random; + + public NtruKemGenerator(SecureRandom random) + { + _random = random; + } + + public ISecretWithEncapsulation GenerateEncapsulated(AsymmetricKeyParameter recipientKey) + { + var parameterSet = ((NtruPublicKeyParameters)recipientKey).GetParameters().ParameterSet; + var sampling = new NtruSampling(parameterSet); + var owcpa = new NtruOwcpa(parameterSet); + Polynomial r; + Polynomial m; + var rm = new byte[parameterSet.OwcpaMsgBytes()]; + var rmSeed = new byte[parameterSet.SampleRmBytes()]; + + _random.NextBytes(rmSeed); + + var pair = sampling.SampleRm(rmSeed); + r = pair.R(); + m = pair.M(); + + var rm1 = r.S3ToBytes(parameterSet.OwcpaMsgBytes()); + Array.Copy(rm1, 0, rm, 0, rm1.Length); + + var rm2 = m.S3ToBytes(rm.Length - parameterSet.PackTrinaryBytes()); + + Array.Copy(rm2, 0, rm, parameterSet.PackTrinaryBytes(), rm2.Length); + + var sha3256 = new Sha3Digest(256); + sha3256.BlockUpdate(rm, 0, rm.Length); + + + var k = new byte[sha3256.GetDigestSize()]; + + sha3256.DoFinal(k, 0); + + + r.Z3ToZq(); + + var c = owcpa.Encrypt(r, m, ((NtruPublicKeyParameters)recipientKey).PublicKey); + + var sharedKey = new byte[parameterSet.SharedKeyBytes]; + Array.Copy(k, 0, sharedKey, 0, sharedKey.Length); + + Array.Clear(k, 0, k.Length); + + return new NtruEncapsulation(sharedKey, c); + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/NtruKeyGenerationParameters.cs b/crypto/src/pqc/crypto/ntru/NtruKeyGenerationParameters.cs new file mode 100644 index 000000000..df2a28bb0 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruKeyGenerationParameters.cs @@ -0,0 +1,21 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Security; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + public class NtruKeyGenerationParameters : KeyGenerationParameters + { + internal NtruParameters NtruParameters { get; } + + // We won't be using strength as the key length differs between public & private key + public NtruKeyGenerationParameters(SecureRandom random, NtruParameters ntruParameters) : base(random, 1) + { + NtruParameters = ntruParameters; + } + + public NtruParameters GetParameters() + { + return NtruParameters; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/NtruKeyPairGenerator.cs b/crypto/src/pqc/crypto/ntru/NtruKeyPairGenerator.cs new file mode 100644 index 000000000..60bddc4c3 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruKeyPairGenerator.cs @@ -0,0 +1,44 @@ +using System; +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Pqc.Crypto.Ntru.Owcpa; +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; +using Org.BouncyCastle.Security; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + public class NtruKeyPairGenerator : IAsymmetricCipherKeyPairGenerator + { + private NtruKeyGenerationParameters _keygenParameters; + private SecureRandom _random; + + public void Init(KeyGenerationParameters parameters) + { + _keygenParameters = (NtruKeyGenerationParameters)parameters; + _random = parameters.Random; + } + + public AsymmetricCipherKeyPair GenerateKeyPair() + { + // Debug.Assert(this._random != null); + NtruParameterSet parameterSet = _keygenParameters.NtruParameters.ParameterSet; + + var seed = new byte[parameterSet.SampleFgBytes()]; + _random.NextBytes(seed); + + NtruOwcpa owcpa = new NtruOwcpa(parameterSet); + OwcpaKeyPair owcpaKeys = owcpa.KeyPair(seed); + + byte[] publicKey = owcpaKeys.PublicKey; + byte[] privateKey = new byte[parameterSet.NtruSecretKeyBytes()]; + byte[] owcpaPrivateKey = owcpaKeys.PrivateKey; + Array.Copy(owcpaPrivateKey, 0, privateKey, 0, owcpaPrivateKey.Length); + // + byte[] prfBytes = new byte[parameterSet.PrfKeyBytes]; + _random.NextBytes(prfBytes); + Array.Copy(prfBytes, 0, privateKey, parameterSet.OwcpaSecretKeyBytes(), prfBytes.Length); + + return new AsymmetricCipherKeyPair(new NtruPublicKeyParameters(_keygenParameters.NtruParameters, publicKey), + new NtruPrivateKeyParameters(_keygenParameters.NtruParameters, privateKey)); + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/NtruKeyParameters.cs b/crypto/src/pqc/crypto/ntru/NtruKeyParameters.cs new file mode 100644 index 000000000..906f7d5d4 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruKeyParameters.cs @@ -0,0 +1,21 @@ +using Org.BouncyCastle.Crypto; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + public abstract class NtruKeyParameters : AsymmetricKeyParameter + { + public NtruParameters Parameters { get; } + + public NtruKeyParameters(bool privateKey, NtruParameters parameters) : base(privateKey) + { + Parameters = parameters; + } + + public abstract byte[] GetEncoded(); + + public NtruParameters GetParameters() + { + return Parameters; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/NtruParameters.cs b/crypto/src/pqc/crypto/ntru/NtruParameters.cs new file mode 100644 index 000000000..3bf2233ff --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruParameters.cs @@ -0,0 +1,33 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + public class NtruParameters : ICipherParameters + { + public static readonly NtruParameters NtruHps2048509 = + new NtruParameters("ntruhps2048509", new NtruHps2048509()); + + public static readonly NtruParameters NtruHps2048677 = + new NtruParameters("ntruhps2048677", new NtruHps2048677()); + + public static readonly NtruParameters NtruHps4096821 = + new NtruParameters("ntruhps4096821", new NtruHps4096821()); + + public static readonly NtruParameters NtruHrss701 = new NtruParameters("ntruhrss701", new NtruHrss701()); + + internal readonly NtruParameterSet ParameterSet; + + private readonly string _name; + + private NtruParameters(string name, NtruParameterSet parameterSet) + { + _name = name; + ParameterSet = parameterSet; + } + + public string Name => _name; + + public int DefaultKeySize => ParameterSet.SharedKeyBytes * 8; + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/NtruPrivateKeyParamaters.cs b/crypto/src/pqc/crypto/ntru/NtruPrivateKeyParamaters.cs new file mode 100644 index 000000000..0c90a8afa --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruPrivateKeyParamaters.cs @@ -0,0 +1,24 @@ +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + public class NtruPrivateKeyParameters : NtruKeyParameters + { + private byte[] _privateKey; + + public byte[] PrivateKey + { + get => (byte[])_privateKey.Clone(); + private set => _privateKey = (byte[])value.Clone(); + } + + public NtruPrivateKeyParameters(NtruParameters parameters, byte[] key) : base(true, parameters) + { + PrivateKey = key; + } + + + public override byte[] GetEncoded() + { + return PrivateKey; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/NtruPublicKeyParameters.cs b/crypto/src/pqc/crypto/ntru/NtruPublicKeyParameters.cs new file mode 100644 index 000000000..6a7cc0752 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruPublicKeyParameters.cs @@ -0,0 +1,23 @@ +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + public class NtruPublicKeyParameters : NtruKeyParameters + { + private byte[] _publicKey; + + public byte[] PublicKey + { + get => (byte[])_publicKey.Clone(); + set => _publicKey = (byte[])value.Clone(); + } + + public NtruPublicKeyParameters(NtruParameters parameters, byte[] key) : base(false, parameters) + { + PublicKey = key; + } + + public override byte[] GetEncoded() + { + return PublicKey; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/NtruSampling.cs b/crypto/src/pqc/crypto/ntru/NtruSampling.cs new file mode 100644 index 000000000..fca99b130 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/NtruSampling.cs @@ -0,0 +1,207 @@ +using System; +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; +using Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials; +using Org.BouncyCastle.Utilities; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + /// <summary> + /// NTRU sampling. + /// + /// <seealso href="https://ntru.org/f/ntru-20190330.pdf">NTRU specification section 1.10</seealso> + /// </summary> + internal class NtruSampling + { + private readonly NtruParameterSet _parameterSet; + + internal NtruSampling(NtruParameterSet parameterSet) + { + _parameterSet = parameterSet; + } + + /// <summary> + /// Sample_fg + /// </summary> + /// <param name="uniformBytes">random byte array</param> + /// <returns>a pair of polynomial <c>f</c> and <c>g</c></returns> + /// <exception cref="ArgumentException"></exception> + // TODO: using tuple as return value might be better but I'm not sure if it's available with the target + // language version + internal PolynomialPair SampleFg(byte[] uniformBytes) + { + switch (_parameterSet) + { + case NtruHrssParameterSet _: + { + var f = SampleIidPlus(Arrays.CopyOfRange(uniformBytes, 0, _parameterSet.SampleIidBytes())); + var g = SampleIidPlus(Arrays.CopyOfRange(uniformBytes, _parameterSet.SampleIidBytes(), + uniformBytes.Length)); + return new PolynomialPair(f, g); + } + case NtruHpsParameterSet _: + { + var f = (HpsPolynomial)SampleIid( + Arrays.CopyOfRange(uniformBytes, 0, _parameterSet.SampleIidBytes())); + var g = SampleFixedType(Arrays.CopyOfRange(uniformBytes, _parameterSet.SampleIidBytes(), + uniformBytes.Length)); + return new PolynomialPair(f, g); + } + default: + throw new ArgumentException("Invalid polynomial type"); + } + } + + /// <summary> + /// Sample_rm + /// </summary> + /// <param name="uniformBytes">random byte array</param> + /// <returns>a pair of polynomial <c>r</c> and <c>m</c></returns> + /// <exception cref="ArgumentException"></exception> + internal PolynomialPair SampleRm(byte[] uniformBytes) + { + switch (_parameterSet) + { + case NtruHrssParameterSet _: + { + var r = (HrssPolynomial)SampleIid(Arrays.CopyOfRange(uniformBytes, 0, + _parameterSet.SampleIidBytes())); + var m = (HrssPolynomial)SampleIid(Arrays.CopyOfRange(uniformBytes, _parameterSet.SampleIidBytes(), + uniformBytes.Length)); + return new PolynomialPair(r, m); + } + case NtruHpsParameterSet _: + { + var r = (HpsPolynomial)SampleIid( + Arrays.CopyOfRange(uniformBytes, 0, _parameterSet.SampleIidBytes())); + var m = SampleFixedType(Arrays.CopyOfRange(uniformBytes, _parameterSet.SampleIidBytes(), + uniformBytes.Length)); + return new PolynomialPair(r, m); + } + default: + throw new ArgumentException("Invalid polynomial type"); + } + } + + /// <summary> + /// Ternary + /// </summary> + /// <param name="uniformBytes">random byte array</param> + /// <returns>A ternary polynomial</returns> + internal Polynomial SampleIid(byte[] uniformBytes) + { + var r = _parameterSet.CreatePolynomial(); + for (var i = 0; i < _parameterSet.N - 1; i++) + { + r.coeffs[i] = (ushort)Mod3(uniformBytes[i]); + } + + r.coeffs[_parameterSet.N - 1] = 0; + return r; + } + + /// <summary> + /// Fixed_Type + /// </summary> + /// <param name="uniformBytes">random byte array</param> + /// <returns>a ternary polynomial with exactly q/16 − 1 coefficients equal to 1 and q/16 − 1 coefficient equal to −1</returns> + internal HpsPolynomial SampleFixedType(byte[] uniformBytes) + { + var n = _parameterSet.N; + var weight = ((NtruHpsParameterSet)_parameterSet).Weight(); + var r = (HpsPolynomial)_parameterSet.CreatePolynomial(); + var s = new int[n - 1]; + int i; + + for (i = 0; i < (n - 1) / 4; i++) + { + s[4 * i + 0] = (uniformBytes[15 * i + 0] << 2) + (uniformBytes[15 * i + 1] << 10) + + (uniformBytes[15 * i + 2] << 18) + (uniformBytes[15 * i + 3] << 26); + s[4 * i + 1] = ((uniformBytes[15 * i + 3] & 0xc0) >> 4) + (uniformBytes[15 * i + 4] << 4) + + (uniformBytes[15 * i + 5] << 12) + (uniformBytes[15 * i + 6] << 20) + + (uniformBytes[15 * i + 7] << 28); + s[4 * i + 2] = ((uniformBytes[15 * i + 7] & 0xf0) >> 2) + (uniformBytes[15 * i + 8] << 6) + + (uniformBytes[15 * i + 9] << 14) + (uniformBytes[15 * i + 10] << 22) + + (uniformBytes[15 * i + 11] << 30); + s[4 * i + 3] = (uniformBytes[15 * i + 11] & 0xfc) + (uniformBytes[15 * i + 12] << 8) + + (uniformBytes[15 * i + 13] << 16) + (uniformBytes[15 * i + 14] << 24); + } + + // (N-1) = 2 mod 4 + if (n - 1 > (n - 1) / 4 * 4) + { + i = (n - 1) / 4; + s[4 * i + 0] = (uniformBytes[15 * i + 0] << 2) + (uniformBytes[15 * i + 1] << 10) + + (uniformBytes[15 * i + 2] << 18) + (uniformBytes[15 * i + 3] << 26); + s[4 * i + 1] = ((uniformBytes[15 * i + 3] & 0xc0) >> 4) + (uniformBytes[15 * i + 4] << 4) + + (uniformBytes[15 * i + 5] << 12) + (uniformBytes[15 * i + 6] << 20) + + (uniformBytes[15 * i + 7] << 28); + } + + for (i = 0; i < weight / 2; i++) + { + s[i] |= 1; + } + + for (i = weight / 2; i < weight; i++) + { + s[i] |= 2; + } + + Array.Sort(s); + + for (i = 0; i < n - 1; i++) + { + r.coeffs[i] = (ushort)(s[i] & 3); + } + + r.coeffs[n - 1] = 0; + return r; + } + + /// <summary> + /// Ternary_Plus + /// </summary> + /// <param name="uniformBytes">random byte array</param> + /// <returns>a ternary polynomial that satisfies the non-negative correlation property</returns> + internal HrssPolynomial SampleIidPlus(byte[] uniformBytes) + { + var n = _parameterSet.N; + int i; + ushort s = 0; + var r = (HrssPolynomial)SampleIid(uniformBytes); + + /* Map {0,1,2} -> {0, 1, 2^16 - 1} */ + for (i = 0; i < n - 1; i++) + { + r.coeffs[i] = (ushort)(r.coeffs[i] | -(r.coeffs[i] >> 1)); + } + + /* s = <x*r, r>. (r[n-1] = 0) */ + for (i = 0; i < n - 1; i++) + { + s += (ushort)((uint)r.coeffs[i + 1] * r.coeffs[i]); + } + + /* Extract sign of s (sign(0) = 1) */ + s = (ushort)(1 | -(s >> 15)); + + for (i = 0; i < n - 1; i += 2) + { + r.coeffs[i] = (ushort)((uint)s * r.coeffs[i]); + } + + /* Map {0,1,2^16-1} -> {0, 1, 2} */ + for (i = 0; i < n - 1; i++) + { + r.coeffs[i] = (ushort)(3 & (r.coeffs[i] ^ (r.coeffs[i] >> 15))); + } + + return r; + } + + private static int Mod3(int a) + { + return a % 3; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/PolynomialPair.cs b/crypto/src/pqc/crypto/ntru/PolynomialPair.cs new file mode 100644 index 000000000..8c7a2c3cb --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/PolynomialPair.cs @@ -0,0 +1,36 @@ +using Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru +{ + internal class PolynomialPair + { + private readonly Polynomial _a; + private readonly Polynomial _b; + + public PolynomialPair(Polynomial a, Polynomial b) + { + _a = a; + _b = b; + } + + internal Polynomial F() + { + return _a; + } + + internal Polynomial G() + { + return _b; + } + + internal Polynomial R() + { + return _a; + } + + internal Polynomial M() + { + return _b; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/owcpa/NtruOwcpa.cs b/crypto/src/pqc/crypto/ntru/owcpa/NtruOwcpa.cs new file mode 100644 index 000000000..b6cbdfd5d --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/owcpa/NtruOwcpa.cs @@ -0,0 +1,246 @@ +using System; +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; +using Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials; +using Org.BouncyCastle.Utilities; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.Owcpa +{ + /// <summary> + /// An OW-CPA secure deterministic public key encryption scheme (DPKE). + /// </summary> + internal class NtruOwcpa + { + private readonly NtruParameterSet _parameterSet; + private readonly NtruSampling _sampling; + + internal NtruOwcpa(NtruParameterSet parameterSet) + { + _parameterSet = parameterSet; + _sampling = new NtruSampling(parameterSet); + } + + /// <summary> + /// Generate a DPKE key pair. + /// </summary> + /// <param name="seed">a random byte array</param> + /// <returns>DPKE key pair</returns> + internal OwcpaKeyPair KeyPair(byte[] seed) + { + byte[] publicKey; + var privateKey = new byte[_parameterSet.OwcpaSecretKeyBytes()]; + var n = _parameterSet.N; + var q = _parameterSet.Q(); + int i; + PolynomialPair pair; + Polynomial x1, x2, x3, x4, x5; + x1 = _parameterSet.CreatePolynomial(); + x2 = _parameterSet.CreatePolynomial(); + x3 = _parameterSet.CreatePolynomial(); + x4 = _parameterSet.CreatePolynomial(); + x5 = _parameterSet.CreatePolynomial(); + + Polynomial f, g, invfMod3 = x3; + Polynomial gf = x3, invgf = x4, tmp = x5; + Polynomial invh = x3, h = x3; + + pair = _sampling.SampleFg(seed); + f = pair.F(); + g = pair.G(); + + invfMod3.S3Inv(f); + var fs3ToBytes = f.S3ToBytes(_parameterSet.OwcpaMsgBytes()); + Array.Copy(fs3ToBytes, 0, privateKey, 0, fs3ToBytes.Length); + var s3Res = invfMod3.S3ToBytes(privateKey.Length - _parameterSet.PackTrinaryBytes()); + Array.Copy(s3Res, 0, privateKey, _parameterSet.PackTrinaryBytes(), s3Res.Length); + + f.Z3ToZq(); + g.Z3ToZq(); + + if (_parameterSet is NtruHrssParameterSet) + { + /* g = 3*(x-1)*g */ + for (i = n - 1; i > 0; i--) + { + g.coeffs[i] = (ushort)(3 * (g.coeffs[i - 1] - g.coeffs[i])); + } + + g.coeffs[0] = (ushort)-(3 * g.coeffs[0]); + } + else + { + for (i = 0; i < n; i++) + { + g.coeffs[i] = (ushort)(3 * g.coeffs[i]); + } + } + + gf.RqMul(g, f); + invgf.RqInv(gf); + + tmp.RqMul(invgf, f); + invh.SqMul(tmp, f); + var sqRes = invh.SqToBytes(privateKey.Length - 2 * _parameterSet.PackTrinaryBytes()); + Array.Copy(sqRes, 0, privateKey, 2 * _parameterSet.PackTrinaryBytes(), sqRes.Length); + + tmp.RqMul(invgf, g); + h.RqMul(tmp, g); + publicKey = h.RqSumZeroToBytes(_parameterSet.OwcpaPublicKeyBytes()); + + return new OwcpaKeyPair(publicKey, privateKey); + } + + /// <summary> + /// DPKE encryption. + /// </summary> + /// <param name="r"></param> + /// <param name="m"></param> + /// <param name="publicKey"></param> + /// <returns>DPKE ciphertext</returns> + internal byte[] Encrypt(Polynomial r, Polynomial m, byte[] publicKey) + { + int i; + Polynomial x1 = _parameterSet.CreatePolynomial(), x2 = _parameterSet.CreatePolynomial(); + Polynomial h = x1, liftm = x1; + Polynomial ct = x2; + + h.RqSumZeroFromBytes(publicKey); + + ct.RqMul(r, h); + + liftm.Lift(m); + + for (i = 0; i < _parameterSet.N; i++) + { + ct.coeffs[i] += liftm.coeffs[i]; + } + + return ct.RqSumZeroToBytes(_parameterSet.NtruCiphertextBytes()); + } + + /// <summary> + /// DPKE decryption. + /// </summary> + /// <param name="ciphertext"></param> + /// <param name="privateKey"></param> + /// <returns>an instance of <see cref="OwcpaDecryptResult"/> containing <c>packed_rm</c> an fail flag</returns> + internal OwcpaDecryptResult Decrypt(byte[] ciphertext, byte[] privateKey) + { + byte[] sk = privateKey; + byte[] rm = new byte[_parameterSet.OwcpaMsgBytes()]; + int i, fail; + Polynomial x1 = _parameterSet.CreatePolynomial(); + Polynomial x2 = _parameterSet.CreatePolynomial(); + Polynomial x3 = _parameterSet.CreatePolynomial(); + Polynomial x4 = _parameterSet.CreatePolynomial(); + + Polynomial c = x1, f = x2, cf = x3; + Polynomial mf = x2, finv3 = x3, m = x4; + Polynomial liftm = x2, invh = x3, r = x4; + Polynomial b = x1; + + c.RqSumZeroFromBytes(ciphertext); + f.S3FromBytes(sk); + + f.Z3ToZq(); + + cf.RqMul(c, f); + + mf.RqToS3(cf); + + finv3.S3FromBytes(Arrays.CopyOfRange(sk, _parameterSet.PackTrinaryBytes(), sk.Length)); + + m.S3Mul(mf, finv3); + + byte[] arr1 = m.S3ToBytes(rm.Length - _parameterSet.PackTrinaryBytes()); + + fail = 0; + + /* Check that the unused bits of the last byte of the ciphertext are zero */ + fail |= CheckCiphertext(ciphertext); + + /* For the IND-CCA2 KEM we must ensure that c = Enc(h, (r,m)). */ + /* We can avoid re-computing r*h + Lift(m) as long as we check that */ + /* r (defined as b/h mod (q, Phi_n)) and m are in the message space. */ + /* (m can take any value in S3 in NTRU_HRSS) */ + + + if (_parameterSet is NtruHpsParameterSet) + { + fail |= CheckM((HpsPolynomial)m); + } + + /* b = c - Lift(m) mod (q, x^n - 1) */ + liftm.Lift(m); + + for (i = 0; i < _parameterSet.N; i++) + { + b.coeffs[i] = (ushort)(c.coeffs[i] - liftm.coeffs[i]); + } + + /* r = b / h mod (q, Phi_n) */ + invh.SqFromBytes(Arrays.CopyOfRange(sk, 2 * _parameterSet.PackTrinaryBytes(), sk.Length)); + r.SqMul(b, invh); + + fail |= CheckR(r); + + r.TrinaryZqToZ3(); + byte[] arr2 = r.S3ToBytes(_parameterSet.OwcpaMsgBytes()); + Array.Copy(arr2, 0, rm, 0, arr2.Length); + Array.Copy(arr1, 0, rm, _parameterSet.PackTrinaryBytes(), arr1.Length); + + return new OwcpaDecryptResult(rm, fail); + } + + private int CheckCiphertext(byte[] ciphertext) + { + ushort t; + t = ciphertext[_parameterSet.NtruCiphertextBytes() - 1]; + t &= (ushort)(0xff << (8 - (7 & (_parameterSet.LogQ * _parameterSet.PackDegree())))); + + /* We have 0 <= t < 256 */ + /* Return 0 on success (t=0), 1 on failure */ + return 1 & ((~t + 1) >> 15); + } + + private int CheckR(Polynomial r) + { + /* A valid r has coefficients in {0,1,q-1} and has r[N-1] = 0 */ + /* Note: We may assume that 0 <= r[i] <= q-1 for all i */ + int i; + int t = 0; // unsigned + ushort c; // unsigned + for (i = 0; i < _parameterSet.N - 1; i++) + { + c = r.coeffs[i]; + t |= (c + 1) & (_parameterSet.Q() - 4); /* 0 iff c is in {-1,0,1,2} */ + t |= (c + 2) & 4; /* 1 if c = 2, 0 if c is in {-1,0,1} */ + } + + t |= r.coeffs[_parameterSet.N - 1]; /* Coefficient n-1 must be zero */ + + /* We have 0 <= t < 2^16. */ + /* Return 0 on success (t=0), 1 on failure */ + return (1 & ((~t + 1) >> 31)); + } + + private int CheckM(HpsPolynomial m) + { + int i; + int t = 0; // unsigned + ushort ps = 0; // unsigned + ushort ms = 0; // unsigned + for (i = 0; i < _parameterSet.N - 1; i++) + { + ps += (ushort)(m.coeffs[i] & 1); + ms += (ushort)(m.coeffs[i] & 2); + } + + t |= ps ^ (ms >> 1); + t |= ms ^ ((NtruHpsParameterSet)_parameterSet).Weight(); + + /* We have 0 <= t < 2^16. */ + /* Return 0 on success (t=0), 1 on failure */ + return (1 & ((~t + 1) >> 31)); + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/owcpa/OwcpaDecryptResult.cs b/crypto/src/pqc/crypto/ntru/owcpa/OwcpaDecryptResult.cs new file mode 100644 index 000000000..53f8b4219 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/owcpa/OwcpaDecryptResult.cs @@ -0,0 +1,14 @@ +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.Owcpa +{ + internal class OwcpaDecryptResult + { + internal byte[] Rm; + internal int Fail; + + internal OwcpaDecryptResult(byte[] rm, int fail) + { + Rm = rm; + Fail = fail; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/owcpa/OwcpaKeyPair.cs b/crypto/src/pqc/crypto/ntru/owcpa/OwcpaKeyPair.cs new file mode 100644 index 000000000..305e653d8 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/owcpa/OwcpaKeyPair.cs @@ -0,0 +1,14 @@ +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.Owcpa +{ + internal class OwcpaKeyPair + { + internal readonly byte[] PublicKey; + internal readonly byte[] PrivateKey; + + internal OwcpaKeyPair(byte[] publicKey, byte[] privateKey) + { + PublicKey = publicKey; + PrivateKey = privateKey; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/parametersets/NtruHps2048509.cs b/crypto/src/pqc/crypto/ntru/parametersets/NtruHps2048509.cs new file mode 100644 index 000000000..dcbf47636 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/parametersets/NtruHps2048509.cs @@ -0,0 +1,9 @@ +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets +{ + internal class NtruHps2048509 : NtruHpsParameterSet + { + internal NtruHps2048509() : base(509, 11, 32, 32, 16) + { + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/parametersets/NtruHps2048677.cs b/crypto/src/pqc/crypto/ntru/parametersets/NtruHps2048677.cs new file mode 100644 index 000000000..2076f160d --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/parametersets/NtruHps2048677.cs @@ -0,0 +1,9 @@ +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets +{ + internal class NtruHps2048677 : NtruHpsParameterSet + { + internal NtruHps2048677() : base(677, 11, 32, 32, 24) + { + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/parametersets/NtruHps4096821.cs b/crypto/src/pqc/crypto/ntru/parametersets/NtruHps4096821.cs new file mode 100644 index 000000000..df01f76be --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/parametersets/NtruHps4096821.cs @@ -0,0 +1,16 @@ +using Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets +{ + internal class NtruHps4096821 : NtruHpsParameterSet + { + internal NtruHps4096821() : base(821, 12, 32, 32, 32) + { + } + + internal override Polynomial CreatePolynomial() + { + return new Hps4096Polynomial(this); + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/parametersets/NtruHpsParameterSet.cs b/crypto/src/pqc/crypto/ntru/parametersets/NtruHpsParameterSet.cs new file mode 100644 index 000000000..9b0d04305 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/parametersets/NtruHpsParameterSet.cs @@ -0,0 +1,32 @@ +using Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets +{ + internal class NtruHpsParameterSet : NtruParameterSet + { + private protected NtruHpsParameterSet(int n, int logQ, int seedBytes, int prfKeyBytes, int sharedKeyBytes) : + base(n, logQ, seedBytes, prfKeyBytes, sharedKeyBytes) + { + } + + internal override Polynomial CreatePolynomial() + { + return new HpsPolynomial(this); + } + + internal override int SampleFgBytes() + { + return SampleIidBytes() + SampleFixedTypeBytes(); + } + + internal override int SampleRmBytes() + { + return SampleIidBytes() + SampleFixedTypeBytes(); + } + + internal int Weight() + { + return Q() / 8 - 2; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/parametersets/NtruHrss701.cs b/crypto/src/pqc/crypto/ntru/parametersets/NtruHrss701.cs new file mode 100644 index 000000000..9e795265e --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/parametersets/NtruHrss701.cs @@ -0,0 +1,9 @@ +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets +{ + internal class NtruHrss701 : NtruHrssParameterSet + { + internal NtruHrss701() : base(701, 13, 32, 32, 24) + { + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/parametersets/NtruHrssParameterSet.cs b/crypto/src/pqc/crypto/ntru/parametersets/NtruHrssParameterSet.cs new file mode 100644 index 000000000..8a5e1ab66 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/parametersets/NtruHrssParameterSet.cs @@ -0,0 +1,27 @@ +using Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets +{ + internal class NtruHrssParameterSet : NtruParameterSet + { + private protected NtruHrssParameterSet(int n, int logQ, int seedBytes, int prfKeyBytes, int sharedKeyBytes) : + base(n, logQ, seedBytes, prfKeyBytes, sharedKeyBytes) + { + } + + internal override Polynomial CreatePolynomial() + { + return new HrssPolynomial(this); + } + + internal override int SampleFgBytes() + { + return 2 * SampleIidBytes(); + } + + internal override int SampleRmBytes() + { + return 2 * SampleIidBytes(); + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/parametersets/NtruParameterSet.cs b/crypto/src/pqc/crypto/ntru/parametersets/NtruParameterSet.cs new file mode 100644 index 000000000..c105e0cd3 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/parametersets/NtruParameterSet.cs @@ -0,0 +1,88 @@ +using Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets +{ + internal abstract class NtruParameterSet + { + internal int N { get; } + internal int LogQ { get; } + internal int SeedBytes { get; } + internal int PrfKeyBytes { get; } + internal int SharedKeyBytes { get; } + + internal NtruParameterSet(int n, int logQ, int seedBytes, int prfKeyBytes, int sharedKeyBytes) + { + N = n; + LogQ = logQ; + SeedBytes = seedBytes; + PrfKeyBytes = prfKeyBytes; + SharedKeyBytes = sharedKeyBytes; + } + + internal abstract Polynomial CreatePolynomial(); + + internal int Q() + { + return 1 << LogQ; + } + + internal int SampleIidBytes() + { + return N - 1; + } + + internal int SampleFixedTypeBytes() + { + return (30 * (N - 1) + 7) / 8; + } + + internal abstract int SampleFgBytes(); + + internal abstract int SampleRmBytes(); + + internal int PackDegree() + { + return N - 1; + } + + internal int PackTrinaryBytes() + { + return (PackDegree() + 4) / 5; + } + + internal int OwcpaMsgBytes() + { + return 2 * PackTrinaryBytes(); + } + + internal int OwcpaPublicKeyBytes() + { + return (LogQ * PackDegree() + 7) / 8; + } + + internal int OwcpaSecretKeyBytes() + { + return 2 * PackTrinaryBytes() + OwcpaPublicKeyBytes(); + } + + internal int OwcpaBytes() + { + return (LogQ * PackDegree() + 7) / 8; + } + + internal int NtruPublicKeyBytes() + { + return OwcpaPublicKeyBytes(); + } + + internal int NtruSecretKeyBytes() + { + return OwcpaSecretKeyBytes() + PrfKeyBytes; + } + + internal int NtruCiphertextBytes() + { + return OwcpaBytes(); + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/polynomials/Hps4096Polynomial.cs b/crypto/src/pqc/crypto/ntru/polynomials/Hps4096Polynomial.cs new file mode 100644 index 000000000..9a0d97759 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/polynomials/Hps4096Polynomial.cs @@ -0,0 +1,42 @@ +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials +{ + internal class Hps4096Polynomial : HpsPolynomial + { + public Hps4096Polynomial(NtruParameterSet parameterSet) : base(parameterSet) + { + } + + public override byte[] SqToBytes(int len) + { + byte[] r = new byte[len]; + uint q = (uint)ParameterSet.Q(); + int i; + + for (i = 0; i < ParameterSet.PackDegree() / 2; i++) + { + r[3 * i + 0] = (byte)(ModQ(((uint)coeffs[2 * i + 0] & 0xffff), q) & 0xff); + r[3 * i + 1] = (byte)((ModQ(((uint)coeffs[2 * i + 0] & 0xffff), q) >> 8) | + ((ModQ((uint)(coeffs[2 * i + 1] & 0xffff), q) & 0x0f) << 4)); + r[3 * i + 2] = (byte)((ModQ(((uint)coeffs[2 * i + 1] & 0xffff), q) >> 4)); + } + + return r; + } + + public override void SqFromBytes(byte[] a) + { + int i; + for (i = 0; i < ParameterSet.PackDegree() / 2; i++) + { + coeffs[2 * i + 0] = + (ushort)(((a[3 * i + 0] & 0xff) >> 0) | (((ushort)(a[3 * i + 1] & 0xff) & 0x0f) << 8)); + coeffs[2 * i + 1] = + (ushort)(((a[3 * i + 1] & 0xff) >> 4) | (((ushort)(a[3 * i + 2] & 0xff) & 0xff) << 4)); + } + + coeffs[ParameterSet.N - 1] = 0; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/polynomials/HpsPolynomial.cs b/crypto/src/pqc/crypto/ntru/polynomials/HpsPolynomial.cs new file mode 100644 index 000000000..6097912a1 --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/polynomials/HpsPolynomial.cs @@ -0,0 +1,162 @@ +using System; +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials +{ + internal class HpsPolynomial : Polynomial + { + public HpsPolynomial(NtruParameterSet parameterSet) : base(parameterSet) + { + } + + public override byte[] SqToBytes(int len) + { + byte[] r = new byte[len]; + + int i, j; + short[] t = new short[8]; + for (i = 0; + i < ParameterSet.PackDegree() / 8; + i++) + { + for (j = 0; j < 8; j++) + { + t[j] = (short)ModQ((uint)coeffs[8 * i + j] & 0xffff, (uint)ParameterSet.Q()); + } + + r[11 * i + 0] = (byte)(t[0] & 0xff); + r[11 * i + 1] = (byte)((t[0] >> 8) | ((t[1] & 0x1f) << 3)); + r[11 * i + 2] = (byte)((t[1] >> 5) | ((t[2] & 0x03) << 6)); + r[11 * i + 3] = (byte)((t[2] >> 2) & 0xff); + r[11 * i + 4] = (byte)((t[2] >> 10) | ((t[3] & 0x7f) << 1)); + r[11 * i + 5] = (byte)((t[3] >> 7) | ((t[4] & 0x0f) << 4)); + r[11 * i + 6] = (byte)((t[4] >> 4) | ((t[5] & 0x01) << 7)); + r[11 * i + 7] = (byte)((t[5] >> 1) & 0xff); + r[11 * i + 8] = (byte)((t[5] >> 9) | ((t[6] & 0x3f) << 2)); + r[11 * i + 9] = (byte)((t[6] >> 6) | ((t[7] & 0x07) << 5)); + r[11 * i + 10] = (byte)(t[7] >> 3); + } + + for (j = 0; j < ParameterSet.PackDegree() - 8 * i; j++) + { + t[j] = (short)ModQ((uint)coeffs[8 * i + j] & 0xffff, (uint)ParameterSet.Q()); + } + + for (; j < 8; j++) + { + t[j] = 0; + } + + switch (ParameterSet.PackDegree() & 0x07) + { + case 4: + { + r[11 * i + 0] = (byte)(t[0] & 0xff); + r[11 * i + 1] = (byte)((t[0] >> 8) | ((t[1] & 0x1f) << 3)); + r[11 * i + 2] = (byte)((t[1] >> 5) | ((t[2] & 0x03) << 6)); + r[11 * i + 3] = (byte)((t[2] >> 2) & 0xff); + r[11 * i + 4] = (byte)((t[2] >> 10) | ((t[3] & 0x7f) << 1)); + r[11 * i + 5] = (byte)((t[3] >> 7) | ((t[4] & 0x0f) << 4)); + break; + } + case 2: + { + r[11 * i + 0] = (byte)(t[0] & 0xff); + r[11 * i + 1] = (byte)((t[0] >> 8) | ((t[1] & 0x1f) << 3)); + r[11 * i + 2] = (byte)((t[1] >> 5) | ((t[2] & 0x03) << 6)); + break; + } + } + + return r; + } + + public override void SqFromBytes(byte[] a) + { + int n = coeffs.Length; + int i; + for (i = 0; i < ParameterSet.PackDegree() / 8; i++) + { + coeffs[8 * i + 0] = + (ushort)(((a[11 * i + 0] & 0xff) >> 0) | (((ushort)(a[11 * i + 1] & 0xff) & 0x07) << 8)); + coeffs[8 * i + 1] = + (ushort)(((a[11 * i + 1] & 0xff) >> 3) | (((ushort)(a[11 * i + 2] & 0xff) & 0x3f) << 5)); + coeffs[8 * i + 2] = (ushort)(((a[11 * i + 2] & 0xff) >> 6) | + (((ushort)(a[11 * i + 3] & 0xff) & 0xff) << 2) | + (((ushort)(a[11 * i + 4] & 0xff) & 0x01) << 10)); + coeffs[8 * i + 3] = + (ushort)(((a[11 * i + 4] & 0xff) >> 1) | (((ushort)(a[11 * i + 5] & 0xff) & 0x0f) << 7)); + coeffs[8 * i + 4] = + (ushort)(((a[11 * i + 5] & 0xff) >> 4) | (((ushort)(a[11 * i + 6] & 0xff) & 0x7f) << 4)); + coeffs[8 * i + 5] = (ushort)(((a[11 * i + 6] & 0xff) >> 7) | + (((ushort)(a[11 * i + 7] & 0xff) & 0xff) << 1) | + (((ushort)(a[11 * i + 8] & 0xff) & 0x03) << 9)); + coeffs[8 * i + 6] = + (ushort)(((a[11 * i + 8] & 0xff) >> 2) | (((ushort)(a[11 * i + 9] & 0xff) & 0x1f) << 6)); + coeffs[8 * i + 7] = + (ushort)(((a[11 * i + 9] & 0xff) >> 5) | (((ushort)(a[11 * i + 10] & 0xff) & 0xff) << 3)); + } + + switch (ParameterSet.PackDegree() & 0x07) + { + case 4: + { + coeffs[8 * i + 0] = + (ushort)(((a[11 * i + 0] & 0xff) >> 0) | (((ushort)(a[11 * i + 1] & 0xff) & 0x07) << 8)); + coeffs[8 * i + 1] = + (ushort)(((a[11 * i + 1] & 0xff) >> 3) | (((ushort)(a[11 * i + 2] & 0xff) & 0x3f) << 5)); + coeffs[8 * i + 2] = (ushort)(((a[11 * i + 2] & 0xff) >> 6) | + (((ushort)(a[11 * i + 3] & 0xff) & 0xff) << 2) | + (((ushort)(a[11 * i + 4] & 0xff) & 0x01) << 10)); + coeffs[8 * i + 3] = + (ushort)(((a[11 * i + 4] & 0xff) >> 1) | (((ushort)(a[11 * i + 5] & 0xff) & 0x0f) << 7)); + break; + } + case 2: + { + coeffs[8 * i + 0] = + (ushort)(((a[11 * i + 0] & 0xff) >> 0) | (((ushort)(a[11 * i + 1] & 0xff) & 0x07) << 8)); + coeffs[8 * i + 1] = + (ushort)(((a[11 * i + 1] & 0xff) >> 3) | (((ushort)(a[11 * i + 2] & 0xff) & 0x3f) << 5)); + break; + } + } + + coeffs[n - 1] = 0; + } + + public override void Lift(Polynomial a) + { + int n = coeffs.Length; + Array.Copy(a.coeffs, 0, coeffs, 0, n); + Z3ToZq(); + } + + public override void R2Inv(Polynomial a) + { + HpsPolynomial f = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + HpsPolynomial g = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + HpsPolynomial v = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + HpsPolynomial w = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + R2Inv(a, f, g, v, w); + } + + public override void RqInv(Polynomial a) + { + HpsPolynomial ai2 = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + HpsPolynomial b = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + HpsPolynomial c = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + HpsPolynomial s = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + RqInv(a, ai2, b, c, s); + } + + public override void S3Inv(Polynomial a) + { + HpsPolynomial f = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + HpsPolynomial g = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + HpsPolynomial v = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + HpsPolynomial w = new HpsPolynomial((NtruHpsParameterSet)ParameterSet); + S3Inv(a, f, g, v, w); + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/polynomials/HrssPolynomial.cs b/crypto/src/pqc/crypto/ntru/polynomials/HrssPolynomial.cs new file mode 100644 index 000000000..c359bf1ad --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/polynomials/HrssPolynomial.cs @@ -0,0 +1,217 @@ +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials +{ + internal class HrssPolynomial : Polynomial + { + internal HrssPolynomial(NtruParameterSet parameterSet) : base(parameterSet) + { + } + + public override byte[] SqToBytes(int len) + { + // throw new NotImplementedException(); + + byte[] r = new byte[len]; + short[] t = new short[8]; + + int i, j; + + for (i = 0; i < ParameterSet.PackDegree() / 8; i++) + { + for (j = 0; j < 8; j++) + { + t[j] = (short)ModQ((uint)coeffs[8 * i + j] & 0xffff, (uint)ParameterSet.Q()); + } + + r[13 * i + 0] = (byte)(t[0] & 0xff); + r[13 * i + 1] = (byte)((t[0] >> 8) | ((t[1] & 0x07) << 5)); + r[13 * i + 2] = (byte)((t[1] >> 3) & 0xff); + r[13 * i + 3] = (byte)((t[1] >> 11) | ((t[2] & 0x3f) << 2)); + r[13 * i + 4] = (byte)((t[2] >> 6) | ((t[3] & 0x01) << 7)); + r[13 * i + 5] = (byte)((t[3] >> 1) & 0xff); + r[13 * i + 6] = (byte)((t[3] >> 9) | ((t[4] & 0x0f) << 4)); + r[13 * i + 7] = (byte)((t[4] >> 4) & 0xff); + r[13 * i + 8] = (byte)((t[4] >> 12) | ((t[5] & 0x7f) << 1)); + r[13 * i + 9] = (byte)((t[5] >> 7) | ((t[6] & 0x03) << 6)); + r[13 * i + 10] = (byte)((t[6] >> 2) & 0xff); + r[13 * i + 11] = (byte)((t[6] >> 10) | ((t[7] & 0x1f) << 3)); + r[13 * i + 12] = (byte)((t[7] >> 5)); + } + + for (j = 0; j < ParameterSet.PackDegree() - 8 * i; j++) + { + t[j] = (short)ModQ((uint)coeffs[8 * i + j] & 0xffff, (uint)ParameterSet.Q()); + } + + for (; j < 8; j++) + { + t[j] = 0; + } + + switch (ParameterSet.PackDegree() - 8 * (ParameterSet.PackDegree() / 8)) + { + case 4: + { + r[13 * i + 0] = (byte)(t[0] & 0xff); + r[13 * i + 1] = (byte)((t[0] >> 8) | ((t[1] & 0x07) << 5)); + r[13 * i + 2] = (byte)((t[1] >> 3) & 0xff); + r[13 * i + 3] = (byte)((t[1] >> 11) | ((t[2] & 0x3f) << 2)); + r[13 * i + 4] = (byte)((t[2] >> 6) | ((t[3] & 0x01) << 7)); + r[13 * i + 5] = (byte)((t[3] >> 1) & 0xff); + r[13 * i + 6] = (byte)((t[3] >> 9) | ((t[4] & 0x0f) << 4)); + break; + } + case 2: + { + r[13 * i + 0] = (byte)(t[0] & 0xff); + r[13 * i + 1] = (byte)((t[0] >> 8) | ((t[1] & 0x07) << 5)); + r[13 * i + 2] = (byte)((t[1] >> 3) & 0xff); + r[13 * i + 3] = (byte)((t[1] >> 11) | ((t[2] & 0x3f) << 2)); + break; + } + } + + return r; + } + + + public override void SqFromBytes(byte[] a) + { + // throw new NotImplementedException(); + + int i; + + for (i = 0; i < ParameterSet.PackDegree() / 8; i++) + { + coeffs[8 * i + 0] = (ushort)((a[13 * i + 0] & 0xff) | (((ushort)(a[13 * i + 1] & 0xff) & 0x1f) << 8)); + coeffs[8 * i + 1] = (ushort)(((a[13 * i + 1] & 0xff) >> 5) | (((ushort)(a[13 * i + 2] & 0xff)) << 3) | + (((short)(a[13 * i + 3] & 0xff) & 0x03) << 11)); + coeffs[8 * i + 2] = + (ushort)(((a[13 * i + 3] & 0xff) >> 2) | (((ushort)(a[13 * i + 4] & 0xff) & 0x7f) << 6)); + coeffs[8 * i + 3] = (ushort)(((a[13 * i + 4] & 0xff) >> 7) | (((ushort)(a[13 * i + 5] & 0xff)) << 1) | + (((short)(a[13 * i + 6] & 0xff) & 0x0f) << 9)); + coeffs[8 * i + 4] = (ushort)(((a[13 * i + 6] & 0xff) >> 4) | (((ushort)(a[13 * i + 7] & 0xff)) << 4) | + (((short)(a[13 * i + 8] & 0xff) & 0x01) << 12)); + coeffs[8 * i + 5] = + (ushort)(((a[13 * i + 8] & 0xff) >> 1) | (((ushort)(a[13 * i + 9] & 0xff) & 0x3f) << 7)); + coeffs[8 * i + 6] = (ushort)(((a[13 * i + 9] & 0xff) >> 6) | (((ushort)(a[13 * i + 10] & 0xff)) << 2) | + (((short)(a[13 * i + 11] & 0xff) & 0x07) << 10)); + coeffs[8 * i + 7] = (ushort)(((a[13 * i + 11] & 0xff) >> 3) | (((ushort)(a[13 * i + 12] & 0xff)) << 5)); + } + + switch (ParameterSet.PackDegree() & 0x07) + { + case 4: + { + coeffs[8 * i + 0] = + (ushort)((a[13 * i + 0] & 0xff) | (((short)(a[13 * i + 1] & 0xff) & 0x1f) << 8)); + coeffs[8 * i + 1] = (ushort)(((a[13 * i + 1] & 0xff) >> 5) | + (((short)(a[13 * i + 2] & 0xff)) << 3) | + (((short)(a[13 * i + 3] & 0xff) & 0x03) << 11)); + coeffs[8 * i + 2] = + (ushort)(((a[13 * i + 3] & 0xff) >> 2) | (((short)(a[13 * i + 4] & 0xff) & 0x7f) << 6)); + coeffs[8 * i + 3] = (ushort)(((a[13 * i + 4] & 0xff) >> 7) | + (((short)(a[13 * i + 5] & 0xff)) << 1) | + (((short)(a[13 * i + 6] & 0xff) & 0x0f) << 9)); + break; + } + case 2: + { + coeffs[8 * i + 0] = + (ushort)((a[13 * i + 0] & 0xff) | (((short)(a[13 * i + 1] & 0xff) & 0x1f) << 8)); + coeffs[8 * i + 1] = (ushort)(((a[13 * i + 1] & 0xff) >> 5) | + (((short)(a[13 * i + 2] & 0xff)) << 3) | + (((short)(a[13 * i + 3] & 0xff) & 0x03) << 11)); + break; + } + } + + coeffs[ParameterSet.N - 1] = 0; + } + + public override void Lift(Polynomial a) + { + int n = coeffs.Length; + + /* NOTE: Assumes input is in {0,1,2}^N */ + /* Produces output in [0,Q-1]^N */ + int i; + HrssPolynomial b = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + + ushort t, zj; + + /* Define z by <z*x^i, x-1> = delta_{i,0} mod 3: */ + /* t = -1/N mod p = -N mod 3 */ + /* z[0] = 2 - t mod 3 */ + /* z[1] = 0 mod 3 */ + /* z[j] = z[j-1] + t mod 3 */ + /* We'll compute b = a/(x-1) mod (3, Phi) using */ + /* b[0] = <z, a>, b[1] = <z*x,a>, b[2] = <z*x^2,a> */ + /* b[i] = b[i-3] - (a[i] + a[i-1] + a[i-2]) */ + t = (ushort)(3 - (n % 3)); + b.coeffs[0] = (ushort)(a.coeffs[0] * (2 - t) + a.coeffs[1] * 0 + a.coeffs[2] * t); + b.coeffs[1] = (ushort)(a.coeffs[1] * (2 - t) + a.coeffs[2] * 0); + b.coeffs[2] = (ushort)(a.coeffs[2] * (2 - t)); + + zj = 0; /* z[1] */ + for (i = 3; i < n; i++) + { + b.coeffs[0] += (ushort)(a.coeffs[i] * (zj + 2 * t)); + b.coeffs[1] += (ushort)(a.coeffs[i] * (zj + t)); + b.coeffs[2] += (ushort)(a.coeffs[i] * zj); + zj = (ushort)((zj + t) % 3); + } + + b.coeffs[1] += (ushort)(a.coeffs[0] * (zj + t)); + b.coeffs[2] += (ushort)(a.coeffs[0] * zj); + b.coeffs[2] += (ushort)(a.coeffs[1] * (zj + t)); + for (i = 3; i < n; i++) + { + b.coeffs[i] = (ushort)(b.coeffs[i - 3] + 2 * (a.coeffs[i] + a.coeffs[i - 1] + a.coeffs[i - 2])); + } + + + /* Finish reduction mod Phi by subtracting Phi * b[N-1] */ + b.Mod3PhiN(); + + /* Switch from {0,1,2} to {0,1,q-1} coefficient representation */ + b.Z3ToZq(); + + + /* Multiply by (x-1) */ + coeffs[0] = (ushort)-b.coeffs[0]; + for (i = 0; i < n - 1; i++) + { + coeffs[i + 1] = (ushort)(b.coeffs[i] - b.coeffs[i + 1]); + } + } + + public override void R2Inv(Polynomial a) + { + HrssPolynomial f = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + HrssPolynomial g = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + HrssPolynomial v = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + HrssPolynomial w = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + R2Inv(a, f, g, v, w); + } + + public override void RqInv(Polynomial a) + { + HrssPolynomial ai2 = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + HrssPolynomial b = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + HrssPolynomial c = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + HrssPolynomial s = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + RqInv(a, ai2, b, c, s); + } + + public override void S3Inv(Polynomial a) + { + HrssPolynomial f = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + HrssPolynomial g = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + HrssPolynomial v = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + HrssPolynomial w = new HrssPolynomial((NtruHrssParameterSet)ParameterSet); + S3Inv(a, f, g, v, w); + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/crypto/ntru/polynomials/Polynomial.cs b/crypto/src/pqc/crypto/ntru/polynomials/Polynomial.cs new file mode 100644 index 000000000..c4db04d7f --- /dev/null +++ b/crypto/src/pqc/crypto/ntru/polynomials/Polynomial.cs @@ -0,0 +1,417 @@ +using Org.BouncyCastle.Pqc.Crypto.Ntru.ParameterSets; + +namespace Org.BouncyCastle.Pqc.Crypto.Ntru.Polynomials +{ + internal abstract class Polynomial + { + internal ushort[] coeffs; + private protected readonly NtruParameterSet ParameterSet; + + internal Polynomial(NtruParameterSet parameterSet) + { + coeffs = new ushort[parameterSet.N]; + ParameterSet = parameterSet; + } + + internal static short BothNegativeMask(short x, short y) + { + return (short)((x & y) >> 15); + } + + internal static ushort Mod3(ushort a) + { + // return (ushort)(a % 3); + return Mod(a, 3); + } + + internal static byte Mod3(byte a) + { + // return (byte)(a % 3); + return (byte)Mod(a, 3); + } + + // Returns a uint since the reference implementation is a define instead of a normal function + internal static uint ModQ(uint x, uint q) + { + // return x % q; + return Mod(x, q); + } + + // Defined in: poly_mod.c + internal void Mod3PhiN() + { + int n = ParameterSet.N; + for (int i = 0; i < n; i++) + { + coeffs[i] = Mod3((ushort)(coeffs[i] + 2 * coeffs[n - 1])); + } + } + + internal void ModQPhiN() + { + int n = ParameterSet.N; + for (int i = 0; i < n; i++) + { + coeffs[i] = (ushort)(coeffs[i] - coeffs[n - 1]); + } + } + + internal static ushort Mod(double a, double b) + { + return (ushort)(a - b * System.Math.Floor(a / b)); + } + + // Pack Sq polynomial as a byte array + public abstract byte[] SqToBytes(int len); + + // Unpack a Sq polynomial + public abstract void SqFromBytes(byte[] a); + + // Pack a Rq0 polynomial as a byte array + public byte[] RqSumZeroToBytes(int len) + { + return SqToBytes(len); + } + + // Unpack a Rq0 polynomial + public void RqSumZeroFromBytes(byte[] a) + { + int n = coeffs.Length; + + SqFromBytes(a); + coeffs[n - 1] = 0; + for (int i = 0; i < ParameterSet.PackDegree(); i++) + { + coeffs[n - 1] -= coeffs[i]; + } + } + + // Pack an S3 polynomial as a byte array + public byte[] S3ToBytes(int messageSize) + { + byte[] msg = new byte[messageSize]; + byte c; + + for (int i = 0; i < ParameterSet.PackDegree() / 5; i++) + { + c = (byte)(coeffs[5 * i + 4] & 255); + c = (byte)(3 * c + coeffs[5 * i + 3] & 255); + c = (byte)(3 * c + coeffs[5 * i + 2] & 255); + c = (byte)(3 * c + coeffs[5 * i + 1] & 255); + c = (byte)(3 * c + coeffs[5 * i + 0] & 255); + msg[i] = c; + } + + if (ParameterSet.PackDegree() > (ParameterSet.PackDegree() / 5) * 5) + { + int i = ParameterSet.PackDegree() / 5; + c = 0; + + for (int j = ParameterSet.PackDegree() - (5 * i) - 1; j >= 0; j--) + { + c = (byte)(3 * c + coeffs[5 * i + j] & 255); + } + + msg[i] = c; + } + + return msg; + } + + // Unpack an S3 polynomial + public void S3FromBytes(byte[] msg) + { + int n = coeffs.Length; + byte c; + + for (int i = 0; i < ParameterSet.PackDegree() / 5; i++) + { + c = msg[i]; + coeffs[5 * i + 0] = c; + coeffs[5 * i + 1] = (ushort)(c * 171 >> 9); + coeffs[5 * i + 2] = (ushort)(c * 57 >> 9); + coeffs[5 * i + 3] = (ushort)(c * 19 >> 9); + coeffs[5 * i + 4] = (ushort)(c * 203 >> 14); + } + + if (ParameterSet.PackDegree() > (ParameterSet.PackDegree() / 5) * 5) + { + int i = ParameterSet.PackDegree() / 5; + c = msg[i]; + for (int j = 0; (5 * i + j) < ParameterSet.PackDegree(); j++) + { + coeffs[5 * i + j] = c; + c = (byte)(c * 171 >> 9); + } + } + + coeffs[n - 1] = 0; + Mod3PhiN(); + } + + // Defined in: poly_rq_mul.c + public void RqMul(Polynomial a, Polynomial b) + { + int n = coeffs.Length; + int k, i; + + for (k = 0; k < n; k++) + { + coeffs[k] = 0; + for (i = 1; i < n - k; i++) + { + coeffs[k] += (ushort)(a.coeffs[k + i] * b.coeffs[n - i]); + } + + for (i = 0; i < k + 1; i++) + { + coeffs[k] += (ushort)(a.coeffs[k - i] * b.coeffs[i]); + } + } + } + + + // Defined in: poly.c + public void SqMul(Polynomial a, Polynomial b) + { + RqMul(a, b); + ModQPhiN(); + } + + + // Defined in: + public void S3Mul(Polynomial a, Polynomial b) + { + RqMul(a, b); + Mod3PhiN(); + } + + public abstract void Lift(Polynomial a); + + public void RqToS3(Polynomial a) + { + int n = coeffs.Length; + ushort flag; + + for (int i = 0; i < n; i++) + { + coeffs[i] = (ushort)ModQ(a.coeffs[i], (uint)ParameterSet.Q()); + //Console.Write(a.coeffs[i].ToString("X2")); + flag = (ushort)(coeffs[i] >> ParameterSet.LogQ - 1); + coeffs[i] += (ushort)(flag << (1 - (ParameterSet.LogQ & 1))); + } + //Console.WriteLine(); + + Mod3PhiN(); + } + + public abstract void R2Inv(Polynomial a); + + internal void R2Inv(Polynomial a, Polynomial f, Polynomial g, Polynomial v, Polynomial w) + { + int n = coeffs.Length; + int i, loop; + short delta, sign, swap, t; + + w.coeffs[0] = 1; + + for (i = 0; i < n; ++i) + { + f.coeffs[i] = 1; + } + + for (i = 0; i < n - 1; ++i) + { + g.coeffs[n - 2 - i] = (ushort)((a.coeffs[i] ^ a.coeffs[n - 1]) & 1); + } + + g.coeffs[n - 1] = 0; + + delta = 1; + + for (loop = 0; loop < 2 * (n - 1) - 1; ++loop) + { + for (i = n - 1; i > 0; --i) + { + v.coeffs[i] = v.coeffs[i - 1]; + } + + v.coeffs[0] = 0; + + sign = (short)(g.coeffs[0] & f.coeffs[0]); + swap = BothNegativeMask((short)-delta, (short)-g.coeffs[0]); + delta ^= (short)(swap & (delta ^ -delta)); + delta++; + + for (i = 0; i < n; ++i) + { + t = (short)(swap & (f.coeffs[i] ^ g.coeffs[i])); + f.coeffs[i] ^= (ushort)t; + g.coeffs[i] ^= (ushort)t; + t = (short)(swap & (v.coeffs[i] ^ w.coeffs[i])); + v.coeffs[i] ^= (ushort)t; + w.coeffs[i] ^= (ushort)t; + } + + for (i = 0; i < n; ++i) + { + g.coeffs[i] = (ushort)(g.coeffs[i] ^ (sign & f.coeffs[i])); + } + + for (i = 0; i < n; ++i) + { + w.coeffs[i] = (ushort)(w.coeffs[i] ^ (sign & v.coeffs[i])); + } + + for (i = 0; i < n - 1; ++i) + { + g.coeffs[i] = g.coeffs[i + 1]; + } + + g.coeffs[n - 1] = 0; + } + + for (i = 0; i < n - 1; ++i) + { + coeffs[i] = v.coeffs[n - 2 - i]; + } + + coeffs[n - 1] = 0; + } + + public abstract void RqInv(Polynomial a); + + internal void RqInv(Polynomial a, Polynomial ai2, Polynomial b, Polynomial c, Polynomial s) + { + ai2.R2Inv(a); + R2InvToRqInv(ai2, a, b, c, s); + } + + private void R2InvToRqInv(Polynomial ai, Polynomial a, Polynomial b, Polynomial c, Polynomial s) + { + int n = coeffs.Length; + int i; + + for (i = 0; i < n; i++) + { + b.coeffs[i] = (ushort)-a.coeffs[i]; + } + + for (i = 0; i < n; i++) + { + coeffs[i] = ai.coeffs[i]; + } + + c.RqMul(this, b); + c.coeffs[0] += 2; + s.RqMul(c, this); + + c.RqMul(s, b); + c.coeffs[0] += 2; + RqMul(c, s); + + c.RqMul(this, b); + c.coeffs[0] += 2; + s.RqMul(c, this); + + c.RqMul(s, b); + c.coeffs[0] += 2; + RqMul(c, s); + } + + + public abstract void S3Inv(Polynomial a); + + internal void S3Inv(Polynomial a, Polynomial f, Polynomial g, Polynomial v, Polynomial w) + { + int n = coeffs.Length; + int i, loop; + short delta, sign, swap, t; + + w.coeffs[0] = 1; + + for (i = 0; i < n; ++i) + { + f.coeffs[i] = 1; + } + + for (i = 0; i < n - 1; ++i) + { + g.coeffs[n - 2 - i] = Mod3((ushort)((a.coeffs[i] & 3) + 2 * (a.coeffs[n - 1] & 3))); + } + + g.coeffs[n - 1] = 0; + + delta = 1; + + for (loop = 0; loop < 2 * (n - 1) - 1; ++loop) + { + for (i = n - 1; i > 0; --i) + { + v.coeffs[i] = v.coeffs[i - 1]; + } + + v.coeffs[0] = 0; + + sign = Mod3((byte)(2 * g.coeffs[0] * f.coeffs[0])); + swap = BothNegativeMask((short)-delta, (short)-g.coeffs[0]); + delta ^= (short)(swap & (delta ^ -delta)); + delta++; + + for (i = 0; i < n; ++i) + { + t = (short)(swap & (f.coeffs[i] ^ g.coeffs[i])); + f.coeffs[i] ^= (ushort)t; + g.coeffs[i] ^= (ushort)t; + t = (short)(swap & (v.coeffs[i] ^ w.coeffs[i])); + v.coeffs[i] ^= (ushort)t; + w.coeffs[i] ^= (ushort)t; + } + + for (i = 0; i < n; ++i) + { + g.coeffs[i] = Mod3((byte)(g.coeffs[i] + sign * f.coeffs[i])); + } + + for (i = 0; i < n; ++i) + { + w.coeffs[i] = Mod3((byte)(w.coeffs[i] + sign * v.coeffs[i])); + } + + for (i = 0; i < n - 1; ++i) + { + g.coeffs[i] = g.coeffs[i + 1]; + } + + g.coeffs[n - 1] = 0; + } + + sign = (short)f.coeffs[0]; + for (i = 0; i < n - 1; ++i) + { + coeffs[i] = Mod3((byte)(sign * v.coeffs[n - 2 - i])); + } + + coeffs[n - 1] = 0; + } + + public void Z3ToZq() + { + int n = coeffs.Length; + for (int i = 0; i < n; i++) + { + coeffs[i] = (ushort)(coeffs[i] | (-(coeffs[i] >> 1) & (ParameterSet.Q() - 1))); + } + } + + public void TrinaryZqToZ3() + { + int n = coeffs.Length; + for (int i = 0; i < n; i++) + { + coeffs[i] = (ushort)ModQ((uint)(coeffs[i] & 0xffff), (uint)ParameterSet.Q()); + coeffs[i] = (ushort)(3 & (coeffs[i] ^ (coeffs[i] >> (ParameterSet.LogQ - 1)))); + } + } + } +} \ No newline at end of file |