version3/go/NHS.go

/*
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements.  See the NOTICE file
distributed with this work for additional information
regarding copyright ownership.  The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License.  You may obtain a copy of the License at

  http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied.  See the License for the
specific language governing permissions and limitations
under the License.
*/

/*
 * Implementation of the Secure Hashing Algorithm (SHA-384)
 *
 * Generates a 384 bit message digest. It should be impossible to come
 * come up with two messages that hash to the same value ("collision free").
 *
 * For use with byte-oriented messages only. 
 */

//nhs_package main

package amcl

//import "fmt"


const NHS_PRIME int32=0x3001	// q in Hex
const NHS_LGN uint=10		// Degree n=2^LGN
const NHS_ND uint32=0xF7002FFF	// 1/(R-q) mod R
const NHS_ONE int32=0x2AC8	// R mod q
const NHS_R2MODP uint64=0x1620	// R^2 mod q


const NHS_DEGREE int=(1<<NHS_LGN)
const NHS_WL uint=32

const NHS_inv int32=  0xeab
const NHS_invpr int32= 0x2c2a

var NHS_roots = [1024] int32 {0x2ac8,0x2baf,0x299b,0x685,0x2f04,0x158d,0x2d49,0x24b5,0x1edc,0xab3,0x2a95,0x24d,0x3cb,0x6a8,0x12f9,0x15ba,0x1861,0x2a89,0x1c5c,0xbe6,0xc1e,0x2024,0x207,0x19ce,0x2710,0x1744,0x18bc,0x2cd7,0x396,0x18d5,0x1c45,0xc4,0x21a6,0xe03,0x2b3c,0x2d91,0xc5d,0x432,0x1fbc,0xcae,0x2512,0x2979,0x3b2,0x714,0xb2e,0x1a97,0x1a03,0x1bcd,0x2216,0x2701,0xa,0x263c,0x1179,0x200c,0x2d08,0x1c34,0x291,0x2c99,0x2a5a,0x723,0xb1d,0x1ccc,0x1fb6,0x2f58,0x2bfe,0x1cda,0x2a0,0x5f1,0x2de,0x1fc7,0x1ea8,0x1719,0x2fa7,0x27ec,0x20ff,0x12c0,0x1ac1,0x2232,0x2f9b,0xd3e,0x2aed,0x15f0,0x11e8,0xed0,0x26a,0x1de5,0xa3f,0xf43,0xebf,0x204e,0xac7,0x2d9c,0x5ea,0x25d1,0xb6,0x49c,0x995,0x2555,0x26e2,0x100,0x1878,0x5aa,0x2e10,0x271c,0xcb,0x1b4c,0x2fb8,0x25b7,0x1543,0x2c7b,0x241a,0x2223,0x20ca,0x24ed,0x137,0x1b65,0x1dc2,0x7c7,0x2ec3,0xd0c,0x1169,0x1c7a,0x1ea1,0xf89,0x2199,0x291d,0x1088,0x2046,0x256d,0x2bc7,0x2e9b,0x41f,0x1b55,0x2b38,0xd0,0x2e6a,0x1755,0x6bc,0x2724,0x3ba,0x222e,0x2c5c,0x2da5,0x213c,0x10fe,0x169a,0x1552,0x5d3,0x300,0x1b5d,0x1342,0x2004,0x256f,0x2039,0x667,0x23b5,0x1123,0xdb,0x2da0,0xe1e,0x2f54,0x2767,0x154a,0x40a,0x11d3,0x2821,0xc09,0x974,0x694,0xfbf,0x27ba,0x132,0x83f,0x2d06,0x10e,0x183f,0x29ae,0x28c3,0x2dc9,0x1144,0x2c70,0x2a4a,0xf3c,0x1e32,0x1171,0x1e43,0xdd4,0x2ddf,0x28d2,0xfac,0x3c4,0x2f19,0x10a6,0x2f7,0xe1d,0x828,0x138f,0x1332,0xfab,0xcf6,0x13f8,0x24a0,0x112d,0x2717,0x6e7,0x1044,0x36e,0xfe8,0x6a,0xba7,0x1d69,0x29ec,0x23b2,0xaee,0x16df,0x1068,0x1a7e,0x253f,0x24c,0xb33,0x2683,0x15ce,0x1ad3,0x1a36,0xc96,0xaea,0x260a,0xce,0x28b1,0xe4f,0x2b11,0x5f8,0x1fc4,0xe77,0x2366,0x11f9,0x153c,0x24eb,0x20cd,0x1398,0x22,0x2b97,0x249b,0x8eb,0x12b2,0x2fe3,0x29c1,0x1b00,0x2663,0xeaa,0x2e06,0xe0,0x1569,0x10f5,0x284e,0xa38,0x201d,0x1c53,0x1681,0x1f6f,0x2f95,0x2fe8,0xacb,0x1680,0x17fd,0x2c39,0x165a,0x10bb,0x29d8,0x2622,0x1196,0x884,0x2a79,0x140e,0x2d80,0x6fa,0x11b2,0x26c4,0x355,0x1054,0x29e9,0x23ed,0xbe3,0x24fa,0x1fb3,0x10ac,0x2919,0x2584,0x10a4,0xe85,0x650,0x1893,0x1dc1,0xd8e,0x12dc,0x2d42,0x284d,0xfff,0x250f,0xacd,0x13c3,0x6cc,0x1a79,0x1221,0x2614,0x270a,0x1ea,0x155,0x2818,0x222c,0x2e5b,0x25d8,0x1dbf,0x191c,0xb0f,0xdac,0x1082,0x12ef,0x11b6,0xfa8,0x2b72,0x159d,0x209e,0x31b,0x2c7c,0x14f7,0xe09,0x1bb2,0x1ec7,0x2404,0x20ae,0x6ad,0xed6,0x2b70,0x1c7b,0x18d1,0x2732,0x12da,0xd56,0x5c1,0x1648,0x18b7,0x1605,0x1bc4,0x280,0x2ece,0xc,0x1aae,0x1c4,0x1cdb,0x22d6,0x21d8,0x257c,0x51f,0x211b,0xff,0x2ee0,0x2585,0xe1,0x2c35,0x26db,0x2971,0x2208,0x17e1,0x21be,0x135e,0x28d6,0x2891,0x1689,0x2138,0xb86,0x2e3a,0x1204,0x2d10,0x2324,0xf3f,0x2508,0x33d,0xcb2,0x292a,0xe27,0x2e64,0x29f8,0x2d46,0x9b7,0x20eb,0x1b7c,0x9eb,0x2b2a,0x58c,0x27d0,0x121b,0x272e,0x29f6,0x2dbd,0x2697,0x2aac,0xd6f,0x1c67,0x2c5b,0x108d,0x363,0x249d,0x2d5e,0x2fd,0x2cb2,0x1f8f,0x20a4,0xa19,0x2ac9,0x19b1,0x1581,0x17a2,0x29eb,0x1b72,0x13b0,0xee4,0xa8f,0x2315,0x5e6,0x951,0x2e29,0xdad,0x1f2b,0x224e,0x37f,0x1a72,0xa91,0x1407,0x2df9,0x3ad,0x23f7,0x1a24,0x1d2a,0x234b,0x1df3,0x1143,0x7ff,0x1a6d,0x2774,0x2690,0x2ab5,0x586,0x2781,0x2009,0x2fdd,0x2881,0x399,0x2fb6,0x144,0x137f,0xfa0,0x2e4c,0x1c7f,0x2fac,0xb09,0x1264,0x127b,0x198c,0x2b40,0x230,0x1cf4,0x180b,0xb58,0x144a,0x2aec,0xfb,0x2602,0x14ee,0x783,0x1098,0x23d8,0x203,0xe9,0x108a,0x14b8,0xeec,0xc58,0x1248,0x243c,0x28aa,0x6bf,0x27c4,0x276e,0x19b8,0x1d11,0x2e16,0x472,0x1464,0x24b9,0x662,0x1097,0x2067,0x20d6,0x171c,0x4,0x682,0x17bb,0x1186,0x4f2,0x3ff,0x2a43,0x1dc7,0x1ae5,0x8cc,0x2e7c,0x2ef8,0x2ae0,0x2904,0xed4,0x6c5,0x14ae,0xb72,0x11c3,0x337,0x2da3,0x2916,0x6d8,0x1cf9,0x10ee,0x1800,0x1ae4,0xa0d,0x101b,0x1a8d,0x2e98,0x24cd,0x813,0x1aa4,0x9b9,0x680,0x2349,0x24d1,0x20f8,0xe31,0x249f,0x216b,0x12d9,0x1d21,0x19db,0x191a,0x1dd0,0x5df,0x55c,0x2b86,0x213,0xe9e,0x1ef1,0x268a,0x1d5e,0x1e20,0x28c1,0x1379,0x249,0x19de,0x18b,0x1e41,0x2a1e,0x2612,0x297,0x2e96,0x2102,0x46,0x1b9f,0x1a4d,0x2050,0x1b32,0x568,0x11f7,0x1829,0x870,0x1f4,0x1dca,0x990,0x1df6,0x2b62,0x13ec,0x9f2,0x1260,0x2997,0x1412,0x1e6d,0x1694,0x11ac,0x2d8b,0x276f,0x26f5,0x233e,0x2b44,0x2f5a,0x2d37,0x2cb1,0xc75,0x98d,0x1d56,0x7ae,0x10e6,0x113f,0x17b8,0xad3,0x737,0x221e,0x1b70,0x1f3e,0x2966,0x18b2,0x4fa,0x2044,0x1312,0x154e,0x2029,0x700,0x1b45,0x27a6,0x226a,0x21bf,0x58d,0x2f11,0x2e02,0x17fc,0x4d2,0x1757,0xcb1,0x2ef1,0x2582,0x1276,0x881,0x2fc0,0x104a,0x670,0x274f,0x2b53,0x19dd,0x752,0x1663,0xcbd,0x2b2b,0x2fc6,0x13b6,0x21e6,0x15f6,0x126b,0x2637,0x1cd9,0x2f50,0xe82,0x5b0,0x24e0,0x1350,0x2f24,0x21f7,0x1a16,0x2f3e,0x167e,0x1f7d,0x28a0,0x16f0,0xe33,0x53b,0x28c5,0x1500,0x2f88,0x26cc,0x2018,0x1604,0x218b,0x2cd1,0x9ee,0x17f3,0x5fd,0x1f5a,0x2d0,0x2b46,0x23cc,0x503,0x1c46,0x1cc3,0x28e2,0x243e,0x122b,0x2e0c,0xe37,0x2611,0x85e,0x9b8,0x1b24,0x762,0x19b6,0x3bc,0x2d50,0x2079,0x18da,0x170a,0x800,0xaa2,0x135a,0x1a15,0x13d1,0xca,0x2113,0x2db9,0xdb2,0x1a5c,0x29a9,0x1488,0x14c1,0x2c9,0x917,0x28e7,0x265c,0xdab,0x2ab9,0x2bc6,0x105b,0x1839,0x219c,0x50,0x11da,0x1802,0xf56,0x2e6,0x2190,0xddb,0x56e,0x9d9,0x1c81,0x1016,0x12d6,0x296f,0x14b4,0x1014,0x1e64,0x1d90,0x89f,0x2bc2,0x2777,0x2819,0x1c65,0x1a41,0x5a2,0x2cd2,0x427,0xd71,0x29c8,0x1e58,0x53f,0x7c5,0x1dcd,0x4a1,0x1268,0x2597,0x2926,0xee,0x111b,0x1038,0xe6c,0x22dc,0x2f2f,0x441,0x2cfd,0x1cb0,0x6a4,0x2224,0x620,0x5dc,0x16b1,0x2a1d,0x1787,0x20c7,0x641,0xd84,0x1c05,0x2d0d,0x2f52,0x1b8c,0xd7d,0x17e8,0x1589,0xc73,0x151b,0x4e2,0x1ae9,0x1b18,0xb9b,0x949,0x2c60,0x1e7a,0xd5,0x1bdc,0x1f57,0x1753,0x124a,0x559,0xb76,0x2334,0x12d1,0x1de1,0x14b2,0x2faa,0x1697,0x147a,0x5a1,0x2c30,0x1c02,0x1043,0x2ee1,0x2402,0x1cc8,0x2a16,0xff7,0x1364,0x1b9a,0x2a53,0x2f94,0x294c,0x1ee5,0x1a87,0x2141,0xd66,0x953,0x28a3,0x2f30,0x2477,0x18e3,0x1035,0x1fc1,0x1d68,0x2fb3,0x138c,0x2487,0x1bf8,0xd96,0x1018,0x748,0x244e,0x15bd,0x175e,0x2be,0x23d,0x1da,0x176d,0xc17,0x24be,0x2ebb,0x7d8,0x100a,0x759,0x1db4,0x2259,0x23f4,0x2d59,0x2847,0xbf5,0x1cfe,0xa20,0x258,0x1180,0x279c,0x54,0x2abf,0xc5c,0x9f9,0x3d5,0x2ce4,0x165f,0x23d9,0x27b9,0x6f9,0x281a,0x169e,0x627,0x156d,0x1ff8,0x211,0x2e34,0x1724,0x2c2e,0x2790,0x2dd5,0x2bf2,0xdbc,0x2884,0x20a9,0x2390,0x1e1a,0x1b6a,0x5f7,0xab7,0x1333,0x16ab,0x28dd,0x20,0x30f,0x24b6,0x5c2,0x1ce4,0x1400,0x2669,0x60,0x156c,0xe20,0x26d4,0x26ab,0x1ebb,0x223d,0x5b4,0x2025,0x1e1c,0xaae,0x2e08,0x6cd,0x1677,0x13d9,0x17b5,0x1046,0x1d8c,0x14eb,0x18d8,0x1ce5,0x2478,0x16ae,0xb79,0x23d4,0x684,0x156b,0x567,0x1a,0x29ce,0x83a,0x19e8,0x58e,0x294a,0x1136,0x2319,0x2fba,0x1a29,0x1d,0x1879,0x291b,0x19f6,0x2c2f,0x21c9,0x19bb,0xbbc,0x26f9,0xc22,0x708,0x11a1,0x18d3,0x7f8,0x28f8,0x2427,0x1deb,0xaed,0x26aa,0x2482,0x203b,0x2f05,0x2b82,0x192f,0x2df4,0x8dc,0x2877,0xd5e,0x240e,0x775,0x2dae,0x1d3e,0x20ba,0x215b,0x22d1,0xeba,0xf50,0xaa8,0x184a,0x1f67,0x2e04,0xc6e,0x6dd,0x1a09,0x27f,0x494,0x1426,0xae3,0xe15,0x65f,0x13c4,0x105,0x872,0x2667,0x1ff6,0xd9f,0x2ca1,0x2f39,0x2657,0x23fd,0x2405,0xb73,0x2294,0x1f1e,0x2eba,0x110a,0x2cae,0x141f,0x22cd,0x25d6,0x11c1,0x1c,0x2d8e,0x161a,0x1aa8,0x229e,0x1bf9,0x7cf,0x106d,0x2c40,0xd93,0x255e,0x28c2,0xc1a,0x2f17,0x7ca,0x2f63,0xbf};
var NHS_iroots= [1024] int32 {0x2ac8,0x452,0x297c,0x666,0xb4c,0x2b8,0x1a74,0xfd,0x1a47,0x1d08,0x2959,0x2c36,0x2db4,0x56c,0x254e,0x1125,0x2f3d,0x13bc,0x172c,0x2c6b,0x32a,0x1745,0x18bd,0x8f1,0x1633,0x2dfa,0xfdd,0x23e3,0x241b,0x13a5,0x578,0x17a0,0xa9,0x104b,0x1335,0x24e4,0x28de,0x5a7,0x368,0x2d70,0x13cd,0x2f9,0xff5,0x1e88,0x9c5,0x2ff7,0x900,0xdeb,0x1434,0x15fe,0x156a,0x24d3,0x28ed,0x2c4f,0x688,0xaef,0x2353,0x1045,0x2bcf,0x23a4,0x270,0x4c5,0x21fe,0xe5b,0xfbb,0x1f79,0x6e4,0xe68,0x2078,0x1160,0x1387,0x1e98,0x22f5,0x13e,0x283a,0x123f,0x149c,0x2eca,0xb14,0xf37,0xdde,0xbe7,0x386,0x1abe,0xa4a,0x49,0x14b5,0x2f36,0x8e5,0x1f1,0x2a57,0x1789,0x2f01,0x91f,0xaac,0x266c,0x2b65,0x2f4b,0xa30,0x2a17,0x265,0x253a,0xfb3,0x2142,0x20be,0x25c2,0x121c,0x2d97,0x2131,0x1e19,0x1a11,0x514,0x22c3,0x66,0xdcf,0x1540,0x1d41,0xf02,0x815,0x5a,0x18e8,0x1159,0x103a,0x2d23,0x2a10,0x2d61,0x1327,0x403,0x25c9,0x7b3,0x1f0c,0x1a98,0x2f21,0x1fb,0x2157,0x99e,0x1501,0x640,0x1e,0x1d4f,0x2716,0xb66,0x46a,0x2fdf,0x1c69,0xf34,0xb16,0x1ac5,0x1e08,0xc9b,0x218a,0x103d,0x2a09,0x4f0,0x21b2,0x750,0x2f33,0x9f7,0x2517,0x236b,0x15cb,0x152e,0x1a33,0x97e,0x24ce,0x2db5,0xac2,0x1583,0x1f99,0x1922,0x2513,0xc4f,0x615,0x1298,0x245a,0x2f97,0x2019,0x2c93,0x1fbd,0x291a,0x8ea,0x1ed4,0xb61,0x1c09,0x230b,0x2056,0x1ccf,0x1c72,0x27d9,0x21e4,0x2d0a,0x1f5b,0xe8,0x2c3d,0x2055,0x72f,0x222,0x222d,0x11be,0x1e90,0x11cf,0x20c5,0x5b7,0x391,0x1ebd,0x238,0x73e,0x653,0x17c2,0x2ef3,0x2fb,0x27c2,0x2ecf,0x847,0x2042,0x296d,0x268d,0x23f8,0x7e0,0x1e2e,0x2bf7,0x1ab7,0x89a,0xad,0x21e3,0x261,0x2f26,0x1ede,0xc4c,0x299a,0xfc8,0xa92,0xffd,0x1cbf,0x14a4,0x2d01,0x2a2e,0x1aaf,0x1967,0x1f03,0xec5,0x25c,0x3a5,0xdd3,0x2c47,0x8dd,0x2945,0x18ac,0x197,0x2f31,0x4c9,0x14ac,0x2be2,0x166,0x43a,0xa94,0x1b53,0x293c,0x212d,0x6fd,0x521,0x109,0x185,0x2735,0x151c,0x123a,0x5be,0x2c02,0x2b0f,0x1e7b,0x1846,0x297f,0x2ffd,0x18e5,0xf2b,0xf9a,0x1f6a,0x299f,0xb48,0x1b9d,0x2b8f,0x1eb,0x12f0,0x1649,0x893,0x83d,0x2942,0x757,0xbc5,0x1db9,0x23a9,0x2115,0x1b49,0x1f77,0x2f18,0x2dfe,0xc29,0x1f69,0x287e,0x1b13,0x9ff,0x2f06,0x515,0x1bb7,0x24a9,0x17f6,0x130d,0x2dd1,0x4c1,0x1675,0x1d86,0x1d9d,0x24f8,0x55,0x1382,0x1b5,0x2061,0x1c82,0x2ebd,0x4b,0x2c68,0x780,0x24,0xff8,0x880,0x2a7b,0x54c,0x971,0x88d,0x1594,0x2802,0x1ebe,0x120e,0xcb6,0x12d7,0x15dd,0xc0a,0x2c54,0x208,0x1bfa,0x2570,0x158f,0x2c82,0xdb3,0x10d6,0x2254,0x1d8,0x26b0,0x2a1b,0xcec,0x2572,0x211d,0x1c51,0x148f,0x616,0x185f,0x1a80,0x1650,0x538,0x25e8,0xf5d,0x1072,0x34f,0x2d04,0x2a3,0xb64,0x2c9e,0x1f74,0x3a6,0x139a,0x2292,0x555,0x96a,0x244,0x60b,0x8d3,0x1de6,0x831,0x2a75,0x4d7,0x2616,0x1485,0xf16,0x264a,0x2bb,0x609,0x19d,0x21da,0x6d7,0x234f,0x2cc4,0xaf9,0x20c2,0xcdd,0x2f1,0x1dfd,0x1c7,0x247b,0xec9,0x1978,0x770,0x72b,0x1ca3,0xe43,0x1820,0xdf9,0x690,0x926,0x3cc,0x2f20,0xa7c,0x121,0x2f02,0xee6,0x2ae2,0xa85,0xe29,0xd2b,0x1326,0x2e3d,0x1553,0x2ff5,0x133,0x2d81,0x143d,0x19fc,0x174a,0x19b9,0x2a40,0x22ab,0x1d27,0x8cf,0x1730,0x1386,0x491,0x212b,0x2954,0xf53,0xbfd,0x113a,0x144f,0x21f8,0x1b0a,0x385,0x2ce6,0xf63,0x1a64,0x48f,0x2059,0x1e4b,0x1d12,0x1f7f,0x2255,0x24f2,0x16e5,0x1242,0xa29,0x1a6,0xdd5,0x7e9,0x2eac,0x2e17,0x8f7,0x9ed,0x1de0,0x1588,0x2935,0x1c3e,0x2534,0xaf2,0x2002,0x7b4,0x2bf,0x1d25,0x2273,0x1240,0x176e,0x29b1,0x217c,0x1f5d,0xa7d,0x6e8,0x1f55,0x104e,0xb07,0x241e,0xc14,0x618,0x1fad,0x2cac,0x93d,0x1e4f,0x2907,0x281,0x1bf3,0x588,0x277d,0x1e6b,0x9df,0x629,0x1f46,0x19a7,0x3c8,0x1804,0x1981,0x2536,0x19,0x6c,0x1092,0x1980,0x13ae,0xfe4,0x2f42,0x9e,0x2837,0xea,0x23e7,0x73f,0xaa3,0x226e,0x3c1,0x1f94,0x2832,0x1408,0xd63,0x1559,0x19e7,0x273,0x2fe5,0x1e40,0xa2b,0xd34,0x1be2,0x353,0x1ef7,0x147,0x10e3,0xd6d,0x248e,0xbfc,0xc04,0x9aa,0xc8,0x360,0x2262,0x100b,0x99a,0x278f,0x2efc,0x1c3d,0x29a2,0x21ec,0x251e,0x1bdb,0x2b6d,0x2d82,0x15f8,0x2924,0x2393,0x1fd,0x109a,0x17b7,0x2559,0x20b1,0x2147,0xd30,0xea6,0xf47,0x12c3,0x253,0x288c,0xbf3,0x22a3,0x78a,0x2725,0x20d,0x16d2,0x47f,0xfc,0xfc6,0xb7f,0x957,0x2514,0x1216,0xbda,0x709,0x2809,0x172e,0x1e60,0x28f9,0x23df,0x908,0x2445,0x1646,0xe38,0x3d2,0x160b,0x6e6,0x1788,0x2fe4,0x15d8,0x47,0xce8,0x1ecb,0x6b7,0x2a73,0x1619,0x27c7,0x633,0x2fe7,0x2a9a,0x1a96,0x297d,0xc2d,0x2488,0x1953,0xb89,0x131c,0x1729,0x1b16,0x1275,0x1fbb,0x184c,0x1c28,0x198a,0x2934,0x1f9,0x2553,0x11e5,0xfdc,0x2a4d,0xdc4,0x1146,0x956,0x92d,0x21e1,0x1a95,0x2fa1,0x998,0x1c01,0x131d,0x2a3f,0xb4b,0x2cf2,0x2fe1,0x724,0x1956,0x1cce,0x254a,0x2a0a,0x1497,0x11e7,0xc71,0xf58,0x77d,0x2245,0x40f,0x22c,0x871,0x3d3,0x18dd,0x1cd,0x2df0,0x1009,0x1a94,0x29da,0x1963,0x7e7,0x2908,0x848,0xc28,0x19a2,0x31d,0x2c2c,0x2608,0x23a5,0x542,0x2fad,0x865,0x1e81,0x2da9,0x25e1,0x1303,0x240c,0x7ba,0x2a8,0xc0d,0xda8,0x124d,0x28a8,0x1ff7,0x2829,0x146,0xb43,0x23ea,0x1894,0x2e27,0x2dc4,0x2d43,0x18a3,0x1a44,0xbb3,0x28b9,0x1fe9,0x226b,0x1409,0xb7a,0x1c75,0x4e,0x1299,0x1040,0x1fcc,0x171e,0xb8a,0xd1,0x75e,0x26ae,0x229b,0xec0,0x157a,0x111c,0x6b5,0x6d,0x5ae,0x1467,0x1c9d,0x200a,0x5eb,0x1339,0xbff,0x120,0x1fbe,0x13ff,0x3d1,0x2a60,0x1b87,0x196a,0x57,0x1b4f,0x1220,0x1d30,0xccd,0x248b,0x2aa8,0x1db7,0x18ae,0x10aa,0x1425,0x2f2c,0x1187,0x3a1,0x26b8,0x2466,0x14e9,0x1518,0x2b1f,0x1ae6,0x238e,0x1a78,0x1819,0x2284,0x1475,0xaf,0x2f4,0x13fc,0x227d,0x29c0,0xf3a,0x187a,0x5e4,0x1950,0x2a25,0x29e1,0xddd,0x295d,0x1351,0x304,0x2bc0,0xd2,0xd25,0x2195,0x1fc9,0x1ee6,0x2f13,0x6db,0xa6a,0x1d99,0x2b60,0x1234,0x283c,0x2ac2,0x11a9,0x639,0x2290,0x2bda,0x32f,0x2a5f,0x15c0,0x139c,0x7e8,0x88a,0x43f,0x2762,0x1271,0x119d,0x1fed,0x1b4d,0x692,0x1d2b,0x1feb,0x1380,0x2628,0x2a93,0x2226,0xe71,0x2d1b,0x20ab,0x17ff,0x1e27,0x2fb1,0xe65,0x17c8,0x1fa6,0x43b,0x548,0x2256,0x9a5,0x71a,0x26ea,0x2d38,0x1b40,0x1b79,0x658,0x15a5,0x224f,0x248,0xeee,0x2f37,0x1c30,0x15ec,0x1ca7,0x255f,0x2801,0x18f7,0x1727,0xf88,0x2b1,0x2c45,0x164b,0x289f,0x14dd,0x2649,0x27a3,0x9f0,0x21ca,0x1f5,0x1dd6,0xbc3,0x71f,0x133e,0x13bb,0x2afe,0xc35,0x4bb,0x2d31,0x10a7,0x2a04,0x180e,0x2613,0x330,0xe76,0x19fd,0xfe9,0x935,0x79,0x1b01,0x73c,0x2ac6,0x21ce,0x1911,0x761,0x1084,0x1983,0xc3,0x15eb,0xe0a,0xdd,0x1cb1,0xb21,0x2a51,0x217f,0xb1,0x1328,0x9ca,0x1d96,0x1a0b,0xe1b,0x1c4b,0x3b,0x4d6,0x2344,0x199e,0x28af,0x1624,0x4ae,0x8b2,0x2991,0x1fb7,0x41,0x2780,0x1d8b,0xa7f,0x110,0x2350,0x18aa,0x2b2f,0x1805,0x1ff,0xf0,0x2a74,0xe42,0xd97,0x85b,0x14bc,0x2901,0xfd8,0x1ab3,0x1cef,0xfbd,0x2b07,0x174f,0x69b,0x10c3,0x1491,0xde3,0x28ca,0x252e,0x1849,0x1ec2,0x1f1b,0x2853,0x12ab,0x2674,0x238c,0x350,0x2ca,0xa7,0x4bd,0xcc3,0x90c,0x892,0x276,0x1e55,0x196d,0x1194,0x1bef,0x66a,0x1da1,0x260f,0x1c15,0x49f,0x120b,0x2671,0x1237,0x2e0d,0x2791,0x17d8,0x1e0a,0x2a99,0x14cf,0xfb1,0x15b4,0x1462,0x2fbb,0xeff,0x16b,0x2d6a,0x9ef,0x5e3,0x11c0,0x2e76,0x1623,0x2db8,0x1c88,0x740,0x11e1,0x12a3,0x977,0x1110,0x2163,0x2dee,0x47b,0x2aa5,0x2a22,0x1231,0x16e7,0x1626,0x12e0,0x1d28,0xe96,0xb62,0x21d0,0xf09,0xb30,0xcb8,0x2981,0x2648,0x155d,0x27ee,0xb34,0x169,0x1574,0x1fe6,0x25f4,0x151d,0x1801,0x1f13,0x1308,0x2929,0x6eb,0x25e,0x2cca,0x1e3e,0x248f};

