To eliminate authenticator specification and to evade abuse of a signature by separating message signature information and authenticating right information obtained from a message and authenticating the message on the basis of the message signature information and authenticating right information.

A digital signature of the message consists of message signature information V14 and authenticating right information T15. Then a signature information generating means 1 generates the signature, which is authenticated by using an authenticating means 2,. Namely, an individual identifier IDA11, message signature information V14 obtained from an open message M13, the identifier IDB12 of an opposite person which is made open, and authenticating information T obtained from the open message M13 are generated and outputted in a separated state. An authenticator B certifies whether or not the message has been sent from a legal body by using the obtained open message M13, message signature information V14, authenticating right information T, opposite- person open identifier IDA11.