DE10057203C1

DE10057203C1 - Digital signal value calculation method for cryptography calculates scalar product from natural number and point along elliptical curve

Info

Publication number: DE10057203C1
Application number: DE2000157203
Authority: DE
Inventors: Rainer Bluemel
Original assignee: CV CRYPTOVISION GmbH
Current assignee: CV CRYPTOVISION GmbH
Priority date: 2000-11-17
Filing date: 2000-11-17
Publication date: 2002-06-06
Anticipated expiration: 2020-11-18

Abstract

The calculation method provides a scalar product from a natural number above 1, which is stored as a binary representation and a point along an elliptical curve, with calculation of the scalar product via an electronic calculator having a processor, e.g. a smart card microprocessor, without data-dependent current and/or power requirement.

Description

Die Erfindung betrifft ein Verfahren zur Berechnung eines digitalen Signalwertes für ein cryptographisches Verfahren, insbesondere für ein cryptographisches Verfahren mit öffentlichen Schlüsseln, das mit elliptischen Kurven über endlichen Körpern ar beitet.The invention relates to a method for calculating a digital signal value for a cryptographic process, in particular for a cryptographic process with public keys that work with elliptic curves over finite bodies beitet.

Das Konzept der Cryptographie mit öffentlichen Schlüsseln beruht auf zwei Schlüs seln, von denen einer dem Kommunikationspartner bekannt sein muß. Dies ist der so genannte öffentliche Schlüssel. Der entsprechende zweite Schlüssel, der sogenannte private Schlüssel, ist geheim zu halten. Zur Verschlüsselung wird der Klartext mit dem öffentlichen Schlüssel des Empfängers zu einer Nachricht so verknüpft, daß ein Chiffretext entsteht. Aus dem Chiffretext kann der Klartext nur unter Verwendung des privaten Schlüssels des Nachrichtenempfängers zurückgewonnen werden. Beispiels weise übermittelt eine Person A ihren öffentlichen Schlüssel an eine Person B. B ver schlüsselt eine Nachricht mit diesem öffentlichen Schlüssel und sendet den entstande nen Chiffretext an A. Den empfangenen Chiffretext kann nun A mit seinem privaten Schlüssel dechiffrieren. Das allgemeine Konzept der Verschlüsselung mit öffentlichen Schlüsseln geht auf einen Vorschlag von Diffie und Hellman aus dem Jahr 1976 zu rück.The concept of public key cryptography is based on two keys seln, one of which must be known to the communication partner. This is the case called public keys. The corresponding second key, the so-called private keys must be kept secret. The plain text is used for encryption the public key of the recipient to a message so that a Ciphertext is created. The plain text can only be extracted from the cipher text using the the recipient's private key can be recovered. example a person A wisely transmits their public key to a person B. B ver encrypts a message with this public key and sends the resulting one A ciphertext to A. A can now receive the ciphertext received with his private Decrypt the key. The general concept of public encryption Keys come to a proposal from Diffie and Hellman in 1976 back.

Neben der Verwendung des Schlüsselpaares zum Verschlüsseln von Nachrichten kann das Schlüsselpaar aus öffentlichem und privatem Schlüssel auch als digitale Signatur verwendet werden. Eine einfache Ausführung einer digitalen Signatur besteht darin, daß die Rolle von öffentlichem und privatem Schlüssel vertauscht wird. A versieht eine Nachricht bzw. deren Hash-Wert mit seinem privaten Schlüssel, B kann nach Er halt der Nachricht mit dem öffentlichen Schlüssel von A überprüfen, ob die Nachricht mit dem privaten Schlüssel von A unterschrieben wurde. Hierbei muß selbstverständ lich gewährleistet sein, daß der private Schlüssel nicht rekonstruiert werden kann.In addition to using the key pair to encrypt messages the key pair of public and private keys also as a digital signature be used. A simple implementation of a digital signature is that the role of public and private keys is reversed. A provides a message or its hash value with its private key, B can, according to Er hold the message with A's public key to check if the message signed with A's private key. This must go without saying Lich be sure that the private key can not be reconstructed.

Wichtige Voraussetzung bei der Verwendung von cryptographischen Verfahren mit öffentlichen Schlüsseln ist die Geheimhaltung des privaten Schlüssels. Denn für eine sichere Kommunikation ist es zum Austausch von Nachrichten gerade erforderlich, daß das Verschlüsselungsverfahren und die dabei verwendeten Größen allgemein bekannt sind, so daß die Sicherheit einzig und allein auf der Unkenntnis des privaten Schlüssels beruht.Important requirement when using cryptographic methods with public keys is the secrecy of the private key. Because for one secure communication it is just necessary to exchange messages that the encryption method and the sizes used are generally known are so that security is based solely on ignorance of the private Key is based.

