A key sharing system is disclosed which uses a public key XεGF(n) (2≦Xn) which belongs to a Galois finite field GF(n) for an integer n (n≧2), and a polynomial T(•, •) defined in 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). In a key sharing apparatus of this system, an integer obtaining unit obtains an integer p (2≦pn), a transmission key calculation unit calculates a transmission key YεGF(n) using the integer p based on Y=T(p, X), a transmission key sending unit sends the transmission key Y to another key sharing apparatus, a transmission key reception unit receives a transmission key W from another key sharing apparatus, and a common key calculation unit calculates a common key ZεGF(n) using the transmission key W based on Z=T(p, W).
展开▼
