Reverse Engineering

Unter Reverse Engineering versteht man das Zurückführen des vorliegenden Binärcodes zum dem eigentliche Quellcode. Es kann auch dazu verwendet werden um Informationen aus dem compilierten Quellcode zu erlangen, bzw. diesen teilweise zu manipulieren.

In der Regel geschieht dies mit unterschiedlichen Debuggern (z. B.: x96dbg). Hier werden dann die verschiedenen CPU-Operationen im Assembler-Code dargestellt. Mit Hilfe dieser einzelnen Assembler-Ausführungsroutinen können Rückschlüsse auf unterschiedliche Informationen innerhalb der Software(Software-Keys, Erlangen von Passwörter, Erstellen von Keylogger, Umwandlung von Shareware-Versionen in Vollversionen usw.) gezogen werden.

Beispiele wie ein solches Reverse Engineering durchgeführt werden kann, wird anschließend anhand von .class-Dateien und .exe-Dateien noch näher erläutert.

Ich muss noch darauf hinweisen, das die hier beschriebenen Methoden nicht für illegale Zwecke missbraucht werden dürfen. Diese dienen rein experimentellen Vorhaben. Der Leser dieser Beiträge verpflichtet sich, sich keinen unberechtigten Zugang zu kostenpflichtiger Software zu verschaffen.

Für die kommenden zwei Beispiele wird zum einen eine .class-Java-Datei und zum anderen eine .exe-C#-Datei für ein Reverse Engineering verwendet. In beiden Programmen ist das jeweilige Passwort, dass für einen Simulierten Zugang verwendet werden soll, fest und unverschlüsselt im Programmcode enthalten. Man sollte nicht dem Druckschluss unterliegen und Glauben, da nur der Byte- bzw. der Binär-Code vorliegt das Passwort nicht auslesbar wäre. Passwörter sollten immer verschlüsselt abgelegt werden (siehe Beispiel „Passwort Hashing mit BCrypt“).

Reverse Engineering am Beispiel einer Java-.class-Datei

Als Beispiel wird nun eine einfaches JavaFX-Programm genommen, das die Eingabe eines Benutzers mittels Passwort überprüft. Ist die Eingabe korrekt, wird als Ergebnis „Zugang erlaubt.“ ausgegeben, ansonsten „Zugang verweigert!!!“.

Erfolgreiche Passwort-Eingabe.
Falsche Passwort-Eingabe.

Die interessante Klasse des Programm-Codes ist PassController, da hier das Passwort festgelegt wird (s.u.).

package reverseEng;

import javafx.event.ActionEvent;
import javafx.fxml.FXML;
import javafx.scene.control.Button;
import javafx.scene.control.Label;
import javafx.scene.control.PasswordField;

public class PassController
{
	@FXML
	private PasswordField myPasswordField;
	@FXML
	private Button checkPassButton;
	@FXML
	private Label meldung;	

	// naive Methode: Passwort liegt unverschluesselt vor.
	private final String MY_SECRET_PASSWORD = "Top@Secret";
	private String aktEingabe;	

	public PassController() 
	{
		// TODO Auto-generated constructor stub
		aktEingabe = "";
	}

	
	public String getAktEingabe()
	{
		return aktEingabe;
	}

	public void setAktEingabe(String aktEingabe)
	{
		this.aktEingabe = aktEingabe;
	}

	
	public String getMySecretPassword()
	{
		return mySecretPassword;
	}

	
	@FXML
	public void checkMyPassword(ActionEvent evt)
	{
		aktEingabe = myPasswordField.getText();

		if(aktEingabe.equals(MY_SECRET_PASSWORD))
		{
			meldung.setText("Zugang erlaubt.");
		}
		else
		{
			meldung.setText("Zugang verweigert!!!");
		}
	}
}

Unser kleines Testprogramm besteht aus drei Dateien: MainLogin.class (Hauptprogramm), PassController.class (Controller-Klasse) und der PassWindow.fxml (dient im wesentliche zur Formatierung).

Da uns in unserem Szenario nur der Byte-Code vorliegt, werden wir diesen mit dem kleinen Programm JD-Gui, einem Java Decompiler, der kostenlos heruntergeladen werden kann, wieder zurück in den eigentliche Quellcode überführen. Wir schauen uns nun die Datei PassController.class mit JD-Gui an.

Ausgabe JD-Gui mit ausgelesenem Passwort.

Wie wir feststellen können, kann in JD-Gui das Passwort „Top@Secret“ sehr leicht ausgelesen werden. Class-Java-Dateien können also sehr leicht wieder in den eigentlichen Quellcode überführt werden. Es ist daher keine gute Idee Passwörter im Quellcode unverschlüsselt zu hinterlegen, mit der Annahme es wird schließlich nur der Binärcode weitergegeben und hier könnte das Passwort nicht rekonstruiert werden.

Reverse Engineering am Beispiel einer C#-.EXE-Datei

Wie man bereits im vorherigen Beispiel sehen konnte, ist es sehr einfach Java-Byte-Code wieder in den ursprünglichen Quellcode zu überführen. Passwörter lassen sich allerdings auch aus EXE-Dateien auslesen (im Beispiel PassDeCrypt.exe). Hierzu benutzen wir das vorangegangene Beispiel nur diesmal geschrieben in C# und anschließend kompiliert, damit wir eine EXE-Datei erhalten.

Erfolgreiche Passworteingabe.
Falsche Passworteingabe.

Der C#-Code sieht in unserem Beispiel wie folgt aus:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace PassDeCrypt
{
    public partial class PassDeCrypt : Form
    {
        private const String MY_SECRET_PASSWORD = "Top@Secret";
        private String eingabe;

        public PassDeCrypt()
        {
            InitializeComponent();
            txt_password.PasswordChar = '*';
            eingabe = "";
        }


        public void SetEingabe(String myEingabe)
        {
            eingabe = myEingabe;
        }


        private void CheckPassword()
        {
            if (MY_SECRET_PASSWORD.Equals(txt_password.Text))
            {
                lb_status.Text = "Zugang erlaubt.";
            }
            else
            {
                lb_status.Text = "Zugang verweigert!!!";
            }
        }


        private void Txt_password_TextChanged(object sender, KeyEventArgs e)
        {
            if(e.KeyCode == Keys.Enter)
            {
                CheckPassword();
            }
        }


        private void Bt_login(object sender, EventArgs e)
        {
            CheckPassword();
        }
    }
}

Auch hier liegt das Passwort innerhalb des Quelltextes im Klartext vor.