Eine zentrale Operation bei der Verwendung von cryptographischen Verfahren mit öf fentlichen Schlüsseln ist das Potenzieren von natürlichen Zahlen. Beispielsweise ver wenden das als RSA verbreitete Verfahren von R. L. Rivest, A. Shamier und L. Adle man aus dem Jahre 1978 und das von El Gamal vorgeschlagene Verfahren aus dem Jahre 1985 das Potenzieren mit sehr großen natürlichen Zahlen zur Ver- und Ent schlüsselung.A key operation when using cryptographic methods with public Public keys are the exponentiation of natural numbers. For example ver apply the procedure of R. L. Rivest, A. Shamier and L. Adle, which is common as RSA one from 1978 and the method proposed by El Gamal from the 1985 the exponentiation with very large natural numbers for ver and ent encryption.

Neben der Verwendung von natürlichen Zahlen modulo einer Primzahl, die sich als Elemente von endlichen Primkörpern auffassen lassen, hat es sich bewährt, die Punkte elliptischer Kurven über endlichen Körpern zu betrachten; diese Punkte sind Lösungen einer Gleichung. Von besonderem Interesse sind hierbei die Galois-Felder GF (p), wobei p eine große Primzahl ist, und GF(2^k). Der Vorteil bei der Verwendung ellip tischer Kurven über endlichen Körpern liegt darin, daß für vergleichbare cryptographi sche Sicherheit mit deutlich kürzeren Schlüsseln gearbeitet werden kann; dies hat dann im allgemeinen deutlich kürzere Rechenzeiten zur Folge. Speziell für GF(2^k) ist eine weitere Beschleunigung durch spezifische Hardware, etwa Schieberegister mit Linearrückkopplung, möglich. In addition to using natural numbers modulo a prime number that turns out to be Let elements be taken up by finite prime bodies, the points have proven successful consider elliptic curves over finite fields; these points are solutions an equation. Of particular interest are the Galois fields GF (p), where p is a large prime number and GF (2 ^ k). The advantage of using ellip tical curves over finite fields is that for comparable cryptographi security can be worked with significantly shorter keys; this has then generally significantly shorter computing times. Especially for GF (2 ^ k) is a further acceleration by using specific hardware, such as shift registers Linear feedback possible.

Mathematisch handelt es sich bei einer elliptischen Kurve um eine kommutative Gruppe, dazu wird zu den Lösungspunkten der Gleichung ein zusätzlicher Punkt, das neutrale Element der Addition, hinzugenommen. Bei dem Rechnen mit Punkten auf einer elliptischen Kurve ist zwischen der Addition zweier verschiedener Punkte und der Verdopplung eines Punktes zu unterscheiden, da sie durch unterschiedliche Ver fahren realisiert werden. Unter einer skalaren Multiplikation wird eine mehrfache Ad dition eines Punktes der elliptischen Kurve zu sich selbst verstanden.Mathematically, an elliptic curve is a commutative Group, this becomes an additional point to the solution points of the equation, the neutral element of addition, added. When calculating with points an elliptic curve is between the addition of two different points and to distinguish the doubling of a point, since they are differentiated by different ver driving can be realized. Under a scalar multiplication, a multiple ad dition of a point of the elliptic curve understood to itself.

Als grobe Regel kann festgehalten werden, daß in einem cryptographischen Verfahren bei der Verwendung von Punkten einer elliptischen Kurve die skalare Multiplikation an die Stelle des Potenzieren von natürlichen Zahlen tritt.As a rough rule it can be stated that in a cryptographic process when using points of an elliptic curve, the scalar multiplication replaces the exponentiation of natural numbers.

Aus Vorstehendem ergibt sich, daß für die zentralen Operationen bei cryptographi schen Verfahren mit öffentlichen Schlüsseln, die Berechnungen schnell und vor An griffen sicher auszuführen sind.It follows from the above that for the central operations at cryptographi procedures with public keys, the calculations quickly and in advance handles must be carried out safely.

Ein möglicher Angriff gegen eine Vorrichtung ist die sogenannte Power-Attack. Bei diesem Angriff versucht der Angreifer Kenntnisse vom Geheimnis, insbesondere vom privaten Schlüssel, zu erlangen, indem er Strom- und/oder Leistungsaufnahme wäh rend der Berechnung einer Signatur oder der Ver- bzw. Entschlüsselung aufzeichnet. Die Strom- und/oder Leistungsaufnahme der Vorrichtung geben Aufschluß über die durchgeführten Operationen, die Rückschlüsse auf die Operanden zulassen. Mit Hilfe des Programmcodes ist der Angreifer dann in der Lage, Teile der verwendeten Zahlen und Daten zu entschlüsseln.A possible attack against a device is the so-called power attack. at During this attack, the attacker tries to gain knowledge of the secret, especially of the obtain a private key by choosing power and / or power consumption records the calculation of a signature or the encryption or decryption. The current and / or power consumption of the device provide information about the performed operations that allow conclusions to be drawn about the operands. With help of the program code, the attacker is then able to parts of the numbers used and decrypt data.

