Identity-based public key cryptography based on pairings

Einleitung

Identity-based Public Key Kryptographie ist eine Form der wohlbekannten Publick Key Kryptographie. Hierbei besteht der öffentliche Schlüssel aus einer eindeutigen ID, welche einem potentiellen Empfänger zugeordnet wird bzw. werden kann (z.B. seine E-Mailadresse).

Erstmals vorgeschlagen von Adi Shamir (1984) bietet ID basierte Kryptographie die Möglichkeit, Nachrichten zu verschlüsseln, zu signieren etc., ohne als Sender A die Authentizität des zum Empfänger B gehörenden öffentlichen Schlüssels sicherstellen zu müssen. Handelt es sich etwa bei der ID um die E-Mailadresse des gewünschten Empfängers, so ist klar, dass dieser öffentliche Schlüssel zum entsprechenden Empfänger gehört.

Parings stellen spezielle Formallismen dar, mithilfe derer Protokolle formuliert werden können, welche die Idee der Identitätsbasierten Kryptografie implementieren.

Im IEEE Draft P1363.3 werden explizite Protokolle für verschiedene Anwendungen ID basierter Kryptographie basierend auf Pairings vorgestellt (dazu gehören vor allem: Verschlüsselung (IBE), Key Encapsulation und Signierung).

Pairings

Definition

Seien Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (G_1, +), (G_2, +), (G_3, \cdot)} Gruppen der primen Ordnung Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p \in N} . Ein Pairing ist eine Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z_p} -bilineare Abbildung Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e : G_1 \times G_2 \longrightarrow G_3} zwischen Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z_p} -Moduln für die die folgenden zwei Realismus-Bedingungen gelten:

1. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e} ist nicht degeneriert (d.h. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \forall P \neq 0_{G_1} \in G_1,Q \neq 0_{G_2} \in G_2: \ e(P,Q) \neq 1_{G_3}} ).
2. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e} ist effizient berechnenbar.

Hintergrund

Die Motivation in der Benutzung solcher Pairings liegt im Wesentlichen in der Bilinear-Diffie-Hellman Assumption (BDH). Diese besagt, dass es für ein Pairing Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e : G_1 \times G_2 \longrightarrow G_3} in obigem Sinne und gegebenen Werten Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P,Q,aP,bP,aQ,cQ} für Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b,c \in Z_p^*} und Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P \in G_1, Q \in G_2} nur äußerst schwer (d.h. nicht effizient) möglich ist, den Wert Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e(P,Q)^{abc}} zu berechnen.

Diese Eigenschaft ist essentiell für IBE Protokolle, welche solche Pairings benutzen, da die Sicherheits solcher Protokolle darauf zurückgeführt werden kann.

Beispiel

Eine konkrete Anwendung von IBE basierend auf Pairings ist die Elliptic Curve Cryptgraphy (ECC).

IBE

Szenario

In der Identity Based Encryption (IBE) betrachtet man das Szenario, indem ein Sender A einem Empfänger B eine verschlüsselte Nachticht Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} zukommen lassen möchte. Des Weiteren besitze der Empfänger B eine eindeutige Identifikation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ID} (z.B. seine E-Mailadresse). Als dritter Teilnehmer einer IBE wird eine Trusted Third Party benötigt, welche häufig als Private Key Generator (PKG) bezeichnet wird.

IBE-Protokollaufbau und Ablauf

Ein IBE Protokoll hat zumeist vier Basisalgorithmen. In der ersten Phase (Setup) initialisiert sich die PKG und erzeugt zum einen eine Menge öffentlicher Parameter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} und einen Master Key Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s} (den sog. Secret Server Key). Mithilfe dieser Daten und der Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ID} kann ein Sender A nun eine Nachricht Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} zu einem Kryptotext Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c} verschlüsseln (Encrypt) und an B senden. Damit der Empfänger diese Nachricht lesen kann, benötigt er einen privaten Schlüssel Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_{ID}} . Diesen erhält er vom PKG, welche den privaten Schlüssel auf der Basis von Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P, s} und Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ID} berechnet (diese Phase wird als Extract bezeichnet) und anschließend über einen sicheren Kanal an B sendet. Schließlich kann der Empfänger B den durch A übermittelten Kryptotext Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c} mithilfe seines privaten Schlüssels Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_{ID}} entschlüsseln (Decrypt).

