METHOD AND SYSTEM FOR DERIVING DETERMINISTIC PRIME NUMBER

Abstract

A system generating a prime number comprising a prime number generator (PNG) module and a pseudorandom number generator (PRNG) module which is configured to: initialise the pseudorandom number generator (PRNG) module; receive a request from the PNG module, the request containing a bit length of the pseudorandom number required; generate the required bit length of pseudorandom number; transmit a response containing the generated bit length of pseudorandom numbers to the PNG module. The PNG module is configured to: transmit the request containing the bit length of the pseudorandom numbers required; receive the response from the PRNG module; assign the pseudorandom numbers in the response to form raw data PPP; set a least significant bit (LSB) and most significant bit (MSB) of PPP as 1 to obtain a first big odd number denoted as PP; and execute an algorithm to determine a first big prime number starting from odd number PP.

Claims

1. A system for generating a prime number comprising: a pseudorandom number generator (PRNG) module and a prime number generator (PNG) module, wherein the PNG module is configured to: obtain a pseudorandom number from the PRNG module; determine a big odd number denoted as PP according to the pseudorandom number; execute primality test on PP; and determine PP as the output prime number in response to PP passing the primality test.

2. The system according to claim 1 wherein the step performed by the PNG module of executing primality test on PP in response to PP has no small prime factor comprises: determining the biggest integer s such that PP1=2.sup.s.Math., where is a positive odd integer; obtaining another pseudorandom number from the PRNG module; selecting a pseudorandom number within a range of 2 and PP2 according to the another pseudorandom number; and determining PP is a composite number if .sup.1 mod PP and a.sup.2.sup.r.sup.1 mod PP for all 0rs1.

3. The system according to claim 1, wherein the PRNG module comprises a PRNG to generate the required bit length of pseudorandom number, the PRNG takes an input seed value from a root key from a source and a given bit length.

4. The system according to claim 1, wherein the PRNG module is configured to: receive a request from the PNG module, the request containing a bit length of the pseudorandom number required; generate the required bit length of pseudorandom number; and transmit a response containing the generated bit length of pseudorandom numbers to the PNG module.

5. The system according to claim 1, wherein the PNG module is further configured to: run filter function on PP to check if it has any small prime factor; the step of executing modified Rabin-Miller primality test on PP comprising: execute modified Rabin-Miller primality test on PP in response to PP has no small prime factor.

6. A method for generating a prime number comprising: obtaining a pseudorandom number; determining a big odd number denoted as PP according to the pseudorandom number; executing primality test on PP; and determining PP as the output prime number in response to PP passing the primality test.

7. The method according to claim 6 wherein the step of executing primality test on PP in response to PP has no small prime factor comprising: determining the biggest integer s such that PP1=2.sup.s.Math., where is a positive odd integer; obtaining another pseudorandom number; selecting a pseudorandom number a within a range of 2 and PP2 according to the another pseudorandom number; and determining PP is a composite number if .sup.1 mod PP and .sup.2.sup.r.sup.1 mod PP for all 0rs1.

8. The method according to claim 7, wherein a required bit length of pseudorandom number is generated by a seed value from a root key from a source and a given bit length.

9. The method according to claim 8, wherein the root key is obtained from a device hardware unique key and the given bit length is 1024 bits.

10. The method according to claim 6, the method further comprising: running filter function on PP to check if it has any small prime factor; the step of executing modified Rabin-Miller primality test on PP comprising: executing modified Rabin-Miller primality test on PP in response to PP has no small prime factor.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0063] The above advantages and features in accordance with this invention are described in the following detailed description and are shown in the following drawings:

[0064] FIG. 1 illustrating a system 100 for performing the proposed algorithm to determine prime numbers in accordance with this application;

[0065] FIG. 2 illustrating a timing diagram 100 of the information flow between the pseudorandom number generator module and a prime number generator module in accordance with this application;

[0066] FIG. 3 illustrating a process 300 performed by a pseudorandom number generator module to generate and transmit pseudorandom number in accordance with this application;

[0067] FIG. 4 illustrating an example of a pseudorandom number generator for generating pseudorandom numbers in accordance with this application;

