MPHELL  5.0.0
MPHELL Documentation

Introduction

The MPHELL library implements Elliptic Curve arithmetic:

  1. Points addition
  2. Points substraction
  3. Points doubling
  4. Points multiplication
  5. Test if a point belong to a given curve

We provide a Simple Power Analysis (SPA) resistant multiplication using unified addition (and COZ arithmetic for Weierstrass curves).

Some dedicated addition / doubling are also provided to improve performances when security is not required.

Available curve types:

  1. WEIERSTRASS, $ E_w: y^2 = x^3 + a_wx + b_w $
  2. JACOBI_QUARTIC, $ E_j: y^2 = z^2 + 2a_jx^2 + t^2; x^2 = zt; a_j \ne 1 $
  3. EDWARDS, $ E_{Ed}: a_{Ed}x^2 + y^2 = 1 + d_{Ed}x^2y^2 $

Possible conversion:

  1. WEIERSTRASS -> JACOBI_QUARTIC, but you need $\theta$ such that $(\theta, 0)$ is a 2-torsion point on the Weierstrass elliptic curve.
  2. JACOBI_QUARTIC -> WEIERSTRASS
  3. TWISTED EDWARDS -> WEIERSTRASS
  4. WEIERSTRASS -> TWISTED EDWARDS, but you need $\alpha, \beta$ such that $(\alpha, 0)$ is a 2-torsion point on the Weierstrass elliptic curve and that $3\alpha^2 + a_w = \beta^2$.

Available coordinates for Weierstrass elliptic curve:

  1. PROJECTIVE: (X,Y,Z) matching the affine point (x,y) where x=X/Z, y=Y/Z, the point at infinity is (0,1,0)
  2. JACOBIAN: (X,Y,Z) matching the affine point (x,y) where x=X/Z^2, y=Y/Z^3, the point at infinity is (a^2,a^3,0) with a!=0

Available coordinates for Twisted Edwards elliptic curve:

  1. PROJECTIVE: (X,Y,Z) matching the affine point (x,y) where x=X/Z, y=Y/Z, the point at infinity is (0,1,0)
  2. EXTENDED_EDWARDS: (X,Y,T,Z) matching the affine point (x,y) where x=X/Z, y=Y/Z, and the coordinate T should verify that T=XY/Z, the point at infinity is (0,1,0,1).

Available coordinates for extended Jacobi Quartic elliptic curve:

  1. EXTENDED_HOMOGENEOUS_PROJECTIVE (X,Y,T,Z) matching the affine point (x,y) where x=X/Z, y=Y/Z and the coordinate T should verify that X^2=TZ, the point at infinity is (0,1,0,1).

Curve can be given manually giving

  1. "a" and "b" coefficients for a Weierstrass Elliptic Curve
  2. "a" coefficient for an extended Jacobi Quartic Elliptic Curve (with d=1)
  3. "a" and "b" (instead of d) coefficients for a Twisted Edwards Elliptic Curve
  4. G, base point on the curve
  5. n, the order of G
  6. h, the cofactor of n

Some known curves are hardcoded and can be setup by their names (eg: FR_256, BRAINPOOL_512, NIST_521, ...).

This library can be used on Linux operating system (x86, 32 and 64 bits), on ARM 32 bits (tested on Raspberry Pi 2) and on microcontroller (tested on STM32F4).

Modular arithmetic

The modular (field level) arithmetic is either managed by

The Adapted Modular Number System (AMNS) code uses strongly the thesis of Fangan-Yssouf Dosso: Contribution de l’arithmétique des ordinateurs aux implémentations résistantes aux attaques par canaux auxiliaires, 2020. And the paper: Efficient modular operations using the adapted modular number system. Journal of Cryptographic Engineering, Springer, 2020. from Pascal Véron. Laurent-Stéphane Didier, Fangan-Yssouf Dosso. The AMNS is especially well fitting for current elliptic curve prime size on 64 bits target when 128 bits integer are available. In this case we set up AMNS as default. When AMNS is used, GMP is still needed for conversion from classical form to AMNS but no arithmetic operation is done using GMP. Some AMNS have been hardcoded for some known elliptic curves, but often many AMNS can be use for a same prime field. The AMNS format used by MPHELL is the one given by the AMNS generator provided here AMNS Generator. MPHELL is able to parse the resulting string from this generator to use the given AMNS. AMNS become less efficient for curve with prime field size higher than 384 bits. If you mainly use curve of 512 bits or more, it can be interresting to disable AMNS.

GMP (without AMNS), is generic and gives for instance the best compromise on a raspberry PI 4 (ARM 64 bits)