Im folgenden noch einmal die vier relevanten Algorithmen im Überblick.

1. Setup

• Wird vom PKG ausgeführt.
• Initialisiert den PKG (Bereitstellung öffentlicher Parameter und Generierung des zugehörigen privaten Secret Server Key).
• Output: P (öffentliche Parameter), s (Secret Server Key).

2. Extract

• Wird vom PKG ausgeführt.
• Wird ausgeführt, sobald Empfänger B seinen privaten Schlüssel Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_{ID}} anfordert.
• Input: P, s, ID.
• Output: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_{ID}} (zur Identität ID gehöriger privater Schlüssel).

3. Encrypt

• Wird vom Sender A ausgeführt.
• Input: P, ID, m (Klartext).
• Output: c (Kryptotext - verschlüselte Nachricht).

4. Decrypt

• Wird vom Empfänger B ausgeführt.
• Input: P, ID, c, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_{ID}} .
• Output: m.

Zumeist ist es hilfreich, wenn bestimmte Basisalgorithmen (sogenannte Primitiven) aus den o.g. Algorithmen ausgelagert werden. Zumeist stellt man hierbei den Basisalgorithmen die Primitiven "Generation", "Encryption" und "Decryption" bereit, wobei die Primitive "Generation" im Basisalgorithmus "Extract" benutzt wird.

Beispiel: ein IBE Protokoll (BB1-IBE)

Einordnung

Das BB1-IBE Protokoll wurde von Dan Boneh und Xavier Boyen entwickelt. Das BB1-IBE ist ein Protokoll, welches IEEE Draft P1363.3 aufgeführt ist und damit ein Beispiel-Protokoll, welches identitätsbasierte Verschlüsselung mithilfe von Pairings möglich macht. Die Sicherheit des Protokoll beruht im Wesentlichen auf dem Bilinear-Diffie-Hellman Problem (BDH). Wie jedes der im IEEE Draft P1363.3 aufgeführten IBE-Protokolle beseht das BB1-IBE Protokoll aus vier Alogirthmen: Setup, Extract, Encrypt and Decrypt.

Basisparameter

Es seien Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_1, G_2, G_3} Gruppen primer Ordnung Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} und Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e : G_1 \times G_2 \longrightarrow G_3} ein Pairing. Des Weiteren sei Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ID \in \{0,1\}^*} ein Identitätsstring des Empfängers A (etwa seine binär codierte E-Mailadresse) und Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m \in \{0,1\}^n} eine Klartextnachricht, welche von A an B gesendet werden soll.

Zur Formulierung der Algorithmen des BB1-IBE-Protokolls werden zusätzlich drei Hash-Funktionen benötigt:

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H_1 : \{0,1\}^* \longrightarrow Z_p^*}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H_2 : G_3 \longrightarrow \{0,1\}^n}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H_3 : G_3 \times \{0,1\}^n \times G_1 \times G_1 \longrightarrow Z_p^*}

Primitiven

Generation

P-BB1-G(Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} )

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r_0 \in_R Z_p^*} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i := s_1s_2 + r_0(s_1M + s_3)} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_{0,M} := iQ_2} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_{1,M} := r_0Q_2} .
• return Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (K_{0,M}, K_{1,M})} .

Encryption

P-BB1-E(Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r} )

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E_0 := rQ_1} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E_1 := (rM)R + rT} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B := V^r} .
• return Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (E_0, E_1, B)} .

Decryption

P-BB1-D(Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E_0, E_1, (K_{0,M}, K_{1,M}} )

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B := e(E_0, K_{0,M}) \cdot e(E_1, K_{1,M})^{-1}}
• return Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} .

