WO2004099953A2

WO2004099953A2 - Generation of cryptographic keys

Info

Publication number: WO2004099953A2
Application number: PCT/IB2004/050566
Authority: WO
Inventors: Henrik Przybilla
Original assignee: Philips Intellectual Property and Standards GmbH; Koninklijke Philips Electronics NV
Current assignee: Philips Intellectual Property and Standards GmbH; Koninklijke Philips NV
Priority date: 2003-05-09
Filing date: 2004-05-03
Publication date: 2004-11-18
Anticipated expiration: 2005-11-09
Also published as: WO2004099953A3

Abstract

For a secure communication between a remote unit and a central unit, keys of a corresponding key set are necessary in the remote unit and the central unit. According to the present invention, information with respect to how the remote unit generates a key for the corresponding key set is stored in the central unit. The keys of the corresponding key set are independently generated in the remote unit and the central unit. Advantageously, this allows for a secure communication while reducing the required memory in the remote unit.

Description

Generation of cryptographic keys

The present invention relates to cryptographic systems and to the generation of cryptographic keys. In particular, the present invention relates to the field where cryptographic key sets are used for the secured access or control or maintenance of units that operate remotely with respect to a central unit. In detail, the present invention relates to a method of generating corresponding keys of a cryptographic key set for a central unit and a remote unit, to a remote unit for association with a central unit, to a system for generating corresponding keys of a cryptographic key set and to a computer program for a system for generating corresponding keys of a cryptographic key set.

In systems where cryptographic key sets are used for the secured access, control or maintenance of units that operate remotely with respect to a central unit, the problem frequently arises how to exchange or install the cryptographic keys in the remote unit, such as a multi-application smart card, a mobile telecommunication device such as a PDA or a mobile phone, or, for example, a car. At present, two schemes are known for the distribution of these cryptographic keys: 1) Exchange/installation of cryptographic key sets during installation.

Here, during initialization, the keys of the key set can be securely installed in a unit that will operate remotely afterwards, because at the time of initialization, all related functional units are located within one protected domain.

2) Exchange/installation of cryptographic key sets during lifetime by a network transaction transmitting the secret cryptographic keys: for this scheme, a previously installed master key set is necessary. The keys that to be installed on the remote units are encrypted with one cryptographic key of the master key set, transferred to the remote unit over a network such as a radio network, then decrypted with the other key of the master key set and subsequently installed on the remote unit. In scheme 1), where the cryptographic key sets which may be used during the lifetime of the remote unit are installed during initialization, it is necessary to fix a final collection of key sets in the remote unit, which requires an extended memory in the remote unit. Furthermore, after the remote unit has left the protected domain, no further changes can be made to the cryptographic keys stored in the remote unit.

In scheme 2), where the cryptographic key sets are transmitted via a network, the secret keys are in danger of being observed, stolen or copied during their transmission via the network. In order to prevent this, security measures have to be taken, like e.g. the encryption of the transmitted key by an additional, pre-defined key set.

It is an object of the present invention to provide an improved and secure generation of a cryptographic key for the communication with a remote unit.

According to an exemplary embodiment of the present invention as set forth in claim 1, a method of generating corresponding keys of a first cryptographic key set for a central unit and a remote unit is provided where a first cryptographic key is generated in the central unit on the basis of a first information set. A second cryptographic key is generated in the remote unit on the basis of a second information set. The first cryptographic key and the second cryptographic key form the corresponding keys of the first cryptographic key set. According to an aspect of the present invention, the first and second cryptographic keys are generated independently from each other.

In other words, according to this exemplary embodiment of the present invention, the first and second cryptographic keys can be generated independently of each other on the basis of the first and second information sets and can thereby for example be generated on demand, which allows to significantly reduce memory space required in the remote unit. The first cryptographic key for accessing the remote unit can be generated independently in the central unit without the transmission of any secrets via a network. Also, no back channel from a remote unit to, for example, the central unit is required for the generation of the cryptographic key set. For this reason, this exemplary embodiment of the present invention, may be suitable for unidirectional data links, such as broadcast systems.

