Faster Point Scalar Multiplication on Short Weierstrass Elliptic Curves over Fp using Twisted Hessian Curves over Fp2

Abstract

This article shows how to use fast Fp2 arithmetic and twisted Hessian curves to obtain faster point scalar multiplication on elliptic curve ESW in short Weierstrass form over Fp. It is assumed that p and #ESW(Fp) are different large primes, #E(Fq) denotes number of points on curve E over field Fq and #Et SW (Fp) Fp), where Et is twist of E, is divisible by 3. For example this method is suitable for two NIST curves over Fp: NIST P-224 and NIST P-256. The presented solution may be much faster than classic approach. Presented solution should also be resistant for side channel attacks and information about Y coordinate should not be lost (using for example Brier-Joye ladder such information may be lost). If coefficient A in equation of curve ESW : y2 =x3+Ax+B in short Weierstrass curve is not of special form, presented solution is up to 30% faster than classic approach. If A=−3, proposed method may be up to 24% faster.