http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/amcl.h ---------------------------------------------------------------------- diff --git a/version3/cpp/amcl.h b/version3/cpp/amcl.h new file mode 100644 index 0000000..b9cfea2 --- /dev/null +++ b/version3/cpp/amcl.h @@ -0,0 +1,585 @@ +/* + 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. +*/ + + +#ifndef AMCL_H +#define AMCL_H + +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> +#include <inttypes.h> +#include "arch.h" + +namespace amcl { + +/* modulus types */ + +#define NOT_SPECIAL 0 /**< Modulus of no exploitable form */ +#define PSEUDO_MERSENNE 1 /**< Pseudo-mersenne modulus of form $2^n-c$ */ +#define MONTGOMERY_FRIENDLY 3 /**< Montgomery Friendly modulus of form $2^a(2^b-c)-1$ */ +#define GENERALISED_MERSENNE 2 /**< Generalised-mersenne modulus of form $2^n-2^m-1$, GOLDILOCKS only */ + + +/* Curve types */ + +#define WEIERSTRASS 0 /**< Short Weierstrass form curve */ +#define EDWARDS 1 /**< Edwards or Twisted Edwards curve */ +#define MONTGOMERY 2 /**< Montgomery form curve */ + +/* Pairing-Friendly types */ + +#define NOT 0 +#define BN 1 +#define BLS 2 + +#define D_TYPE 0 +#define M_TYPE 1 + +/** + * @brief SHA256 hash function instance */ +typedef struct +{ + unsign32 length[2]; /**< 64-bit input length */ + unsign32 h[8]; /**< Internal state */ + unsign32 w[80]; /**< Internal state */ + int hlen; /**< Hash length in bytes */ +} hash256; + +/** + * @brief SHA384-512 hash function instance */ +typedef struct +{ + unsign64 length[2]; /**< 64-bit input length */ + unsign64 h[8]; /**< Internal state */ + unsign64 w[80]; /**< Internal state */ + int hlen; /**< Hash length in bytes */ +} hash512; + +/** + * @brief SHA384 hash function instance */ +typedef hash512 hash384; + +/** + * @brief SHA3 hash function instance */ +typedef struct { + unsign64 length; + unsign64 S[5][5]; + int rate,len; +} sha3; + +#define SHA256 32 /**< SHA-256 hashing */ +#define SHA384 48 /**< SHA-384 hashing */ +#define SHA512 64 /**< SHA-512 hashing */ + +#define SHA3_HASH224 28 /**< SHA3 224 bit hash */ +#define SHA3_HASH256 32 /**< SHA3 256 bit hash */ +#define SHA3_HASH384 48 /**< SHA3 384 bit hash */ +#define SHA3_HASH512 64 /**< SHA3 512 bit hash */ + +#define SHAKE128 16 /**< SHAKE128 hash */ +#define SHAKE256 32 /**< SHAKE256 hash */ + + +/* NewHope parameters */ + +//q= 12289 + +#define RLWE_PRIME 0x3001 // q in Hex +#define RLWE_LGN 10 // Degree n=2^LGN +#define RLWE_ND 0xF7002FFF // 1/(R-q) mod R +#define RLWE_ONE 0x2AC8 // R mod q +#define RLWE_R2MODP 0x1620 // R^2 mod q + +/* Symmetric Encryption AES structure */ + +#define ECB 0 /**< Electronic Code Book */ +#define CBC 1 /**< Cipher Block Chaining */ +#define CFB1 2 /**< Cipher Feedback - 1 byte */ +#define CFB2 3 /**< Cipher Feedback - 2 bytes */ +#define CFB4 5 /**< Cipher Feedback - 4 bytes */ +#define OFB1 14 /**< Output Feedback - 1 byte */ +#define OFB2 15 /**< Output Feedback - 2 bytes */ +#define OFB4 17 /**< Output Feedback - 4 bytes */ +#define OFB8 21 /**< Output Feedback - 8 bytes */ +#define OFB16 29 /**< Output Feedback - 16 bytes */ +#define CTR1 30 /**< Counter Mode - 1 byte */ +#define CTR2 31 /**< Counter Mode - 2 bytes */ +#define CTR4 33 /**< Counter Mode - 4 bytes */ +#define CTR8 37 /**< Counter Mode - 8 bytes */ +#define CTR16 45 /**< Counter Mode - 16 bytes */ + +#define uchar unsigned char /**< Unsigned char */ + +/** + @brief AES instance +*/ + + +typedef struct +{ + int Nk; /**< AES Key Length */ + int Nr; /**< AES Number of rounds */ + int mode; /**< AES mode of operation */ + unsign32 fkey[60]; /**< subkeys for encrypton */ + unsign32 rkey[60]; /**< subkeys for decrypton */ + char f[16]; /**< buffer for chaining vector */ +} aes; + +/* AES-GCM suppport. */ + +#define GCM_ACCEPTING_HEADER 0 /**< GCM status */ +#define GCM_ACCEPTING_CIPHER 1 /**< GCM status */ +#define GCM_NOT_ACCEPTING_MORE 2 /**< GCM status */ +#define GCM_FINISHED 3 /**< GCM status */ +#define GCM_ENCRYPTING 0 /**< GCM mode */ +#define GCM_DECRYPTING 1 /**< GCM mode */ + + +/** + @brief GCM mode instance, using AES internally +*/ + +typedef struct +{ + unsign32 table[128][4]; /**< 2k byte table */ + uchar stateX[16]; /**< GCM Internal State */ + uchar Y_0[16]; /**< GCM Internal State */ + unsign32 lenA[2]; /**< GCM 64-bit length of header */ + unsign32 lenC[2]; /**< GCM 64-bit length of ciphertext */ + int status; /**< GCM Status */ + aes a; /**< Internal Instance of aes cipher */ +} gcm; + +/* Marsaglia & Zaman Random number generator constants */ + +#define NK 21 /**< PRNG constant */ +#define NJ 6 /**< PRNG constant */ +#define NV 8 /**< PRNG constant */ + + +/** + @brief Cryptographically secure pseudo-random number generator instance +*/ + +typedef struct +{ + unsign32 ira[NK]; /**< random number array */ + int rndptr; /**< pointer into array */ + unsign32 borrow; /**< borrow as a result of subtraction */ + int pool_ptr; /**< pointer into random pool */ + char pool[32]; /**< random pool */ +} csprng; + + +/** + @brief Portable representation of a big positive number +*/ + +typedef struct +{ + int len; /**< length in bytes */ + int max; /**< max length allowed - enforce truncation */ + char *val; /**< byte array */ +} octet; + + +/* Octet string handlers */ +/** @brief Formats and outputs an octet to the console in hex + * + @param O Octet to be output + */ +extern void OCT_output(octet *O); +/** @brief Formats and outputs an octet to the console as a character string + * + @param O Octet to be output + */ +extern void OCT_output_string(octet *O); +/** @brief Wipe clean an octet + * + @param O Octet to be cleaned + */ +extern void OCT_clear(octet *O); +/** @brief Compare two octets + * + @param O first Octet to be compared + @param P second Octet to be compared + @return 1 if equal, else 0 + */ +extern int OCT_comp(octet *O,octet *P); + + +/** @brief Compare first n bytes of two octets + * + @param O first Octet to be compared + @param P second Octet to be compared + @param n number of bytes to compare + @return 1 if equal, else 0 + */ +extern int OCT_ncomp(octet *O,octet *P,int n); +/** @brief Join from a C string to end of an octet + * + Truncates if there is no room + @param O Octet to be written to + @param s zero terminated string to be joined to octet + */ +extern void OCT_jstring(octet *O,char *s); +/** @brief Join bytes to end of an octet + * + Truncates if there is no room + @param O Octet to be written to + @param s bytes to be joined to end of octet + @param n number of bytes to join + */ +extern void OCT_jbytes(octet *O,char *s,int n); +/** @brief Join single byte to end of an octet, repeated n times + * + Truncates if there is no room + @param O Octet to be written to + @param b byte to be joined to end of octet + @param n number of times b is to be joined + */ +extern void OCT_jbyte(octet *O,int b,int n); +/** @brief Join one octet to the end of another + * + Truncates if there is no room + @param O Octet to be written to + @param P Octet to be joined to the end of O + */ +extern void OCT_joctet(octet *O,octet *P); +/** @brief XOR common bytes of a pair of Octets + * + @param O Octet - on exit = O xor P + @param P Octet to be xored into O + */ +extern void OCT_xor(octet *O,octet *P); +/** @brief reset Octet to zero length + * + @param O Octet to be emptied + */ +extern void OCT_empty(octet *O); +/** @brief Pad out an Octet to the given length + * + Padding is done by inserting leading zeros, so abcd becomes 00abcd + @param O Octet to be padded + @param n new length of Octet + */ +extern int OCT_pad(octet *O,int n); +/** @brief Convert an Octet to printable base64 number + * + @param b zero terminated byte array to take base64 conversion + @param O Octet to be converted + */ +extern void OCT_tobase64(char *b,octet *O); +/** @brief Populate an Octet from base64 number + * + @param O Octet to be populated + @param b zero terminated base64 string + + */ +extern void OCT_frombase64(octet *O,char *b); +/** @brief Copy one Octet into another + * + @param O Octet to be copied to + @param P Octet to be copied from + + */ +extern void OCT_copy(octet *O,octet *P); +/** @brief XOR every byte of an octet with input m + * + @param O Octet + @param m byte to be XORed with every byte of O + + */ +extern void OCT_xorbyte(octet *O,int m); +/** @brief Chops Octet into two, leaving first n bytes in O, moving the rest to P + * + @param O Octet to be chopped + @param P new Octet to be created + @param n number of bytes to chop off O + + */ +extern void OCT_chop(octet *O,octet *P,int n); +/** @brief Join n bytes of integer m to end of Octet O (big endian) + * + Typically n is 4 for a 32-bit integer + @param O Octet to be appended to + @param m integer to be appended to O + @param n number of bytes in m + + */ +extern void OCT_jint(octet *O,int m,int n); +/** @brief Create an Octet from bytes taken from a random number generator + * + Truncates if there is no room + @param O Octet to be populated + @param R an instance of a Cryptographically Secure Random Number Generator + @param n number of bytes to extracted from R + + */ +extern void OCT_rand(octet *O,csprng *R,int n); +/** @brief Shifts Octet left by n bytes + * + Leftmost bytes disappear + @param O Octet to be shifted + @param n number of bytes to shift + + */ +extern void OCT_shl(octet *O,int n); +/** @brief Convert a hex number to an Octet + * + @param dst Octet + @param src Hex string to be converted + */ +extern void OCT_fromHex(octet *dst,char *src); +/** @brief Convert an Octet to printable hex number + * + @param dst hex value + @param src Octet to be converted + */ +extern void OCT_toHex(octet *src,char *dst); +/** @brief Convert an Octet to string + * + @param dst string value + @param src Octet to be converted + */ +extern void OCT_toStr(octet *src,char *dst); + + + +/* Hash function */ +/** @brief Initialise an instance of SHA256 + * + @param H an instance SHA256 + */ +extern void HASH256_init(hash256 *H); +/** @brief Add a byte to the hash + * + @param H an instance SHA256 + @param b byte to be included in hash + */ +extern void HASH256_process(hash256 *H,int b); +/** @brief Generate 32-byte hash + * + @param H an instance SHA256 + @param h is the output 32-byte hash + */ +extern void HASH256_hash(hash256 *H,char *h); + + +/** @brief Initialise an instance of SHA384 + * + @param H an instance SHA384 + */ +extern void HASH384_init(hash384 *H); +/** @brief Add a byte to the hash + * + @param H an instance SHA384 + @param b byte to be included in hash + */ +extern void HASH384_process(hash384 *H,int b); +/** @brief Generate 48-byte hash + * + @param H an instance SHA384 + @param h is the output 48-byte hash + */ +extern void HASH384_hash(hash384 *H,char *h); + + +/** @brief Initialise an instance of SHA512 + * + @param H an instance SHA512 + */ +extern void HASH512_init(hash512 *H); +/** @brief Add a byte to the hash + * + @param H an instance SHA512 + @param b byte to be included in hash + */ +extern void HASH512_process(hash512 *H,int b); +/** @brief Generate 64-byte hash + * + @param H an instance SHA512 + @param h is the output 64-byte hash + */ +extern void HASH512_hash(hash512 *H,char *h); + + +/** @brief Initialise an instance of SHA3 + * + @param H an instance SHA3 + @param t the instance type + */ +extern void SHA3_init(sha3 *H,int t); +/** @brief process a byte for SHA3 + * + @param H an instance SHA3 + @param b a byte of date to be processed + */ +extern void SHA3_process(sha3 *H,int b); +/** @brief create fixed length hash output of SHA3 + * + @param H an instance SHA3 + @param h a byte array to take hash + */ +extern void SHA3_hash(sha3 *H,char *h); +/** @brief create variable length hash output of SHA3 + * + @param H an instance SHA3 + @param h a byte array to take hash + @param len is the length of the hash + */ +extern void SHA3_shake(sha3 *H,char *h,int len); +/** @brief generate further hash output of SHA3 + * + @param H an instance SHA3 + @param h a byte array to take hash + @param len is the length of the hash + */ +extern void SHA3_squeeze(sha3 *H,char *h,int len); + + + +/* AES functions */ +/** @brief Reset AES mode or IV + * + @param A an instance of the aes + @param m is the new active mode of operation (ECB, CBC, OFB, CFB etc) + @param iv the new Initialisation Vector + */ +extern void AES_reset(aes *A,int m,char *iv); +/** @brief Extract chaining vector from aes instance + * + @param A an instance of the aes + @param f the extracted chaining vector + */ +extern void AES_getreg(aes *A,char * f); +/** @brief Initialise an instance of aes and its mode of operation + * + @param A an instance aes + @param m is the active mode of operation (ECB, CBC, OFB, CFB etc) + @param n is the key length in bytes, 16, 24 or 32 + @param k the AES key as an array of 16 bytes + @param iv the Initialisation Vector + @return 0 for invalid n + */ +extern int AES_init(aes *A,int m,int n,char *k,char *iv); +/** @brief Encrypt a single 16 byte block in ECB mode + * + @param A an instance of the aes + @param b is an array of 16 plaintext bytes, on exit becomes ciphertext + */ +extern void AES_ecb_encrypt(aes *A,uchar * b); +/** @brief Decrypt a single 16 byte block in ECB mode + * + @param A an instance of the aes + @param b is an array of 16 cipherext bytes, on exit becomes plaintext + */ +extern void AES_ecb_decrypt(aes *A,uchar * b); +/** @brief Encrypt a single 16 byte block in active mode + * + @param A an instance of the aes + @param b is an array of 16 plaintext bytes, on exit becomes ciphertext + @return 0, or overflow bytes from CFB mode + */ +extern unsign32 AES_encrypt(aes *A,char *b ); +/** @brief Decrypt a single 16 byte block in active mode + * + @param A an instance of the aes + @param b is an array of 16 ciphertext bytes, on exit becomes plaintext + @return 0, or overflow bytes from CFB mode + */ +extern unsign32 AES_decrypt(aes *A,char *b); +/** @brief Clean up after application of AES + * + @param A an instance of the aes + */ +extern void AES_end(aes *A); + + +/* AES-GCM functions */ +/** @brief Initialise an instance of AES-GCM mode + * + @param G an instance AES-GCM + @param nk is the key length in bytes, 16, 24 or 32 + @param k the AES key as an array of 16 bytes + @param n the number of bytes in the Initialisation Vector (IV) + @param iv the IV + */ +extern void GCM_init(gcm *G,int nk,char *k,int n,char *iv); +/** @brief Add header (material to be authenticated but not encrypted) + * + Note that this function can be called any number of times with n a multiple of 16, and then one last time with any value for n + @param G an instance AES-GCM + @param b is the header material to be added + @param n the number of bytes in the header + */ +extern int GCM_add_header(gcm *G,char *b,int n); +/** @brief Add plaintext and extract ciphertext + * + Note that this function can be called any number of times with n a multiple of 16, and then one last time with any value for n + @param G an instance AES-GCM + @param c is the ciphertext generated + @param p is the plaintext material to be added + @param n the number of bytes in the plaintext + */ +extern int GCM_add_plain(gcm *G,char *c,char *p,int n); +/** @brief Add ciphertext and extract plaintext + * + Note that this function can be called any number of times with n a multiple of 16, and then one last time with any value for n + @param G an instance AES-GCM + @param p is the plaintext generated + @param c is the ciphertext material to be added + @param n the number of bytes in the ciphertext + */ +extern int GCM_add_cipher(gcm *G,char *p,char *c,int n); +/** @brief Finish off and extract authentication tag (HMAC) + * + @param G is an active instance AES-GCM + @param t is the output 16 byte authentication tag + */ +extern void GCM_finish(gcm *G,char *t); + + + +/* random numbers */ +/** @brief Seed a random number generator from an array of bytes + * + The provided seed should be truly random + @param R an instance of a Cryptographically Secure Random Number Generator + @param n the number of seed bytes provided + @param b an array of seed bytes + + */ +extern void RAND_seed(csprng *R,int n,char *b); +/** @brief Delete all internal state of a random number generator + * + @param R an instance of a Cryptographically Secure Random Number Generator + */ +extern void RAND_clean(csprng *R); +/** @brief Return a random byte from a random number generator + * + @param R an instance of a Cryptographically Secure Random Number Generator + @return a random byte + */ +extern int RAND_byte(csprng *R); + +} + +#endif
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/arch.h ---------------------------------------------------------------------- diff --git a/version3/cpp/arch.h b/version3/cpp/arch.h new file mode 100644 index 0000000..d21d0cd --- /dev/null +++ b/version3/cpp/arch.h @@ -0,0 +1,98 @@ +/* + 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. +*/ + +/* Architecture definition header file */ + +/** + * @file arch.h + * @author Mike Scott + * @date 23rd February 2016 + * @brief Architecture Header File + * + * Specify Processor Architecture + * + */ + +/* NOTE: There is only one user configurable section in this header - see below */ + +#ifndef ARCH_H +#define ARCH_H +#include <stdint.h> + +namespace amcl { + +/*** START OF USER CONFIGURABLE SECTION - set architecture ***/ + +#define CHUNK @WL@ /**< size of chunk in bits = wordlength of computer = 16, 32 or 64. Note not all curve options are supported on 16-bit processors - see rom.c */ + +/*** END OF USER CONFIGURABLE SECTION ***/ + +/* Create Integer types */ +/* Support for C99? Note for GCC need to explicitly include -std=c99 in command line */ + + +#define byte uint8_t /**< 8-bit unsigned integer */ +#define sign8 int8_t /**< 8-bit signed integer */ +#define sign16 int16_t /**< 16-bit signed integer */ +#define sign32 int32_t /**< 32-bit signed integer */ +#define sign64 int64_t /**< 64-bit signed integer */ +#define unsign32 uint32_t /**< 32-bit unsigned integer */ +#define unsign64 uint64_t /**< 64-bit unsigned integer */ + +#define uchar unsigned char /**< Unsigned char */ + +/* Don't mess with anything below this line unless you know what you are doing */ +/* This next is probably OK, but may need changing for non-C99-standard environments */ + +/* This next is probably OK, but may need changing for non-C99-standard environments */ + +#if CHUNK==16 + +#define chunk int16_t /**< C type corresponding to word length */ +#define dchunk int32_t /**< Always define double length chunk type if available */ + +#endif + +#if CHUNK == 32 + +#define chunk int32_t /**< C type corresponding to word length */ +#define dchunk int64_t /**< Always define double length chunk type if available */ + +#endif + +#if CHUNK == 64 + + #define chunk int64_t /**< C type corresponding to word length */ + #ifdef __GNUC__ + #define dchunk __int128 /**< Always define double length chunk type if available - GCC supports 128 bit type ??? */ + #endif + + #ifdef __clang__ + #define dchunk __int128 + #endif + +#endif + +#ifdef dchunk +#define COMBA /**< Use COMBA method for faster muls, sqrs and reductions */ +#endif + +} + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/benchtest_all.cpp ---------------------------------------------------------------------- diff --git a/version3/cpp/benchtest_all.cpp b/version3/cpp/benchtest_all.cpp new file mode 100644 index 0000000..9589f98 --- /dev/null +++ b/version3/cpp/benchtest_all.cpp @@ -0,0 +1,1024 @@ +/* Test and benchmark elliptic curve and RSA functions + First build amcl.a from build_ec batch file + gcc -O3 benchtest_ec.c amcl.a -o benchtest_ec.exe +*/ + +#include <stdio.h> +#include <stdlib.h> +#include <time.h> + +#include "rsa_RSA2048.h" +#include "ecp_ED25519.h" +#include "pair_BN254.h" + +#if CHUNK==32 || CHUNK==64 +#include "ecp_NIST256.h" +#include "ecp_GOLDILOCKS.h" +#include "pair_BLS383.h" +#include "pair192_BLS24.h" +#include "pair256_BLS48.h" +#endif + +#define MIN_TIME 10.0 +#define MIN_ITERS 10 + +using namespace amcl; + +int ED_25519(csprng *RNG) +{ + using namespace ED25519; + using namespace ED25519_BIG; + + int i,iterations; + clock_t start; + double elapsed; + ECP EP,EG; + BIG s,r,x,y; + printf("\nTesting/Timing ED25519 ECC\n"); + +#if CURVETYPE_ED25519==WEIERSTRASS + printf("Weierstrass parameterization\n"); +#endif +#if CURVETYPE_ED25519==EDWARDS + printf("Edwards parameterization\n"); +#endif +#if CURVETYPE_ED25519==MONTGOMERY + printf("Montgomery parameterization\n"); +#endif + + +#if MODTYPE_F25519 == PSEUDO_MERSENNE + printf("Pseudo-Mersenne Modulus\n"); +#endif + +#if MODTYPE_F25519 == GENERALISED_MERSENNE + printf("Generalised-Mersenne Modulus\n"); +#endif + +#if MODTYPE_F25519 == MONTGOMERY_FRIENDLY + printf("Montgomery Friendly Modulus\n"); +#endif + +#if MODTYPE_F25519 == NOT_SPECIAL + printf("Not special Modulus\n"); +#endif + + +#if CHUNK==16 + printf("16-bit Build\n"); +#endif +#if CHUNK==32 + printf("32-bit Build\n"); +#endif +#if CHUNK==64 + printf("64-bit Build\n"); +#endif + + ECP_generator(&EG); + + BIG_rcopy(r,CURVE_Order); + BIG_randomnum(s,r,RNG); + ECP_copy(&EP,&EG); + ECP_mul(&EP,r); + + if (!ECP_isinf(&EP)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_copy(&EP,&EG); + ECP_mul(&EP,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("EC mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + return 0; +} + +#if CHUNK==32 || CHUNK==64 +int NIST_256(csprng *RNG) +{ + using namespace NIST256; + using namespace NIST256_BIG; + + int i,iterations; + clock_t start; + double elapsed; + ECP EP,EG; + BIG s,r,x,y; + printf("\nTesting/Timing NIST256 ECC\n"); + +#if CURVETYPE_NIST256==WEIERSTRASS + printf("Weierstrass parameterization\n"); +#endif +#if CURVETYPE_NIST256==EDWARDS + printf("Edwards parameterization\n"); +#endif +#if CURVETYPE_NIST256==MONTGOMERY + printf("Montgomery parameterization\n"); +#endif + + +#if MODTYPE_NIST256 == PSEUDO_MERSENNE + printf("Pseudo-Mersenne Modulus\n"); +#endif + +#if MODTYPE_NIST256 == GENERALISED_MERSENNE + printf("Generalised-Mersenne Modulus\n"); +#endif + +#if MODTYPE_NIST256 == MONTGOMERY_FRIENDLY + printf("Montgomery Friendly Modulus\n"); +#endif + +#if MODTYPE_NIST256 == NOT_SPECIAL + printf("Not special Modulus\n"); +#endif + +#if CHUNK==16 + printf("16-bit Build\n"); +#endif +#if CHUNK==32 + printf("32-bit Build\n"); +#endif +#if CHUNK==64 + printf("64-bit Build\n"); +#endif + + ECP_generator(&EG); + + BIG_rcopy(r,CURVE_Order); + BIG_randomnum(s,r,RNG); + ECP_copy(&EP,&EG); + ECP_mul(&EP,r); + + if (!ECP_isinf(&EP)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_copy(&EP,&EG); + ECP_mul(&EP,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("EC mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + return 0; +} + +int GOLDI_LOCKS(csprng *RNG) +{ + using namespace GOLDILOCKS; + using namespace GOLDILOCKS_BIG; + + int i,iterations; + clock_t start; + double elapsed; + ECP EP,EG; + BIG s,r,x,y; + printf("\nTesting/Timing GOLDILOCKS ECC\n"); + +#if CURVETYPE_GOLDILOCKS==WEIERSTRASS + printf("Weierstrass parameterization\n"); +#endif +#if CURVETYPE_GOLDILOCKS==EDWARDS + printf("Edwards parameterization\n"); +#endif +#if CURVETYPE_GOLDILOCKS==MONTGOMERY + printf("Montgomery parameterization\n"); +#endif + +#if MODTYPE_GOLDILOCKS == PSEUDO_MERSENNE + printf("Pseudo-Mersenne Modulus\n"); +#endif + +#if MODTYPE_GOLDILOCKS == GENERALISED_MERSENNE + printf("Generalised-Mersenne Modulus\n"); +#endif + +#if MODTYPE_GOLDILOCKS == MONTGOMERY_FRIENDLY + printf("Montgomery Friendly Modulus\n"); +#endif + +#if MODTYPE_GOLDILOCKS == NOT_SPECIAL + printf("Not special Modulus\n"); +#endif + +#if CHUNK==16 + printf("16-bit Build\n"); +#endif +#if CHUNK==32 + printf("32-bit Build\n"); +#endif +#if CHUNK==64 + printf("64-bit Build\n"); +#endif + + ECP_generator(&EG); + + BIG_rcopy(r,CURVE_Order); + BIG_randomnum(s,r,RNG); + ECP_copy(&EP,&EG); + ECP_mul(&EP,r); + + if (!ECP_isinf(&EP)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_copy(&EP,&EG); + ECP_mul(&EP,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("EC mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + return 0; +} +#endif + +int BN_254(csprng *RNG) +{ + using namespace BN254; + using namespace BN254_FP; + using namespace BN254_BIG; + + int i,iterations; + clock_t start; + double elapsed; + + ECP P,G; + ECP2 Q,W; + FP12 g,w; + FP4 cm; + FP2 wx,wy; + + BIG s,r,x,y; + printf("\nTesting/Timing BN254 Pairings\n"); + + ECP_generator(&G); + + BIG_rcopy(r,CURVE_Order); + BIG_randomnum(s,r,RNG); + ECP_copy(&P,&G); + PAIR_G1mul(&P,r); + + if (!ECP_isinf(&P)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_copy(&P,&G); + PAIR_G1mul(&P,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("G1 mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + ECP2_generator(&W); + + ECP2_copy(&Q,&W); + ECP2_mul(&Q,r); + + if (!ECP2_isinf(&Q)) + { + printf("FAILURE - rQ!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP2_copy(&Q,&W); + PAIR_G2mul(&Q,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("G2 mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + PAIR_ate(&w,&Q,&P); + PAIR_fexp(&w); + + FP12_copy(&g,&w); + + PAIR_GTpow(&g,r); + + if (!FP12_isunity(&g)) + { + printf("FAILURE - g^r!=1\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + FP12_copy(&g,&w); + PAIR_GTpow(&g,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("GT pow - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + FP12_copy(&g,&w); + + iterations=0; + start=clock(); + do { + FP12_compow(&cm,&g,s,r); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("GT pow (compressed) - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + iterations=0; + start=clock(); + do { + PAIR_ate(&w,&Q,&P); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("PAIRing ATE - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + iterations=0; + start=clock(); + do { + FP12_copy(&g,&w); + PAIR_fexp(&g); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("PAIRing FEXP - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + ECP_copy(&P,&G); + ECP2_copy(&Q,&W); + + PAIR_G1mul(&P,s); + PAIR_ate(&g,&Q,&P); + PAIR_fexp(&g); + + ECP_copy(&P,&G); + + PAIR_G2mul(&Q,s); + PAIR_ate(&w,&Q,&P); + PAIR_fexp(&w); + + if (!FP12_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,sP) \n"); + return 0; + } + + ECP2_copy(&Q,&W); + PAIR_ate(&g,&Q,&P); + PAIR_fexp(&g); + + PAIR_GTpow(&g,s); + + if (!FP12_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,P)^s \n"); + return 0; + } + return 0; +} + +#if CHUNK==32 || CHUNK==64 +int BLS_383(csprng *RNG) +{ + using namespace BLS383; + using namespace BLS383_FP; + using namespace BLS383_BIG; + + int i,iterations; + clock_t start; + double elapsed; + + ECP P,G; + ECP2 Q,W; + FP12 g,w; + FP4 cm; + FP2 wx,wy; + + BIG s,r,x,y; + printf("\nTesting/Timing BLS383 Pairings\n"); + + ECP_generator(&G); + + BIG_rcopy(r,CURVE_Order); + BIG_randomnum(s,r,RNG); + ECP_copy(&P,&G); + PAIR_G1mul(&P,r); + + if (!ECP_isinf(&P)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_copy(&P,&G); + PAIR_G1mul(&P,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("G1 mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + ECP2_generator(&W); + + ECP2_copy(&Q,&W); + ECP2_mul(&Q,r); + + if (!ECP2_isinf(&Q)) + { + printf("FAILURE - rQ!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP2_copy(&Q,&W); + PAIR_G2mul(&Q,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("G2 mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + PAIR_ate(&w,&Q,&P); + PAIR_fexp(&w); + + FP12_copy(&g,&w); + + PAIR_GTpow(&g,r); + + if (!FP12_isunity(&g)) + { + printf("FAILURE - g^r!=1\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + FP12_copy(&g,&w); + PAIR_GTpow(&g,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("GT pow - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + FP12_copy(&g,&w); + + iterations=0; + start=clock(); + do { + FP12_compow(&cm,&g,s,r); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("GT pow (compressed) - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + iterations=0; + start=clock(); + do { + PAIR_ate(&w,&Q,&P); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("PAIRing ATE - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + iterations=0; + start=clock(); + do { + FP12_copy(&g,&w); + PAIR_fexp(&g); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("PAIRing FEXP - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + ECP_copy(&P,&G); + ECP2_copy(&Q,&W); + + PAIR_G1mul(&P,s); + PAIR_ate(&g,&Q,&P); + PAIR_fexp(&g); + + ECP_copy(&P,&G); + + PAIR_G2mul(&Q,s); + PAIR_ate(&w,&Q,&P); + PAIR_fexp(&w); + + if (!FP12_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,sP) \n"); + return 0; + } + + ECP2_copy(&Q,&W); + PAIR_ate(&g,&Q,&P); + PAIR_fexp(&g); + + PAIR_GTpow(&g,s); + + if (!FP12_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,P)^s \n"); + return 0; + } + return 0; +} + +int BLS_24(csprng *RNG) +{ + using namespace BLS24; + using namespace BLS24_FP; + using namespace BLS24_BIG; + + int i,iterations; + clock_t start; + double elapsed; + + ECP P,G; + ECP4 Q,W; + FP24 g,w; + + FP8 cm; + BIG a,b,s,r; + + printf("\nTesting/Timing BLS24 Pairings\n"); + + ECP_generator(&G); + + BIG_rcopy(r,CURVE_Order); + BIG_randomnum(s,r,RNG); + ECP_copy(&P,&G); + PAIR_G1mul(&P,r); + + if (!ECP_isinf(&P)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_copy(&P,&G); + PAIR_G1mul(&P,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("G1 mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + ECP4_generator(&W); + + ECP4_copy(&Q,&W); + ECP4_mul(&Q,r); + + if (!ECP4_isinf(&Q)) + { + printf("FAILURE - rQ!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP4_copy(&Q,&W); + PAIR_G2mul(&Q,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("G2 mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + PAIR_ate(&w,&Q,&P); + PAIR_fexp(&w); + + FP24_copy(&g,&w); + + PAIR_GTpow(&g,r); + + if (!FP24_isunity(&g)) + { + printf("FAILURE - g^r!=1\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + FP24_copy(&g,&w); + PAIR_GTpow(&g,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("GT pow - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + FP24_copy(&g,&w); + + iterations=0; + start=clock(); + do { + FP24_compow(&cm,&g,s,r); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("GT pow (compressed) - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + iterations=0; + start=clock(); + do { + PAIR_ate(&w,&Q,&P); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("PAIRing ATE - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + iterations=0; + start=clock(); + do { + FP24_copy(&g,&w); + PAIR_fexp(&g); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("PAIRing FEXP - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + ECP_copy(&P,&G); + ECP4_copy(&Q,&W); + + PAIR_G1mul(&P,s); + PAIR_ate(&g,&Q,&P); + PAIR_fexp(&g); + + ECP_copy(&P,&G); + + PAIR_G2mul(&Q,s); + PAIR_ate(&w,&Q,&P); + PAIR_fexp(&w); + + if (!FP24_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,sP) \n"); + return 0; + } + + ECP4_copy(&Q,&W); + PAIR_ate(&g,&Q,&P); + PAIR_fexp(&g); + + PAIR_GTpow(&g,s); + + if (!FP24_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,P)^s \n"); + return 0; + } + return 0; +} + + + +int BLS_48(csprng *RNG) +{ + using namespace BLS48; + using namespace BLS48_FP; + using namespace BLS48_BIG; + + int i,iterations; + clock_t start; + double elapsed; + + ECP P,G; + ECP8 Q,W; + FP48 g,w; + + FP16 cm; + BIG a,b,s,r; + + printf("\nTesting/Timing BLS48 Pairings\n"); + + ECP_generator(&G); + + BIG_rcopy(r,CURVE_Order); + BIG_randomnum(s,r,RNG); + ECP_copy(&P,&G); + PAIR_G1mul(&P,r); + + if (!ECP_isinf(&P)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_copy(&P,&G); + PAIR_G1mul(&P,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("G1 mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + + ECP8_generator(&W); + + ECP8_copy(&Q,&W); + ECP8_mul(&Q,r); + + if (!ECP8_isinf(&Q)) + { + printf("FAILURE - rQ!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP8_copy(&Q,&W); + PAIR_G2mul(&Q,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("G2 mul - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + + PAIR_ate(&w,&Q,&P); + PAIR_fexp(&w); + + FP48_copy(&g,&w); + + PAIR_GTpow(&g,r); + + if (!FP48_isunity(&g)) + { + printf("FAILURE - g^r!=1\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + FP48_copy(&g,&w); + PAIR_GTpow(&g,s); + + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("GT pow - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + FP48_copy(&g,&w); + + iterations=0; + start=clock(); + do { + FP48_compow(&cm,&g,s,r); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("GT pow (compressed) - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + iterations=0; + start=clock(); + do { + PAIR_ate(&w,&Q,&P); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("PAIRing ATE - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + iterations=0; + start=clock(); + do { + FP48_copy(&g,&w); + PAIR_fexp(&g); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("PAIRing FEXP - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + ECP_copy(&P,&G); + ECP8_copy(&Q,&W); + + PAIR_G1mul(&P,s); + PAIR_ate(&g,&Q,&P); + PAIR_fexp(&g); + + ECP_copy(&P,&G); + + PAIR_G2mul(&Q,s); + PAIR_ate(&w,&Q,&P); + PAIR_fexp(&w); + + if (!FP48_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,sP) \n"); + return 0; + } + + ECP8_copy(&Q,&W); + PAIR_ate(&g,&Q,&P); + PAIR_fexp(&g); + + PAIR_GTpow(&g,s); + + if (!FP48_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,P)^s \n"); + return 0; + } + return 0; +} +#endif + + +int RSA_2048(csprng *RNG) +{ + using namespace RSA2048; + + rsa_public_key pub; + rsa_private_key priv; + + int i,iterations; + clock_t start; + double elapsed; + + char m[RFS_RSA2048],d[RFS_RSA2048],c[RFS_RSA2048]; + octet M= {0,sizeof(m),m}; + octet D= {0,sizeof(d),d}; + octet C= {0,sizeof(c),c}; + + printf("\nTesting/Timing 2048-bit RSA\n"); + + printf("Generating 2048-bit RSA public/private key pair\n"); + + iterations=0; + start=clock(); + do { + RSA_KEY_PAIR(RNG,65537,&priv,&pub,NULL,NULL); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("RSA gen - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + M.len=RFS_RSA2048; + for (i=0;i<RFS_RSA2048;i++) M.val[i]=i%128; + + iterations=0; + start=clock(); + do { + RSA_ENCRYPT(&pub,&M,&C); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("RSA enc - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + iterations=0; + start=clock(); + do { + RSA_DECRYPT(&priv,&C,&D); + iterations++; + elapsed=(clock()-start)/(double)CLOCKS_PER_SEC; + } while (elapsed<MIN_TIME || iterations<MIN_ITERS); + elapsed=1000.0*elapsed/iterations; + printf("RSA dec - %8d iterations ",iterations); + printf(" %8.2lf ms per iteration\n",elapsed); + + for (i=0;i<RFS_RSA2048;i++) + { + if (M.val[i]!=D.val[i]) + { + printf("FAILURE - RSA decryption\n"); + return 0; + } + } + + printf("All tests pass\n"); + + return 0; +} + +int main() +{ + csprng RNG; + int i; + char pr[10]; + unsigned long ran; + + time((time_t *)&ran); + pr[0]=ran; + pr[1]=ran>>8; + pr[2]=ran>>16; + pr[3]=ran>>24; + for (i=0;i<10;i++) pr[i]=i; /*****4****/ + RAND_seed(&RNG,10,pr); + + ED_25519(&RNG); +#if CHUNK==32 || CHUNK==64 + NIST_256(&RNG); + GOLDI_LOCKS(&RNG); +#endif + BN_254(&RNG); +#if CHUNK==32 || CHUNK==64 + BLS_383(&RNG); + BLS_24(&RNG); + BLS_48(&RNG); +#endif + RSA_2048(&RNG); + +} http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/big.cpp ---------------------------------------------------------------------- diff --git a/version3/cpp/big.cpp b/version3/cpp/big.cpp new file mode 100644 index 0000000..ae72936 --- /dev/null +++ b/version3/cpp/big.cpp @@ -0,0 +1,1457 @@ +/* + 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. +*/ + +/* AMCL basic functions for BIG type */ +/* SU=m, SU is Stack Usage */ + +#include "big_XXX.h" + +/* test a=0? */ +int XXX::BIG_iszilch(BIG a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + if (a[i]!=0) return 0; + return 1; +} + +/* test a=1? */ +int XXX::BIG_isunity(BIG a) +{ + int i; + for (i=1; i<NLEN_XXX; i++) + if (a[i]!=0) return 0; + if (a[0]!=1) return 0; + return 1; +} + +/* test a=0? */ +int XXX::BIG_diszilch(DBIG a) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + if (a[i]!=0) return 0; + return 1; +} + +/* SU= 56 */ +/* output a */ +void XXX::BIG_output(BIG a) +{ + BIG b; + int i,len; + len=BIG_nbits(a); + if (len%4==0) len/=4; + else + { + len/=4; + len++; + } + if (len<MODBYTES_XXX*2) len=MODBYTES_XXX*2; + + for (i=len-1; i>=0; i--) + { + BIG_copy(b,a); + BIG_shr(b,i*4); + printf("%01x",(unsigned int) b[0]&15); + } +} + +/* SU= 16 */ +void XXX::BIG_rawoutput(BIG a) +{ + int i; + printf("("); + for (i=0; i<NLEN_XXX-1; i++) +#if CHUNK==64 + printf("%jx,",(uintmax_t) a[i]); + printf("%jx)",(uintmax_t) a[NLEN_XXX-1]); +#else + printf("%x,",(unsigned int) a[i]); + printf("%x)",(unsigned int) a[NLEN_XXX-1]); +#endif +} + +/* Swap a and b if d=1 */ +void XXX::BIG_cswap(BIG a,BIG b,int d) +{ + int i; + chunk t,c=d; + c=~(c-1); +#ifdef DEBUG_NORM + for (i=0; i<NLEN_XXX+2; i++) +#else + for (i=0; i<NLEN_XXX; i++) +#endif + { + t=c&(a[i]^b[i]); + a[i]^=t; + b[i]^=t; + } +} + +/* Move b to a if d=1 */ +void XXX::BIG_cmove(BIG f,BIG g,int d) +{ + int i; + chunk b=(chunk)-d; +#ifdef DEBUG_NORM + for (i=0; i<NLEN_XXX+2; i++) +#else + for (i=0; i<NLEN_XXX; i++) +#endif + { + f[i]^=(f[i]^g[i])&b; + } +} + +/* Move g to f if d=1 */ +void XXX::BIG_dcmove(DBIG f,DBIG g,int d) +{ + int i; + chunk b=(chunk)-d; +#ifdef DEBUG_NORM + for (i=0; i<DNLEN_XXX+2; i++) +#else + for (i=0; i<DNLEN_XXX; i++) +#endif + { + f[i]^=(f[i]^g[i])&b; + } +} + +/* convert BIG to/from bytes */ +/* SU= 64 */ +void XXX::BIG_toBytes(char *b,BIG a) +{ + int i; + BIG c; + BIG_copy(c,a); + BIG_norm(c); + for (i=MODBYTES_XXX-1; i>=0; i--) + { + b[i]=c[0]&0xff; + BIG_fshr(c,8); + } +} + +/* SU= 16 */ +void XXX::BIG_fromBytes(BIG a,char *b) +{ + int i; + BIG_zero(a); + for (i=0; i<MODBYTES_XXX; i++) + { + BIG_fshl(a,8); + a[0]+=(int)(unsigned char)b[i]; + } +#ifdef DEBUG_NORM + a[MPV_XXX]=1; a[MNV_XXX]=0; +#endif +} + +void XXX::BIG_fromBytesLen(BIG a,char *b,int s) +{ + int i,len=s; + BIG_zero(a); + + if (len>MODBYTES_XXX) len=MODBYTES_XXX; + for (i=0; i<len; i++) + { + BIG_fshl(a,8); + a[0]+=(int)(unsigned char)b[i]; + } +#ifdef DEBUG_NORM + a[MPV_XXX]=1; a[MNV_XXX]=0; +#endif +} + + + +/* SU= 88 */ +void XXX::BIG_doutput(DBIG a) +{ + DBIG b; + int i,len; + BIG_dnorm(a); + len=BIG_dnbits(a); + if (len%4==0) len/=4; + else + { + len/=4; + len++; + } + + for (i=len-1; i>=0; i--) + { + BIG_dcopy(b,a); + BIG_dshr(b,i*4); + printf("%01x",(unsigned int) b[0]&15); + } +} + + +void XXX::BIG_drawoutput(DBIG a) +{ + int i; + printf("("); + for (i=0; i<DNLEN_XXX-1; i++) +#if CHUNK==64 + printf("%jx,",(uintmax_t) a[i]); + printf("%jx)",(uintmax_t) a[DNLEN_XXX-1]); +#else + printf("%x,",(unsigned int) a[i]); + printf("%x)",(unsigned int) a[DNLEN_XXX-1]); +#endif +} + +/* Copy b=a */ +void XXX::BIG_copy(BIG b,BIG a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=a[i]; +#ifdef DEBUG_NORM + b[MPV_XXX]=a[MPV_XXX]; + b[MNV_XXX]=a[MNV_XXX]; +#endif +} + +/* Copy from ROM b=a */ +void XXX::BIG_rcopy(BIG b,const BIG a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=a[i]; +#ifdef DEBUG_NORM + b[MPV_XXX]=1; b[MNV_XXX]=0; +#endif +} + +/* double length DBIG copy b=a */ +void XXX::BIG_dcopy(DBIG b,DBIG a) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + b[i]=a[i]; +#ifdef DEBUG_NORM + b[DMPV_XXX]=a[DMPV_XXX]; + b[DMNV_XXX]=a[DMNV_XXX]; +#endif +} + +/* Copy BIG to bottom half of DBIG */ +void XXX::BIG_dscopy(DBIG b,BIG a) +{ + int i; + for (i=0; i<NLEN_XXX-1; i++) + b[i]=a[i]; + + b[NLEN_XXX-1]=a[NLEN_XXX-1]&BMASK_XXX; /* top word normalized */ + b[NLEN_XXX]=a[NLEN_XXX-1]>>BASEBITS_XXX; + + for (i=NLEN_XXX+1; i<DNLEN_XXX; i++) b[i]=0; +#ifdef DEBUG_NORM + b[DMPV_XXX]=a[MPV_XXX]; + b[DMNV_XXX]=a[MNV_XXX]; +#endif +} + +/* Copy BIG to top half of DBIG */ +void XXX::BIG_dsucopy(DBIG b,BIG a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=0; + for (i=NLEN_XXX; i<DNLEN_XXX; i++) + b[i]=a[i-NLEN_XXX]; +#ifdef DEBUG_NORM + b[DMPV_XXX]=a[MPV_XXX]; + b[DMNV_XXX]=a[MNV_XXX]; +#endif +} + +/* Copy bottom half of DBIG to BIG */ +void XXX::BIG_sdcopy(BIG b,DBIG a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=a[i]; +#ifdef DEBUG_NORM + b[MPV_XXX]=a[DMPV_XXX]; + b[MNV_XXX]=a[DMNV_XXX]; +#endif +} + +/* Copy top half of DBIG to BIG */ +void XXX::BIG_sducopy(BIG b,DBIG a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=a[i+NLEN_XXX]; +#ifdef DEBUG_NORM + b[MPV_XXX]=a[DMPV_XXX]; + b[MNV_XXX]=a[DMNV_XXX]; + +#endif +} + +/* Set a=0 */ +void XXX::BIG_zero(BIG a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + a[i]=0; +#ifdef DEBUG_NORM + a[MPV_XXX]=a[MNV_XXX]=0; +#endif +} + +void XXX::BIG_dzero(DBIG a) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + a[i]=0; +#ifdef DEBUG_NORM + a[DMPV_XXX]=a[DMNV_XXX]=0; +#endif +} + +/* set a=1 */ +void XXX::BIG_one(BIG a) +{ + int i; + a[0]=1; + for (i=1; i<NLEN_XXX; i++) + a[i]=0; +#ifdef DEBUG_NORM + a[MPV_XXX]=1; + a[MNV_XXX]=0; +#endif +} + + + +/* Set c=a+b */ +/* SU= 8 */ +void XXX::BIG_add(BIG c,BIG a,BIG b) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + c[i]=a[i]+b[i]; +#ifdef DEBUG_NORM + c[MPV_XXX]=a[MPV_XXX]+b[MPV_XXX]; + c[MNV_XXX]=a[MNV_XXX]+b[MNV_XXX]; + if (c[MPV_XXX]>NEXCESS_XXX) printf("add problem - positive digit overflow %d\n",c[MPV_XXX]); + if (c[MNV_XXX]>NEXCESS_XXX) printf("add problem - negative digit overflow %d\n",c[MNV_XXX]); + +#endif +} + +/* Set c=a or b */ +/* SU= 8 */ +void XXX::BIG_or(BIG c,BIG a,BIG b) +{ + int i; + BIG_norm(a); + BIG_norm(b); + for (i=0; i<NLEN_XXX; i++) + c[i]=a[i]|b[i]; +#ifdef DEBUG_NORM + c[MPV_XXX]=1; + c[MNV_XXX]=0; +#endif + +} + + +/* Set c=c+d */ +void XXX::BIG_inc(BIG c,int d) +{ + BIG_norm(c); + c[0]+=(chunk)d; +#ifdef DEBUG_NORM + c[MPV_XXX]+=1; +#endif +} + +/* Set c=a-b */ +/* SU= 8 */ +void XXX::BIG_sub(BIG c,BIG a,BIG b) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + c[i]=a[i]-b[i]; +#ifdef DEBUG_NORM + c[MPV_XXX]=a[MPV_XXX]+b[MNV_XXX]; + c[MNV_XXX]=a[MNV_XXX]+b[MPV_XXX]; + if (c[MPV_XXX]>NEXCESS_XXX) printf("sub problem - positive digit overflow %d\n",c[MPV_XXX]); + if (c[MNV_XXX]>NEXCESS_XXX) printf("sub problem - negative digit overflow %d\n",c[MNV_XXX]); + +#endif +} + +/* SU= 8 */ + +void XXX::BIG_dsub(DBIG c,DBIG a,DBIG b) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + c[i]=a[i]-b[i]; +#ifdef DEBUG_NORM + c[DMPV_XXX]=a[DMPV_XXX]+b[DMNV_XXX]; + c[DMNV_XXX]=a[DMNV_XXX]+b[DMPV_XXX]; + if (c[DMPV_XXX]>NEXCESS_XXX) printf("double sub problem - positive digit overflow %d\n",c[DMPV_XXX]); + if (c[DMNV_XXX]>NEXCESS_XXX) printf("double sub problem - negative digit overflow %d\n",c[DMNV_XXX]); +#endif +} + +void XXX::BIG_dadd(DBIG c,DBIG a,DBIG b) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + c[i]=a[i]+b[i]; +#ifdef DEBUG_NORM + c[DMPV_XXX]=a[DMPV_XXX]+b[DMNV_XXX]; + c[DMNV_XXX]=a[DMNV_XXX]+b[DMPV_XXX]; + if (c[DMPV_XXX]>NEXCESS_XXX) printf("double add problem - positive digit overflow %d\n",c[DMPV_XXX]); + if (c[DMNV_XXX]>NEXCESS_XXX) printf("double add problem - negative digit overflow %d\n",c[DMNV_XXX]); +#endif +} + +/* Set c=c-1 */ +void XXX::BIG_dec(BIG c,int d) +{ + BIG_norm(c); + c[0]-=(chunk)d; +#ifdef DEBUG_NORM + c[MNV_XXX]+=1; +#endif +} + +/* multiplication r=a*c by c<=NEXCESS_XXX */ +void XXX::BIG_imul(BIG r,BIG a,int c) +{ + int i; + for (i=0; i<NLEN_XXX; i++) r[i]=a[i]*c; +#ifdef DEBUG_NORM + r[MPV_XXX]=a[MPV_XXX]*c; + r[MNV_XXX]=a[MNV_XXX]*c; + if (r[MPV_XXX]>NEXCESS_XXX) printf("int mul problem - positive digit overflow %d\n",r[MPV_XXX]); + if (r[MNV_XXX]>NEXCESS_XXX) printf("int mul problem - negative digit overflow %d\n",r[MNV_XXX]); + +#endif +} + +/* multiplication r=a*c by larger integer - c<=FEXCESS */ +/* SU= 24 */ +chunk XXX::BIG_pmul(BIG r,BIG a,int c) +{ + int i; + chunk ak,carry=0; + for (i=0; i<NLEN_XXX; i++) + { + ak=a[i]; + r[i]=0; + carry=muladd(ak,(chunk)c,carry,&r[i]); + } +#ifdef DEBUG_NORM + r[MPV_XXX]=1; + r[MNV_XXX]=0; +#endif + return carry; +} + +/* r/=3 */ +/* SU= 16 */ +int XXX::BIG_div3(BIG r) +{ + int i; + chunk ak,base,carry=0; + BIG_norm(r); + base=((chunk)1<<BASEBITS_XXX); + for (i=NLEN_XXX-1; i>=0; i--) + { + ak=(carry*base+r[i]); + r[i]=ak/3; + carry=ak%3; + } + return (int)carry; +} + +/* multiplication c=a*b by even larger integer b>FEXCESS, resulting in DBIG */ +/* SU= 24 */ +void XXX::BIG_pxmul(DBIG c,BIG a,int b) +{ + int j; + chunk carry; + BIG_dzero(c); + carry=0; + for (j=0; j<NLEN_XXX; j++) + carry=muladd(a[j],(chunk)b,carry,&c[j]); + c[NLEN_XXX]=carry; +#ifdef DEBUG_NORM + c[DMPV_XXX]=1; + c[DMNV_XXX]=0; +#endif +} + +/* .. if you know the result will fit in a BIG, c must be distinct from a and b */ +/* SU= 40 */ +void XXX::BIG_smul(BIG c,BIG a,BIG b) +{ + int i,j; + chunk carry; + + BIG_zero(c); + for (i=0; i<NLEN_XXX; i++) + { + carry=0; + for (j=0; j<NLEN_XXX; j++) + { + if (i+j<NLEN_XXX) + carry=muladd(a[i],b[j],carry,&c[i+j]); + } + } +#ifdef DEBUG_NORM + c[MPV_XXX]=1; + c[MNV_XXX]=0; +#endif + +} + +/* Set c=a*b */ +/* SU= 72 */ +void XXX::BIG_mul(DBIG c,BIG a,BIG b) +{ + int i; +#ifdef dchunk + dchunk t,co; + dchunk s; + dchunk d[NLEN_XXX]; + int k; +#endif + +#ifdef DEBUG_NORM + if ((a[MPV_XXX]!=1 && a[MPV_XXX]!=0) || a[MNV_XXX]!=0) printf("First input to mul not normed\n"); + if ((b[MPV_XXX]!=1 && b[MPV_XXX]!=0) || b[MNV_XXX]!=0) printf("Second input to mul not normed\n"); +#endif + + /* Faster to Combafy it.. Let the compiler unroll the loops! */ + +#ifdef COMBA + + /* faster psuedo-Karatsuba method */ +#ifdef UNWOUND + + /* Insert output of faster.c here */ + +#else + for (i=0; i<NLEN_XXX; i++) + d[i]=(dchunk)a[i]*b[i]; + + s=d[0]; + t=s; + c[0]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + + for (k=1; k<NLEN_XXX; k++) + { + s+=d[k]; + t=co+s; + for (i=k; i>=1+k/2; i--) t+=(dchunk)(a[i]-a[k-i])*(b[k-i]-b[i]); + c[k]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + } + for (k=NLEN_XXX; k<2*NLEN_XXX-1; k++) + { + s-=d[k-NLEN_XXX]; + t=co+s; + for (i=NLEN_XXX-1; i>=1+k/2; i--) t+=(dchunk)(a[i]-a[k-i])*(b[k-i]-b[i]); + c[k]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + } + c[2*NLEN_XXX-1]=(chunk)co; + +#endif + +#else + int j; + chunk carry; + BIG_dzero(c); + for (i=0; i<NLEN_XXX; i++) + { + carry=0; + for (j=0; j<NLEN_XXX; j++) + carry=muladd(a[i],b[j],carry,&c[i+j]); + + c[NLEN_XXX+i]=carry; + } + +#endif + +#ifdef DEBUG_NORM + c[DMPV_XXX]=1; + c[DMNV_XXX]=0; +#endif +} + +/* Set c=a*a */ +/* SU= 80 */ +void XXX::BIG_sqr(DBIG c,BIG a) +{ + int i,j,last; +#ifdef dchunk + dchunk t,co; +#endif + +#ifdef DEBUG_NORM + if ((a[MPV_XXX]!=1 && a[MPV_XXX]!=0) || a[MNV_XXX]!=0) printf("Input to sqr not normed\n"); +#endif + /* Note 2*a[i] in loop below and extra addition */ + +#ifdef COMBA + +#ifdef UNWOUND + + /* Insert output of faster.c here */ + +#else + + + t=(dchunk)a[0]*a[0]; + c[0]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + + for (j=1;j<NLEN_XXX-1; ) + { + t=(dchunk)a[j]*a[0]; + for (i=1; i<(j+1)/2; i++) {t+=(dchunk)a[j-i]*a[i]; } + t+=t; t+=co; + c[j]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + j++; + t=(dchunk)a[j]*a[0]; + for (i=1; i<(j+1)/2; i++) {t+=(dchunk)a[j-i]*a[i]; } + t+=t; t+=co; + t+=(dchunk)a[j/2]*a[j/2]; + c[j]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + j++; + } + + for (j=NLEN_XXX-1+NLEN_XXX%2;j<DNLEN_XXX-3; ) + { + t=(dchunk)a[NLEN_XXX-1]*a[j-NLEN_XXX+1]; + for (i=j-NLEN_XXX+2; i<(j+1)/2; i++) {t+=(dchunk)a[j-i]*a[i]; } + t+=t; t+=co; + c[j]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + j++; + t=(dchunk)a[NLEN_XXX-1]*a[j-NLEN_XXX+1]; + for (i=j-NLEN_XXX+2; i<(j+1)/2; i++) {t+=(dchunk)a[j-i]*a[i]; } + t+=t; t+=co; + t+=(dchunk)a[j/2]*a[j/2]; + c[j]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + j++; + } + + t=(dchunk)a[NLEN_XXX-2]*a[NLEN_XXX-1]; + t+=t; t+=co; + c[DNLEN_XXX-3]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + + t=(dchunk)a[NLEN_XXX-1]*a[NLEN_XXX-1]+co; + c[DNLEN_XXX-2]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + c[DNLEN_XXX-1]=(chunk)co; + + +#endif + +#else + chunk carry; + BIG_dzero(c); + for (i=0; i<NLEN_XXX; i++) + { + carry=0; + for (j=i+1; j<NLEN_XXX; j++) + carry=muladd(a[i],a[j],carry,&c[i+j]); + c[NLEN_XXX+i]=carry; + } + + for (i=0; i<DNLEN_XXX; i++) c[i]*=2; + + for (i=0; i<NLEN_XXX; i++) + c[2*i+1]+=muladd(a[i],a[i],0,&c[2*i]); + + BIG_dnorm(c); +#endif + + +#ifdef DEBUG_NORM + c[DMPV_XXX]=1; + c[DMNV_XXX]=0; +#endif + +} + +/* Montgomery reduction */ +void XXX::BIG_monty(BIG a,BIG md,chunk MC,DBIG d) +{ + int i,k; + +#ifdef dchunk + dchunk t,c,s; + dchunk dd[NLEN_XXX]; + chunk v[NLEN_XXX]; +#endif + +#ifdef COMBA + +#ifdef UNWOUND + + /* Insert output of faster.c here */ + +#else + + t=d[0]; + v[0]=((chunk)t*MC)&BMASK_XXX; + t+=(dchunk)v[0]*md[0]; + c=(t>>BASEBITS_XXX)+d[1]; + s=0; + + for (k=1; k<NLEN_XXX; k++) + { + t=c+s+(dchunk)v[0]*md[k]; + for (i=k-1; i>k/2; i--) t+=(dchunk)(v[k-i]-v[i])*(md[i]-md[k-i]); + v[k]=((chunk)t*MC)&BMASK_XXX; + t+=(dchunk)v[k]*md[0]; + c=(t>>BASEBITS_XXX)+d[k+1]; + dd[k]=(dchunk)v[k]*md[k]; + s+=dd[k]; + } + for (k=NLEN_XXX; k<2*NLEN_XXX-1; k++) + { + t=c+s; + for (i=NLEN_XXX-1; i>=1+k/2; i--) t+=(dchunk)(v[k-i]-v[i])*(md[i]-md[k-i]); + a[k-NLEN_XXX]=(chunk)t&BMASK_XXX; + c=(t>>BASEBITS_XXX)+d[k+1]; + s-=dd[k-NLEN_XXX+1]; + } + a[NLEN_XXX-1]=(chunk)c&BMASK_XXX; + +#endif + + + +#else + int j; + chunk m,carry; + for (i=0; i<NLEN_XXX; i++) + { + if (MC==-1) m=(-d[i])&BMASK_XXX; + else + { + if (MC==1) m=d[i]; + else m=(MC*d[i])&BMASK_XXX; + } + carry=0; + for (j=0; j<NLEN_XXX; j++) + carry=muladd(m,md[j],carry,&d[i+j]); + d[NLEN_XXX+i]+=carry; + } + BIG_sducopy(a,d); + BIG_norm(a); + +#endif + +#ifdef DEBUG_NORM + a[MPV_XXX]=1; a[MNV_XXX]=0; +#endif +} + +/* General shift left of a by n bits */ +/* a MUST be normalised */ +/* SU= 32 */ +void XXX::BIG_shl(BIG a,int k) +{ + int i; + int n=k%BASEBITS_XXX; + int m=k/BASEBITS_XXX; + + a[NLEN_XXX-1]=((a[NLEN_XXX-1-m]<<n)); + if (NLEN_XXX>=m+2) a[NLEN_XXX-1]|=(a[NLEN_XXX-m-2]>>(BASEBITS_XXX-n)); + + for (i=NLEN_XXX-2; i>m; i--) + a[i]=((a[i-m]<<n)&BMASK_XXX)|(a[i-m-1]>>(BASEBITS_XXX-n)); + a[m]=(a[0]<<n)&BMASK_XXX; + for (i=0; i<m; i++) a[i]=0; + +} + +/* Fast shift left of a by n bits, where n less than a word, Return excess (but store it as well) */ +/* a MUST be normalised */ +/* SU= 16 */ +int XXX::BIG_fshl(BIG a,int n) +{ + int i; + + a[NLEN_XXX-1]=((a[NLEN_XXX-1]<<n))|(a[NLEN_XXX-2]>>(BASEBITS_XXX-n)); /* top word not masked */ + for (i=NLEN_XXX-2; i>0; i--) + a[i]=((a[i]<<n)&BMASK_XXX)|(a[i-1]>>(BASEBITS_XXX-n)); + a[0]=(a[0]<<n)&BMASK_XXX; + + return (int)(a[NLEN_XXX-1]>>((8*MODBYTES_XXX)%BASEBITS_XXX)); /* return excess - only used in ff.c */ +} + +/* double length left shift of a by k bits - k can be > BASEBITS_XXX , a MUST be normalised */ +/* SU= 32 */ +void XXX::BIG_dshl(DBIG a,int k) +{ + int i; + int n=k%BASEBITS_XXX; + int m=k/BASEBITS_XXX; + + a[DNLEN_XXX-1]=((a[DNLEN_XXX-1-m]<<n))|(a[DNLEN_XXX-m-2]>>(BASEBITS_XXX-n)); + + for (i=DNLEN_XXX-2; i>m; i--) + a[i]=((a[i-m]<<n)&BMASK_XXX)|(a[i-m-1]>>(BASEBITS_XXX-n)); + a[m]=(a[0]<<n)&BMASK_XXX; + for (i=0; i<m; i++) a[i]=0; + +} + +/* General shift rightof a by k bits */ +/* a MUST be normalised */ +/* SU= 32 */ +void XXX::BIG_shr(BIG a,int k) +{ + int i; + int n=k%BASEBITS_XXX; + int m=k/BASEBITS_XXX; + for (i=0; i<NLEN_XXX-m-1; i++) + a[i]=(a[m+i]>>n)|((a[m+i+1]<<(BASEBITS_XXX-n))&BMASK_XXX); + if (NLEN_XXX>m) a[NLEN_XXX-m-1]=a[NLEN_XXX-1]>>n; + for (i=NLEN_XXX-m; i<NLEN_XXX; i++) a[i]=0; + +} + +/* Fast combined shift, subtract and norm. Return sign of result */ +int XXX::BIG_ssn(BIG r,BIG a,BIG m) +{ + int i,n=NLEN_XXX-1; + chunk carry; + m[0]=(m[0]>>1)|((m[1]<<(BASEBITS_XXX-1))&BMASK_XXX); + r[0]=a[0]-m[0]; + carry=r[0]>>BASEBITS_XXX; + r[0]&=BMASK_XXX; + + for (i=1;i<n;i++) + { + m[i]=(m[i]>>1)|((m[i+1]<<(BASEBITS_XXX-1))&BMASK_XXX); + r[i]=a[i]-m[i]+carry; + carry=r[i]>>BASEBITS_XXX; + r[i]&=BMASK_XXX; + } + + m[n]>>=1; + r[n]=a[n]-m[n]+carry; +#ifdef DEBUG_NORM + r[MPV_XXX]=1; r[MNV_XXX]=0; +#endif + return ((r[n]>>(CHUNK-1))&1); +} + +/* Faster shift right of a by k bits. Return shifted out part */ +/* a MUST be normalised */ +/* SU= 16 */ +int XXX::BIG_fshr(BIG a,int k) +{ + int i; + chunk r=a[0]&(((chunk)1<<k)-1); /* shifted out part */ + for (i=0; i<NLEN_XXX-1; i++) + a[i]=(a[i]>>k)|((a[i+1]<<(BASEBITS_XXX-k))&BMASK_XXX); + a[NLEN_XXX-1]=a[NLEN_XXX-1]>>k; + return (int)r; +} + +/* double length right shift of a by k bits - can be > BASEBITS_XXX */ +/* SU= 32 */ +void XXX::BIG_dshr(DBIG a,int k) +{ + int i; + int n=k%BASEBITS_XXX; + int m=k/BASEBITS_XXX; + for (i=0; i<DNLEN_XXX-m-1; i++) + a[i]=(a[m+i]>>n)|((a[m+i+1]<<(BASEBITS_XXX-n))&BMASK_XXX); + a[DNLEN_XXX-m-1]=a[DNLEN_XXX-1]>>n; + for (i=DNLEN_XXX-m; i<DNLEN_XXX; i++ ) a[i]=0; +} + +/* Split DBIG d into two BIGs t|b. Split happens at n bits, where n falls into NLEN_XXX word */ +/* d MUST be normalised */ +/* SU= 24 */ +chunk XXX::BIG_split(BIG t,BIG b,DBIG d,int n) +{ + int i; + chunk nw,carry=0; + int m=n%BASEBITS_XXX; + + if (m==0) + { + for (i=0; i<NLEN_XXX; i++) b[i]=d[i]; + if (t!=b) + { + for (i=NLEN_XXX; i<2*NLEN_XXX; i++) t[i-NLEN_XXX]=d[i]; + carry=t[NLEN_XXX-1]>>BASEBITS_XXX; + t[NLEN_XXX-1]=t[NLEN_XXX-1]&BMASK_XXX; /* top word normalized */ + } + return carry; + } + + for (i=0; i<NLEN_XXX-1; i++) b[i]=d[i]; + + b[NLEN_XXX-1]=d[NLEN_XXX-1]&(((chunk)1<<m)-1); + + if (t!=b) + { + carry=(d[DNLEN_XXX-1]<<(BASEBITS_XXX-m)); + for (i=DNLEN_XXX-2; i>=NLEN_XXX-1; i--) + { + nw=(d[i]>>m)|carry; + carry=(d[i]<<(BASEBITS_XXX-m))&BMASK_XXX; + t[i-NLEN_XXX+1]=nw; + } + } +#ifdef DEBUG_NORM + t[MPV_XXX]=1; t[MNV_XXX]=0; + b[MPV_XXX]=1; b[MNV_XXX]=0; +#endif + return carry; +} + +/* you gotta keep the sign of carry! Look - no branching! */ +/* Note that sign bit is needed to disambiguate between +ve and -ve values */ +/* normalise BIG - force all digits < 2^BASEBITS_XXX */ +chunk XXX::BIG_norm(BIG a) +{ + int i; + chunk d,carry=0; + for (i=0; i<NLEN_XXX-1; i++) + { + d=a[i]+carry; + a[i]=d&BMASK_XXX; + carry=d>>BASEBITS_XXX; + } + a[NLEN_XXX-1]=(a[NLEN_XXX-1]+carry); + +#ifdef DEBUG_NORM + a[MPV_XXX]=1; a[MNV_XXX]=0; +#endif + return (a[NLEN_XXX-1]>>((8*MODBYTES_XXX)%BASEBITS_XXX)); /* only used in ff.c */ +} + +void XXX::BIG_dnorm(DBIG a) +{ + int i; + chunk d,carry=0; + for (i=0; i<DNLEN_XXX-1; i++) + { + d=a[i]+carry; + a[i]=d&BMASK_XXX; + carry=d>>BASEBITS_XXX; + } + a[DNLEN_XXX-1]=(a[DNLEN_XXX-1]+carry); +#ifdef DEBUG_NORM + a[DMPV_XXX]=1; a[DMNV_XXX]=0; +#endif +} + +/* Compare a and b. Return 1 for a>b, -1 for a<b, 0 for a==b */ +/* a and b MUST be normalised before call */ +int XXX::BIG_comp(BIG a,BIG b) +{ + int i; + for (i=NLEN_XXX-1; i>=0; i--) + { + if (a[i]==b[i]) continue; + if (a[i]>b[i]) return 1; + else return -1; + } + return 0; +} + +int XXX::BIG_dcomp(DBIG a,DBIG b) +{ + int i; + for (i=DNLEN_XXX-1; i>=0; i--) + { + if (a[i]==b[i]) continue; + if (a[i]>b[i]) return 1; + else return -1; + } + return 0; +} + +/* return number of bits in a */ +/* SU= 8 */ +int XXX::BIG_nbits(BIG a) +{ + int bts,k=NLEN_XXX-1; + BIG t; + chunk c; + BIG_copy(t,a); + BIG_norm(t); + while (k>=0 && t[k]==0) k--; + if (k<0) return 0; + bts=BASEBITS_XXX*k; + c=t[k]; + while (c!=0) + { + c/=2; + bts++; + } + return bts; +} + +/* SU= 8, Calculate number of bits in a DBIG - output normalised */ +int XXX::BIG_dnbits(DBIG a) +{ + int bts,k=DNLEN_XXX-1; + DBIG t; + chunk c; + BIG_dcopy(t,a); + BIG_dnorm(t); + while (k>=0 && t[k]==0) k--; + if (k<0) return 0; + bts=BASEBITS_XXX*k; + c=t[k]; + while (c!=0) + { + c/=2; + bts++; + } + return bts; +} + + +/* Set b=b mod c */ +/* SU= 16 */ +void XXX::BIG_mod(BIG b,BIG c1) +{ + int k=0; + BIG r; /**/ + BIG c; + BIG_copy(c,c1); + + BIG_norm(b); + if (BIG_comp(b,c)<0) + return; + do + { + BIG_fshl(c,1); + k++; + } + while (BIG_comp(b,c)>=0); + + while (k>0) + { + BIG_fshr(c,1); + +// constant time... + BIG_sub(r,b,c); + BIG_norm(r); + BIG_cmove(b,r,1-((r[NLEN_XXX-1]>>(CHUNK-1))&1)); + k--; + } +} + +/* Set a=b mod c, b is destroyed. Slow but rarely used. */ +/* SU= 96 */ +void XXX::BIG_dmod(BIG a,DBIG b,BIG c) +{ + int k=0; + DBIG m,r; + BIG_dnorm(b); + BIG_dscopy(m,c); + + if (BIG_dcomp(b,m)<0) + { + BIG_sdcopy(a,b); + return; + } + + do + { + BIG_dshl(m,1); + k++; + } + while (BIG_dcomp(b,m)>=0); + + while (k>0) + { + BIG_dshr(m,1); +// constant time... + BIG_dsub(r,b,m); + BIG_dnorm(r); + BIG_dcmove(b,r,1-((r[DNLEN_XXX-1]>>(CHUNK-1))&1)); + + k--; + } + BIG_sdcopy(a,b); +} + +/* Set a=b/c, b is destroyed. Slow but rarely used. */ +/* SU= 136 */ + +void XXX::BIG_ddiv(BIG a,DBIG b,BIG c) +{ + int d,k=0; + DBIG m,dr; + BIG e,r; + BIG_dnorm(b); + BIG_dscopy(m,c); + + BIG_zero(a); + BIG_zero(e); + BIG_inc(e,1); + + while (BIG_dcomp(b,m)>=0) + { + BIG_fshl(e,1); + BIG_dshl(m,1); + k++; + } + + while (k>0) + { + BIG_dshr(m,1); + BIG_fshr(e,1); + + BIG_dsub(dr,b,m); + BIG_dnorm(dr); + d=1-((dr[DNLEN_XXX-1]>>(CHUNK-1))&1); + BIG_dcmove(b,dr,d); + + BIG_add(r,a,e); + BIG_norm(r); + BIG_cmove(a,r,d); + + k--; + } +} + +/* SU= 136 */ + +void XXX::BIG_sdiv(BIG a,BIG c) +{ + int d,k=0; + BIG m,e,b,r; + BIG_norm(a); + BIG_copy(b,a); + BIG_copy(m,c); + + BIG_zero(a); + BIG_zero(e); + BIG_inc(e,1); + + while (BIG_comp(b,m)>=0) + { + BIG_fshl(e,1); + BIG_fshl(m,1); + k++; + } + + while (k>0) + { + BIG_fshr(m,1); + BIG_fshr(e,1); + + BIG_sub(r,b,m); + BIG_norm(r); + d=1-((r[NLEN_XXX-1]>>(CHUNK-1))&1); + BIG_cmove(b,r,d); + + BIG_add(r,a,e); + BIG_norm(r); + BIG_cmove(a,r,d); + k--; + } +} + +/* return LSB of a */ +int XXX::BIG_parity(BIG a) +{ + return a[0]%2; +} + +/* return n-th bit of a */ +/* SU= 16 */ +int XXX::BIG_bit(BIG a,int n) +{ + if (a[n/BASEBITS_XXX]&((chunk)1<<(n%BASEBITS_XXX))) return 1; + else return 0; +} + +/* return last n bits of a, where n is small < BASEBITS_XXX */ +/* SU= 16 */ +int XXX::BIG_lastbits(BIG a,int n) +{ + int msk=(1<<n)-1; + BIG_norm(a); + return ((int)a[0])&msk; +} + +/* get 8*MODBYTES_XXX size random number */ +void XXX::BIG_random(BIG m,csprng *rng) +{ + int i,b,j=0,r=0; + int len=8*MODBYTES_XXX; + + BIG_zero(m); + /* generate random BIG */ + for (i=0; i<len; i++) + { + if (j==0) r=RAND_byte(rng); + else r>>=1; + b=r&1; + BIG_shl(m,1); + m[0]+=b; + j++; + j&=7; + } + +#ifdef DEBUG_NORM + m[MPV_XXX]=1; m[MNV_XXX]=0; +#endif +} + +/* get random BIG from rng, modulo q. Done one bit at a time, so its portable */ + +void XXX::BIG_randomnum(BIG m,BIG q,csprng *rng) +{ + int i,b,j=0,r=0; + DBIG d; + BIG_dzero(d); + /* generate random DBIG */ + for (i=0; i<2*BIG_nbits(q); i++) + { + if (j==0) r=RAND_byte(rng); + else r>>=1; + b=r&1; + BIG_dshl(d,1); + d[0]+=b; + j++; + j&=7; + } + /* reduce modulo a BIG. Removes bias */ + BIG_dmod(m,d,q); +#ifdef DEBUG_NORM + m[MPV_XXX]=1; m[MNV_XXX]=0; +#endif +} + +/* Set r=a*b mod m */ +/* SU= 96 */ +void XXX::BIG_modmul(BIG r,BIG a1,BIG b1,BIG m) +{ + DBIG d; + BIG a,b; + BIG_copy(a,a1); + BIG_copy(b,b1); + BIG_mod(a,m); + BIG_mod(b,m); + + BIG_mul(d,a,b); + BIG_dmod(r,d,m); +} + +/* Set a=a*a mod m */ +/* SU= 88 */ +void XXX::BIG_modsqr(BIG r,BIG a1,BIG m) +{ + DBIG d; + BIG a; + BIG_copy(a,a1); + BIG_mod(a,m); + BIG_sqr(d,a); + BIG_dmod(r,d,m); +} + +/* Set r=-a mod m */ +/* SU= 16 */ +void XXX::BIG_modneg(BIG r,BIG a1,BIG m) +{ + BIG a; + BIG_copy(a,a1); + BIG_mod(a,m); + BIG_sub(r,m,a); +} + +/* Set a=a/b mod m */ +/* SU= 136 */ +void XXX::BIG_moddiv(BIG r,BIG a1,BIG b1,BIG m) +{ + DBIG d; + BIG z; + BIG a,b; + BIG_copy(a,a1); + BIG_copy(b,b1); + BIG_mod(a,m); + BIG_invmodp(z,b,m); + + BIG_mul(d,a,z); + BIG_dmod(r,d,m); +} + +/* Get jacobi Symbol (a/p). Returns 0, 1 or -1 */ +/* SU= 216 */ +int XXX::BIG_jacobi(BIG a,BIG p) +{ + int n8,k,m=0; + BIG t,x,n,zilch,one; + BIG_one(one); + BIG_zero(zilch); + if (BIG_parity(p)==0 || BIG_comp(a,zilch)==0 || BIG_comp(p,one)<=0) return 0; + BIG_norm(a); + BIG_copy(x,a); + BIG_copy(n,p); + BIG_mod(x,p); + + while (BIG_comp(n,one)>0) + { + if (BIG_comp(x,zilch)==0) return 0; + n8=BIG_lastbits(n,3); + k=0; + while (BIG_parity(x)==0) + { + k++; + BIG_shr(x,1); + } + if (k%2==1) m+=(n8*n8-1)/8; + m+=(n8-1)*(BIG_lastbits(x,2)-1)/4; + BIG_copy(t,n); + + BIG_mod(t,x); + BIG_copy(n,x); + BIG_copy(x,t); + m%=2; + + } + if (m==0) return 1; + else return -1; +} + +/* Set r=1/a mod p. Binary method */ +/* SU= 240 */ +void XXX::BIG_invmodp(BIG r,BIG a,BIG p) +{ + BIG u,v,x1,x2,t,one; + BIG_mod(a,p); + BIG_copy(u,a); + BIG_copy(v,p); + BIG_one(one); + BIG_copy(x1,one); + BIG_zero(x2); + + while (BIG_comp(u,one)!=0 && BIG_comp(v,one)!=0) + { + while (BIG_parity(u)==0) + { + BIG_fshr(u,1); + if (BIG_parity(x1)!=0) + { + BIG_add(x1,p,x1); + BIG_norm(x1); + } + BIG_fshr(x1,1); + } + while (BIG_parity(v)==0) + { + BIG_fshr(v,1); + if (BIG_parity(x2)!=0) + { + BIG_add(x2,p,x2); + BIG_norm(x2); + } + BIG_fshr(x2,1); + } + if (BIG_comp(u,v)>=0) + { + BIG_sub(u,u,v); + BIG_norm(u); + if (BIG_comp(x1,x2)>=0) BIG_sub(x1,x1,x2); + else + { + BIG_sub(t,p,x2); + BIG_add(x1,x1,t); + } + BIG_norm(x1); + } + else + { + BIG_sub(v,v,u); + BIG_norm(v); + if (BIG_comp(x2,x1)>=0) BIG_sub(x2,x2,x1); + else + { + BIG_sub(t,p,x1); + BIG_add(x2,x2,t); + } + BIG_norm(x2); + } + } + if (BIG_comp(u,one)==0) + BIG_copy(r,x1); + else + BIG_copy(r,x2); +} + +/* set x = x mod 2^m */ +void XXX::BIG_mod2m(BIG x,int m) +{ + int i,wd,bt; + chunk msk; + BIG_norm(x); + + wd=m/BASEBITS_XXX; + bt=m%BASEBITS_XXX; + msk=((chunk)1<<bt)-1; + x[wd]&=msk; + for (i=wd+1; i<NLEN_XXX; i++) x[i]=0; +} + +// new +/* Convert to DBIG number from byte array of given length */ +void XXX::BIG_dfromBytesLen(DBIG a,char *b,int s) +{ + int i,len=s; + BIG_dzero(a); + + for (i=0; i<len; i++) + { + BIG_dshl(a,8); + a[0]+=(int)(unsigned char)b[i]; + } +#ifdef DEBUG_NORM + a[DMPV_XXX]=1; a[DMNV_XXX]=0; +#endif +}
