Berechnungsverfahren

Python-Modul BasicFunctions

Die folgenden Python-Funktionen implementieren grundlegende Berechnungen für krypto­grafische Anwendungen.

Nähere Erläuterungen zu den hier zusammen­fassend 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 nicht­negativen 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 Linear­kombination 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 multi­plikativ inverse Element a-1 eines Elements a in der multi­plikativen 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 Programmier­sprache Python liefern die ent­sprechenden Zahlen.

Voraus­setzung für die Erzeugung von Zufalls­zahlen 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 Pseudo­zufalls­zahlen – sie wirken wie zufällig gleich­verteilt in dem ent­sprechenden Intervall hingestreut, aber sie werden nach einem bestimmten Algorithmus, also vorhersehbar, berechnet. Wird der Zufalls­zahlen-Algorithmus zweimal mit dem gleichen Startwert gestartet, so erzeut er zweimal die gleiche Folge von Pseudo­zufalls­zahlen. Und wenn eine genügend lange Folge von erzeugten Pseudo­zufalls­zahlen 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 Zufalls­zahlen nicht vorhersehbar sind. Es gibt krypto­grafisch sichere Pseudo­zufalls­zahlen, 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 nach­voll­ziehbar gewählt werden. Die Python-Funktion SystemRandom().randint berück­sichtigt 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. Beispiels­weise sind 100, 101, 110 und 111 die ent­sprechenden 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: 15.06.2025
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden