CIRCUIT ARRANGEMENT AND METHOD FOR RSA KEY GENERATION

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
2Forward
Citations 
0
Petitions 
10
Assignments
First Claim
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 inthat 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.
10 Assignments
0 Petitions
Accused Products
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.
22 Citations
View as Search Results
METHOD FOR ONBOARD PRIME NUMBER GENERATION  
Patent #
US 20170346632A1
Filed 11/25/2015

Current Assignee
Thales DIS France SA

Sponsoring Entity
Thales DIS France SA

Method for onboard prime number generation  
Patent #
US 10,447,477 B2
Filed 11/25/2015

Current Assignee
Thales DIS France SA

Sponsoring Entity
Thales DIS France SA

Security module and method for production of forgeproof documents  
Patent #
US 7,386,728 B1
Filed 10/05/2000

Current Assignee
Deutsche Post AG

Sponsoring Entity
Deutsche Post AG

Method and apparatus for calculating a multiplicative inverse of an element of a prime field  
Patent #
US 7,191,333 B1
Filed 10/25/2001

Current Assignee
Cisco Technology Incorporated

Sponsoring Entity
Cisco Technology Incorporated

Caller identification system with encryption  
Patent #
US 5,289,542 A
Filed 03/04/1991

Current Assignee
American Telephone Telegraph

Sponsoring Entity
American Telephone Telegraph

Stream cipher operation using public key cryptosystem  
Patent #
US 4,471,164 A
Filed 10/13/1981

Current Assignee
Bell Telephone Laboratories Inc.

Sponsoring Entity
Bell Telephone Laboratories Inc.

Device for digital signature of an electronic document  
Patent #
US 20050039018A1
Filed 01/16/2004

Current Assignee
Brainshield Technologies Incorporated

Sponsoring Entity
Brainshield Technologies Incorporated

Polynomial time deterministic method for testing primality of numbers  
Patent #
US 20050027764A1
Filed 07/31/2003

Current Assignee
Indian Institute of Technology Kharagpur

Sponsoring Entity
Indian Institute of Technology Kharagpur

Remote authorization for unlocking electronic data system and method  
Patent #
US 20040030903A1
Filed 03/31/2003

Current Assignee
Greater Boston Authentication Solutions LLC

Sponsoring Entity
Peter Janssen Creath, Christian Bielefeldt Hicks

Method for generating a random prime number within a predetermined interval  
Patent #
US 20040049526A1
Filed 09/09/2002

Current Assignee
Gemalto SA

Sponsoring Entity
Gemplus Corporation

Selecting cached RSA keys in response to RSA key requests  
Patent #
US 20040156506A1
Filed 02/10/2003

Current Assignee
Micro Focus LLC

Sponsoring Entity
HewlettPackard Development Company L.P.

Secure method for performing a modular exponentiation operation  
Patent #
US 20040184604A1
Filed 04/30/2004

Current Assignee
Gemplus Corporation

Sponsoring Entity
Gemplus Corporation

Leakresistant cryptographic payment smartcard  
Patent #
US 20030028771A1
Filed 04/29/2002

Current Assignee
Cryptography ResearchInc.

Sponsoring Entity
Cryptography ResearchInc.

Information processing device, information processing method and smartcard  
Patent #
US 6,666,381 B1
Filed 03/16/2001

Current Assignee
Hitachi America Limited

Sponsoring Entity
Hitachi America Limited

Computerimplemented method for fast generation and testing of probable prime numbers for cryptographic applications  
Patent #
US 20030235299A1
Filed 06/21/2002

Current Assignee
Rambus Inc.

Sponsoring Entity
Atmel Corporation

Methods and apparatus for verifying the cryptographic security of a selected private and public key pair without knowing the private key  
Patent #
US 6,411,715 B1
Filed 11/10/1998

Current Assignee
EMC Corporation

Sponsoring Entity
RSA Security LLC

OSS signature scheme  
Patent #
US 20020188846A1
Filed 02/01/2002

Current Assignee
Cisco Technology Incorporated

Sponsoring Entity
Cisco Technology Incorporated

Prime number generation apparatus Bsmoothness judgement apparatus and computer memory product  
Patent #
US 6,330,332 B1
Filed 03/10/1998

Current Assignee
Fujitsu Limited

Sponsoring Entity
Fujitsu Limited

