Universität des Saarlandes FR 6.1 Mathematik Prof. Dr. F.-O. Schreyer

Tel.: +49 (0)681/302-2785 schreyer@math.uni-sb.de Zi. 317, Geb. 27 D-66123 Saarbrücken

Kryptographie - algebraischer Hintergrund

News

 Mapleskripte zum diskreten Logarithmus (Babystep-Giantstep, Silver-Pohlig-Hellman, Rho-Methode, Indexcalculus) .

 Mapleskripte zur Konstruktion von F_p^k , zum Zählen der Punkte einer elliptischen Kurve über F_p^k und zur Weilformel.

 Übungsblatt 7

Thema

Kryptographie ist für den modernen Informationsaustausch unerlässlich, insbesondere die sogenannten "Public Codes''. Das bekannteste Verfahren "RSA'' beruht auf der Schwierigkeit, grosse Zahlen in Primfaktoren zu zerlegen.

In der Vorlesung werden dieses und andere Verfahren, wie elliptische Kurven Kryptographie und Angriffe auf diese Systeme besprochen.

Die Vorlesung richtet sich in erster Linie an Informatikstudenten im Hauptstudium.

Literatur

Vorlesungen

Die Vorlesungen finden donnerstags 11-13 Uhr im HS 003, Gebäude 45 Informatik statt.

Übungen

Die Übungen sind jeweils dienstags 16:00-17:30 Uhr im Seminarraum 7, Gebäude 27 Mathematik.

Bei Fragen zu den Übungen steht Ihnen zur Verfügung:

Übungsblatt 1 (Enigma):

Das Mapleskript enigma.mws simuliert eine Enigma-Maschine.
Diese soll mit einem möglichst geringen Anteil von bekanntem Klartext geknackt werden.

Übungsblatt 2 (RSA und Faktorisierung):

Übungsblatt:     
blatt2.ps         blatt2.pdf         html

Textfile mit den zu faktorisierenden Zahlen für Aufgabe 2 und dem RSA-Schlüsseltext und dem öffentlichen Schlüssel für Aufgabe 3:
blatt2.txt

Mapleskript für die Pollardsche (p-1)-Methode:
pollard.mws

Mapleskript für die Fermat-Faktorisierung:
fermat.mws

Mapleskript für das quadratische Sieb:
qsieb.mws

Ein einfaches RSA-Skript für Maple
rsa.mws
 

Übungsblatt 3 (Elliptische Kurven und Faktorisierung):

Ein kleine Maple-Einführung:
maple.mws

Übungsblatt:     
blatt3.ps         blatt3.pdf         html

Plots von einigen elliptischen Kurven und singulären Kurven von Grad 3:
ecplots.mws

Mapleskripte zum Übungsblatt:
Berechnen und Zählen der Punkte einer elliptischen Kurve über Fp, Test des Satzes von Hasse
punkte.mws

Addition auf einer elliptischen Kurve, schnelles Potenzieren, Bestimmen der Anzahl der Punkte einer elliptischen Kurve mit dem Satz von Hasse
add_pot_hasse.mws

Elliptische-Kurven-Faktorisierung
ecf.mws

Übungsblatt 4 (Elementare Elliptische-Kurven-Kryptographie):

Übungsblatt:     
blatt4.ps         blatt4.pdf         html

Maple-Skript zum klassischen ElGamal-Kryptosystem und zu ElGamal auf elliptischen Kurven, inklusive Codierung von Textnachrichten als Punkte einer elliptischen Kurve:
ECelgamal.mws

Übungsblatt 5 (Endliche Körper und Quadratische Reziprozität):

Übungsblatt:     
blatt5.ps         blatt5.pdf         html

Naives Aufzählen der irreduziblen Polynome über F_p:
irreduzible.mws

Konstruktion von F_p^k:
Fpk.mws

Zählen der Punkte auf einer elliptischen Kurve mit dem Legendresymbol und Vergleich mit der aus dem Satz von Hasse abgeleiteten Methode:
ECLegendre.mws

Übungsblatt 6 (Der Hintergrund von Hasses Theorem):

Übungsblatt:     
blatt6.ps         blatt6.pdf         html

Zählen der Punkte einer elliptischen Kurve über F_p^k, Bestimmung der N_k aus N_1 mit der Weilformel durch Potenzreihenentwicklung der logarithmischen Ableitung der Zetafunktion und mit dem Corollar zur Weilformel:
EC_Fpk.mws

Zetafunktion einer Kurve vom Grad 4:
deg4.mws

Übungsblatt 7 (Diskrete Logarithmen):

Übungsblatt:     
blatt7.ps         blatt7.pdf         html

Implementation des Babystep-Giantstep-Algorithmus zur Berechnung von diskreten Logarithmen für eine allgemeine Gruppe und Test für Fp* und elliptische Kurven:
bsgs_log.mws

Das Pohlig-Silver-Hellman-Verfahren zur Reduktion des DL-Problems in Fp* auf Primpotenzordnung und Primzahlordnung bei bekannter Faktorisierung der Gruppenordung:
sph_log.mws

Pollards Rho-Methode zur DL-Berechnung in Fp* (Speicherung des Folgeelements Nr. 2^j bei der Berechung der Folgeelemente Nr. 2^j+1,...,2^(j+1)):
rho_log.mws

Das Index-Calculus-Verfahren zur DL-Berechnung in Fp* ;
index_log.mws

  Hauptseite der Fachrichtung   Arbeitsgruppe Frank-Olaf Schreyer