func round(a int32,b int32) int32 {
	return (a+b/2)/b
}

/* constant time absolute vaue */
func nabs(x int32 ) int32 {
	mask:=(x>>31)
	return (x+mask)^mask
}

/* Montgomery stuff */

func redc(T uint64) int32 {
	m:=(uint32(T)*NHS_ND)
	return int32((uint64(m)*uint64(NHS_PRIME)+T)>>NHS_WL)
}

func nres(x int32) int32 {
	return redc(uint64(x)*NHS_R2MODP)
}

func modmul(a int32,b int32) int32 {
	return redc(uint64(a)*uint64(b))
}

/* NTT code */
/* Cooley-Tukey NTT */

func ntt(x []int32) {
	t:=NHS_DEGREE/2
	q:=NHS_PRIME

/* Convert to Montgomery form */
	for j:=0;j<NHS_DEGREE;j++ {x[j]=nres(x[j])}
	m:=1
	for m<NHS_DEGREE {
		k:=0
		for i:=0;i<m;i++ {
			S:=NHS_roots[m+i]
			for j:=k;j<k+t;j++ {
				U:=x[j]
				V:=modmul(x[j+t],S)
				x[j]=U+V
				x[j+t]=U+2*q-V
			}
			k+=2*t
		}
		t/=2
		m*=2
	}
}

