Accelerated Key Agreement With Assisted Computations

• US 20120221858A1
• Filed: 02/28/2011
• Published: 08/30/2012
• Est. Priority Date: 02/28/2011
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Struik, Marinus
• Granted Patent: US 8,549,299 B2
• Time in Patent Office: Days
• US Class Current: 713/171
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys

Abstract

A method is provided for obtaining a secret value for use as a key 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 includes obtaining a pair of scalars x_o, x₁ such that x=x_o+x₁ t where t is a scaling factor; obtaining a supplementary public key t Y; combining the scalars and the public keys to obtain a representation of the secret value xY as a linear combination of the scalars and the public keys; and utilising the secret value as a key in a cryptographic operation performed by the one computing device.

Claims

1. 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_o, x₁ such that x=x_o+x₁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; and

the one computing device utilising the secret value as a key in a cryptographic operation.

2. The method of claim 1 wherein the linear combination of the scalars and public keys comprises x_oY+x₁ (tY).

3. The method of claim 1 wherein the scaling factor is a value less than n, and wherein n is the order of an elliptic curve group used to compute the public key Y.

4. The method of claim 3 wherein the scaling factor is of the order of √

{square root over (n)}.

5. The method of claim 1 wherein the scaling factor is known to both the one computing device and the other computing device.

6. The method of claim 1 wherein the scalar x_o is the remainder when the private key x is divided by the scaling factor t.

7. The method of claim 1 wherein the linear combination of the scalars and the public keys is computed using at least one of:

non adjacent forms (NAF), windowing, interleaving, combing, simultaneous multiple point multiplication, and precomputation of values.

8. The method of claim 1 wherein the linear combination is computed using simultaneous multiple point multiplication comprising:

writing the scalars x₀ and x₁ 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₀ and w bits of the scalar x₁ from the matrix as examined by the window;

retrieving from the memory the precomputed values corresponding to the w bits of the scalar x₀ and the w bits of the scalar x₁; and

storing the retrieved precomputed values in an accumulator on the computing device.

9. The method of claim 1 wherein the scaling factor is associated with the other computing device and a different scaling factor is associated with the one computing device.

10. The method of claim 1.0 wherein the scaling factor and the different scaling factor are incorporated into one or more messages exchanged between the one computing device and the other computing device.

11. The method of claim 1 wherein the one computing device obtains the supplementary public key from a certificate of the public key Y.

12. The method of claim 11 wherein the certificate further comprises the scaling factor.

13. A computing device comprising a cryptographic unit and a memory, the computing device configured to communicate with another computing device, and the computing device storing computer readable instructions to obtain a secret value for use in a cryptographic operation, the secret value combining a private key, x, of the computing device with a public key, Y, of the other computing device to obtain a secret value xY, the computer readable instructions comprising:

computing a pair of scalars x_o, x₁ such that x=x_o+x₁t where t is a scaling factor;

receiving a supplementary public key tY;

combining the scalars and the public keys to compute the secret value xY as a linear combination of the scalars and the public keys; and

utilising the secret value as a key in a cryptographic operation performed by the computing device.

14. A method of obtaining a secret value for use in a cryptographic operation, the secret value combining,

from one computing device, a private static key a, a private ephemeral key x, and a representation X of an ephemeral, public key X, the ephemeral public key corresponding to the ephemeral private key,

with, from another computing device, an ephemeral public key Y, a representation Y of the ephemeral public key Y, and a static public key B,

to obtain a secret value (x+a X) (Y+ YB), the method comprising:

the one computing device computing a pair of scalars α

_o, α

₁ such that α

=α

_o+α

₁t where t is a scaling factor and where α

=(x+a X);

the one computing device computing another pair of scalars γ

_o, γ

₁ such that γ

=γ

_o+γ

₁t and γ

=α

Y;

₁

the one computing device receiving a supplementary ephemeral public key tY and a supplementary static public key tB;

the one computing device combining the scalars and the public keys to compute the secret value (x+a X) (Y+ YB) as a linear combination of the scalars and the public keys; and

the one computing device utilising the secret value as the key in the cryptographic operation.

15. The method of claim 14 wherein the linear combination of the scalars and public keys comprising α

_oY+α

₁(tY)+γ

_oB+γ

₁(tB).

16. The method of claim 14 wherein the scaling factor is a value less than n, and wherein n is the order of an elliptic curve group used to compute the ephemeral public key Y.

17. The method of claim 16 wherein the scaling factor is of the order of √

{square root over (n)}.

18. The method of claim 14 wherein the scaling factor is known to both the one computing device and the other computing device.

19. The method of claim 14 wherein the linear combination of the scalars and the public keys is computed using at least one of non-adjacent forms (NAF), windowing, interleaving, combing, simultaneous multiple point multiplication, and precomputation of values.

20. The method of claim 14 wherein the linear combination is computed using simultaneous point multiplication comprising:

arranging the scalars α

_0. α

_1, γ

_o, γ

₁ into a matrix;

selecting a window of width w bits;

precomputing values corresponding to iY+j(tY) and corresponding to iB+j(tB) wherein 0≦

ij<

2^w, and storing the precomputed values on a memory of the one computing device;

obtaining w bits of each of the scalars α

_o, α

_1, γ

_o, γ

₁ from the matrix as examined by the window;

retrieving from the memory the precomputed values corresponding to the w bits of each of the scalars α

_o, α

_1, γ

_o, γ

₁; and

storing the retrieved precomputed values in an accumulator on the computing device.

21. The method of claim 14 wherein the scaling factor is associated with the other computing device and a different scaling factor is associated with the one computing device.

22. The method of claim 21 wherein the scaling factor and the different scaling factor are incorporated into one or more messages exchanged between the one computing device and the other computing device.

23. The method of claim 14 wherein the one computing device obtains the supplementary public key from a certificate of the ephemeral public key K

24. The method of claim 23 wherein the certificate further comprises the scaling factor.

25. A computing device comprising a cryptographic unit and a memory, the computing device configured to communicate with another computing device, and the computing device storing computer readable instructions to obtain a secret value for use in a cryptographic operation, the secret value combining,.

from the computing device, a private static key a, an ephemeral private key x, and a representation X of an ephemeral public key X, the ephemeral public key corresponding to the ephemeral private key,

with, from another computing device, an ephemeral public key Y, a representation Y of the ephemeral public key Y, and a static public key B,

to obtain (x+a X) (Y+ YB), the computer readable instructions comprising:

computing a pair of scalars α

_o, α

₁ such that α

+α

_o+α

₁t where t is a scaling factor and where α

=(x+a X);

computing another pair of scalars γ

_o, γ

₁ such that γ

=γ

₀+γ

₁t and γ

=α

Y;

receiving a supplementary ephemeral public key t Y and a supplementary static public key tB;

combining the scalars and the public keys to compute the secret value (x+a X) (Y+ YB) as a linear combination of the scalars and the public keys; and

utilising the secret value as the key in the cryptographic operation performed by the computing device.