Copyright (C) 2017
This software is licensed under a dual BSD and GPL v2 license. See LICENSE file at the root folder of the project.
- Ryad BENADJILA (mailto:[email protected])
- Arnaud EBALARD (mailto:[email protected])
- Jean-Pierre FLORI (mailto:[email protected])
- Nicolas VIVET (mailto:[email protected])
- Karim KHALFALLAH (mailto:[email protected])
- Niels SAMWEL (mailto:[email protected])
This software implements a library for elliptic curves based cryptography (ECC). The API supports signature algorithms specified in the ISO 14888-3:2016 standard, with the following specific curves and hash functions:
- Signatures: ECDSA, ECKCDSA, ECGDSA, ECRDSA, EC{,O}SDSA, ECFSDSA.
- Curves: SECP{224,256,384,521}R1, BRAINPOOLP{224,256,384,512}R1, FRP256V1, GOST{256,512}. The library can be easily expanded with user defined curves using a standalone helper script.
- Hash functions: SHA-2 and SHA-3 hash functions (224, 256, 384, 512).
Advanced usages of this library also include the possible implementation of elliptic curve based Diffie--Hellman protocols as well as any algorithm on top of prime fields based elliptic curves (or prime fields, or rings of integers). Compared to other cryptographic libraries providing such features, the differentiating points are:
- A focus on code readability and auditability. The code is pure C99, with no dynamic allocation and includes pre/post-asserts in the code. Hence, this library is a good candidate for embedded targets (it should be easily portable accross various platforms).
- A clean layer separation for all needed mathematical abstractions and operations. Strong typing (as "strong" as C99 allows, of course) of mathematical objects has been used in each layer.
- The library has NOT been designed to break performance records, though it does a decent job (see the performance section discussion). Similarly, the library memory footprint (in terms of ROM and RAM usage) is not the smallest achievable one (though some efforts have been made to limit it and fit "common" platforms, see the dedicated section).
- libecc library core has no external dependency (not even the standard libc library) to make it portable. See the section about portability for more information.
The main Makefile is in the root directory, and compiling is as simple as executing:
$ make
This will compile different elements in the build directory:
- Three archive static libraries, each one containing (based on) the previous ones:
- libarith.a: this library contains the Natural Numbers (NN) and Finite field over primes (Fp) arithmetic layers.
- libec.a: this library is based on libarith.a and contains the EC curves implementation (points abstraction, point addition/doubling formulas and scalar multiplication).
- libsign.a: this library is based on libec.a and contains all our ISO 14888-3 signature algorithms over some statically defined curves and hash functions.
- Two binaries based on the libsign.a static library:
- ec_self_tests: the self tests for signature/verification algorithm of ISO 14888-3 with known and random test vectors, as well as performance tests. Launching the self tests without an argument will execute the three tests (known and fixed test vectors, random sign/verify checks, and performance measurements). One can also launch each test separately.
For known test vectors:
$ ./build/ec_self_tests vectors ======= Known test vectors test =================== [+] ECDSA-SHA224/secp224r1 selftests: known test vectors sig/verif ok [+] ECDSA-SHA256/secp256r1 selftests: known test vectors sig/verif ok [+] ECDSA-SHA512/secp256r1 selftests: known test vectors sig/verif ok ...
For sign/verify checks (with random key pairs and random data):
$ ./build/ec_self_tests rand ======= Random sig/verif test =================== [+] ECDSA-SHA224/FRP256V1 randtests: random import/export with sig(0)/verif(0) ok [+] ECDSA-SHA224/SECP224R1 randtests: random import/export with sig(0)/verif(0) ok ...
For performance measurements:
$ ./build/ec_self_tests perf ======= Performance test ===================== [+] ECDSA-SHA224/FRP256V1 perf: 462 sign/s and 243 verif/s [+] ECDSA-SHA224/SECP224R1 perf: 533 sign/s and 276 verif/s ...
- ec_utils: a tool for signing and verifying user defined files, with a user provided signature algorithm/curve/hash function triplet. The tool can also be used to generate signature keys.
Generate keys for ECKCDSA over the BRAINPOOLP512R1 curve, with the 'mykeypair' prefix:
$ ./build/ec_utils gen_keys BRAINPOOLP512R1 ECKCDSA mykeypair
This will create four files. Two binary '.bin' files corresponding to the private key (mykeypair_private_key.bin) and the public key (mykeypair_public_key.bin). Two header '.h' files are also created, corresponding to a C style header version of the keys so that these can be included and used in a C program using libecc. Note that both kind of keys (public and private) include leading metadata (type, algorithm, curve, etc) for possible sanity checks when they are used (e.g. to detect passing of an ECDSA private key to an ECKCDSA signature call, etc).
Once the key pair has been created, one can sign a raw binary file named 'myfile' and store the signature in 'sig.bin'. In the example below, we use SHA3_512 as the hash function for the signature. BRAINPOOLP512R1 and ECKCDSA are explicitly given (matching the type of key we generated during previous step). Note that the call would yield an error if invalid parameters were given (thanks to the metadata elements described above).
$ ./build/ec_utils sign BRAINPOOLP512R1 ECKCDSA SHA3_512 myfile mykeypair_private_key.bin sig.bin
After this, a raw signature is created, mainly consisting of the ECKCDSA (r, s) big numbers concatenated (the length of this file should be 1024 bits = 2 x 512 bits). The signature can now be verified with the 'verify' command and the public key, the result being either OK or failed:
$ ./build/ec_utils verify BRAINPOOLP512R1 ECKCDSA SHA3_512 myfile mykeypair_public_key.bin sig.bin Signature check of myfile OK
The ec_utils tool can also be used to produce/verify structured binaries containing a header, raw binary and their signature (see the 'struct_sign' and 'struct_verify' commands for a help on this mode). The rationale behind these commands is to ease the production/verification of self-contained signed images (which can be useful when dealing with embedded firmware updates for instance).
Since it is possible to use libecc as a NN (positive Natural Numbers), Fp (Finite field over primes) or EC curve layer library, we provide some examples in the src/examples folder. Compiling these examples is as simple as:
$ cd src/examples $ make
-
NN layer examples:
- src/examples/nn_miller_rabin.c: this example implements the Miller-Rabin composition (or probabilistic primality) test as described in the Handbook of Applied Cryptography (4.29).
- src/examples/nn_pollard_rho.c: this example is a straightforward implementation of the Pollard's Rho integer factorization algorithm as specified in the Handbook of Applied Cryptography (3.9).
-
Fp layer examples:
- src/examples/fp_square_residue.c: this is an implementation of the Tonelli-Shanks algorithm for finding quadratic residues over a prime field Fp. Given a prime field element x, the algorithm finds y so that y2 = x (or informs that there is no solution if this is the case).
-
Curves layer examples:
-
src/examples/curve_basic_examples.c: this example shows basic features of libec for playing with elliptic curves group arithmetic, namely loading defined named curves, generating random points on these curves, checking point addition and doubling formulas as well as scalar multiplication (both Montgomery and non Montgomery based).
-
src/examples/curve_ecdh.c: the purpose of this code is to provide a toy example of how to implement an Elliptic Curve Diffie-Hellman protocol between two entities 'Alice' and 'Bob' in order to produce a shared secret over a public channel.
-
WARNING: these examples are toy implementations not to be used in a production environment (for instance, the code has neither been designed to be efficient nor robust against side channel attacks). Their purpose is only to show basic usage of the libarith and libec libraries.
The public headers containing the functions to be used by higher level code are src/libarith.h, src/libec.h and src/libsig.h: they are respectively used for the NN and Fp arithmetic layers, the Elliptic Curves layer, and the signature layer.
libecc is provided with arithmetic random tests for the low level NN and Fp routines (addition, subtraction, logical operations, multiplication and Montgomery multiplication, ...).
These tests are located inside the src/arithmetic_tests/ folder. More specifically, the tests are split in two files:
- src/arithmetic_tests/arithmetic_tests.c: a '.c' file to be compiled and linked with libecc static library and performing a set of tests given on the standard input or in a file. The tests have a specific ASCII format with expected input/output as big numbers, and crafted opcodes defining the operation type (addition over NN, over Fp, ...).
- src/arithmetic_tests/arithmetic_tests_generator.py: a python script that generates a set of arithmetic tests.
libecc can be statically configured at compilation time: the user can tune what curves, hash functions and signature algorithms are embedded in 'libsign.a' and all the binaries using it.
The main entry point to configure/tune the library is src/lib_ecc_config.h. By default libecc
embeds everything. In order to remove something, one has to comment the element to remove (i.e. comment the
WITH_XXX macro). For instance, removing
FRP256V1 is simply done by commenting the line:
/* Supported curves */ /* #define WITH_CURVE_FRP256V1 */ /* REMOVING FRP256V1 */ #define WITH_CURVE_SECP192R1 #define WITH_CURVE_SECP224R1 #define WITH_CURVE_SECP256R1 #define WITH_CURVE_SECP384R1 #define WITH_CURVE_SECP521R1 #define WITH_CURVE_BRAINPOOLP224R1 #define WITH_CURVE_BRAINPOOLP256R1 #define WITH_CURVE_BRAINPOOLP384R1 #define WITH_CURVE_BRAINPOOLP512R1 #define WITH_CURVE_GOST256 #define WITH_CURVE_GOST512 ...
As another example, if one wants to build a custom project supporting only ECFSDA using SHA3-256 on BrainpoolP256R1, this can be done by keeping only the following elements in src/lib_ecc_config.h:
#define WITH_SIG_ECFSDSA #define WITH_HASH_SHA3_256 #define WITH_CURVE_BRAINPOOLP256R1
libecc supports 16, 32 and 64 bits word sizes. Though this word size is usually inferred during compilation and adapted depending on the detected platform (to fit the best performance), the user can force it in three ways:
- Overloading the
WORDSIZEmacro in src/words/words.h. - Overloading the
WORDSIZEmacro in the MakefileCFLAGS. - Use specific Makefile targets.
Please refer to the portability guide for details on this.
libecc infers the Natural Numbers maximum length from the curves parameters that have been statically defined in src/lib_ecc_config.h. Though this behaviour is perfectly fine and transparent for the user when dealing with the elliptic curves and signature layers, this can become a limitation when building code around the NN and Fp arithmetic layers. The user will be stuck with a hard coded maximum size of numbers depending on the curve that is used by libecc, which can be a nonsense if he is only interested in the big number basic algorithmic side (when the default curves are used, this maximum size is 521 bits, corresponding to SECP521 parameters).
libecc provides a way to overload the NN maximum size, with a strong limit depending on the word size (around
5300 bits for 64-bit words, around 2650 bits for 32-bit words, and around 1300 bits for 16-bit words). See
the comments in src/nn/nn_config.h for more details about this. In order to manually increase
the NN size, the user will have to define the macro USER_NN_BIT_LEN, either directly in
src/nn/nn_config.h, or more appropriately through overloading the Makefile CFLAGS
with -DUSER_NN_BIT_LEN= (see the dedicated section for more on how to do this).
NOTE: objects and binaries compiled with different word sizes and/or user defined NN maximum bit lengths are not compatible,
and could produce executables with dangerous runtime behaviour. In order to prevent possible honest mistakes, there is
a safety net function catching such situations at compilation time in src/nn/nn_config.h: the
nn_check_libconsistency routine will throw an error. For instance, if 'libarith.a' has been compiled with
WORDSIZE=64, and one tries to compile the arithmetic tests with WORDSIZE=32, here is the error the compiler
should produce:
... arithmetic_tests.c:(.text+0x3af21) : undefined reference to « nn_consistency_check_maxbitlen521wordsize32 » ...
Though libecc has been designed to be compiled with a static embedding of all its features (i.e. no dynamic modules loading), its static code extensibility has been a matter of attention. The library can be:
- Easily expanded by adding new curves, with zero coding effort. Note that only curves over prime fields are supported.
- Expanded with new hash functions and new signature algorithms with some coding effort, but clean and well defined APIs should ease this task.
A companion python script scripts/expand_libecc.py will transparently add (and remove) new user defined curves in the source tree of the project. The '.h' headers defining the new curves will be created in a dedicated folder: src/curves/user_defined/.
The python script should have a self explanatory and complete help:
$ python scripts/expand_libecc.py -h This script is intented to *statically* expand the ECC library with user defined curves. ...
In order to add a curve, one can give explicit parameters (prime, order, ...) on the command line or
provide a RFC3279 formatted ASN.1 file (DER or PEM) with the
parameters. Sanity checks are performed by the script. The script is also able to generate
test vectors for the new curve with the --add-test-vectors toggle.
Let's show how we can add the BRAINPOOLP320R1 supported by OpenSSL. We use the ecparam option of
the openssl command line:
$ openssl ecparam -param_enc explicit -outform DER -name brainpoolP320r1 -out brainpoolP320r1.der
This creates a DER file 'brainpoolP320r1.der' embedding the parameters (beware of the -param_enc explicit
option that is important here). Now, in order to add this new curve to libecc, we will execute:
$ python scripts/expand_libecc.py --name="mynewcurve" --ECfile=brainpoolP320r1.der --add-test-vectors=1 Test vectors generation asked: this can take some time! Please wait ... 1/56
This will create a new header file 'ec_params_user_defined_mynewcurve.h' in the src/curves/user_defined/ folder, and it will modify some libecc core files to transparently add this curve for the next compilation (modified files are src/curves/curves_list.h, src/tests/ec_self_tests_core.h, src/lib_ecc_config.h and src/lib_ecc_types.h).
The test vectors generation can take some time since all the possible triplets (curve, hash function, signature algorithm) are processed with the new curve.
After compiling the library, the new curve should show up in the self tests:
$ ./build/ec_self_tests ======= Known test vectors test ================= ... [+] ECDSA_SHA224_USER_DEFINED_MYNEWCURVE_0 selftests: known test vectors sig/verif ok ... ======= Random sig/verif test =================== ... [+] ECDSA-SHA224/USER_DEFINED_MYNEWCURVE randtests: random import/export with sig/verif ok ... ======= Performance test ======================== ... [+] ECDSA-SHA224/USER_DEFINED_MYNEWCURVE perf: 269 sign/s and 141 verif/s ...
It should also appear in the ec_utils help:
$ ./build/ec_utils sign Bad args number for ./build/ec_utils sign: arg1 = curve name: FRP256V1 USER_DEFINED_MYNEWCURVE ... arg2 = signature algorithm type: ECDSA ... arg3 = hash algorithm type: SHA224 ... arg4 = input file to sign arg5 = input file containing the private key (in raw binary format) arg6 = output file containing the signature
It is possible to remove a user defined curve by using the python script and its name:
$ python scripts/expand_libecc.py --remove --name mynewcurve You asked to remove everything related to user defined mynewcurve curve. Enter y to confirm, n to cancel [y/n]. y Removing user defined curve mynewcurve ...
It is also possible to remove all the user defined curves at once:
$ python scripts/expand_libecc.py --remove-all
Finally, two companion shell scripts are provided along with the expanding python script in order to show its basic usage:
- scripts/gen_curves_tests.sh: this script generates the default libecc curves with explicit parameters given on the command line. Of course, since these curves are already embedded in libecc, there is no real use of generating them - the script is only here to serve as a showcase for expanding the library with explicit parameters.
- scripts/gen_openssl_curves_tests.sh: this script enumerates all OpenSSL named curves, generates a DER file with their parameters, and adds them to libecc.
Obviously, adding new algorithms (hash or signature) will require adding new code.
We detail hereafter the necessary steps to add a new hash function. The main file listing all the hash functions is src/hash/hash_algs.h. The new hash
algorithm should be added here in compliance with the API described in the hash_mapping struct. This API includes:
- The digest and block sizes and a pretty print name for the algorithm.
hfunc_init: the hash function initialization routine.hfunc_update: the hash function update routine.hfunc_finalize: the hash function finalization routine.hfunc_scattered: this function applies the hash function (i.e. compute the digest) on multiple messages (it takes as input an array of pointers to message chunks, and an array of sizes).
These libecc API functions are in fact redirections to the core routines of the hash algorithm, and the user is expected to add the specific implementation in '.c' and '.h' files inside the src/hash/ folder. See src/hash/sha224.c and src/hash/sha224.h for a practical example of how to do this with SHA-224.
Finally, the user is expected to update the libecc main configuration file src/lib_ecc_config.h
with the WITH_MY_NEW_HASH toggle ('my_new_hash' being the new hash function).
In order to add a new elliptic curve based signature algorithm, here is the needed work:
- The main file listing all the signature algorithms is src/sig/sig_algs_internal.h.
The signature algorithm should be added in compliance with the API described in the
ec_sig_mapping struct. This API includes:- The signature type and a pretty print name.
siglen: a function giving the length of the produced signature.init_pub_key: a routine producing a public key when given a corresponding private key.sign_init,sign_updateandsign_finalize: the usual functions initializing a signature, updating it with input buffers, and finalizing it to produce an output signature.verify_init,verify_updateandverify_finalize: the usual functions initializing a signature verification, updating it with input buffers, and finalizing it to produce a check status (i.e. signature OK or not OK).
These libecc APIs have to be plugged to the core signature functions, and the user is expected to handle this implementation with adding the specific '.c' and '.h' files inside the src/sig folder. See src/sig/ecdsa.c and src/sig/ecdsa.h for a practical example of how to do this with ECDSA.
Finally, the user is expected to update the libecc main configuration file src/lib_ecc_config.h
with the WITH_MY_NEW_SIGN_ALG toggle ('my_new_sign_alg' being the new signature algorithm).
As already stated, libecc has not been designed with performance in mind, but with simplicity and portability as guiding principles; this implies several things when it comes to performance:
- libecc does not intend to compete with libraries developed with platform specific accelerations, such as the use of assembly routines or the adaptation to CPUs quirks at execution time (e.g. a CPU with very slow shift instructions). OpenSSL is an example of such libraries with good and homogeneous performance in mind on most heterogeneous platforms (with the lack of portability on very small embedded platforms though).
- Some algorithmic tricks on specific prime curves are not implemented: the same algorithms are used for all the curves. This means for instance that curves using pseudo-Mersenne primes (such as NIST's SECP curves) won't be faster than curves using generic random primes (such as Brainpool curves), though pseudo-Mersenne primes can benefit from a dedicated reduction algorithm, yielding orders of magnitude faster field arithmetic (around five to ten times faster). See here for further discussions on this. Consequently, we will only focus on performance comparison with other libraries using the Brainpool curves.
- We use a very straightforward elliptic curve arithmetic implementation, without using literature generic algorithmic optimizations such as windowing or fixed-base comb precomputations.
Nonetheless and despite all these elements, libecc is on par with some other general purpose and portable cryptographic libraries such as mbedTLS (see the performance figures given below).
We present hereafter the ECDSA performance comparison of libecc with mbedTLS and OpenSSL on various platforms representing different CPU flavours. Here are some information about the tested version when not stated otherwise:
- mbedTLS: stable version 2.4.2, the figures have been gathered with the builtin benchmark.
- OpenSSL: debian packaged version 1.1.0e. Since OpenSSL builtin ECDSA benchmark does not handle Brainpool curves, a basic C code using "named curves" have been compiled against the installed dynamic library.
- Core i7-5500U (Broadwell family) is a typical x86 mid-range current laptop CPU.
- Xeon E3-1535M (Skylake family) is a typical x86 high-end CPU.
- Power-7 is a typical server CPU of the previous generation (2010) with a PowerPC architecture.
For all the platforms in this subsection, the CPUs have been tested in 64-bit mode.
| libecc | Core i7-5500U @ 2.40GHz | Xeon E3-1535M v5 @ 2.90GHz | Power-7 |
|---|---|---|---|
| BP256R1 | 583 sign/s - 300 verif/s | 700 sign/s - 355 verif/s | 213 sign/s - 110 verif/s |
| BP384R1 | 231 sign/s - 118 verif/s | 283 sign/s - 150 verif/s | 98 sign/s - 50 verif/s |
| BP512R1 | 111 sign/s - 56 verif/s | 133 sign/s - 68 verif/s | 51 sign/s - 26 verif/s |
| mbedTLS | Core i7-5500U @ 2.40GHz | Xeon E3-1535M v5 @ 2.90GHz | Power-7 |
|---|---|---|---|
| BP256R1 | 426 sign/s - 106 verif/s | 552 sign/s - 141 verif/s | 178 sign/s - 45 verif/s |
| BP384R1 | 239 sign/s - 56 verif/s | 322 sign/s - 77 verif/s | 44 sign/s - 23 verif/s |
| BP512R1 | 101 sign/s - 26 verif/s | 155 sign/s - 34 verif/s | 38 sign/s - 12 verif/s |
| OpenSSL | Core i7-5500U @ 2.40GHz | Xeon E3-1535M v5 @ 2.90GHz | Power-7 |
|---|---|---|---|
| BP256R1 | 2463 sign/s - 1757 verif/s | 2873 sign/s - 2551 verif/s | 1879 sign/s - 1655 verif/s |
| BP384R1 | 1091 sign/s - 966 verif/s | 1481 sign/s - 1265 verif/s | 792 sign/s - 704 verif/s |
| BP512R1 | 727 sign/s - 643 verif/s | 1029 sign/s - 892 verif/s | 574 sign/s - 520 verif/s |
- Marvel Armada A388 is a good representative of moderately constrained embedded devices, such as IAD (Internet Access Devices), NAS (Network Attached Storage), STB (Set Top Boxes) and smartphones. This SoC is built around a Cortex-A9 ARMv7-A 32-bit architecture.
- BCM2837 is a Broadcom SoC built around the recent 64-bit ARMv8-A architecture, with a Cortex-A53 core. This SoC can be found in the Raspberry Pi 3, and also represents what can be found in recent Smartphones.
- Atom D2700 is a small x86 CPU typically embedded in NAS devices. Though its "embedded" coloration, it uses a 64-bit mode that we have tested here.
| libecc | Marvell A388 @ 1.6GHz | BCM2837 (aarch64) @ 1.2GHz | Atom D2700 @ 2.13GHz |
|---|---|---|---|
| BP256R1 | 64 sign/s - 33 verif/s | 43 sign/s - 22 verif/s | 68 sign/s - 35 verif/s |
| BP384R1 | 24 sign/s - 12 verif/s | 17 sign/s - 9 verif/s | 25 sign/s - 13 verif/s |
| BP512R1 | 11 sign/s - 5 verif/s | 8 sign/s - 4 verif/s | 12 sign/s - 6 verif/s |
| mbedTLS | Marvell A388 @ 1.6GHz | BCM2837 (aarch64) @ 1.2GHz | Atom D2700 @ 2.13GHz - |
|---|---|---|---|
| BP256R1 | 33 sign/s - 8 verif/s | 14 sign/s - 4 verif/s | 87 sign/s - 22 verif/s |
| BP384R1 | 20 sign/s - 4 verif/s | 8 sign/s - 2 verif/s | 50 sign/s - 11 verif/s |
| BP512R1 | 10 sign/s - 2 verif/s | 4 sign/s - 1 verif/s | 23 sign/s - 5 verif/s |
| OpenSSL | Marvell A388 @ 1.6GHz | BCM2837 (aarch64) @ 1.2GHz | Atom D2700 @ 2.13GHz |
|---|---|---|---|
| BP256R1 | 369 sign/s - 332 verif/s | 124 sign/s - 112 verif/s | 372 sign/s - 334 verif/s |
| BP384R1 | 102 sign/s - 94 verif/s | 54 sign/s - 49 verif/s | 163 sign/s - 149 verif/s |
| BP512R1 | 87 sign/s - 81 verif/s | 31 sign/s - 29 verif/s | 92 sign/s - 83 verif/s |
The library, when configured for a 256-bit curve (SECP256R1, FRP256), SHA-256 and ECDSA signature fits in around
30 Kilo Bytes of flash/EEPROM, and uses around 8 Kilo Bytes of RAM (stack) with variations depending on the
chosen WORDSIZE (16, 32, 64), the compilation options (optimization for space -Os or speed -O3) and the
target (depending on the instructions encoding, produced binary code can be more or less compact).
A 521-bit curve with SHA-256 hash function and ECDSA signature should fit in 38 Kilo Bytes of flash and around
16 Kilo Bytes of RAM (stack), with the same variations depending on the WORDSIZE and the compilation options.
Note: libecc does not use any heap allocation, and the only global variables used are the constant ones. The
constant data should end up in the flash/EEPROM section with a read only access to them: no RAM memory should
be consumed by these. The libecc read/write data are only made of local variables on the stack. Hence, RAM
consumption (essentially made of arrays representing internal objects such as numbers, point on curves ...)
should be reasonably constant across platforms. However, some platforms using the
Harvard architecture (as opposed to Von Neumann's one)
can have big limitations when accessing so called "program memory" as data. The 8-bit
Atmel AVR MCU
is such an example. Compilers and toolchains for such architectures usually copy read only data in RAM at run time,
and/or provide non-standard ways
to access read only data in flash/EEPROM program memory (through specific macros, pragmas, functions). The
first case means that the RAM consumption will increase for libecc compared to the stack only usage (because of
the runtime copy). The second case means that libecc code will have to be adapted to the platform if the user
want to keep RAM usage at its lowest. In any case, tracking where const qualified data reside will be important
when the amount of RAM is a critical matter.
A full software stack containing a known test vector scenario has been compiled and tested on a Cortex-M0 (STM32F030R8T6 @ 48MHz with 64KB of flash and 8KB of RAM). It has also been compiled and tested on a Cortex-M3 (STM32F103C8T6 @ 72MHz with 64KB of flash and 20KB of RAM). The results of the flash/RAM occupancy are given in the table below, as well as the timings of the ECDSA signature and verification operations.
Note: The Cortex-M0 case is a bit special in the ARM family. Since this MCU lacks a 32-bit x 32-bit to 64-bit multiplication instruction, the multiplication is implemented using a builtin software function. This yields in poor performance with WORDSIZE=64 compared to WORDSIZE=32 (this might be explained by the calling cost to the builtin function).
| libecc | STM32F103C8T6 (Cortex-M3 @ 72MHz) | STM32F030R8T6 (Cortex-M0 @ 48MHz) |
|---|---|---|
| Flash size | 32KB | 30KB |
| RAM size | 8KB | 8KB |
| Sign time | 950ms | 2146ms |
| Verif time | 1850ms | 4182ms |
In order to compare the libecc performance on these embedded platforms, we give figures for mbedTLS on Cortex-M3 taken from a recent study by ARM. As we have previously discussed, only the figures without NIST curves specific optimizations are of interest for a fair comparison:
| mbedTLS | LPC1768 (Cortex-M3 @ 92MHz)1 |
|---|---|
| Flash size | ?? |
| RAM size | 3KB2 |
| Sign time | 1893ms |
| Verif time | 3788ms |
1 Beware of the MCU frequency difference when comparing with libecc test case.
2 This figure only includes heap usage (stack usage is unknown so this is only a rough lower limit for RAM usage).
When dealing with the portability of a program across various platforms, many issues are in fact hidden behind this property. This is due to the very complex nature of what a platform is, namely:
- A core CPU architecture (x86, ARM, MIPS, PowerPC, ...).
- A target OS (Linux, Windows, Mac OS, ...) or more low level firmware (including a bare-metal programming model or exotic real-time OS for microcontrollers for instance).
- A proper compilation (cross-)toolchain producing binaries for the platform. This toolchain will usually include a compiler and a linker, both with possibly specific flags and limitations.
Regarding libecc, here are the main elements to be aware of when dealing with a "new" platform:
- libecc is in pure C-99 (no assembly), so it should compile on any platform with a decent C-99 compatible compiler. The code is endian neutral, meaning that libecc should work on little endian and big endian platforms.
- The Makefile has been tested with clang and gcc under Linux, as well as gcc cross-compilation variants such as mingw for Windows or gcc Mac OS version. In order to adapt the makefile behaviour when the compiler is not gcc/clang compatible, the user can modify the CFLAGS as well as the LDFLAGS by exporting them.
- The library supports 16-bit/32-bit/64-bit word sizes, which should ensure compatibility with most of the platforms
for 8-bit MCUs to 64-bit CPUs. If the toolchain does not have a
stdint.hheader, it is still possible to compile libecc by exporting LIBECC_NOSTDLIB=1: in this case, the code will try to guess and fit to native C types or throw an error so that the user can adapt src/words/types.h to its specific case. - The library core is platform independent. However, when the platform is not recognized (i.e. everything aside UNIX/Windows/Mac OS),
an error is thrown at compilation time asking the user to provide implementations for external dependencies
in src/external_deps/, namely:
- The printing helper in src/external_deps/print.c. This helper serves output debugging purposes.
- The timing helper in src/external_deps/time.c. This helper is used to measure performances of the library in the performance self tests.
- The random helper in src/external_deps/rand.c. This helper is used in the core library for the signature schemes. One should notice that a good random source is crucial for the security of Elliptic Curve based signature schemes, so great care must be taken when implementing this.
Some other external dependencies could arise depending on the compilation chain and/or the platform. Such an example is the implementation of the gcc and clang stack protection option, usually expecting the user to provide stack canaries generation (with random values) and failover behavior.
Compiling for Cortex-M targets should be straightforward using the arm-gcc none-eabi (for bare metal) cross-compiler as
well as the specific Cortex-M target platform SDK. In order to compile the core libsign.a static library, the only thing to do is to execute
the makefile command by overloading CCand the CFLAGS:
$ CC=arm-none-eabi-gcc CFLAGS="$(TARGET_OPTS) -W -Wextra -Wall -Wunreachable-code \ -pedantic -fno-builtin -std=c99 -Os \ -ffreestanding -fno-builtin -nostdlib -DWORDSIZE=64" \ make build/libsign.a
where $(TARGET_OPTS) are the flags specific to the considered target: -mcpu=cortex-m3 -mthumb for Cortex-M3 for example. The word size
flag should be adapted to -DWORDSIZE=32 for the specific case of Cortex-M0/M0+ as discussed in the performance section
(because of the lacking of 32-bit to 64-bit native multiplication instruction). The library can then be used to be linked against a file
containing the main calling function, and the linking part will depend on the
target platform (in addition to the target CPU): one will use the linker scripts provided by the platform/board manufacturer to produce
a firmware suitable for the target (ST for STM32, NXP for LPC, Atmel for SAM, ...).
If the external dependencies have been implemented by the user, it is also possible to build a self-tests binary by adding the
GNU ld linker script specific to the target platform (linker_script.ld in the example below):
$ CC=arm-none-eabi-gcc CFLAGS="$(TARGET_OPTS) -W -Wextra -Wall -Wunreachable-code \ -pedantic -fno-builtin -std=c99 -Os \ -ffreestanding -fno-builtin -nostdlib -DWORDSIZE=64" \ LDFLAGS="-T linker_script.ld" \ make build/libsign.a
NOTE1: By default, the linker scripts share the RAM between heap and stack. Since libecc only uses stack, it is convenient (sometimes necessary, specifically on devices with very constrained RAM, such as Cortex-M0 with 8KB) to adapt the stack base address so that no stack overflow errors occur. These errors can be tricky to detect since they generally produce hard faults silently at run time.
NOTE2: It is up to the user to link against the libc (if standard functions are necessary) or not, but this will obviously influence the program size in flash. As already stated, the libc footprint is not included in the figured that have been given in the performance section.
NOTE3: libecc has also been successfully tested with other non-GNU compilation SDK and toolchains such as Keil MDK configured to use the ARM compiler.
This section is dedicated to giving some more details on how to compile libecc when non-GNU compilers are used (i.e. C compilers that do not support gcc syntax), and/or when compiling with environments that do not provide a GNU make compilation style (this is generally the case for all-in-one IDEs such as Visual Studio or other BSP and SDK provided by proprietary integrated circuits founders and board manufacturers).
As we have already stated, libecc requires a C99 compiler. More specifically, libecc makes use of only four feature of the C99 standard (over the older C89/C90 standard), namely:
- The
long long inttype. - Designated initializers for structures.
- The usage of the
inlinekeyword. - The usage of variadic macros.
Hence, when compiling with a given compiler, one will have to check that the compiler is either fully C99 compliant, or that these four features are at least implemented as extensions. Such details are generally provided by the compiler documentation.
NOTE: if one wants to adapt libecc for compilers where some of the necessary C99 features are missing, here is a big picture of the necessary work:
- The
long long intand structures initializers are used all over libecc code, so they are strong requirements, and would imply deep code modifications. - The
inlinekeyword can be removed in most cases, except in the context of header files where it is used to definestatic inlinefunctions. These functions will have to be moved to '.c' files, and one will have to deal with minor adaptations. - The usage of variadic macros is marginal and can be removed with minimal efforts: these are only used to deal with debug helpers in src/utils.
libecc uses a GNU style Makefile to automate the compilation process. One can however use other compilation environments that are not GNU make compatible by implementing the following guidelines:
- Make the compilation toolchain compile into '.o' objects all the necessary '.c' files in src/nn, src/fp, src/curve, src/sig, src/utils and src/hash.
- Make the compilation toolchain link the necessary object files to generate the static libraries:
libarith.a: °°°°°°°°°°° src/fp/fp_rand.o src/fp/fp_mul.o src/fp/fp_montgomery.o src/fp/fp_mul_redc1.o src/fp/fp_add.o src/fp/fp.o src/fp/fp_pow.o src/nn/nn_mul.o src/nn/nn_mul_redc1.o src/nn/nn_logical.o src/nn/nn.o src/nn/nn_modinv.o src/nn/nn_add.o src/nn/nn_rand.o src/nn/nn_div.o src/utils/print_nn.o src/utils/print_fp.o src/utils/print_keys.o src/utils/print_curves.o src/utils/utils.o
libec.a: °°°°°°°° src/fp/fp_rand.o src/fp/fp_mul.o src/fp/fp_montgomery.o src/fp/fp_mul_redc1.o src/fp/fp_add.o src/fp/fp.o src/fp/fp_pow.o src/nn/nn_mul.o src/nn/nn_mul_redc1.o src/nn/nn_logical.o src/nn/nn.o src/nn/nn_modinv.o src/nn/nn_add.o src/nn/nn_rand.o src/nn/nn_div.o src/utils/print_nn.o src/utils/print_fp.o src/utils/print_keys.o src/utils/print_curves.o src/utils/utils.o src/curves/prj_pt.o src/curves/curves.o src/curves/aff_pt.o src/curves/prj_pt_monty.o src/curves/ec_shortw.o src/curves/ec_params.o
libsign.a: °°°°°°°°°° src/fp/fp_rand.o src/fp/fp_mul.o src/fp/fp_montgomery.o src/fp/fp_mul_redc1.o src/fp/fp_add.o src/fp/fp.o src/fp/fp_pow.o src/nn/nn_mul.o src/nn/nn_mul_redc1.o src/nn/nn_logical.o src/nn/nn.o src/nn/nn_modinv.o src/nn/nn_add.o src/nn/nn_rand.o src/nn/nn_div.o src/utils/print_nn.o src/utils/print_fp.o src/utils/print_keys.o src/utils/print_curves.o src/utils/utils.o src/curves/prj_pt.o src/curves/curves.o src/curves/aff_pt.o src/curves/prj_pt_monty.o src/curves/ec_shortw.o src/curves/ec_params.o src/hash/sha384.o src/hash/sha3-512.o src/hash/sha512.o src/hash/sha3-256.o src/hash/sha3-224.o src/hash/sha3.o src/hash/sha256.o src/hash/sha3-384.o src/hash/sha224.o src/hash/hash_algs.o src/sig/ecsdsa.o src/sig/ecdsa.o src/sig/ecrdsa.o src/sig/ecosdsa.o src/sig/ecfsdsa.o src/sig/eckcdsa.o src/sig/ecgdsa.o src/sig/ecsdsa_common.o src/sig/sig_algs.o src/sig/ec_key.o
Compiling binaries (such as ec_self_tests and ec_utils) is nothing more than compiling concerned '.c' files under src/tests
and linking them with libsign.a.
Some important preprocessor flags are expected to be defined when compiling libecc:
WORDSIZE=: this is a preprocessor flag defining libecc internal words size (16, 32, or 64). By default libecc will detect the best size depending on the platform, but if the platform is not recognized the user is expected to provide this flag.WITH_STDLIB: this flag is used for standard library usage inside libecc. Exporting the environment variableLIBECC_NOSTDLIB=1will trigger the non usage of standard includes and libraries. Standard C library headers and files are used for two things in the project:- Defining standard types through the
stdint.hheader. Though using this header helps libecc to properly define basic types in src/words/types.h, it is not required to use it and some heuristics can be used to define these types without standard headers (see explanations on that in src/words/types.h) comments. - Defining standard library functions used by external dependencies as well as
ec_utils. Compiling withoutWITH_STDLIBflag means that one has to provide these.
- Defining standard types through the
In any case, if the user forgot to provide important preprocessing flags whenever they are necessary, errors will be thrown during
the compilation process. As explained in src/words/types.h, when stdint.h is not used (i.e. WITH_STDLIB
not defined), heuristics are used to guess primitive types sizes. These heuristics can fail and the user will have to adapt the types
definitions accordingly depending on the platform.
When compiling using compilers that are not compatible with the gcc syntax, but still using a GNU make
compilation environment, it is possible to adpat the Makefile behavior. In addition to the LIBECC_NOSTDLIB=1
environment variable previously described, here is the list of the variables that tune the compilation process:
CC: as usual, this overloads the compiler to be used.CFLAGSandLDFLAGS: these flags can be overloaded by user defined ones. The user defined flags will completely shadow the default flags for both the static libraries (libarith.a, libec.a, libsign.a) and the produced binaries.LIB_CFLAGS,BIN_CFLAGS,BIN_LDFLAGS: when one wants to specifically tune compilation and linking flags for the static libraries and the binaries, these flags can be used and they will shadow theCFLAGSandLDFLAGS.ARandRANLIB: these flags override the ar and ranlib tools used to generate the static library archives.
As a simple example of when and how to use this environment variables overloading system, let's take the following case:
one wants to compile libecc with an old version of gcc that does not support the -fstack-protector-strong option
(this is the case for gcc < 4.9). Since this is the flag used by default in
libecc Makefile, an error will be triggered. It is possible to overcome this issue by overloading the CFLAGS with
the following:
$ CFLAGS="-W -Werror -Wextra -Wall -Wunreachable-code -pedantic -fno-builtin -std=c99 -D_FORTIFY_SOURCE=2 \ -fstack-protector-all -O3 -DWITH_STDLIB -fPIC" make
As we can see, we keep the other CFLAGS from default compilation while replacing -fstack-protector-strong with
the less efficient but more compatible -fstack-protector-all.
In addition to compilation flags, it is also possible to overload the library word sizes as well as debug modes through Makefile targets:
make debugwill compile a debug version of the library and binaries, with debugging symbols.make 16,make 32andmake 64will respectively compile the library with 16, 32 and 64 bits word sizes.make debug16,make debug32andmake debug64will compile the debug versions of these.make force_arch32andmake force_arch64will force 32-bit and 64-bit architectures compilation (-m32and-m64flags under gcc). These targets allow cross-compilation for a 32-bit (respectively 64-bit) target under a 64-bit (respectively 32-bit) host: a typical example is compiling for i386 under x86_64.
NOTE: the targets that we have described here can be used in conjunction with overloading the CFLAGS and LDFLAGS. Hence,
a: CFLAGS="-fstack-protector-all" make debug16
will indeed compile all the binaries for debug, with a word size of 16 bits and a -fstack-protector-all stack protection option.
As an example to show how to adapt the compilation process to compilers that are not compatible with the GNU compilers syntax, we will detail how to proceed by exploring the SDCC (Small Device C Compiler) toolchain. Porting libecc to this compiler is interesting for many reasons:
- The SDCC compiler uses some specific syntax, though it shares some similarities with
other compilers (
-cflag to generate object files,-oflag to define output file). - This compiler is "almost" C99 compliant: depending on the target, it has some C99 features partially implemented.
- The compiler has "exotic" targets such as the Zilog Z80 MCU.
We suppose that the user has also provided the external dependecies for print, random and time functions (otherwise explicit errors will be thrown).
We will show how overloading the Makefile flags can be of use in this case. Say that we want
to compile libecc in order to embed it in a Game Boy ROM. The Game Boy console uses a proprietary
version of the Z80 MCU supported by SDCC under the target name gbz80.
Hence, a first attempt at compilation would be to:
- Overload
CC=sdccto change the default compiler. - Overload
AR=sdarandRANLIB=sdranlibto overload the archives handling binaries (they are specific to SDCC). - Overload
CFLAGS="-mbgz80 --std-sdcc99"to specify the target, and ask for the C99 compatibility mode. - Overload
LDFLAGS=" "with nothing since we do not want default gcc linking flags to break compilation.
This first attempt will trigger an error:
$ CC=sdcc AR=sdar RANLIB=sdranlib CFLAGS="-mgbz80 --std-sdcc99" LDFLAGS=" " make ... src/external_deps/../words/words.h:62:2: error: #error "Unrecognized platform. \ Please specify the word size of your target (with make 16, make 32, make 64)"
As we have explained, when the platform is not recognized one has to specify the word size. We will
do it by overloading WORDSIZE=16: the Z80 is an 8-bit CPU, so it seems reasonable to fit the word
size to 16-bit (8-bit half words). The second attempt will go further but will fail at some point:
$ CC=sdcc AR=sdar RANLIB=sdranlib CFLAGS="-mgbz80 --std-sdcc99 -DWORDSIZE=16" LDFLAGS=" " make ... at 1: error 119: don't know what to do with file 'src/tests/ec_self_tests_core.o'. file extension unsupported
However, one can notice that the static libraries have been compiled, which is a
first step! Compiling a full binary is a bit technical due to the fact that SDCC does not know how
to deal with '.o' object files and '.a' archives. However, we can find our way out of this by renaming
the 'libsign.a' to 'libsign.lib', and adding missing objects in the library. Compiling the ec_self_tests
binary needs external dependencies (src/external_deps/print.c,
src/external_deps/rand.c and src/external_deps/time.c)
as well as the two '.c' files src/tests/ec_self_tests_core.c and
src/tests/ec_self_tests.c, the latter being the one containing the main
function. So we will first add the necessary objects files in the existing library with sdar:
$ cp build/libsign.a build/libsign.lib $ sdar q build/libsign.lib src/external_deps/print.o src/external_deps/rand.o src/external_deps/time.o src/tests/ec_self_tests_core.o
Then, we compile and link src/tests/ec_self_tests.c with the library:
$ sdcc -mgbz80 -DWORDSIZE=16 --std-sdcc99 src/tests/ec_self_tests.c build/libsign.lib
This should create a ec_self_tests.ihx, which has an Intel HEX
file format for firmware programming. From this file, it is usually straightforward to create a Game Boy ROM file
that can be interpreted by an emulator (there are however some quirks related
to the Game Boy platform hardware architecture, see the note below).
NOTE: the purpose of the section was to show how to adapt the compilation process to compilers non compatible with the GNU C one. Consequently, fully porting libecc to the Game Boy platform is left as a complementary work, and this is not a "so easy" task. Among other things, one will have to deal with the ROM size limitation of 32KB that can be solved using bank switching, which will involve some code and compilation tuning. Another issue would be the RAM size of 8KB and properly handling the stack pointer base as described in the previous sections.
Though some efforts have been made to have (most of) the core algorithms constant time, turning libecc into a library shielded against side channel attacks is still a work in progress.
Beyond pure algorithmic considerations, many aspects of a program can turn secret leakage resistance into a very complex problem, especially when writing portable C code. Among other things, we can list the following:
- Low level issues can arise when dealing with heterogeneous platforms (some instructions might not be constant time) and compilers optimizations (a C code that seems constant time is in fact compiled to a non constant time assembly).
- Any shared hardware resource can become a leakage source (the caches, the branch prediction unit, ...). When dealing with a portable source code meant to run on most platforms, it is not an easy task to think of all these leakage sources.
For a thorough discussion about cryptography and constant time challenges, one can check this page.
In order to avoid a range of attacks on the signature algorithm exploiting various side channel attacks and leading to the recovery of the secret key (see here for more details), blinding operations can be used.
Since such security countermeasures have a significant performance hit on the signature algorithm, we have decided to leave the activation of such countermeasures as a voluntary decision to the end user. The performance impact might be acceptable or not depending on the context where the signature is performed, and whether attackers exploiting side channels are indeed considered in the threat model of the specific use case. Of course, for security critical use cases we recommend the blinding usage despite its performance cost.
Compiling the library with blinding is as simple as using the BLINDIG=1 environment variable (or the -DUSE_SIG_BLINDING C flag):
$ BLINDING=1 make
NOTE: if you are unsure about your current security context, use the BLINDING=1 by
default!
### Overview of SCA (Side Channel Attacks) countermeasures
All in all, libecc has now the following approaches to limit SCA:
- SPA (Simple Power Analysis) is thwarted using Double and Add Always, plus complete formulas (see here) to avoid leaking point at infinity (by avoiding exceptions). Constant time operations are (tentatively) used to limit leakage of different operations, even though this task is very complex to achieve (especially in pure C). See the discussion above.
- DDPA (Data DPA) is thwarted using blinding of the point (projective coordinates) and of the scalar (with adding a random multiple of the curve order with maximum entropy). Because of its major impact on performance, blinding must be specifically turned on by the used using the BLINDING=1 switch, see the discussion above.
- ADPA (Address-bit DPA) is limited using Itoh et al. Double and Add Always masked variant. See the article "A Practical Countermeasure against Address-Bit Differential Power Analysis" by Itoh, Izu and Takenaka for more information.
All these countermeasures must, of course, be validated on the specific target where the library runs with leakage assessments. Because of the very nature of C code and CPU microarchitectural details, it is very complex without such a leakage assessment (that again depends on the target) to be sure that SCA protection is indeed efficient.
The source code is composed of eight main parts that consist of the core source code:
-
[1] Machine code: in src/words
Abstraction layer to handle word size depending on the target machine (the word size can also be forced during compilation). Some useful low level macros and functions are handled there.
-
[2] Natural Numbers layer: in src/nn
This part implements all the functions related to positive integers arithmetic (including modular arithmetic).
-
[3] Fp layer: in src/fp
Finite field of prime order (binary fields are intentionally not supported).
-
[4] Elliptic curves core: in src/curves
This layer implements all the primitives handling elliptic curves over prime fields, including point addition and doubling, affine and projective coordinates, ...
-
[5] Curves definitions: in src/curves/known and src/curves/user_defined
These are the definitions of some standard curves (SECP, Brainpool, FRP, ...).
-
[6] EC*DSA signature algorithms: in src/sig
This layer implements the main elliptic curves based signature algorithms (ECSDSA, ECKCDSA, ECFSDSA, ECGDSA, ECRDSA, ECOSDSA). It exposes a sign and verify API with the standard Init/Update/Final logic.
-
[7] Hash functions: in src/hash
Hash functions (SHA-2 and SHA-3 based algorithms for now).
- [8] Utils: in src/utils
Various useful libc functions (memcpy, memset, ...) as well as well as pretty printing functions for our NN, Fp and curves layers.
In addition to the core source code of the library, various resources are also present in the source tree. We descrive them hereafter.
Some self tests are provided for the signature algorithms over all the curves and using all the hash functions [9], as well as tests targetting arithmetic operations over NN and Fp more specifically [10]:
-
[9] Sig self tests: in src/tests
Functions to test that the compiled library is properly working with regard to the signature algorithms over the curves statically defined in the library. These tests consiste in known test vectors, random test vectors (i.e. random data sign/verify) as well as performance measurements.
-
[10] Arithmetic self tests: in src/arithmetic
Functions to test that the compiled arithmetic library is properly working in its basic operations (addition, subtraction, multiplication, ...).
Some examples to help the user interact with the NN, Fp and cruves layers are also provided:
-
[11] User examples: in src/examples
User examples for each of the NN, Fp and curves layers. These examples show what are headers to use, and how to interact with the abstract mathematical objects of each layer.
The configuration of the library [13] as well as an external dependencies abstraction layer are also provided:
-
[12] External dependencies: in src/external_deps
These files contain the functions that are considered as external dependencies, meaning that their implementation is platform dependent (this concerns debug output on a console or file, random generation, time measurement). If no C standard library is provided, the user must implement those functions.
-
[13] Configuration files: in src/lib_ecc_config.h
These are top C headers that are used for libecc configuration, i.e. activate given hash/curve/signature algorithms at compilation time through ifdefs.
Finally, various useful scripts are provided:
- [14] Scripts: in scripts
Tools to expand the libecc with new user defined curves.
Here is a big picture of the library architecture summarizing the links between the modules previously described:
+-------------------------+
|EC*DSA signature |
|algorithms | <------------------+
|(ISO 14888-3) [6] | |
+-----------+-------------+ |
^ |
| |
+-----------+-------------+ +----------+------------+
|Curves (SECP, Brainpool, | | Hash |
|FRP, ...) | | functions |
| [5] | | [7] |
+-----------+-------------+ +-----------------------+
^ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@
| @ {Useful auxiliary modules}@
+-----------+-------------+ @ +------------------------+@
| Elliptic curves [4] | @ | Utils [8] |@
| core (scalar mul, ...) | @ +------------------------+@
+-----------+-------------+ @ | Sig Self tests [9] |@
^ @ | Arith Self tests [10] |@
| @ | User Examples [11] |@
| @ +------------------------+@
| @ | External deps [12] |@
+-----------+-------------+ @ +------------------------+@
| Fp finite fields [3] | @ | LibECC conf files [13] |@
| arithmetic | @ +------------------------+@
+-----------+-------------+ @ | Scripts [14] |@
^ @ +------------------------+@
| @@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+-----------+-------------+ +------------------------+
| NN natural [2] | <------+ Machine related |
| numbers arithmetic | | (words, ...) [1] |
+-------------------------+ +------------------------+