Circuit arrangement and method for RSA key generation

• US 8,265,265 B2
• Filed: 08/09/2006
• Issued: 09/11/2012
• Est. Priority Date: 08/19/2005
• Status: Active Grant

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: NXP B.V. (NXP Semiconductors NV)
• Inventors: Van Rijnswou, Sander Matthijs
• Primary Examiner(s): Gergiso, Techane
• Application Number:
  US12/063,865
• Publication Number:
  US 20090185681A1
• Time in Patent Office: 2,225 Days
• Field of Search: 380/28, 380/44
• US Class Current: 380/28
• CPC Class Codes: G06F 2207/7204 Prime number generation or prime number testing
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

In order to further develop a circuit arrangement for as well as a method of performing at least one operation, in particular at least one cryptographic calculation, wherein the problem of creating at least one key, in particular the R[ivest-]S[hamir-]A[dleman] key, satisfying at least one defined digital signature laws, in particular satisfying the German Digital Signature Law, is solved it is proposed that at least one, preferably two, prime numbers (p; q) for key generation, in particular for R[ivest-]S[hamir-]A[dleman] key generation, are searched in compliance with at least one defined digital signature law, in particular with the German Digital Signature Law.

Claims

1. A hardware implementation of a data processing device, the data processing device comprising at least one integrated circuit (IC), wherein the at least one IC has start bytes of random numbers offline pre-computed from a table of bytes to satisfy requirements of a defined digital signature law, uses the pre-computed start bytes in a key generating stage to start the random numbers, and searches two prime numbers for key generation both in compliance with the defined digital signature law and based upon the started random numbers.

2. The data processing device of claim 1, wherein the data processing device is an embedded system.

3. The data processing device of claim 1, wherein the at least one IC carries out a cryptographic calculation.

4. A method of performing, on a hardware implementation of a data processing device, at least one cryptographic calculation, the method comprising:

searching, on the hardware implementation of a data processing device, two prime numbers for key generation in compliance with at least one defined digital signature law;

pre-computing start bytes for random numbers offline from a table of bytes to satisfy all requirements of the defined digital signature law; and

using, in a key generating stage, the pre-computed start bytes to start the random numbers used in searching for the two prime numbers.

5. The method according to claim 4, wherein the two prime numbers (p;

q) are subject to the following condition;

2<sup>2n−

1</sup><

p*q<

2²ⁿ,

wherein p*q is a modulus having a required bit length 2*n.

6. The method of claim 4, wherein both prime numbers are of length n.

7. The method of claim 4, further comprising:

determining which prime number of the two prime numbers is smaller; and

applying a label to the smaller prime number.

8. A method of performing, on a hardware implementation of a data processing device, at least one cryptographic calculation, the method comprising:

searching, on the hardware implementation of a data processing device, two prime numbers for key generation in compliance with at least one defined digital signature law;

pre-computing all start bytes for random numbers to satisfy all requirements of the defined digital signature law; and

using, in a key generating stage, the pre-computed start bytes to start the random numbers used in searching for the two prime numbers, wherein the two prime numbers (p;

q) to be produced are subject to the following conditions;

2<sup>2n−

1</sup><

p*q<

2²ⁿ;

 

 

(i)

0.5<

|log(p)−

log(q)|<

30;

 

 

(ii)

p<

q; and

 

 

(iii)

p<

2ⁿ and q<

2ⁿ, 

 

(iv)

wherein p*q is a modulus having a required bit length 2*n and each prime number has a bit length n.