5
$\begingroup$

I'm an embedded systems researcher, and new in the crypto field. Actually, I need to know if there are any lightweight asymmetric encryption algorithm especially considering the time needed for key generation.

I found that NTRU is considered one of the most lightweight asymmetric crypto systems, is this correct?

$\endgroup$
3
  • 2
    $\begingroup$ You should also consider elliptic curves. A popular and relatively fast choice is Curve25519, but there are even faster curves. $\endgroup$ Dec 15, 2015 at 8:57
  • $\begingroup$ Ed25519 has exceptionally fast key generation, with random number generation the primary bottleneck. It also has other strong performance characteristics, is widely reviewed, and widely implemented as well. $\endgroup$
    – Joe Bebel
    Dec 15, 2015 at 9:13
  • $\begingroup$ @JoeBebel Ed25519 key generation is fast, but by far not as fast as a CSPRNG. $\endgroup$ Dec 17, 2015 at 22:50

3 Answers 3

5
$\begingroup$

When an embedded device needs asymmetric crypto to encrypt, (e.g. measurements it makes) or check authenticity (e.g. of commands or firmware updates it receives), there is no need for a private key or key generation in the device, and nothing beats RSA and Rabin on simplicity and speed (for RSA: with $e=3$, which is safe when used with proper padding); plus RSA and Rabin are well known, and patent-free. In these applications, RSA and Rabin main drawbacks are that cryptograms are at least the size of the private key (e.g. 256 bytes for 2048-bit RSA); however only a fraction of that needs to be overhead not conveying actual data (e.g. 66 bytes for RSA-OAEP with SHA-256).

When and if a device needs a private key (see final note), Elliptic Curve Crypto (e.g. ECDSA, ed25519) has many advantages, including very easy key generation, significantly faster computations for the private-key operation (e.g. signature generation), smaller keys, and smaller minimum size of cryptograms. But there is debate about if some particular implementations are patent-encumbered in some jurisdictions, or not.

On the RSA vs ECC debate: RSA private-key (except perhaps its key generation) can be made fast, using dedicated hardware, as used in many Smart Cards. Dedicated hardware is also used in all modern Common-Criteria security-certified embedded devices using ECC that I am aware of, thus if ECC might allow to do without the burden of dedicated hardware in some contexts, that's uncommon in such security-certified devices.

NTRU can also be considered, but is alleged to be patent-encumbered in some jurisdictions, and is a relatively recent player, thus is of less recognized security, in no FIPS standard, nor endorsed by ANSSI (French) or BSI (German). In particular the signature part of it (NTRUSign) was broken in 2006 (Phong Q. Nguyen and Oded Regev, Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, in Journal of Cryptology, 2009; preliminary version in proceedings of Eurocrypt 2006); and the break and fix cycle on NTRUSign has hardly stabilized (Léo Ducas and Phong Q. Nguyen, Learning a Zonotope and More: Cryptanalysis of NTRUSign countermeasures, in proceedings of AsiaCrypt 2012).

Note: having a private key in a device is useful only when some of the other entities that have to authenticate such device, or send it confidential data, can not be trusted to hold and properly use a common secret key. If all such other entities can be trusted, symmetric crypto with device-unique diversified keys (derived from a master key and device serial number) can be made functionally equivalent to full-blown asymmetric crypto everywhere (when combined with asymmetric crypto, restricted to public-key operation on the devices, to authenticate said other entities, and encipher to them); that solution is much simpler and faster on the device side.

$\endgroup$
4
  • 1
    $\begingroup$ Is there an advantage of ed25519 over curve25519? $\endgroup$
    – Kevin__
    Dec 15, 2015 at 10:48
  • 3
    $\begingroup$ @Kevin__: ed25519 is essentially an ECDSA variant using curve25519; so an advantage of ed25519 over curve25519 is like an advantage of train over rail: the former is more directly useful towards a goal (signing, traveling). $\endgroup$
    – fgrieu
    Dec 15, 2015 at 11:08
  • $\begingroup$ Just to add to your answer, NTRUSign seems to be completely insecure as of today, see this paper. An attacker would only need a fairly low amount of transcripts to recover the private key. $\endgroup$
    – Kevin__
    Dec 15, 2015 at 11:17
  • $\begingroup$ @Kevin__: my answer already link to that paper (save for the introductory page); it does show that at least some parameterizations of NTRUSign proposed as secure in 2003 are completely insecure, and that makes other parameterizations questionable. $\endgroup$
    – fgrieu
    Dec 15, 2015 at 11:29
2
$\begingroup$

There is an alternative to ECC, called Ring-LWE, it claims to be 10x faster than ECC on microcontrollers.

details: Efficient Software Implementation of Ring-LWE Encryption

enter image description here

There is a C/C++ implementation here https://github.com/jnortiz/RLWE

It only implements keygen/de/encryption,

This paper contains signing/verifying Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems

$\endgroup$
3
  • 2
    $\begingroup$ Note that the parameter set that generated the quoted performance uses a lattice of dimension 256; I don't believe that would be considered strong enough for many purposes. $\endgroup$
    – poncho
    Jan 4 at 15:05
  • $\begingroup$ In P2 mode it's 512, at the cost of taking 2x more time. Not sure how it relates to security bits. For signing it's not ideal, public key sizes are KB big. Looks like it's back to ECC P256 as an all around suite. $\endgroup$
    – Eva4684
    Jan 4 at 21:46
  • $\begingroup$ There's also Module-LWE (and Module-SIS) that can scale better by reusing codes for arithmetic over degree-256 polynomials in NTT domain(s). $\endgroup$
    – DannyNiu
    Jan 5 at 4:17
1
$\begingroup$

The Problem with NTRU is that it is still patented and rather complex compared to other Cryptoschemes. There are some reference implementations and they are usable with a GPL license. Though I would agree with the comments on your question. You should really have a look into Elliptic Curve Cryptography. Cryptosystems with ECC are usually efficient in space and time. If there are no sudden breakthroughs, ECC should be secure for at least the next ~5-10 years if the parameters are chosen correctly.

Other than that I would advise not to use asymmetric algorithm for the encryption, as these a significantly slower than symmetric algorithms. Maybe have a look at WolfSSL. They focus on implementations for embedded systems.

$\endgroup$
2
  • $\begingroup$ Actually, I have hard real-time constraint, therefore, I'll use asymmetric algorithm for key distribution only then back again to symmetric encryption. My question was which is most suitable from performance and memory for just startup phase ( key distribution) $\endgroup$
    – a.refaat
    Dec 15, 2015 at 23:33
  • 2
    $\begingroup$ In that case Elliptic Curve Diffie-Hellmann with curve25519 with ECDSA and ed25519 curve (as referred to by fgrieu) might suit your case. $\endgroup$
    – Kevin__
    Dec 16, 2015 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.