According to another exemplary embodiment of the present invention as set forth in claim 2, the generation of the second cryptographic key in the remote unit can be triggered by, for example, a dedicated message sent from the central unit to one remote unit, a multicast or broadcast message sent from the central unit to a plurality of remote units, the arrival of data representing an operation that requires a new key set or the application of a cryptographic key that belongs to a previously generated key set to the remote unit or the central unit. According to an aspect of the present invention, the event triggering the generation of the first respectively the second cryptographic key in the central unit respectively the remote unit may be the same. However, it is also possible that the generation of the first cryptographic key in the central unit is triggered by an event other than the generation of the second cryptographic key in the remote unit.

In particular, due to the generation of the keys on demand, memory space can be saved in the remote unit. Especially for systems that use algorithms such as, for instance, the public key encryption and signature scheme described by Rivest, Shamir and Adleman (RSA), it is possible to significantly reduce the memory space in the remote unit.

Furthermore, according to this exemplary embodiment of the present invention, it is possible to initiate the installation of different cryptographic keys in an arbitrary number of remote units at once with one multicast or broadcast message which allows the generation of new keys with only the transmission of one message to all or selected remote units.

According to another exemplary embodiment of the present invention as set forth in claim 3, the first and second cryptographic keys are generated such that a calculation of the first and second information sets is not possible on the basis of the first and second cryptographic keys and such that no further cryptographic keys can be derived from the first and second cryptographic keys. Advantageously, this provides for a secure generation of the keys. According to an aspect of the present invention, this can, for example, be attained by mathematical one-way algorithms like the ones already used for example in public key cryptography such as the one described in US 4,405,829, which is hereby incorporated by reference.

According to another exemplary embodiment of the present invention as set forth in claim 4, a remote unit is provided for association with a central unit. The remote unit comprises a memory and calculating means for generating a second cryptographic key on the basis of a second information set independently from a generation of a first cryptographic key on the basis of the first information set in the central unit.

Due to the capability of independently generating new keys in the remote unit, a memory space required in the remote unit can be reduced which allows for the reduction of the overall costs of the remote unit.

Claims 5 and 6 provide further advantageous exemplary embodiments of the remote unit according to the present invention.

According to the exemplary embodiment of the remote unit set forth in claim 7, the remote unit is a smart card, such as a credit card, including a chip. However, the remote unit may also be a mobile communications device such as a mobile phone, a PDA, a notebook computer or even a part of a car. According to another exemplary embodiment of the present invention as set forth in claim 8, a system for generating corresponding keys of a first cryptographic key set is provided comprising a remote unit and a central unit. The remote unit is adapted to generate a second cryptographic key on the basis of a second information set independently from the generation of the first cryptographic key in the central unit. According to an aspect of this exemplary embodiment of the present invention, the central unit is capable of generating a key of the cryptographic key set for accessing the remote unit.

Claims 9 and 10 provide further exemplary embodiments of the system for generating corresponding keys of a cryptographic key set according to the present invention.

The present invention also relates to a computer program for a system for generating corresponding keys of a cryptographic key set. The computer program according to the present invention is set forth in claim 11. The computer program according to this exemplary embodiment of the present invention is preferably loaded into a working memory of processors in the remote unit and the central unit. The processors in the remote unit and the central unit are thus equipped to carry out the methods of the invention. The computer program may be stored on a computer- readable medium, such as a CD-ROM. The computer program may also be presented over a network, such as the World Wide Web and can be downloaded into the working memory of a processor from such a network.

It may be seen as a gist of an exemplary embodiment of the present invention that the first and second keys of the cryptographic key set are generated independently from each other in the central unit and the remote unit. If the remote unit needs to be accessed, the central unit generates a first cryptographic key for accessing the remote unit on the basis of the first information set, i.e. on the basis of the knowledge about the algorithms the remote unit uses to generate its keys. This key generated at the central unit may then be used for example by a service provider to access the remote unit which, for example, on demand generates a corresponding key such that a corresponding key set is provided for the communication between the service provider or the central unit and the remote unit.

These and other aspects of the present invention are apparent from and will be elucidated with reference to the embodiments described hereinafter and with reference to the following drawings:

