A lightweight and secure algorithm of elliptic curve cryptography scalar multiplication using Q-NAF method in Lopez-Dahab coordinate
Elliptic curve cryptography (ECC) is gaining increasing popularity and acceptance within the research community. This is because it uses shorter keys to achieve security level equivalent to other public-key cryptosystems. Over the years, special attention has been given to improving the scalar re...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2019
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/83759/1/FSKTM%202019%201%20-%20ir.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Elliptic curve cryptography (ECC) is gaining increasing popularity and acceptance
within the research community. This is because it uses shorter keys to achieve security
level equivalent to other public-key cryptosystems. Over the years, special attention
has been given to improving the scalar recoding algorithm, since it is the most
computationally intensive operation of ECC.
The general research objective of this thesis is to improve the efficiency of the scalar
multiplication algorithm of ECC in Lopez Dahab coordinate for elliptic curve over
binary field. This is targeted at constrained-resource devices for the internet of things
(IoT) such as field programmable gate array (FPGA), radio frequency identifications
(RFID) and smart cards.
In literature, window w-NAF method is considered one of the best and most widely
used methods for scalar recoding. However, this method does not stand against the
recent side channel attack (SCA). The first objective of this thesis is to introduce a
new scalar recoding algorithm to achieve better efficiency in terms of security and
performance for constrained-resource devices. A new Q-NAF scalar recoding
algorithm is proposed to improve the scalar recoding efficiency criteria. Specifically,
these criteria includes, hamming weight HW (numbers of non-zeroes), security, and
its performance in terms of execution time and memory consumption. To conform to
the application requirements of the IoT, the new algorithm improves w-NAF, where
w=4. The proposed scalar recoding converts the binary scalar into {-1, 0, 1, 3, 5}-NAF
using Q-NAF scalar recoding lookup table or a Q-NAF scalar recoding mathematical
formula. Markov chain is used to calculate the HW of the lookup table. Q-NAF
reduces the HW of the scalar by 81% on average for n-bit scalar rather than the 80% HW for w-NAF. By coding the two algorithms, the proposed algorithm improves the
execution time and memory consumption with a percentage of about 58% and 93%
respectively. Theoretically, Q-NAF scalar recoding is proven to be secure against SCA
in terms of timing and simple power attacks.
Since the scalar recoding contains the digit 5 in the representation digits, using
quintupling point 5P will increase the efficiency of the scalar multiplication. However,
5P over Lopez-Dahab coordinate in the binary curve has not been considered in
literature despite its potential to increase the scalar multiplication performance. A new
valid quintupling point 5P arithmetic formula is thus proposed to improve the cost of
elliptic curve scalar multiplication method on binary curve over Lopez-Dahab
coordinate. The proposed point is formulated as (2(2P) + P) using Al-Daoud for
doubling and mix addition. The cost of the proposed point is 17M+12S.
By combining the proposed scalar arithmetic and the new point arithmetic 5P, a new
scalar multiplication algorithm was developed. This scalar multiplication algorithm is
named Q-NAF scalar multiplication for binary curve over Lopez-Dahab coordinates.
The proposed scalar multiplication is more efficient in term of performance than w-
NAF scalar multiplication. This is because Q-NAF method reduces the HW without
the need to use the digit 7, which it is highly cost during point arithmetic. So, the
proposed cryptosystem is more efficient than w-NAF while scalar recoding cost of
points to recode and during the scalar multiplication.
Finally, a new look-up table is proposed to optimize the formula {0, 1, 3}-NAF lookup
table. The new lookup table reduces the size of the {0, 1, 3}-NAF lookup table from
15X6 into 4X5. This is achieved by scanning two digits to produce one digit instead
of three digits, which significantly reduces the time and memory with percentage of
about 60% and 75% respectively.
In the first three contributions, a new Q-NAF scalar multiplication method is proposed
for the three scalar levels, such that scalar recoding, point arithmetic and scalar
multiplication. Compare to 4-NAF, Q-NAF scalar recoding gives better results in
terms of HW, time, memory and security, Q-NAF proposed a new point quintupling
which used in the scalar recoding. While 4-NAF used more digits in the first two
contributions, Q-NAF scalar multiplication is better than 4-NAF scalar multiplication
in terms of precomputed points, security, HW and performance. While for the fourth
contribution, a modified lookup table is proposed to improve the original method in
terms of time, memory and security. |
|---|