A signature generation apparatus is capable of making a value used in signature generation processing difficult to analyze. In the signature generation apparatus, a random number generation module generates a len-bit random number u, a selection module converts the generated random number u into a bit expression, and acquires element pairs corresponding to the bit values from a table memory unit. A random element generation module applies a basic operation of a first group G and a second group to all acquired element pairs, and calculates an element Pk on the first group G and an element Pak on the second group Ga. The signature generation apparatus generates a digital signature S for a message m with use of a transformation module, a main operation module, an inverse transformation module, a multiplication module, a division module, and a signature data generation module.