A key generating apparatus generates a fibration X(x, y, t)=0 of an algebraic surface X serving as a part of a public key and defined on a finite field Fq (where q=pr [p is a prime number and r is an extended degree]) and a private key which is two sections D1 and D2 corresponding to the fibration X(x, y, t)=0. The fibration X(x, y, t) is generated such that a term (cij(t)xiyj) of xiyj having a 1-variable polynomial cij(t) of t as a coefficient is included in the fibration X(x, y, t).