[0068] FIG. 5 illustrating a process 500 performed by the prime number generator module for determining a prime number in accordance with this application;

[0069] FIG. 6 illustrating a first process 600 performed by the prime number generator module executing a first algorithm to determine the first prime number starting from odd number PP in accordance with this application;

[0070] FIG. 7 illustrating a first process 700 performed by the prime number generator module executing a second algorithm to determine the first prime number starting from odd number PP in accordance with this application;

[0071] FIG. 8 illustrating a process 800 performed by the PNG module 140 executing the Rabin-Miller primality test in accordance with this application;

[0072] FIG. 9 illustrating an overall process 900 for generating and recovering the two prime numbers for generating a RSA key pairs in accordance with this application;

[0073] FIG. 10 illustrating an example of an application of system 100 in accordance with this application.

DESCRIPTION OF EMBODIMENTS

[0074] This application relates to a method and system for obtaining two prime numbers for generating a pair of keys. Particularly, the application relates to a method and system implementing a deterministic derivation function to obtain prime numbers.

[0075] In this application, it is proposed that the algorithm to be implemented is a deterministic derivation function that takes a seed value (usually a root key of 256 bits) and a given bit length, and outputs a prime number with the given bit length. When the same input values are provided to this algorithm, the output prime number is required to be always the same. The proposed algorithm consists of two parts:

[0076] First, the primes are generated from RK, where deterministic procedure is used to find primes and fast recovery information. The fast recovery information is offset value allowing quick recovery.

[0077] Secondly, primes are recovered by using RK and recovery information. This may happen in different device during the first part. For example powerful server may pre-compute fast recovery values for P and Q. Devices with less computation power can quickly recover P and Q from recovery values.

[0078] FIG. 1 illustrates a system 100 for performing the proposed algorithm. The system 100 comprises a pseudorandom number generator (PRNG) module 130 and a prime number generator (PNG) module 140. In operation, the PNG module 140 sends a request for required bit length of pseudorandom number to the PRNG module 130. In response to the request, the PRNG module 130 generates pseudorandom number and sends the required bit length of pseudorandom number to the PNG module 130. Upon receipt of the pseudorandom number, the PNG module 140 executes an algorithm to determine 2 large prime numbers, namely, P and Q. The use of two separate modules is such that the actual process of generating the pseudorandom number by the PRNG module 130 is not known to the PNG module 140. Further details of the processes performed by the PRNG module 130 and PNG module 140 would be described below.

[0079] FIG. 2 illustrates a timing diagram 200 of the information flow between the PRNG module 130 and the PNG module 140. Timing diagram 200 begins with step 205 where the PRNG module 130 initialises.

[0080] In step 210, the PNG module 140 generates and transmits a request for bit length of pseudorandom number to the PRNG module 130. In response to receiving the request, the PRNG module 130 generates the required bit length of pseudorandom number in step 215.

[0081] In step 220, the PRNG module 130 transmits the requested bit length of pseudorandom number to the prime number generator module 140. In response to receiving the requested bit length of pseudorandom number, the PNG module 140 generates the prime numbers. Steps 210, 215 and 220 are repeated as and when the PNG module 140 request for pseudorandom number. Further details of the processes performed by each of the PRNG module 130 and PNG module 140 would be described as follows.

[0082] FIG. 3 illustrates a process 300 performed by the PRNG module 130 to generating and transmitting pseudorandom number to the PNG module 140 in accordance with this application.

[0083] Process 300 begins with step 305 where the PRNG 134 is initialised. The PRNG module 130 then receives a request from the PNG module 140 in step 310. The request contains the bit length of the pseudorandom number required.

[0084] In response to receiving the request, the PRNG module 130 generates, via the PRNG 134, the required bit length of pseudorandom number in step 315.

[0085] In step 320, the PRNG module 130 transmits the generated bit length of pseudorandom numbers to the PNG module 140. Steps 310-320 are repeated as and when the PRNG module 130 receives a request from the PNG module 140 and will repeat from step 305 when the PRNG 134 is being requested to be initialised.