Figure 1 shows a schematic representation of a system for generating corresponding keys of a cryptographic key set according to the present invention including a remote unit according to an exemplary embodiment of the present invention.

Figures 2a and 2b show a simplified flow chart of an exemplary embodiment of a method of operating the system of Figure 1.

Figure 1 shows an exemplary embodiment of a system for generating corresponding keys of a cryptographic key set according to the present invention.

The system according to the present invention will be described below with reference to a remote unit which is a smart card. However, it has to be noted that the present invention is not limited to the application with smart cards, but can also be applied to, for example, mobile phones, PDAs, mobile computers or cars. In the system depicted in Figure 1, reference numeral 2 designates a central unit. The central unit 2 in this case may be a computer including a processor 8 and a memory 10.

Reference numeral 4 designates a remote unit 4 such as a smart card including a processor 12 and a memory 14.

Reference numeral 6 designates a service provider which is for example a customer of the manufacturer of the smart card.

Arrows 16, 18 and 20 designate connections between the service provider 6, the central unit 2 and the remote unit 4, which may be physical connections, connections established via radio networks, such as mobile telecommunication networks, or data networks. In addition, the connections 16 and 18 may be formed by the handover of physical data storage units, such as optical storage disks. The transmissions or transactions carried out via the connections indicated by arrows 16, 18 and 20 may be bi-directional or uni-directional. A possible operation of the system depicted in Figure 1 is as follows:

The operator of the Central Unit issues the remote unit 4, i.e. the smart card, which may for example be a credit card, to an individual customer. Each smart card has its own identification number ID. The central unit 2 of the manufacturers knows for every smart card how to generate a key of the cryptographic key set for the communication with the smart card . Thus, the memory 10 of the central unit 2 includes for each smart card which was issued the ID number of the smart card and the respective algorithm to generate the key of the cryptographic key set for communication with the smart card 4. This algorithm may also be a data object or information set.

In case a service provider 6 wants to communicate with the smart card, for example in order to install an application that facilitates a transaction that is specific to the service provider 6, the service provider 6 sends a request for a key via the connection 16 to the central unit 2 of the manufacturer. This request includes the ID number of the smart card concerned. Then, the processor 8 of the central unit 2 of the manufacturer generates a corresponding key for the smart card 4 concerned on the basis of the data object/information set/algorithm stored in the memory 10 for this ID number. Then, this key is transmitted to the service provider 6 via the connection 16 which may then access the smart card via the network 20. The smart card generates another key on the basis of the data object/data set/algorithm stored in the memory 14 by means of the processor 12. Two keys have now been generated independently of each other which allow for a secure communication between the service provider 6 and the smart card (i.e. remote unit 4). An exemplary embodiment of a method of operating the system depicted in Figure 1 will now be described below with reference to Figures 2a and 2b.

After the start in step SI, the remote unit 4, i.e. the smart card, and the central unit 2 are configured in steps S2-S7. For configuring the remote unit 4 and the central unit 2, the remote unit 4 is configured with data object 2. Here, the identifier ID of the remote unit 4 is written into the memory 14 and the data object 1/data set/algorithm is set according to which/on the basis of which the keys of the key set for communicating with the remote unit 4 are generated. Then, the error-free operation of the remote unit 4 is ensured by testing the remote unit 4. This can for example be done by generating a test key. Then, the method continues to step S4, where a query is made whether the remote unit 4 operates error-free and the test was passed. In case it is decided in step S4 that the test was not passed, i.e. the remote unit 4 does not operate error-free, the method continues to step S5, where it ends.

In case it is determined in step S4 that the remote unit 4 passed the test and is working error-free, the method continues to step S6, where the memory 10 of the central unit is updated with a data object 1. This data object 1 includes the ID of the remote unit 4 and includes the data object 2 and/or a data set and/or an algorithm on the basis of which the remote unit 4 generates the key. In other words, the central unit 2 stores in the memory 10 the ID of the remote unit and the way the remote unit 4 generates the key. Thus, the central unit 2 is capable of generating a key corresponding to the key generated by the remote unit 4 to form a corresponding cryptographic key set for communication to and from the remote unit 4.