Als Gegenmaßnahme zur Abwehr dieser Power-Attacken wurde vorgeschlagen, einen Programmcode zu verwenden, der zufällige und nicht zur Berechnung notwendige Be fehle ausführt. So können beispielsweise mehrfache Sprungbefehle auftreten, die un abhängig von den geheim zu haltenden Werten die relevanten Befehle verschleiern, so daß die bei einer Power-Attack gemessenen Signale keine Information über die ge heimzuhaltenden Größen liefern. Nachteilig an diesem Verfahren ist jedoch, daß hier durch die Berechnung verlangsamt wird. Für eine akzeptable Antwortzeit des Systems müssen also kürzere Schlüssel verwendet werden, so daß hierdurch die Sicherheit vermindert wird.As a countermeasure to ward off these power attacks, one was suggested To use program code, the random and not necessary for the calculation lack executes. For example, multiple jump commands can occur that un depending on the values to be kept secret, disguise the relevant commands, so that the signals measured during a power attack have no information about the ge deliver sizes to be kept. A disadvantage of this method, however, is that here is slowed down by the calculation. For an acceptable system response time So shorter keys must be used, so that security is reduced.

Soll die Verwendung von kurzen Schlüsseln vermieden werden, so ist aus US-Patent US 5,999,627 ein schnelles Verfahren zum Exponentieren für cryptographische Ver fahren mit öffentlichen Schlüsseln bekannt. Bei diesem Verfahren werden Werte vor berechnet und in einem Speicher abgelegt. Das Ergebnis ergibt sich durch ein Berech nen von Produkten der im Speicher abgelegten Werte. Umgesetzt wird das Verfahren, indem beginnend mit einem Startwert, abwechselnd dieser Wert mit einem vorberech neten Wert multipliziert und anschließend der so erhaltene Wert quadriert wird. Um das Verfahren möglichst effizient ablaufen zu lassen, wird im Verfahren nach US 5,999,627 möglichst häufig mit dem neutralen Element multipliziert, da solche Ope rationen nicht durchgeführt werden müssen.From the US patent is to be avoided the use of short keys US 5,999,627 a fast exponentiation method for cryptographic ver drive with public keys known. With this procedure values are given calculated and stored in a memory. The result is calculated products of the values stored in the memory. The procedure is implemented by starting with a starting value, alternating this value with a precalculation multiplied neten value and then squared the value thus obtained. Around The process according to US Pat. No. 5,999,627 allows the process to run as efficiently as possible multiplied as often as possible with the neutral element, since such ope rations do not have to be carried out.

Eine Übertragung des Verfahrens auf elliptische Kurven ist möglich, dabei ersetzt die Addition von Punkten die Multiplikation beim Verfahren nach US 5,999,627. Jedoch sind die Algorithmen für Verdopplung bzw. Addition zweier Punkte auf einer ellipti schen Kurve so unterschiedlich, dass aus Power Attack Messungen geschlossen wer den kann, ob addiert oder verdoppelt wurde. Dadurch wird der geheimzuhaltende skalare Multiplikator in Teilen für den Angreifer zugänglich. Eine Abschätzung ergibt, daß bei der Verwendung des Verfahrens nach US 5,999,627 ungefähr 25% der Binär stellen der geheimzuhaltenden Zahl durch eine einzige Power-Attack zugänglich ist. Der Geschwindigkeitsvorteil der sich aus der möglichst häufigen Addition mit dem neutralen Element ergibt, wird somit zu einem wesentlichen Sicherheitsproblem.A transfer of the method to elliptic curves is possible, replacing the Addition of points the multiplication in the method according to US 5,999,627. however are the algorithms for doubling or adding two points on an ellipti curve so different that power attack measurements can be concluded that can be added or doubled. This will keep the secret scalar multiplier partially accessible to the attacker. An estimate shows that using the method according to US 5,999,627 approximately 25% of the binary make the number to be kept secret accessible by a single power attack. The speed advantage resulting from the most frequent addition with the neutral element, becomes a major security problem.

