Method for generating large prime number in embedded system

摘要

A method for generating a large prime number in an embedded system, comprising: (1) setting all identifiers in an identifier group in a first storage area; generating and storing a random number with preset bit length in a third storage area; modulizing the data in the third storage area by using the data stored in the storage unit of a second storage area as a modulus; determining the serial number of the identifier to be reset in the identifier group according to the modulized value and the data in the storage unit corresponding to the modulized value; and resetting the identifier corresponding to the serial number; (2) judging whether a set identifier exists in the identifier group, if yes, then executing step (3); otherwise, returning to step (1); and (3), determining a number to be detected according to the random number and the serial number of the set identifier in the identifier group; detecting the primality of the number to be detected; if the number to be detected passes the primality detection, then outputting the number to be detected; and if the numbers to be detected corresponding to all the set identifiers in the identifier group fail to pass the primality detection, then returning to step (1). The present method has high efficiency and is suitable for an embedded system.

主权项

1. An encryption process, the encryption process uses a large prime number as a key parameter, the large prime number is generated in an embedded system, the embedded system comprising a first storage area and a second storage area, wherein the first storage area stores an identifier group with a predetermined size, sequence numbers of the identifiers in the identifier group are consecutive integers including 0, and different identifiers have different sequence numbers, and the second storage area comprises a plurality of storage units, and the different storage units store different prime numbers,
the method of generating the large prime number in the embedded system comprising steps of: 1) resetting all identifiers in the identifier group stored in the first storage area; using a random number generator to generate a random number with a predetermined bit length, and storing the random number in a third storage area, taking the data of the storage unit in the second storage area as modulus to perform modulus operation on the data stored in the third storage area to obtain a modulus value; according to the modulus value and the data stored in the storage unit corresponding to the modulus value, determining a sequence number of the identifier which requires to be reset in the identifier group, and resetting the identifier corresponding to the sequence number; 2) determining whether a reset identifier exists in the identifier group, if yes, go to Step 3); if no, go back to Step 1); 3) determining a number to be tested according to the random number and the sequence number of the reset identifier in the identifier group, and performing a primality test on the number to be tested; if the number to be tested passes the primality test, outputting the number to be tested as a large prime number; while if numbers to be tested corresponding to all the reset identifiers in the identifier group do not pass the primality test, go back to Step 1); and using the large prime number in the encryption process.