[0086] Essentially, the PRNG module 130 comprises a PRNG 134 for generating pseudorandom number. PRNG takes an input seed value (usually of fixed length) and output a pseudo-random bit stream of arbitrary length. The output pseudo-random bit stream will always be the same if the input seed value is used. FIG. 4 illustrates an example of a PRNG 134 where the seed value 110 is based on the root key of 256 bits from a mobile device and a given bit length, i.e. Seed=(RK, bit length). The given bit length determines the bit length of the output of the PRNG 134.

[0087] With the seed value 110, the PRNG 134 generates pseudorandom number 135, B0, B1, B2, . . . . On the right of the PRNG 134 shows the expanded view of the PRNG 134 taking the seed value 110 and block-wise counter starting from zero and running through a hash function, SHA-256 to generate the pseudo-random stream, which is deterministic and can be of arbitrary length. The output of the PRNG 134 as illustrated in FIG. 4 can be expressed as follows, Bi=SHA-256(Seed,i). Assuming the bit length is 256-bit, the block size of each block of pseudorandom number 135 is 256-bit. If the bit length is 1-bit, the block size of each block of pseudorandom number 135 is 1-bit. The choice of the bit length is left to those skilled in the art.

[0088] The pointers 135a and 135b are to illustrate that assuming the bit length requested by the PNG module 140 is 256 bits, the PRNG module 130 would generate B0 with the pointer ending at 135a and B0 would be sent to the PNG module 140. If the next request from the PNG module 140 is 256 bits, the PRNG module 130 would generate B1 with the pointer ending at 135b and B1 would be sent to the PNG module 130. In another example, assuming the bit length requested by the PNG module 140 is 1000 bits, the PRNG module 130 would generate B0, B1, B2 and B3 with the pointer ending at the end of B3 and the first 1000 bits from B0-B3 would be sent to the PNG module 140 with the remaining 24 bits of data discarded. If the next request from the PNG module 140 is 500 bits, the PRNG module 130 would generate B4 and B5 with the pointer ending at the end of B5 and the first 500 bits from B4-B5 would be sent to the PNG module 140 with the remaining 12 bits of data discarded.

[0089] Briefly, the PRNG module 130 would generate blocks of pseudorandom number at least until the required bit length of pseudorandom number is available. The PRNG 134 would pause after generating the blocks of pseudorandom number and wait for the next request from the PNG module 140 while the PRNG module 130 transmits the required bit length of pseudorandom number to the PNG module 140.

[0090] One skilled in the art will recognise that other choices of PRNG may be implemented without departing from this application. For example, NIST (National Institute of Standards and Technology of USA) has DRBG standards such as CTR_DRBG, HASH_DRBG and HMAC_DRBG, whose specification can be found in NIST Special Publication 800-90A.

[0091] FIG. 5 illustrates a process 500 performed by the PNG module 140 for determining a prime number in accordance with this application. Process 500 begins with step 505 where the PNG module 140 transmits a request containing the bit length of the pseudorandom numbers required. For this illustration, we would be using 1024 bits for determining a prime number, since the RSA key pair uses 2048 bits, i.e. 1024 bits for each of P and Q.

[0092] In step 510, the PNG module 140 receives the bit length of 1024 bits of pseudorandom number from the PRNG module 130.

[0093] In response to receiving the pseudorandom number from the PRNG module 130, the PNG module 140 assigns the pseudorandom numbers to form raw data PPP which is 1024 bits in step 515.

[0094] In step 520, the PNG module 140 sets the least significant bit (LSB) and most significant bit (MSB) of PPP 1 and obtains a big odd number denoted as PP. The big odd number is for determining the big prime number, P.

[0095] In step 525, the PNG module 140 executes an algorithm to determine the first prime number starting from odd number PP. In short, the algorithm receives the odd number PP as an input and returns an output which is being assigned as the big prime number, P. Briefly, the algorithm comprises checking whether PP has small a prime factor. If PP has a small prime factor (e.g. p.sub.i|PP), the algorithm repeats the check for the next prime, i.e. set PP=Next(PP, step). The Next function (PP=Next(PP, step)) can be addition (PP=PP+step), XOR (PP=PPstep) and modular addition (PPPP+step mod N) etc. One skilled in the art will recognise that any other types of function may be chosen as the Next function, as long as we can repeatedly apply it to the value of PP to enumerate different possible values of PP.

