GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-Bit Nonce Bias

ISBN : 978-3-662-45610-1International audienceThe fastest implementations of elliptic curve cryptography in recent years have been achieved on curves endowed with nontriv-ial efficient endomorphisms, using techniques due to Gallant–Lambert– Vanstone (GLV) and Galbraith–Lin–Scott (GLS). In such implementa-tions, a scalar multiplication [k]P is computed as a double multiplication [k1]P + [k2]ψ(P), for ψ an efficient endomorphism and k1, k2 appropri-ate half-size scalars. To compute a random scalar multiplication, one can either select the scalars k1, k2 at random, hoping that the resulting k = k1 + k2λ is close to uniform, or pick a uniform k instead and decom-pose it as k1 + k2λ afterwards. The main goal of this paper is to discuss security issues that may arise using either approach. When k1 and k2 are chosen uniformly at random in [0, √ n), n = ord(P), we provide a security proofs under mild assumptions. However, if they are chosen as random integers of 1