Method for encrypted data exchange and communication system

0001The invention relates to a method for encrypted data exchange between subscribers of a communication system and a communication system.

0002The present invention is in the field of communication technology and in particular in the field of contactless communication for the purpose of identification. Although applicable in principle to any communication systems, the present invention and the problems underlying it are explained below with reference to so-called RFID communication systems and their applications. RFID stands for "Radio Frequency Identification". For the general background of this RFID technology reference is made to the "RFID Handbook" by Klaus Finkenzeller, Hansa-Verlag, third updated edition, 2002.

0003In RFID systems known today, an electromagnetic signal emitted by a base station (or reading station or reader) is typically picked up by a passive transponder (or tag) which uses it to obtain the energy required in the transponder. In most UHF-based or microwave-based RFID systems, in addition to this unidirectional energy transmission, there is also typically bidirectional data communication based on a so-called challenge / response method. The base station continuously sends out request signals (data request, challenge), which are only answered when a corresponding transponder is within the effective range of this base station. In this case, the transponder located in the immediate vicinity of the base station responds with a response signal (response). Such RFID transponders are used, for example, for marking objects, such as goods, documents and the like.

0004In contrast to conventional wire-based data communication, the data communication between the base station and a corresponding transponder takes place almost independently and to a certain extent in the background, without a user having to be present at all. This means that the data communication is recorded as soon as an authenticated transponder is within the effective range of the associated base station. While, for example, when reading a data carrier, such as a floppy disk, a USB stick or the like, this must be brought into conscious contact with a corresponding reader by the user and in the case of a wired data communication, the data communication must also be initiated by the user aware This is not the case with RFID-based wireless data communication.

0005This has some significant advantages, such as identification in the logistics sector, in department stores, etc. However, this technology of RFID-based data communication also has some disadvantages that must be considered in many applications.

0006Such a problem relates to the reading of data contained in an RFID transponder by an unauthorized user (attacker), especially if this data is security-critical data. For these reasons, an RFID-based data communication system also typically includes a security mechanism that secures, for example, data communication by modulating a security code from the base station to the transmit signal, which can then be decoded and evaluated by the transponders allowed to communicate with the data. After successful evaluation, the transponder allowed on the data communication sends a response signal, which also contains a security code, back to the base station, which can then be evaluated for authentication of the transponder in the base station. By means of this authentication, it is ensured in the base station that unnoticed no unauthorized user can couple into the data communication and thus read security-critical data.

0007An essential constraint in transponder-based data communication is that the simplest and quickest possible data communication between base station and transponder should take place. On the one hand, this is due to the fact that the transponder typically has only low resources, that is, on the one hand, low energy resources and, on the other hand, low storage and computational resources, so that typically the smallest possible amounts of data should be evaluated and authenticated during authentication. On the other hand, this authentication should also be carried out as quickly as possible, since, especially in the case of dynamic RFID-based data communication systems, the transponder to be authenticated is very often within the range of action of the respective base station for only a small amount of time. Within this short period of time, on the one hand, a data communication connection must be established, authenticated, and then the data exchanged.

0008To ensure the data communication between base station and transponder, for example, a cryptographically secured data communication based on asymmetric cryptographic methods can take place. Essential for these cryptographic encryption methods is that a reversal, that is a determination of the private key from the public key, in a reasonable time with the available computing capacity is hardly manageable.

0009It has proven to be advantageous to use cryptographic encryption algorithms based on elliptic curves, since these provide high security with short key lengths. Such cryptographic encryption methods based on elliptic curves are very efficient, which is in particular due to the fact that, in contrast to other known cryptographic methods, no subexponential propagation attack method is known in these methods. In other words, this means that the security gain per bit of the security parameters used is higher in the case of elliptic curve-based methods and thus significantly shorter key lengths can be used for practical applications. Thus, cryptographic methods based on elliptic curves are more efficient and require less bandwidth for transmission of the system parameters than other cryptographic methods with a comparable degree of achievable security.

0010The cryptographic methods thus represent a compromise between an expected security and the computational effort when encrypting data.

0011In the German patent application <patcit id="pcit0001" dnum="DE10161138A1"><text>DE 101 61 138 A1</text></patcit> It is shown that a determination of the scalar multiple of a point is possible based on the X-coordinate of this point already without consulting the Y-coordinate. Corresponding calculation rules are also described for any body in this document. This can result in much more efficient implementations of point arithmetic, such as a Montgomery ladder, for scalar multiplications, a lower number of body multiplies per point addition, and a smaller number of registers for dot representation of the intermediate results.