IPP can be faster for some NIST curves, but for x86 only.

MbedTLS is interresting on stm32 microcontroller (dedicated ASM), but suprinsingly AMNS gives also good performances on this target. MbedTLS version must be higher than 2.11 and stricly lower than 3.0 (version 3 change of API).

When GMP or MbedTLS is used for the big number arithmetic, the field arithmetic is then build over this big number arithmetic. We can choose (at configure time) to use either a

  • Classical modular arithmetic
  • Montgomery arithmetic (default because it is faster)

Finite fields

Available finite fields are

  • FP, primary field of characteristic a prime number p
  • FP2, quadratic extension of characteristic a prime number p and order p^2. The irreduciple polynomial must me on the form (X^2 - a) where a is a non-square residue in FP.
  • FP3, cubic extension of characteristic a prime number p and order p^3. The irreduciple polynomial must me on the form (X^3 - a) where a is a non-cubic residue in FP.

Random number generation

MPHELL has a random number generation system in accordance with the "NIST Special Publication 800-90A".

Entropy

The seed (and the nonce) are extrated from one of the entropy source available in MPHELL:

  • /dev/urandom a non blocant entropy source, can be of poor quality
  • /dev/random a blocant entropy source, can be slow, consider installing HAVEGED to increase the entropy throughput
  • RDSEED instruction, available since Broadwell ("5th-generation Core" of the Intel Core processors)

Deterministic Random Bit Gerenators

Two types of DRBG are supported in MPHELL:

  • HASH-DRBG using:
    • SHA1 hash function, can be used for a security strength <= 128 bits
    • SHA256 hash function, can be used for a security strength <= 256 bits
    • SHA512 hash function, can be used for a security strength <= 256 bits
  • CTR-DRBG using:
    • AES-128 block cipher, can be used for a security strength <= 128 bits
    • AES-192 block cipher, can be used for a security strength <= 192 bits
    • AES-256 block cipher, can be used for a security strength <= 256 bits

If –enable-vectorization=yes then MPHELL uses the AES NI instructions set.

Default parameters

The following parameters are used by MPHELL when using its own DRBG:

  • The nonce is extracted from the entropy source of size (entropy length / 2)
  • The personalization string is NULL
  • The additional input when reseeding is NULL
  • The additional input when generating random bytes is NULL
  • The reseed interval is 2^20 = 1048576, provides only Backtracking resistance (must be 1 to provide Prediction Resistance).

Random Generator using their own entropy source

Two types of Random Generator using their own entropy source are available in MPHELL:

  • RDRAND instruction, available since Ivy Bridge ("third generation" of the Intel Core processors)
  • The stm32f4 generator, if MPHELL is running on the microcontroller

Test

The 15 tests made by the the NIST sts program, have been passed by all the combination of MPHELL entropy and DRBG availables. In order to fullfill the requirements of all the tests we used the following parameters:

  • The bitstream length n = 10^6
  • The number of bitstreams = 100
  • All the other test parameters are the default proposed by the NIST program

The DRBG (both HASH-DRBG and CTR-DRBG) are tested with the NIST vector tests while running "make check"

Temporary memory

In order to avoid multiple system calls (malloc, free, ...) we use some temporary memory stacks and some pools of already initialised field elements.

  • To allocate an element (number) on the stack use the functions *_tmp_alloc(...)
  • To get an element (field_elt, ec_point) from the pool use the functions *_get_pool_elt(...)
  • To free an element on the stack use the functions *_tmp_free(...)
  • To release an element from the pool use the functions *_relax_pool_elt(...)

  • BEWARE: Element on the stack should be free in the reverse order than their allocation:

    • alloc(a), alloc(b), operations, free(b), free(a) -> OK
    • alloc(a), alloc(b), operations, free(a), use b, free(b) -> ERROR because a stack is a stack !

  • Use STACK_1 everywhere you do not need to parallelise
  • Use STACK_2 in a parallelised function
  • For the moment only 2 stacks are available, contact us if your application needs more, we can consider to add others stacks.

Multithreading

In order to use MPHELL in different threads you must:

  • Configure with: –enable-multithreading=yes
  • Use the MPHELL functions with a different memory stack (STACK_1, STACK_2, ...) for each thread

Requirement

    • GMP version 6.0.0 or higher, for big number arithmetic OR
    • IPP version 2020.0.0 or higher, for field arithmetic OR
    • MbedTLS version 2.11.0 or higher, for big number arithmetic

  2. doxygen and graphviz for the documentation

Installation (on x86 architecture)