The method then continues to step S7, where the remote unit 4 is handed out to a customer. In case of the example of Figure 1 , this remote unit may be handed out to a service provider 6, such as a credit card company, which in turn distributes the remote unit, which may be a credit card, to its customers. Then, the method continues to step S8. In steps S8-S12, it is determined how access rights to the remote unit 4 are distributed. As can be taken from Figure 2a, this can be done on demand or on en bloc. In detail, in step S9, a query is made with respect to whether the access rights, i.e. the keys or the key for accessing the remote units, are sold en bloc or individually. In case it is determined in step S9 that the keys are sold en bloc, the method continues to step S10, where access rights to more than one remote unit in the form of first cryptographic keys are generated. In step S 11 the first cryptographic keys are sold and transferred to these service providers 6.

After step SI 1, as indicated by the encircled 1 at the bottom of Figure 2a and the encircled 1 at the top of Figure 2b, the method continues to step SI 5. In case it is determined in step S9 that the keys are sold/distributed/transferred individually, the method continues to step S12, where the central unit 2 waits for a request from a service provider 6 for a key. In case the central unit 2 receives a request for a key for accessing a remote unit 4 from a service provider 6, the respective key or access right is generated or retrieved in the central unit 2 in step S 13 and then sold and transferred to the service provider 6 in step S14. Then, as indicated by the encircled 1 at the bottom of Figure 2a and the encircled 1 at the top of Figure 2b, the method continues to step S15. In step SI 5, access is made from the service provider 6 to the remote unit 4, i.e. the service provider 6 attempts to install an application on the remote unit 4.

In step SI 6, a query is made in the processor 12 of the remote unit 4 whether there is aheady a spare key in the remote unit 4 or not. In case the remote unit 4 is of a kind that generates a spare key each time a transaction was completed, the method continues to step SI 7, where the service provider 6 issues a request for access, i.e. a request for installation of an application via the network 20 to the remote unit 4. Then, in the subsequent step SI 8, an access is carried out by using the spare key set, i.e. an application is installed on the remote unit 4 by using the spare key set. Then, the method continues to step S19 and S20, where in the remote unit 4 a new spare key is generated for a new spare key set. The method then continues to step S21, where it ends.

In case it was determined in step S16 that there are no spare keys, the method continues to step S22, where the generation of a new key set is initiated. In the subsequent step S23, a query is made whether a dedicated generation message is to be issued. This is the case when the system depicted in Figure 1 is configured such that new keys for the corresponding cryptographic key set are only generated on demand, i.e. when a corresponding message is received.

In case it is determined in step S23 that a dedicated generation message is to be sent, the service provider 6 sends a generation message in step S24 via the network 20 to the remote unit 4. In the subsequent step S25, a new key for a cryptographic key set is generated in the remote unit 4. In the following steps S26 and S27, by using the key generated by the central unit 2 and the key generated by the remote unit 4, an access can be made to the remote unit 4 S26 and an application can be installed by using this new key set S 27. The method then continues to step S21, where it ends.

It case it was determined in step S23 that no dedicated generation message is required, the method continues to step S28. In this case, the remote unit 4 is configured such that it starts the generation of a key when it receives an access request from the service provider 6 or the central unit 2. In step S28, the service provider 6 issues a request for installation to the remote unit 4 using the key generated by the central unit 2 in step S10 or step S12.

In the subsequent step S29, after receiving the request for installation from the service provider 6 at the remote unit, the remote unit 4 generates a new key. In the subsequent step S30, the remote unit 4 installs the application in the memory 14. Then, the method continues to step S21, where it ends.

Advantageously, the above operation allows to provide corresponding keys of cryptographic key sets to two independent remote functional units without the exchange of the cryptographic keys or other secrets. The cryptographic keys that are subject of the current invention are subsequently used in transactions with the remote unit 4, while the access rights that are associated with the key set can be restricted.

