Zahlentheoretische Grundlagen der Kryptografie

Elliptische Kurven - Implementierung

Im Folgenden sind die Programme zusammengefasst, die für die Implementierung von Rechenoperationen auf elliptischen Kurven über einem endlichen Körper ℤ_n erforderlich sind.

Die Klasse ModInt repräsentiert Elemente des Körpers ℤ_n und stellt die erforderlichen Operationen für die Grundrechenarten zur Verfügung. Dies geschieht, indem die Operatoren überschrieben werden, etwa der Operator + durch die Methode __add__. Für die Funktion rec (reciprocal - Kehrwert) wird die Funktion modinverse zur Berechnung des multiplikativ inversen Elements modulo n importiert.

Der Wert von n wird als Klassenattribut (statisches Attribut) ModInt.n gespeichert.

ModInt.py

# repraesentiert ein Element von Zn (dem Koerper der Zahlen modulo n)
# und stellt die Grundrechenoperationen zur Verfuegung
class ModInt(object):

    # Modul n (n Primzahl) ist Klassenattribut (statisches Attribut),
    # muss vor Beginn der Berechnungen gesetzt werden
    # z.B. ModInt.n=23

    def __init__(self, i):
        self.i=i % ModInt.n

    # Addition
    def __add__(self, other):
        return ModInt(self.i+other.i)

    # additiv inverses Element
    def __neg__(self):
        return ModInt(-self.i)

    # Subtraktion
    def __sub__(self, other):
        return self+(-other)

    # Multiplikation
    def __mul__(self, other):
        return ModInt(self.i*other.i)

    # multiplikativ inverses (reziprokes) Element
    def rec(self):
        return ModInt(modinverse(self.i, ModInt.n))

    # Division
    def __div__(self, other):
        return self*other.rec()

    # Exponentiation, k Integer-Zahl
    def __pow__(self, k):
        if k==0:
            return ModInt(1)
        if k%2==1:    # k ungerade
            return self*self**(k-1)
        else:
            return (self*self)**(k//2)

    # Gleichheit
    def __eq__(self, other):
        return self.i==other.i

    # Umwandlung in String
    def __str__(self):
        return str(self.i)


# --------- Test -------------
if __name__=="__main__":

    def assertion(k, r):
        assert str(k)==str(r)

    # Zahlen und Berechnungen modulo n=7:
    ModInt.n=7    # n ist Klassenattribut (statisches Attribut)
    s=ModInt(2)
    t=ModInt(13)

    assertion(s, 2)
    assertion(t, 6)
    assertion(s+t, 1)
    assertion(s*t, 5)
    assertion(s-t, 3)
    assertion(s/t, 5)
    assertion(s**999, 1)
    assertion(s*t, s/t)
    print("Ok")

Die Klasse EcPoint repräsentiert einen Punkt einer elliptischen Kurve und stellt Methoden für die Verknüpfung von Punkten zur Verfügung (__mul__ für den Operator * und __pow__ für den Operator **).

Der Parameter a der elliptischen Kurve wird in einem Klassenattribut (statisches Attribut) EcPoint.a gespeichert. Der Parameter b wird hier nicht benötigt.

Im anschließenden Test wird zunächst im Körper ℝ der reellen Zahlen gerechnet. Anschließend wird dieselbe Berechnung im Körper ℤ₂₃ durchgeführt.

EcPoint.py

# repraesentiert einen Punkt auf einer elliptischen Kurve
class EcPoint(object):

    # der Parameter a der elliptischen Kurve ist
    # Klassenattribut (statisches Attribut), muss vor
    # der Berechnung mit einem Wert versehen werden,
    # z.B. EcPoint.a=-2.0

    # x und y sind die Koordinaten
    # u==True stellt den unendlich fernen Punkt dar
    def __init__(self, x, y, u=False):
        self.x=x
        self.y=y
        self.u=u

    # liefert True, wenn self der unendlich ferne Punkt ist
    def isInfinity(self):
        return self.u

    # liefert den unendlich fernen Punkt
    @staticmethod
    def infinity():
        return EcPoint(None, None, True)

    # verknuepft die Punkte p=self und q=other
    # Koordinaten xp und yp sind self.x und self.y
    # Koordinaten xq und yq sind other.x und other.y
    def __mul__(self, other):
        if self.isInfinity():    # self = unendlich ferner Punkt
            return other
        if other.isInfinity():   # other = unendlich ferner Punkt
            return self
        if self.x==other.x and self.y==-other.y:  # Punkte sind gespiegelt
            return EcPoint.infinity()
        if self.x==other.x and self.y==other.y:   # Punkte sind gleich
            s=self.x*self.x
            m=(s+s+s+EcPoint.a)/(self.y+self.y)   # (3xp^2+a)/2yp (Steigung der Tangente)
        else:
            m=(self.y-other.y)/(self.x-other.x)   # Steigungsdreieck (yp-yq)/(xp-xq)
        xr=m*m-self.x-other.x            # m^2 - xp - xq
        yr=m*(self.x-xr)-self.y          # m(xp-xr) - yp
        return EcPoint(xr, yr)

    # berechnet self**k
    # d.h. verknuepft den Punkt self k-mal mit sich selbst
    # schnelle Exponentiation mit square-and-multiply
    def __pow__(self, k):
        if k==0:
            return EcPoint.infinity()
        elif k%2==1:
            return self*self**(k-1)    # ** rekursiv
        else:
            return (self*self)**(k//2) # ** rekursiv

    def __str__(self):
        if self.isInfinity():
            return "infinity"
        else:
            return str(self.x)+" "+str(self.y)

# Test
if __name__=="__main__":
    # --------------------------------
    # Koerper festlegen: reelle Zahlen
    # Parameter a der elliptischen Kurve festlegen:
    EcPoint.a=-2.0
    # Punkt p festlegen:
    p=EcPoint(2.0, 2.0)

    # Test: p**9 berechnen:
    q=EcPoint.infinity()
    for i in range(9):
        q=q*p
        print(i+1, q)

    print(" ", p**9)
    print()

    # --------------------------------
    # Koerper festlegen: Koerper Z_23
    from ModInt import *
    ModInt.n=23
    # Parameter a der elliptischen Kurve festlegen:
    EcPoint.a=ModInt(-2)
    # Punkt p festlegen:
    p=EcPoint(ModInt(2), ModInt(2))

    # Test: p**9 berechnen:
    q=EcPoint.infinity()
    for i in range(9):
        q=q*p
        print(i+1, q)

    print(" ", p**9)
    print()

Für die Implementierung der Diffie-Hellman-Schlüsselvereinbarung legen wir eine Standard-Elliptische-Kurve E zugrunde und auf dieser einen Standard-Punkt p. Die Funktion standardPoint liefert den Standard-Punkt p, zugleich legt sie den Modul n des Körpers ℤ_n sowie den Parameter a der elliptischen Kurve E fest.

    def standardPoint():
        ModInt.n=1332297598440044874827085558802491743757193798159
        EcPoint.a=ModInt(297190522446607939568481567949428902921613329152)
        x=1089473557631435284577962539738532515920566082499
        y=127912481829969033206777085249718746721365418785
        return EcPoint(ModInt(x), ModInt(y))

Um die Methode standardPoint zu testen, benutzen wir wieder ein ähnliches Programm wie oben:

    # Standard-Punkt p auf der Standard-Elliptischen-Kurve
    p=standardPoint()

    # Test: p**9 berechnen:
    q=EcPoint.infinity()
    for i in range(9):
        q=q*p
        print(i+1, q)

    print(" ", p**9)
    print()

Weiter mit: [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 10.03.2011 Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden

Zahlentheoretische Grundlagen der Kryptografie

Elliptische Kurven - Implementierung

Klasse ModInt

Klasse EcPoint

Standard-Punkt auf Standard-Kurve