[0096] If PP does not have a small prime factor, the algorithm runs Rabin-Miller primality test on PP with the random number (a). It is important to note that random number (a) is requested from the PRNG module 130. As mentioned above, the more iteration used in Rabin-Miller primality test increases the confidence in the primality of the output probabilistic prime number, but requires more computing power and time. Hence, there will be trade-offs between having a good primality and performance. If the PP does not pass Rabin-Miller primality test, the algorithm repeats from the check for the next prime, i.e. set PP=Next(PP, step). If the PP passes Rabin-Miller primality test, the algorithm determines the PP as the prime number P. Further details on the algorithm to determine the next prime number would be described below.

[0097] Process 500 illustrates the process of generating one big prime number. In order to determine two prime numbers for generating RSA key pair, process 500 may be repeated to determine the second prime number, Q. Alternatively, process 500 may be modified such that instead of requesting a bit length of pseudorandom number to form a big odd number PP in steps 505-520, process 500 may request for a bit length of pseudorandom number to form two big odd numbers PP and QQ. Thereafter, step 525 may be executed twice either sequentially or concurrently to determine two big prime numbers, P and Q.

[0098] FIG. 6 illustrates a first process 600 performed by the PNG module 140 executing a first algorithm to determine a prime number starting from odd number PP. Let x be the input value from step 525 of process 500, i.e. x=PP. Process 600 begins with step 605 by calculating the product of m number of small prime number, prod=.sub.i=0.sup.m1p.sub.i, where p.sub.i is the i-th smallest prime number, i.e. 2. We choose the smallest prime numbers as {p.sub.i}.sub.0i<m={2, 3, 5, 7, 11, 13 . . . }. When we are deriving a 1024-bit prime number, the maximum value of m is 130. Since if m>130, prod becomes more than 1024 bits, the filter of small prime factor no longer works. It means that we can filter at most 130 small prime factors using this technique.

[0099] In step 610, process 600 initialises two counters as zero, namely, d1=0 and d2=0. Process 600 then calculates the greatest common divisor of x and prod in step 615 with the following function, t=GCD(x,prod).

[0100] In step 620, if t1, it means t is a factor of x (t|x) and x is not a prime number. Hence, process 600 proceeds to step 625. If t=1, it means that x does not have factors of small primes any more: GCD(x,prod)=1, which make it a good candidate for primality test. In short, if t=1, x may be a prime number and process 600 proceeds to step 630.

[0101] In step 625, process 600 sets x=x+step1 and d1=d1+1 and repeats from step 615. Preferably, step1=2. The next function (x=x+step1) can be replaced with XOR function (x=xstep1) or modular addition (xx+step1 mod N) etc.

[0102] In step 630, process 600 runs Rabin-Miller primality test on x. Further details on the Rabin-Miller primality test would be described below with reference to FIG. 8.

[0103] In step 635, if the Rabin-Miller test fails on x, process 600 proceeds to step 640. If x passes the Rabin-Miller test, process 600 proceeds to step 645.

[0104] In step 640, process 600 updates x=x+prod, and d2=d2+1 and repeats from step 630. It is observed that GCD (x+prod, prod)=GCD (x, prod)=1. The updated value of x doesn't have factor of small primes either, which makes it also a good candidate. If x pass the Rabin-Miller test, process 600 proceeds to step 645 and outputs the value x and stores d1 and d2 as offset values. The offset values d1 and d2 are stored on the memory for recovering the prime number.

[0105] Process 600 may be repeated to determine another prime number, Q. Process 600 may be executed twice either sequentially or concurrently to determine both prime numbers, P and Q. Further details on generating two prime numbers would be described below with reference to FIG. 9.

[0106] In order to recover the 2 prime numbers, step 525 of process 500 is replaced with a recovery process. In short, in order to recover the two prime numbers, P and Q, the recovery process goes through steps 505-520 to obtain two big odd numbers PP and QQ and thereafter executes a recovery process where the PNG module 140 retrieves the offset values d1, d2 of both P (d.sub.1.sup.P and d.sub.2.sup.P) and Q (d.sub.1.sup.Q and d.sub.2.sup.Q) from the memory and determines P and Q, with the following functions:

