Method of generating prime numbers proven suitable for chip cards

摘要

This disclosure relates to methods for generating a prime number, which can be implemented in an electronic device. An example method can include calculating a candidate prime number using a formula Pr=2P·R+1, where P is a prime number and R is an integer. The method can also include applying the Pocklington primality test to the candidate prime number and rejecting the candidate prime number if it fails the Pocklington test. The integer can be generated from an invertible number belonging to a set of invertible elements modulo the product of numbers belonging to a group of small prime numbers greater than 2, where the candidate prime number is not divisible by any number of the group. The prime number P having a number of bits equal to within one bit, to half or a third of the number of bits of the candidate prime number.

主权项

1. A cryptographic method implemented in an electronic device including a microcircuit that is integrated in a smart card or a chip card, the method comprising steps of:
receiving, at the electronic device, data from a computer; (a) storing, in a memory of the electronic device, a group of small prime numbers greater than 2, (b) calculating, by the microcircuit, and storing, in the memory of the electronic device, a product of the prime numbers of the stored group, (c) generating, by the microcircuit, an invertible number belonging to a set of invertible elements modulo the stored product, (d) generating, by the microcircuit, a prime number, (e) generating, by the microcircuit, an integer, (f) generating, by the microcircuit, a candidate prime number having a desired number of bits, using a formula:
Pr=2P·R+1, Pr being the candidate prime number, P being the prime number and having a number of bits equal with a margin of one bit to half or one third of the number of bits of the candidate prime number, and R being the integer which is generated from the invertible number so that the candidate prime number is not divisible by any number of the stored group, the desired number of bits being greater than or equal to 512; (g) storing, in an the microcircuit, the candidate prime number as a proven prime number in response to passing the Pocklington primality test, else generating a new candidate prime number and performing steps (d) to (g) again with the new candidate prime number; and (h) applying, by the microcircuit, a cryptographic operation to data using the stored proven prime number, wherein the cryptographic operation is an encryption operation or a decryption operation, or a verification of a digital signature contained in the data.