0012The European patent application <patcit id="pcit0002" dnum="EP1675300A1"><text>EP 1 675 300 A1</text></patcit> describes an authentication method between subscribers of a communication system in which, using bilinear mappings, a cryptographic encryption of the data communication between the subscribers of the communication system takes place. This cryptographically secured data communication is based on elliptic curves using a challenge-response method. In the publication "The Static-Diffie-Hellman Problem" by Daniel R. L. Brown and Robert P. Gallant of June 23, 2005, describe a new attack on cryptographic methods whose security relies on the discrete logarithm problem in a finite group. This is particularly applicable to elliptic curves. The described attack can then be carried out efficiently if an attacker has a device available (called "oracle" in the literature) which contains a secret scalar s and the attacker is given the result of the calculation T = sU when an arbitrary point U is entered. So the result point T of scalar multiplication, returns. In particular, the attack requires a sequence of points P0, P1, P2,..., Pn on the elliptic curve, where P_i = sP_i-1 applies. This attacker scenario is particularly in the case of the German patent application<patcit id="pcit0003" dnum="DE10161138A1"><text>DE 101 61 138 A1</text></patcit> given method, which is particularly suitable for applications on systems with limited storage space and low processing power available.

0013Against this background, the object of the present invention is to provide an authentication for wireless data communication, which is not compromised by the attack disclosed above. Furthermore, the object of the invention to provide an authentication for a wireless data communication, for which in particular a lower computational effort with consistently high security is needed and which is especially fast.

0014According to the invention, this object is achieved by a method having the features of patent claim 1 and / or by a communication system having the features of patent claims 20.

0015Accordingly, it is provided:<ul id="ul0001" list-style="none" compact="compact"><li>A method for encrypted data exchange between subscribers (2, 3) of a communication system (1) using cryptography based on elliptic curves, wherein upon a request from a first subscriber (2) from the second subscriber (3) a result of a first scalar multiplication is calculated. With the aid of a non-injective mapping, a function value is determined from the result of the scalar multiplication so that the function value does not permit a clear conclusion on the result. Finally, the determined function value is sent in response back to the first subscriber (2).</li></ul>

0016A communication system for the authentication of the participants of the communication system using an encryption method according to the invention.

0017The idea on which the present invention is based, in the case of authentication between two subscribers of a communication system and, in particular, when a reply signal is transmitted from a transponder back to a base station, supplies this data to be transferred back to a non-injective image, so that the function values ​​thus determined do not allow a clear conclusion on the result. The fact that, for example, the complete x-coordinate of the result point is no longer output, but a function value calculated therefrom, which no longer allows a clear reconstruction of the x-coordinate, the iteration of the scalar multiplication using the oracle is no longer possible for the described attack and the attack is repelled.

0018In a particularly advantageous embodiment of the present invention, in the authentication between two users of a communication system and in particular in the transmission of a response signal from a transponder back to a base station, these data to be transmitted back to the non-injective image are reduced.

0019In the authentication of a transponder by a base station, an authentication protocol based on a challenge-response method is typically used. According to this authentication protocol, for example, the transponder calculates a scalar multiplication in response to a request from the base station and, as a result, obtains an x-coordinate in an affine representation. In previously known methods, the transponder returned the complete affine x-coordinate as a response signal to the base station during retransmission of the response.

0020The finding underlying the advantageous embodiment of the invention consists in the fact that the transponder does not have to send the complete values ​​back to the base station for the transmission of the affine representation of the x-coordinate. Rather, it is sufficient if the value is at least partially returned. Even with this almost incomplete answer then the base station is still able to make an authentication with relatively high security.

0021In a further advantageous embodiment of the present invention, for example, the transponder calculates a scalar multiplication in response to a request from the base station and, as a result, obtains an x-coordinate in a projective representation. This projective representation contains two values ​​(X, Z) that can be displayed in binary representation next to one another. In previously known methods both values, that is, the pair (X, Z) of the x-coordinate, were sent back to the base station as response signal by the transponder in the retransmission of the response.

0022The finding underlying the advantageous embodiment of the invention consists in the fact that not both values ​​have to be sent back to the base station from the transponder for the transmission of the projective representation of the x-coordinate. Rather, it is sufficient if only one of these two values ​​is completely returned and the second value in each case at least partially returned. Even with this almost incomplete answer then the base station is still able to make an authentication with relatively high security.

