# US 2017/0373841 A1 · Key exchange method, key exchange system, key device, terminal device, and program

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

- Number: US 2017/0373841 A1
- Document ID: US20170373841A1
- Status: Published application
- Kind: A1
- Application number: 15/542,538
- Filed: 2016-01-12
- Published: 2017-12-28
- Earliest claimed: 2015-01-16
- Assignees: Nippon Telegraph and Telephone Corporation
- Applicants: Nippon Telegraph and Telephone Corporation
- Inventors: Akira NAGAI; Tsunekazu SAITO; Tetsutaro KOBAYASHI
- Web page: https://patentgrep.com/patent/US20170373841A1

## CPC

- 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}
- G09C 1/00: Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00)
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 9/0819: {Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) (network architectures or network communication protocols for key distribution in a packet data network H04L63/062)}
- H04L 9/0841: {involving Diffie-Hellman or related key agreement protocols}
- H04L 9/0869: {involving random numbers or seeds}
- H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage}
- H04L 9/0897: {involving additional devices, e.g. trusted platform module [TPM], smartcard or USB}
- H04L 9/14: using a plurality of keys or algorithms
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 2209/046: of operations, operands or results of the operations
- H04L 2209/76: Proxy, i.e. using intermediary entity to perform cryptographic operations
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G09C: CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY

## Abstract

A random number generating unit generates random numbers s1, s2, s′1, and s′2. A public keys randomizing unit generates first randomized public keys information obtained by randomizing public keys using the random number s1 and second randomized public keys information obtained by randomizing the public keys using the random number s2. A proxy calculation unit calculates a first commission result by using a secret key and calculates a second commission result by using the secret key. A verification unit calculates a first verification value by using the random number s2, calculates a second verification value by using the random number s1, and verifies whether or not the first verification value and the second verification value coincide with each other. A common key calculation unit calculates a common key by using the random numbers s′1 and s′2 if the first verification value and the second verification value coincide with each other.

## Claims

### Claim 1

A key exchange method, wherein
s1 and s2 are assumed to be random numbers which are mutually prime and s′1 and s′2 are assumed to be random numbers which satisfy a predetermined relationship with the random numbers s1 and s2,
the key exchange method includes:
storing, in a storage of a key device, a secret key of a terminal device;
generating, by circuitry of the terminal device, the random numbers s1, s2, s′1, and s′2;
generating, by circuitry of the terminal device, first randomized public keys information obtained by randomizing a public key of the terminal device and a public key of another terminal device by using the random number s1 and second randomized public keys information obtained by randomizing the public key of the terminal device and the public key of the other terminal device by using the random number s2;
calculating, by circuitry of the key device, a first commission result from the first randomized public keys information by using the secret key and calculating a second commission result from the second randomized public keys information by using the secret key;
calculating, by circuitry of the terminal device, a first verification value from the first commission result by using the random number s2, calculating a second verification value from the second commission result by using the random number s1, and verifying whether or not the first verification value and the second verification value coincide with each other; and
calculating, by circuitry of the terminal device, if the first verification value and the second verification value coincide with each other, a common key from the first commission result and the second commission result by using the random numbers s′1 and s′2.

### Claim 2 (depends on 1)

The key exchange method according to claim 1, wherein
g is assumed to be an element of a group G, x is assumed to be the secret key of the terminal device, gx is assumed to be the public key of the terminal device, y is assumed to be a secret key of the other terminal device, gy is assumed to be the public key of the other terminal device, and r1 and r2 are assumed to be arbitrary numbers,
calculating, by circuitry of the terminal device, the first randomized public keys information by a formula below:
(g−r1x,gs1y+r1)
and calculating the second randomized public keys information by a formula below:
(g−r2x,gs2y+r2),
calculating, by circuitry of the key device, the first commission result Z1 by a formula below:
Z1=g−r1xg(s1y+r1)x
and calculating the second commission result Z2 by a formula below:
Z2=g−r2xg(s2y+r2)x,
verifying, by circuitry of the terminal device, whether or not the first verification value and the second verification value coincide with each other by a formula below:
Z1s2=Z2s1, and
calculating, by circuitry of the terminal device, the common key K by a formula below:
K=Z1s′1*Z2s′2.

### Claim 3 (depends on 1)

