WO1999055991A2 - Authentication method - Google Patents

Abstract

The invention relates to a method which enables an authentication of a first instance (key) with regard to a second instance (lock). To this end, a first component of a sequence of numbers are transmitted from the lock to the key, said numbers being determined by means of an iterated one-way function. Using a trap door, the precedent component is established from the key, and is sent back to the lock. The lock tests whether the precedent component is correct. If this is the case, the key is successfully authenticated with regard to the lock. Otherwise, the authentication is not carried out.

Description

description

Authentication procedure

The invention relates to a method for authentication.

A method for authentication (also: authentication, authentication) is known from [1].

An iterated one-way function f is a function that applies to

x ^ + 1 = f (* k) ^for k = 0, l, 2, ... (1),

i.e. starting with a value xo, the iterative application of the one-way function f returns a sequence of numbers

{x ₀ , xi, X2 • • • * k '• • •} ⁽²⁾ •

A reversal, that is to say a backward iteration according to which x _{m is to be determined} from knowledge of Xjn ₊ 1, is not possible at all or only with very great effort. An example of such a one-way function is the discrete logarithm modulo of a prime number p.

A "trapdoor function" is an iterated one-way function which allows its inversion by using a special solution mechanism (said "trapdoor").

If a second instance, e.g. a key, is to authenticate itself to a first instance, e.g. a lock (application example: immobilizer of a vehicle), the second instance sends a component to the first instance, the first instance in turn with another Component answers and thus authenticates itself to the second instance (mechanism of one-sided authentication). In general, authentication methods place high demands on a storage space to be made available.

The object of the invention is to provide a method for authentication, whereby extremely low demands are made on a storage space to be provided.

This object is achieved according to the features of the independent claim.

To solve this task, an authentication method is specified which comprises the following steps:

a) At the beginning, a first component is transmitted from a first instance to a second instance.

b) A second component is determined from the transmitted first component by means of a backward iteration with a special solution mechanism (the trap door described) and transmitted to the first instance.

c) Now it is checked on the side of the first instance whether the transmitted second component can authenticate the second instance. This will be the second

Component used as input for an iterated one-way function and the result compared with the first component.

d) If the result and the first component have identical values, then the second instance is successful compared to the first instance authenticated; If the result and the first component do not have identical values, the authentication is not successful.

It should be noted here that the second component in a sequence of values, which are determined by the backward iteration or the inverse iterated one-way function, represents a processor component of the first component.

The described transmissions can optionally be connectionless, e.g. via radio or by induction, or e.g. done connection-oriented via a cable.

A decisive advantage of the method described is that only a few components have to be kept in the memory, and the memory can therefore be dimensioned accordingly small.

An iteration, that is to say repeated authentication of the second instance with respect to the first instance, is preferably achieved in that after carrying out steps a) to d) the second component is set equal to the first component and the method is continued with step a).

An embodiment of the method is the implementation of a predetermined action, e.g. starting a vehicle from the first instance after the second instance has successfully authenticated.

A further development consists in that the iterated one-way function is determined by

wobei n eine ganze Zahl, mod den MODULO-Operator, xi die erste Komponente und X2 die zweite Komponente bezeichnen.

where n is an integer, mod the MODULO operator, xi the first component and X2 the second component.

Furthermore, the backward iteration is determined by

^x 2 ⁼ ^ T ^{mocl n} -

Said solution mechanism is that the second instance knows the prime numbers from which the number n is composed. For this purpose, the number n is preferably determined by

n = p q,

where p and q denote prime numbers that are very large.

This means that the determination of p and q with a simple knowledge of the number n cannot be realized with manageable effort. The "trapdoor" is the knowledge of p and q on the side of the second instance.

In the backward iteration there are four solutions (see exemplary embodiment below for illustration), from which the solution is selected which is a square mod n.

As part of an additional training, the first instance is an electronic lock and the second instance is an electronic key. In particular, the method can be used in an immobilizer for a vehicle.

Further developments of the invention also result from the dependent claims.

Exemplary embodiments of the invention are illustrated and explained below with reference to the drawings.

Show it 1 shows a block diagram comprising steps of a method for authentication,

Fig.2 is a sketch that symbolically represents an arrangement of lock and key.

In Fig.l a block diagram is shown, which comprises steps of a method for authentication. For this purpose, a second instance 102, preferably a key, is to authenticate itself to a first instance 101, preferably a lock.

The first instance 101 is aware of a component K (cf. step 103). This component Kj_ is transmitted to the second instance 102 in a step 105 and the component K is received in a step 106 on the second instance 102. A component Ki_ι_ preceding the component Ki is now determined on the second instance in a step 107 and transmitted to the first instance 101 in a step 108. For this purpose, the solution mechanism ("trap door") is used in step 107 in order to calculate the four roots of the first component Ki. Again through this solution mechanism one arrives at the root which is itself a square. So you have that

