Wir haben in dieser Arbeit Secret-Sharing-Systeme eingeführt und als Spezialfall davon Schwellwertkryptosysteme betrachtet, die durch eine besondere Zugriffsstruktur ausgezeichnet sind, die sich in der Anwendung bewährt hat. Es handelt sich hierbei um Schwellwertzugriffsstrukturen, diese sind stets monoton.
Schwellwertsysteme zur Erzeugung von digitalen Signaturen nennt man Schwellwertsignaturschemata. Diese können auf ein bestimmtes asymmetrisches Kryptosystem beruhen, beispielsweise RSA, ElGamal, Paillier oder andere. In der vorliegen Arbeit haben wir das von Shoup beschriebene RSA-(k, l)−Schwellwertsignaturschema untersucht und seine Konstruktion konkretisiert und analysiert. Der Schwellwert k gibt sowohl die mindestens benötigte Anzahl der von den insgesamt l Spielern Beteiligten an, um eine gültige Signatur zu erzeugen. Gleichzeitig ist durch k−1 die maximale Anzahl möglicherweise von einem Angreifer kompromittierter Teilnehmer angegeben, damit das System sicher bleibt. Es sind daher insgesamt k−t ehrliche Spieler nötig, um eine sichere Signatur zu erstellen, t seien dabei die kompromittierten Spieler.
Es handelt sich bei dem beschriebenen Verfahren um ein RSA-Schwellwertsignaturschema, sowohl der öffentliche Schlüssel als auch der Verifikationsalgorithmus sind vom gleichen Format wie beim normalen RSA-Signaturverfahren. Lediglich kleine unterschiedliche Voraussetzungen an den Verschlüsselungsexponenten e und den RSA-Modulus n sind vorhanden. So muss etwa e > l eine Primzahl sein und n Produkt zweier Sophie- Germain-Primzahlen. Wir haben im Hauptteil die Protokolle zu den Fällen k = t+1 sowie k >t+1 angegeben und deren Sicherheit bewiesen. Ein sicheres Schwellwertsignaturschema muss robust und fälschungssicher sein. In den Sicherheitsbeweisen mussten wir teilweise ein Random-Oracle-Modell verwenden, teilweise mussten wir bestimmte Annahmen voraussetzen.
Im zweiten, allgemeineren Fall, konnte die Notation durch Elimination einer Variablen vereinfacht werden. Auch ist dieses Protokoll effizienter und stellt dadurch auch für den Spezialfall k = t + 1 eine gute Alternative dar. Dennoch ist der Beweis der Fälschungssicherheit aufwendiger zu führen.
Inhaltsverzeichnis
1 Einleitung
2 Mathematische Grundlagen
2.1 Notationen
2.2 Grundlagen der Algebra und Zahlentheorie
2.3 Grundlagen der Kryptografie
3 Schwellwertkryptosysteme
3.1 Secret-Sharing-Verfahren
3.2 Schwellwertsignaturverfahren
4 Das RSA-Schwellwertsignaturschema
4.1 Das RSA-Signaturschema
4.2 Das Protokoll zum Fall k = t + 1
4.3 Ein Beispiel
5 Sicherheitsbetrachtungen
5.1 Grundlagen zur Sicherheit
5.2 Sicherheit im Fall k = t + 1
6 Der Fall k ≥ t + 1
6.1 Das Protokoll zum Fall k ≥ t + 1
6.2 Ein Beispiel
6.3 Sicherheit im Fall k ≥ t + 1
7 Zusammenfassung und Ausblick
Zielsetzung & Forschungsschwerpunkte
Ziel dieser Arbeit ist die detaillierte Beschreibung und Analyse des von Victor Shoup entwickelten RSA-Schwellwertsignaturschemas. Dabei wird untersucht, wie eine digitale Signatur durch die Kooperation mehrerer Teilnehmer erzeugt werden kann, ohne dass ein einzelner Teilnehmer den vollständigen privaten Schlüssel erfährt, wobei die Robustheit und Fälschungssicherheit des Systems unter verschiedenen Annahmen, wie der RSA-Annahme und der Decisional-Diffie-Hellman-Annahme, bewiesen werden.
- Mathematische Grundlagen der Algebra, Zahlentheorie und Kryptografie als Basis für Schwellwertverfahren.
- Konstruktion und Funktionsweise des RSA-Schwellwertsignaturschemas für die Fälle k = t + 1 und k ≥ t + 1.
- Durchführung einer fundierten Sicherheitsanalyse inklusive Korrektheitsbeweisen und Zero-Knowledge-Eigenschaften.
- Vergleich der Effizienz und Komplexität der vorgestellten Protokolle.
Auszug aus dem Buch
4.2 Das Protokoll zum Fall k = t + 1
Das RSA-Schwellwertsignaturverfahren wurde von Shamir eingeführt und basiert auf dem bekannten RSA-Kryptosystem. Shoup entwickelte es weiter. Der Fall k = t + 1 wurde bereits vor Shoup betrachtet. Im Folgenden werden wir Shoups Protokoll des (k,l)−Schwellwertsignaturschemas erläutern (vgl. [32]):
Der Spielleiter wählt zufällig zwei große Primzahlen gleicher Länge (z. B. 512 bit) p und q, wobei p = 2p + 1 und q = 2q + 1, und p, q selbst Primzahlen sind, sogenannte Sophie-Germain-Primzahlen. Damit heißen p, q sichere Primzahlen. Daraus berechnet sich das RSA-Modul n = pq sowie m = p'q'.
Die Primzahlen finden sich durch zufälliges Auswählen und Anwenden eines Primzahltests (z. B. Fermatscher Primzahltest, Solovay-Strassen-Test oder Rabin-Miller-Test, vgl. [2], [23]). Hat man schließlich eine Primzahl p gefunden, so berechnet man p' und testet, ob es sich wieder um eine Primzahl handelt.
Kapitelzusammenfassungen
1 Einleitung: Motivation und theoretischer Hintergrund für die Entwicklung von Schwellwertsignaturschemata zur Erschwerung von Kryptoanalysen.
2 Mathematische Grundlagen: Zusammenstellung der benötigten Notationen und Definitionen aus Algebra, Zahlentheorie und Kryptografie.
3 Schwellwertkryptosysteme: Definition von Zugriffsstrukturen und Einführung von Secret-Sharing-Verfahren sowie deren Erweiterung zu Schwellwertsystemen.
4 Das RSA-Schwellwertsignaturschema: Konstruktion des RSA-Signaturschemas und Vorstellung der Protokolle für den Fall k = t + 1.
5 Sicherheitsbetrachtungen: Detaillierte Sicherheitsanalyse einschließlich Robustheit, Fälschungssicherheit und der Nutzung des Random-Oracle-Modells.
6 Der Fall k ≥ t + 1: Erweiterung des Protokolls auf den allgemeinen Fall und Durchführung der entsprechenden Sicherheitsbetrachtungen.
7 Zusammenfassung und Ausblick: Resümee der erzielten Ergebnisse und ein Ausblick auf alternative Signaturverfahren.
Schlüsselwörter
RSA-Kryptosystem, Schwellwertsignaturschema, Secret-Sharing, digitale Signatur, Zugriffsstruktur, Sicherheitsanalyse, Korrektheitsbeweis, Random-Oracle-Modell, Robustheit, Fälschungssicherheit, Decisional-Diffie-Hellman-Annahme, Primfaktorzerlegung, Kryptografie, Algebra, Zahlentheorie
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die mathematische Konstruktion und Sicherheitsanalyse von RSA-Schwellwertsignaturschemata, die es erlauben, digitale Signaturen sicher durch mehrere Parteien zu erstellen.
Was sind die zentralen Themenfelder?
Die zentralen Felder umfassen Schwellwertkryptografie, RSA-basierte Signaturverfahren, Secret-Sharing und die formale Sicherheitsbewertung dieser Protokolle.
Was ist das primäre Ziel oder die Forschungsfrage?
Ziel ist die detaillierte Beschreibung des Shoup-Protokolls für Schwellwertsignaturen und der Beweis, dass dieses System unter spezifischen kryptografischen Annahmen robust und fälschungssicher ist.
Welche wissenschaftliche Methode wird verwendet?
Es werden klassische kryptografische Beweismethoden verwendet, insbesondere Korrektheitsbeweise (proof of correctness) und Sicherheitsnachweise innerhalb des Random-Oracle-Modells.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die Einführung des RSA-Signaturschemas, das detaillierte Protokoll für den Spezialfall k = t + 1, die Sicherheitsanalyse und die Verallgemeinerung für den Fall k ≥ t + 1.
Welche Schlüsselwörter charakterisieren die Arbeit?
RSA, Schwellwertsignatur, Secret-Sharing, Sicherheitsanalyse, Random-Oracle-Modell, Robustheit und Fälschungssicherheit.
Warum ist das RSA-Schwellwertsignaturschema robuster als frühere Verfahren?
Frühere Verfahren lieferten oft keine rigorose Sicherheitsanalyse und basierten auf interaktiven Beweismethoden, während das Shoup-Verfahren nicht-interaktiv ist und eine formale Sicherheitsreduktion bietet.
Welche Rolle spielt das Random-Oracle-Modell in dieser Arbeit?
Es dient als Beweistechnik, um die kryptologischen Hashfunktionen in den Protokollen zu simulieren und damit die Sicherheit der Signaturteile und Korrektheitsbeweise formal nachzuweisen.
- Quote paper
- Vanessa Buhrmester (Author), 2018, Das RSA-Schwellwertsignaturschema, Munich, GRIN Verlag, https://www.grin.com/document/437019
