Berechnungsverfahren

Python-Modul BasicFunctions

Die folgenden Python-Funktionen implementieren grundlegende Berechnungen für kryptografische Anwendungen.

Nähere Erläuterungen zu den hier zusammenfassend aufgeführten Programmen finden sich unter Modulare Exponentiation, Erweiterter euklidischer Algorithmus und Multiplikativ inverses Element.

Modulare Exponentiation

# berechnet m hoch e mod n
def modexp(m, e, n):
    if e==0:
        return 1
    if e%2==1:
        return modexp(m, e-1, n)*m % n
    else:
        return modexp(m, e//2, n)**2 % n

Erweiterter euklidischer Algorithmus

Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler g von zwei nichtnegativen ganzen Zahlen a und b. Der erweiterte euklidische Algorithmus berechnet zusätzlich die Koeffizienten u und v einer Darstellung des größten gemeinsamen Teilers g als ganzzahlige Linearkombination von a und b.

# berechnet den groessten gemeinsamen Teiler
# von zwei nichtnegativen ganzen Zahlen a und b
def ggt(a, b):
    if b==0:
        return a
    else:
        return ggt(b, a%b)

# berechnet den groessten gemeinsamen Teiler g von a und b
# sowie eine Darstellung von g als Linearkombination
# von a und b mit ganzzahligen Koeffizienten u und v
# gibt das Tripel (g, u, v) zurueck
def extgcd(a, b):
    if b==0:
        return a, 1, 0
    else:
        g, u, v = extgcd(b, a%b)
        q=a//b
        return g, v, u-q*v

Multiplikativ inverses Element

Gesucht ist das multiplikativ inverse Element a-1 eines Elements a in der multiplikativen Gruppe ℤn*. Hierzu wird der erweiterte euklidische Algorithmus verwendet. Damit a ∈ ℤn* gilt, müssen a und n teilerfremd sein.

# berechnet das multiplikativ inverse Element von a modulo n
def modinverse(a, n):
    g, u, v=extgcd(a, n)
    return u%n

Zufällige gewählte Zahlen

Häufig wird eine zufällig gewählte Zahl aus einem bestimmten Intervall oder einer bestimmten Länge von k Bit benötigt. Die folgenden Funktionen in der Programmiersprache Python liefern die entsprechenden Zahlen.

Voraussetzung für die Erzeugung von Zufallszahlen ist der Import des Moduls random:

from random import *

 

Eine zufällige ganze Zahl n aus dem Intervall [a, b] wird durch Aufruf der Python-Funktion randint erzeugt:

n=randint(a, b)

 

Die erzeugten Zahlen sind allerdings nur Pseudozufallszahlen – sie wirken wie zufällig gleichverteilt in dem entsprechenden Intervall hingestreut, aber sie werden nach einem bestimmten Algorithmus, also vorhersehbar, berechnet. Wird der Zufallszahlen-Algorithmus zweimal mit dem gleichen Startwert gestartet, so erzeut er zweimal die gleiche Folge von Pseudozufallszahlen. Und wenn eine genügend lange Folge von erzeugten Pseudozufallszahlen bereits bekannt ist, lässt sich diese Folge analysieren und in die Zukunft fortsetzen.

Für Zwecke in der Kryptografie ist es jedoch wichtig, dass die erzeugten Zufallszahlen nicht vorhersehbar sind. Es gibt kryptografisch sichere Pseudozufallszahlen, bei denen zumindest eine Analyse der Zahlenfolge nicht durchführbar ist. Aber auch hier wird ein Startwert benötigt; dieser muss aus einer möglichst großen Menge von möglichen Startwerten möglichst nicht nachvollziehbar gewählt werden. Die Python-Funktion SystemRandom().randint berücksichtigt diese Bedingungen. Sie wird in der folgenden Funktion truerandint verwendet.

# liefert eine nicht vorhersehbare zufaellige
#  ganze Zahl aus dem Intervall [a, b]
def truerandint(a, b):
    return SystemRandom().randint(a, b)

 

Wir benutzen diese Funktion, um eine zufällige ganze Zahl der Länge k Bit zu erzeugen. Gemeint sind Zahlen, die sich nur mit genau k Bit darstellen lassen, deren erstes Bit dabei also eine 1 ist. Beispielsweise sind 100, 101, 110 und 111 die entsprechenden 3-Bit-Zahlen, als 4, 5, 6 und 7.

# waehlt zufaellige Zahl der Laenge k Bit, k>0
def randomInt(k):
    a=2**(k-1)
    b=2*a-1
    return truerandint(a, b)

 

Eine zufällige ungerade ganze Zahl n der Länge k Bit wird durch Aufruf der Funktion randomOdd erzeugt:. In der Funktion randomOdd wird zunächst eine zufällige Zahl n der Länge k-1 gezogen. Dann wird n verdoppelt und um 1 erhöht.

# waehlt zufaellige ungerade Zahl der Laenge k Bit, k>1
def randomOdd(k):
    n=randomInt(k-1)
    return 2*n+1

 

 

Weiter mit:   [up]

 

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