A Family of Lightweight Twisted Edwards Curves for the Internet of Things

in Blazy, Olivier; Yeun, Chan Y. (Eds.) Information Security Theory and Practice, 12th IFIP WG 11.2 International Conference, WISTP 2018, Brussels, Belgium, December 10-11, 2018, Proceedings (2018, December)

We introduce a set of four twisted Edwards curves that satisfy common security requirements and allow for fast implementations of scalar multiplication on 8, 16, and 32-bit processors. Our curves are ... [more ▼]

We introduce a set of four twisted Edwards curves that satisfy common security requirements and allow for fast implementations of scalar multiplication on 8, 16, and 32-bit processors. Our curves are defined by an equation of the form -x^2 + y^2 = 1 + dx^2y^2 over a prime field Fp, where d is a small non-square modulo p. The underlying prime fields are based on "pseudo-Mersenne" primes given by p = 2^k - c and have in common that p is congruent to 5 modulo 8, k is a multiple of 32 minus 1, and c is at most eight bits long. Due to these common features, our primes facilitate a parameterized implementation of the low-level arithmetic so that one and the same arithmetic function is able to process operands of different length. Each of the twisted Edwards curves we introduce in this paper is birationally equivalent to a Montgomery curve of the form -(A+2)y^2 = x^3 + Ax^2 + x where 4/(A+2) is small. Even though this contrasts with the usual practice of choosing A such that (A+2)/4 is small, we show that the Montgomery form of our curves allows for an equally efficient implementation of point doubling as Curve25519. The four curves we put forward roughly match the common security levels of 80, 96, 112 and 128 bits. In addition, their Weierstraß representations are isomorphic to curves of the form y^2 = x^3 - 3x + b so as to facilitate inter-operability with TinyECC and other legacy software. [less ▲]

Secure Number Theoretic Transform and Speed Record for Ring-LWE Encryption on Embedded Processors

in The 20th Annual International Conference on Information Security and Cryptology - ICISC2017 (2017, December 30)

Fast Discretized Gaussian Sampling and Post-quantum TLS Ciphersuite

in The 13th International Conference on Information Security Practice and Experience - ISPEC 2017 (2017, December 01)

Multiprecision Multiplication on ARMv8

in IEEE 24th Symposium on Computer Arithmetic - ARITH24 (2017, August 01)

Exploring Effect of Location Number on Map-Based Graphical Password Authentication

in 22nd Australasian Conference on Information Security and Privacy - ACISP2017 (2017, July 03)

Efficient Arithmetic on ARM-NEON and Its Application for High-Speed RSA Implementation

in Security and Communication Networks (2016), 9(18), 5401-5411

A steadily increasing number of modern processors support Single Instruction Multiple Data (SIMD) instructions to speed up multimedia, communication, and security applications. The computational power of ... [more ▼]

A steadily increasing number of modern processors support Single Instruction Multiple Data (SIMD) instructions to speed up multimedia, communication, and security applications. The computational power of Intel's SSE and AVX extensions as well as ARM's NEON engine has initiated a body of research on SIMD-parallel implementation of multiple-precision integer arithmetic operations, in particular modular multiplication and modular squaring, which are performance-critical components of widely-used public-key cryptosystems such as RSA, DSA, Diffie-Hellman, and their elliptic-curve variants ECDSA and ECDH. In this paper, we introduce the Double Operand Scanning (DOS) method for multiple-precision squaring and describe its implementation for ARM NEON processors. The DOS method uses a full-radix representation of the operand to be squared and aims to maximize performance by reducing the number of Read-After-Write (RAW) dependencies between source and destination registers. We also analyze the benefits of applying Karatsuba's technique to both multiple-precision multiplication and squaring, and present an optimized implementation of Montgomery's algorithm for modular reduction. Our performance evaluation shows that the DOS method along with the other optimizations described in this paper allows one to execute a full 2048-bit modular exponentiation in about 14.25 million clock cycles on an ARM Cortex-A15 processor, which is significantly faster than previously-reported RSA implementations for the ARM-NEON platform. [less ▲]

Energy-Efficient Elliptic Curve Cryptography for MSP430-Based Wireless Sensor Nodes

in Liu, Joseph K.; Steinfeld, Ron (Eds.) Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Melbourne, VIC, Australia, July 4-6, 2016, Proceedings, Part I (2016, July)

The Internet is rapidly evolving from a network of personal computers and servers to a network of smart objects ("things") able to communicate with each other and with central resources. This evolution ... [more ▼]

The Internet is rapidly evolving from a network of personal computers and servers to a network of smart objects ("things") able to communicate with each other and with central resources. This evolution has created a demand for lightweight implementations of cryptographic algorithms suitable for resource-constrained devices such as RFID tags and wireless sensor nodes. In this paper we describe a highly optimized software implementation of Elliptic Curve Cryptography (ECC) for the MSP430 series of ultra-low-power 16-bit microcontrollers. Our software is scalable in the sense that it supports prime fields and elliptic curves of different order without recompilation, which allows for flexible trade-offs between execution time (i.e. energy consumption) and security. The low-level modular arithmetic is optimized for pseudo-Mersenne primes of the form p = 2^n - c where n is a multiple of 16 minus 1 and c fits in a 16-bit register. All prime-field arithmetic functions are parameterized with respect to the length of operands (i.e. the number of 16-bit words they consist of) and written in Assembly language, whereby we avoided conditional jumps and branches that could leak information about the secret key. Our ECC implementation can perform scalar multiplication on two types of elliptic curves, namely Montgomery curves and twisted Edwards curves. A full scalar multiplication using a Montgomery curve over a 159-bit field requires about 3.86*10^6 clock cycles when executed on an MSP430F1611 microcontroller. [less ▲]