P=PP+(step1d.sub.1.sup.P)+(prodd.sub.2.sup.P)

Q=QQ+(step1d.sub.1.sup.Q)+(prodd.sub.2.sup.Q)

[0107] Where step1 is 2; prod is the product of m number of small prime number, prod=.sub.i=0.sup.m1p.sub.i, where p.sub.i is the i-th smallest prime number, i.e. p.sub.0=2, p.sub.1=3, p.sub.2=5, . . . .

[0108] As observed in the recovery process, the prime number P can be easily recovered by the following function, P=PP+(2d1)+(prod.Math.d2) without the time-consuming primality testing algorithm. Hence, recovery process runs much faster than the generation process.

[0109] FIG. 7 illustrates a second process 700 performed by the PNG module 140 executing a second algorithm to determine the first prime number starting from odd number PP. Let x be the input value from step 525 of process 500, i.e. x=PP. Process 700 begins with step 705 by calculating rx.sub.ix mod p.sub.i for 0i<m, where p.sub.i is the i-th smallest prime number and rx.sub.i is a single-precision word (usually 32-bit or 64-bit).

[0110] In step 710, process 700 sets counter d=0.

[0111] In step 715, process check if rx.sub.i+2d can be divided by any p.sub.i for 0i<m.

[0112] In step 720, if i, s. t. p.sub.i|rx.sub.i+2d, process 700 proceeds to step 730 and runs the Rabin-Miller primality test. In other words, if for all i[0, m1], rx.sub.i+2d cannot be divided by p.sub.i, process 700 proceeds to step 730. Otherwise, process 700 proceeds to step 725 and sets d=d+1. In step 720, if p.sub.i|rx.sub.i+2d, we know that x+2drx.sub.i+2d0 mod p.sub.i, x+2d is not prime. Checking if p.sub.i|rx+2d only cost a single-precision remainder operation, which is much more efficient than remainder calculation on the big number x+2d. This technique allows us to efficiently check m number of small prime factors.

[0113] After step 725, process 700 repeats from step 715.

[0114] In step 730, process 700 runs the Rabin-Miller primality test on x+2d. Further details on the Rabin-Miller primality test would be described below with reference to FIG. 8.

[0115] In step 735, if x+2d does not pass Rabin-Miller test, process 700 proceeds to step 725. Otherwise, process 700 proceeds to step 745 and outputs x+2d a big prime number and stores d as offset value. The offset value d is stored on the memory for recovering the big prime number.

[0116] Process 700 may be repeated to determine another prime number, Q. Process 700 may be executed twice either sequentially or concurrently to determine both prime numbers, P and Q. Further details on generating two prime numbers would be described below with reference to FIG. 9.

[0117] In order to recover the 2 prime numbers, step 525 of process 500 is replaced with a recovery process. In short, in order to recover the two prime numbers, P and Q, the recovery process goes through steps 505-520 to obtain two big odd numbers PP and QQ and thereafter execute a recovery step where the PNG module 140 retrieves the offset value d of both P (d.sup.P) and Q (d.sup.Q) from the memory and determines P and Q, with the following functions:

P=PP+(2d.sup.P)

Q=QQ+(2d.sup.Q)

[0118] FIG. 8 illustrates a process 800 performed by the PNG module 140 executing the Rabin-Miller primality test in step 630 of process 600 and step 730 of process 700. Let y be the odd number to be tested. In other words, y=x in relation to step 630 in process 600 and y=x+2d in relation to step 730 in process 700. Process 800 begins with step 805 where the PNG module 140 determines the biggest integer s such that y1=2.sup.s.Math., where is a positive odd integer.

[0119] In step 810, the PNG module 140 transmits a request containing the bit length of the pseudorandom numbers required. For purpose of this illustration, we would be using 1024 bits.

[0120] In step 815, the PNG module 140 receives the bit length of 1024 bits of pseudorandom number from the PRNG module 130.

[0121] In response to receiving the pseudorandom number from the PRNG module 130, the PNG module 140 assigns the pseudorandom numbers to form a first random number in step 820.

[0122] In step 825, the PNG module 140 selects a second random number which is in a range of [2, y2] with the following expression, =2+( mod (y3)). One skilled in the art will recognise that other methods of selecting the second random number a may be implemented without departing from the application.