0023The particular advantage of both listed embodiments is that it allows the response data transmitted back from the transponder to be reduced, which reduces the total amount of response data to be transmitted for authentication. As a result, the transponder requires less time for retransmission, authentication and the associated computation operations. In addition, the Static Diffie Hellman attack is also repelled in these embodiments, since no longer the complete x-coordinate of the result point is output in affine or projective representation, and thus the iteration of scalar multiplication using the oracle is no longer possible for the described attack , Overall, this makes the entire authentication process significantly easier and faster, without any loss of security during authentication.

0024For example, the transponder transmits only a part, for example half, of the value of the affine x-coordinate or of one of the two values ​​of the projectively represented x-coordinate. According to the invention this is realized in that, for example, only the upper part or the upper half or the lower part or the lower half of the corresponding calculated value of the x-coordinate is transmitted back. The base station then checks whether this part or half of the value coincides with the corresponding part or half of the value corresponding to this calculated value. Only when the part or half of the bits are identical, the transponder that transmits the response data is accepted as authentic by the base station.

0025The authentication method according to the invention with the variant of the data reduction in certain applications of the transponder, in which the transponder transmits projectively represented coordinates in response, has various advantages:

0026The amount of bits to be transmitted in the x-coordinate in the projective representation is significantly reduced. In the case mentioned above, in which only half of the bits of one of the two values ​​is transmitted, the total amount of data to be transmitted is then reduced by half in the affine case and by one fourth in the projective case.

0027The data reduction causes only a negligible reduction in security in many applications, such as the authentication protocol disclosed in the present patent application. It is a well-known result of cryptography that an elliptic curve suitable for cryptographic applications over a finite field GF (2^d) only a security of 2^{d / 2} offers. That is, although elements of the body having a length of d bits are used, the security of this type of authentication using a public key corresponds to only a key length of d / 2. Thus, from the point of view of an unauthorized user, it is just as difficult to break the authentication process and thereby access the transponder's secret key, as in the above-described inventive method of reducing the amount of data provided in reply response transmission, to provide a valid response. Depending on the application and the security requirement specified there or also required, it is possible to further reduce the number of bits of the x-coordinate proportionately transmitted by the transponder to the base station.

0028The non-transmitting bits represent a randomly generated secret known only to the transponder and the base station involved in the data communication. These non-transmitted bits can be used, for example, as keys in subsequent protocol steps of the authentication method according to the invention. This means that in the inventive authentication method with data reduction by only partial transmission of x-coordinates, the protocol for (unilateral) authentication is extended to a protocol for (unilateral) authentication with key agreement.

0029In a variant of the authentication method according to the invention, if the transponder can perform divisions in the finite field and thus calculate the affine representation of the coordinates of the response, the authentication method can also be applied to the affine value in the manner described. In this case, the number of bits to be transmitted also reduces significantly, typically to half of the bits to be transmitted.

0030Advantageous embodiments and modifications of the invention will become apparent from the other dependent claims and from the description in conjunction with the figures of the drawing.

0031The invention will be explained in more detail with reference to the embodiments indicated in the drawings. Showing:<dl id="dl0001"><dt>Fig. 1a, 1b</dt><dd>Examples of an elliptic curve;</dd><dt>Fig. 2</dt><dd>an example of addition using an elliptic curve;</dd><dt>Fig. 3</dt><dd>a block diagram of the structure of a communication system according to the invention;</dd><dt>Fig. 4</dt><dd>a flowchart for illustrating the inventive authentication method on the basis of elliptic curves;</dd><dt>Fig. 5a-5c</dt><dd>schematic representations for explaining the method for data reduction of the response data and the method for comparing these data-reduced response data with calculated response data.</dd></dl>

0032In the figures of the drawing are identical and functionally identical elements, features and signals, unless otherwise stated, provided with the same reference numerals.

0033The authentication method according to the invention has a new security protocol, which is based on an arithmetic for elliptic curves. Therefore, before describing the authentication method according to the invention, the most important properties of elliptic curves will first be described on the basis of FIG<figref idref="f0001">Fig. 1a and 1b</figref> explained.