Processor component Ki-i of component Ki found. After the transmission (cf. step 108), the component K -i is received by the first instance 101 in a step 109. In a subsequent step 110, it is checked whether the received component Ki-i correctly authenticates the second instance 102. For this purpose, the component Ki-i is used as input for an iterated one-way function and the result is compared with the component Ki. If the result is not the same as the component Ki, a step 111 indicates that the authentication of the second instance 102 to the first instance 101 has failed and that Procedure ended (see step 112). Otherwise, the second instance 102 is successfully authenticated to the first instance 101 in a step 113. In a step 114, the component Ki__ becomes the new component Ki and continues with step 103.

In the following, the mechanism shown in Fig.l is explained using an example, without this being intended to limit the case described.

For example:

The following sizes are available:

Ki = 9 and n = p • q = 7 • 11 = 77.

In step 107, the processor component Ki-i is to be determined:

With the solution mechanism ("trapdoor") there are two sizes for p = 7 and q = ll:

^a l, 2 = J ^{mod 7} (Ia)

= ai = 3 mod 7 a ₂ = 4 mod 7

^a , 4 = ^ 9 mod 11 (Ib)

=> a = 3 mod 11 a4 = 8 mod 11 For p = 7 the numbers 3 and 4 solve the equation (la) and for q = ll the numbers 3 and 8 solve the equation (Ib).

The four solutions for equation (I) are now sought that take into account both a solution of equation (la) and a solution of equation (Ib):

(Ki ^x - _l ^± A mod n;

ia ₂ mod pl [4 mod 7

^(κ -ι ⁾ = \ A4 m _^ od qJj = [3 mo.d lJl l ^{=? mod n} -

The solution (Ki_ι), mod n is sought which has the result "3 mod 7" and the result "3 mod 11" as a condition. Such a solution is found with the Chinese remaining sentence. In the example above, the four solutions are:

(K __), = 3 mod 77;

( ^κ il) ₃ = ⁷⁴ mod 77;

( ^κ il) ₄ = 5 mod 77.

From the solutions (Ki_ι _) -, the solution that is a square mod n is selected. The squares mod p and mod q can each be calculated to: Squares mod 7: {1, 2, 4 (= a ₂ )};

Squares mod 11: {1, 4, 9, 5, 3 (= a3)}.

Thus it can be seen that the solution (Ki _] _) ₄ = 25 results from the solutions a ₂ and a ₃ for the equations (la) and (Ib) and both a ₂ and a3 themselves squares "mod 7" or represent "mod 11". So the solution is also (Ki_ιA = 25 a square "mod 77".

The number sought is 25 and is transmitted to the first instance as a second component.

2 shows a sketch which symbolically represents an arrangement of lock and key. This arrangement is preferably used in an immobilizer of a motor vehicle. A lock 201 requires authentication of a key 202 via a predetermined one

Communication channel 203. The information transmitted on the communication channel can be found in the flow chart from FIG.

Bibliography :

[1] C. Ruland: Information security in data networks, DATACOM-Verlag, Bergheim, 1993, ISBN 3-89238-081-3, pages 33-38 and 121-143.

Claims

claims 1. An authentication method comprising the following steps: a) a first component is transmitted from a first instance to a second instance; b) the second instance uses a backward iteration and a solution mechanism (Trapdoor) a second component from the first component and transmits the second component to the first instance; c) the first instance checks whether the first Component is equal to a result of an iterated one-way function applied to the second component; d) if the first component and the result are identical, the second instance authenticates itself to the first instance; if the first component and the result are not identical, the authentication fails. 2. The method of claim 1, in which, if authentication is successful, the second component is set equal to the first component and the method is continued with step la) in the next authentication attempt. Method according to Claim 1 or 2, in which a predetermined action is carried out by the first instance with the authenticated second instance. . Method according to one of the preceding claims, a) in which the iterated one-way function is determined by Xi = x ₂ mod n, where n denotes an integer, mod the MODULO operator, xi the first component and x ₂ the second component; b) in which the backward iteration is determined by

c) where the solution mechanism is that the second instance knows prime numbers from which the number n is composed; d) in which, from several solutions of the backward iteration, that second component is transmitted from the second instance to the first instance which is itself a square. 5. The method according to any one of the preceding claims, wherein the first instance is an electronic lock and the second instance is an electronic key. Method according to one of the preceding claims, ie the first instance is a lock of the motor vehicle and the second instance is a key of the motor vehicle.