Browse Prior Art Database

Aufwandsangleichung der Addition von Punkten auf elliptischen Kurven der Charakteristik p, p prim, p>3

IP.com Disclosure Number: IPCOM000178303D
Original Publication Date: 2009-Feb-13
Included in the Prior Art Database: 2009-Feb-13
Document File: 4 page(s) / 35K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

Heutzutage werden bei der Verschluesselung von Daten verschiedene kryptographische Verfahren angewendet. Zum Beispiel werden bei kryptographischen Verfahren auf Basis elliptischer Kurven kryptographische Schluessel bitweise verarbeitet. Dabei wird bei einem Bitwert gleich null eine Punktverdoppelung vorgenommen, bei einem Bitwert von eins erfolgt eine Punktverdopplung mit sofortiger nachfolgender Addition zweier verschiedener Punkte. Diese Verfahren sind auch bekannt als Double-and-Add-Algorithmus.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 4

Aufwandsangleichung der Addition von Punkten auf elliptischen Kurven der Charakteristik p, p prim, p>3

Idee: Dr. Erwin Hess, DE-Muenchen; Dr. Jean Georgiades, DE-Muenchen

Heutzutage werden bei der Verschluesselung von Daten verschiedene kryptographische Verfahren

angewendet. Zum Beispiel werden bei kryptographischen Verfahren auf Basis elliptischer Kurven

kryptographische Schluessel bitweise verarbeitet. Dabei wird bei einem Bitwert gleich null eine

Punktverdoppelung vorgenommen, bei einem Bitwert von eins erfolgt eine Punktverdopplung mit

sofortiger nachfolgender Addition zweier verschiedener Punkte. Diese Verfahren sind auch bekannt

als Double-and-Add-Algorithmus.

Das zu loesende Problem besteht darin, dass durch geeignete Strommessungen gelesen werden

kann, ob nur eine Verdopplung oder eine Verdopplung plus Addition stattgefunden hat. Somit sind die

kryptographischen Verfahren auf Basis elliptischer Kurven nicht sicher vor Angriffen. Diese

Strommessverfahren sind Simple Power Analysis (SPA) oder der Timing-Attack.

Im Folgenden wird vorgeschlagen, dass die Formeln zur Addition von Punkten bei Kryptoalgorithmen,

die auf der Basis elliptischer Kurven operieren, so umschrieben werden, dass der Aufwand an

arithmetischen Operationen gleich bleibt, egal ob die zu addierenden Punkte P1 und P2 (siehe

Formeln zu 4.) identisch oder von einander verschieden sind. Die entsprechenden Formeln, ausser

die der weiter unten abgebildeten projektiven Darstellung von mod p mit p>3, entstammen dem Buch

"Elliptic Curve Public Key Cryptosystems" von Alfred J. Menezes:
1. Affine Koordination fuer p = 2 (Seite 22)
1.1 j(E) ≠ 0
1.1.1 P1 ≠ P2
Die benoetigten Operationen zur Berechnung von x3 und y3 sind:
A = y1 + y2
B = x1 + x2
C = A/B
D = C*C
x3 = D + C + B a2
E = x1 + x3
C = A/B (nochmals)

F = C*E
y3 = F + x3 + y1
Die arithmetischen Operationen sind in Summe: acht Additionen, zwei Multiplikationen, zwei

Divisionen.

1.1.2 P1 = P2
A = x1*x1
B = a6/A
C = y1/x1
D = x1 + C + B + B
x3 = A + B
y3 = A + D*x3 + A + x3 + A
Die arithmetischen Operationen sind ebenfalls in Summe: acht Additionen, zwei Multiplikationen, zwei

Divisionen.

© SIEMENS AG 2009 file: 2008J24696.rtf page: 1

[This page contains 2 pictures or other non-text objects]

Page 2 of 4

1.2 j(E) = 0, Precomputation: k beliebig, r = 1/k
1.2.1 P1 ≠ P2
A = y1 + y2
B = x1 + x2
C = A/B
D = C*k*C*r
x3 = D + B
y3 = C*(x1 + x3) + y1 + a3
Die arithmetischen Operationen sind in Summe: sechs Additionen, vier Multiplikationen, eine Division.

1.2.2 P1 = P2
A = x1*x1
B = A + k + a4 + k
C = B/a3
x3 = C*C
y3 = C*x1 + C*x3 + y1 + a3
Die arithmetischen Operationen sind in Summe: sechs Additionen, vier Multiplikationen, eine Division.

2. Affine Koordination fuer p>3 Precomputation: k = 3-1 mod p

x3 = s² - x1 - x2
y3 = s + (x1 - x3) - y1
mit s = 3*k*(y2 - y1)/(x2 - x1) fuer P1 ≠ P2
und s = (3*x1*x1 + a)/(y1 + y1) fuer P1 =...