0034An elliptic curve over a finite field (Galois field) GF (2^d) is the zero set of the cubic equation <maths id="math0001" num="(1)"><math display="block"><msup><mi mathvariant="normal">y</mi><mn mathvariant="normal">2</mn></msup><mo mathvariant="normal">+</mo><mi>xy</mi><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">y</mi><mn mathvariant="normal">3</mn></msup><mo mathvariant="normal">+</mo><mi mathvariant="normal">a</mi><mo>⁢</mo><msup><mi mathvariant="normal">x</mi><mn mathvariant="normal">2</mn></msup><mo mathvariant="normal">+</mo><mi mathvariant="normal">b</mi><mn mathvariant="normal">.</mn></math><img file="EP2124382A1_D0001.tif" /></maths>Here x and y denote variables and the coefficients a and b with b ≠ 0 denote coefficients in the Galois field GF (2^d).

0035In <figref idref="f0001">Fig. 1a and Fig. 1b</figref> By way of example, two elliptic curves are shown above the real numbers.

0036With the addition of an infinitely distant point as a neutral element, this set of zeros forms an additive group whose group law can be geometrically interpreted, at least for elliptic curves, over the real bodies. Such an additive group consists of a set of numbers and an addition (group operation). In addition, there is a neutral element in this group which, when added to a number from the set of numbers, does not change its value (for example, zero). Furthermore, an inverse element exists for each value of the number set, so that when the corresponding value is added to the inverse element, the neutral element is obtained. Essential are two results from algebraic geometry (see<figref idref="f0002">Fig. 2</figref>):

0037Each line intersects an elliptic curve in three points that are not necessarily different. For two, not necessarily different points, a third point can be calculated so that the sum of the three points represents the neutral element. Let P and Q (with P ≠ -Q) be two points and g the straight line through these points P, Q, then this line g intersects the elliptic curve at a third point R. By mirroring R at the X-axis one obtains S = P + Q. For the case P = -Q the slope of g is infinite and the third intersection R is the infinite far point.

0038Analogous to the definition of scalar multiplication in vector spaces, scalar multiplication is defined on elliptic curves. Let P be a point of an elliptic curve and let k be a natural number. The scalar multiplication k * P corresponds to a k-times addition of P to itself. This scalar multiplication k * P forms the essential building block in cryptographic systems based on elliptic curves. For cryptographically strong elliptic curves, scalar multiplication is a one-way function, ie it can be calculated in polynomial time, but according to current research and technology, it can only be inverted in exponential time. An efficient algorithmic reconstruction of the scalar is therefore difficult to imagine. This one-way function forms the basis for cryptographic authentication procedures based on elliptic curves.

0039A known method for implementing such scalar multiplications based on elliptic curves is the so-called Montgomery ladder or Montgomery algorithm. The Montgomery ladder can be implemented in such a way that to calculate the x-coordinate of a scalar multiple of a point P only the x-coordinate of P and only additions and multiplications in the Galois field GF (2^d) be used. There are no elaborate inversions required here. The two-sided authentication method according to the invention described below is based on this Montgomery algorithm.

0040Before the two-sided authentication method according to the invention is described, will be described below with reference to the block diagram in the <figref idref="f0003">Fig. 3</figref> first explained in more detail the basic structure of a communication system according to the invention.

0041In <figref idref="f0003">Fig. 3</figref> Reference numeral 1 denotes a communication system, for example, an RFID communication system. The RFID communication system 1 contains a first subscriber (base station 2) and at least one second subscriber (transponder 3). Base station 2 and transponder 3 are in a bidirectional communicative connection via a wireless communication link 4. The communication system 1 can be designed, for example, as a so-called master-slave communication system 1, the base station 2, for example, acting as a master and the transponder or transponders 3, for example, each as a slave.

0042The base station 2 comprises a control device 5, a transmitting / receiving device 6 and a transmitting / receiving antenna 7. In the same way, the transponder also comprises a control device 8, a transmitting / receiving device 9 and a common transmitting / receiving antenna 10.

0043The transmitting / receiving antennas 7, 10 can be designed as inductive coil antennas or as dipole antennas.

0044In the respective control devices 5, 8, the flow of data communication is controlled. For this purpose, this control device typically contains a computing device (arithmetic unit, CPU) in which the arithmetic operations are carried out, in particular for authentication. The control devices 5, 8 may be designed, for example, as a program-controlled device, such as, for example, as a microcontroller or microprocessor, or may also be implemented in a hard-wired logic circuit.