/* Gentleman-Sande INTT */

func intt(x []int32) {
	t:=1;
	q:=NHS_PRIME

	m:=NHS_DEGREE/2;
	for m>1 {
		k:=0;
		for i:=0;i<m;i++ {
			S:=NHS_iroots[m+i]
			for j:=k;j<k+t;j++ {	
				U:=x[j] 
				V:=x[j+t]
				x[j]=U+V	
				W:=U+int32(NHS_DEGREE)*q-V
				x[j+t]=modmul(W,S) 
			}
			k+=2*t
		}
		t*=2
		m/=2
	}

/* Last iteration merged with n^-1 */

	t=NHS_DEGREE/2
	for j:=0;j<t;j++ {
		U:=x[j]
		V:=x[j+t]
		W:=U+int32(NHS_DEGREE)*q-V
		x[j+t]=modmul(W,NHS_invpr)
		x[j]=modmul(U+V,NHS_inv)
	}
/* convert back from Montgomery to "normal" form */
	for j:=0;j<NHS_DEGREE;j++ {
		x[j]=redc(uint64(x[j]))
		x[j]-=q
		x[j]+=(x[j]>>(NHS_WL-1))&q
	} 
}

/* See https://eprint.iacr.org/2016/1157.pdf */ 

func encode(key []byte,poly []int32) {

	q2:=NHS_PRIME/2
	j:=0
	for i:=0;i<256;  {
		kj:=key[j]
		j++
		for k:=0;k<8;k++ {
			b:=int32(kj&1)
			poly[i]=b*q2
			poly[i+256]=b*q2
			poly[i+512]=b*q2
			poly[i+768]=b*q2
			kj>>=1
			i++
		}
	}		
}

