Patent ID: 8549299

Claim:
A method of obtaining a secret value for use in a cryptographic operation, the secret value combining a private key, x, of one computing device with a public key, Y, of another computing device to obtain a secret value xY, the method comprising: the one computing device computing a pair of scalars x 0 , x 1 , the private key x related to the pair of scalars by x=x 0 +x 1 t where t is a scaling factor; the one computing device receiving a supplementary public key tY; the one computing device combining the scalars and the public keys to compute the secret value xY as a linear combination of the scalars and the public keys; the one computing device utilising the secret value as a key in a cryptographic operation; and wherein the linear combination is computed using simultaneous multiple point multiplication comprising: writing the scalars x 0 and x 1 as a matrix; selecting a window of width w bits; precomputing values corresponding to iY+j(tY), wherein 0<i, j<2 w , and storing the precomputed values on a memory of the one computing device; obtaining w bits of the scalar x 0 and w bits of the scalar x 1 from the matrix as examined by the window; retrieving from the memory the precomputed values corresponding to the w bits of the scalar x 0 and the w bits of the scalar x 1 ; and storing the retrieved precomputed values in an accumulator on the computing device.