An electronic watermark embedding apparatus includes means for storing a pixel matrix G with n rows and n columns of an input image, means for acquiring eigenvalues s1 to sn and eigenvectors p1 to pn of the pixel matrix G, means for selecting at least one pair of eigenvalues (si,sj) having different values from the eigenvalues s1 to sn and correcting the eigenvalues s1 to sn such that the values of the selected pair can be equal, means for creating a Jordan-normal-form matrix Sw having the corrected eigenvalues as diagonal elements and 1 as one of the nondiagonal elements corresponding to the selected pair, means for outputting the eigenvectors p1 to pn as electronic watermark key information, means for performing the inverse transform of diagonalization computing on the created matrix Sw by using the eigenvectors p1 to pn to create a pixel matrix Gw with n rows and n columns thereby and outputting it as an electronic-watermark-embedded image of the input image.