The key exchange method according to claim 1, wherein
G1, G2, and GT are assumed to be cyclic groups whose order is a prime number q with κ bit length, g1, g2, and gT are assumed to be generators of the groups G1, G2, and GT, respectively, e: G1×G2→GT is assumed to be pairing that satisfies gT=e(g1,g2), H: {0, 1}*→{0,1}κ, H1: {0, 1}*→G1, and H2: {0, 1}*→G2 are assumed to be cryptographic hash functions, m is assumed to be a natural number which is greater than or equal to 2, an assumption is made that i=1, . . . , m holds, ci,0,0, ci,0,1, ci,1,0, and ci,1,1 are assumed to be constants, piεZq[u0, u1, v0, v1] is assumed to be m polynomials which are defined by a formula below:
pi(u0,u1,v0,v1)=ci,0,0u0v0+ci,0,1u0v1+ci,1,0u1v0+ci,1,1u1v1,
zεZq is assumed to be a master secret key, Z1=g1zεG1 and Z2=g2zεG2 are assumed to be master public keys, IDA is assumed to be an identifier of the terminal device, QA,1=H1(IDA)εG1 and QA,2=H2(IDA)εG2 are assumed to be public keys, IDB is assumed to be an identifier of the other terminal device, QB,1=H1(IDB)εG1 and QB,2=H2(IDB)εG2 are assumed to be public keys, DA,1=QA,1z and DA,2=QA,2z are assumed to be secret keys of the terminal device, DB,1=QB,1z and DB,2=QB,2z are assumed to be secret keys of the other terminal device, zAεZq is assumed to be a short-term secret key of the terminal device, XA,1=g1xA and XA,2=g2xA are assumed to be short-term public keys of the terminal device, zBεZq is assumed to be a short-term secret key of the other terminal device, XB,1=g1xB and XB,2=g2xB are assumed to be short-term public keys of the other terminal device, Pi,B is assumed to be a value which is defined by a formula below:
Pi,B=QB,2ci,0,0XB,2ci,0,1,
si1 and si1 are assumed to be random numbers which are mutually prime, and s′i1 and s′i2 are assumed to be random numbers which satisfy a predetermined relationship with the random numbers si1 and si2,
generating, by circuitry of the terminal device, the random numbers si1, si2, s′i1, and s′i2,
calculating, by circuitry of the terminal device, the first randomized public keys information for i=1, . . . , m by a formula below:
(g2−ri1,g2ri1Pi,Bsi1)
and calculating the second randomized public keys information for i=1, . . . , m by a formula below:
(g2−ri2,g2ri2Pi,Bsi2),
calculating, by circuitry of the key device, the first commission result ζi1 for i=1, . . . , m by a formula below:
ζi1=e(DA,1,g2−ri1)e(DA,1,g2ri1Pi,Bsi1)
and calculating the second commission result ζi2 for i=1, . . . , m by a formula below:
ζi2=e(DA,1,g2−ri2)e(DA,1,g2ri2Pi,Bsi2),
verifying, by circuitry of the terminal device, whether or not the first verification value and the second verification value coincide with each other for i=1, . . . , m by a formula below:
ζi1si2=ζi2si1, and
generating, by circuitry of the terminal device, the common key by using commission results ζ1, . . . , ζm after calculating a commission result ζi for i=1, . . . , m by a formula below:
ζi=ζi1s′i1ζi2s′i2.

### Claim 4 (depends on 1)

The key exchange method according to claim 1, wherein
G is assumed to be a cyclic group whose order is a prime number q with κ bit length, g is assumed to be a generator of the group G, H: {0, 1}*→{0,1}κ and H1: {0, 1}*→G are assumed to be cryptographic hash functions, m is assumed to be a natural number which is greater than or equal to 2, an assumption is made that i=1, . . . , m holds, ci,0,0, ci,0,1, ci,1,0, and ci,1,1 are assumed to be constants, piεZq[u0, u1, v0, v1] is assumed to be m polynomials which are defined by a formula below:
pi(u0,u1,v0,v1)=ci,0,0u0v0+ci,0,1u0v1+ci,1,0u1v0+ci,1,1u1v1,
sAεZq is assumed to be the secret key of the terminal device, SA=gsAεG is assumed to be the public key of the terminal device, sBεZq is assumed to be a secret key of the other terminal device, SB=gsBεG is assumed to be the public key of the other terminal device, xAεZq is assumed to be a short-term secret key of the terminal device, XA=gxAεG is assumed to be a short-term public key of the terminal device, xBεZq is assumed to be a short-term secret key of the other terminal device, XB=gxBεG is assumed to be a short-term public key of the other terminal device, FA is assumed to be a homomorphism which is FA: G→G, h→hxA, αB,i is assumed to be a value which is defined by a formula below:
αB,i=XBci,0,0SBci,0,1,
si1 and si2 are assumed to be random numbers which are mutually prime, and s′i1 and s′i2 are assumed to be random numbers which satisfy a predetermined relationship with the random numbers si1 and si2,
generating, by circuitry of the terminal device, the random numbers si1, si2, s′i1, and s′i2,
calculating, by circuitry of the terminal device, the first randomized public keys information for i=1, . . . , m by a formula below:
(g1−1,g1αB,isi1)
and calculating the second randomized public keys information for i=1, . . . , m by a formula below:
(g2−1,g2αB,isi2)
calculating, by circuitry of the key device, the first commission result ζi1 for i=1, . . . , m by a formula below:
ζi1=FA(g1−1)FA(g1αB,isi1)
and calculating the second commission result ζi2 for i=1, . . . , m by a formula below:
ζi2=FA(g2−1)FA(g2αB,isi2),
verifying, by circuitry of the terminal device, whether or not the first verification value and the second verification value coincide with each other for i=1, . . . , m by a formula below:
ζi1si2=ζi2si1, and
generating, by circuitry of the terminal device, the common key by using commission results ζ1, . . . , ζm after calculating a commission result ζi for i=1, . . . , m by a formula below:
ζi=ζi1s′i1ζi2s′i2.