[0123] In step 830, the PNG module 140 determines if y is a composite number. In particular, if .sup.1 mod y and .sup.2.sup.r.sup.1 mod y for all 0rs1, y is a composite number and y is not a prime.

[0124] Steps 810-830 are repeated for K times with different random number a and if no judgment that y is composite is given, y is output as a probabilistic prime number.

[0125] Rabin-Miller primality test is probabilistic, which means if y is prime, it will never be determined as composite; if y is composite, there is a small chance that it will be determined as prime number. As observed, by repeating the above test with different choices of random number a in steps 810-825, the chance that a composite number be determined as prime will be decreased exponentially.

[0126] FIG. 9 illustrates an overall process 900 for determining two prime numbers for generating a RSA key pairs from a given root key RK and bit length. Process 900 begins with step 905 where the PNG module 140 transmits a request containing the bit length of the pseudorandom numbers required. For this illustration, we would be using 2048 bits for determining two prime numbers, since the RSA key pair uses 2048 bits, i.e. 1024 bits for each of P and Q.

[0127] In step 910, the PNG module 140 receives the bit length of 2048 bits of pseudorandom number from the PRNG module 130.

[0128] In response to receiving the pseudorandom number from the PRNG module 130, the PNG module 140 assigns the first 1024 bits of pseudorandom numbers to form a first raw data PPP and the subsequent 1024 bits of pseudorandom numbers to form a second raw data QQQ.

[0129] In step 920, the PNG module 140 sets the least significant bit (LSB) and most significant bit (MSB) of PPP and QQQ as 1 and obtains a first big odd number denoted as PP and a second big odd number denoted as QQ. The first big odd number is for determining the first big prime number, P while the second big odd number is for determining the second big prime number, Q.

[0130] In step 925, the PNG module 140 determines whether the offset values are stored in the memory. If the offset values are stored on the memory, process 900 proceeds to step 935 to recover the prime numbers based on the offset values. If the offset values are not stored on the memory, process 900 proceeds to step 930 to execute the algorithm to determine the prime numbers.

[0131] In step 930, the PNG module 14 executes the algorithm to determine the prime numbers according to either process 600 or process 700. In this regard, either process 600 or process 700 is selected to determine the two prime numbers. Alternatively, it is also possible to execute process 600 to determine the first prime number and process 700 to determine the second prime number, and vice versa, without departing from the application.

[0132] In step 935, the recovery process is dependent on the selection of process 600 or process 700 for generating the prime numbers, P and Q.

[0133] The two prime numbers, P and Q are then used for generating the RSA key pairs. The details of generating the RSA key pairs are well known and have been described above in the summary of prior art.

[0134] FIG. 10 illustrates an example of an application of this application. The processes performed by the system 100 is used to generate and recover device RSA key pairs using the device hardware unique key HUK as the seed value. This only requires to store 256-bit root key, instead of 2048-bit RSA key pairs. Root Key is typically stored in One Time Programmable (OTP) memory using eFuse technology. This kind of memory is typically very limited and expensive, therefore it is not reasonable to store directly large data such as RSA key into OTP memory. In other words, system 100 is used instead of storing 2048-bit RSA key pairs. Further, as the processes performed by the system 100 is software implemented, older version of devices which only have symmetric device key can also benefit from this as it is only required to upgrade the software of the devices.

[0135] It is also possible to obtain unique RSA key pair by replacing RK with the following function, f(RK, seed), where f is one-way key derivation function (KDF). For example f is KDF1-SHA256. This allows us to support derivation of multiple keys.

[0136] Beneficially, prime generation needs to be done only once and later, much faster recovery is needed. Since the system 100 uses PRNG 134, the two prime numbers are be reproduced.

[0137] The system 100 is also applicable in resource constrained devices such as sensors and other IoT devices, because they can use pre-computed offset values for prime recovery.

[0138] The above is a description of embodiments of a method and system of implementing a deterministic derivation function to obtain two large prime numbers in order to generate a pair of keys. It is foreseeable that those skilled in the art can and will design alternative method and system based on this application that infringe upon this invention as set forth in the following claims.