func decode(poly []int32,key []byte) {
	q2:=NHS_PRIME/2
	for i:=0;i<32;i++ {
		key[i]=0
	}

	j:=0
	for i:=0;i<256; {
		for k:=0;k<8;k++ {
			t:=nabs(poly[i]-q2)+nabs(poly[i+256]-q2)+nabs(poly[i+512]-q2)+nabs(poly[i+768]-q2)
			b:=t-NHS_PRIME
			b=(b>>31)&1
			key[j]=(key[j]>>1)+byte(b<<7)
			i++
		}
		j++
	}
}

/* convert 32-byte seed to random polynomial */

func parse(seed []byte,poly []int32) {
	var hash [4*NHS_DEGREE] byte
	sh:=NewSHA3(SHA3_SHAKE128)

	for i:=0;i<32;i++ {
		sh.Process(seed[i])
	}
	sh.Shake(hash[:],4*NHS_DEGREE)

	j:=0
	for i:=0;i<NHS_DEGREE;i++ {
		n:=int32(hash[j]&0x7f); n<<=8
		n+=int32(hash[j+1]); n<<=8
		n+=int32(hash[j+2]); n<<=8
		n+=int32(hash[j+3]); j+=4
		poly[i]=nres(n)
		//poly[i]=modmul(n,NHS_ONE) // reduce 31-bit random number mod q
	}
} 

