Synopsys, Inc.
Efficient calculation of ED25519/448 signature verification in an encryption device

Abstract:

A computer system module(s) substitutes a double scalar multiplication, used for signature verification in an encryption/decryption system, for two single scalar multiplications. The modules verify a group equation defined by [S]B=R+[k]A' of the encryption/decryption system, where S is an integer characterized by the signature, K is an integer generated by a message being encrypted, B is a base point on the elliptic curve, R is a point on the elliptic curve and characterized by the signature, and A' is a public key. The modules optionally rearrange the group equation to [S]B+[-k]A'=R, and convert it to [S]B+[n-k]A'=R, where n is the order of the base point. The modules determine a joint sparse form for the integers S and n-k and apply the Shamir's algorithm to the joint sparse form to verify the group equation.