If you got MPHELL from the git repository run (require autoconf, automake, libtool): autoreconf --i

Keep your sources directory clean

We advide to create a directory: mkdir obj_dir && cd obj_dir

then run configure from there using ../configure instead of ./configure

Installation with AMNS and GMP if GMP is installed in /usr/ or /usr/local/

Run the classical commands:

  1. ./configure --enable-gmp
  2. make
  3. make check
  4. make install (need the root rights to install in /usr/local)

Installation with AMNS and GMP installed elsewhere

If GMP is install in /path/to/gmp, run the commands:

  1. ./configure --enable-gmp --with-gmp=/path/to/gmp
  2. make
  3. make check
  4. make install (need the root rights to install in /usr/local)

Installation with IPP

If ipp-crypto is install in /path/to/ipp-crypto (ex: /home/softs/ipp-crypto), run the commands:

  1. ./configure --enable-ipp --with-ipp=/path/to/ipp-crypto (ex: ./configure --enable-ipp --with-ipp=/home/softs/ipp-crypto)
  2. make
  3. make check
  4. make install (need the root rights to install in /usr/local)

Installation with GMP if GMP is installed in /usr/ or /usr/local/

Run the classical commands:

  1. ./configure --enable-gmp --enable-amns=no
  2. make
  3. make check
  4. make install (need the root rights to install in /usr/local)

Installation with GMP installed elsewhere

If GMP is install in /path/to/gmp, run the commands:

  1. ./configure --enable-gmp --with-gmp=/path/to/gmp --enable-amns=no
  2. make
  3. make check
  4. make install (need the root rights to install in /usr/local)

Installation with MbedTLS if MbedTLS is installed in /usr/ or /usr/local/

MbedTLS version must be higher than 2.11 and stricly lower than 3.0 (version 3 change of API).

Run the classical commands:

  1. ./configure --enable-mbedtls
  2. make
  3. make check
  4. make install (need the root rights to install in /usr/local)

Installation with MbedTLS installed elsewhere

If MbedTLS is install in /path/to/mbedtls, run the commands:

  1. ./configure --enable-mbedtls --with-mbedtls=/path/to/mbedtls
  2. make
  3. make check
  4. make install (need the root rights to install in /usr/local)

Configure options

Default values are in uppercase.

  1. --enable-amns=YES/no (AMNS is set as default if GMP is used and 128 bits integer are available)
  2. --enable-amns_32=yes/NO (Use 32 bits AMNS, it is very slow and often better to use an other arithmetic, only interesting on STM32 microcontroller)
  3. --enable-optimisation=YES/no (Use -O3)
  4. --enable-vectorization=YES/no (Use -march=native and AES NI instructions set)
  5. --enable-montgomery=YES/no, use Montgomery arithmetic (for GMP and MbedTLS only).
  6. --enable-multithreading=yes/NO (Allow to use STACK_1 and STACK_2 for temporary memory, for GMP only)
  7. --enable-debug=yes/NO (add -g and, remove -DNDEBUG, and enable MPHELL_USE_ASSERT)
  8. --enable-valgrind=yes/NO, create a target in test/ to run make check-valgrind
  9. --help gives other informations (especially for external package paths)

Cross-Compilation (for STM32F4)

Toolchain

A toolchain for bare metal compilation is available here: arm-none-eabi toolchain

You can add the path of your toolchain binaries to the PATH environnement variable with: export PATH=$PATH:/path/to/toolchain/bin

MPHELL with AMNS and GMP (good performances)

Despite the not optimize 32 bits AMNS for ECC field size, it gives some goop performances on STM32F4

GMP Cross Compilation

  1. ./configure CC=arm-none-eabi-gcc CFLAGS="-nostartfiles --specs=nosys.specs -mcpu=cortex-m4" --host=arm-none-eabi --disable-assembly --prefix=your-bare-metal-gmp-location
  2. make
  3. make install

MPHELL Cross Compilation

  1. CC=arm-none-eabi-gcc ./configure --host=arm-none-eabi --prefix=your-bare-metal-mphell-location --enable-gmp --with-gmp=your-bare-metal-gmp-location --enable-vectorization=no --enable-amns --enable-amns_32
  2. make
  3. make install

MPHELL with MbedTLS (faster than GMP alone, but slower than AMNS and GMP)

MbedTLS provides a fast arithmetic on the NIST curves for the STM32F4 compare to GMP. However the good performances of AMNS on STM32F4 are now better on all the curves. However AMNS uses quite some memory space, and MbedTLS can be better on this point.

MbedTLS Cross Compilation

