CIRCUIT ARRANGEMENT AND METHOD FOR RSA KEY GENERATION

• US 20090185681A1
• Filed: 08/09/2006
• Published: 07/23/2009
• 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
• Granted Patent: US 8,265,265 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• 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 circuit arrangement, in particular an integrated circuit, such as a mathematical coprocessor, for performing at least one operation, in particular at least one cryptographic calculation,

characterized in

that at least one, preferably two, prime numbers 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.

2. The circuit arrangement according to claim 1, characterized in that

that the possible start bytes for the random numbers being the basis for the prime numbers are offline pre-computed such that all requirements of the defined digital signature law, in particular all requirements of the German Digital Signature Law, are satisfied;

and

that in the key generating stage, in particular in the R[ivest-]S[hamir-]A[dleman] key generating stage, these pre-computed values are used to start the random numbers used in the searching for the prime numbers.

3. A microcontroller, in particular an embedded security controller, comprising at least one circuit arrangement, in particular at least one integrated circuit, such as at least one mathematical coprocessor, according to claim 1.

4. A data processing device, in particular an embedded system, for example a chip card or a smart card, comprising at least one circuit arrangement, in particular at least one integrated circuit, such as at least one mathematical coprocessor, according to claim 1, the circuit arrangement carrying out the operation, in particular the cryptographic calculation.

10. Use of at least one circuit arrangement, in particular of at least one integrated circuit, such as of at least one mathematical coprocessor, according to claim 1 in at least one data processing device, in particular in at least one embedded system, for example in at least one chip card or a smart card, according to claim 4 in the field of public key cryptography, such as banking, online shopping, security, etc.

5. A method of performing at least one operation, in particular at least one cryptographic calculation,

characterized in

that at least one, preferably two, prime numbers 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.

6. The method arrangement according to claim 5, characterized in that

that the possible start bytes for the random numbers being the basis for the prime numbers are offline pre-computed such that all requirements of the defined digital signature law, in particular all requirements of the German Digital Signature Law, are satisfied;

and

that in the key generating stage, in particular in the R[ivest-]S[hamir-]A[dleman] key generating stage, these pre-computed values are used to start the random numbers used in the searching for the prime numbers.

7. The method according to claim 5, characterized in that the prime numbers (p;

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

2^2n-1<

p*q<

2²ⁿ;

 

 

(i)

0.5<

| log(p)−

log(q)|<

30;

 

 

(ii)

p<

q; and

 

 

(iii)

p<

2ⁿ and q<

2ⁿ;

 

 

(iv)

with the number 2*n representing the required bit length of the modulus, in particular of p*q.

8. A computer program product directly loadable into the memory of at least one computer, comprising at least one software code portion for performing the method according to claim 5 when said computer program product is run on the computer.

9. Electronic distribution of at least one computer program product according to claim 8.