0045The control device 5 of the base station 2 is designed to transmit high-frequency carrier signals 11 to the antenna 10 of the transponder 3 via the antenna 7. In the same way, the control device 8 and the transceiver 9 of the transponder 3 are designed to send back corresponding response signals 12 to the base station 2 in response to the transmitted carrier signals 11.

0046The base station 2 also has an evaluation device 14. This evaluation device 14 is arranged in the receiving path 21 of the base station 2 and arranged downstream of the receiver of the transmitting / receiving device 6. In the same way, the transponder 3 has an evaluation device 15 in the reception path 23 of the transponder 3. In the respective evaluation devices 14, 15, the evaluation of the received data of a data communication takes place.

0047According to the invention, both the base station 2 and the transponder 3 now have an authentication module 16, 17, which are arranged between the respective transmitting / receiving device 6, 9 and control device 5, 8 of the base station 2 or of the transponder 3. These authentication modules 16, 17 are designed here as separate modules. Preferably, however, a respective authentication module 16, 17 is part of the respective control device 5, 8.

0048An authentication module 16, 17 further comprises a memory 18, 19, in which, for example, data, keys or the like, which are required for the authentication or must be cached, are stored. The memories 18, 19 typically contain a RAM memory in which, for example, calculation results are stored. Additionally or alternatively, these memories 18, 19 may also comprise a nonvolatile memory, such as EEPROM or flash memory, in which system parameters, parameters of the various communication participants, such as a subscriber-specific private key, a public key, a subscriber-specific certificate or like, are stored.

0049The principle of the authentication method (or authentication protocol) according to the invention will be described by way of example with reference to the schematic representations in FIGS <figref idref="f0004">Fig. 4</figref> and <figref idref="f0005">5</figref> explained.

0050<figref idref="f0004">Fig. 4</figref> schematically shows the base station 2 and the transponder 3 of the communication system 1, where there only the authentication modules 16, 17 and the memory devices 18, 19 are shown within these devices 2, 3. It is assumed that public keys are stored in the base station-side memory device 18 and that in the memory device 19 of the transponder 3 its certificate, the transponder-side secret key and possibly the public key are stored.

0051An example of the inventive authentication method on the basis of elliptic curves will now be described with reference to the flowchart in FIG <figref idref="f0004">Fig. 4</figref> described.

0052The following parameters are specified as system parameters, ie as parameters that apply to the entire communication system 1 and thus to the entire authentication.<ul id="ul0002" list-style="dash" compact="compact"><li>It is given a suitable elliptic curve.</li><li>xp denotes an affine x-coordinate of the base point P on the elliptic curve.</li><li>xS designates a public, ie the base station and the transponder known key for signature verification.</li></ul>

0053The following parameters are provided for the transponder 3:<ul id="ul0003" list-style="dash" compact="compact"><li>ξT denotes the transponder-side secret key, which therefore the base station 2 does not know.</li><li>xT, rT, sT denote the certificate Z of the transponder 2, where xT denotes the public key (affine x-coordinate of the point T = ξT * P) and rT, sT the signature of xT verifiable by the public key xS.</li></ul>

0054This in <figref idref="f0004">Fig. 4</figref> The authentication method illustrated is performed as follows:

0055In steps 1) - 3), the base station 2 generates the request C = x1 (C = Challenge). For this purpose, a value r1 is randomly selected. The base station 2 then calculates from this value r1 and the system parameter xp the request (X1, Z1) which represents the projective x-coordinate of the point P1 (P1 = r1 * P). From these two values ​​X1, Z1 the affine x-coordinate x1 calculated as a request is calculated by a division. This query x1 represents the x-coordinate of the point P1 = r1 * P for a random scalar.

0056The base station 2 sends this request C = x1 in step 4) to the transponder 3.

0057In step 5), the response R (R = response) is calculated. For this purpose, the transponder 3 calculates the corresponding response data R = (X2, Z2) for the query x1, which represent the projective x-coordinates of the point P2 = ξT * P1 = ξT * (r1 * P).

0058In step 6), the response data R = (X2, Z2) generated by the transponder 3, which represent a randomly selected projective representation of the x-coordinate of the point P2, are applied to R '= (X2', Z2) using a noninjective transformation ) reduced. According to the invention, a data reduction is thus carried out here at one of these two values ​​(X2, Z2) in method step 6).