Aus EP 0 874 307 ist ein Verfahren zur beschleunigten Multiplikation eines Punktes einer elliptischen Kurve mit einer natürlichen Zahl k bekannt. Hierbei wird die Zahl k als Binärvektor in einem Register gespeichert. Abhängig davon, ob eine Binärstelle den Wert Null oder Eins aufweist, werden die Koordinaten des Punktes P addiert oder multipliziert. Bei dem Einsatz für cryptographische Verfahren ist hierbei nachteilig, daß abhängig von den geheimzuhaltenden Zahlen bei der Berechnung verzweigt wird, so daß diese für einen Angreifer zugänglich ist. EP 0 874 307 describes a method for the accelerated multiplication of a point an elliptic curve with a natural number k is known. Here the number k stored as a binary vector in a register. Depending on whether a binary digit has the value zero or one, the coordinates of the point P are added or multiplied. When used for cryptographic processes, it is disadvantageous here that depending on the numbers to be kept secret, the calculation branches, so that it is accessible to an attacker.

Aus EP 1 014 617 ist ein Verfahren zur Berechnung eines Skalarprodukts auf einer el liptischen Kurve bekannt. Auch bei diesem Verfahren wird in Abhängigkeit der Bi närdarstellung eines Multiplikators verzweigt, so daß auch dieses Verfahren keine si chere Berechnung mit geheimzuhaltenden Größen erlaubt.EP 1 014 617 describes a method for calculating a dot product on an el known liptic curve. Depending on the Bi närdarstellung a multiplier branches, so that this method no si Calculation with sizes to be kept secret allowed.

Der Erfindung liegt die Aufgabe zugrunde ein Verfahren bereitzustellen, das eine schnelle und sichere Berechnung von geheimzuhaltenden Größen erlaubt.The invention has for its object to provide a method that fast and safe calculation of sizes to be kept secret allowed.

Die erfindungsgemäße Aufgabe wird durch ein Verfahren zur Berechnung eines digi talen Signalwertes für ein cryptographisches Verfahren mit Hilfe eines elektronischen Rechners gelöst. Das erfindungsgemäße Verfahren ist bei der Verwendung von digi talen Größen B von Vorteil, die sich als Punkte einer elliptischen Kurve über einem endlichen Körper darstellen lassen. Das Verfahren berechnet die Größe rB, also das skalare Produkt aus einem Basispunkt B und einer natürlichen Zahl r, bei einer da tenunabhängigen Strom- und/oder Leistungsaufnahme. Der Programmablauf kann so mit als execution invariant angesehen werden, denn die Reihenfolge der einzelnen ablaufenden Schritte hängt nicht von den geheimzuhaltenden Daten ab. Hierbei sei (_n-1, _n-2, . . ., ₀) die Binärdarstellung der natürlichen Zahl r mit einer Bitlänge n. Ferner sei h eine natürliche Zahl mit 1 ≦ h < n, bevorzugt eine kleine Zahl zwischen 2 und 8. Es sei a die kleinste natürliche Zahl mit ha ≦ n, wobei durch Auffüllen von r mit führenden Nullen erreicht wird, daß ha = n ist. The object of the invention is achieved by a method for calculating a digital signal value for a cryptographic method using an electronic computer. The method according to the invention is advantageous when using digital variables B, which can be represented as points of an elliptic curve over a finite field. The method calculates the quantity rB, i.e. the scalar product from a base point B and a natural number r, with a data-independent current and / or power consumption. The program sequence can thus be regarded as execution invariant, because the sequence of the individual steps does not depend on the data to be kept secret. Let ( _n-1 , _n-2 ,..., ₀ ) be the binary representation of the natural number r with a bit length n. Furthermore, let h be a natural number with 1 ≦ h <n, preferably a small number between 2 and 8. Let a be the smallest natural number with ha ≦ n, whereby by filling r with leading zeros it is achieved that ha = n.

In einem ersten Verfahrensschritt werden 2^h-Werte vorberechnet und in einem Feld C [f] in einem Speicher abgespeichert. Hierbei sei (_h-1, _h-2, . . ., ₀) die Binärdarstel lung von f. Die vorberechneten Werte des Feldes C[f] werden alle Werte von f mit 0 ≦ f < 2^h berechnet:
In a first process step, 2 ^h values are precalculated and stored in a field C [f] in a memory. Let ( _h-1 , _h-2 ,..., ₀ ) be the binary representation of f. The precalculated values of the field C [f] all values of f with 0 ≦ f <2 ^{h are} calculated:

Hierbei steht "⊕" für die Gruppenaddition der Punkte auf der elliptischen Kurve.Here "⊕" stands for the group addition of the points on the elliptic curve.

In einem zweiten Verfahrensschritt werden a-Werte g_j mit 0 ≦ j < a berechnet:
In a second process step, a values g _{j are} calculated with 0 ≦ j <a:

Beim dritten Verfahrensschritt wird die Größe D berechnet:
In the third process step, size D is calculated:

Die zu berechnende Größe rB ergibt sich zu
The size rB to be calculated is given by

Aus der Definition des Feldes C wird deutlich, daß das Gruppenelement B stets unab hängig von den Werten f hinzu addiert wird. Die Addition des Elements B zu jedem Wert in dem Feld C bewirkt, daß bei Ausführung des Produkts rB zusätzlich der Wert D addiert wird, der nachfolgend wieder subtrahiert werden muß. Für die Subtraktion des Wertes D, also für die Addition des inversen Elements von D, steht das Zeichen "⊖". Indem stets das Element B hinzu addiert ist, wird im Laufe der Berechnung beim Zugriff auf das Feld C niemals das neutrale Element verwendet. Das vorgestellte Ver fahren ist somit vor der oben beschriebenen Power-Attack sicher, denn aus der immer gleichen Reihenfolge von Addition und Verdoppelung kann nicht auf den geheimzu haltenden Zahlenwert geschlossen werden. Selbstverständlich kann das erfindungsge mäße Verfahren auch mit Elementen anderer kommutativer Gruppen, bevorzugt auch mit hyperelliptischen Kurven, durchgeführt werden.From the definition of the field C it is clear that the group element B is always independent depending on the values f is added. The addition of element B to each Value in field C causes the value to be added when the product rB is executed D is added, which must then be subtracted again. For subtraction of the value D, i.e. for the addition of the inverse element of D, is the sign "⊖". Since element B is always added, in the course of the calculation at Access to field C never uses the neutral element. The presented ver driving is therefore safe from the power attack described above, because of the always same order of addition and duplication cannot be secret holding numerical value can be closed. Of course, the fiction moderate method also with elements of other commutative groups, preferably also with hyperelliptic curves.

Wird das erfindungsgemäße Verfahren auf einer Smart-Card implementiert, so ent steht eine gegen Power-Attacks sichere Vorrichtung, die beispielsweise für digitale Signaturen verwendet werden kann.If the method according to the invention is implemented on a smart card, ent is a device that is secure against power attacks, for example for digital Signatures can be used.

Ein weiterer besonderer Vorteil des erfindungsgemäßen Verfahrens liegt darin, daß sich die Berechnung der Größe Z = rB in einfacher Weise durch folgende Schleife realisieren läßt:
Z = C[g_a-1];
for (j = a - 2; j < = 1; j--)
{
Z = Z ⊕ Z;
Z = Z ⊕ C[g_j];
}
Z = Z ⊕ Z;
Z = Z ⊖ D;
Z = Z ⊕ C [g₀].Another particular advantage of the method according to the invention is that the calculation of the variable Z = rB can be carried out in a simple manner using the following loop:
Z = C [g _a-1 ];
for (j = a - 2; j <= 1; j--)
{
Z = Z ⊕ Z;
Z = Z ⊕ C [g _j ];
}
Z = Z ⊕ Z;
Z = Z ⊖ D;
Z = Z ⊕ C [g ₀ ].

Zusammenfassend verdeutlicht auch der vorstehende Pseudocode die wichtigsten Aspekte des Zusammenspiels:
In summary, the above pseudocode also clarifies the most important aspects of the interaction:

- The calculation of the values g [i] must not go outside. At the hardware level this is implemented by means of a protection against eavesdropping on the data bus, the software under supports it through "execution invariant" programming, like the above pseu docode shows with its alternating addition and doubling.
- Both addition and doubling must not be included in advance or in the after correlate with modular computing operations to be determined. this will realized by the method according to the invention in that r is chosen at random.
- From a single elementary operation (especially modular multiplication tion) may not be deduced from any of the operands used. This must be ensured by the hardware and is a basic requirement for the secure use of a cryptographic procedure.

Da ein Angriff recht unproblematisch möglich ist, falls der Datenbus abgehört werden kann, kommen als geeignete Mikrokontroller nur solche in Frage, bei denen der Da tenbus nur innerhalb des Chips zugänglich ist; im wesentlichen handelt es sich dabei um die Smartcardprozessoren. Des weiteren ist aus Sicherheits- und Geschwindig keitsgründen ein cryptographischer Koprozessor sinnvoll, der die modulare Arithmetik durchführt. Es ist allerdings durchaus möglich, solche Prozessoren mit gleichen Si cherheitsvorkehrungen auch außerhalb von Smartcards zu verwenden.Since an attack is possible without any problems if the data bus is intercepted can be considered suitable microcontrollers only those in which the Da tenbus is only accessible within the chip; essentially it is around the smart card processors. Furthermore is from security and speed a cryptographic coprocessor, which does the modular arithmetic performs. However, it is quite possible to use such processors with the same Si security precautions can also be used outside of smart cards.

