EP1723511A1

EP1723511A1 - Manipulation proof production of authentic random numbers

Info

Publication number: EP1723511A1
Application number: EP05707924A
Authority: EP
Inventors: Andreas Franke; Reinhold Koller
Original assignee: Siemens AG
Current assignee: Continental Automotive GmbH
Priority date: 2004-03-08
Filing date: 2005-02-02
Publication date: 2006-11-22
Also published as: KR20060132921A; DE102004011170A1; US20070276890A1; JP2007537502A; DE102004011170B4; CN1930546A; CN100485604C; US7496617B2; WO2005085992A1

Abstract

The invention relates to a method and device for producing an authentic random number. The inventive method consists in obtaining the authentic random number on the base of a stochastic distributed duration (t) of an electric charge exchanging process. For this purpose, the processes for exchanging charge of memory cells, for example the EEPROM or FLASH memory cells, carried out by means of a charging pump are mentioned.

Description

Tamper-proof generation of real random numbers

The present invention relates to a method and an apparatus for generating a real random number

For example, for access protection or encryption purposes, it is necessary to generate good manipulation-proof random numbers. In connection with motor vehicle immobilizers, this generation of the random numbers takes place, for example, at the engine control level, which in many cases is an embedded system. The use of external sources due to manipulation possibilities and the use of special circuits due to the associated additional unit costs are ruled out.

To generate real random numbers, it is known, among other things, to use the low-order ^ bits of an A / D conversion of signals from a separate noise source, but this is associated with considerable costs. It is also known to generate a real random number by measuring the time of an external event, for example the duration of a key press carried out by the user. However, this solution is ruled out at least in cases where the system opens communication and therefore has to generate the random number before an external event. In addition to the generation of real random numbers, it is also known to use a pseudo-random number series and to store the current status, for example in a non-volatile memory: of the system. However, the quality of pseudo random numbers is insufficient compared to real random numbers. The invention is based on the object of specifying a method and a device with which a real random number can be generated quickly, that is to say, for example in the millisecond range, in a memory-saving manner, regardless of the device runtime, without storage between the operating cycles of the control device and without external sources (random triggers).

This object is solved by the features of the independent claims.

Advantageous refinements and developments of the invention result from the dependent claims.

The method according to the invention builds on the generic state of the art in that the real random number is generated on the basis of a stochastically distributed duration of an electrical recharging process. This solution creates a real random number, that is, not a pseudo-random number. Furthermore, the method cannot be manipulated by external wiring. In many cases, no additional components are required compared to the existing assembly of the respective system, so that the additional costs are low. Another advantage of the method is that it is not necessary to store a state which then manipulated _or: could be reset. The method according to the invention is particularly advantageous if the reloading process forming the stochastic source can be carried out in a component which is in any case part of the system which, in addition to fulfilling other tasks, must also generate the random number. In preferred embodiments of the method according to the invention it is provided that the reloading process comprises reloading at least one memory cell. Storage cells-n are part of modern systems anyway and therefore represent a particularly cost-effective basis for carrying out cLes reloading.

In this context, it can be provided, for example, that at least one memory cell is a memory cell of an EEPROM. The duration of a reload of an EEP-ROM

The memory cell is subject to comparatively large stoctastic scattering, on the basis of which real random numbers can be generated.

Alternatively, it is also possible that at least one

Memory cell is a memory cell of a FLASH memory --- rs. FLASH memories are being used increasingly and therefore in many cases represent a suitable basis for the generation according to the invention in real additional numbers without additional costs.

In preferred embodiments of the method according to the invention, it is further provided that the reloading process is carried out with the aid of a charge pump. The use of charge pumps is common, for example, in connection with EEPROMs, with on-chip charge pumps being provided in many cases.

In the method according to the invention, it can advantageously also be provided that the stochastic duration of the reloading process is recorded with the aid of a counter. It is advantageous if the clocking of the counter is as high as possible, so that with regard to the Gt-round position for the random number serving meter reading at the end of the reloading process, the largest possible scatter.

The method according to the invention is considered to be particularly advantageous if it is provided that it is carried out by an embedded system, in particular by an engine control system of a motor vehicle. In principle, all embedded systems come into question which are used in environments in which (also) the generation of good random numbers is necessary.

The device according to the invention builds on the generic state of the art in that it generates the real random number on the basis of a stochastically distributed duration of an electrical charging process. This results in the advantages and properties explained in connection with the method according to the invention in the same or similar manner, which is why reference is made to the corresponding statements above in order to avoid repetitions.

The same applies mutatis mutandis to the advantageous developments of the device according to the invention specified below, reference also being made to the corresponding statements in connection with the method according to the invention. ,

The device according to the invention is advantageously further developed in that it has at least one memory cell which is electrically charged to generate the random number. It can advantageously be provided that at least one memory cell is a memory cell of an EEPROM.

