Benutzer:Bananenfalter/Sicherheit (Kryptografie)

Arbeitsversion: Sicherheit (Kryptografie)

Die Sicherheit eines kryptografischen Systems ist dadurch definiert, welchen Angreifern es maximal standhält. Man unterscheidet insbesondere die Sicherheitsklassen informationstheoretisch sicher und kryptografisch (auch: komplexitätstheoretisch) sicher.

Angreifermodelle

→ Hauptartikel: Angreifermodelle (Kryptoanalyse)

Ein Angreifer kann

allmächtig,
komplexitätstheoretisch unbeschränkt oder
komplexitätstheoretisch beschränkt sein.

Gegen einen allmächtigen Angreifer ist kein Kraut gewachsen, denn er hat Zugriff auf alle Komponenten des Systems. Er kann sämtliche Daten erfassen, verändern oder zerstören, wann und wo er möchte.^[1]

Ist ein Angreifer komplexitätstheoretisch unbeschränkt, so bedeutet dies, dass ihm beliebige Rechenkapazität zur Verfügung steht. Ein komplexitätstheortisch beschränkter Angreifer hat dagegen nur begrenzte Rechenkapazität.

Informationstheoretische Sicherheit

Ein System zum Verschlüsseln von Nachrichten (Konzelationssystem) ist dann informationstheoretisch sicher, wenn ein Angreifer bei vorliegendem Schlüsseltext nicht mehr über den Klartext erfährt, als er ohnehin weiß.^[2] Das heißt ein Angreifer mit unbegrenzter Rechenleistung kann aus dem Schlüsseltext keine Informationen über den Inhalt des Klartextes gewinnen. Damit ist die Wahrscheinlichkeit, dass ein bestimmter Klartext $x$ verschlüsselt wurde ohne und mit Kenntnis des Schlüsseltextes $s$ gleich^[1]:

\forall s\in S\quad \forall x\in X:W(x)=W(x|s)

Es sind $S$ die Menge aller Schlüsseltexte und $X$ die Menge aller Klartexte.

Der verwendete Schlüssel muss mindestens so lang sein, wie der Klartext. Nur dann kann jede Nachricht in jeden beliebigen Schlüsseltext verschlüsselt werden. Einige Autoren verwenden die Begriffe ideale Konzelation, perfekte Konzelation und unbedingte Konzelation analog zur informationstheoretischen Sicherheit.^[1]

Ein informationstheoretisch sicherer MAC kann nur mit einem Schlüssel erzeugt werden, der mindestens doppelt so lang ist, wie die Nachricht. Setzt man für jedes Nachrichtenzeichen genau zwei Schlüsselzeichen ein, so ist die Wahrscheinlichkeit, dass ein Angreifer den MAC zu einem gefälschten Nachrichtenzeichen richtig rät genau ${\tfrac {1}{2}}$ .

Kryptografische Sicherheit

Ein System heißt kryptografisch sicher, falls unter bestimmten Annahmen bewiesen werden kann, dass es keinen effizienten (schnellen) Algorithmus zum Brechen des Systems gibt. Damit ist es nur gegen einen komplexitätstheoretisch beschränkten Angreifer sicher.

Kryptografisch sichere Systeme bauen überwiegend auf folgende Annahmen aus der Komplexitätstheorie auf:

Faktorisieren ist schwer: Das heißt es gibt keinen Algorithmus, der jede beliebige ganze Zahl $n$ mit polynomialem Zeitaufwand in ihre Primfaktoren $n=p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$ zerlegt.
Wurzelziehen in $\mathbb {Z} /n$ ist schwer: Es lässt sich beweisen, dass Wurzelziehen modulo $n$ genau so schwer ist wie Faktorisieren.
Entscheiden ob eine Zahl quadratischer Rest in $\mathbb {Z} /n$ ist, ist schwer: Es gibt keinen Algorithmus der für eine Zahl $s\in \mathbb {Z} /n$ mit polynomialem Zeitaufwand entscheidet, ob es eine Zahl $w\in \mathbb {Z} /n$ gibt für die $w^{2}\equiv s{\pmod {n}}$ gilt.
Logarithmen ziehen in $(\mathbb {Z} /n)^{\times }$ ist schwer: Die Diskreter-Logarithmus-Annahme geht davon aus, dass es keinen Algorithmus gibt, der aus einer Zahl $h\equiv g^{a}{\pmod {n}}$ mit $g$ Primitivwurzel in $(\mathbb {Z} /n)^{\times }$ in polynomialer Zeit $a$ berechnen kann.

