# US 8,543,822 B2 · Device authentication

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,543,822 B2
- Document ID: US8543822B2
- Status: Granted
- Kind: B2
- Application number: 13/429,654
- Filed: 2012-03-26
- Published: 2012-11-22
- Granted: 2013-09-24
- Earliest claimed: 2004-04-30
- Assignees: BlackBerry Limited
- Applicants: Michael K. Brown; Herbert A. Little; Dinah L. M. Davis
- Inventors: Michael K. Brown; Herbert A. Little; Dinah L. M. Davis
- Web page: https://patentgrep.com/patent/US8543822B2

## CPC

- G11C 7/24: Memory cell safety or protection circuits, e.g. arrangements for preventing inadvertent reading or writing; Status cells; Test cells
- G11C: STATIC STORES (semiconductor memory devices H10B)

## Abstract

A first device in possession of a value is able to determine, without communicating the value and without communicating any information from which the value can be identified, whether a second device is also in possession of the value. The first device accomplishes this with the assistance of a third device that is able to communicate with the first device and with the second device. The second device also does not communicate the value and does not communicate any information from which the value can be identified. The first device may send additional information to the third device which, if passed to the second device, enables the second device to determine that the first device is in possession of the value. The value may be a secret.

## Claims

### Claim 1

A method to be performed by a first device that possesses a value h for determining whether a second device possesses the value h, the method comprising:
generating a product RD and transmitting the product RD to a third device, wherein RD is a product of a random value rD and a public key value P;
receiving from the third device a challenge value eD that was received by the third device from the second device;
receiving from the third device a product RB that was received by the third device from the second device, wherein RB is a product of a random value rB and the public key value P;
obtaining a challenge value eB and transmitting the challenge value eB to the third device;
receiving from the third device a value yB that was received by the third device from the second device;
calculating yBP+eBRB to obtain a first result;
calculating hP to obtain a second result;
comparing the first result to the second result; and
determining that the second device is in possession of the value h when the first result is identical to the second result,
wherein the public key value P generates a prime subgroup of the group E(Fq) of order p, wherein Fq is a finite field of prime order q, wherein the random values rD and rB are between the number 1 and the number (p−1), and wherein the challenge values eD and eB are between the number 1 and the number (p−1).

### Claim 2 (depends on 1)

The method of claim 1, wherein the value h is derived from a secret value s, the method further comprising:
determining that the second device is in possession of the secret value s when the first result is identical to the second result.

### Claim 3 (depends on 2)

The method of claim 2, wherein the value h is a hash of the secret value s.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
generating a value yD and transmitting the value yD to the third device, thus enabling the third device to determine that the first device is in possession of the value h, for further transmission by the third device to the second device, thus enabling the second device to determine that the first device is in possession of the value h.

### Claim 5 (depends on 4)

The method of claim 4, wherein the value yD is generated from the value h, from the challenge value eD, and from the random value rD.

### Claim 6

A method for determining whether a first device possesses a value h, the method to be performed by a second device that possesses the value h, the method comprising:
receiving from a third device a product RD that was received by the third device from the first device, wherein RD is a product of a random value rD and a public key value P;
generating a product RB and transmitting the product RB to the third device, wherein RB is a product of a random value rB and the public key value P;
obtaining a challenge value eD and transmitting the challenge value eD to the third device;
receiving from the third device a value yD that was received by the third device from the first device;
receiving from the third device a challenge value eB that was received by the third device from the first device;
calculating yDP+eDRD to obtain a first result;
calculating hP to obtain a second result;
comparing the first result to the second result; and
determining that the first device is in possession of the value h when the first result is identical to the second result,
wherein the public key value P generates a prime subgroup of the group E(Fq) of order p, wherein Fq is a finite field of prime order q, wherein the random values rD and rB are between the number 1 and the number (p−1), and wherein the challenge values eD and eB are between the number 1 and the number (p−1).

### Claim 7 (depends on 6)

The method of claim 6, wherein the value h is derived from a secret value s, the method further comprising:
determining that the first device is in possession of the secret value s when the first result is identical to the second result.

### Claim 8 (depends on 7)

The method of claim 7, wherein the value h is a hash of the secret value s.

### Claim 9 (depends on 6)

The method of claim 6, further comprising:
generating a value yB and transmitting the value yB to the third device, thus enabling the third device to determine that the second device is in possession of the value h, for further transmission by the third device to the first device, thus enabling the first device to determine that the second device is in possession of the value h.

### Claim 10 (depends on 9)

The method of claim 9, wherein the value yB is generated from the value h, from the challenge value eB, and from the random value rB.

### Claim 11 (depends on 6)

The method of claim 6, further comprising:
generating a product RC and transmitting the product RC to the third device, wherein RC is a product of a random value rC and the public key value P, and further wherein RC is constrained to have a different value than both the product RB and the product RD;
receiving from the third device a challenge value eC that is constrained to have a different value than both the challenge value eB and the challenge value eD; and
generating a value yC and transmitting the value yC to the third device to enable the third device to determine that the second device is still in possession of the value h.