Nachfolgend wird ein cryptographisches Verfahren mit öffentlichen Schlüsseln basie rend auf elliptischen Kurven erläutert: Beiden Benutzern A und B ist eine elliptische Kurve E und ein Basispunkt F auf dieser Kurve bekannt. Um einen geheimen Schlüs sel zu erzeugen, wählt ein Benutzer A eine natürliche Zahl v zufällig aus, wobei v groß ist. Der Benutzer A berechnet vF Element aus E. Das Ergebnis vF wird bekannt gemacht, während die Zahl v geheimgehalten wird. Ein zweiter Benutzer B wählt ein zufälliges w und veröffentlicht das Ergebnis wF Element aus E. Beide Benutzer sind in der Lage, einen geheimen Schlüssel P = vwF Element E zu berechnen, denn v(wF) = w(vF). Da v und w geheimgehalten werden, müßte ein Angreifer aus vF und wF die Zahlen v und/oder w berechnen. Dies wird als das Problem des sogenannten diskreten Logarithmus bezeichnet und gilt als sehr schwierig zu lösen. Durch den Schutz der Smart-Card vor Power-Attacks wird die Berechnung der Produkte vF und vwF vor Angriffen geschützt. Da nun A und B ein gemeinsamer Schlüssel bekannt ist, können verschlüsselte Daten ausgetauscht werden.The following is a cryptographic procedure using public keys explained on elliptic curves: Both users A and B is an elliptical Curve E and a base point F are known on this curve. For a secret key to generate sel, user A randomly selects a natural number v, where v is great. User A calculates vF element from E. The result vF becomes known made while keeping the number v secret. A second user B dials in random w and publish the result wF element from E. Both users are able to calculate a secret key P = vwF element E, because v (wF) = w (vF). Since v and w are kept secret, an attacker from vF and wF would have to Calculate numbers v and / or w. This is called the problem of the so-called discrete Logarithm denotes and is considered to be very difficult to solve. By protecting the Smart card before power attacks will calculate the products vF and vwF before Attacks protected. Now that A and B have a common key, you can encrypted data are exchanged.

Für die Signatur kommt üblicherweise ein mit "ECDSA" bezeichnetes Verfahren zum Einsatz:
Es sei p eine Primzahl, die elliptische Kurve sei über GF(p) definiert;
n sei die Ordnung der vom Basispunkt der elliptischen Kurve erzeugten Untergruppe (für cryptographische Anwendungen werden meist elliptische Kurven verwendet, die nur eine nichttriviale Untergruppe haben. In diesen Fällen ist n gleich der Anzahl der Elemente der elliptischen Kurve und hat damit bis auf max. eine Stelle Differenz die gleiche Bitlänge wie p, vgl. Theorem von Hasse-Weil);
d sei der private Schlüssel.A procedure called "ECDSA" is usually used for the signature:
Let p be a prime number, the elliptic curve is defined by GF (p);
n be the order of the subgroup generated by the base point of the elliptic curve (for cryptographic applications mostly elliptical curves are used which only have a non-trivial subgroup. In these cases n is equal to the number of elements of the elliptical curve and thus has up to a maximum of one Make difference the same bit length as p, see Theorem von Hasse-Weil);
d is the private key.

Das Verfahren besitzt die folgenden Schritte:
The process has the following steps:

1. Determine the hash value m of a message to be signed,
2. determine k as a random number with 1 <k <n - 1,
3. Determine x and y coordinates (x, y) of G = kB, where B is the Ba as before sis point is
4. r = x mod n and
5. s = (m + dr) / k mod n, where the signature consists of the pair (r, s).

Zum Entschlüsseln wird der öffentliche Punkt Q = dB benötigt. Im wesentlichen ist die Gleichung
(x, y) = ((m/s)P + (r/s)Q) (die skalaren Operationen (m/s und r/s) sind mod n zu ver stehen).The public point Q = dB is required for decoding. Essentially, the equation
(x, y) = ((m / s) P + (r / s) Q) (the scalar operations (m / s and r / s) are to be understood as mod n).

Die Signatur ist korrekt, falls x = r mod n ist.The signature is correct if x = r mod n.

Das erfindungsgemäße Verfahren kommt in Schritt 3 zum Einsatz.The method according to the invention is used in step 3.

Ein Beispiel dient zur Verdeutlichung des Verfahrens mit kleinen Zahlen:
h = 3
n = 17
==< a = 6 (und ah = 18)An example serves to illustrate the procedure with small numbers:
h = 3
n = 17
== <a = 6 (and ah = 18)