/* Compress 14 bits polynomial coefficients into byte array */
/* 7 bytes is 3x14 */

func nhs_pack(poly []int32,array []byte) {
	j:=0
	for i:=0;i<NHS_DEGREE;  {
		a:=poly[i]; b:=poly[i+1]; c:=poly[i+2]; d:=poly[i+3]; i+=4
		array[j]=byte(a&0xff)
		array[j+1]=byte(((a>>8)|(b<<6))&0xff)
		array[j+2]=byte((b>>2)&0xff)
		array[j+3]=byte(((b>>10)|(c<<4))&0xff)
		array[j+4]=byte((c>>4)&0xff)
		array[j+5]=byte(((c>>12)|(d<<2))&0xff)
		array[j+6]=byte(d>>6)
		j+=7
	}
}

func nhs_unpack(array []byte,poly []int32) {
	j:=0
	for i:=0;i<NHS_DEGREE; {
		a:=int32((array[j])&0xff); b:=int32((array[j+1])&0xff); c:=int32((array[j+2])&0xff); d:=int32((array[j+3])&0xff); e:=int32((array[j+4])&0xff); f:=int32((array[j+5])&0xff); g:=int32((array[j+6])&0xff); j+=7
		poly[i]=a|((b&0x3f)<<8)
		poly[i+1]=(b>>6)|(c<<2)|((d&0xf)<<10)
		poly[i+2]=(d>>4)|(e<<4)|((f&3)<<12)
		poly[i+3]=(f>>2)|(g<<6)
		i+=4
	}
}

