http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version3/cpp/amcl.h ---------------------------------------------------------------------- diff --git a/version3/cpp/amcl.h b/version3/cpp/amcl.h deleted file mode 100644 index 4b88f07..0000000 --- a/version3/cpp/amcl.h +++ /dev/null @@ -1,585 +0,0 @@ -/* - 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/1add7560/version3/cpp/arch.h ---------------------------------------------------------------------- diff --git a/version3/cpp/arch.h b/version3/cpp/arch.h deleted file mode 100644 index d21d0cd..0000000 --- a/version3/cpp/arch.h +++ /dev/null @@ -1,98 +0,0 @@ -/* - 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/1add7560/version3/cpp/benchtest_all.cpp ---------------------------------------------------------------------- diff --git a/version3/cpp/benchtest_all.cpp b/version3/cpp/benchtest_all.cpp deleted file mode 100644 index 28d1d33..0000000 --- a/version3/cpp/benchtest_all.cpp +++ /dev/null @@ -1,973 +0,0 @@ -/* 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 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 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 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/1add7560/version3/cpp/big.cpp ---------------------------------------------------------------------- diff --git a/version3/cpp/big.cpp b/version3/cpp/big.cpp deleted file mode 100644 index 0da0de8..0000000 --- a/version3/cpp/big.cpp +++ /dev/null @@ -1,1508 +0,0 @@ -/* - 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_norm(a); - 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]; - //BIG_inc(a,(int)(unsigned char)b[i]); BIG_norm(a); - } -#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; -// BIG_norm(a); - 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_norm(a); -// BIG_norm(b); - - 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; -// BIG_dnorm(d); - - 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 NAF value as +/- 1, 3 or 5. x and x3 should be normed. -nbs is number of bits processed, and nzs is number of trailing 0s detected */ -/* SU= 32 */ -/* -int BIG_nafbits(BIG x,BIG x3,int i,int *nbs,int *nzs) -{ - int j,r,nb; - - nb=BIG_bit(x3,i)-BIG_bit(x,i); - *nbs=1; - *nzs=0; - if (nb==0) return 0; - if (i==0) return nb; - - if (nb>0) r=1; - else r=(-1); - - for (j=i-1;j>0;j--) - { - (*nbs)++; - r*=2; - nb=BIG_bit(x3,j)-BIG_bit(x,j); - if (nb>0) r+=1; - if (nb<0) r-=1; - if (abs(r)>5) break; - } - - if (r%2!=0 && j!=0) - { // backtrack - if (nb>0) r=(r-1)/2; - if (nb<0) r=(r+1)/2; - (*nbs)--; - } - - while (r%2==0) - { // remove trailing zeros - r/=2; - (*nzs)++; - (*nbs)--; - } - return r; -} -*/ - -/* 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); -// BIG_mod(r,m); -} - -/* 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); -// if (m>=MODBITS) return; - 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 -}