After the generation, a cryptographic key set can be sold or transferred independently of other access rights in order to entitle a service provider 6 a dedicated access to the remote unit 4. According to the present invention, a single or repeated secured access to the remote unit 4, such as smart cards, can be distributed or sold to the service provider. Advantageously, this may make the remote unit available for, for example, event promoters, cinemas or other kinds of service providers.

Advantageously, according to the present invention it is not necessary to fix at any time a final collection of keys in the remote unit 4. Furthermore, new keys can be installed without the transmission of secrets or confidential information, such as secret master keys via the connections 16, 18 and 20. Furthermore, since the generation of the key in the remote unit 4 may be carried out on demand, memory space can be saved in the remote unit 4. This may particularly be of concern in case algorithms, such as for example RSA are used for encryption. Furthermore, according to the present invention the central unit 2 and the remote unit 4 can be configured such that they always store exactly one "currently unused" - spare - cryptographic key available at one point (see steps S16-S20). This allows for more efficient use of the available memory and furthermore for a very fast access to the remote unit 4.

Furthermore, as already indicated above, the remote unit 4 and the central unit 2 can be configured such that the installation/generation of different cryptographic keys is initiated in an arbitrary number of units at once with one multicast or broadcast message. This advantageously allows to reduce the amount of transactions to be carried out in order to, for example, access a plurality of remote units 4.

Furthermore, according to the present invention, no back channel from the remote unit 4 to the service provider 6 or the central unit 2 is required. Thus, the present invention may also be applied to uni-directional data links such as broadcast systems. Advantageously, according to an aspect of the present invention, the generation of the keys of the key set is done with a scheme that guarantees that it is not possible to calculate, based on one or more keys of a key set, any of the following: a) one or more keys or other secret or private information of the data object 1 or the data object 2, b) one or more keys of a previously calculated key set, c) one or more keys of a future key set.

According to an aspect of the present invention, this may be assured by mathematical one way algorithms that are e.g. based on the integer factorizing problem. As mentioned above with respect to steps S2-S8, the remote unit 4 and the central unit 2 are initialized with an ID number of the remote unit 4 and an information set relating to the way the way in which the remote unit 4 generates a key. According to an aspect of the present invention, the remote unit 4 and the central unit 2 may also be provided with a counter for counting the number of key sets that have already been generated. This counter is set appropriately during initialization.

As mentioned above, during the lifetime of the remote unit 4, new key sets can be generated independently in the remote unit 4 and the central unit 2. The generation of the new key sets, as already indicated above, can be triggered for example by: a) a dedicated message sent from the central unit 2 to one remote unit 4, b) a multicast or broadcast message from the central unit 2 to a plurality of remote units 4, c) an arrival of data representing an operation such as an access operation which requires a new key set; the arriving data may for example already contain information that is encrypted with a key corresponding to the key that is subsequently generated by the remote units 4 such as described for example with reference to steps S28-S30; d) use of a cryptographic key belonging to a previously generated key set.

As indicated in step S13 and in the step S 10, new keys are generated in the central unit 2. The method used in the central unit 2 to generate a key corresponding to the key generated in the remote unit 4 may be based on the calculation of a seed value from the data object 1, data object 2, or information set or algorithm associated with the ID number of the respective remote unit 4. For example, the seed value may be calculated from a key of the Data Object 1 (which may be a key from a master key set) stored in the central unit 2. If the Data Object 1 is different from the Data Object 2, then the two methods of calculating the same seed value from the Data Objects are different in the remote unit and in the central unit, but the outcome of the calculation is the same seed value in the remote unit 4 and the central unit 2.

A calculation of a second key set in case the preceding key set was used is done in the same way, with the variation that a different seed value is calculated from the Data Objects. This can be achieved for instance by applying the algorithms that are used to calculate the seed value for the preceding key set, in this case twice for generating the seed value for the second key set.

Claims

CLAIMS:

1. Method of generating corresponding keys of a first cryptographic key set for a central unit and a remote unit, the method comprising the steps of: generating a first cryptographic key in the central unit on the basis of a first infoπnation set; generating a second cryptographic key in the remote unit on the basis of a second information set; wherein the first cryptographic key and the second cryptographic key form the corresponding keys of the first cryptographic key set; wherein the first and second cryptographic keys are generated independently from each other.