Method of cryptography with public key based on the discrete logarithm  
Patent #
US 5,946,397 A
Filed 09/24/1997

Current Assignee
Gemalto SA

Sponsoring Entity
Gemplus Corporation

Method and apparatus for protecting public key schemes from timing and fault attacks  
Patent #
US 5,991,415 A
Filed 05/12/1997

Current Assignee
Yeda Research and Development Co. Ltd.

Sponsoring Entity
Yeda Research and Development Co. Ltd.

Method and apparatus for enhancing software security and distributing software  
Patent #
US 5,724,425 A
Filed 06/10/1994

Current Assignee
Sun Microsystems Incorporated

Sponsoring Entity
Sun Microsystems Incorporated

Public key authentication and key agreement for lowcost terminals  
Patent #
US 5,406,628 A
Filed 08/02/1993

Current Assignee
TTI Inventions C LLC

Sponsoring Entity
Bell Communications Research Inc.

10 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.
 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.
1 Specification
The present invention relates to a circuit arrangement, in particular to an integrated circuit, such as to a mathematical coprocessor, for performing at least one operation, in particular at least one cryptographic calculation.
The present invention further relates to a method of performing at least one operation, in particular at least one cryptographic calculation.
In cryptography, the currently most used public key system is R[ivest]S[hamir] A[dleman]. This is a system allowing to sign with a secret private key but this signature can be verified by anyone in possession of the nonsecret public key. The RSA system or RSA algorithm requires specially constructed keys to work; in particular, two large prime numbers are required, the product of which is the socalled mod[ulus].
In some countries, laws have been passed giving the digital signature a similar legal status as ordinary signatures; for example, in Germany the “German Digital Signature Law” has been passed giving the digital signature a similar legal status as ordinary signatures. For security reasons, such laws pose a number of requirements on the keys being used, such as with respect to the key length. But also the following more technical requirement is given:
The prime factors or prime numbers p, q of n should have the same order of magnitude but should not be too close together:
ε_{1}< log_{2}(p)−log_{1}(q)<ε_{2}.
Proposed here as a guide for ε_{1 }and ε_{2 }are ε_{1}≈0.5 and ε_{2}≈30.
The prime factors p and q have to be generated randomly and independently of one another, observing the given constraints (cf. http://regtp.de/imperia/md/content/tech reg t/digsign/141.pdf).
Having a system working in accordance with the German Digital Signature Law is a business necessity, in fact not only for the German market but increasingly for the European and worldwide market.
Generating prime numbers for R[ivest]S[hamir]A[dleman] works by generating a random number of sufficient length and then applying the operator “NextPrime” to it. To this approach, there was already known a small improvement, namely to insure that the product of the two primes so produced are precisely of a certain length thus allowing to modify the first few bits of the random numbers.
However, it is a problem to generate primes satisfying the above requirement of the German Digital Signature Law. One approach having been used elsewhere is to produce these random numbers, check if they satisfy the requirement and, if not, produce new random numbers. This can be continued until the produced random number would satisfy all conditions.
Obviously this approach has numerous problems. First of all, it is unclear how long it takes to get good random numbers by chance. Secondly, many random numbers are required (which is a scarce resource in some environments, such as smart cards or certain types of servers). Thirdly, complex software is required to do the necessary computations (which is undesirable for several reasons).
Prior art document US 2004/0049526 A1 refers to a method for generating a random prime number within a predetermined interval; a single value being used to generate prime numbers is precalculated and stored.
Prior art article “Offline/Online Generation of RSA Keys with Smart Cards” by Nathalie Feyt, Marc Joye, David Naccache, and Pascal Paillier, Second International Workshop for Asian Public Key Infrastructures, Taipei, Taiwan, Oct. 30, 2002, to Nov. 1, 2002, discloses a division of the RSA key generation into two phases.
The first phase is performed offline, before the input parameters are even known; the second phase is performed online by the smart card once the input parameters are known, and is meant to be very fast.
By this known technique, an online generation of RSA keys of arbitrary length is achieved from a small set of seeds computed during the offline phase. Thus, a mixed offboard/onboard solution is presented where the variable and timeconsuming part is performed offline by producing small seeds being used in the second, fast, online part of the generation of the keys themselves.
Another solution according to this prior art article consists in precomputing values for the primes p, q for various pairs and to store those values in an E[lectrically]E[rasable] P[rogrammable]R[ead] O[nly]M[emory]like, non volatile memory.
A very natural yet cumbersome solution according to this prior art article consists in precomputing and writing in the card'"'"'s nonvolatile memory a set of integer values such that for each i a P[seudo]R[andom]N[umber]G[enerator] yields a prime number.
Regarding the technological background of the present invention, reference can be made to prior art document U.S. Pat. No. 5,946,397 revealing a method of cryptography with public key based on the discrete logarithm; a database of random values is formed and these random values are combined to determine exponents for keys.
Prior art document US 2004/0156506 A1 relates to selecting cached RSA keys in response to RSA key requests.
Regarding the technological background of the present invention, further reference can be made to prior art article “Implementation of Fast RSA Key Generation on Smart Cards” by Chenghuai Lu, Andre L. M. dos Santos, and Francisco R. Pimentel, Proceedings of the 2002 ACM symposium on Applied computing, Madrid, Spain.
Starting from the disadvantages and shortcomings as described above, in particular starting from the requirements of certain digital signature laws, such as from the requirements of the German Digital Signature Law, and taking the prior art as discussed into account, an object of the present invention is to further develop a circuit arrangement of the kind as described in the technical field as well as a method of the kind as described in the technical field in order to enable the solution of the problem of creating at least one key, in particular the R[ivest]S[hamir]A[dleman] key, satisfying these digital signature laws, in particular satisfying the German Digital Signature Law.
The object of the present invention is achieved by a circuit arrangement comprising the features of claim 1 as well as by a method comprising the features of claim 5. Advantageous embodiments and expedient improvements of the present invention are disclosed in the respective dependent claims.
The present invention is principally based on the idea of accelerating the key generation, in particular for creating R[ivest]S[hamir]A[dleman] keys satisfying the German Digital Signature Law, in a much better way than previous methods, i.e. faster, less complex and also introducing very little bias.
According to the teaching of the present invention, the following algorithm for the prime searching process for key generation can be implemented:
 offline, all possible start bytes for the random numbers being the basis for the primes are computed such that they satisfy all requirements of the respective digital signature law, for example all requirements of the German Digital Signature Law;
 in the R[ivest]S[hamir]A[dleman] key generating stage, these precomputed values are used to start the random numbers used in the prime searching process.
The present invention further relates to a data processing device, in particular to an embedded system, for example to a chip card or to a smart card, comprising at least one circuit arrangement, in particular at least one integrated circuit, such as at least one mathematical coprocessor, carrying out the calculations, in particular the cryptographic calculations, of the abovedescribed type.
The present invention further relates to 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 of the abovedescribed type when said computer program product is run on the computer.
The present invention further relates to the electronic distribution of at least one computer program product of the abovedescribed type.
The present invention finally relates to the use of at least one circuit arrangement, in particular of at least one integrated circuit, such as of at least one mathematical coprocessor, of the abovedescribed type and/or of the method of the abovedescribed type 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, of the abovedescribed type in the field of public key cryptography, such as banking, online shopping, security, etc.
Correspondingly, the present invention can be used in any field where public key cryptography is used, such as banking, online shopping, security, etc. The light weight of the algorithm makes it especially suited to restricted environments, such as chip cards or smart cards.
As already discussed above, there are several options to embody as well as to improve the teaching of the present invention in an advantageous manner. To this aim, reference is made to the claims respectively dependent on claim 1 and on claim 5; further improvements, features and advantages of the present invention are explained below in more detail with reference to a preferred embodiment by way of example and to the accompanying drawings where
The embodiment of a data processing device 100, namely an embedded system in the form of a chip card or of a smart card comprising an I[ntegrated]C[ircuit] carrying out calculations, namely cryptographic operations, refers to a P[ublic]K[ey]I[nfrastructure] system and works according to the method of the present invention.
In this context, a system to produce prime numbers p, q needed for R[ivest]S[hamir] A[dleman] keys satisfying certain digital signature laws, for example the German Digital Signature Law, is described. Moreover, this system does not require additional random numbers, is very fast, and needs only a quite simple program algorithm.
The essential idea of the present invention is to use a precomputed table of bytes with which the random numbers can be safely started; these started random numbers can start the prime searching process.
By this way of proceeding, the present invention overcomes the problems which were introduced when particular digital signature laws, especially the German Digital Signature Law, imposed detailed restrictions on RSA keys. As shown in the chapter “Background and prior art” above, previous methods were burdensome and unsuitable for restricted environments, such as smart cards.
Using the present invention, RSA key generation is again possible wherein the algorithm works as follows:
Offline, all possible bytes are computed with which the random numbers can be started that are the basis for the primes, and still guarantee that these primes satisfy all the requirements.
Next, when generating RSA keys, these precomputed values are used to start the random numbers with. Below an in depth description is given, where
 first the precise conditions to be satisfied (including those of the German Digital Signature Law) are given,
 next it is gone into a discussion on what these conditions lead to, and
 finally, the algorithm as it can be implemented is given.
For generating RSA keys, primes p and q are to be produced, these primes p and q being subject to the following conditions to be satisfied (including those of the German Digital Signature Law):
2^{2n1}<p*q<2^{2n;} (i)
0.5< log(p)−log(q)<30 (signature law condition); (ii)
p<q; (iii)
p<2^{n }and q<2^{n}. (iv)
In these four inequalities (i), (ii), (iii), (iv), the number 2*n presents the required bit length of the mod[ulus], that is p*q.
The first condition (i) expresses the fact that the mod[ulus] p*q is to be precisely of the required bit length.
The second condition (ii) is imposed by the German Digital Signature Law.
The third condition (iii) is for convenience.
The fourth condition (iv) is also for convenience and expresses the fact that also the individual primes are to be precisely of the bit length n. This is not strictly speaking necessary from requirements of the German Digital Signature Law but it makes handling these numbers easier.
Since one of the two primes p, q is going to end up smaller that prime is to be labeled (this makes use of the key in Chinese Remainder applications more easy).
Finally, also the condition can be added that no more biases in the choice of primes than necessary are imposed.
After having defined the precise conditions to be satisfied (including those of the German Digital Signature Law), next the question can be asked what restriction can be imposed upon the first byte of the prime numbers p and q such that the four conditions (i), (ii), (iii), (iv) listed above are automatically satisfied, for the whole of p and q.
Using the appropriate mathematics it turns out that the following list of condition is sufficient wherein the first byte of p and q is abbreviated with p_{—}8 and q_{—}8:
2^{15}<p_{—}8*q_{—}8; (a)
(p_{—}8+1)*2^{0.5}<=q_{—}8; (b)
2^{7}<p_{—}8<q_{—}8<2^{8}. (c)
When solving this system of equations (a), (b), (c), the result is a list of 1.040 solutions, i.e. of 1.040 pairs of bytes (p_{—}8, q_{—}8) which can potentially occur at the start of suitable prime numbers. Concerning these pairs of bytes (p_{—}8, q_{—}8), the following observation may be made:
there are only solutions with q_{—}8 in the range 217<=q_{—}8<=255;
given a q_{—}8 for which a solution exists, the highest p_{—}8 being valid is given by the floor of q_{—}8*(181/256)−1;
the following list of numbers represents the number of solutions p_{—}8 given q_{—}8 (starting at q_{—}8=217 and up to q_{—}8=255):
 1, 3, 4, 6, 7, 8, 10, 11, 13, 14, 15, 17, 17, 19, 21, 22, 23, 24, 26, 27, 28, 30, 30, 32, 34, 35, 36, 37, 39, 39, 41, 42, 44, 44, 46, 47, 48, 49, 51
From this, an algorithm can be straightforwardly designed:
This algorithm takes as input a random number R, and produces as output two bytes p_{—}8 and q_{—}8 which can be used as the first bytes of a string of random bytes, to which in turn the next prime operator can be applied.
Finally,
The smart card 100 comprises the following components:
 a microcontroller 10 for general control to communicate with the outside world via an interface 12, for example according to ISO78163 standard; the microcontroller 10 sets pointers for data in R[andom]A[ccess]M[emory]/R[ead]O[nly]M[emory] and starts the coprocessor 20;
 a R[ead]O[nly]M[emory] 30 for the program of the microcontroller 10;
 a P[rogrammable]R[ead]O[nly]M[emory] (flash memory or E[lectrically]E[rasable] P[rogrammable]R[ead] O[nly]M [emory]) 40 for the nonvolatile storage of data and/or of programs;
 a R[andom]A[ccess]M[emory] 50 for the volatile storage of data, for instance for the storage of intermediate results during calculations; and
 a coprocessor 20 dedicated to perform special highspeed tasks for E[lliptic]C[urve]C[ryptography] calculations, in particular for E[lliptic] C[urve]D [igital] S [ignature]A[lgorithm] calculations, or for R[ivest]S[hamir]A[dleman] calculations.
When a task is ready, control is returned to the microcontroller 10.
In a variant, the present invention is implemented in software with at least one microprocessor A[rithmetic]L[ogical]U[nit] to provide add operations, subtract operations, and/or shift operations with programming of the controller to provide control logic, and degree detection by shift registers.
The abovespecified algorithm as well as the abovespecified hardware implementation as well as the abovespecified software implementation can be used in the crypto library for the next generation eight bit smart card, the socalled SmartMX.
Fully compatible with the MIFARE PROX range, SmartMX meets the needs of highvolume, costsensitive, singleapplication and multiapplication markets, such as banking cards, S[ubscriber]I[dentity]M[odule] cards, pay T[ele]V[ision] subscription cards, ebusiness, egovernment and public transportation.
Offering Large
E[lectrically]E[rasable]P[rogrammable]R[ead]O[nly]M[emory] capacities (up to 72 K[ilo]B[ytes]) and high levels of security, the SmartMX dual/triple interface family members meet and exceed the specifications for smart passports (M[achine]R[eadable]T[ravel]D[ocuments]) set by the International Civil Aviation Organization (ICAO).
SmartMX card I[ntegrated]C[ircuit]s feature exception sensors for voltage, frequency, temperature and light. In conjunction with handshake solutions'"'"' design methodology, this makes the entire family extremely resistant to any kind of physical analysis.
A hardware memory management unit (firewall) provides additional protection for P[ublic]K[ey]I[nfrastructure] controllers. The SmartMX family has been evaluated to ensure the highest security standards and includes the first I[ntegrated]C[ircuit]s for smart passports which have achieved C[ommon]C[riteria] E[valuation]A[ssurance] L[evel]5+[augmented] certification.
SmartMX is the most advanced solution available in its targeted segment, combining exceptionally powerful coprocessors for P[ublic]K[ey]I[nfrastructure] and secret key encryption to support R[ivest]S[hamir]A[dleman], E[lliptic] C[urve]C [ryptography], D [ata]E[ncryption] S [tandard], and A[dvanced]E[ncryption]S[tandard], with the highsecurity, lowpower, performanceoptimized design concept of handshake solutions technology.
SmartMX enables troublefree implementations of operating systems and open platform solutions including Java Open Platform and MULT[iapplicationcard]O[perating [S]ystem (=smart card operating system aimed at operating multiple applications off a single chip card), while offering an optimized feature set and the highest security.
SmartMX microcontrollers can be manufactured using advanced 0.18 micrometer, five metal layer C[omplementary]M[etal]O[xide]S[emiconductor] process technology and support class “C”, class “B” and class “A” voltage ranges (1.8 Volt to five Volt), as required by application standards such as 3[rd]G[eneration]P[artnership]P[roject] for 3[rd]G[eneration] mobile communications and the E[uropay]M[asterCard]V[is a] credit card/debit card standard.
SmartMX is based on a proven secure C51compatible architecture offering a wide choice of interface options (I[ntemational] S [tandardization] O[rganization] 7816, I[nternational] S [tandardization]O[rganization] 14443 and U[niversal]S [erial]B [us] 2.0) and is available with cryptographic coprocessors for 3D[ata]E[ncryption]S[tandard] algorithms and optional A[dvanced]E[ncryption]S[tandard] algorithms and a crypto accelerator called FrameXE for P[ublic]K[ey]I[nfrastructure] algorithms.

 100 data processing device, in particular embedded system, for example chip card or smart card
 10 microcontroller unit
 12 interface unit of microcontroller unit 12
 20 coprocessor unit
 30 R[ead]O[nly]M[emory] unit
 40 P[rogrammable]R[ead]O[nly]M[emory], in particular flash memory or E[lectrically]E[rasable]P[rogrammable]R[ead] O[nly]M[emory]
 50 R[andom]A[ccess]M[emory]