Patent ID: 7231048

Claim:
A key sharing system for enabling a first key sharing apparatus and a second key sharing apparatus to share a key, using a public key XεGF(n) which belongs to a Galois finite field GF(n) for an integer n (n≧2), and which is equal to or larger than 2 and smaller than n, and a polynomial T(•, •) which is defined in the Galois finite field GF(n) by T ( a, x )≡ S ( a, x )mod n where S(•, •) is a Chebyshev polynomial defined by S ( a , cos θ)=cos( a θ) where a is an integer (a≧2), and said first key sharing apparatus and said second key sharing apparatus are connected with each other via a computer network, wherein: (a) said first key sharing apparatus comprises an integer obtaining unit which obtains an integer p which is equal to or larger than 2, and smaller than n, a transmission key calculation unit which calculates a transmission key YεGF(n) using the obtained integer p based on the following equation Y=T ( p, X ), and a transmission key sending unit which sends the calculated transmission key Y to said second key sharing apparatus via a computer network; (b) said second key sharing apparatus comprises an integer obtaining unit which obtains an integer p which is equal to or larger than 2, and smaller than n, a transmission key calculation unit which calculates a transmission key YεGF(n) using the obtained integer p based on the following equation W=T ( q, X ), and a transmission key sending unit which sends the calculated transmission key W to said first key sharing apparatus via a computer network; (c) said first key sharing apparatus further comprises a transmission key reception unit which receives the transmission key W sent from said second key sharing apparatus via a computer network, and a common key calculation unit which calculates a common key ZεGF(n) using the received transmission key W based on the following equation Z=T ( p, W ); and (d) said second key sharing apparatus further comprises a transmission key reception unit which receives the transmission key Y sent from said first key sharing apparatus via a computer network, and a common key calculation unit which calculates a common key Z′εGF(n) using the received transmission key Y based on the following equation Z′=T ( q, Y ).