2. The method of claim 1 , wherein the generation of the second cryptographic key in the remote unit is triggered by at least one of the following events: a) a reception of a first message from the central unit at the remote unit, wherein the first message is a dedicated message from the central unit to the remote unit; b) a reception of a multicast message from the central unit at the remote unit, wherein the multicast message is a message sent from the central unit to a plurality of remote units; c) a reception of operation data at the remote unit, wherein the operation data represents an operation at the remote unit which requires the second cryptographic key; and d) an application of a third cryptographic key to the remote unit, wherein the third cryptographic key belongs to a second cryptographic key set which is older than the first cryptographic key set.

3. The method of claim 1, wherein the first and second cryptographic keys are generated such that a calculation of the first and second information sets is not possible on the basis of the first and second cryptographic keys and such that no further cryptographic keys can be derived from the first and second cryptographic keys.

4. Remote unit for association with a central unit, wherein a first cryptographic key is generated on the basis of a first information set in the central unit, comprising: a memory; and calculating means for generating a second cryptographic key on the basis of a second information set; wherein the first cryptographic key and the second cryptographic key form the corresponding keys of a first cryptographic key set; wherein the second cryptographic key is generated independently from the central unit.

5. The remote unit of claim 4, wherein the generation of the second cryptographic key in the remote unit is triggered by at least one of the following events: a) a reception of a first message from the central unit at the remote unit, wherein the first message is a dedicated message from the central unit to the remote unit; b) a reception of a multicast message from the central unit at the remote unit, wherein the multicast message is a message sent from the central unit to a plurality of remote units; c) a reception of operation data at the remote unit, wherein the operation data represents an operation at the remote unit which requires the second cryptographic key; and d) an application of a third cryptographic key to the remote unit, wherein the third cryptographic key belongs to a second cryptographic key set which is older than the first cryptographic key set.

6. The remote unit of claim 4, wherein the second cryptographic key is generated such that a calculation of the first and second information sets is not possible on the basis of the first and second cryptographic keys and such that no further cryptographic keys can be derived from the first and second cryptographic keys.

7. The remote unit of claim 4, wherein the remote unit is a smart card, a mobile communications device, a personal data assistant or a part of a car.

8. System for generating corresponding keys of a first cryptographic key set, the system comprising: a remote unit and a central unit; wherein the central unit is adapted to generate a first cryptographic key on the basis of a first information set, wherein the first cryptographic key allows to access the remote unit; wherein the remote unit is adapted to generate a second cryptographic key on the basis of a second information set; wherein the first cryptographic key and the second cryptographic key form the corresponding keys of the first cryptographic key set; wherein the first and second cryptographic keys are generated independently from each other.

9. The system of claim 8, wherein the generation of the second cryptographic key in the remote unit is triggered by at least one of the following events: a) a reception of a first message from the central unit at the remote unit, wherein the first message is a dedicated message from the central unit to the remote unit; b) a reception of a multicast message from the central unit at the remote unit, wherein the multicast message is a message sent from the central unit to a plurality of remote units; c) a reception of operation data at the remote unit, wherein the operation data represents an operation at the remote unit which requires the second cryptographic key; and d) an application of a third cryptographic key to the remote unit, wherein the third cryptographic key belongs to a second cryptographic key set which is older than the first cryptographic key set.

10. The system of claim 8, wherein the first and second cryptographic keys are generated such that a calculation of the first and second information sets is not possible on the basis of the first and second cryptographic keys and such that no further cryptographic keys can be derived from the first and second cryptographic keys.

11. Computer program for a system for generating corresponding keys of a first cryptographic key set, the system comprising a remote unit with a first processor and a central unit with a second processor, wherein, when the computer program is executed on the first and second processors, the following operation is performed: generating a first cryptographic key in the central unit on the basis of a first information set; generating a second cryptographic key in the remote unit on the basis of a second information set; wherein the first cryptographic key and the second cryptographic key form the corresponding keys of the first cryptographic key set; wherein the first and second cryptographic keys are generated independently from each other.