0059In step 7), the response data R '= (X2', Z2) generated by the transponder 3 are sent back together with the certificate Z = xT, rT, sT of the transponder 3 to the base station 2.

0060The base station 2 checks the certificate Z = xT, rT, sT of the transponder 3 in step 8). If the certificate Z is not valid, then the base station 2 rejects the transponder 3 as not authentic.

0061In steps 9) and 10), the base station 2 checks the response of the transponder 3. The base station 2 calculates the calculated projective x-coordinate (X3, Z3) of the point P3 = r1 * xT = r1 * (ξT * P) and checks in this case, whether the data (X2 ', Z2) transmitted by the transponder 3 with the data (X3, Z3) generated in the base station 2 can be projective coordinates of the same point. This is the case if and only if the results of scalar multiplications are:<maths id="math0002"><math display="block"><mi mathvariant="normal">F</mi><mfenced><mi mathvariant="normal">Z</mi><mo>⁢</mo><mn mathvariant="normal">2</mn><mo mathvariant="normal">*</mo><mi mathvariant="normal">X</mi><mo>⁢</mo><mn mathvariant="normal">3</mn><mo mathvariant="normal">/</mo><mi mathvariant="normal">Z</mi><mo>⁢</mo><mn mathvariant="normal">3</mn></mfenced><mo mathvariant="normal">=</mo><mi mathvariant="normal">X</mi><mo>⁢</mo><mn mathvariant="normal">2</mn><mo>⁢</mo><mi mathvariant="normal">'</mi><mo mathvariant="normal">,</mo></math><img file="EP2124382A1_D0002.tif" /></maths>where F represents the same non-injective mapping that the transponder 3 used in step 6) to calculate the response data R '= (X2', Z2). In the described embodiment, a data reduction on the calculated value Z2 * X3 / Z3 is carried out in the same way, as was done in step 6) in the transponder 3).

0062If this relationship applies, then the transponder 3 is authentic. If this is not the case, then the base station 2 rejects the transponder 3 sending the response data R 'as not authentic.

0063It is essential here that the generation of the request C and the response R, R 'and the corresponding certificates Z are specified such that the corresponding authentication protocol based on elliptic curves over the Galois field GF (2^d) can be carried out.

0064In previously known methods, the entire x-coordinate (X2, Z2) of the point P2 was transmitted back to the base station, that is, from this x-coordinate, both values ​​X2, Z2 of the response R were completely retransmitted. The base station 2 was able to dispense with the application of the non-injective transformation for data reduction in the examination of the response R and the connection required for the test had the form X2 * Z3 = X3 * X2. This has after step 5) immediately the step 7) connected. According to the invention, an additional method step 6) is now provided between steps 5) and 7). This additional process step 6) denotes a data reduction step. In this method step 6), the response data R = (X2, Z2) generated by the transponder 3, which represent a randomly selected projective representation of the x-coordinate of the point P2, are reduced by applying a non-injective transformation. According to the invention, a data reduction is thus carried out here at one of these two values ​​(X2, Z2) in method step 6).

0065In the embodiment in the <figref idref="f0005">Fig. 5</figref> Let it be assumed that at the first value X2 of the projective representation of the x-coordinate (X2, Z2) a data reduction is performed so that the x-coordinate now has the two values ​​(X2 ', Z2) and X2' one over the value X2 has reduced data content. This data-reduced response R '= (X2', Z2) is then sent in the method step 7) from the transponder 3 to the base station 2 together with the certificate Z of the transponder 3.

0066It goes without saying that instead of a data reduction of the first value X2 of the x-coordinate additionally or alternatively, a data reduction of the respective second value Z2 can be made.

