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 $(G_{1},+),(G_{2},+),(G_{3},\cdot )$ Gruppen der primen Ordnung $p\in N$. Ein Pairing ist eine $Z_{p}$-bilineare Abbildung $e:G_{1}\times G_{2}\longrightarrow G_{3}$ zwischen $Z_{p}$-Moduln für die die folgenden zwei Realismus-Bedingungen gelten:

1. $e$ ist nicht degeneriert (d.h. $\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. $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 $e:G_{1}\times G_{2}\longrightarrow G_{3}$ in obigem Sinne und gegebenen Werten $P,Q,aP,bP,aQ,cQ$ für $a,b,c\in Z_{p}^{*}$ und $P\in G_{1},Q\in G_{2}$ nur äußerst schwer (d.h. nicht effizient) möglich ist, den Wert $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 $m$ zukommen lassen möchte. Des Weiteren besitze der Empfänger B eine eindeutige Identifikation $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 $P$ und einen Master Key $s$ (den sog. Secret Server Key). Mithilfe dieser Daten und der $ID$ kann ein Sender A nun eine Nachricht $m$ zu einem Kryptotext $c$ verschlüsseln (Encrypt) und an B senden. Damit der Empfänger diese Nachricht lesen kann, benötigt er einen privaten Schlüssel $K_{ID}$. Diesen erhält er vom PKG, welche den privaten Schlüssel auf der Basis von $P,s$ und $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 $c$ mithilfe seines privaten Schlüssels $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 $K_{ID}$ anfordert.
• Input: P, s, ID.
• Output: $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, $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 $G_{1},G_{2},G_{3}$ Gruppen primer Ordnung $p$ und $e:G_{1}\times G_{2}\longrightarrow G_{3}$ ein Pairing. Des Weiteren sei $ID\in \{0,1\}^{*}$ ein Identitätsstring des Empfängers A (etwa seine binär codierte E-Mailadresse) und $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:

• $H_{1}:\{0,1\}^{*}\longrightarrow Z_{p}^{*}$
• $H_{2}:G_{3}\longrightarrow \{0,1\}^{n}$
• $H_{3}:G_{3}\times \{0,1\}^{n}\times G_{1}\times G_{1}\longrightarrow Z_{p}^{*}$

Primitiven

Generation

P-BB1-G($M$)

• $r_{0}\in _{R}Z_{p}^{*}$.
• $i:=s_{1}s_{2}+r_{0}(s_{1}M+s_{3})$.
• $K_{0,M}:=iQ_{2}$.
• $K_{1,M}:=r_{0}Q_{2}$.
• return $(K_{0,M},K_{1,M})$.

Encryption

P-BB1-E($r$)

• $E_{0}:=rQ_{1}$.
• $E_{1}:=(rM)R+rT$.
• $B:=V^{r}$.
• return $(E_{0},E_{1},B)$.

Decryption

P-BB1-D($E_{0},E_{1},(K_{0,M},K_{1,M}$)

• $B:=e(E_{0},K_{0,M})\cdot e(E_{1},K_{1,M})^{-1}$
• return $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.