Patent ID: 8204232
Filing Date: 2012-06-19
Classification: G06F,H04L

Abstract:
1. In a cryptographic module having an arithmetic processing unit, a method of verifying a relationship between a sum of scalar multiples of a pair of points on an elliptic curve and a third point on said curve, the sum of scalar multiples of said pair of points including a first scalar multiplied by a first point of said pair of points added to a second scalar multiplied by a second point of said pair of points, the method comprising: the cryptographic module obtaining a pair of integers, each of the pair of integers having a bit length less than the bit length of one of said first scalar and said second scalar and wherein the ratio of the pair of integers corresponds to said one of said first scalar and said second scalar, the arithmetic processing unit performing computations from which said relationship can be verified, said computations involving said first point, said second point, said third point, and said pair of integers, wherein said integers are used in said computations instead of said one of said first scalar and said second scalar, thereby reducing the number of said computations, subsequent to said computations, the cryptographic module determining whether the result of said computations indicates verification of said relationship, and if the result of said computations indicates the verification of said relationship, producing an output indicative of the verification.