Algorithmen

Setup

1. PKG wählt einen master key

• $s:=(s_{1},s_{2},s_{3})\in _{R}Z_{p}^{*}\times Z_{p}^{*}\times Z_{p}^{*}$.

2. PKG generiert öffentliche Parameter $P:=(Q_{1},Q_{2},R,T,V,G_{1},G_{2},e)$, wobei

• $Q_{i}$ ist Erzeuger von $G_{i}$, $i=1,2$, d.h. $\left\langle Q_{i}\right\rangle =G_{i}$,
• $R:=s_{1}Q_{1}$,
• $T:=s_{3}Q_{1}$,
• $V:=e(R,s_{2}Q_{2})$.

Extract

1. $M:=H_{1}(ID)$.
2. $K_{ID}:=(K_{0,M},K_{1,M})\longleftarrow {\texttt {P-BB1-G}}(M)$.

$K_{ID}$ ist der private Schlüssel des Empfängers B.

Encrypt

1. $r\in _{R}Z_{p}^{*}$.
2. $(B,E_{0},E_{1})\longleftarrow {\texttt {P-BB1-E}}(r)$.
3. $Y:=H_{2}(B)\oplus m$.
4. $t:=r+H_{3}(B,Y,E_{0},E_{1})$.
5. $c:=(Y,E_{0},E_{1},t)$.

$c$ ist der Kryptotext. $B$ heißt blinding factor.

Decrypt

1. $B\longleftarrow {\texttt {P-BB1-D}}(E_{0},E_{1},K_{\rm {ID}})$.
2. $r:=t-H_{3}(B,Y,E_{0},E_{1})$.
3. ${\texttt {if}}\ \neg (B==V^{r}\ {\texttt {and}}\ E_{0}==rQ_{1})\ {\texttt {then}}\ {\texttt {exit}}\ {\texttt {with}}$ "`error"'.
4. $m:=Y\oplus H_{2}(B)$.

$m$ ist der Klartext.

Vor- und Nachteile

Vorteile

• IBE benötigt keine Public-Key-Distribution Infrastruktur, denn der öffentliche Schlüssel in Form der ID ist dem Sender in der Regel wohlbekannt. Zudem ist die Zugehörigkeit der ID zum Empfänger per Annahme eindeutig und nicht fälschbar (etwa die E-Mailadresse).

• IBE benötigt (wie jede andere PKI) keinen Schlüsselaustausch (dies ist natürlich ein Vorteil jedes Public Key Verfahrens).

• IBE bietet einige interessante Anwendungen, welche in gewissem Sinne als Nebenprodukt abfallen. So ist es z.B. denkbar, dass der Empfänger in die ID, welche er zum Verschlüsseln der Nachricht benutzt, zusätzliche Informationen Encodiert. Denkbar wäre hier z.B. ein Ablaufdatum (expiration date) der Nachricht.

Nachteile

• Natürlich hat der PKG sämtliche Möglichkeiten, Nachrichten unauthorisiert zu entschlüsseln, zu verändern etc. Dementsprechend muss es sich beim PKG um eine höchst vertrauenswürdige Instanz handeln.

• Zum Austausch des privaten Schlüssels zwischen PKG und Empfänger in der Extract-Phase wird ein sicherer Kanal (z.B. SSL verschlüsselt) benötigt.

Quellen

• [1]: IEEE P1636.3/D1 Draft Standard for Identity-based Public-key Cryptography Using Pairings.

• [2] Wikipedia-Artikel zu "Identity Based Encryption".

• Adi Shamir: "Identity-Based Cryptosystems and Signature Schemes. Advances in Cryptology: Proceedings of CRYPTO 84", Lecture Notes in Computer Science 7, 1984.

• D. Boneh, X. Boyen: "Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles", Advances in Cryptology – Eurocrypt, 2004, Springer-Verlag (2004), pp. 223–238.