### Claim 12 (depends on 11)

The method of claim 11, wherein the value yC is generated from the value h, from the challenge value eC, and from the random value rC.

### Claim 13

A program product comprising a computer readable non-transitory storage medium having executable program code stored in said medium, the executable program code being operative, when executed, to cause a first device that is in possession of a value h:
to generate a product RD and to transmit the product RD to a third device, wherein RD is a product of a random value rD and a public key value P;
to receive from the third device a challenge value eD that was received by the third device from a second device;
to receive from the third device a product RB that was received by the third device from the second device, wherein RB is a product of a random value rB and the public key value P;
to obtain a challenge value eB and to transmit the challenge value eB to the third device;
to receive from the third device a value yB that was received by the third device from the second device;
to calculate yBP+eBRB to obtain a first result;
to calculate hP to obtain a second result;
to compare the first result to the second result; and
to determine that the second device is in possession of the value h when the first result is identical to the second result
wherein the public key value P generates a prime subgroup of the group E(Fq) of order p, wherein Fq is a finite field of prime order q, wherein the random values rD and rB are between the number 1 and the number (p−1), and wherein the challenge values eD and eB are between the number 1 and the number (p−1).

### Claim 14

A program product comprising a computer readable non-transitory storage medium having executable program code stored in said medium, the executable program code being operative, when executed, to cause a second device that is in possession of a value h:
to receive from a third device a product RD that was received by the third device from a first device, wherein RD is a product of a random value rD and a public key value P;
to generate a product RB and to transmit the product RB to the third device, wherein RB is a product of a random value rB and the public key value P;
to obtain a challenge value eD and to transmit the challenge value eD to the third device;
to receive from the third device a value yD that was received by the third device from the first device;
to receive from the third device a challenge value eB that was received by the third device from the first device;
to calculate yDP+eDRD to obtain a first result;
to calculate hP to obtain a second result;
to compare the first result to the second result; and
to determine that the first device is in possession of the value h when the first result is identical to the second result,
wherein the public key value P generates a prime subgroup of the group E(Fq) of order p, wherein Fq is a finite field of prime order q, wherein the random values rD and RB are between the number 1 and the number (p−1), and wherein the challenge values eD and eB are between the number 1 and the number (p−1).

### Claim 15 (depends on 14)

The program product of claim 14, the executable program code being further operative, when executed, to cause the second device:
to generate a product RC and to transmit the product RC to the third device, wherein RC is a product of a random value rC and the public key value P, and further wherein RC is constrained to have a different value than both the product RB and the product RD;
to receive from the third device a challenge value eC that is constrained to have a different value than both the challenge value eB and the challenge value eD; and
to generate a value yC and to transmit the value yC to the third device to enable the third device to determine that the second device is still in possession of the value h.

### Claim 16

A first device adapted:
to possess a value h;
to generate a product RD and to transmit the product RD to a third device, wherein RD is a product of a random value rD and a public key value P;
to receive from the third device a challenge value eD that was received by the third device from a second device;
to receive from the third device a product RB that was received by the third device from the second device, wherein RB is a product of a random value rB and the public key value P;
to obtain a challenge value eB and to transmit the challenge value eB to the third device;
to receive from the third device a value yB that was received by the third device from the second device;
to calculate yBP+eBRB to obtain a first result;
to calculate hP to obtain a second result;
to compare the first result to the second result; and
to determine that the second device is in possession of the value h when the first result is identical to the second result
wherein the public key value P generates a prime subgroup of the group E(Fq) of order p, wherein Fq is a finite field of prime order q, wherein the random values rD and rB are between the number 1 and the number (p−1), and wherein the challenge values eD and eB are between the number 1 and the number (p−1).

### Claim 17 (depends on 16)

The first device of claim 16, wherein the first device comprises a wireless handheld device.

### Claim 18

A second device adapted:
to possess a value h;
to receive from a third device a product RD that was received by the third device from a first device, wherein RD is a product of a random value rD and a public key value P;
to generate a product RB and to transmit the product RB to the third device, wherein RB is a product of a random value rB and the public key value P;
to obtain a challenge value eD and to transmit the challenge value eD to the third device;
to receive from the third device a value yD that was received by the third device from the first device;
to receive from the third device a challenge value eB that was received by the third device from the first device;
to calculate yDP+eDRD to obtain a first result;
to calculate hP to obtain a second result;
to compare the first result to the second result; and
to determine that the first device is in possession of the value h when the first result is identical to the second result,
wherein the public key value P generates a prime subgroup of the group E(Fq) of order p, wherein Fq is a finite field of prime order q, wherein the random values rD and rB are between the number 1 and the number (p−1), and wherein the challenge values eD and eB are between the number 1 and the number (p−1).

### Claim 19 (depends on 18)

The second device of claim 18, wherein the second device comprises an enterprise server.