Im Feld C stehen die Werte
C[0] = B
C[1] = 2B
C[2] = (2^6 + 1)B = 65B
C[3] = (2^6 + 2)B = 66B
C[4] = (2^12 + 1)B = 4097B
C[5] = (2^12 + 2)B = 4098B
C[6] = (2^12 + 2^6 + 1)B = 4161B
C[7] = (2^12 + 2^6 + 2)B = 4162B
D berechnet sich zu
D = (2^6 - 1) = 63BThe values are in field C.
C [0] = B
C [1] = 2B
C [2] = (2 ^ 6 + 1) B = 65B
C [3] = (2 ^ 6 + 2) B = 66B
C [4] = (2 ^ 12 + 1) B = 4097B
C [5] = (2 ^ 12 + 2) B = 4098B
C [6] = (2 ^ 12 + 2 ^ 6 + 1) B = 4161B
C [7] = (2 ^ 12 + 2 ^ 6 + 2) B = 4162B
D calculates itself
D = (2 ^ 6 - 1) = 63B

Der (zufällige) Multiplikator r in Binärdarstellung (original mit 17 Bit):
The (random) multiplier r in binary representation (original with 17 bit):

r = 01110010101100111
r = 01110010101100111

ergänzt mit führenden Nullen (ah Bitstellen)
supplemented with leading zeros (ah bit positions)

r = 001110000101100111 = 001110 000101 100111 = 14.2^12 + 5.2^6 + 39 = 57344 + 320 + 39 = 57703
r = 001110000101100111 = 001110 000101 100111 = 14.2 ^ 12 + 5.2 ^ 6 + 39 = 57344 + 320 + 39 = 57703

r wird in 3 Gruppen aufgeteilt, die die g[i] ergeben, wobei jeweils die (i + 1)-ten Stellen der drei Blöcke zusammen die 3 Bit der g[i] ergeben:
001 ==< g[5] = 1
000 ==< g[4] = 0
100 ==< g[3] = 4
111 ==< g[2] = 7
101 ==< g[1] = 5
011 ==< g[0] = 3r is divided into 3 groups, which give the g [i], whereby the (i + 1) th positions of the three blocks together give the 3 bits of the g [i]:
001 == <g [5] = 1
000 == <g [4] = 0
100 == <g [3] = 4
111 == <g [2] = 7
101 == <g [1] = 5
011 == <g [0] = 3

Der Rechenablauf ergibt nun die Zwischenschritte:
The calculation process now shows the intermediate steps:

Z: = C[1] = 2B
Z: = C [1] = 2B

Z: = Z + Z = 4B
Z: = Z + C[0] = 4B + B = 5B
Z: = Z + Z = 4B
Z: = Z + C [0] = 4B + B = 5B

Z: = Z + Z = 10B
Z: = Z + C[4] = 10B + 4097B = 4107B
Z: = Z + Z = 10B
Z: = Z + C [4] = 10B + 4097B = 4107B

Z: = Z + Z = 8214B
Z: = Z + C[7] = 8214B + 4162B = 12376B
Z: = Z + Z = 8214B
Z: = Z + C [7] = 8214B + 4162B = 12376B

Z: = Z + Z = 24752
Z: = Z + C[5] = 24752B + 4098B = 28850B
Z: = Z + Z = 24752
Z: = Z + C [5] = 24752B + 4098B = 28850B

Z: = Z + Z = 57700B
Z: = Z + Z = 57700B

Z: = Z - D = 57700B - 63B = 57637B
Z: = Z - D = 57700B - 63B = 57637B

Z: = Z + C[3] = 57638B + 66B = 57703BZ: = Z + C [3] = 57638B + 66B = 57703B

Damit das Verfahren ordnungsgemäß ablaufen kann, ist an r eine Bedingung zu stel len:
Es darf nicht gleichzeitig g[a - 1] = 0 und g[a - 2] = 1 sein, denn dann würde bei der ersten Addition 2B zu 2B addiert. In order for the procedure to run properly, a condition must be placed on r:
It must not be g [a - 1] = 0 and g [a - 2] = 1 at the same time, because then the first addition would add 2B to 2B.

