Was ist rabin?

Rabin-Kryptosystem

Das Rabin-Kryptosystem ist ein asymmetrisches Verschlüsselungsverfahren, dessen Sicherheit auf der Schwierigkeit der Integer-Faktorisierung basiert. Es wurde von Michael O. Rabin im Jahr 1979 entwickelt. Es ist ein Vorläufer des RSA-Kryptosystems und weist einige Ähnlichkeiten auf, allerdings mit dem Unterschied, dass seine Entschlüsselung deterministisch schwierig, aber nicht eindeutig ist.

Schlüsselgenerierung:

1. Wähle zwei große Primzahlen p und q. Diese sollten kongruent zu 3 mod 4 sein (p ≡ q ≡ 3 mod 4).
2. Berechne n = p * q. n ist der öffentliche Schlüssel, während p und q der private Schlüssel sind.

Verschlüsselung:

Um eine Nachricht m zu verschlüsseln (0 <= m < n):

1. Berechne c = m² mod n. c ist der Chiffretext.

Entschlüsselung:

Um den Chiffretext c zu entschlüsseln:

1. Berechne die Quadratwurzeln von c modulo p und q. Da p ≡ q ≡ 3 mod 4 sind, kann dies effizient mit den folgenden Formeln geschehen:

   • m_p = c^(p+1)/4 mod p
   • m_q = c^(q+1)/4 mod q

2. Verwende den Chinesischen Restsatz (CRT), um die vier möglichen Lösungen für m mod n zu finden:

   • m₁ = (m_p * q * (q^-1 mod p) + m_q * p * (p^-1 mod q)) mod n
   • m₂ = (m_p * q * (q^-1 mod p) - m_q * p * (p^-1 mod q)) mod n
   • m₃ = (-m_p * q * (q^-1 mod p) + m_q * p * (p^-1 mod q)) mod n
   • m₄ = (-m_p * q * (q^-1 mod p) - m_q * p * (p^-1 mod q)) mod n

3. Eine der vier Lösungen ist die ursprüngliche Nachricht m. Es ist notwendig, zusätzliche Informationen zu haben oder zu kennen, um die richtige Lösung zu identifizieren.

Sicherheit:

Die Sicherheit des Rabin-Kryptosystems ist äquivalent zur Integer-Faktorisierung. Das heißt, das Brechen des Rabin-Kryptosystems ist genauso schwierig wie das Faktorisieren großer Zahlen.

Nachteile:

• Nicht-Eindeutigkeit der Entschlüsselung: Die Entschlüsselung liefert vier mögliche Klartexte. Dies erfordert zusätzliche Informationen zur Identifizierung der korrekten Nachricht.
• Anfälligkeit für gewählte Chiffretext-Angriffe: Ohne sorgfältige Padding-Schemata kann das Rabin-Kryptosystem anfällig für gewählte Chiffretext-Angriffe sein.

Verwendung:

Obwohl das Rabin-Kryptosystem theoretisch interessant ist, wird es aufgrund der Entschlüsselungsmehrdeutigkeit und der Anfälligkeit für Angriffe in der Praxis weniger häufig verwendet als beispielsweise RSA. Es wird jedoch gelegentlich in speziellen Anwendungen eingesetzt, in denen die Mehrdeutigkeit der Entschlüsselung durch geeignete Protokolle und Padding-Schemata behoben werden kann.