Mit Hilfe des Decompilierungstools dnSpy, das ebenfalls kostenlos aus dem Internet heruntergeladen werden kann, lässt sich das im Quellcode enthaltenen Passwort relativ einfach auslesen.

Mit dnSpy ausgelesenes Passwort.

Passwort Hashing innerhalb des Programm-Codes (Java)

Wie wir bereits in vorangegangenen Beispielen gesehen haben, ist es keine besonders gute Idee, ein Passwort im Klartext innerhalb des Programmcodes zu hinterlegen. Es stellt sich nun die Frage, wie geht es besser?

Werden Passwörter hinterlegt, ob innerhalb des Programmcodes oder in einer Datenbank, so sollten dies immer in gehashter Form geschehen. Im folgenden Beispiel wird unser Passwort ‚Top@Secret‘ mit BCrypt gehasht hinterlegt.

Bei BCrypt handelt es sich um eine kryptologische Hashfunktion, die speziell für das Hashen und Speichern von Passwörtern entwickelt wurde. Die auf dem Blowfish-Algorithmus basierende Funktion wurde von Niels Provos und David Mazières konzipiert und auf der USENIX-Konferenz im Jahre 1999 der Öffentlichkeit präsentiert. (Quelle und weitere Informationen: Wikipedia BCrypt).

Nun zum Beispiel; unsere Klasse PassController sieht nun wie folgt aus:

package reverseEngCrypt;

import javafx.event.ActionEvent;
import javafx.fxml.FXML;
import javafx.scene.control.Button;
import javafx.scene.control.Label;
import javafx.scene.control.PasswordField;

public class PassController
{
	@FXML
	private PasswordField myPasswordField;
	@FXML
	private Button checkPassButton;
	@FXML
	private Label meldung;
	
	// Passwort als Passwort-Hash (BCrypt) hinterlegen
	private final String MY_SECRET_PASSWORD = "$2a$07$1tXygQHPJvEdPFMqi.r8BuH/pC5LrrFs5.kVJRANSLlQSUJ9V0TIS";
	
	private String aktEingabe;
	
	public PassController() 
	{
		// TODO Auto-generated constructor stub
		aktEingabe = "";
	}
	
	public String getAktEingabe()
	{
		return aktEingabe;
	}
	
	public void setAktEingabe(String aktEingabe)
	{
		this.aktEingabe = aktEingabe;
	}
	
	public String getMySecretPassword()
	{
		return MY_SECRET_PASSWORD;
	}
	
	@FXML
	public void checkMyPassword(ActionEvent evt)
	{
		aktEingabe = myPasswordField.getText();
		CompareHashes hash = new CompareHashes(MY_SECRET_PASSWORD, aktEingabe);
		
		if(hash.comparePassword())
		{
			meldung.setText("Zugang erlaubt.");
		}
		else
		{
			meldung.setText("Zugang verweigert!!!");
		}
	}
}

Wie man sehen kann ist das Passwort im obigen Beispiel gehasht hinterlegt. Um einen Passwort Abgleich herzustellen benötigt man noch eine zweite Klasse CompareHashes. Die obige Klasse erhält eine Referenz auf diese Klasse um dort den Passwortabgleich über die Funktion comparePassword() herzustellen. Der Konstruktor erhält als Parameter den Passwort-Hash und die Benutzereingabe mit der der Vergleich durchgeführt wird.

package reverseEngCrypt;

import org.springframework.security.crypto.bcrypt.BCryptPasswordEncoder;

public class CompareHashes
{	
	private String hash;
	private String eingabe;
	private BCryptPasswordEncoder encoder;
	
	public CompareHashes(String hash, String eingabe)
	{
		this.hash = hash;
		this.eingabe = eingabe;
		encoder = new BCryptPasswordEncoder();
	}
	
	public boolean comparePassword()
	{
		boolean test = encoder.matches(eingabe, hash);
		return test;
	}
}

Passwörter sollten immer gehasht im Programmcode oder in Datenbanken hinterlegt werden, damit diese nicht mit Hilfe von Debuggern oder anderen Tools ausgelesen werden können.

Rivest-Shamir-Adleman Verschlüsselung (RSA)

Das RSA-Verschlüsselungsverfahren gehört zu den asymmetrischen Kryptosystemen (siehe auch Beitrag symmetrische- und asymmetrische Verschlüsselung). Es wurde im Jahr 1977 von den Kryptografen Ron Rivest, Adi Shamir und Leonard Adleman entwickelt. Es eignet sich neben der eigentlichen Verschlüsselung auch als Signaturverfahren. Der RSA-Algorithmus basiert auf dem Faktorisierungsproblem.

Funktionsweise RSA

Wie schon gesagt, beruht der RSA-Algorithmus auf dem Faktorisierungsproblem. Dies besagt, dass es mathematisch sehr schwierig ist, das Produkt zweier sehr großer Primzahlen wieder in die einzelnen Faktoren in annehmbarer Zeit zu zerlegen. Aktuell ist kein Faktorisierungverfahren bekannt, das die ganzzahligen Teiler einer Zahl effizient berechnen kann. Dies hat zur Folge, dass die beiden Faktoren nur durch probieren ermittelt werden können. Dies ist bei sehr großen Primzahlen sehr aufwendig und nimmt eine wenig praktikable Zeit in Anspruch. So lange kein effizientes Verfahren zur Primfaktorenzerlegung gefunden wird, gilt das RSA-Kryptosystem als sicher.

Vorgehensweise: Es werden zwei ausreichend große Primzahlen p und q zufällig gewählt, die geheim bleiben müssen. Lediglich das Produkt N ist bekannt. Anschließend konstruiert man zwei Exponenten, die in der Kryptographie als Schlüssel dienen. Einer davon ist öffentlich, der sogenannte Public Key (e), der andere privat – Private Key (d). Hierbei ist die Schlüssellänge variabel. Je länger der Schlüssel, desto sicherer ist das Verfahren.

Bei der Chiffrierung wird die zu übertragende Nachricht als Zahl m mit dem öffentlichen Schlüssel e und dem Produkt aus p und q zum Geheimtext c verschlüsselt.

c \equiv m^e \ mod \ \underbrace{p \cdot q}_N

Zur Entschlüsselung wird d benötigt:

m \equiv c^d \ mod \ \underbrace{p \cdot q}_N

d lässt sich nicht aus e berechnen, ohne die beiden Primzahlen p und q zu kennen.