/* See https://eprint.iacr.org/2016/1157.pdf */ 

func compress(poly []int32,array []byte) {
	
	var col int32=0
	j:=0
	for i:=0;i<NHS_DEGREE;  {
		for k:=0;k<8;k++  {
			b:=round((poly[i]*8),NHS_PRIME)&7 
			col=(col<<3)+b
			i+=1
		}
		array[j]=byte(col&0xff)
		array[j+1]=byte((col>>8)&0xff)
		array[j+2]=byte((col>>16)&0xff)
		j+=3; col=0
	}
}

func decompress(array []byte,poly []int32) {
	var col int32=0
	j:=0
	for i:=0;i<NHS_DEGREE;  {
		col=int32(array[j+2])&0xff
		col=(col<<8)+(int32(array[j+1])&0xff)
		col=(col<<8)+(int32(array[j])&0xff)
		j+=3
		for k:=0;k<8;k++ {
			b:=(col&0xe00000)>>21; col<<=3
			poly[i]=round((b*NHS_PRIME),8)
			i+=1
		}
	}
}

/* generate centered binomial distribution */ 

func error(rng *RAND,poly []int32) {
	var r int32
	for i:=0;i<NHS_DEGREE;i++ {
		n1:=(int32(rng.GetByte())&0xff)+((int32(rng.GetByte())&0xff)<<8)
		n2:=(int32(rng.GetByte())&0xff)+((int32(rng.GetByte())&0xff)<<8)
		r=0
		for j:=0;j<16;j++ {
			r+=(n1&1)-(n2&1)
			n1>>=1; n2>>=1
		}
		poly[i]=(r+NHS_PRIME)
	}
}