The sources of MbedTLS can be included in your project Makefile, and be crosscompiled with your project. These sources are in the repository Middlewares/Third_Party/ if you activated "mbedTLS" in the STM32CubeMX code generator.

MPHELL Cross Compilation

On the same scheme than MbedTLS, you can add the sources of MPHELL to your project Makefile and crosscompile it with your project. We provide here a source directory with MPHELL configured for MbedTLS to paste in your Middlewares/Third_Party/ directory.

Used formulas for elliptic curves

Weiestrass elliptic curves

Jacobi Quartic elliptic curves

Edwards elliptic curves

Conversion between Weiestrass and Jacobi Quartic elliptic curves

Conversion between Short Weierstrass Curve Model and Twisted Edwards Curves Model

Tutorials

All tutorial can be compile with gcc mphell_tuto_fp.c \
-I/your-gmp-location/include \
-L/your-gmp-location/lib \
-lgmp \
-I/your-mphell-location/include \
-L/your-mphell-location/lib \
-Wl,-rpath=your-mphell-location/lib \
-lmphell \
-o tuto_fp

by replacing mphell_tuto_fp.c and tuto_fp by the tutorial you want to compile.

Field arithmetic

FP

Look at mphell_tuto_fp.c

FP2

MPHELL handle only quadratic field extension over FP, with irreducible polynomial x^2-a where a is a non square in FP

Look at mphell_tuto_fp2.c

FP3

MPHELL handle only cubic field extension over FP, with irreducible polynomial x^3-a where a is a non cubic element in FP

Look at mphell_tuto_fp3.c

Random

One time MPHELL is instantiated, MPHELL provides functions to get random elements, at

  1. Number level
  2. Field level (FP, FP2, FP3)
  3. Curve level (Weierstrass, Jacobi quartic, Edwards)

The following tutorials are only to understand, and evaluate the underlying random process

DRBG use

Look at mphell_tuto_drbg.c

Random use

Look at mphell_tuto_random.c

Elliptic curves

Weierstrass

Look at mphell_tuto_weierstrass.c

Jacobi Quartic

Look at mphell_tuto_jacobi_quartic.c

Edwards

Look at mphell_tuto_edwards.c

ECDSA

Look at mphell_tuto_ecdsa.c or

Add -fopenmp to the compilation line (the signature verification is parallelised), verify that MPHELL was configure with "--enable-multithreading=yes" and

Look at mphell_tuto_ecdsa_fips.c

Bugs report

In case of problem using MPHELL, thanks to:

  1. Configure MPHELL with the option --enable-debug=yes, then make clean, make check, make install.
  2. If the make check does not work, attach a copy of test-suite.log (in test/ directory) to your email
  3. If your program reveal a new bug, isolate if possible the bug and attach an easy C program to your email
  4. Precise your OS (Linux are the only tested OS), and your processor specification (cat /proc/cpuinfo)
  5. Send your email at mphell@univ-grenoble-alpes.fr

Benchmarks

Benchmark on x86 64 bits

The benchmarks are made on a x86_64 architecture with an Intel Core i7-4790 CPU 3.60GHz × 8.

MPHELL uses some unified operations (slower) for the signatures to make it resistant to SPA, it's not the case for the others.

MPHELL uses some dedicated operations and some precomputation technics for the verification to make it faster.

Comparison between MPHELL (using AMNS) and other softs for ECDSA signatures
Comparison between MPHELL (using AMNS) and other softs for ECDSA verification

Benchmark on STM32F4

Comparison between MPHELL and MbedTLS for ECDSA signatures

MbedTLS is faster for the signature because MPHELL uses a SPA resistant scalar multiplication (and not a windows one). Moreover MbedTLS has a dedicated arithmetic for the nist curves which is not implemented in MPHELL (except the NIST 521 which got a specially good AMNS).

Comparison between MPHELL and MbedTLS for ECDSA verification

MPHELL is faster for the verification because here the security against SPA is not required and we use an efficient sliding windows scalar multiplication. AMNS is efficient on STM32F4 despite the 32 bits restriction.

Benchmark on Raspberry Pi 4

Comparison between MPHELL and MbedTLS for ECDSA signatures

MbedTLS is sometimes faster for the signature because MPHELL uses a SPA resistant scalar multiplication (and not a windows one). Moreover MbedTLS has a dedicated arithmetic for the nist curves which is not implemented in MPHELL. AMNS cannot use 128 bits integers here and is slow.

Comparison between MPHELL and MbedTLS for ECDSA verification

MPHELL is faster for the verification because here the security against SPA is not required and we use an efficient sliding windows scalar multiplication.

Generated by doxygen 1.9.1