Zahlentheoretische Grundlagen der Kryptografie

Elliptische Kurven - Implementierung

 aufwärts

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

Hinweis: Die print-Anweisung von Python 2 ist ab Python 3 zu einer print-Funktion geworden und benötigt daher Klammern um das Argument:

Python 2: print 42
Python 3: print(42)

Klasse ModInt

Die Klasse ModInt repräsentiert Elemente des Körpers ganze Zahlenn 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"

 

Klasse EcPoint

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 reelle Zahlen der reellen Zahlen gerechnet. Anschließend wird dieselbe Berechnung im Körper ganze Zahlen23 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

 

Standard-Punkt auf Standard-Kurve

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 ganze Zahlenn 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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 10.03.2011   Updated: 08.06.2018
Valid HTML 4.01 Transitional