0067The base station 2 then checks whether the calculated in the base station 2 number (X3, Z3) with the transmitted from the transponder 3 R 'match. However, since this response R '= (X2', Z2) is not complete but data-reduced, only the corresponding part of the term X3 * Z2 / Z3 obtained by applying the noninjective transformation will be the component of the response X2 'checked. Only if, in the exemplary embodiment, this corresponding part of the number X3 * Z2 / Z3 coincides with X2 ', then the transponder 3 is accepted as authentic by the base station 2.

0068In the following, this method of data reduction as well as the corresponding method for comparing these data-reduced values ​​by means of schematic representations in FIGS <figref idref="f0005">Fig. 5a-5c</figref> briefly explained:

0069<figref idref="f0005">Fig. 5a</figref> shows the x coordinate or number 30 generated with method step 5) <figref idref="f0005">Fig. 5a</figref> First, the structure of the number 30 is shown. This number 30 contains two numerical values ​​X2, Z2. This x-coordinate 30 and thereby their values ​​X2, Z2 are shown here in binary coding. It is assumed that each of the two values ​​X2, Z2 is eight bits wide and these two eight-bit wide values ​​X2, Z2 are arranged directly adjacent to each other. The entire x-coordinate 30 is thus 16 bits wide. In the example shown, the value X2 of this number 30 is subdivided into an upper, four-bit-wide half 32 with the bit sequence 1010 and a lower four-bit-wide half 33 with the bit sequence 1011. The value Z2 of the number 30 also has two half-thieves 34, 35 with the bit sequences 0111 and 0101.

0070In method step 6), a data-reduced number 31 having the values ​​X2 ', Z2 is generated from the number 30. For this purpose, for example, the upper half 32 of the value X2 for the generation of the data-reduced number 31 is neglected, that is, the data-reduced number 31 has only the lower half 33 of the value X2 and the complete value Z2. After the data reduction in step 6), the data-reduced x-coordinate 31 contains only the lower half 33 of the value X2 and both halves 34, 35 of the value Z2. The upper half 32 of the value X2 is no longer part of the data-reduced x-coordinate 31 and thus is not transmitted back from the transponder 3 to the base station 2.

0071In the example shown the <figref idref="f0005">Fig. 5</figref> For the data-reduced x-coordinate 31, the upper half 32 was neglected. Of course, it would also be conceivable to neglect here the lower half 33 of the value X2 or one of the two halves 34, 35 of the value Z2. In addition, exactly half of the value X2 and thus four bits of the eight-bit content of the value X2 were neglected in each case. It would be conceivable here to have any data reduction of the value X2 different from 0, that is, it would also be conceivable to neglect, for example, only one bit up to seven bits of the value X2 for the generation of the data-reduced x-coordinate. It would also be conceivable to apply further non-injective maps of elements of the finite field which can not be easily realized by neglecting bits of one of the values ​​of the projective representation.

0072Based on <figref idref="f0005">Fig. 5c</figref> the method step 10) will now be described. In the authenticity check, the number 37 is first calculated from the values ​​X3, Z3 and the value Z3 contained in the response of the transponder 3 by the formula X3 * Z2 / Z3. The number 37 is again divided into two halves, the numbers 38 and 39. The verification of authenticity is now not by comparing the two pairs of numbers 32,33 and 38,39, but it is only the number 33 compared with the number 39.

0073In the present case the <figref idref="f0005">Fig. 5</figref> For example, the bit content of the section 33 is identical to the respective bit content of the section 39, so in this case, the base station 2 identifies the corresponding transponder 3 having sent the data reduced number 31 as authentic. This, although the upper portion 32 of the value X2 is not compared with the upper portion 38 of the corresponding value X3 * Z2 / Z3. It is based on the knowledge that, in particular with very large bit width of the numbers to be compared, it is already sufficient to transmit only a part of these values ​​and to compare them with the corresponding part. If these sections compared with each other agree, then one can assume with very high probability that the corresponding pairs of numbers 32,33 and 38,39 are identical.

0074Although the present invention has been described above with reference to a preferred embodiment, it is not limited thereto, but can be modified in various ways.

0075In particular, the invention is not restricted exclusively to RFID systems, but can also be extended, for example, to the item identification (item identification). Frequently, such parts need not be clearly identified. Here it is also often sufficient that the presence of, for example, a faulty part can be excluded. This is usually referred to as non-unique identification. When operating the transponder in this context, this has the function of a sensor. Thus, the invention also expressly relates to such sensors in which a communication for reading and writing data of a data carrier or sensor are made.

0076Also, the invention is intended to refer to any data communication systems that are not necessarily RFID systems and that are not necessarily wirelessly configured.

0077In the <figref idref="f0003">Fig. 3</figref> and <figref idref="f0004">4</figref> was the sake of clarity, the structure of the RFID system and in particular the

0078Transponders and the base station deliberately shown greatly simplified. It goes without saying that the base station and the corresponding transponder may also contain the functional units required for data communication between base station and transponder, such as demodulator, modulator, power supply, synchronization device, decoder and the like.