Lightweight Public-Key Cryptography for Wireless Sensor Nodes

Doctoral thesis (2015)

This thesis studies techniques for the efficient implementation of public-key cryptography on resource-constrained computing devices such as wireless sensor nodes. We focus on three different families of ... [more ▼]

This thesis studies techniques for the efficient implementation of public-key cryptography on resource-constrained computing devices such as wireless sensor nodes. We focus on three different families of public-key cryptosystems, namely RSA, elliptic curve schemes (e.g. ECDH), as well as a lattice-based encryption algorithm using the ring variant of the Learning With Errors problem (Ring-LWE). In the context of efficient RSA implementation, this thesis first describes the Reverse Product Scanning (RPS) technique for multi-precision multiplication and squaring on 8-bit AVR processors. Then, we analyze and compare six algorithms for software implementation of Montgomery multiplication and shed some new light on the relative performance of the different variants. Finally, we present a highly-optimized 1024-bit RSA software that achieves record-setting execution times on 8-bit ATmega processors thanks to a combination of sophisticated implementation options including the Chinese Remainder Theorem (CRT), the m-ary exponentiation method, as well as the RPS multiplication technique. The main contribution of this thesis lies in the area of Elliptic Curve Cryptography (ECC), where we describe three different implementations for wireless sensor nodes equipped with 8 and 16-bit processors. First, we present several techniques to improve the performance of prime-field arithmetic operations (e.g. optimized operand caching, sliding block doubling, and Karatsuba block squaring) and report the fastest implementation of key exchange and signature generation/verification based on the NIST P-192 curve. Second, we introduce an efficient yet highly-regular library for arithmetic in Optimal Prime Fields (OPFs) and propose a novel approach for the implementation of ephemeral ECDH key exchange that exploits the birational equivalence of Montgomery and twisted Edwards curves. Third, we describe an algorithm for the generation of so-called MoTE curves that allows one to use the fastest formulae for point addition/doubling in both the Montgomery form and the twisted Edwards form. Finally, we describe efficient ECC implementations for 159 and 191-bit MoTE curves that achieve record-setting execution times for scalar multiplication on a 16-bit MSP430 processor. The third part of this thesis deals with the efficient implementation of Ring-LWE encryption and proposes novel approaches to speed up the Number Theoretic Transform (NTT) used for polynomial multiplication. Our contributions in this area include the Move-and-Add (MA) method for coefficient multiplication, the Shift-Add-Multiply-Subtract-Subtract (SAMS2) technique for modular reduction, and an optimized variant for Montgomery multiplication. Furthermore, we describe an optimized coefficient storage method to minimize the RAM footprint of NTT multiplications. Finally, we propose a special byte-scanning technique to reduce the execution time of discrete Gaussian sampling based on the Knuth-Yao random walk algorithm. [less ▲]

Efficient Implementation of ECDH Key Exchange for MSP430-Based Wireless Sensor Networks

in Bao, Feng; Miller, Steven; Zhou, Jianying (Eds.) et al ASIACCS'15: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, April 14-17, 2015, Singapore (2015, April)

Public-Key Cryptography (PKC) is an indispensable building block of modern security protocols, and, thus, essential for secure communication over insecure networks. Despite a significant body of research ... [more ▼]

Public-Key Cryptography (PKC) is an indispensable building block of modern security protocols, and, thus, essential for secure communication over insecure networks. Despite a significant body of research devoted to making PKC more "lightweight," it is still commonly perceived that software implementations of PKC are computationally too expensive for practical use in ultra-low power devices such as wireless sensor nodes. In the present paper we aim to challenge this perception and present a highly-optimized implementation of Elliptic Curve Cryptography (ECC) for the TI MSP430 series of 16-bit microcontrollers. Our software is inspired by MoTE-ECC and supports scalar multiplication on two families of elliptic curves, namely Montgomery and twisted Edwards curves. However, in contrast to MoTE-ECC, we use pseudo-Mersenne prime fields as underlying algebraic structure to facilitate inter-operability with existing ECC implementations. We introduce a novel "zig-zag" technique for multiple-precision squaring on the MSP430 and assess its execution time. Similar to MoTE-ECC, we employ the Montgomery model for variable-base scalar multiplications and the twisted Edwards model if the base point is fixed (e.g. to generate an ephemeral key pair). Our experiments show that the two scalar multiplications needed to perform an ephemeral ECDH key exchange can be accomplished in 4.88 million clock cycles altogether (using a 159-bit prime field), which sets a new speed record for ephemeral ECDH on a 16-bit processor. We also describe the curve generation process and analyze the execution time of various field and point arithmetic operations on curves over a 159-bit and a 191-bit pseudo-Mersenne prime field. [less ▲]

Montgomery Modular Multiplication on ARM-NEON Revisited

in Kim, Jongsung; Lee, Jooyoung (Eds.) Information Security and Cryptology - ICISC 2014, 17th International Conference, Seoul, Korea, December 3-5, 2014, Revised Selected Papers (2014, December)