func redc_it(p []int32) {
	for i:=0;i<NHS_DEGREE;i++ {
		p[i]=redc(uint64(p[i]))
	}	
}

func nres_it(p []int32) {
	for i:=0;i<NHS_DEGREE;i++ {
		p[i]=nres(p[i])
	}	
}

func poly_mul(p1 []int32,p2 [] int32,p3 []int32) {
	for i:=0;i<NHS_DEGREE;i++ {
		p1[i]=modmul(p2[i],p3[i])
	}
}

func poly_add(p1 []int32,p2 []int32,p3 []int32) {
	for i:=0;i<NHS_DEGREE;i++ {
		p1[i]=(p2[i]+p3[i])
	}
}

func poly_sub(p1 []int32,p2 []int32,p3 []int32) {
	for i:=0;i<NHS_DEGREE;i++ {
		p1[i]=(p2[i]+NHS_PRIME-p3[i])
	}
}

/* reduces inputs < 2q */
func poly_soft_reduce(poly []int32) {
	for i:=0;i<NHS_DEGREE;i++ {
		e:=poly[i]-NHS_PRIME
		poly[i]=e+((e>>(NHS_WL-1))&NHS_PRIME)
	}
}

/* fully reduces modulo q */
func poly_hard_reduce(poly []int32) {
	for i:=0;i<NHS_DEGREE;i++ {
		e:=modmul(poly[i],NHS_ONE)
		e=e-NHS_PRIME
		poly[i]=e+((e>>(NHS_WL-1))&NHS_PRIME)
	}
}