### Claim 5 (depends on 1, 2, 3, 4)

The key exchange method according to any one of claims 1 to 4, wherein
storing, in the storage of the key device, intrinsic information of the terminal device, and
calculating, by circuitry of the key device, the first commission result and the second commission result if intrinsic information which is received along with the first randomized public keys information and the second randomized public keys information coincides with the intrinsic information of the terminal device.

### Claim 6

A key exchange system, wherein
s1 and s2 are assumed to be random numbers which are mutually prime and s′1 and s′2 are assumed to be random numbers which satisfy a predetermined relationship with the random numbers s1 and s2,
the key exchange system includes a plurality of terminal devices and at least one key device,
each of the terminal devices including:
circuitry configured to:
generate the random number s1, s2, s′1, and s′2;
generate first randomized public keys information obtained by randomizing a public key of the terminal device and a public key of another terminal device by using the random number s1 and second randomized public keys information obtained by randomizing the public key of the terminal device and the public key of the other terminal device by using the random number s2;
receive a first commission result and a second commission result from the key device, calculate a first verification value from the first commission result by using the random number s2, calculate a second verification value from the second commission result by using the random number s1, and verify whether or not the first verification value and the second verification value coincide with each other; and
calculate a common key from the first commission result and the second commission result by using the random numbers s′1 and s′2 if the first verification value and the second verification value coincide with each other; and
the key device including:
another circuitry configured to:
store a secret key of the terminal device in a storage; and
calculate the first commission result from the first randomized public keys information by using the secret key and calculates the second commission result from the second randomized public keys information by using the secret key.

### Claim 7

A key device, wherein
s1 and s2 are assumed to be random numbers which are mutually prime and s′1 and s′2 are assumed to be random numbers which satisfy a predetermined relationship with the random number s1 and s2,
the key device including:
circuitry configured to:
store a secret key of a terminal device in a storage; and
calculate a first commission result from a first randomized public keys information by using the secret key and calculates a second commission result from a second randomized public keys information by using the secret key,
the first randomized public keys information is obtained by randomizing a public key of the terminal device and a public key of another terminal device by using the random number s1; and
the second randomized public keys information is obtained by randomizing the public key of the terminal device and the public key of the other terminal device by using the random number s2.

### Claim 8

A terminal device, wherein
s1 and s2 are assumed to be random numbers which are mutually prime and s′1 and s′2 are assumed to be random numbers which satisfy a predetermined relationship with the random numbers s1 and s2,
the terminal device including:
circuitry configured to:
generate first randomized public keys information obtained by randomizing a public key of the terminal device and a public key of another terminal device by using the random number s1 and second randomized public keys information obtained by randomizing the public key of the terminal device and the public key of the other terminal device by using the random number s2;
receive a first commission result and a second commission result which are calculated by a key device, calculate a first verification value from the first commission result by using the random number s2, calculate a second verification value from the second commission result by using the random number s1, and verify whether or not the first verification value and the second verification value coincide with each other; and
calculate a common key from the first commission result and the second commission result by using the random numbers s′1 and s′2 if the first verification value and the second verification value coincide with each other,
the first commission result is calculated from the first randomized public keys information by using a secret key of the terminal device; and
the second commission result is calculated from the second randomized public keys information by using the secret key of the terminal device.

### Claim 9

A non-transitory computer readable medium including computer executable instructions that make a key device, wherein
s1 and s2 are assumed to be random numbers which are mutually prime and s′1 and s′2 are assumed to be random numbers which satisfy a predetermined relationship with the random number s1 and s2,
perform a method including:
storing a secret key of a terminal device in a storage; and
calculating a first commission result from a first randomized public keys information by using the secret key and calculate a second commission result from a second randomized public keys information by using the secret key,
the first randomized public keys information is obtained by randomizing a public key of the terminal device and a public key of another terminal device by using the random number s1; and
the second randomized public keys information is obtained by randomizing the public key of the terminal device and the public key of the other terminal device by using the random number s2.

### Claim 10

A non-transitory computer readable medium including computer executable instructions that make a terminal device, wherein
s1 and s2 are assumed to be random numbers which are mutually prime and s′1 and s′2 are assumed to be random numbers which satisfy a predetermined relationship with the random numbers s1 and s2,
perform a method including:
generating first randomized public keys information obtained by randomizing a public key of the terminal device and a public key of another terminal device by using the random number s1 and second randomized public keys information obtained by randomizing the public key of the terminal device and the public key of the other terminal device by using the random number s2;
receiving a first commission result and a second commission result which are calculated by a key device, calculating a first verification value from the first commission result by using the random number s2, calculating a second verification value from the second commission result by using the random number s1, and verifying whether or not the first verification value and the second verification value coincide with each other; and
calculating a common key from the first commission result and the second commission result by using the random numbers s′1 and s′2 if the first verification value and the second verification value coincide with each other,
the first commission result is calculated from the first randomized public keys information by using a secret key of the terminal device, and
the second commission result is calculated from the second randomized public keys information by using the secret key of the terminal device.