Additionally or alternatively, it is possible for at least one memory cell to be a memory cell of a FLASH memory.

The device according to the invention is advantageously further developed in that it has a charge pump for carrying out the reloading process.

In connection with the device according to the invention, it can further be provided that it has a counter for recording the stochastically distributed duration of the transfer process.

Embodiments of the device according to the invention in which it is provided that it is an embedded system, in particular an engine control of a motor vehicle, are considered to be particularly advantageous.

An essential basic idea of the present invention is that true random numbers can be generated practically without additional costs by systems if a component that is already part of the system is used as the stochastic source, for example a charge pump, which is part of a control unit. The invention is particularly suitable for all departments that have to generate a good, real random number with existing systems (that is to say without specially provided components) without having access to independent, tamper-proof generators (triggers). This includes, but is not limited to, in particular all cost-optimized embedded systems. In connection with motor vehicle technology, random numbers are required, for example, in particular for access protection (also during maintenance work) and for encryption purposes (for example immobilizer).

Embodiments of the invention are explained below by way of example with reference to the accompanying drawings.

Show it:

FIG. 1 shows a flow diagram which illustrates an embodiment of the method according to the invention;

FIG. 2 shows a graph which illustrates possible recharging processes of a memory cell;

Figure 3 is a highly simplified, schematic block diagram of components of an engine control.

The embodiment of the method according to the invention shown in FIG. 1 begins at step S1. In step S2, a counter is reset whose later counter reading serves as the basis for the generation of the real random number or which directly represents this random number. A reloading process is started in step S3 and the counter is started at the same time. The reloading process can be, in particular, writing to an EEPROM or FLASH memory cell, which is usually carried out using a charge pump. In step S4, it is checked whether the reloading process has been completed until this is the case. The counter is then stopped in step S5. In step S6, the counter reading is read out and as a real random number used. If necessary, however, the final random number can also be generated with the aid of further computing functions. The illustrated method ends in step S7.

FIG. 2 illustrates three stochastically distributed recharging processes of a memory cell. The actual duration of a current reloading process can lie between a shortest duration T '(curve Q') and a longest duration T ^{, f} (curve Q '") and can be, for example, T (curve Q).

FIG. 3 shows a highly simplified, schematic block diagram of components of an engine control, the engine control 18 shown being in the form of an embedded system. The motor controller 18 can include a large number of further components, not shown, which are required to fulfill all the tasks placed on the motor controller. All hereinafter explained in more detail components, that is not specifically superiors already part of the motor controller 18 to generate the true random numbers, see _v. The motor controller 18 shown has an intelligent controller 20, which is suitable, among other things, for controlling a charge pump 14, which is provided for reloading a memory cell 10 of a memory cell array 22 of an EEPROM 12 when the content of the memory cell 10 is to be changed. The controller 20 continues to communicate with a counter 16, with which the actual duration of a reloading process of the memory cell 10 is recorded. The person skilled in the art recognizes that the components illustrated in FIG. 3 can be used to carry out the method explained with reference to FIG. 1 in an advantageous manner. A renewed explanation of the process of generating a random number is therefore omitted at this point. The features of the invention disclosed in the above description, in the drawings and in the claims can be essential both individually and in any combination for realizing the invention.

Claims

claims

1. A method for generating a real random number, so that the real random number is generated on the basis of a stochastically distributed duration (T) of an electrical recharging process.

2. The method according to claim 1, wherein the reloading process comprises reloading at least one memory cell (10).

3. The method as claimed in claim 2, in that at least one memory cell (10) is a memory cell of an EEPROM (12).

4. The method according to claim 2 or 3, so that at least one memory cell (10) is a memory cell of a FLASH memory.

5. The method according to any one of the preceding claims, that the transferring process is carried out with the aid of a charge pump (14).

6. The method according to any one of the preceding claims, characterized in that the stochastic duration (T) of the transfer process is recorded with the aid of a counter (16).

7. The method as claimed in one of the preceding claims, such that it is carried out by an embedded system (18), in particular by an engine control system (18) of a motor vehicle.

8. A device suitable for generating a real random number, so that it generates the real random number on the basis of a stochastically distributed duration (T) of an electrical recharging process.

9. The device as claimed in claim 8, so that it has at least one memory cell (10) which is electrically recharged to generate the random number.

10. The device according to claim 9, so that at least one memory cell (10) is a memory cell of an EEPROM (12).

11. The device according to claim 9 or 10, so that at least one memory cell (10) is a memory cell of a FLASH memory.

12. Device according to one of claims 8 to 11, characterized in that it has a charge pump (14) for performing the reloading process.

13. The device according to one of claims 8 to 12, so that it has a counter (16) for detecting the stochastically distributed duration (T) of the recharging process.

14. The device as claimed in one of claims 8 to 13, that it is an embedded system (18), in particular an engine control (18) of a motor vehicle.