/* API files */

func NHS_SERVER_1(rng *RAND,SB []byte,S []byte) {
	var seed [32] byte
	var array [1792] byte
	var s [NHS_DEGREE] int32
	var e [NHS_DEGREE] int32
	var b [NHS_DEGREE] int32

	for i:=0;i<32;i++ {
		seed[i]=rng.GetByte()
	}

	parse(seed[:],b[:])
	
	error(rng,e[:])
	error(rng,s[:])

	ntt(s[:])
	ntt(e[:])
	poly_mul(b[:],b[:],s[:])
	poly_add(b[:],b[:],e[:])
	poly_hard_reduce(b[:])

	redc_it(b[:])
	nhs_pack(b[:],array[:])

	for i:=0;i<32;i++ {
		SB[i]=seed[i]
	}

	for i:=0;i<1792;i++ {
		SB[i+32]=array[i]
	}

	poly_hard_reduce(s[:])
	nhs_pack(s[:],array[:])

	for i:=0;i<1792;i++ {
		S[i]=array[i]
	}

}

func NHS_CLIENT(rng *RAND,SB []byte,UC []byte,KEY []byte) {
	sh:=NewSHA3(SHA3_HASH256)
	var seed [32] byte
	var array [1792] byte
	var key [32] byte
	var cc [384] byte

	var sd [NHS_DEGREE] int32
	var ed [NHS_DEGREE] int32
	var u [NHS_DEGREE] int32
	var k [NHS_DEGREE] int32
	var c [NHS_DEGREE] int32

	error(rng,sd[:])
	error(rng,ed[:])

	ntt(sd[:])
	ntt(ed[:])

	for i:=0;i<32;i++ {
		seed[i]=SB[i]
	}

	for i:=0;i<1792;i++ {
		array[i]=SB[i+32]
	}

	parse(seed[:],u[:])

	poly_mul(u[:],u[:],sd[:])
	poly_add(u[:],u[:],ed[:])
	poly_hard_reduce(u[:])

	for i:=0;i<32;i++ {
		key[i]=rng.GetByte()
	}

	for i:=0;i<32;i++ {
		sh.Process(key[i])
	}
	sh.Hash(key[:])

	encode(key[:],k[:])

	nhs_unpack(array[:],c[:])
	nres_it(c[:])

	poly_mul(c[:],c[:],sd[:])
	intt(c[:])
	error(rng,ed[:])
	poly_add(c[:],c[:],ed[:])
	poly_add(c[:],c[:],k[:])

	compress(c[:],cc[:])

	sh.Init(SHA3_HASH256)
	for i:=0;i<32;i++ {
		sh.Process(key[i])
	}
	sh.Hash(key[:])

	for i:=0;i<32;i++ {
		KEY[i]=key[i]
	}

	redc_it(u[:])
	nhs_pack(u[:],array[:])

	for i:=0;i<1792;i++ {
		UC[i]=array[i]
	}

	for i:=0;i<384;i++ {
		UC[i+1792]=cc[i]
	}
}

func NHS_SERVER_2(S []byte,UC []byte,KEY []byte) {
	sh:=NewSHA3(SHA3_HASH256)

	var c [NHS_DEGREE] int32
	var s [NHS_DEGREE] int32
	var k [NHS_DEGREE] int32

	var array [1792] byte
	var key [32] byte
	var cc [384] byte

	for i:=0;i<1792;i++ {
		array[i]=UC[i]
	}

	nhs_unpack(array[:],k[:])
	nres_it(k[:])

	for i:=0;i<384;i++ {
		cc[i]=UC[i+1792]
	}

	decompress(cc[:],c[:])

	for i:=0;i<1792;i++ {
		array[i]=S[i]
	}

	nhs_unpack(array[:],s[:])

	poly_mul(k[:],k[:],s[:])
	intt(k[:])
	poly_sub(k[:],c[:],k[:])
	poly_soft_reduce(k[:])

	decode(k[:],key[:])

	for i:=0;i<32;i++ {
		sh.Process(key[i])
	}
	sh.Hash(key[:])

	for i:=0;i<32;i++ {
		KEY[i]=key[i]
	}
}

/*
func main() {

	srng:=NewRAND()
	var sraw [100]byte
	for i:=0;i<100;i++ {sraw[i]=byte(i+1)}
	srng.Seed(100,sraw[:])

							crng:=NewRAND()
							var craw [100]byte
							for i:=0;i<100;i++ {craw[i]=byte(i+2)}
							crng.Seed(100,craw[:])

	var S [1792] byte

				var SB [1824] byte	
	NHS_SERVER_1(srng,SB[:],S[:])
				var UC [2176] byte
							var KEYB [32] byte
							NHS_CLIENT(crng,SB[:],UC[:],KEYB[:])
				
							fmt.Printf("Bob's Key= ")
							for i:=0;i<32;i++ {
								fmt.Printf("%02x", KEYB[i])
							}
							fmt.Printf("\n")
	var KEYA [32] byte
	NHS_SERVER_2(S[:],UC[:],KEYA[:])

	fmt.Printf("Alice Key= ")
	for i:=0;i<32;i++ {
		fmt.Printf("%02x", KEYA[i])
	}
	
} 
*/