Patent ID: 7706528

Claim:
A key issuing server apparatus for calculating a prime candidate N larger than a known prime q and testing primality of the calculated prime candidate N and for issuing a public key and a private key of an RSA encryption system for a terminal, the key issuing server apparatus comprising: an information storage unit storing the known prime q, management information that is an odd number and corresponds to a prime to be generated, and a predetermined verification value; a random number generation unit operable to generate a random number; a candidate calculation unit operable to (i) read the prime q, the management information, and the verification value, (ii) calculate a multiplication value R by multiplying the management information by the random number, and (iii) calculate the prime candidate N, according to N=2×(the multiplication value R+w)×the prime q+1, using w satisfying 2×w×the prime q+1=the verification value (mod the management information); a primality testing unit operable to test primality of the calculated prime candidate N; an output unit operable to output the calculated prime candidate N as a prime N when the primality of the calculated prime candidate N is determined; and a key output unit operable to output the private key and the public key of the RSA encryption system to the terminal, the private key and the public key being generated using the prime N output by the output unit.