0079In the <figref idref="f0003">Fig. 3</figref> and <figref idref="f0004">4</figref> in each case a distinction was made between the control device, the evaluation device and the authentication module. It goes without saying that these devices or parts thereof, for example, may be part of the control device or may be formed separately therefrom.

0080It should also be noted that both the base station and the transponder can have a single transceiver and an associated transceiver antenna. Of course, it would also be conceivable that the base station and / or the transponder can have separate transmitting / receiving devices and in particular a transmitting antenna and a separate receiving antenna.

0081The data communication system and data communication method described above have been described by the reader-talks-first principle. It would also be conceivable, of course, the principle of "day-talks-first", in which the base station is initially waiting for a request from a transponder. However, this second mentioned principle has a worse reaction time, so that especially in modern so-called "long-range" data communication systems, such as those used for RFID, preferably the "reader-talks-first" principle is used.

0082It goes without saying that based on <figref idref="f0005">Fig. 5</figref> described authentication method according to the invention is to be understood only as an example. Of course, the individual method steps and applied mathematical operations could also be modified and modified within the scope of the invention, for example by functionally equivalent or alternative method steps.

0083It should also be noted that the numbers and bit widths given are to be understood as examples only and should in no case limit the invention to them. In particular, it would also be conceivable to use a larger or a smaller bit width for the respective values. Moreover, the different sections of a value do not have to have the same bit width, but may be different. The same applies to the bit width of the two values ​​X, Z of a respective projective x-coordinate.

0084In the publication "<nplcit id="ncit0001" npl-type="s"><text>The Static-Diffie-Hellman Problem "by Daniel RL Brown and Robert P. Gallant of June 23, 2005</text></nplcit> A new attack on cryptographic procedures whose security is based on the discrete logarithm problem in a finite group is described. This is particularly applicable to elliptic curves. The described attack can then be carried out efficiently if an attacker has a device available (called "oracle" in the literature) which contains a secret scalar s and the attacker is given the result of the calculation T = sU when an arbitrary point U is entered. So the result point T of scalar multiplication, returns. In particular, the attack requires a sequence of points P0, P1, P2,... Pn on the elliptic curve, where P_i = sP_i-1 applies. This attacker scenario is given in particular in the described RFID tag. The described RFID tag is exactly the technical realization of such an oracle.

0085In the case of the authentication protocol of the described RFID tag, the tag calculates a scalar multiplication and as a result obtains the x-coordinate in a randomly selected projective representation (X2, Z2). So far, the whole pair (X2, Z2) has been sent back to the terminal as a response. The security of the authentication protocol against the static-Diffie-Hellman attack has been ensured to date by the characteristics of the elliptical curves used. To ward off the static-Diffie-Hellman attack elliptic curves were therefore used whose orders contain so-called strong prime divisors. Within these cyclic subsets of the finite point groups generated by strong primers, the cryptographic applications were performed.

0086The method according to the invention is advantageously suitable for warding off such "static-diffie-hellman attacks". The RFID tag, as in the embodiment described above, returns only part of the calculated bits from one of the values ​​X2, Z2. The terminal then checks to see if the corresponding bits of the number X3 * Z2 / Z3 match the returned bits. If the bits are identical, the RFID tag is accepted as authentic. This reduces, on the one hand, the amount of bits of the response (X2, Z2) to be transmitted and, on the other hand, prevents the affine x-coordinate of the result from being reconstructed and used for a renewed invocation of the scalar multiplication in order to achieve the above-described sequence of Points P0, P1, P2, ..., Pn to create an attack.

0087Since the complete x-coordinate of the result point is no longer output, the iteration of the scalar multiplication using the oracle required for the described attack is no longer possible and the attack is averted. In general, if an attacker gets only part of the x-coordinate of the result point, there are very many values ​​that can occur as the x-coordinate of a point and still match the part known to the attacker. If an attacker attempts to perform the described attack on all possible points whose x-coordinates match the output pieces, the number of possible score sequences grows exponentially with the number of iterations and quickly becomes inefficient. In order to ward off the described attack, it is sufficient in practice if some bits of a coordinate of the result are already cut off and only a few continuations to x coordinates of points are possible.

0088Thus, in addition to data reduction, the method according to the invention additionally offers the advantage that an implicit protection against the static-Diffie-Hellman attack is achieved. The fact that an attacker can no longer iterate the calculations of the oracle, the described attack is no longer possible. In particular, no elliptic curves need to be used whose orders have strong primes.