relic-toolkit/relic

Code

RELIC is a modern research-oriented cryptographic meta-toolkit with emphasis on efficiency and flexibility. RELIC can be used to build efficient and usable cryptographic toolkits tailored for specific security levels and algorithmic choices.

Goals

RELIC is an ongoing project and features will be added on demand. The focus is to provide:

• Ease of portability and inclusion of architecture-dependent code
• Simple experimentation with alternative implementations
• Tests and benchmarks for every implemented function
• Flexible configuration
• Maximum efficiency

Algorithms

RELIC implements to date:

• Multiple-precision integer arithmetic
• Prime and Binary field arithmetic
• Elliptic curves over prime and binary fields (NIST curves and pairing-friendly curves)
• Bilinear maps and related extension fields
• Cryptographic protocols (RSA, Rabin, ECDSA, ECMQV, ECSS (Schnorr), ECIES, Sakai-Ohgishi-Kasahara ID-based authenticated key agreement, Boneh-Lynn-Schacham and Boneh-Boyen short signatures, Paillier and Benaloh homomorphic encryption systems)

Citing

If you use RELIC, please cite using the template below:

@misc{relic-toolkit,
    author = {D. F. Aranha and C. P. L. Gouvêa and T. Markmann and R. S. Wahby and K. Liao},        
    title = {{RELIC is an Efficient LIbrary for Cryptography}},
    howpublished = {\url{https://github.com/relic-toolkit/relic}},
}

Build instructions

Instructions for building the library can be found in the Wiki.

Support

You can probably get some help over the official mailing list at [email protected]

If you like the library, please consider supporting development through Paypal.

Licensing

This work is dual-licensed under Apache 2.0 and LGPL 2.1-or-above to encourage collaboration with other research groups and contributions from the industry. You can choose between one of them if you use this work.

SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1

Starting from version 0.3.3, static linking and changes in the configuration or build system are explicitly exempted from representing derived works. Please refer to the LICENSE files for additional details.

Disclaimer

RELIC is at best alpha-quality software. Implementations may not be correct or secure and may include patented algorithms. There are many configuration options which make the library horribly insecure. Backward API compatibility with early versions may not necessarily be maintained. Side-channel and fault injection attacks are not considered in particular, unless it is explicitly noted. Use at your own risk.

relic's Issues

relic_bn: bn_rand_mod() distribution out of bounds

Context

RELIC version: 1d08528
Configure parameters: irrelevant

Issue

bn_rand_mod(p) is expected to have a uniform distribution in [0, p).
However, assuming bn_rand(b bits) has a uniform distribution in [0, 2^b), the output of the current bn_rand_mod is uniform in [1, p].
This makes the distribution non-uniform in [0, p) as zero is never generated. More importantly, p can be generated thus breaking the promise of "modulo p".

Possible fix:

Replace the stopping condition with

void bn_rand_mod(bn_t a, bn_t b) {
        do {
                bn_rand(a, bn_sign(b), bn_bits(b));
        } while (bn_cmp_abs(a, b) != CMP_LT);
}

x64-asm-382 doesn't build TESTS and BENCH

This is a clean x64-pbc-128-b12.sh build.

[ 76%] Building C object test/CMakeFiles/test_ed.dir/test_ed.c.o
[ 77%] Linking C executable ../bin/test_ed
/usr/lib/gcc/x86_64-alpine-linux-musl/6.4.0/../../../../x86_64-alpine-linux-musl/bin/ld: ../lib/librelic_s.a(relic_fp_add_low.s.o): relocation R_X86_64_32S against `.data' can not be used when making a shared object; recompile with -fPIC
/usr/lib/gcc/x86_64-alpine-linux-musl/6.4.0/../../../../x86_64-alpine-linux-musl/bin/ld: ../lib/librelic_s.a(relic_fp_mul_low.s.o): relocation R_X86_64_32S against `.data' can not be used when making a shared object; recompile with -fPIC
/usr/lib/gcc/x86_64-alpine-linux-musl/6.4.0/../../../../x86_64-alpine-linux-musl/bin/ld: ../lib/librelic_s.a(relic_fp_rdc_low.s.o): relocation R_X86_64_32S against `.data' can not be used when making a shared object; recompile with -fPIC
/usr/lib/gcc/x86_64-alpine-linux-musl/6.4.0/../../../../x86_64-alpine-linux-musl/bin/ld: final link failed: Nonrepresentable section on output
collect2: error: ld returned 1 exit status
make[2]: *** [test/CMakeFiles/test_ed.dir/build.make:97: bin/test_ed] Error 1
make[1]: *** [CMakeFiles/Makefile2:206: test/CMakeFiles/test_ed.dir/all] Error 2
make: *** [Makefile:141: all] Error 2

Adding -DTESTS=0 -DBENCH=0 makes the build succeed but is, clearly, undesirable.

win64 microsoft calling convention for assembly

As far I can't tell, it's not possible to convince mingw to call the asm routines with SYSV. Thus one having to fall back to gmp or easy for field arithmetic (in case of EC).

Would something to the effect of:

#ifndef __MINGW64__
// Everyone else
#define RDI %rdi
#define RSI %rsi
#define RDX %rdx
#define RCX %rcx
#define R8 %r8
#define R9 %r9
#define WINPUSH
#define WINPOP
#else
// Microsoft
#define RDI %rcx
#define RSI %rdx
#define RDX %r8
#define RCX %r9
#define R8 %rax // Make sure rax isn't used
#define R9 %rdi
#define WINPUSH push %rdi
#define WINPOP pop %rdi
#endif

Make sense, or would it be simpler to just stick SYSV->MS register shuffle in front of each asm _low. Slight overhead, but far less invasive than making all the registers conditional. Of course if somebody knows how to convince mingw to talk to both worlds via some attribute, that would be nice, but never found a such a thing on my own.

ed_map in relic_ed_map.c is insecure

Hi all,

I was looking for implementations of hashing to elliptic curves, and I found RELIC's ed_map, ep_map etc. The ed_map function appears to have a mostly secure (but not constant-time) implementation of mapping to the curve #if0'd out. What is implemented is just g^hash.

This is very dangerous! Most protocols which hash to the curve need an inverse-sampling requirement, and break instantly and completely if you use g^hash. For example, BLS signatures (if you have pairings on an Ed curve), Dragonfly, SPAKE2, SPAKE2EE and GJKW signatures break completely.

Compile relic on mac

I'm trying to compile relic library on mac using gcc 4.9 and got the following error:

Undefined symbols for architecture x86_64:
  "_ed_curve_clean", referenced from:
      _core_clean in relic_core.c.o
  "_ed_curve_init", referenced from:
      _core_init in relic_core.c.o
  "_ep_curve_clean", referenced from:
      _core_clean in relic_core.c.o
  "_ep_curve_init", referenced from:
      _core_init in relic_core.c.o
  "_fp_prime_clean", referenced from:
      _core_clean in relic_core.c.o
  "_fp_prime_init", referenced from:
      _core_init in relic_core.c.o
  "_pp_map_clean", referenced from:
      _core_clean in relic_core.c.o
  "_pp_map_init", referenced from:
      _core_init in relic_core.c.o
ld: symbol(s) not found for architecture x86_64
collect2: error: ld returned 1 exit status

I'm using MacOS Sierra version 10.12.6

Test failures with ALLOC=STATIC

When building with ALLOC=STATIC, some tests fail.

$ ./bin/test_pc
-- Tests for the PC module:

-- Curve B12-P381:

[...]

-- Group G_T:

[...]

** Arithmetic:

Testing if multiplication is commutative...                                   
ERROR: not enough memory.

$ ./bin/test_pp

-- Tests for the PP module

-- Curve B12-P381:

** Arithmetic

Testing if miller addition is correct...                                      [PASS]
Testing if miller addition in affine coordinates is correct...                [PASS]
Testing if miller addition in projective coordinates is correct...            [PASS]
Testing if basic projective miller addition is consistent...                  [PASS]
Testing if lazy-reduced projective miller addition is consistent...           [PASS]
Testing if miller doubling is correct...                                      [PASS]
Testing if miller doubling in affine coordinates is correct...                [PASS]
Testing if miller doubling in projective coordinates is correct...
ERROR: not enough memory.

$ valgrind ./bin/test_cp
[ ...]

Testing if vbnn_ibs is correct...                                             [PASS]
==17621== Invalid free() / delete / delete[] / realloc()
==17621==    at 0x4C2ED5B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==17621==    by 0x11DB15: vbnn_ibs (test_cp.c:795)
==17621==    by 0x125F64: main (test_cp.c:1180)
==17621==  Address 0xffefff9c0 is on thread 1's stack
==17621==  in frame #1, created by vbnn_ibs (test_cp.c:737)
==17621==
==17621== Invalid free() / delete / delete[] / realloc()
==17621==    at 0x4C2ED5B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==17621==    by 0x11DBCA: vbnn_ibs (test_cp.c:796)
==17621==    by 0x125F64: main (test_cp.c:1180)
==17621==  Address 0xffefff900 is on thread 1's stack
==17621==  in frame #1, created by vbnn_ibs (test_cp.c:737)
==17621==
==17621== Invalid free() / delete / delete[] / realloc()
==17621==    at 0x4C2ED5B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==17621==    by 0x11DC7F: vbnn_ibs (test_cp.c:797)
==17621==    by 0x125F64: main (test_cp.c:1180)
==17621==  Address 0xffefff860 is on thread 1's stack
==17621==  in frame #1, created by vbnn_ibs (test_cp.c:737)
==17621==

fp_st type is incompatible with cgo FFI

cggo can't see through "fp_st and fp_t are both different fancy typedefs for dig_t*", and gets particularly confused by the array type.

relic/relic.go:189: cannot use ep.st.y (type C.fp_st) as type *C.dig_t in argument to _Cfunc__fp_neg
relic/relic.go:189: cannot use ep.st.y (type C.fp_st) as type C.fp_t in argument to _Cfunc__fp_neg

Unused parameter

Why does the functions fp_size_bin() have an unused parameters?

G2 generator for BLS12-381 is undocumented

relic/src/epx/relic_ep2_curve.c

Lines 98 to 101 in f97c36e

	#define B12_P381_X0 "173994825DB88350CA024FA3EE453F723D6E52ED7BEB8AFAE29D223009CA43711E3566E92069F13CE1038C795305A9DE"
	#define B12_P381_X1 "D886D66520D016D27C2699CF0CEBDC87D6EDA1D5B13C392DC327BA2E7FA21C30C8E1F93BD86419D3E594DA84E459FE3"
	#define B12_P381_Y0 "13FD60481C160DB73B3E3F3298CD68C99C9E8C5675A137D8AC42E2CE45CDA854704A539990E675012F6BB3662D7B18DC"
	#define B12_P381_Y1 "0C702DB9DA31B645452DC46A83C0C773A8E3292FDCD422FC4EA112D852190162339140BA78385F473782477E9A59E9F5"

How was this generator chosen?

Alternatively, change to use the generator:

#define B12_P381_X0		"024AA2B2F08F0A91260805272DC51051C6E47AD4FA403B02B4510B647AE3D1770BAC0326A805BBEFD48056C8C121BDB8"
#define B12_P381_X1		"13E02B6052719F607DACD3A088274F65596BD0D09920B61AB5DA61BBDC7F5049334CF11213945D57E5AC7D055D042B7E"
#define B12_P381_Y0		"0CE5D527727D6E118CC9CDC6DA2E351AADFD9BAA8CBDD3A76D429A695160D12C923AC9CC3BACA289E193548608B82801"
#define B12_P381_Y1		"0606C4A02EA734CC32ACD2B02BC28B99CB3E287E85A763AF267492AB572E99AB3F370D275CEC1DA1AAA9075FF05F79BE"

Obtained by "finding the lexicographically smallest valid x-coordinate, and its lexicographically smallest y-coordinate and scaling it by the cofactor such that the result is not the point at infinity."

test_cp.c: cp_rsa_sig_basic() failure

Configuration/preset

cmake -DARCH=X86 -DWORD=32 -DBENCH=1 "-DBN_METHD=BASIC;BASIC;BASIC;BASIC;BASIC;BASIC" -DCHECK=OFF -DCOLOR=OFF -DCOMP="-O0 -g" -DDOCUM=OFF -DEP_ENDOM=OFF "-DFP_METHD=BASIC;BASIC;BASIC;BASIC;BASIC;BASIC" -DEP_DEPTH=3 -DMD_MAP=SH256 -DFP_PMERS=ON -DSEED=ZERO -DSHLIB=OFF -DSTRIP=ON -DTESTS=1 -DTIMER=CYCLE -DVERBS=OFF -DFP_PRIME=256 -DBN_PRECI=256 -DMD_METHD=SH256 "-DWITH=FP;EP;EC;DV;CP;MD;BN;BC" -DCP_ECDSA=BASIC -DEC_ENDOM=OFF -DCP_METHD=PRIME -DEC_METHD=PRIME $1

Also tested (same issue) with CP_RSA = BASIC and QUICK, and CP_RSAPD = BASIC, PCKS1 and PCKS2.

Issue

Platform: Linux 3.13.0-62-generic #102-Ubuntu SMP Tue Aug 11 14:28:35 UTC 2015 i686 GNU/Linux

All tests and benches are fine, except test_cp:

// in main() at test_cp.c:1128
// in rsa() at test_cp.c:100
// in cp_rsa_sig_basic() at relic_cp_rsa.c:946
int cp_rsa_sig_basic(/* snip */) {
    /* snip */
    size = bn_size_bin(prv->n);
    // size = 32
    if (pad_len > (size - RSA_PAD_LEN)) {
    // pad_len = 32, RSA_PAD_LEN = 11, thus 32 > 32 - 11 indeed
        return STS_ERR;
    }

Is it a configuration issue?

Infinite loop in fp_inv_monty when 0 is passed

This leads to infinite loops when deserializing GT, looks like a critical bug

On machines, where #MUL = #ADD hybrid karazuba is faster

Hey,

I'm currently developing the optimal Ate pairing on an ARM Cortex M4 processor. On that the used cycles for multiplication and addition of (unsigned) 32-bit integers is equal to one. Therefore, the trade off of multiplication for additions is faster, as long the total count is the lowest. So it turned out for multiplication on $F_p$ the schoolbook method, if you can handle the carry well, is the fastest method. But in tower fields, where the $F_p$ multiplication is used, a hybrid Karazuba gains alot of speed.

Consider $F_{p^{16}}$, on my measures the 2-iterative Karazuba (two 16 word arrays split into four eight word arrays, which are itselve split into two four word arrays) with a final fall back schoolbook method, (for degree four polynomials) turned out to be the fastest method.

The only bottleneck is the modular reduction. If you try to use the $F_p$ reduction after every multiplication you lose a lot of performance. The probably best way is to sum up all coefficients and using the reduction afterwards. I guess this could be called something like "lazy reduction".

undefined reference to `ed_mul_fix_lwnaf_mixed'

When running the commented out test in .travis.yml, the build fails with undefined reference to ed_mul_fix_lwnaf_mixed'`. I couldn't find this function defined anywhere in the library.

naming collision for ZERO

ZERO is defined as 6 in
https://github.com/relic-toolkit/relic/blob/master/include/relic_conf.h.in#L687

which can collide with other code easily, that defines ZERO as 0 :)

Would be good to change to RELIC_ZERO for defines in that file (and maybe other variables too).

Signature Aggregation

Hi,

I am a developer with limited math knowledge, I would like to know, will it be possible to use this library to implement signature aggregation to combine n signatures generated from n distinct keys and messages into 1 compact signature that will not take more space then 1 of the n signatures.

Basically, I would like to know if using this library I can implement the signature aggregation idea as it described in Aggregate and Verifiably Encrypted Signatures from Bilinear Maps

MacOS: tests take insane amount of time?

It looks like some tests take forever, and some just hang:

$ make test
. . . . .
19/34 Test #19: bench_err ........................   Passed    0.02 sec
      Start 20: bench_bn
20/34 Test #20: bench_bn .........................   Passed  483.57 sec
      Start 21: bench_dv
21/34 Test #21: bench_dv .........................   Passed    0.01 sec
      Start 22: bench_fp
22/34 Test #22: bench_fp .........................   Passed   41.10 sec
      Start 23: bench_fpx
23/34 Test #23: bench_fpx ........................   Passed  479.88 sec
      Start 24: bench_fb
24/34 Test #24: bench_fb .........................   Passed   95.82 sec
      Start 25: bench_fbx
25/34 Test #25: bench_fbx ........................   Passed    2.01 sec
      Start 26: bench_ep
26/34 Test #26: bench_ep .........................   Passed  2147.41 sec
      Start 27: bench_epx

[and Test #26 seems stuck eating CPU cycles at this point, having consumed more than an hour already]

MacOS High Sierra 10.13.4, Xcode-9.3, configured with all the default options.

Missing fp6_mul_dxs_unr when STRIP=on is used together with PP_EXT == LAZYR

I use preset

• x64-pbc-128-b12.sh

-DWORD=64 -DRAND=UDEV -DSHLIB=OFF -DSTBIN=ON -DTIMER=CYCLE -DCHECK=off -DVERBS=off -DARITH=x64-asm-382 -DFP_PRIME=381 -DFP_METHD="INTEG;INTEG;INTEG;MONTY;LOWER;SLIDE" -DCOMP="-O3 -funroll-loops -fomit-frame-pointer -finline-small-functions -march=native -mtune=native" -DFP_PMERS=off -DFP_QNRES=on -DFPX_METHD="INTEG;INTEG;LAZYR" -DEP_PLAIN=off -DEP_SUPER=off -DPP_METHD="LAZYR;OATEP"

if I add STRIP=on to it then I get

./lib/librelic_s.a(relic_fp18_mul.c.o): In function `fp18_mul_dxs_lazyr':

relic_fp18_mul.c:(.text+0xed0): undefined reference to `fp6_mul_dxs_unr'

relic_fp18_mul.c:(.text+0xeee): undefined reference to `fp6_mul_dxs_unr'

Looks like fp6_mul_dxs_unr should be moved under

#if PP_EXT == LAZYR || !defined(STRIP)

and not

#if PP_EXT == BASIC || !defined(STRIP)

which fixes the problem.

Should I make a PR?

relic_pc: gt_is_unity() does not work as expected

Context

RELIC version: 1d08528
Configure parameters: -DDEBUG=on -DBENCH=10 -DTESTS=10 -DARITH=gmp -DALLOC=DYNAMIC -DBN_PRECI=8192 -DFP_PRIME=256

For this configuration, gt is fp12.

Reproduction

Example 1

fp12_print(a)
1B6EEEBC330A20B5 8B3F6CCCC5EA3A6B 160B8CE4BA2AD063 9C8B8428CD3000EF
AD57C9EDDD332E0B D7C21344C757BE6E AA81013EDE3AC7E9 9CED22772A962FC2
66BDABD9ECCE14E6 C6CF36B0B4E4F66B F5CB6968D0250A99 59021F08FC7D3A9E
6BFE7B284667E5D1 C57A79D2C1691F2B 54A802447372D6A9 998BB60F1797B5DC
AA23F7E21D98F25A B1E81A80EAAAA7D7 6225AD45329CD85F F6FB647C2811C02B
58F1FD7BC67E50AA 31130AF193C80A48 1BA53A61F1345CEF 38D039EA0B639A51
3D2442CC297C1AC2 F91AD601C8F207F8 C996BE68ABE56316 0690C2D8C9A109FC
B5B0F937BDBC4BE1 BACE3D838C73051A DA1DAB1AE4AAFDC8 B616DD52993EEFD6
A04EEF6A9DC425A5 77DECA0ACA80C295 73EB12826706DB3D F3D3778A4979CCD9
5476C9853F92B5AA 6A7D1752B1162FE8 DF7AC7E377AD0EAA 6CB70D9713F5921E
5145CB73ABA6F97C 64E500488E6BAE1A 67081B38651102FE 10A4C7442EB45DEF
62B4000B57990329 DF2EB2C936D2986C 63822B65193A62E1 B22FBD975D7C718E

Testing if(gt_is_unity(key)) always evaluates to true.

Example 2

The following addition to the test suite of the pc module highlights the issue:

diff --git a/test/test_pc.c b/test/test_pc.c
index 041d1b2..c3e53ab 100755
--- a/test/test_pc.c
+++ b/test/test_pc.c
@@ -1081,6 +1081,12 @@ int util(void) {
                        TEST_ASSERT(gt_is_unity(a), end);
                }
                TEST_END;
+
+//           TEST_BEGIN("EXTRA unity test") {
+//                   gt_rand(a);
+//                   TEST_ASSERT(!gt_is_unity(a), end);
+//           }
+//           TEST_END;
        }
        CATCH_ANY {
                util_print("FATAL ERROR!\n");

With the bug, the test should fail with high probability.

Possible fix

Developer side

A manual call to fp12_cmp_dig(key, 1) == CMP_EQ works.
More generically, setting an element to gt_set_unity(unity) and then comparing gt_cmp(key, unity) == CMP_EQ works.

Library side

gt_is_unity is a macro that expands to fp12_cmp_dig (a=0xxxx, b=1) (or fp2_cmp_dig for the supersingular curve). The result of the comparison (be it fp12_cmp or fp2_cmp) should be checked against CMP_EQ.

Compiling RELIC with BN_MOD set to PMERS

Hi all,

I configured RELIC with DBN_METHD="COMBA;COMBA;PMERS;SLIDE;BASIC;BASIC" (i.e., PMERS rather than MONTY) on OS X using XCode's clang:

mkdir build/
cd build/
cmake -DWORD=64 -DRAND=UDEV -DSHLIB=ON -DSTLIB=ON -DSTBIN=OFF -DTIMER=HREAL -DCHECK=on -DVERBS=on -DARITH=x64-asm-254 -DFP_PRIME=254 -DFP_METHD="INTEG;INTEG;INTEG;MONTY;LOWER;SLIDE" -DCOMP="-O3 -funroll-loops -fomit-frame-pointer -finline-small-functions -march=native -mtune=native" -DFP_PMERS=off -DFP_QNRES=on -DFPX_METHD="INTEG;INTEG;LAZYR" -DPP_METHD="LAZYR;OATEP" -DBN_METHD="COMBA;COMBA;PMERS;SLIDE;BASIC;BASIC" ..

...and got the following errors:

[ 88%] Building C object test/CMakeFiles/test_bn.dir/test_bn.c.o
clang: warning: optimization flag '-finline-small-functions' is not supported [-Wignored-optimization-argument]
/Users/alinush/repos/relic/test/test_bn.c:1005:16: warning: incompatible integer to pointer conversion passing 'int' to parameter of type
      'const bn_st *' [-Wint-conversion]
                bn_sub(p, p, 1);
                             ^
/Users/alinush/repos/relic/include/relic_bn.h:740:46: note: passing argument to parameter 'b' here
void bn_sub(bn_t c, const bn_t a, const bn_t b);
                                             ^
/Users/alinush/repos/relic/test/test_bn.c:1556:10: error: use of undeclared identifier 'p'
                bn_sub(p, p, 1);
                       ^
/Users/alinush/repos/relic/test/test_bn.c:1556:13: error: use of undeclared identifier 'p'
                bn_sub(p, p, 1);
                          ^
1 warning and 2 errors generated.

The first warning seems to be because bn_sub_dig needs to be called, not bn_sub since the second argument is a dig_t/integer.

The second error seems to be because of a misnamed variable (copy & paste gone wrong?). p should be d I think.

The patch should be:

diff --git a/test/test_bn.c b/test/test_bn.c
index 75d12915..c170f1cf 100644
--- a/test/test_bn.c
+++ b/test/test_bn.c
@@ -1002,7 +1002,7 @@ static int exponentiation(void) {
 		/* Let's try a Mersenne prime. */
 		bn_zero(p);
 		bn_set_bit(p, 127, 1);
-		bn_sub(p, p, 1);
+		bn_sub_dig(p, p, 1);
 #endif

 		TEST_BEGIN("modular exponentiation is correct") {
@@ -1553,7 +1553,7 @@ static int digit(void) {
 		/* Let's try a Mersenne prime. */
 		bn_zero(d);
 		bn_set_bit(d, 127, 1);
-		bn_sub(p, p, 1);
+		bn_sub_dig(d, d, 1);
 #endif

 		TEST_BEGIN("modular exponentiation with a digit is consistent") {

Unable to use ARITH=x64-asm-382 together with SHLIB=ON

When using the preset x64-pbc-128-b12.sh together with -DSHLIB=on, the build fails with:

/usr/bin/ld: CMakeFiles/relic_relic.dir/low/x64-asm-382/relic_fp_add_low.s.o: relocation R_X86_64_32S against `.data' can not be used when making a shared object; recompile with -fPIC
/usr/bin/ld: CMakeFiles/relic_relic.dir/low/x64-asm-382/relic_fp_mul_low.s.o: relocation R_X86_64_32S against `.data' can not be used when making a shared object; recompile with -fPIC
/usr/bin/ld: CMakeFiles/relic_relic.dir/low/x64-asm-382/relic_fp_rdc_low.s.o: relocation R_X86_64_32S against `.data' can not be used when making a shared object; recompile with -fPIC

I also see similar issues when linking the static relic build into any shared library.

Feedback on library interface

Instead of opening multiple individual issues, I grouped here a few behaviours that seemed a bit unusual from a library user's perspective.

Comparison routines

Comparison routines like ep_cmp / g1_cmp expect the points / group elements to be normalized. The comparison fails otherwise.

I understand that normalizing the points in the comparison function could be a side-effect that the programmer might not expect. This is why the arguments are const.

A possible solution would be to internally duplicate the points, normalize them, and only then compare them.

Another less resource-heavy solution would be to udpate the documenation to warn about this behaviour.

Methods taking elements in Zn

As I started to use the library I was left with the impression that the best way to handle elements in Zn is by using the bn_t type. This feeling is confirmed by the API of many functions that use bn_t when they expect an element in Zn.

However, there are some inconsistencies which break this unspoken promise, sometimes to the detriment of performance, sometimes even for correctness. Additive or multiplicative notation, applies to both:

• One has to compute -x\*g as - (x\*g). Doing (-x) * g fails silently. More explicitly, one has to do

        g2_mul(g_x, g, x);
        g2_neg(g_x, g_x);

instead of

      bn_neg(tmp, x);
      g2_mul(g_x, g, tmp);

• g^0 is not 1 (it crashes). See #9
• g^exp when exp >> n (where n is the modulo in Zn) makes the library exit due to insufficient buffer capacity. Which means that exp is not treated modulo n, so even when it doesn't crash, it is possibly slower.

In general

Many methods expect some inputs to be in a very specific format in order to work correctly. Although this might be obvious for somebody familiar with the implementation of the library, it might come as a surprise for somebody using the library as a blackbox to experiment with a cryptographic protocol.

One way to mitigate this is to sanitize inputs and make the library more robust.

Another way would be to change the documentation such that it is clear what a programmer should do in order for the library to work correctly.

bug in relic_cp_bgn.c:153

Commit 4c0af5 introduced a bug at line 153

relic_cp_bgn.c:153:4: error: break statement not within loop or switch
break;
^

Name clashes between RELIC and OpenSSL in C++

RELIC version: 706f38e
OpenSSL version: 1.0.1k

RELIC and OpenSSL don't work together when used in a C++ program. Some of the problems are:

• usr/include/relic/relic_bn.h:54:0: warning: "BN_BITS" redefined
• usr/include/relic/relic_bn.h:74:0: warning: "BN_BYTES" redefined
• usr/include/relic/relic_cp.h:97:3: error: conflicting declaration ‘typedef struct _rsa_t rsa_st’

I noticed OpenSSL guards the include files in extern "C". RELIC doesn't. Apart from that, I don't understand much more.

I'm using RELIC for pairings and OpenSSL for the AES implementation. Through the EVP interface, it has AES-NI support and it also has more modes of operations (ie CTR). RELIC has only CBC.

Baking some values into code to save RAM?

Hi guys,

I am using RELIC on constrained devices with 64KB RAM or less, so I try to reduce BSS/RAM usage as much as possible.

RELIC's core context allocates something like ~10KB in my case for core_init() during compilation. After runtime initialization, much of that space isn't written to anymore. As far as I understand, the only possibility to initialize the core context variables is during runtime, so it uses BSS/RAM. core_init() sets those values once.

So as a experiment, I put them into flash/ROM as read-only values to make them constant, by extracting some values after initialization and baking them into the code:

Then I change the types to pointers and set them manually after core_init() and remove all code that wants to overwrite that. Those values don't depend on randomness, they are always the same for the same relic config.

This method saves much RAM and also works for custom values outside of core context. Of course that values will be on the flash/ROM which should be slower in theory, but negligible in the tests for my use case. The baked values must be changed when changing the curve etc. but it could be automated.

Questions:

1. Is there a simpler way that I miss? Some serialization for core context values?
2. It there a simpler way to bake other values (outside of core context), like custom precomputation tables etc., rather than reading them at runtime and pasting those values into code?
3. In which case can this lead to side channel attacks, because of the RAM <-> ROM speed differences? Is there a problem when baking precomputation tables, Frobenius maps or constant pairing results like e(P,Q)?

Thanks in advance!

TL;DR moving runtime-initialized constants from RAM to ROM

Is there a way to build the library on Android?

Hello,

As the topic asked. The target I am working on is to use the library on a specific android version: 5.1.1_r30. The best tool I could find to convert CMake to android project is: https://github.com/taka-no-me/android-cmake

There are lots of errors when I run the script. I fixed some but still not able to generate libraries files successfully.

Before I keep trying to fix those errors. I would like to ask: Is there a better way to use the relic library on an android device?

---

Environment :
Ubuntu 16.04
gcc / g++ : 4.9.3
AOSP: 5.1.1_r30
Android API level: 22
NDK: android-ndk-r12b
cmake version 3.5.1
GNU Make 4.1 Built for x86_64-pc-linux-gnu

---

Cheers,

Rong

if the relic library will remove the gmp library dependency, just to make it a pure crypto library ?

I wonder if the library will be a pure crypto library, because in some circumstance, we need to transform to chrome or windows platform, will pure crypto library it will be much more easy. But now the gmp library is some kind of limitation. How to remove gmp from the library, I am not sure how much works it will take ! Any advice to offer will be gratefull, help !!!

relic_pc: gt_exp fails for zero exponent

Context

RELIC version: 1d08528
Configure parameters: -DDEBUG=on -DBENCH=10 -DTESTS=10 -DARITH=gmp -DALLOC=DYNAMIC -DBN_PRECI=8192 -DFP_PRIME=256

Reproduction

diff --git a/test/test_pc.c b/test/test_pc.c
index 041d1b2..7a19b11 100755
--- a/test/test_pc.c
+++ b/test/test_pc.c
@@ -1241,6 +1247,14 @@ int exponentiation(void) {
                        TEST_ASSERT(gt_is_unity(c), end);
                }
                TEST_END;
+
+         TEST_BEGIN("EXTRA gt_exp(a, 0)") {
+                 gt_rand(a);
+                 bn_set_dig(n, 0);
+                 gt_exp(c, a, n);
+                 TEST_ASSERT(gt_is_unity(c), end);
+         }
+         TEST_END;
        }
        CATCH_ANY {
                util_print("FATAL ERROR!\n");

Result: Segmentation fault
Expected result: a^0 == identity element in G_T

how do I integrate Relic on Laravel ??

Is there a proper way to integrate Relic on a proyect running in Laravel? I have some several problems to achieve this in my proyect, if anyone has documentation about this, please share it with me

relic calls exit(0) on error

On a call to ep_read_bin, relic encounters two errors in a row (stopping me from handling/clearing the first, which I think is a bug in and of itself), and then exits with code 0.

ERROR in bn_div_rem() at /Users/filippo/src/github.com/FiloSottile/powersoftau/relic/relic/src/bn/relic_bn_div.c,139: invalid value passed as input.
	CAUGHT in fp_prime_conv() at /Users/filippo/src/github.com/FiloSottile/powersoftau/relic/relic/src/fp/relic_fp_prime.c,472.
	CAUGHT in fp_read_bin() at /Users/filippo/src/github.com/FiloSottile/powersoftau/relic/relic/src/fp/relic_fp_util.c,252.

ERROR in bn_div_rem() at /Users/filippo/src/github.com/FiloSottile/powersoftau/relic/relic/src/bn/relic_bn_div.c,139: invalid value passed as input.
	CAUGHT in fp_prime_conv() at /Users/filippo/src/github.com/FiloSottile/powersoftau/relic/relic/src/fp/relic_fp_prime.c,472.

md_hmac(...) uses Variable-length automatic arrays after scope exit

in the function void md_hmac(...) in the file relic_md_hmac.c, there is illegal use of Variable-length automatic arrays in that these arrays are allocated in a local if scope and then used outside this scope.

The C99 standard stated that these arrays are deallocated on the completion of the scope. However, the code copies the pointer into the containing scope and then uses it.

Save cycles while copy elements

I'm actually on my master thesis and discovered a small but signifanct difference in doing:
void fp_copy(fp_t c, const fp_t a) { for (int i = 0; i < FP_DIGS; i++) { c[i] = a[i]; } }

and using memcpy.

I'm implementing the KSS-16 arithmetics on an ARM Cortex M4 and discovered, that this way uses 1.5 times of the cycle count of memcpy. Another fact I found out, defining a macro for memcpy uses 38 instead of 30 cycles by a word size of 11*4 bytes. Defining a function that uses memcpy needs 60 cycles.

I don't know if you have mentioned such things before, but this is a hint and could enhance some evaluations on a small amount. (Compiling with arm-none-eabi-gcc and -Ofast.) For me, the best but not fastest method is defining a macro.

Problem with linking relic functions

I'm using TinyOS 2.1.2 with last relic release for my thesis and i have the following issue:
when I compile my project it goes well but when I run the application I get an error referred to relic functions. Dumping the _TOSSIMmodule.so file i found out that relic library doesn't result linked. I checked the MakeFile and I correctly set library path but the problem persists.

Unable to build on windows because of the FIXED constant

Windows has FIXED defined, so when trying to build Relic under windows (with mingw) it fails with

• D:/go/src/gopkg.in/pythia.v0/pythia/lib/pythia/cmake-build-release/relic-prefix/src/relic-build/include/relic_conf.h:531:16: error: expected identifier or '(' before numeric constant

This is fixed in #45 . Could you please port that part of fix?

Unexpected failure of ep2_mul[_lwnaf] above the prime group order

I have a point and I want to scale it by the cofactor. I get three different answers with three different methods.

ep2_mul_basic

void ep2_scale_by_cofactor(ep2_t p) {
    bn_t k;
    bn_new(k);
    bn_read_str(k, "5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5", 127, 16); // FROM RUST IMPLEMENTATION
    ep2_mul_basic(p, p, k);
    bn_free(k);
}

This matches the result of the ebfull/pairing Rust implementation when used with the cofactor lifted from there.

https://github.com/ebfull/pairing/blob/a8583dd81840d1b970ff90905bfa582d67910e41/src/bls12_381/ec.rs#L1346-L1353

ep2_mul

void ep2_scale_by_cofactor(ep2_t p) {
    bn_t k;
    bn_new(k);
    bn_read_str(k, "5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5", 127, 16); // FROM RUST IMPLEMENTATION
    ep2_mul(p, p, k); // FOR SOME REASON ep2_mul[_lwnaf] returns a wrong result
    bn_free(k);
}

Using the default ep2_mul implementation returns a different result when used with the same cofactor value.

ep2_mul_cof_b12

Using the ahem unexported ep2_mul_cof_b12 from ep2_map returns a yet different result.

---

Full cmake:

cmake -DALLOC=DYNAMIC -DFP_PRIME=381 \
		-DSHLIB=off -DSTLIB=on -DRAND=UDEV -DTESTS=1 -DBENCH=0 \
		-DCOMP="-O3 -funroll-loops -Wno-unused-function"

Use NIST_K283 curves gives an error

I tried to use NIST_K283 curve with eb_param_set(NIST_K283); it gives me an runtime error

FATAL ERROR in .../relic/src/eb/relic_eb_param.c:342

I'm running on latest version of ubuntu with gcc5. no preset used when compiling the code.

The installation of relic is not clear

Hi,
I am trying to install relic on ubuntu to use cp-rsa .. I just read recently about relic so I am trying to install it but it seems the steps is not clear. Is any one can help me please ?

Crashing whenever calling ec_read_bin()

Whenever calling the library code to read an ec_t from an array previously filled with ec_write_bin(), the library crashes with a SEGFAULT.

The code calls which can cause a crash are as follows:

        ec_t curve;
	ec_null(curve);
	ec_new(curve);

	int size = ec_size_bin(curve, 0);
	uint8_t* curveArr = malloc(size * sizeof(uint8_t));

	ec_write_bin(curveArr, size, curve, 0);

	ec_t curveCopy;
	ec_null(curveCopy);
	ec_new(curveCopy);

	ec_read_bin(curveCopy, curveArr, size);

My system information is:

Linux hostname.tld 4.4.0-104-generic #127-Ubuntu SMP Mon Dec 11 12:16:42 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

gcc (Ubuntu 5.4.0-6ubuntu1~16.04.5) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

libgmp-dev (2:6.1.0+dfsg-2) from ubuntu repos.

If you need any more information to help diagnose this issue, please ask: I'll be happy to provide it!

Overflow in bn_rec_tnaf_get()

My compiler (gcc (GCC) 4.9.2 20150204 (prerelease)) is warning about an overflow in implicit constant conversion in https://github.com/relic-toolkit/relic/blob/master/src/bn/relic_bn_rec.c#L242 and to my understanding that's true. t is an int8_t pointer and 166 is > 2^8/2.

Is there a way to export specific arithmetics for a specific kind of curve?

Hey,
I'm interested in implementing KSS-16 and the optimal Ate-pairing on Cortex M4 and I would like build this up on a well running lib. So I would like to export the whole arithmetic for KSS 16 curves and declare the latest suggested key sizes from [1].

In the end I'm only interested in some benchmarks.

[1] https://eprint.iacr.org/2017/334

Relic Error

Hi，
I had a problem when I try to cmake relic-master. The problem as follows:
CMake Error at src/CMakeList.txt:9 (string):
string no output variable specified
-- Could not find Doxygen (missing: DOXYGEN_EXECUTABLE)
-- Configuring incomplete, error occurred!

Thanks!

fp_cmd returns wrong results with FP_RDC=MONTY

Here is some output from this code:

fp_print(ep->y);
fp_print(other);
int res = fp_cmp(ep->y, other);
printf("%d\n", res);

Using the default "BASIC;COMBA;COMBA;MONTY;MONTY;SLIDE" (wrong):

--- 1
114D1D6855D545A8 AA7D76C8CF2E21F2 67816AEF1DB507C9 6655B9D5CAAC4236 4E6F38BA0ECB751B AD54DCD6B939C2CA
08B3F481E3AAA0F1 A09E30ED741D8AE4 FCF5E095D5D00AF6 00DB18CB2C04B3ED D03CC744A2888AE4 0CAA232946C5E7E1
1
08B3F481E3AAA0F1 A09E30ED741D8AE4 FCF5E095D5D00AF6 00DB18CB2C04B3ED D03CC744A2888AE4 0CAA232946C5E7E1
114D1D6855D545A8 AA7D76C8CF2E21F2 67816AEF1DB507C9 6655B9D5CAAC4236 4E6F38BA0ECB751B AD54DCD6B939C2CA
-1
--- 2
166A9D8CABC673A3 22FDA673779D8E38 22BA3ECB8670E461 F73BB9021D5FD76A 4C56D9D4CD16BD1B BA86881979749D28
0396745D8DB972F7 281E0142CBAE1E9F 41BD0CB96D142E5D 6FF5199ED9511EB9 D2552629E43D42E3 FF7877E6868B0D83
-1
166A9D8CABC673A3 22FDA673779D8E38 22BA3ECB8670E461 F73BB9021D5FD76A 4C56D9D4CD16BD1B BA86881979749D28
0396745D8DB972F7 281E0142CBAE1E9F 41BD0CB96D142E5D 6FF5199ED9511EB9 D2552629E43D42E3 FF7877E6868B0D83
-1
--- 3
032B80D3A6F5B09F 8A84623389C5F80C A69A0CDDABC3097F 9D9C27310FD43BE6 E745256C634AF45C A3473B0590AE30D1
16D59116928A35FA C0974582B985B4CA BDDD3EA747C2093F C994AB6FE6DCBA3D 3766DA924E090BA3 16B7C4FA6F5179DA
1
032B80D3A6F5B09F 8A84623389C5F80C A69A0CDDABC3097F 9D9C27310FD43BE6 E745256C634AF45C A3473B0590AE30D1
16D59116928A35FA C0974582B985B4CA BDDD3EA747C2093F C994AB6FE6DCBA3D 3766DA924E090BA3 16B7C4FA6F5179DA
1
--- 4
143BE6D078C2B79A 7D4F1D1B21486A03 0EC93F56AA54E1DE 880DB5A66DD833A6 52A95BEE27C82408 4006CB5644CBD43F
05C52B19C0BD2EFF CDCC8A9B220342D4 55AE0C2E493030E0 DF231CFA88D8C27D CC02A410898BDBF7 79F834A9BB33D66C
1
143BE6D078C2B79A 7D4F1D1B21486A03 0EC93F56AA54E1DE 880DB5A66DD833A6 52A95BEE27C82408 4006CB5644CBD43F
05C52B19C0BD2EFF CDCC8A9B220342D4 55AE0C2E493030E0 DF231CFA88D8C27D CC02A410898BDBF7 79F834A9BB33D66C
1
--- 5
16BA437EDCC6551E 30C10512367494BF B6B01CC6681E8A4C 3CD2501832AB5C4A BC40B4578B85CBAF FBF0BCD70D67C6E2
0346CE6B5CB9917C 1A5AA2A40CD71817 ADC72EBE8B668873 2A5E8288C40599D9 626B4BA725CE344F BE0E4328F297E3C9
1
16BA437EDCC6551E 30C10512367494BF B6B01CC6681E8A4C 3CD2501832AB5C4A BC40B4578B85CBAF FBF0BCD70D67C6E2
0346CE6B5CB9917C 1A5AA2A40CD71817 ADC72EBE8B668873 2A5E8288C40599D9 626B4BA725CE344F BE0E4328F297E3C9
1
--- 6
022901B141A9DAAB BA0ACDF56C7A9CA7 819DB2BB9B92848D 7B0885E0B57C1695 D6C307CEBDA4D19F 13259775BA9C632F
17D81038F7D60BEE 9110D9C0D6D1102F E2D998C957F28E31 EC284CC04134DF8E 47E8F82FF3AF2E60 A6D9688A4563477C
-1
17D81038F7D60BEE 9110D9C0D6D1102F E2D998C957F28E31 EC284CC04134DF8E 47E8F82FF3AF2E60 A6D9688A4563477C
022901B141A9DAAB BA0ACDF56C7A9CA7 819DB2BB9B92848D 7B0885E0B57C1695 D6C307CEBDA4D19F 13259775BA9C632F
1
--- 7
0973642F94C9B055 F4E1D20812C1F913 29ED2E3D71F635A7 2D599A679D0CDA13 20E597B4E1B24F73 5FED1381D767908F
108DADBAA4B63644 5639D5AE3089B3C4 3A8A1D47818EDD18 39D7383959A41C10 FDC66849CFA1B08C 5A11EC7E28981A1C
1
108DADBAA4B63644 5639D5AE3089B3C4 3A8A1D47818EDD18 39D7383959A41C10 FDC66849CFA1B08C 5A11EC7E28981A1C
0973642F94C9B055 F4E1D20812C1F913 29ED2E3D71F635A7 2D599A679D0CDA13 20E597B4E1B24F73 5FED1381D767908F
-1
--- 8
0019323EAF069B2F 8F7C22D0CC11CEC0 3A140A327F90B1EE 06B12BF9A7A6288C 4544E47E938202B0 A1DBD22EDA6C510A
19E7DFAB8A794B6A BB9F84E57739DE17 2A63415273F460D1 607FA6A74F0ACD97 D9671B801DD1FD4F 18232DD1259359A1
-1
19E7DFAB8A794B6A BB9F84E57739DE17 2A63415273F460D1 607FA6A74F0ACD97 D9671B801DD1FD4F 18232DD1259359A1
0019323EAF069B2F 8F7C22D0CC11CEC0 3A140A327F90B1EE 06B12BF9A7A6288C 4544E47E938202B0 A1DBD22EDA6C510A
1
--- 9
12B8F6CB13653AED 56BF396680D3A783 22B79BEAFD8040C7 31705D762D3CCADE FBE20A37339FF675 D2249F7AFA2B2495
07481B1F261AABAC F45C6E4FC2780554 41BFAF99F604D1F8 35C0752AC9742B45 22C9F5C77DB40989 E7DA608505D48616
1
07481B1F261AABAC F45C6E4FC2780554 41BFAF99F604D1F8 35C0752AC9742B45 22C9F5C77DB40989 E7DA608505D48616
12B8F6CB13653AED 56BF396680D3A783 22B79BEAFD8040C7 31705D762D3CCADE FBE20A37339FF675 D2249F7AFA2B2495
-1
--- 10
0851AF54A7936008 DDAEC43DCB9468D9 43DD108EE23D7953 4938D584AF00C4A2 512B902B95238E48 801A214DCB420C92
11AF629591EC8691 6D6CE37877B743FE 209A3AF61147996C 1DF7FD1C47B03181 CD806FD31C3071B7 39E4DEB234BD9E19
1
11AF629591EC8691 6D6CE37877B743FE 209A3AF61147996C 1DF7FD1C47B03181 CD806FD31C3071B7 39E4DEB234BD9E19
0851AF54A7936008 DDAEC43DCB9468D9 43DD108EE23D7953 4938D584AF00C4A2 512B902B95238E48 801A214DCB420C92
-1

Using -DFP_METHD="BASIC;COMBA;COMBA;BASIC;BASIC;SLIDE" (correct):

--- 0
--- 1
114D1D6855D545A8 AA7D76C8CF2E21F2 67816AEF1DB507C9 6655B9D5CAAC4236 4E6F38BA0ECB751B AD54DCD6B939C2CA
08B3F481E3AAA0F1 A09E30ED741D8AE4 FCF5E095D5D00AF6 00DB18CB2C04B3ED D03CC744A2888AE4 0CAA232946C5E7E1
1
08B3F481E3AAA0F1 A09E30ED741D8AE4 FCF5E095D5D00AF6 00DB18CB2C04B3ED D03CC744A2888AE4 0CAA232946C5E7E1
114D1D6855D545A8 AA7D76C8CF2E21F2 67816AEF1DB507C9 6655B9D5CAAC4236 4E6F38BA0ECB751B AD54DCD6B939C2CA
-1
--- 2
166A9D8CABC673A3 22FDA673779D8E38 22BA3ECB8670E461 F73BB9021D5FD76A 4C56D9D4CD16BD1B BA86881979749D28
0396745D8DB972F7 281E0142CBAE1E9F 41BD0CB96D142E5D 6FF5199ED9511EB9 D2552629E43D42E3 FF7877E6868B0D83
1
166A9D8CABC673A3 22FDA673779D8E38 22BA3ECB8670E461 F73BB9021D5FD76A 4C56D9D4CD16BD1B BA86881979749D28
0396745D8DB972F7 281E0142CBAE1E9F 41BD0CB96D142E5D 6FF5199ED9511EB9 D2552629E43D42E3 FF7877E6868B0D83
1
--- 3
16D59116928A35FA C0974582B985B4CA BDDD3EA747C2093F C994AB6FE6DCBA3D 3766DA924E090BA3 16B7C4FA6F5179DA
032B80D3A6F5B09F 8A84623389C5F80C A69A0CDDABC3097F 9D9C27310FD43BE6 E745256C634AF45C A3473B0590AE30D1
1
032B80D3A6F5B09F 8A84623389C5F80C A69A0CDDABC3097F 9D9C27310FD43BE6 E745256C634AF45C A3473B0590AE30D1
16D59116928A35FA C0974582B985B4CA BDDD3EA747C2093F C994AB6FE6DCBA3D 3766DA924E090BA3 16B7C4FA6F5179DA
-1
--- 4
05C52B19C0BD2EFF CDCC8A9B220342D4 55AE0C2E493030E0 DF231CFA88D8C27D CC02A410898BDBF7 79F834A9BB33D66C
143BE6D078C2B79A 7D4F1D1B21486A03 0EC93F56AA54E1DE 880DB5A66DD833A6 52A95BEE27C82408 4006CB5644CBD43F
-1
143BE6D078C2B79A 7D4F1D1B21486A03 0EC93F56AA54E1DE 880DB5A66DD833A6 52A95BEE27C82408 4006CB5644CBD43F
05C52B19C0BD2EFF CDCC8A9B220342D4 55AE0C2E493030E0 DF231CFA88D8C27D CC02A410898BDBF7 79F834A9BB33D66C
1
--- 5
16BA437EDCC6551E 30C10512367494BF B6B01CC6681E8A4C 3CD2501832AB5C4A BC40B4578B85CBAF FBF0BCD70D67C6E2
0346CE6B5CB9917C 1A5AA2A40CD71817 ADC72EBE8B668873 2A5E8288C40599D9 626B4BA725CE344F BE0E4328F297E3C9
1
16BA437EDCC6551E 30C10512367494BF B6B01CC6681E8A4C 3CD2501832AB5C4A BC40B4578B85CBAF FBF0BCD70D67C6E2
0346CE6B5CB9917C 1A5AA2A40CD71817 ADC72EBE8B668873 2A5E8288C40599D9 626B4BA725CE344F BE0E4328F297E3C9
1
--- 6
17D81038F7D60BEE 9110D9C0D6D1102F E2D998C957F28E31 EC284CC04134DF8E 47E8F82FF3AF2E60 A6D9688A4563477C
022901B141A9DAAB BA0ACDF56C7A9CA7 819DB2BB9B92848D 7B0885E0B57C1695 D6C307CEBDA4D19F 13259775BA9C632F
1
17D81038F7D60BEE 9110D9C0D6D1102F E2D998C957F28E31 EC284CC04134DF8E 47E8F82FF3AF2E60 A6D9688A4563477C
022901B141A9DAAB BA0ACDF56C7A9CA7 819DB2BB9B92848D 7B0885E0B57C1695 D6C307CEBDA4D19F 13259775BA9C632F
1
--- 7
108DADBAA4B63644 5639D5AE3089B3C4 3A8A1D47818EDD18 39D7383959A41C10 FDC66849CFA1B08C 5A11EC7E28981A1C
0973642F94C9B055 F4E1D20812C1F913 29ED2E3D71F635A7 2D599A679D0CDA13 20E597B4E1B24F73 5FED1381D767908F
1
108DADBAA4B63644 5639D5AE3089B3C4 3A8A1D47818EDD18 39D7383959A41C10 FDC66849CFA1B08C 5A11EC7E28981A1C
0973642F94C9B055 F4E1D20812C1F913 29ED2E3D71F635A7 2D599A679D0CDA13 20E597B4E1B24F73 5FED1381D767908F
1
--- 8
0019323EAF069B2F 8F7C22D0CC11CEC0 3A140A327F90B1EE 06B12BF9A7A6288C 4544E47E938202B0 A1DBD22EDA6C510A
19E7DFAB8A794B6A BB9F84E57739DE17 2A63415273F460D1 607FA6A74F0ACD97 D9671B801DD1FD4F 18232DD1259359A1
-1
19E7DFAB8A794B6A BB9F84E57739DE17 2A63415273F460D1 607FA6A74F0ACD97 D9671B801DD1FD4F 18232DD1259359A1
0019323EAF069B2F 8F7C22D0CC11CEC0 3A140A327F90B1EE 06B12BF9A7A6288C 4544E47E938202B0 A1DBD22EDA6C510A
1
--- 9
07481B1F261AABAC F45C6E4FC2780554 41BFAF99F604D1F8 35C0752AC9742B45 22C9F5C77DB40989 E7DA608505D48616
12B8F6CB13653AED 56BF396680D3A783 22B79BEAFD8040C7 31705D762D3CCADE FBE20A37339FF675 D2249F7AFA2B2495
-1
07481B1F261AABAC F45C6E4FC2780554 41BFAF99F604D1F8 35C0752AC9742B45 22C9F5C77DB40989 E7DA608505D48616
12B8F6CB13653AED 56BF396680D3A783 22B79BEAFD8040C7 31705D762D3CCADE FBE20A37339FF675 D2249F7AFA2B2495
-1
--- 10
0851AF54A7936008 DDAEC43DCB9468D9 43DD108EE23D7953 4938D584AF00C4A2 512B902B95238E48 801A214DCB420C92
11AF629591EC8691 6D6CE37877B743FE 209A3AF61147996C 1DF7FD1C47B03181 CD806FD31C3071B7 39E4DEB234BD9E19
-1
11AF629591EC8691 6D6CE37877B743FE 209A3AF61147996C 1DF7FD1C47B03181 CD806FD31C3071B7 39E4DEB234BD9E19
0851AF54A7936008 DDAEC43DCB9468D9 43DD108EE23D7953 4938D584AF00C4A2 512B902B95238E48 801A214DCB420C92
1

Full configuration:

cmake -DALLOC=DYNAMIC -DFP_PRIME=381 \
		-DSHLIB=off -DSTLIB=on -DRAND=UDEV -DTESTS=1 -DBENCH=0 \
		-DCOMP="-O3 -funroll-loops -Wno-unused-function"

bench_eb for curve2251

after compilation using preset curve2251-clmul-gcc.sh , running bencn_eb does not perform the benchmarking. It just print some information and quits.

8bit and 16bit platforms: block ciphers won't build

Trying to build relic for RIOT I noticed that building for platforms like AVR or MSP430 fails when trying to build block ciphers.

I get a lot of errors like:

/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:46:5: error: large integer implicitly truncated to unsigned type [-Werror=overflow]
     0xc66363a5U, 0xf87c7c84U, 0xee777799U, 0xf67b7b8dU,
     ^
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:46:18: error: large integer implicitly truncated to unsigned type [-Werror=overflow]
     0xc66363a5U, 0xf87c7c84U, 0xee777799U, 0xf67b7b8dU,
                  ^
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:46:31: error: large integer implicitly truncated to unsigned type [-Werror=overflow]
     0xc66363a5U, 0xf87c7c84U, 0xee777799U, 0xf67b7b8dU,
...
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c: In function 'rijndaelKeySetupEnc':
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:719:35: error: left shift count >= width of type [-Werror=shift-count-overflow]
 #define GETU32(pt) (((u32)(pt)[0] << 24) ^ ((u32)(pt)[1] << 16) ^ ((u32)(pt)[2] <<  8) ^ ((u32)(pt)[3]))
                                   ^
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:732:10: note: in expansion of macro 'GETU32'
  rk[0] = GETU32(cipherKey     );
          ^
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:719:58: error: left shift count >= width of type [-Werror=shift-count-overflow]
 #define GETU32(pt) (((u32)(pt)[0] << 24) ^ ((u32)(pt)[1] << 16) ^ ((u32)(pt)[2] <<  8) ^ ((u32)(pt)[3]))
                                                          ^
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:732:10: note: in expansion of macro 'GETU32'
  rk[0] = GETU32(cipherKey     );
          ^
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:719:35: error: left shift count >= width of type [-Werror=shift-count-overflow]
 #define GETU32(pt) (((u32)(pt)[0] << 24) ^ ((u32)(pt)[1] << 16) ^ ((u32)(pt)[2] <<  8) ^ ((u32)(pt)[3]))
                                   ^
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:733:10: note: in expansion of macro 'GETU32'
  rk[1] = GETU32(cipherKey +  4);
          ^
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:719:58: error: left shift count >= width of type [-Werror=shift-count-overflow]
 #define GETU32(pt) (((u32)(pt)[0] << 24) ^ ((u32)(pt)[1] << 16) ^ ((u32)(pt)[2] <<  8) ^ ((u32)(pt)[3]))
                                                          ^
/home/oleg/git/RIOT/pkg/relic/relic/src/bc/rijndael-alg-fst.c:733:10: note: in expansion of macro 'GETU32'
  rk[1] = GETU32(cipherKey +  4);

when building for AVR.

relic does not work with windows, when i create vs project with cmake

i found that this library does not work with my win7 and Visual Studio development environment, a lot of compile error, and i cannot find the "dbl_t" definition.
Here are the output:
1>D:\workspace\git-work\MPC\WinTest\MPC\mpc-emp\relic\src\low\easy\relic_fp_sqr_low.c(94): error C2065: “dbl_t”: undelared symbol
1>D:\workspace\git-work\MPC\WinTest\MPC\mpc-emp\relic\src\low\easy\relic_fp_sqr_low.c(94): error C2065: “s”: undelared symbol
1>D:\workspace\git-work\MPC\WinTest\MPC\mpc-emp\relic\src\low\easy\relic_fp_sqr_low.c(97): error C2065: “dbl_t”: undelared symbol
1>D:\workspace\git-work\MPC\WinTest\MPC\mpc-emp\relic\src\low\easy\relic_fp_sqr_low.c(97): error C2146: syntax error

test_pp fails

System: Debian Jessie (x86-64)
RELIC version: git (2015-01-19)
Configuration: -DARITH=gmp -DALLOC=DYNAMIC -DBN_PRECI=8192 -DFP_PRIME=1536

---

The unit test for the PP module fails for the 1536-bits supersingular curve bundled with RELIC (SS-P1536): Testing if weil pairing is bilinear... [FAIL] at relic.git/test/test_pp.c:356.

The test passes for other non-supersingular curves like BN-P158, BN-P254, B12-P638.

I have also tried with one of my own supersingular curves and the test fails sooner at Testing if miller doubling is correct... in test_pp.c:191. I believe I set the parameters correctly, as test_ep works.

Insecure generation of random curve points

The way random curve points (at least for prime curves) are generated is biased: the following code comes from relic_ep_util.c (lines 82-87).

ep_curve_get_ord(n);

bn_rand(k, BN_POS, bn_bits(n));
bn_mod(k, k, n);

ep_mul_gen(p, k);

More precisely, there is a bias in the way k is generated, that can be statistically significant.
Instead, you should either proceed by rejection sampling, or by randomly generating k with bn_bits(n)+lambda bits, and then reducing mod n. In the latter case, the generation of k will be 2^{-lambda} statistically close to uniform in [0, n-1].

I suggest to replace the code as follows (not tested)

ep_curve_get_ord(n);

bn_rand(k, BN_POS, bn_bits(n)+STAT_DISTANCE);
bn_mod(k, k, n);

ep_mul_gen(p, k);

and let STAT_DISTANCE be defined in a configuration file. By default, it should be 30.

make error: conflicting types for ‘bn_mula_low’

When compiling
src/CMakeFiles/relic.dir/low/curve2251-sse/relic_bn_mul_low.c.o

it throws the following error:
low/curve2251-sse/relic_bn_mul_low.c:42:7: error: conflicting types for ‘bn_mula_low’
low/relic_bn_low.h:206:7: note: previous declaration of ‘bn_mula_low’ was here

Fails to compile with clang when ALLOC != AUTO

When using clang (the default on macOS) instead of gcc to compile, and when ALLOC is not AUTO but any of the other options, compilation errors occur. For example, when using STACK I get these:

relic/src/pp/relic_pp_map.c:107:2: error: array type 'ep_t [m]'
      is not assignable
        ep_null(_q);
        ^       ~~
relic/src/pp/relic_pp_map.c:139:3: error: subscripted value is
      not an array, pointer, or vector
                fp2_free(m);
                ^~~~~~~~~~~
relic/src/pp/relic_pp_map.c:139:3: error: subscripted value is
      not an array, pointer, or vector
                fp2_free(m);
                ^~~~~~~~~~~
relic/src/pp/relic_pp_map.c:140:3: error: member reference base
      type 'ep_t' (aka 'ep_st *') is not a structure or union
                ep_free(_q);
                ^~~~~~~~~~~
relic/src/pp/relic_pp_map.c:140:3: error: member reference base
      type 'ep_t' (aka 'ep_st *') is not a structure or union
                ep_free(_q);
                ^~~~~~~~~~~
relic/src/pp/relic_pp_map.c:140:3: error: member reference base
      type 'ep_t' (aka 'ep_st *') is not a structure or union
                ep_free(_q);
                ^~~~~~~~~~~
relic/src/pp/relic_pp_map.c:140:3: error: array type 'ep_t [m]'
      is not assignable
                ep_free(_q);
                ^       ~~

Prefix configuration defines with RELIC_ or similar to avoid conflicts when used with other projects

pc_map() / pp_map_k12() work only for normalized points

Context

RELIC version: 1d08528
Configure parameters: -DDEBUG=on -DBENCH=10 -DTESTS=10 -DARITH=gmp -DALLOC=DYNAMIC -DBN_PRECI=8192 -DFP_PRIME=256

Issue

pc_map() / pp_map_k12() silently fail when one of the arguments (element of G1 or G2) is not normalized.

Possible fix

Adapt the method to handle such inputs or update the documentation to inform the programmer about this requirement.

Note

This might apply to pp_map_k2() as well.