Wichtig ist es, um es einem Angreifer unmöglich zu machen den privaten Schlüssel zu erraten, einen ausreichend großen Schlüssel zu wählen. Alle gängigen Verschlüsselungsalgorithmen sind in der Regel so konstruiert, dass die Rechenleistung moderner Computer nicht ausreichend ist, um in annehmbarer Zeit an den privaten Schlüssel durch einfaches Ausprobieren (vollständige Schlüsselsuche) zu gelangen.

Beispiel

Ein Beispiel der RSA-Verschlüsselung könnte wie folgt aussehen (der allgemeine Ablauf kann unter dem Beitrag Primzahlen nachgelesen werden):

  1. Wir wählen zuerst zwei Primzahlen p und q
    • Wert für p=23
    • Wert für q=31
  2. Ermittlung von N mit
    • N=p \cdot q=713 und berechne
    • \varphi(N) mit \varphi(N)=(23-1) \cdot (31-1) = 660
  3. Wähle dann e \in \{2,..., \varphi(N)-2 \} mit ggT(e, \varphi(N))=1 \Rightarrow 97
  4. Bestimme d mit e \cdot d \equiv 1 \ mod \ \varphi(N) = 313
  5. Damit sind N, e der öffentliche und N, d der private Schlüssel
    • N=713, e=97, d=313.

Mit obigen öffentlichem Schlüssel soll nun die Zahl 5 verschlüsselt und mit dem privatem Schlüssel wieder entschlüsselt werden.

563 \equiv 5^{97} \ mod \ 713 \Rightarrow die 563 ist somit unser Geheimtext c.

Der Geheimtext c soll nun wieder zum Klartext m entschlüsselt werden.

5 \equiv 563^{313} \ mod \ 713 \Rightarrow somit gelangen wir wieder zur 5 als Klartext m.

Untenstehndes Python-Programm beschreibt im wesentlichen den RSA-Algorithmus. Auf einen Test ob p und q Primzahlen sind, wurde aus Gründen der Einfachheit verzichtet. Wie ein solcher Test durchgeführt wird, kann in den Beiträgen „Fermat-Test“ und „Miller-Rabin-Test“ nachgelesen werden. Weiterführende Erklärungen zu den Bestandteilen von RSA sind zu finden unter: Euklidischer- und erweiterter Euklidischer Algorithmus sowie die Eulersche Phi-Funktion.

from random import randint

'''berechnet N'''
def berechneN(p,q):
    n = p * q
    return n

'''berechnet phi(N)'''
def berechnePhi(p,q):
    phi = (p - 1) * (q - 1)
    return phi

'''berechnet den ggT(e,phi(N))'''
def berechneGGT(e,phiN):
    while phiN!=0:
        e ,phiN = phiN, e % phiN
    return e

'''sucht ein zufaelliges e aus einer Liste'''
def sucheE(phiN):
    e = 2
    eListe = []
    egef = False
    while e <= phiN-2 and egef == False:
        if berechneGGT(e, phiN) == 1:
            eListe.append(e)
        e = e + 1
    return eListe

'''Alternative zur Ermittlung von e. Liefert erstes gefundenes e' --> schneller'''
def sucheEalter(phiN):
    e = 2
    eGef = e
    while e <= phiN-2:
        if berechneGGT(e, phiN) == 1:
            eGef = e
            break
        e = e + 1
    return eGef
        
'''Erweiterter Euklidischer Algorithmus zum Loesen der diophantischen Gleichung e*d+k*phi(n)=ggT(e,phi(n))=1'''
def extgcd(e, phiN):
    tmpphiN = phiN
    d, k, di, ki = 1, 0, 0, 1
    while phiN!=0:
        q=e//phiN
        e, phiN = phiN, e-q*phiN
        k, ki = ki, k-q*ki
        d, di = di, d-q*di
    if d < 0:
        d = d + tmpphiN
    return d

'''zufaelliges e aus Liste zurueck liefern'''   
def retEtmp(laenge):
    return randint(1, laenge)
    
    
'''Der Einfachheit halber, wird auf eine Pruefung, ob p und q Prim sind verzichtet --> Pruefung z.B. ueber Miller-Rabin-Test'''
if __name__ == '__main__':
    p = 23
    q = 31
    n = berechneN(p, q)
    phi = berechnePhi(p, q)
    eteilerf = sucheE(phi)
    laengeEListe = len(eteilerf)
    randE = retEtmp(laengeEListe-1)
    e = eteilerf[randE]
    d = extgcd(e,phi)
    
    print("N:", n)
    print("Phi(n):", phi)
    print("e (Public Key):", e)
    print("d (Private Key):", d)
    

Sicherheit RSA

Das RSA-Kryptoverfahren beruht, wie schon erwähnt darauf, dass es schwierig ist große Primzahlen in ihre Primfaktoren zu zerlegen. Die vollständige Schlüsselsuche ist beispielsweise bei einer Schlüssellänge von 256 Bit aussichtslos. Allerdings stellt die vollständige Schlüsselsuche nicht die beste Angriffsmethode auf das RSA-Verfahren dar. Gefährlicher ist ein Faktorisierungsangriff. Dieser ist zwar sehr aufwendig, kann aber dennoch zum Erfolg führen, wenn die verwendeten Primzahlen zu klein gewählt wurden.

Im Vergleich zum AES-Verfahren bietet das RSA-Kryptosystem eine größere Angriffsfläche. Die Sicherheit von RSA hängt im wesentlichen von der Implementierung und von der gewählten Schlüssellänge ab. Ist ein Verfahren sauber programmiert, dann hat der Angreifer nur noch die Möglichkeit durch bloßes Probieren aus dem öffenlichen Schlüssel den privaten Schlüssel abzuleiten. Im wesentlichen wird eine Schlüssellänge von 2.048 Bit oder besser von 4.096 Bit empfohlen.

Ein Problem bei dem asymmetrischen Verfahren RSA ist, dass die erforderlichen Schlüssellängen für eine sichere Verschlüsselung sehr lang sind. Sollten weitere Möglichkeiten für eine schnelllere Faktorisierung ermittelt werden, so ist eine sichere Verschlüsselung mit RSA auf Grung der Länge der benötigten Schlüssel nur schwer hanhabbar. Empfehlenswert sind daher EEC (Elliptic Curve Cryptography)-Verfahren mit elliptischen Kurven. Diese kommen mit einer geringeren Schlüssellänge aus um eine hohe Sicherheit zu gewährleisten.

Advanced Encryption Standard (AES)

Wie schon in dem Beitrag symmetrische- und asymmetrische Verschlüsselung erwähnt, handelt es sich bei der Verschlüsselungsmethode AES um ein symmetrisches Kryptosystem.

Der AES Verschlüsselungalgorithmus ist eine der sichersten und meistgenutzten Kryptoverfahren. Er wird zum Beispiel in den USA für Regierungsdokumente der höchsten Geheimhaltungsstufe verwendet.

Die Entwicklung von AES begann im Jahr 1997 als ein Nachfolger des in die Jahre gekommenen Verschlüsselungsstandards DES (Data Encryption Standard) gesucht wurde. Diese Suche dauerte vier Jahre und wurde offiziell vom Standardinstitut NIST ausgerufen. Unter einer Vielzahl von Bewerbern konnte sich letztenendes der von Joan Daemen und Vincent Rijmen entwickelte Rijndael-Algorithmus durchsetzten. Er überzeugte sowohl in Bezug auf Felxibilität, Sicherheit und Performance. 2001 wurde er schließlich offiziell als der neue Standard AES bekanntgegeben.

Die Funktionsweise von AES beruht auf einer Reihe von Byteersetzungen (Substitutionen), Verwürfelungen (Permutationen) und linearen Transformationen, die auf Datenblöcke von 16 Byte ausgeführt werden – hierauf beruht auch der Begriff Blockverschlüsselung. Diese Operationen werden mehrfach wiederholt, wobei in jeder dieser Runden ein individueller, aus dem Schlüssel berechneter Rundenschlüssel in die Berechnung mit einfließt. Wird nur ein einziges Bit im Schlüssel oder im Datenblock verändert, entsteht ein komplett anderer Chiffreblock.

Die Bezeichnungen AES-128, AES-192, AES-256 oder AES-512 beziehen sich auf die Länge des Schlüssels. Die Schlüssellängen des AES-Verschlüsselungsverfahren unterscheiden sich beträchtlich in der Länge des Schlüssels des DES-Kryptoverfahrens. Hier war nur eine 56-Bit Schlüssellänge möglich.

Um einen 192-Bit Schlüssel zu knacken würde ein moderner Supercomputer länger benötigen, als das geschätzte Alter des Universums. Bis heute ist für keine der AES-Varianten ein praktisch durchzuführender Angriff bekannt. AES gehört daher zu einem der meist genutzten Kryptosystemen bei Banken, Regierungen und High-Security-Systemen.

symmetrische- und asymmetrische Verschlüsselung

In der Kryptographie wird zwischen symmetrischen und asymmetrischen Kryptosystemen unterschieden. Diese unterscheiden sich vorallem in der Anzahl der verwendeten Schlüssel.

symmetrische Verschlüsselung

Beim symmetrischen Kryptoverfahren gibt es, anders als beim asymmetrischen Kryptoverfahren, nur einen Schlüssel. Dieser Schlüssel dient sowohl zur Ver- als auch zur Entschlüsselung. Dies bedeutet, falls Informationen ausgetauscht werden sollen, dass sowohl der Sender als auch der Empfänger im Besitz des Schlüssels sein müssen. Beim Sender ist dies natürlich kein Problem, da er bereits im Besitz des Schlüssels ist.

Beim Empfänger jedoch stellt sich die Frage, auf welchem Übertragungsweg der Schlüssel (Passwort, Key, …) sicher mitgeteilt oder übergeben werden kann. Dies ist auch zugleich ein Hauptnachteil der symmetrischen Verschlüsselung.

Beachtet werde muss, dass man symmetrische Kryptoverfahren in Block- und Stromchiffren unterteilen kann. Bei Stromchiffren wird z.B. der Klartext Zeiche für Zeichen verschlüsselt, während der Geheimtext auch wieder Zeichen für Zeichen entschlüsselt werden muss. Hingegen bei Blockchiffren, werden die Zeichen des Textes in feste Blockgrößen eingeteilt, sodass mehrere Zeichen in einem Schritt ver- bzw. entschlüsselt werden können.

Vorteile der symmetrischen Verschlüsselung sind:

  • einfaches Schlüsselmanagement, da nur ein Schlüssel zum ver- und entschlüsseln benötigt wird
  • verhältnismäßig hohe Geschwindigkeit für Ver- und Entschlüsselung, da Verfahren meist auf effizienten Operationen wie Bit-Shifts und logischen XOR-Operationen aufbauen

Nachteile der symmetrischen Verschlüsselung sind:

  • nur ein Schlüssel zur Ver- und Entschlüsselung, dieser darf nicht in unbefugte Hände geraten
  • wie schon erwähnt, muss der Schlüssel über einen sicheren Kommunikationskanal ausgetauscht werden
  • Anzahl der Schlüssel bezogen auf die Anzahl der Teilnehmer wächst quadratisch

Symmetrische Kryptoverfahren:

  • AES – Advanced Encryption Standard
  • DES – Data Encryption Standard (Schlüssellänge nur 56-Bit für mache Anwendungen nicht ausreichend sicher)
  • Trible DES – auch als TDES, 3DES oder DESede bezeichnet
  • IDEA – International Data Encryption Algorithm
  • Blowfish
  • Towfish
  • CAST-128, CAST-256
  • RC2, RC4, RC5, RC6
  • Fox

asymmetrische Verschlüsselung

Bei einem asymmetrischen Kryptosystem arbeitet man, anders als beim symmetrischen Kryptosystem, mit zwei unterschiedlichen Schlüsseln. Ein Schlüssel, der sogenannte Public Key, dient der reinen Verschlüsselung. Der zweite Schlüssel, der Private Key, dient der Entschlüsselung und sollte vom Eigentümer gut und sicher aufbewahrt werden.

Dieses Schlüsselpaar, der Public Key und der Private Key, hängt über einen mathematischen Algorithmus eng zusammen. Daten die mit dem öffentlichen Schlüssel verschlüsselt wurden, können nur mit dem privatem Schlüssel wieder entschlüsselt werden (siehe Abbildung unten). Der private Schlüssel muss daher vom Besitzer geheim gehalten werden.

Quelle: de.wikipedia.org

Ein konkreter Anwendungsfall könnte z. B. wie folgt aussehen: Will Benutzer A Daten verschlüsselt an Benutzer B übermitteln, so muss er ihm seinen öffentlichen Schlüssel übermitteln. Der private Schlüssel hingegen bleibt im Besitz von Benutzer A. Benutzer B verschlüsselt nun die Nachricht mit dem Public Key von Benutzer A und kann nun die geheime Nachricht an Benutzer A senden. Benutzer A kann nun wiederum die geheime Nachricht mit Hilfe seines privaten Schlüssels wieder entschlüsseln

Das Problem der asymmetrischen Verschlüsselung ist die Verteilung des Public Keys. In der Regel gesschieht die beim Erstkontakt mit dem Kommunikationspartner. Jedoch stellt sich hierbei die Frage, ob der vermutete Kommunikationspartner auch derjenige ist, für den er sich ausgibt.

Bei Asymmetrische Kryptosysteme geht es in der Regel darum, eine Funktion zu wählen, die sehr einfach zu berechenen ist, deren Umkehrung hingegen sich als sehr aufwendig gestaltet. Realisiert wird dies mit Modulo-Rechenfunktionen (siehe Kategorie Zahlentheorie). Diese sind teilweise recht einfach zu berechenen, jedoch gestaltet sich deren Umkehrung als sehr aufwendig. Solche Funktionen bezeichnet man auch als Einwegfunktionen. Funktionen bei denen sich die Umkehrung mit einer zusätzlichen Information abkürzen lässt, werden als Falltürfunktionen bezeichnet.

Ein Beispiel für eine Einwegfunktion ist der diskrete Logarithmus. Dieser kann sehr leicht berechnet werden. Umgekehrt ist es jedoch nicht in praktikabler Zeit möglich eine große Zahl zurüchzurechnen. Man bezeichnet dies als Diskreter-Logarithmus-Problem. Viele asymmetrische Verschlüsselungsverfahren beruhen darauf. Allerdings soll dies nicht bedeuten, dass nicht irgendwann ein Weg gefunden wird das Diskrete-Logarithmus-Problem zu lösen.

Beispiel:

Der diskrete Logarithmus beschreibt eine Kongruenz der Form: a^x \equiv m \ modulo \ p wobei x geheim ist.

a=2
m=396923
p=1419403
x \ ist \ geheim.

x lässt sich nur durch probieren ermitteln.

Untenstehender Python-Code liefert das erste Ergebnis durch einfaches probieren für den Wert x. Im Beispiel wird der Wert für x=26 schnell ermittelt, da die einzelnen Werte relativ klein gewählt wurden.

'''Phython-Programm zur Ermittlung von x'''
def calcX(a, m, p):
    i = 1
    while ((a**i % p) != (m % p)):
        i += 1
    return i
        
if __name__ == '__main__':
    a = 2
    m = 396923
    p = 1419403
    '''Berechnet a^i kongruent m modulo p'''
    diskLog = calcX(a, m, p)
    print("Wert fuer diskreten Logarithmus: ", diskLog)

Eine weitere Einwegfunktion ist das Multiplizieren von Primzahlen. Während die Multiplikationen für einen Computer kein Problem darstellt, so ist das Zurückrechnen d. h. das Zerlegen des Primzahlproduktes in die einzelnen Primfaktoren, bei sehr großen Primzahlen nicht in praktikabler Zeit möglich. Man spricht hierbei von Faktorisierung und in dem Zusammenhang vom Faktorisierungsproblem.

Beispiel:

Man berechnet 23 \cdot 31. Als Ergebnis erhält man 713. Um nun die 713 wieder in ihre einzelnen Faktoren zu zerlegen, gibt es hier nur einen Weg; man muss alle Möglichkeiten durchprobieren. Sind die Primzahlen sehr groß gewählt, so dauert dies sehr sehr lange.

Untenstehendes Pythonprogramm liefert einen möglichen Algorithmus zur Primfaktorzerlegung.

'''Python-Programm zur Primfaktorzerlegung'''
def primfaktor(zahl):
    primListe = []
    while zahl % 2 == 0:
        primListe.append(2)
        zahl = zahl // 2
    i = 2
    while i <=  zahl:
        if zahl % i == 0:
            primListe.append(i)
            zahl = zahl // i
            i = 2
        i += 1
    primListe.append(zahl)
    primListe.sort()
    if primListe[0] == 1:
        primListe.remove(1)
    return primListe  
    
if __name__ == '__main__':
    zahl = 713
    print(primfaktor(zahl))

Mögliche Angriffe auf asymmetrische Verschlüsselungsverfahren:

  • Public-Key-Only-Angriff: Ist der öffentliche Schlüssel bekannt, kann der Angreifer beliebigen Klartext verschlüsseln und beispielsweise mit bereits verschlüsselten Klartext vergleichen.
  • Chosen-Cipertext-Angriff: Der Angreifer schickt einen beliebigen Geheimtext an sein Ziel, um diesen entschlüsseln zu lassen.

Asymmetrische Kryptoverfahren:

Die bekanntesten asymmetrischen Kryptoverfahren sind das RSA- und das Diffie-Hellmann-Verfahren.

IT-Notfallplan

Innerhalb eines Notfallplans ist definiert, was nach der Entdeckung eines Angriffs zu tun ist. Wichtig ist vorallem ein besonnes Handeln. Es geht schließlich darum:

  • schnell, aber richtig zu handeln, wenn der Angriff akut gestoppt werden muss – Unsicherheit und unklare Kompetenzen hätten fatale Folgen.
  • den Schaden möglichst zu minimieren, statt ihn durch eigenes Handeln zu vergrößern.
  • einen genauen Überblick über den Schaden und das Ausmaß der notwendigen Reperaturen zu bekommen: man sollte allerdings darauf achten, die Spuren des Angriffs nicht durch sein Handeln zu verwischen. Eine Spurensicherung ist deshalb sinnvoll, da dadurch zum einen der Angriff rekonstruiert werden kann und so vorhandene Schwachstellen geschlossen werden können, und zum anderen ist nur so eine gute Beweissicherung („digitale Forensik“) durchführbar.
  • sich selbst im betrieblichen Einsatz arbeitsrechtlich zu schützen.

Ein Notfallplan besteht idealerweise aus zwei Teilen:

  • Der organisatorische Teil behandelt vorwiegend die Fragen: -wer macht was? -wer darf was? -wer koordiniert und trägt die Verantwortung? -wer ist zu informieren?
  • Der technisch-beschreibende Teil geht spezifisch auf die vor Ort vorhandene Installation ein und legt fest, wie zu reparieren und vorzugehen ist, falls es Besonderheiten gibt.

Auf der Webseite des Bundesamtes für Sicherheit in der Informationstechnik (BSI) sind Vorlagen für die Unterschiedlichen IT-Systeme zu finden (VPN, Windows-Server, Webserver, DNS-Server usw.). Diese Vorlagen können u.a. dazu verwendet werden, diese als Leitfaden zu benutzen, damit nichts Grundsätzliches vergessen wird. Die Erstellung eines IT-Notfallplanes sollte ernst genommen werden. Es ist zwar lästig Arbeit in Dinge zu investieren, die im Idealfall nie gebraucht werden, aber so ist man für den Fall der Fälle vorbereitet. Weiterhin sollte jeder Mitarbeiter der IT Kenntnis über den Inhalt und Aufbewahrungsort des Dokumentes haben.

Sofern es notwendig ist, sollte auch nicht vergessen werden den IT-Notfallplan vom Vorgesetzten (per Unterschrift) absegnen zu lassen. So wird zusätzlich dokumentiert wer welche Kompetenzen erhält. Dies kann vorallem arbeitsrechtlich wichtig sein falls schwerwiegende Entscheidungen getroffen werden müssen. Schnell kann einem hier ein Strick gedreht werden, wenn das Betriebsklima ohnehin angespannt ist und ein Bauernopfer gesucht wird.

IT-Sicherheitsplan

Der IT-Sicherheitsplan ist die praktisch-planerische Umsetzung der Security Policy. Er sollte alle von der Security Policy offen gelassenen Risikien erkennen und eventuelle Lücken schließen.

Vier Stufen zur Erstellung eines IT-Sicherheitsplanes.

Wie aus obiger Abbildung ersichtlich, umfasst die Erstellung eines Sicherheitsplanes vier Stufen:

1. Ermittlung der Schutzbedürftigkeit

Es wird festgestellt, welche Werte in einem Netzwerk schutzbedürftig sind.

2. Analyse der Bedrohung

Hier sollten alle möglichen Bedrohungen für die im ersten Schritt festgestellten Schutzziele ermittelt werden.

3. Risikoanalyse

Bei dieser Bewertung soll festgestellt werden, wie stark sich Bedrohungen auf das Netzwerk oder einzelne Dienste auswirken und welche Risiken damit verbunden sind. Wichtig dabei sind zwei Faktoren:

  • Eintrittswahrscheinlichkeit: Wie wahrscheinlich ist es, dass sich eine festgestellte Bedrohung in einem bestimmten Zeitraum einstellt?
  • Schadenshöhe: Unabhängig von Wahrscheinlichkeit und Ursache können Schäden sehr unterschiedliche Ausmaße (zwischen Bagatellschaden und Katastrophe) annehmen.

Um ein Risiko zu quantifizieren, sollte man die Eintrittswahrscheinlichkeit und die mögliche Schadenshöhe in Relation setzen. Dies kann mit Hilfe folgender Formel geschehen:

Risiko = Eintrittswahrscheinlichkeit  x  Schaden

Manche Risiken lassen sich jedoch entweder gar nicht oder nur mit einem unverhälnismäßig hohen Aufwand ausschließen. Es ist also notwendig ein „gesundes Maß“ zu finden, das sogenannte Schutzziel. Damit wird eine kalkulierte Grenze gesetzt, die Risiko und Aufwand betrachtet und markiert, welches Risiko noch in Kauf zu nehmen ist.

4. Sicherheitskonzept

Das Kernstück aller Sicherheitsbemühungen: Nachdem die Analyse abgeschlossen ist, sollte ein Sicherheitskonzept erstellt werden, das die zu ergreifenden Maßnahmen festlegt.
Es verfolgt – anders als die Security Policy – einen ganz konkreten Ansatz:
Hier wird die zu realisierende Lösung definiert. Das Sicherheitskonzept darf keine Risiken
erlauben, die über dem definierten Schutzziel liegen.

Dazu gehört zum Beispiel:

  • die exakte restriktive Konzeption der Firewall(s)
  • die Konzeption eines IDS, das die erkannten Schutzziele überwacht und die festgestellten Bedrohungen erkennt
  • die Konfiguration der Desktop-PCs
  • die Definition einer Backup Policy
  • die Definition von Zugangsberechtigungen, Passwortvergaberichtlinien und Kompetenzen

Das Sicherheitskonzept ist keine Privatsache des Administrators, sondern sollte von der Hausspitze abgesegnet und mitgetragen werden. Es sollte von Anfang an daran gedacht werden alle zuständigen Kollegen ggf. in die Konzeption mit einzubeziehen, andernfalls riskiert man, das irgendwann von höherer Stelle Ausnahmen gefordert werden, die eigentlich laut Policy nicht zugelassen sind. Ebensowenig nützt eine Sicherheitskonzept, das von den Angestellten nicht mitgetragen und darum schlichtweg ignoriert oder gar voarsätzlich verletzt wird.

Die Bedeutung der Netzwerksicherheit wird meist auf jeder Hierarchiestufe massiv unterschätzt. Es sollte nie vergessen werden, welche materiellen und immateriellen Schäden (Finanzen und Image) einem Unternehmen entstehen können, wenn es zu einem schweren Sicherheitsvorfall kommt.


obige Ausführungen stammen größtenteils aus dem Buch: Snort, Acid & Co. – Einbruchserkennung mit Linux, Autoren: Thomas Bechtold u. Peer Heinlein, Verlag: 2004 Open Source Press GmbH.

Security Policy

Die Security Policy (Sicherheitspolitik) eines Unternehmens soll definieren, wie ein Computernetzwerk zu benutzen ist. Sie sollte festgelegt werden, bevor es an die Erstellung und Umsetzung eines Sicherheitskonzepts geht, das wiederum festlegt wie das Netzwerk zu schützen ist.

Die Sicherheitspolitik richtet sich an alle Benutzer eines Netzwerks und sollte daher für jedermann leicht verständlich und möglichst allgemein gehalten sein. Jedoch sollte darauf geachtet werden, dass eine zu allgemein gehaltene Fassung der Security Policy zu Missverständnissen führen kann. Es sollte im betrieblichen Umfeld also ein Weg gefunden werden, die Sicherheitspolitik zwar allgemein zu gestalten, dabei aber so wenig Interpretationsspielraum wie möglich zu lassen.

Zuerst sollte ein entsprechender Soll-Zustand festgelegt werden. In wie weit dieser realsierbar ist, sollte zunächst nicht im Vordergrund stehen. Später kann die Sicherheitspolitik, falls notwendig, immer noch angepasst und unter Umständen restriktiver gefasst werden, wenn es sich abzeichnet, dass sie zu großzügig ist und durch das Sicherheitskonzept nicht abgesichert werden kann.

Grundsätzlich gibt es zwei unterschiedliche Betrachtungsweisen bei der Formulierung einer Security Policy:

  • restriktiv: Alles, was nicht ausdrücklich erlaubt wurde, ist verboten.
  • permissiv: Alles, was nicht ausdrücklich verboten wurde, ist erlaubt.

Nach Möglichkeit ist die restriktivere Methode der permissiveren vorzuziehen, denn ein Fehler führt bei ihr eher dazu, dass zu viel verboten ist. Die permissivere Methode scheint zwar leichter umsetzbar, besitzt allerdings wesentlich mehr Gefahrenpotential. Bequemlichkeit und Sicherheit sind leider zwei gegenläufige Interessen.

Die Sicherheitspolitik legt fest was erlaubt ist. Es wird im Rahmen eines IT-Sicherheitsplans überlegt, welcher Schutz notwendig ist und wie er durch ein entsprechendes Sicherheitskonzept zu realsieren ist. Wird die Security Policy übergangen, kann dadurch (im schlimmsten Fall) der komplette Schutz ausgehebelt werden. Sie ist demnach mehr als nur eine Richtlinie, sondern vielmehr eine verbindliche Norm.

Innerhalb der Security Policy können z.B. folgende Regelungen festgehalten werden:

  • Welche Rechte haben die Benutzer auf ihren Clients? Dürfen sie z.B. selbst Programme installieren?
  • Wann und wie werden Backups angelegt? Welcher Datenverlust ist noch tolerierbar?
  • Welche Internetdienste dürfen von den Mitarbeitern genutzt werden?
  • Welche Software ist Standardmäßig auf den Clients installiert?
  • Wo müssen Dateien gespeichert werden? Lokal auf den einzelnen Clients oder auf einem Server im entsprechenden Home-Verzeichnis?
  • usw. …

Einen Großteil der Regelungen die in der Security Policy festgehalten sind betreffen selbstverständlich auch das Verhalten der Mitarbeiter. Daher sollte die Sicherheitspolitik auch innerhalb des Unternehmens bekannt gemacht werden. Ebenfalls wichtig ist es, um die Akzeptanz der hauseigenen Sicherheitspolitik zu stärken, zu erklären warum gewisse Dinge erlaubt sind und welche nicht. Geschieht dies nicht besteht die Möglichkeit, dass der Laie dies zu schnell als reine Gängelung und Willkür des Administrators auffassen könnte.

Nähere Informationen über Security Policys können auch auf der Seite des BSI (Bundesamt für Sicherheit in der Informationstechnik) nachgelesen werden.

Miller-Rabin-Test

Der Miller-Rabin-Test ist eine Verschärfung des Fermat-Tests und dient ebenfalls der Bestimmung von Primzahlen (p). Dieser hat allerdings im Vergleich zum Fermat-Test eine wesentlich höhere Trefferwahrscheinlichkeit in Bezug auf die Bestimmung von Primzahlen.
Beim Miller-Rabin-Test handelt es sich um einen probilistischen Primzahltest. Dies bedeutet, dass die Basis n auf welcher die Exponentation durchgeführt wird zufällig innerhalb des Intervalls ]1, \ p-1] \in \mathbb{Z} gewählt wird. Anders als beim Fermat-Test werden beim Miller-Rabin-Test mehrere Basen n als sogenannte Zeugen verwendet.

Eine Basis n gilt als Belastungszeuge für p, wenn n^2 \ mod \ p=1 ist, aber n \neq 1 und n \neq p-1.
Die Begründung hierfür ist folgende:

Ist p eine Primzahl, dann ist \mathbb{Z}_p ein Körper. In einem mathematischen Körper hat jede quadratische Gleichung höchstens zwei unterschiedliche Lösungen. Nun hat aber in \mathbb{Z}_p die quadratische Gleichung n^2=1 schon die beiden Lösungen n=1 und n=-1=p-1. Da p>2 vorausgesetzt werden kann, sind diese auch verschieden. Gibt es nun noch eine weitere Lösung, dann kann \mathbb{Z}_p kein Körper sein. Dann kann auch p keine Primzahl sein.

Beispiel:
Vermutete Primzahl p=37 \longrightarrow p-1=36=b_i
Ausgehend vom Satz von Fermat: n^{p-1} \ mod \ p=1
p-1 wird solange durch zwei dividiert bis ein ungerader Wert b_1 \in \mathbb{Z} entsteht:
36 : 2 = 18
18 : 2 = 9
Diese Werte b_{1...i} \in \mathbb{Z} werden anschleißend in eine Tabelle eingetragen und die Berechnungen n^{b_{1...i}} \ mod \ p durchgeführt. Die Basis n für die Exponentation liegt im Intervall ]1, \ p-1].

nn^9 \ mod \ 37
n^{18} \ mod \ 37
n^{36} \ mod \ 37
56361
12111
15
31361

Aus den 1-sen in der letzten Spalte kann nun geschlossen werden, dass es sich bei p=37 mit hoher Wahrscheinlichkeit um eine Primzahl handelt.

Mit Hilfe der Programmiersprache Python, kann der Miller-Rabin-Test wie folgt beschrieben werden:

from random import randint

def millerRabin(prim):
    tmp = prim - 1
    wPrim = True
    i = 0
    while i < 20:
        basis = randNumber(tmp)
        while tmp % 2 == 0:
            if basis**tmp % prim == 1:
                wPrim = True
                break
            else:
                wPrim = False
            tmp = tmp // 2
        if not wPrim:
            break
        i += 1
    if wPrim:
        print("wahrscheinlich Primzahl.")
    else:
        print("Keine Primzahl.")
        
    
def randNumber(wert):
    return randint(2, wert)

def isgerade(zahl):
    if zahl == 2:
        print("wahrscheinlich Primzahl.")
    elif zahl % 2 == 0 and zahl > 2:
        print("Keine Primzahl.")
    else:
        if millerRabin(zahl):
            print("wahrscheinlich Primzahl.")
        else:
            print("Keine Primzahl")

if __name__ == '__main__':
    prim = 561
    isgerade(prim)

Im obigen Programm wird, anders als beim Fermat-Test, die 561 (Pseudoprimzahl) als nicht Primzahl durch den Miller-Rabin-Test erkannt. Um ein besseres Laufzeitverhalten zu gewährleisten, kann die Anzahl der Schleifendurchläufe und die Anzahl der zu testenden Basen reduziert werden. Dies geht allerdings auf Kosten der Treffergenauigkeit. Man sollte demzufolge eine gute Balance zwischen Treffergenauigkeit und Laufzeitverhalten finden.

Fermat-Test

Mit Hilfe des Fermat-Tests kann mit einer gewissen Wahrscheinlichkeit ausgesagt werden, ob eine gegebene Zahl eine Primzahl ist.
Der fermatsche Primzahlttest beruht auf dem kleinen Satz von Fermat.
Für jede Primzahl p und jede dazu teilerfremde natürliche Zahl a ist folgende Kongruenz erfüllt:

a^{p-1}  \equiv  1 \ mod \ p

Beispiel:
Man nehme eine zu p teilerfremde natürliche Zahl, zum Beispiel 2, und bilde 2^{p-1} \ mod \ p.
Kommt etwas anderes als 1 heraus, so kann p keine Primzahl sein. Kommt 1 heraus, so ist p ziemlich wahrscheinlich eine Primzahl.
Im ersten Fall spielt die Zahl 2 die Rolle eines Belastungszeugen (engl. witness) dafür, dass p zusammengesetzt ist. Im zweiten Fall kann der Zeuge 2 die Zahl p nicht belasten. Somit muss p mangels Beweisen freigesprochen werden. Ob p aber wirklich unschuldig (= Primzahl) ist, bleibt zumindest zweifelhaft.

Der Fermat-Test kann mit Hilfe von Python wie folgt implementiert werden:

def fermat(zeuge, testzahl):
    if zeuge ** (testzahl-1) % testzahl != 1:
        print("Keine Primzahl.")
    else:
        print("wahrscheinlich Primzahl.")

if __name__ == '__main__':
    '''Pseudoprimzahl bezgl. Fermat-Test'''
    testzahl = 561 
    zeuge = 2
    fermat(zeuge, testzahl)

Das obige Phython-Programm liefert als Ergebnis für die Testzahl 561 mit Zuhilfenahme der 2 als Zeuge „wahrscheinlich Primzahl“. Die Testzahl 561 ist allerdings keine Primzahl. Sie lässt sich in die Primfaktoren 17, 11 und 3 (3 \cdot 11 \cdot 17 = 561) zerlegen. Hierbei handelt es sich um eine sogenannte Pseudoprimzahl zur Basis 2 bezüglich des Fermat-Tests (genauer gesagt ist die 561 die kleinste Carmichael-Zahl). In der Praxis spielt daher der Fermat-Test, wegen seiner nicht ausreichenden genauen Bestimmung von Primzahlen keine oder kaum eine Rolle.
Hier finden eher Primzahltests mit einer höheren Trefferwahrscheinlichkeit Anwendung (wie z. B. der Miller-Rabin-Test).

Der Euklidische- und erweiterte Euklidische Algorithmus

Der Euklidische Algorithmus

Der Euklidische Algorithmus dient dazu, den größten gemeinsamen Teiler (ggT) zweier natürlicher Zahlen zu ermitteln. Das Ermitteln des ggT findet in der Kryptographie bei vielen Kryptosystemen Anwendung.

Beispiel:
Es soll für zwei natürliche Zahlen a=285 und b=33 der ggT(285,33) ermittelt werden.
Formal kann die Ausgangssituation wie folgt beschrieben werden:  a=q \cdot b + r (r steht hierbei für den Rest der ganzahligen Division).

Beispiel für a=285 und b=33:
285=8 \cdot 33 + 21
33=1 \cdot 21 + 12
21=1 \cdot 12 + 9
12= 1 \cdot 9 + 3
9= 3 \cdot \textbf{3} + 0

In der letzten Zeile kann der ggT(285,33)=3 abgelesen werden (fett gedruckte 3). Die Berechnung des ggT ist abgeschlossen, sobald der Rest (r) den Wert 0 angenommen hat.

Kompakter kann der ggT(285,3) auch in Form einer Tabelle ermittelt werden:

abr
2853321
332112
21129
1293
930

Die Spalte b in der letzten Zeile liefert das Ergebnis ggT(285,33)=3.

Als Python-Programm lässt sich die Ermittlung des ggT wie folgt implementieren:

def ggt(a ,b):
    while b!=0:
        a ,b = b, a % b
    return a

if __name__ == '__main__':
    a = 285
    b = 33
    print("Ausgabe ggt: ", ggt(a, b))

Der erweiterte Euklidische Algorithmus

Der erweiterte Euklidische Algorithmus wird u. a. dazu verwendet lineare diophantische Gleichungen der Form a \cdot x + b \cdot y = ggT(a,b) zu lösen. Vielfache des ggT(a,b) sind ebenfalls lösbar und können allgemein mit a \cdot x \cdot z + b \cdot y \cdot z=z \cdot ggT(a,b) für z \in \mathbb{Z} beschrieben werden.

Beispiel:
Gegeben sei die lineare diophantische Gleichung:

285 \cdot x + 81 \cdot y = 3 \\
Zuerst wir der Euklidische Algorithmus wie zuvor durchgeführt:

285 = 3 \cdot 81 +  42\\
81 = 1 \cdot 42 + 39 \\
42 = 1 \cdot 39 + 3 \\
39 = 3 \cdot 13 + 0 \\
Die Werte werden nun in eine Tabelle übertrage. Diese Tabelle erhält neben den Spalten für a, b und r noch zusätzlich die Spalten für die Werte q,  x und y. Die Spalte r spielt bei der Berechnung von x und y keine Rolle und kann auch weggelassen werden.

abqrxy
285813422-1-3 \cdot 2=-7
8142139-11-1 \cdot (-1)=2
42391310-1 \cdot 1=-1
39133001-3 \cdot 0=1
13010

Hierbei gilt für die Berechnungen der Werte für die Spalten x und y:

  • in die letzte Zeile wird immer für x=1 und y=0 eingetragen und
  • anschließend wird sich sukzessive Zeile für Zeile nach oben gearbeit, wobei gilt:

x=y_{alt} \ und \ y=x_{alt}-q \cdot y_{alt}

Als Lösung für das obige Beispiel gilt demnach:
L=\{(x,y) \ | \ \{2,-7\} \} \\
Probe: 285 \cdot 2 + 81 \cdot (-7)=3

In Python lassen sich die Werte für x und y sowie der ggT(285,81) wie folgt ermitteln:

def extgcd(a, b):
    x, y, xi, yi = 1, 0, 0, 1
    while b!=0:
        q=a//b
        a, b = b, a-q*b
        y, yi = yi, y-q*yi
        x, xi = xi, x-q*xi
    return a, x, y

if __name__ == '__main__':
    print("Werte a, x, y: ", extgcd(285, 81))