Die genannten Algorithmen müssen dabei auf ihre Laufzeit im günstigsten Fall und nicht wie in der Komplexitätstheorie üblich auf Worst-Case-Komplexität untersucht werden. Es muss in jedem Fall gewährleistet sein, dass das System gleich schwer zu brechen ist.^[2]

Weniger sichere Systeme

Weitere Klassen mit geringeren Sicherheitsanforderungen wären beispielsweise^[3]

wohluntersucht,
wenig untersucht und
geheim gehalten.

Viele der bekannten Kryptosysteme (z. B. RSA und AES) gehören zur Klasse der wohluntersuchten Verfahren. Sie beruhen nicht beweisbar auf einer der schwächeren Annahmen aus der Klasse kryptografisch starker Systeme. Einige dieser stärkeren Annahmen lassen sich aber vermutlich auf schwächere Annahmen, wie die Faktorisierungs-Annahme, zurückführen.

Als besonders unsicher können kryptografische Systeme geltern, deren Sicherheit auf Geheimhaltung beruht. Das Problem besteht besonders darin, dass die Systeme nicht von einer Vielzahl unabhängiger Experten untersucht werden können. Man bezeichnet dieses Prinzip auch als Security by Obscurity. Gemäß Kerckhoffs’ Prinzip sollte ein kryptografisches Verfahren nicht auf Geheimhaltung des Algorithmus beruhen.

Sicherheit einzelner kryptografischer Systeme

Die Tabelle zeigt die Einordung konkreter kryptografischer Systeme in die drei wichtigsten Sicherheitsklassen. Es gilt dabei, dass informationstheoretisch sichere Systeme auch kryptografisch sicher sind. Kryptografisch sichere Systeme sind auch wohluntersucht.

	Konzelation		Authentikation		Sonstige
	symmetrisch	asymmetrisch	symmetrisch	asymmetrisch	Sonstige
informationstheoretisch sicher	One-Time-Pad	nicht möglich	MAC	nicht möglich	DC-Netz, Shamirs Secret-Sharing
kryptografisch sicher	One-Time-Pad mit Pseudozufallsgenerator (Pseudo-One-Time-Pad)	Rabin		GMR	MIX-Netz
wohluntersucht	DES, Triple-DES, AES (Rijndael), Blowfish, Twofish	RSA, Elgamal	DES	RSA, DSA

Asymmetrische informationstheoretisch sichere Verfahren sind nicht möglich, da ein Angreifer mit unbegrenzter Rechenkapazität aus dem öffentlich bekannten Schlüssel den privaten Schlüssel berechnen kann.^[1]

Weblinks

Wikibooks: Äquivalente Definitionen informationstheoretischer Sicherheit – Lern- und Lehrmaterialien

Einzelnachweise

↑ ^a ^b ^c ^d Andreas Pfitzmann: Vorlesungsskript Sicherheit in Rechnernetzen 2000, S.13ff, S.45 und S.49ff (als PDF)
↑ ^a ^b A. Menezes, P. van Oorschot und S. Vanstone: Handbook of Applied Cryptography, CRC Press 1996 S.42f (Kapitel als PS und PDF)
↑ Heiko Mittas: Seminararbeit Sicherheit von Kryptosystemen, 2001 (als PDF)

[[Kategorie:Kryptologie]]

[Pfitzmann00-1] Andreas Pfitzmann: Vorlesungsskript Sicherheit in Rechnernetzen 2000, S.13ff, S.45 und S.49ff (als PDF)

[Menezes96-2] A. Menezes, P. van Oorschot und S. Vanstone: Handbook of Applied Cryptography, CRC Press 1996 S.42f (Kapitel als PS und PDF)

[Mittas-3] Heiko Mittas: Seminararbeit Sicherheit von Kryptosystemen, 2001 (als PDF)

[1]

[2]

[3]