http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/arch.h ---------------------------------------------------------------------- diff --git a/version3/c/arch.h b/version3/c/arch.h new file mode 100644 index 0000000..1de0332 --- /dev/null +++ b/version3/c/arch.h @@ -0,0 +1,129 @@ +/* + 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 + + + + +/*** START OF USER CONFIGURABLE SECTION - set architecture ***/ + +#ifdef CMAKE +#define CHUNK @AMCL_CHUNK@ /**< 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 */ +#else +#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 */ +#endif + +/*** END OF USER CONFIGURABLE SECTION ***/ + +/* Create Integer types */ +/* Support for C99? Note for GCC need to explicitly include -std=c99 in command line */ + +#if __STDC_VERSION__ >= 199901L +/* C99 code */ +#define C99 +#else +/* Not C99 code */ +#endif + +#ifndef C99 /* You are on your own! These are for Microsoft C */ +#define byte unsigned char /**< 8-bit unsigned integer */ +#define sign32 __int32 /**< 32-bit signed integer */ +#define sign8 signed char /**< 8-bit signed integer */ +#define sign16 short int /**< 16-bit signed integer */ +#define sign64 long long /**< 64-bit signed integer */ +#define unsign32 unsigned __int32 /**< 32-bit unsigned integer */ +#define unsign64 unsigned long long /**< 64-bit unsigned integer */ +#else +#include <stdint.h> +#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 */ +#endif + +#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 +#ifndef C99 +#define chunk __int16 /**< C type corresponding to word length */ +#define dchunk __int32 /**< Always define double length chunk type if available */ +#else +#define chunk int16_t /**< C type corresponding to word length */ +#define dchunk int32_t /**< Always define double length chunk type if available */ +#endif +#endif + +#if CHUNK == 32 +#ifndef C99 +#define chunk __int32 /**< C type corresponding to word length */ +#define dchunk __int64 /**< Always define double length chunk type if available */ +#else +#define chunk int32_t /**< C type corresponding to word length */ +#define dchunk int64_t /**< Always define double length chunk type if available */ +#endif +#endif + +#if CHUNK == 64 + +#ifndef C99 +#define chunk __int64 /**< C type corresponding to word length */ +/**< Note - no 128-bit type available */ +#else +#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 +#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/c/benchtest_all.c ---------------------------------------------------------------------- diff --git a/version3/c/benchtest_all.c b/version3/c/benchtest_all.c new file mode 100644 index 0000000..a70b713 --- /dev/null +++ b/version3/c/benchtest_all.c @@ -0,0 +1,1064 @@ +/* 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_2048.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 + +#if CHUNK==16 + +#define BIG_ED BIG_256_13 +#define BIG_ED_rcopy BIG_256_13_rcopy +#define BIG_ED_randomnum BIG_256_13_randomnum + +#define BIG_BN BIG_256_13 +#define BIG_BN_rcopy BIG_256_13_rcopy +#define BIG_BN_randomnum BIG_256_13_randomnum + +#endif + +#if CHUNK==32 + +#define BIG_ED BIG_256_29 +#define BIG_ED_rcopy BIG_256_29_rcopy +#define BIG_ED_randomnum BIG_256_29_randomnum + +#define BIG_NT BIG_256_28 +#define BIG_NT_rcopy BIG_256_28_rcopy +#define BIG_NT_randomnum BIG_256_28_randomnum + +#define BIG_GL BIG_448_29 +#define BIG_GL_rcopy BIG_448_29_rcopy +#define BIG_GL_randomnum BIG_448_29_randomnum + +#define BIG_BN BIG_256_28 +#define BIG_BN_rcopy BIG_256_28_rcopy +#define BIG_BN_randomnum BIG_256_28_randomnum + +#define BIG_BLS12 BIG_384_29 +#define BIG_BLS12_rcopy BIG_384_29_rcopy +#define BIG_BLS12_randomnum BIG_384_29_randomnum + +#define BIG_BLS24 BIG_480_29 +#define BIG_BLS24_rcopy BIG_480_29_rcopy +#define BIG_BLS24_randomnum BIG_480_29_randomnum + +#define BIG_BLS48 BIG_560_29 +#define BIG_BLS48_rcopy BIG_560_29_rcopy +#define BIG_BLS48_randomnum BIG_560_29_randomnum + +#endif + +#if CHUNK==64 + +#define BIG_ED BIG_256_56 +#define BIG_ED_rcopy BIG_256_56_rcopy +#define BIG_ED_randomnum BIG_256_56_randomnum + +#define BIG_NT BIG_256_56 +#define BIG_NT_rcopy BIG_256_56_rcopy +#define BIG_NT_randomnum BIG_256_56_randomnum + +#define BIG_GL BIG_448_58 +#define BIG_GL_rcopy BIG_448_58_rcopy +#define BIG_GL_randomnum BIG_448_58_randomnum + +#define BIG_BN BIG_256_56 +#define BIG_BN_rcopy BIG_256_56_rcopy +#define BIG_BN_randomnum BIG_256_56_randomnum + +#define BIG_BLS12 BIG_384_58 +#define BIG_BLS12_rcopy BIG_384_58_rcopy +#define BIG_BLS12_randomnum BIG_384_58_randomnum + +#define BIG_BLS24 BIG_480_56 +#define BIG_BLS24_rcopy BIG_480_56_rcopy +#define BIG_BLS24_randomnum BIG_480_56_randomnum + +#define BIG_BLS48 BIG_560_58 +#define BIG_BLS48_rcopy BIG_560_58_rcopy +#define BIG_BLS48_randomnum BIG_560_58_randomnum + +#endif + +int ED_25519(csprng *RNG) +{ + int i,iterations; + clock_t start; + double elapsed; + ECP_ED25519 EP,EG; + BIG_ED s,r,x,y; + printf("Testing/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_ED25519_generator(&EG); + + BIG_ED_rcopy(r,CURVE_Order_ED25519); + BIG_ED_randomnum(s,r,RNG); + ECP_ED25519_copy(&EP,&EG); + ECP_ED25519_mul(&EP,r); + + if (!ECP_ED25519_isinf(&EP)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_ED25519_copy(&EP,&EG); + ECP_ED25519_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) +{ + int i,iterations; + clock_t start; + double elapsed; + ECP_NIST256 EP,EG; + BIG_NT s,r,x,y; + printf("Testing/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_NIST256_generator(&EG); + + BIG_NT_rcopy(r,CURVE_Order_NIST256); + BIG_NT_randomnum(s,r,RNG); + ECP_NIST256_copy(&EP,&EG); + ECP_NIST256_mul(&EP,r); + + if (!ECP_NIST256_isinf(&EP)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_NIST256_copy(&EP,&EG); + ECP_NIST256_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 GOLD_LOCKS(csprng *RNG) +{ + int i,iterations; + clock_t start; + double elapsed; + ECP_GOLDILOCKS EP,EG; + BIG_GL s,r,x,y; + printf("Testing/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 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_GOLDILOCKS_generator(&EG); + + BIG_GL_rcopy(r,CURVE_Order_GOLDILOCKS); + BIG_GL_randomnum(s,r,RNG); + ECP_GOLDILOCKS_copy(&EP,&EG); + ECP_GOLDILOCKS_mul(&EP,r); + + if (!ECP_GOLDILOCKS_isinf(&EP)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_GOLDILOCKS_copy(&EP,&EG); + ECP_GOLDILOCKS_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) +{ + int i,iterations; + clock_t start; + double elapsed; + + ECP_BN254 P,G; + ECP2_BN254 Q,W; + FP12_BN254 g,w; + FP4_BN254 cm; + + BIG_BN s,r,x,y; + printf("\nTesting/Timing BN254 Pairings\n"); + + ECP_BN254_generator(&G); + + + BIG_BN_rcopy(r,CURVE_Order_BN254); + BIG_BN_randomnum(s,r,RNG); + ECP_BN254_copy(&P,&G); + PAIR_BN254_G1mul(&P,r); + + if (!ECP_BN254_isinf(&P)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_BN254_copy(&P,&G); + PAIR_BN254_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_BN254_generator(&W); + + ECP2_BN254_copy(&Q,&W); + ECP2_BN254_mul(&Q,r); + + if (!ECP2_BN254_isinf(&Q)) + { + printf("FAILURE - rQ!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP2_BN254_copy(&Q,&W); + PAIR_BN254_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_BN254_ate(&w,&Q,&P); + PAIR_BN254_fexp(&w); + + FP12_BN254_copy(&g,&w); + + PAIR_BN254_GTpow(&g,r); + + if (!FP12_BN254_isunity(&g)) + { + printf("FAILURE - g^r!=1\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + FP12_BN254_copy(&g,&w); + PAIR_BN254_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_BN254_copy(&g,&w); + + iterations=0; + start=clock(); + do { + FP12_BN254_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_BN254_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_BN254_copy(&g,&w); + PAIR_BN254_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_BN254_copy(&P,&G); + ECP2_BN254_copy(&Q,&W); + + PAIR_BN254_G1mul(&P,s); + PAIR_BN254_ate(&g,&Q,&P); + PAIR_BN254_fexp(&g); + + ECP_BN254_copy(&P,&G); + + PAIR_BN254_G2mul(&Q,s); + PAIR_BN254_ate(&w,&Q,&P); + PAIR_BN254_fexp(&w); + + if (!FP12_BN254_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,sP) \n"); + return 0; + } + + ECP2_BN254_copy(&Q,&W); + PAIR_BN254_ate(&g,&Q,&P); + PAIR_BN254_fexp(&g); + + PAIR_BN254_GTpow(&g,s); + + if (!FP12_BN254_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) +{ + int i,iterations; + clock_t start; + double elapsed; + + ECP_BLS383 P,G; + ECP2_BLS383 Q,W; + FP12_BLS383 g,w; + FP4_BLS383 cm; + + BIG_BLS12 s,r,x,y; + printf("\nTesting/Timing BLS383 Pairings\n"); + + ECP_BLS383_generator(&G); + + + BIG_BLS12_rcopy(r,CURVE_Order_BLS383); + BIG_BLS12_randomnum(s,r,RNG); + ECP_BLS383_copy(&P,&G); + PAIR_BLS383_G1mul(&P,r); + + if (!ECP_BLS383_isinf(&P)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_BLS383_copy(&P,&G); + PAIR_BLS383_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_BLS383_generator(&W); + + ECP2_BLS383_copy(&Q,&W); + ECP2_BLS383_mul(&Q,r); + + if (!ECP2_BLS383_isinf(&Q)) + { + printf("FAILURE - rQ!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP2_BLS383_copy(&Q,&W); + PAIR_BLS383_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_BLS383_ate(&w,&Q,&P); + PAIR_BLS383_fexp(&w); + + FP12_BLS383_copy(&g,&w); + + PAIR_BLS383_GTpow(&g,r); + + if (!FP12_BLS383_isunity(&g)) + { + printf("FAILURE - g^r!=1\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + FP12_BLS383_copy(&g,&w); + PAIR_BLS383_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_BLS383_copy(&g,&w); + + iterations=0; + start=clock(); + do { + FP12_BLS383_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_BLS383_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_BLS383_copy(&g,&w); + PAIR_BLS383_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_BLS383_copy(&P,&G); + ECP2_BLS383_copy(&Q,&W); + + PAIR_BLS383_G1mul(&P,s); + PAIR_BLS383_ate(&g,&Q,&P); + PAIR_BLS383_fexp(&g); + + ECP_BLS383_copy(&P,&G); + + PAIR_BLS383_G2mul(&Q,s); + PAIR_BLS383_ate(&w,&Q,&P); + PAIR_BLS383_fexp(&w); + + if (!FP12_BLS383_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,sP) \n"); + return 0; + } + + ECP2_BLS383_copy(&Q,&W); + PAIR_BLS383_ate(&g,&Q,&P); + PAIR_BLS383_fexp(&g); + + PAIR_BLS383_GTpow(&g,s); + + if (!FP12_BLS383_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,P)^s \n"); + return 0; + } + return 0; +} + +int BLS_24(csprng *RNG) +{ + int i,iterations; + clock_t start; + double elapsed; + + ECP_BLS24 P,G; + ECP4_BLS24 Q,W; + FP24_BLS24 g,w; + FP8_BLS24 cm; + + BIG_BLS24 s,r,x,y; + printf("\nTesting/Timing BLS24 Pairings\n"); + + ECP_BLS24_generator(&G); + + + BIG_BLS24_rcopy(r,CURVE_Order_BLS24); + BIG_BLS24_randomnum(s,r,RNG); + ECP_BLS24_copy(&P,&G); + PAIR_BLS24_G1mul(&P,r); + + if (!ECP_BLS24_isinf(&P)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_BLS24_copy(&P,&G); + PAIR_BLS24_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_BLS24_generator(&W); + + ECP4_BLS24_copy(&Q,&W); + ECP4_BLS24_mul(&Q,r); + + if (!ECP4_BLS24_isinf(&Q)) + { + printf("FAILURE - rQ!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP4_BLS24_copy(&Q,&W); + PAIR_BLS24_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_BLS24_ate(&w,&Q,&P); + PAIR_BLS24_fexp(&w); + + FP24_BLS24_copy(&g,&w); + + PAIR_BLS24_GTpow(&g,r); + + if (!FP24_BLS24_isunity(&g)) + { + printf("FAILURE - g^r!=1\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + FP24_BLS24_copy(&g,&w); + PAIR_BLS24_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_BLS24_copy(&g,&w); + + iterations=0; + start=clock(); + do { + FP24_BLS24_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_BLS24_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_BLS24_copy(&g,&w); + PAIR_BLS24_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_BLS24_copy(&P,&G); + ECP4_BLS24_copy(&Q,&W); + + PAIR_BLS24_G1mul(&P,s); + PAIR_BLS24_ate(&g,&Q,&P); + PAIR_BLS24_fexp(&g); + + ECP_BLS24_copy(&P,&G); + + PAIR_BLS24_G2mul(&Q,s); + PAIR_BLS24_ate(&w,&Q,&P); + PAIR_BLS24_fexp(&w); + + if (!FP24_BLS24_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,sP) \n"); + return 0; + } + + ECP4_BLS24_copy(&Q,&W); + PAIR_BLS24_ate(&g,&Q,&P); + PAIR_BLS24_fexp(&g); + + PAIR_BLS24_GTpow(&g,s); + + if (!FP24_BLS24_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,P)^s \n"); + return 0; + } + return 0; +} + + +int BLS_48(csprng *RNG) +{ + int i,iterations; + clock_t start; + double elapsed; + + ECP_BLS48 P,G; + ECP8_BLS48 Q,W; + FP48_BLS48 g,w; + FP16_BLS48 cm; + + BIG_BLS48 s,r,x,y; + printf("\nTesting/Timing BLS48 Pairings\n"); + + ECP_BLS48_generator(&G); + + + BIG_BLS48_rcopy(r,CURVE_Order_BLS48); + BIG_BLS48_randomnum(s,r,RNG); + ECP_BLS48_copy(&P,&G); + PAIR_BLS48_G1mul(&P,r); + + if (!ECP_BLS48_isinf(&P)) + { + printf("FAILURE - rG!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP_BLS48_copy(&P,&G); + PAIR_BLS48_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_BLS48_generator(&W); + + ECP8_BLS48_copy(&Q,&W); + ECP8_BLS48_mul(&Q,r); + + if (!ECP8_BLS48_isinf(&Q)) + { + printf("FAILURE - rQ!=O\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + ECP8_BLS48_copy(&Q,&W); + PAIR_BLS48_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_BLS48_ate(&w,&Q,&P); + PAIR_BLS48_fexp(&w); + + FP48_BLS48_copy(&g,&w); + + PAIR_BLS48_GTpow(&g,r); + + if (!FP48_BLS48_isunity(&g)) + { + printf("FAILURE - g^r!=1\n"); + return 0; + } + + iterations=0; + start=clock(); + do { + FP48_BLS48_copy(&g,&w); + PAIR_BLS48_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_BLS48_copy(&g,&w); + + iterations=0; + start=clock(); + do { + FP48_BLS48_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_BLS48_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_BLS48_copy(&g,&w); + PAIR_BLS48_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_BLS48_copy(&P,&G); + ECP8_BLS48_copy(&Q,&W); + + PAIR_BLS48_G1mul(&P,s); + PAIR_BLS48_ate(&g,&Q,&P); + PAIR_BLS48_fexp(&g); + + ECP_BLS48_copy(&P,&G); + + PAIR_BLS48_G2mul(&Q,s); + PAIR_BLS48_ate(&w,&Q,&P); + PAIR_BLS48_fexp(&w); + + if (!FP48_BLS48_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,sP) \n"); + return 0; + } + + ECP8_BLS48_copy(&Q,&W); + PAIR_BLS48_ate(&g,&Q,&P); + PAIR_BLS48_fexp(&g); + + PAIR_BLS48_GTpow(&g,s); + + if (!FP48_BLS48_equals(&g,&w)) + { + printf("FAILURE - e(sQ,p)!=e(Q,P)^s \n"); + return 0; + } + return 0; +} +#endif + +int RSA_2048(csprng *RNG) +{ + rsa_public_key_2048 pub; + rsa_private_key_2048 priv; + + int i,iterations; + clock_t start; + double elapsed; + + char m[RFS_2048],d[RFS_2048],c[RFS_2048]; + 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_2048_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_2048; + for (i=0;i<RFS_2048;i++) M.val[i]=i%128; + + iterations=0; + start=clock(); + do { + RSA_2048_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_2048_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_2048;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=4;i<10;i++) pr[i]=i; + RAND_seed(&RNG,10,pr); + + ED_25519(&RNG); +#if CHUNK==32 || CHUNK==64 + NIST_256(&RNG); + GOLD_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/c/big.c ---------------------------------------------------------------------- diff --git a/version3/c/big.c b/version3/c/big.c new file mode 100644 index 0000000..3b1a655 --- /dev/null +++ b/version3/c/big.c @@ -0,0 +1,1485 @@ +/* + 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 BIG_XXX_iszilch(BIG_XXX a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + if (a[i]!=0) return 0; + return 1; +} + +/* test a=1? */ +int BIG_XXX_isunity(BIG_XXX 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 BIG_XXX_diszilch(DBIG_XXX a) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + if (a[i]!=0) return 0; + return 1; +} + +/* SU= 56 */ +/* output a */ +void BIG_XXX_output(BIG_XXX a) +{ + BIG_XXX b; + int i,len; + len=BIG_XXX_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_XXX_copy(b,a); + BIG_XXX_shr(b,i*4); + printf("%01x",(unsigned int) b[0]&15); + } +} + +/* SU= 16 */ +void BIG_XXX_rawoutput(BIG_XXX a) +{ + int i; + printf("("); + for (i=0; i<NLEN_XXX-1; i++) +#if CHUNK==64 + printf("%"PRIxMAX",",(uintmax_t) a[i]); + printf("%"PRIxMAX")",(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 BIG_XXX_cswap(BIG_XXX a,BIG_XXX 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 BIG_XXX_cmove(BIG_XXX f,BIG_XXX 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 BIG_XXX_dcmove(DBIG_XXX f,DBIG_XXX 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 BIG_XXX_toBytes(char *b,BIG_XXX a) +{ + int i; + BIG_XXX c; + BIG_XXX_copy(c,a); + BIG_XXX_norm(c); + for (i=MODBYTES_XXX-1; i>=0; i--) + { + b[i]=c[0]&0xff; + BIG_XXX_fshr(c,8); + } +} + +/* SU= 16 */ +void BIG_XXX_fromBytes(BIG_XXX a,char *b) +{ + int i; + BIG_XXX_zero(a); + for (i=0; i<MODBYTES_XXX; i++) + { + BIG_XXX_fshl(a,8); + a[0]+=(int)(unsigned char)b[i]; + } +#ifdef DEBUG_NORM + a[MPV_XXX]=1; + a[MNV_XXX]=0; +#endif +} + +void BIG_XXX_fromBytesLen(BIG_XXX a,char *b,int s) +{ + int i,len=s; + BIG_XXX_zero(a); + + if (len>MODBYTES_XXX) len=MODBYTES_XXX; + for (i=0; i<len; i++) + { + BIG_XXX_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 BIG_XXX_doutput(DBIG_XXX a) +{ + DBIG_XXX b; + int i,len; + BIG_XXX_dnorm(a); + len=BIG_XXX_dnbits(a); + if (len%4==0) len/=4; + else + { + len/=4; + len++; + } + + for (i=len-1; i>=0; i--) + { + BIG_XXX_dcopy(b,a); + BIG_XXX_dshr(b,i*4); + printf("%01x",(unsigned int) b[0]&15); + } +} + + +void BIG_XXX_drawoutput(DBIG_XXX a) +{ + int i; + printf("("); + for (i=0; i<DNLEN_XXX-1; i++) +#if CHUNK==64 + printf("%"PRIxMAX",",(uintmax_t) a[i]); + printf("%"PRIxMAX")",(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 BIG_XXX_copy(BIG_XXX b,BIG_XXX 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 BIG_XXX_rcopy(BIG_XXX b,const BIG_XXX 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 BIG_XXX_dcopy(DBIG_XXX b,DBIG_XXX 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 BIG_XXX_dscopy(DBIG_XXX b,BIG_XXX 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 BIG_XXX_dsucopy(DBIG_XXX b,BIG_XXX 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 BIG_XXX_sdcopy(BIG_XXX b,DBIG_XXX 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 BIG_XXX_sducopy(BIG_XXX b,DBIG_XXX 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 BIG_XXX_zero(BIG_XXX 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 BIG_XXX_dzero(DBIG_XXX 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 BIG_XXX_one(BIG_XXX 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 BIG_XXX_add(BIG_XXX c,BIG_XXX a,BIG_XXX 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 */ +void BIG_XXX_or(BIG_XXX c,BIG_XXX a,BIG_XXX b) +{ + int i; + BIG_XXX_norm(a); + BIG_XXX_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 BIG_XXX_inc(BIG_XXX c,int d) +{ + BIG_XXX_norm(c); + c[0]+=(chunk)d; +#ifdef DEBUG_NORM + c[MPV_XXX]+=1; +#endif +} + +/* Set c=a-b */ +/* SU= 8 */ +void BIG_XXX_sub(BIG_XXX c,BIG_XXX a,BIG_XXX 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 BIG_XXX_dsub(DBIG_XXX c,DBIG_XXX a,DBIG_XXX 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 BIG_XXX_dadd(DBIG_XXX c,DBIG_XXX a,DBIG_XXX 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 BIG_XXX_dec(BIG_XXX c,int d) +{ + BIG_XXX_norm(c); + c[0]-=(chunk)d; +#ifdef DEBUG_NORM + c[MNV_XXX]+=1; +#endif +} + +/* multiplication r=a*c by c<=NEXCESS_XXX */ +void BIG_XXX_imul(BIG_XXX r,BIG_XXX 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 BIG_XXX_pmul(BIG_XXX r,BIG_XXX a,int c) +{ + int i; + chunk ak,carry=0; + for (i=0; i<NLEN_XXX; i++) + { + ak=a[i]; + r[i]=0; + carry=muladd_XXX(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 BIG_XXX_div3(BIG_XXX r) +{ + int i; + chunk ak,base,carry=0; + BIG_XXX_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 BIG_XXX_pxmul(DBIG_XXX c,BIG_XXX a,int b) +{ + int j; + chunk carry; + BIG_XXX_dzero(c); + carry=0; + for (j=0; j<NLEN_XXX; j++) + carry=muladd_XXX(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 BIG_XXX_smul(BIG_XXX c,BIG_XXX a,BIG_XXX b) +{ + int i,j; + chunk carry; + + BIG_XXX_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_XXX(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 BIG_XXX_mul(DBIG_XXX c,BIG_XXX a,BIG_XXX 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_XXX_dzero(c); + for (i=0; i<NLEN_XXX; i++) + { + carry=0; + for (j=0; j<NLEN_XXX; j++) + carry=muladd_XXX(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 BIG_XXX_sqr(DBIG_XXX c,BIG_XXX a) +{ + int i,j; +#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_XXX_dzero(c); + for (i=0; i<NLEN_XXX; i++) + { + carry=0; + for (j=i+1; j<NLEN_XXX; j++) + carry=muladd_XXX(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_XXX(a[i],a[i],0,&c[2*i]); + + BIG_XXX_dnorm(c); +#endif + + +#ifdef DEBUG_NORM + c[DMPV_XXX]=1; + c[DMNV_XXX]=0; +#endif + +} + +/* Montgomery reduction */ +void BIG_XXX_monty(BIG_XXX a,BIG_XXX md,chunk MC,DBIG_XXX 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_XXX(m,md[j],carry,&d[i+j]); + d[NLEN_XXX+i]+=carry; + } + BIG_XXX_sducopy(a,d); + BIG_XXX_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 BIG_XXX_shl(BIG_XXX 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 BIG_XXX_fshl(BIG_XXX 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 , a MUST be normalised */ +/* SU= 32 */ +void BIG_XXX_dshl(DBIG_XXX 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 right of a by k bits */ +/* a MUST be normalised */ +/* SU= 32 */ +void BIG_XXX_shr(BIG_XXX 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 BIG_XXX_ssn(BIG_XXX r,BIG_XXX a,BIG_XXX 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 BIG_XXX_fshr(BIG_XXX 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 */ +/* SU= 32 */ +void BIG_XXX_dshr(DBIG_XXX 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 word */ +/* d MUST be normalised */ +/* SU= 24 */ +chunk BIG_XXX_split(BIG_XXX t,BIG_XXX b,DBIG_XXX 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 */ +chunk BIG_XXX_norm(BIG_XXX 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 BIG_XXX_dnorm(DBIG_XXX 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 BIG_XXX_comp(BIG_XXX a,BIG_XXX 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 BIG_XXX_dcomp(DBIG_XXX a,DBIG_XXX 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 BIG_XXX_nbits(BIG_XXX a) +{ + int bts,k=NLEN_XXX-1; + BIG_XXX t; + chunk c; + BIG_XXX_copy(t,a); + BIG_XXX_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 BIG_XXX_dnbits(DBIG_XXX a) +{ + int bts,k=DNLEN_XXX-1; + DBIG_XXX t; + chunk c; + BIG_XXX_dcopy(t,a); + BIG_XXX_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 BIG_XXX_mod(BIG_XXX b,BIG_XXX c1) +{ + int k=0; + BIG_XXX r; /**/ + BIG_XXX c; + BIG_XXX_copy(c,c1); + + BIG_XXX_norm(b); + if (BIG_XXX_comp(b,c)<0) + return; + do + { + BIG_XXX_fshl(c,1); + k++; + } + while (BIG_XXX_comp(b,c)>=0); + + while (k>0) + { + BIG_XXX_fshr(c,1); + +// constant time... + BIG_XXX_sub(r,b,c); + BIG_XXX_norm(r); + BIG_XXX_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 BIG_XXX_dmod(BIG_XXX a,DBIG_XXX b,BIG_XXX c) +{ + int k=0; + DBIG_XXX m,r; + BIG_XXX_dnorm(b); + BIG_XXX_dscopy(m,c); + + if (BIG_XXX_dcomp(b,m)<0) + { + BIG_XXX_sdcopy(a,b); + return; + } + + do + { + BIG_XXX_dshl(m,1); + k++; + } + while (BIG_XXX_dcomp(b,m)>=0); + + while (k>0) + { + BIG_XXX_dshr(m,1); +// constant time... + BIG_XXX_dsub(r,b,m); + BIG_XXX_dnorm(r); + BIG_XXX_dcmove(b,r,1-((r[DNLEN_XXX-1]>>(CHUNK-1))&1)); + + k--; + } + BIG_XXX_sdcopy(a,b); +} + +/* Set a=b/c, b is destroyed. Slow but rarely used. */ +/* SU= 136 */ + +void BIG_XXX_ddiv(BIG_XXX a,DBIG_XXX b,BIG_XXX c) +{ + int d,k=0; + DBIG_XXX m,dr; + BIG_XXX e,r; + BIG_XXX_dnorm(b); + BIG_XXX_dscopy(m,c); + + BIG_XXX_zero(a); + BIG_XXX_zero(e); + BIG_XXX_inc(e,1); + + while (BIG_XXX_dcomp(b,m)>=0) + { + BIG_XXX_fshl(e,1); + BIG_XXX_dshl(m,1); + k++; + } + + while (k>0) + { + BIG_XXX_dshr(m,1); + BIG_XXX_fshr(e,1); + + BIG_XXX_dsub(dr,b,m); + BIG_XXX_dnorm(dr); + d=1-((dr[DNLEN_XXX-1]>>(CHUNK-1))&1); + BIG_XXX_dcmove(b,dr,d); + + BIG_XXX_add(r,a,e); + BIG_XXX_norm(r); + BIG_XXX_cmove(a,r,d); + + k--; + } +} + +/* SU= 136 */ + +void BIG_XXX_sdiv(BIG_XXX a,BIG_XXX c) +{ + int d,k=0; + BIG_XXX m,e,b,r; + BIG_XXX_norm(a); + BIG_XXX_copy(b,a); + BIG_XXX_copy(m,c); + + BIG_XXX_zero(a); + BIG_XXX_zero(e); + BIG_XXX_inc(e,1); + + while (BIG_XXX_comp(b,m)>=0) + { + BIG_XXX_fshl(e,1); + BIG_XXX_fshl(m,1); + k++; + } + + while (k>0) + { + BIG_XXX_fshr(m,1); + BIG_XXX_fshr(e,1); + + BIG_XXX_sub(r,b,m); + BIG_XXX_norm(r); + d=1-((r[NLEN_XXX-1]>>(CHUNK-1))&1); + BIG_XXX_cmove(b,r,d); + + BIG_XXX_add(r,a,e); + BIG_XXX_norm(r); + BIG_XXX_cmove(a,r,d); + k--; + } +} + +/* return LSB of a */ +int BIG_XXX_parity(BIG_XXX a) +{ + return a[0]%2; +} + +/* return n-th bit of a */ +/* SU= 16 */ +int BIG_XXX_bit(BIG_XXX 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 */ +/* SU= 16 */ +int BIG_XXX_lastbits(BIG_XXX a,int n) +{ + int msk=(1<<n)-1; + BIG_XXX_norm(a); + return ((int)a[0])&msk; +} + +/* get 8*MODBYTES size random number */ +void BIG_XXX_random(BIG_XXX m,csprng *rng) +{ + int i,b,j=0,r=0; + int len=8*MODBYTES_XXX; + + BIG_XXX_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_XXX_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 BIG_XXX_randomnum(BIG_XXX m,BIG_XXX q,csprng *rng) +{ + int i,b,j=0,r=0; + DBIG_XXX d; + BIG_XXX_dzero(d); + /* generate random DBIG */ + for (i=0; i<2*BIG_XXX_nbits(q); i++) + { + if (j==0) r=RAND_byte(rng); + else r>>=1; + b=r&1; + BIG_XXX_dshl(d,1); + d[0]+=b; + j++; + j&=7; + } + /* reduce modulo a BIG. Removes bias */ + BIG_XXX_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 BIG_XXX_modmul(BIG_XXX r,BIG_XXX a1,BIG_XXX b1,BIG_XXX m) +{ + DBIG_XXX d; + BIG_XXX a,b; + BIG_XXX_copy(a,a1); + BIG_XXX_copy(b,b1); + BIG_XXX_mod(a,m); + BIG_XXX_mod(b,m); + + BIG_XXX_mul(d,a,b); + BIG_XXX_dmod(r,d,m); +} + +/* Set a=a*a mod m */ +/* SU= 88 */ +void BIG_XXX_modsqr(BIG_XXX r,BIG_XXX a1,BIG_XXX m) +{ + DBIG_XXX d; + BIG_XXX a; + BIG_XXX_copy(a,a1); + BIG_XXX_mod(a,m); + BIG_XXX_sqr(d,a); + BIG_XXX_dmod(r,d,m); +} + +/* Set r=-a mod m */ +/* SU= 16 */ +void BIG_XXX_modneg(BIG_XXX r,BIG_XXX a1,BIG_XXX m) +{ + BIG_XXX a; + BIG_XXX_copy(a,a1); + BIG_XXX_mod(a,m); + BIG_XXX_sub(r,m,a); +} + +/* Set a=a/b mod m */ +/* SU= 136 */ +void BIG_XXX_moddiv(BIG_XXX r,BIG_XXX a1,BIG_XXX b1,BIG_XXX m) +{ + DBIG_XXX d; + BIG_XXX z; + BIG_XXX a,b; + BIG_XXX_copy(a,a1); + BIG_XXX_copy(b,b1); + + BIG_XXX_mod(a,m); + BIG_XXX_invmodp(z,b,m); + + BIG_XXX_mul(d,a,z); + BIG_XXX_dmod(r,d,m); +} + +/* Get jacobi Symbol (a/p). Returns 0, 1 or -1 */ +/* SU= 216 */ +int BIG_XXX_jacobi(BIG_XXX a,BIG_XXX p) +{ + int n8,k,m=0; + BIG_XXX t,x,n,zilch,one; + BIG_XXX_one(one); + BIG_XXX_zero(zilch); + if (BIG_XXX_parity(p)==0 || BIG_XXX_comp(a,zilch)==0 || BIG_XXX_comp(p,one)<=0) return 0; + BIG_XXX_norm(a); + BIG_XXX_copy(x,a); + BIG_XXX_copy(n,p); + BIG_XXX_mod(x,p); + + while (BIG_XXX_comp(n,one)>0) + { + if (BIG_XXX_comp(x,zilch)==0) return 0; + n8=BIG_XXX_lastbits(n,3); + k=0; + while (BIG_XXX_parity(x)==0) + { + k++; + BIG_XXX_shr(x,1); + } + if (k%2==1) m+=(n8*n8-1)/8; + m+=(n8-1)*(BIG_XXX_lastbits(x,2)-1)/4; + BIG_XXX_copy(t,n); + + BIG_XXX_mod(t,x); + BIG_XXX_copy(n,x); + BIG_XXX_copy(x,t); + m%=2; + + } + if (m==0) return 1; + else return -1; +} + +/* Set r=1/a mod p. Binary method */ +/* SU= 240 */ +void BIG_XXX_invmodp(BIG_XXX r,BIG_XXX a,BIG_XXX p) +{ + BIG_XXX u,v,x1,x2,t,one; + BIG_XXX_mod(a,p); + BIG_XXX_copy(u,a); + BIG_XXX_copy(v,p); + BIG_XXX_one(one); + BIG_XXX_copy(x1,one); + BIG_XXX_zero(x2); + + while (BIG_XXX_comp(u,one)!=0 && BIG_XXX_comp(v,one)!=0) + { + while (BIG_XXX_parity(u)==0) + { + BIG_XXX_fshr(u,1); + if (BIG_XXX_parity(x1)!=0) + { + BIG_XXX_add(x1,p,x1); + BIG_XXX_norm(x1); + } + BIG_XXX_fshr(x1,1); + } + while (BIG_XXX_parity(v)==0) + { + BIG_XXX_fshr(v,1); + if (BIG_XXX_parity(x2)!=0) + { + BIG_XXX_add(x2,p,x2); + BIG_XXX_norm(x2); + } + BIG_XXX_fshr(x2,1); + } + if (BIG_XXX_comp(u,v)>=0) + { + BIG_XXX_sub(u,u,v); + BIG_XXX_norm(u); + if (BIG_XXX_comp(x1,x2)>=0) BIG_XXX_sub(x1,x1,x2); + else + { + BIG_XXX_sub(t,p,x2); + BIG_XXX_add(x1,x1,t); + } + BIG_XXX_norm(x1); + } + else + { + BIG_XXX_sub(v,v,u); + BIG_XXX_norm(v); + if (BIG_XXX_comp(x2,x1)>=0) BIG_XXX_sub(x2,x2,x1); + else + { + BIG_XXX_sub(t,p,x1); + BIG_XXX_add(x2,x2,t); + } + BIG_XXX_norm(x2); + } + } + if (BIG_XXX_comp(u,one)==0) + BIG_XXX_copy(r,x1); + else + BIG_XXX_copy(r,x2); +} + +/* set x = x mod 2^m */ +void BIG_XXX_mod2m(BIG_XXX x,int m) +{ + int i,wd,bt; + chunk msk; + BIG_XXX_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 BIG_XXX_dfromBytesLen(DBIG_XXX a,char *b,int s) +{ + int i,len=s; + BIG_XXX_dzero(a); + + for (i=0; i<len; i++) + { + BIG_XXX_dshl(a,8); + a[0]+=(int)(unsigned char)b[i]; + } +#ifdef DEBUG_NORM + a[DMPV_XXX]=1; + a[DMNV_XXX]=0; +#endif +} http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/big.h ---------------------------------------------------------------------- diff --git a/version3/c/big.h b/version3/c/big.h new file mode 100644 index 0000000..36b0c7c --- /dev/null +++ b/version3/c/big.h @@ -0,0 +1,610 @@ +/* + 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. +*/ + +/** + * @file big.h + * @author Mike Scott + * @brief BIG Header File + * + */ + +#ifndef BIG_XXX_H +#define BIG_XXX_H + +#include <stdio.h> +#include <stdlib.h> +#include <inttypes.h> +#include "arch.h" +#include "amcl.h" +#include "config_big_XXX.h" + +//#define UNWOUND + +#define BIGBITS_XXX (8*MODBYTES_XXX) /**< Length in bits */ +#define NLEN_XXX (1+((8*MODBYTES_XXX-1)/BASEBITS_XXX)) /**< length in bytes */ +#define DNLEN_XXX 2*NLEN_XXX /**< Double length in bytes */ +#define BMASK_XXX (((chunk)1<<BASEBITS_XXX)-1) /**< Mask = 2^BASEBITS-1 */ +#define NEXCESS_XXX (1<<(CHUNK-BASEBITS_XXX-1)) /**< 2^(CHUNK-BASEBITS-1) - digit cannot be multiplied by more than this before normalisation */ + +#define HBITS_XXX (BASEBITS_XXX/2) /**< Number of bits in number base divided by 2 */ +#define HMASK_XXX (((chunk)1<<HBITS_XXX)-1) /**< Mask = 2^HBITS-1 */ + +//#define DEBUG_NORM + +#ifdef DEBUG_NORM /* Add an extra location to track chunk extension */ +#define MPV_XXX NLEN_XXX +#define MNV_XXX (NLEN_XXX+1) +typedef chunk BIG_XXX[NLEN_XXX+2]; /**< Define type BIG as array of chunks */ +#define DMPV_XXX DNLEN_XXX +#define DMNV_XXX (DNLEN_XXX+1) +typedef chunk DBIG_XXX[DNLEN_XXX+2]; /**< Define type DBIG as array of chunks */ +#else +typedef chunk BIG_XXX[NLEN_XXX]; /**< Define type BIG as array of chunks */ +typedef chunk DBIG_XXX[DNLEN_XXX]; /**< Define type DBIG as array of chunks */ +#endif + +/* BIG number prototypes */ + +/** @brief Tests for BIG equal to zero + * + @param x a BIG number + @return 1 if zero, else returns 0 + */ +extern int BIG_XXX_iszilch(BIG_XXX x); +/** @brief Tests for BIG equal to one + * + @param x a BIG number + @return 1 if one, else returns 0 + */ +extern int BIG_XXX_isunity(BIG_XXX x); +/** @brief Tests for DBIG equal to zero + * + @param x a DBIG number + @return 1 if zero, else returns 0 + */ +extern int BIG_XXX_diszilch(DBIG_XXX x); +/** @brief Outputs a BIG number to the console + * + @param x a BIG number + */ +extern void BIG_XXX_output(BIG_XXX x); +/** @brief Outputs a BIG number to the console in raw form (for debugging) + * + @param x a BIG number + */ +extern void BIG_XXX_rawoutput(BIG_XXX x); +/** @brief Conditional constant time swap of two BIG numbers + * + Conditionally swaps parameters in constant time (without branching) + @param x a BIG number + @param y another BIG number + @param s swap takes place if not equal to 0 + */ +extern void BIG_XXX_cswap(BIG_XXX x,BIG_XXX y,int s); +/** @brief Conditional copy of BIG number + * + Conditionally copies second parameter to the first (without branching) + @param x a BIG number + @param y another BIG number + @param s copy takes place if not equal to 0 + */ +extern void BIG_XXX_cmove(BIG_XXX x,BIG_XXX y,int s); +/** @brief Conditional copy of DBIG number + * + Conditionally copies second parameter to the first (without branching) + @param x a DBIG number + @param y another DBIG number + @param s copy takes place if not equal to 0 + */ +extern void BIG_XXX_dcmove(BIG_XXX x,BIG_XXX y,int s); +/** @brief Convert from BIG number to byte array + * + @param a byte array + @param x BIG number + */ +extern void BIG_XXX_toBytes(char *a,BIG_XXX x); +/** @brief Convert to BIG number from byte array + * + @param x BIG number + @param a byte array + */ +extern void BIG_XXX_fromBytes(BIG_XXX x,char *a); +/** @brief Convert to BIG number from byte array of given length + * + @param x BIG number + @param a byte array + @param s byte array length + */ +extern void BIG_XXX_fromBytesLen(BIG_XXX x,char *a,int s); +/**@brief Convert to DBIG number from byte array of given length + * + @param x DBIG number + @param a byte array + @param s byte array length + */ +extern void BIG_XXX_dfromBytesLen(DBIG_XXX x,char *a,int s); +/** @brief Outputs a DBIG number to the console + * + @param x a DBIG number + */ +extern void BIG_XXX_doutput(DBIG_XXX x); + +/** @brief Outputs a DBIG number to the console + * + @param x a DBIG number + */ +extern void BIG_XXX_drawoutput(DBIG_XXX x); + +/** @brief Copy BIG from Read-Only Memory to a BIG + * + @param x BIG number + @param y BIG number in ROM + */ +extern void BIG_XXX_rcopy(BIG_XXX x,const BIG_XXX y); +/** @brief Copy BIG to another BIG + * + @param x BIG number + @param y BIG number to be copied + */ +extern void BIG_XXX_copy(BIG_XXX x,BIG_XXX y); +/** @brief Copy DBIG to another DBIG + * + @param x DBIG number + @param y DBIG number to be copied + */ +extern void BIG_XXX_dcopy(DBIG_XXX x,DBIG_XXX y); +/** @brief Copy BIG to upper half of DBIG + * + @param x DBIG number + @param y BIG number to be copied + */ +extern void BIG_XXX_dsucopy(DBIG_XXX x,BIG_XXX y); +/** @brief Copy BIG to lower half of DBIG + * + @param x DBIG number + @param y BIG number to be copied + */ +extern void BIG_XXX_dscopy(DBIG_XXX x,BIG_XXX y); +/** @brief Copy lower half of DBIG to a BIG + * + @param x BIG number + @param y DBIG number to be copied + */ +extern void BIG_XXX_sdcopy(BIG_XXX x,DBIG_XXX y); +/** @brief Copy upper half of DBIG to a BIG + * + @param x BIG number + @param y DBIG number to be copied + */ +extern void BIG_XXX_sducopy(BIG_XXX x,DBIG_XXX y); +/** @brief Set BIG to zero + * + @param x BIG number to be set to zero + */ +extern void BIG_XXX_zero(BIG_XXX x); +/** @brief Set DBIG to zero + * + @param x DBIG number to be set to zero + */ +extern void BIG_XXX_dzero(DBIG_XXX x); +/** @brief Set BIG to one (unity) + * + @param x BIG number to be set to one. + */ +extern void BIG_XXX_one(BIG_XXX x); +/** @brief Set BIG to inverse mod 2^256 + * + @param x BIG number to be inverted + */ +extern void BIG_XXX_invmod2m(BIG_XXX x); +/** @brief Set BIG to sum of two BIGs - output not normalised + * + @param x BIG number, sum of other two + @param y BIG number + @param z BIG number + */ +extern void BIG_XXX_add(BIG_XXX x,BIG_XXX y,BIG_XXX z); + +/** @brief Set BIG to logical or of two BIGs - output normalised + * + @param x BIG number, or of other two + @param y BIG number + @param z BIG number + */ +extern void BIG_XXX_or(BIG_XXX x,BIG_XXX y,BIG_XXX z); + +/** @brief Increment BIG by a small integer - output not normalised + * + @param x BIG number to be incremented + @param i integer + */ +extern void BIG_XXX_inc(BIG_XXX x,int i); +/** @brief Set BIG to difference of two BIGs + * + @param x BIG number, difference of other two - output not normalised + @param y BIG number + @param z BIG number + */ +extern void BIG_XXX_sub(BIG_XXX x,BIG_XXX y,BIG_XXX z); +/** @brief Decrement BIG by a small integer - output not normalised + * + @param x BIG number to be decremented + @param i integer + */ +extern void BIG_XXX_dec(BIG_XXX x,int i); +/** @brief Set DBIG to sum of two DBIGs + * + @param x DBIG number, sum of other two - output not normalised + @param y DBIG number + @param z DBIG number + */ +extern void BIG_XXX_dadd(DBIG_XXX x,DBIG_XXX y,DBIG_XXX z); +/** @brief Set DBIG to difference of two DBIGs + * + @param x DBIG number, difference of other two - output not normalised + @param y DBIG number + @param z DBIG number + */ +extern void BIG_XXX_dsub(DBIG_XXX x,DBIG_XXX y,DBIG_XXX z); +/** @brief Multiply BIG by a small integer - output not normalised + * + @param x BIG number, product of other two + @param y BIG number + @param i small integer + */ +extern void BIG_XXX_imul(BIG_XXX x,BIG_XXX y,int i); +/** @brief Multiply BIG by not-so-small small integer - output normalised + * + @param x BIG number, product of other two + @param y BIG number + @param i small integer + @return Overflowing bits + */ +extern chunk BIG_XXX_pmul(BIG_XXX x,BIG_XXX y,int i); +/** @brief Divide BIG by 3 - output normalised + * + @param x BIG number + @return Remainder + */ +extern int BIG_XXX_div3(BIG_XXX x); +/** @brief Multiply BIG by even bigger small integer resulting in a DBIG - output normalised + * + @param x DBIG number, product of other two + @param y BIG number + @param i small integer + */ +extern void BIG_XXX_pxmul(DBIG_XXX x,BIG_XXX y,int i); +/** @brief Multiply BIG by another BIG resulting in DBIG - inputs normalised and output normalised + * + @param x DBIG number, product of other two + @param y BIG number + @param z BIG number + */ +extern void BIG_XXX_mul(DBIG_XXX x,BIG_XXX y,BIG_XXX z); +/** @brief Multiply BIG by another BIG resulting in another BIG - inputs normalised and output normalised + * + Note that the product must fit into a BIG, and x must be distinct from y and z + @param x BIG number, product of other two + @param y BIG number + @param z BIG number + */ +extern void BIG_XXX_smul(BIG_XXX x,BIG_XXX y,BIG_XXX z); +/** @brief Square BIG resulting in a DBIG - input normalised and output normalised + * + @param x DBIG number, square of a BIG + @param y BIG number to be squared + */ +extern void BIG_XXX_sqr(DBIG_XXX x,BIG_XXX y); + +/** @brief Montgomery reduction of a DBIG to a BIG - input normalised and output normalised + * + @param a BIG number, reduction of a BIG + @param md BIG number, the modulus + @param MC the Montgomery Constant + @param d DBIG number to be reduced + */ +extern void BIG_XXX_monty(BIG_XXX a,BIG_XXX md,chunk MC,DBIG_XXX d); + +/** @brief Shifts a BIG left by any number of bits - input must be normalised, output normalised + * + @param x BIG number to be shifted + @param s Number of bits to shift + */ +extern void BIG_XXX_shl(BIG_XXX x,int s); +/** @brief Fast shifts a BIG left by a small number of bits - input must be normalised, output will be normalised + * + The number of bits to be shifted must be less than BASEBITS + @param x BIG number to be shifted + @param s Number of bits to shift + @return Overflow bits + */ +extern int BIG_XXX_fshl(BIG_XXX x,int s); +/** @brief Shifts a DBIG left by any number of bits - input must be normalised, output normalised + * + @param x DBIG number to be shifted + @param s Number of bits to shift + */ +extern void BIG_XXX_dshl(DBIG_XXX x,int s); +/** @brief Shifts a BIG right by any number of bits - input must be normalised, output normalised + * + @param x BIG number to be shifted + @param s Number of bits to shift + */ +extern void BIG_XXX_shr(BIG_XXX x,int s); + +/** @brief Fast time-critical combined shift by 1 bit, subtract and normalise + * + @param r BIG number normalised output + @param a BIG number to be subtracted from + @param m BIG number to be shifted and subtracted + @return sign of r + */ +extern int BIG_XXX_ssn(BIG_XXX r,BIG_XXX a, BIG_XXX m); + +/** @brief Fast shifts a BIG right by a small number of bits - input must be normalised, output will be normalised + * + The number of bits to be shifted must be less than BASEBITS + @param x BIG number to be shifted + @param s Number of bits to shift + @return Shifted out bits + */ +extern int BIG_XXX_fshr(BIG_XXX x,int s); +/** @brief Shifts a DBIG right by any number of bits - input must be normalised, output normalised + * + @param x DBIG number to be shifted + @param s Number of bits to shift + */ +extern void BIG_XXX_dshr(DBIG_XXX x,int s); +/** @brief Splits a DBIG into two BIGs - input must be normalised, outputs normalised + * + Internal function. The value of s must be approximately in the middle of the DBIG. + Typically used to extract z mod 2^MODBITS and z/2^MODBITS + @param x BIG number, top half of z + @param y BIG number, bottom half of z + @param z DBIG number to be split in two. + @param s Bit position at which to split + @return carry-out from top half + */ +extern chunk BIG_XXX_split(BIG_XXX x,BIG_XXX y,DBIG_XXX z,int s); +/** @brief Normalizes a BIG number - output normalised + * + All digits of the input BIG are reduced mod 2^BASEBITS + @param x BIG number to be normalised + */ +extern chunk BIG_XXX_norm(BIG_XXX x); +/** @brief Normalizes a DBIG number - output normalised + * + All digits of the input DBIG are reduced mod 2^BASEBITS + @param x DBIG number to be normalised + */ +extern void BIG_XXX_dnorm(DBIG_XXX x); +/** @brief Compares two BIG numbers. Inputs must be normalised externally + * + @param x first BIG number to be compared + @param y second BIG number to be compared + @return -1 is x<y, 0 if x=y, 1 if x>y + */ +extern int BIG_XXX_comp(BIG_XXX x,BIG_XXX y); +/** @brief Compares two DBIG numbers. Inputs must be normalised externally + * + @param x first DBIG number to be compared + @param y second DBIG number to be compared + @return -1 is x<y, 0 if x=y, 1 if x>y + */ +extern int BIG_XXX_dcomp(DBIG_XXX x,DBIG_XXX y); +/** @brief Calculate number of bits in a BIG - output normalised + * + @param x BIG number + @return Number of bits in x + */ +extern int BIG_XXX_nbits(BIG_XXX x); +/** @brief Calculate number of bits in a DBIG - output normalised + * + @param x DBIG number + @return Number of bits in x + */ +extern int BIG_XXX_dnbits(DBIG_XXX x); +/** @brief Reduce x mod n - input and output normalised + * + Slow but rarely used + @param x BIG number to be reduced mod n + @param n The modulus + */ +extern void BIG_XXX_mod(BIG_XXX x,BIG_XXX n); +/** @brief Divide x by n - output normalised + * + Slow but rarely used + @param x BIG number to be divided by n + @param n The Divisor + */ +extern void BIG_XXX_sdiv(BIG_XXX x,BIG_XXX n); +/** @brief x=y mod n - output normalised + * + Slow but rarely used. y is destroyed. + @param x BIG number, on exit = y mod n + @param y DBIG number + @param n Modulus + */ +extern void BIG_XXX_dmod(BIG_XXX x,DBIG_XXX y,BIG_XXX n); +/** @brief x=y/n - output normalised + * + Slow but rarely used. y is destroyed. + @param x BIG number, on exit = y/n + @param y DBIG number + @param n Modulus + */ +extern void BIG_XXX_ddiv(BIG_XXX x,DBIG_XXX y,BIG_XXX n); +/** @brief return parity of BIG, that is the least significant bit + * + @param x BIG number + @return 0 or 1 + */ +extern int BIG_XXX_parity(BIG_XXX x); +/** @brief return i-th of BIG + * + @param x BIG number + @param i the bit of x to be returned + @return 0 or 1 + */ +extern int BIG_XXX_bit(BIG_XXX x,int i); +/** @brief return least significant bits of a BIG + * + @param x BIG number + @param n number of bits to return. Assumed to be less than BASEBITS. + @return least significant n bits as an integer + */ +extern int BIG_XXX_lastbits(BIG_XXX x,int n); +/** @brief Create a random BIG from a random number generator + * + Assumes that the random number generator has been suitably initialised + @param x BIG number, on exit a random number + @param r A pointer to a Cryptographically Secure Random Number Generator + */ +extern void BIG_XXX_random(BIG_XXX x,csprng *r); +/** @brief Create an unbiased random BIG from a random number generator, reduced with respect to a modulus + * + Assumes that the random number generator has been suitably initialised + @param x BIG number, on exit a random number + @param n The modulus + @param r A pointer to a Cryptographically Secure Random Number Generator + */ +extern void BIG_XXX_randomnum(BIG_XXX x,BIG_XXX n,csprng *r); +/** brief return NAF (Non-Adjacent-Form) value as +/- 1, 3 or 5, inputs must be normalised + * + Given x and 3*x extracts NAF value from given bit position, and returns number of bits processed, and number of trailing zeros detected if any + param x BIG number + param x3 BIG number, three times x + param i bit position + param nbs pointer to integer returning number of bits processed + param nzs pointer to integer returning number of trailing 0s + return + or - 1, 3 or 5 +*/ + +/** @brief Calculate x=y*z mod n + * + Slow method for modular multiplication + @param x BIG number, on exit = y*z mod n + @param y BIG number + @param z BIG number + @param n The BIG Modulus + */ +extern void BIG_XXX_modmul(BIG_XXX x,BIG_XXX y,BIG_XXX z,BIG_XXX n); +/** @brief Calculate x=y/z mod n + * + Slow method for modular division + @param x BIG number, on exit = y/z mod n + @param y BIG number + @param z BIG number + @param n The BIG Modulus + */ +extern void BIG_XXX_moddiv(BIG_XXX x,BIG_XXX y,BIG_XXX z,BIG_XXX n); +/** @brief Calculate x=y^2 mod n + * + Slow method for modular squaring + @param x BIG number, on exit = y^2 mod n + @param y BIG number + @param n The BIG Modulus + */ +extern void BIG_XXX_modsqr(BIG_XXX x,BIG_XXX y,BIG_XXX n); +/** @brief Calculate x=-y mod n + * + Modular negation + @param x BIG number, on exit = -y mod n + @param y BIG number + @param n The BIG Modulus + */ +extern void BIG_XXX_modneg(BIG_XXX x,BIG_XXX y,BIG_XXX n); +/** @brief Calculate jacobi Symbol (x/y) + * + @param x BIG number + @param y BIG number + @return Jacobi symbol, -1,0 or 1 + */ +extern int BIG_XXX_jacobi(BIG_XXX x,BIG_XXX y); +/** @brief Calculate x=1/y mod n + * + Modular Inversion - This is slow. Uses binary method. + @param x BIG number, on exit = 1/y mod n + @param y BIG number + @param n The BIG Modulus + */ +extern void BIG_XXX_invmodp(BIG_XXX x,BIG_XXX y,BIG_XXX n); +/** @brief Calculate x=x mod 2^m + * + Truncation + @param x BIG number, on reduced mod 2^m + @param m new truncated size +*/ +extern void BIG_XXX_mod2m(BIG_XXX x,int m); + +/** @brief Calculates a*b+c+*d + * + Calculate partial product of a.b, add in carry c, and add total to d + @param x multiplier + @param y multiplicand + @param c carry + @param r pointer to accumulated bottom half of result + @return top half of result + */ + +#ifdef dchunk + +/* Method required to calculate x*y+c+r, bottom half in r, top half returned */ +static inline chunk muladd_XXX(chunk x,chunk y,chunk c,chunk *r) +{ + dchunk prod=(dchunk)x*y+c+*r; + *r=(chunk)prod&BMASK_XXX; + return (chunk)(prod>>BASEBITS_XXX); +} + +#else + +/* No integer type available that can store double the wordlength */ +/* accumulate partial products */ + +static inline chunk muladd_XXX(chunk x,chunk y,chunk c,chunk *r) +{ + chunk x0,x1,y0,y1; + chunk bot,top,mid,carry; + x0=x&HMASK_XXX; + x1=(x>>HBITS_XXX); + y0=y&HMASK_XXX; + y1=(y>>HBITS_XXX); + bot=x0*y0; + top=x1*y1; + mid=x0*y1+x1*y0; + x0=mid&HMASK_XXX; + x1=(mid>>HBITS_XXX); + bot+=x0<<HBITS_XXX; + bot+=*r; + bot+=c; + + top+=x1; + carry=bot>>BASEBITS_XXX; + bot&=BMASK_XXX; + top+=carry; + + *r=bot; + return top; +} + +#endif + + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/bls.c ---------------------------------------------------------------------- diff --git a/version3/c/bls.c b/version3/c/bls.c new file mode 100644 index 0000000..6706316 --- /dev/null +++ b/version3/c/bls.c @@ -0,0 +1,89 @@ +/* +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. +*/ + +/* Boneh-Lynn-Shacham signature 128-bit API */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include "bls_ZZZ.h" + +/* hash a message to an ECP point, using SHA3 */ + +static void BLS_HASHIT(ECP_ZZZ *P,char *m) +{ + int i; + sha3 hs; + char h[MODBYTES_XXX]; + octet HM= {0,sizeof(h),h}; + SHA3_init(&hs,SHAKE256); + for (i=0;m[i]!=0;i++) SHA3_process(&hs,m[i]); + SHA3_shake(&hs,HM.val,MODBYTES_XXX); + HM.len=MODBYTES_XXX; + ECP_ZZZ_mapit(P,&HM); +} + +/* generate key pair, private key S, public key W */ + +int BLS_ZZZ_KEY_PAIR_GENERATE(csprng *RNG,octet* S,octet *W) +{ + ECP2_ZZZ G; + BIG_XXX s,q; + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + ECP2_ZZZ_generator(&G); + BIG_XXX_randomnum(s,q,RNG); + BIG_XXX_toBytes(S->val,s); + S->len=MODBYTES_XXX; + PAIR_ZZZ_G2mul(&G,s); + ECP2_ZZZ_toOctet(W,&G); + return BLS_OK; +} + +/* Sign message m using private key S to produce signature SIG */ + +int BLS_ZZZ_SIGN(octet *SIG,char *m,octet *S) +{ + BIG_XXX s; + ECP_ZZZ D; + BLS_HASHIT(&D,m); + BIG_XXX_fromBytes(s,S->val); + PAIR_ZZZ_G1mul(&D,s); + ECP_ZZZ_toOctet(SIG,&D,true); /* compress output */ + return BLS_OK; +} + +/* Verify signature of message m, the signature SIG, and the public key W */ + +int BLS_ZZZ_VERIFY(octet *SIG,char *m,octet *W) +{ + FP12_YYY v; + ECP2_ZZZ G,PK; + ECP_ZZZ D,HM; + BLS_HASHIT(&HM,m); + ECP_ZZZ_fromOctet(&D,SIG); + ECP2_ZZZ_generator(&G); + ECP2_ZZZ_fromOctet(&PK,W); + ECP_ZZZ_neg(&D); + PAIR_ZZZ_double_ate(&v,&G,&D,&PK,&HM); + PAIR_ZZZ_fexp(&v); + if (FP12_YYY_isunity(&v)) return BLS_OK; + return BLS_FAIL; +} + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/bls.h ---------------------------------------------------------------------- diff --git a/version3/c/bls.h b/version3/c/bls.h new file mode 100644 index 0000000..9b6ab29 --- /dev/null +++ b/version3/c/bls.h @@ -0,0 +1,75 @@ +/* +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. +*/ + +/** + * @file bls.h + * @author Mike Scott + * @date 28th Novemebr 2018 + * @brief BLS Header file + * + * Allows some user configuration + * defines structures + * declares functions + * + */ + +#ifndef BLS_ZZZ_H +#define BLS_ZZZ_H + +#include "pair_ZZZ.h" + +/* Field size is assumed to be greater than or equal to group size */ + +#define BGS_ZZZ MODBYTES_XXX /**< BLS Group Size */ +#define BFS_ZZZ MODBYTES_XXX /**< BLS Field Size */ + +#define BLS_OK 0 /**< Function completed without error */ +#define BLS_FAIL -1 /**< Point is NOT on the curve */ + +/* BLS API functions */ + +/** @brief Generate Key Pair + * + @param RNG is a pointer to a cryptographically secure random number generator + @param S on output a private key + @param V on output a private key = S*G, where G is fixed generator + @return BLS_OK + */ +int BLS_ZZZ_KEY_PAIR_GENERATE(csprng *RNG,octet* S,octet *W); + +/** @brief Calculate a signature + * + @param SIG the ouput signature + @param m is the message to be signed + @param S an input private key + @return BLS_OK + */ +int BLS_ZZZ_SIGN(octet *SIG,char *m,octet *S); + +/** @brief Verify a signature + * + @param SIG an input signature + @param m is the message whose signature is to be verified. + @param W an public key + @return BLS_OK if verified, otherwise BLS_FAIL + */ +int BLS_ZZZ_VERIFY(octet *SIG,char *m,octet *W); + +#endif + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/bls192.c ---------------------------------------------------------------------- diff --git a/version3/c/bls192.c b/version3/c/bls192.c new file mode 100644 index 0000000..5eb8852 --- /dev/null +++ b/version3/c/bls192.c @@ -0,0 +1,89 @@ +/* +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. +*/ + +/* Boneh-Lynn-Shacham signature 192-bit API */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include "bls192_ZZZ.h" + +/* hash a message to an ECP point, using SHA3 */ + +static void BLS_HASHIT(ECP_ZZZ *P,char *m) +{ + int i; + sha3 hs; + char h[MODBYTES_XXX]; + octet HM= {0,sizeof(h),h}; + SHA3_init(&hs,SHAKE256); + for (i=0;m[i]!=0;i++) SHA3_process(&hs,m[i]); + SHA3_shake(&hs,HM.val,MODBYTES_XXX); + HM.len=MODBYTES_XXX; + ECP_ZZZ_mapit(P,&HM); +} + +/* generate key pair, private key S, public key W */ + +int BLS_ZZZ_KEY_PAIR_GENERATE(csprng *RNG,octet* S,octet *W) +{ + ECP4_ZZZ G; + BIG_XXX s,q; + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + ECP4_ZZZ_generator(&G); + BIG_XXX_randomnum(s,q,RNG); + BIG_XXX_toBytes(S->val,s); + S->len=MODBYTES_XXX; + PAIR_ZZZ_G2mul(&G,s); + ECP4_ZZZ_toOctet(W,&G); + return BLS_OK; +} + +/* Sign message m using private key S to produce signature SIG */ + +int BLS_ZZZ_SIGN(octet *SIG,char *m,octet *S) +{ + BIG_XXX s; + ECP_ZZZ D; + BLS_HASHIT(&D,m); + BIG_XXX_fromBytes(s,S->val); + PAIR_ZZZ_G1mul(&D,s); + ECP_ZZZ_toOctet(SIG,&D,true); /* compress output */ + return BLS_OK; +} + +/* Verify signature given message m, the signature SIG, and the public key W */ + +int BLS_ZZZ_VERIFY(octet *SIG,char *m,octet *W) +{ + FP24_YYY v; + ECP4_ZZZ G,PK; + ECP_ZZZ D,HM; + BLS_HASHIT(&HM,m); + ECP_ZZZ_fromOctet(&D,SIG); + ECP4_ZZZ_generator(&G); + ECP4_ZZZ_fromOctet(&PK,W); + ECP_ZZZ_neg(&D); + PAIR_ZZZ_double_ate(&v,&G,&D,&PK,&HM); + PAIR_ZZZ_fexp(&v); + if (FP24_YYY_isunity(&v)) return BLS_OK; + return BLS_FAIL; +} +