Eine Vorrichtung zur Durchführung des Verfahrens besitzt eine zentrale Prozessorein heit, einen Speicher, eine Datenausgabe sowie elektrische Kontakte zum Anlegen ei ner Versorgungsspannung. Die Prozessoreinheit lädt ansprechend auf ein Startsignal zwei binäre Signalfolgen sowie ein Programm zur Berechnung des digitalen Signal werts aus den zwei Bitfolgen in die Prozessoreinheit und führt das geladene Programm zur Berechnung von K aus derart, daß von außen lediglich ein im wesentlichen von den geheimzuhaltenden Daten unabhängiger Wert für die Strom- und Leistungsauf nahme feststellbar ist. Es wird mit dem erfindungsgemäßen Verfahren erreicht, daß die Stromaufnahme während der relevanten Berechnungen, also insbesondere Addition und Verdoppelung von Punkten auf der elliptischen Kurve, keine Korrelation zu dem geheimzuhaltenden skalaren Faktor aufweist. Durch das Zusammenspiel von Prozes soreinheit und geladenem Programm während der Berechnung mit dem geheimzuhal tenden Wert bleiben die in der Prozessoreinheit ablaufenden Befehlsfolgen mit ihren Daten von außen verborgen.A device for performing the method has a central processor unit, a memory, a data output and electrical contacts for creating an egg ner supply voltage. The processor unit loads in response to a start signal two binary signal sequences and a program for calculating the digital signal value from the two bit sequences into the processor unit and executes the loaded program for calculating K from such that from the outside only a substantially of the data to be kept secret independent value for the current and power consumption acceptance is noticeable. It is achieved with the inventive method that the Current consumption during the relevant calculations, in particular addition and doubling points on the elliptic curve, no correlation to that has to be kept secret scalar factor. Through the interplay of processes sor unit and loaded program during the calculation with the secret key tending value remain the instruction sequences running in the processor unit with their Data hidden from the outside.

In einer möglichen Ausgestaltung sind zentrale Prozessoreinheit und Speicher in einen einzigen Chip integriert. Die gesamte Vorrichtung kann als eine Smart-Card ausge führt, die über externe Kontakte mit Spannung versorgt wird. Für gewöhnlich besitzt eine Smart-Card einen 8-Bit-Mikroprozessor, der mit ungefähr 1280 Byte RAM und ungefähr 32 kByte ROM und entweder mit einem EPROM oder einem EEPROM und mit einer Crypto engine zur schnellen Berechnung von modulo-Multiplikationen aus geführt ist. Selbstverständlich können Smart-Cards auch mit anderen Kapazitäten verwendet werden. Die Stromversorgung der Smart-Card erfolgt über das Einstecken in das Lesegerät. Die geheime Berechnung von digitalen Größen ist bei Smart-Cards von besonderer Bedeutung, denn in der Regel unterliegen die Lesegeräte nicht der Kontrolle des Kartenbesitzers und können daher von Dritten für Angriffe genutzt wer den, wobei die Power-Attack als zerstörungsfreier Angriff auf die Karte zudem belie big oft wiederholt werden kann.In one possible embodiment, the central processor unit and memory are in one integrated single chip. The entire device can be made out as a smart card leads, which is supplied with voltage via external contacts. Usually owns a smart card has an 8-bit microprocessor that has approximately 1280 bytes of RAM and about 32 kByte ROM and either with an EPROM or an EEPROM and with a crypto engine for fast calculation of modulo multiplications is led. Of course, smart cards can also have other capacities be used. The smart card is supplied with power by plugging it in into the reader. The secret calculation of digital sizes is with smart cards of particular importance, because the readers are usually not subject to the Control of the cardholder and can therefore be used by third parties for attacks the power attack as a non-destructive attack on the card big can be repeated many times.

Im Speicher der Smart-Card sind ein oder mehrere Programme zur Ver- oder Ent schlüsselung von digitalen Daten und/oder zum Signieren digitaler Daten nach einem oder mehreren cryptographischen Verfahren abgelegt, die auf Daten in dem Speicher zugreifen. Das geladene Programm führt die skalare Multiplikation eines Punktes ei ner elliptischen Kurve mit einer natürlichen Zahl aus.The smart card memory contains one or more programs for locking or unlocking encryption of digital data and / or for signing digital data according to a or several cryptographic methods based on data stored in memory access. The loaded program performs the scalar multiplication of a point an elliptic curve with a natural number.

Claims

1. Method for calculating a scalar product from a natural number r and a point B of an elliptic curve for a cryptographic application, in which the scalar product is calculated by an electronic computer with a processor with essentially data-independent current and / or power consumption of the processor, characterized by the following process steps:

- let ( _n-1 , _n-2 ,..., ₀ ) be the binary representation of the natural number r, let h be a natural number with 1 ≦ h <n and let a be a natural number with ha = n, where r is filled with leading zeros,
- In a first method step, a total of 2 ^h values are calculated and stored in a field C [f], where ( _h-1 , _h-2 ,..., ₀ ) is the binary representation of f and the values of the field C [f] can be calculated for all values of f with 0 ≦ f <2 ^h :
- In a second process step, a-quantities g _j with 0 ≦ j <a are calculated with the following values:
- In a third method step, an element D is calculated:
- In a fourth process step, the scalar product rB to be calculated for the cryptographic process is obtained

2. The method according to claim 1, characterized in that the method on a Microprocessor of a smart card expires.