Identity-based public key cryptography based on pairings: Difference between revisions

From
Jump to navigation Jump to search
 
(15 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Einleitung ==
== Einleitung ==


'''Identity-based Public Key Kryptographie''' ist eine Form der wohlbekannten Publick Key Kryptographie. Hierbei besteht der öffentliche Schlüssel eines Empfängers aus einer eindeutigen ID, welche B zugeordnet wird bzw. werden kann (z.B. eine E-Mailadresse).
'''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).


Zuerst vorgeschlagen von Adi Shamir (1984) bietet ID basierte Kryptographie die Möglichkeit Nachrichten verschlüsselt zu versenden, ohne als Sender A die Authentizität des zu B gehörenden öffentlichen Schlüssels sichergestellen 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.
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.
'''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).
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).
Line 14: Line 14:
Seien <math>(G_1, +), (G_2, +), (G_3, \cdot)</math> Gruppen der primen Ordnung <math>p \in N</math>. Ein '''Pairing''' ist eine <math>Z_p</math>-bilineare Abbildung <math>e : G_1 \times G_2 \longrightarrow G_3</math> zwischen <math>Z_p</math>-Moduln für die die folgenden zwei Realismus-Bedingungen gelten:
Seien <math>(G_1, +), (G_2, +), (G_3, \cdot)</math> Gruppen der primen Ordnung <math>p \in N</math>. Ein '''Pairing''' ist eine <math>Z_p</math>-bilineare Abbildung <math>e : G_1 \times G_2 \longrightarrow G_3</math> zwischen <math>Z_p</math>-Moduln für die die folgenden zwei Realismus-Bedingungen gelten:


1. <math>e</math> ist nicht degeneriert (d.h. <math>\forall P \neq 0_{G_1} \in G_1,Q \neq 0_{G_2} \in G_2: \ e(P,Q) \neq 1_{G_3}</math>)<br />
1. <math>e</math> ist nicht degeneriert (d.h. <math>\forall P \neq 0_{G_1} \in G_1,Q \neq 0_{G_2} \in G_2: \ e(P,Q) \neq 1_{G_3}</math>).<br />
2. <math>e</math> ist effizient berechnenbar.
2. <math>e</math> ist effizient berechnenbar.


===Hintergrund===
===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 <math>e : G_1 \times G_2 \longrightarrow G_3</math> in obigem Sinne und gegebenen Werten <math>P,Q,aP,bP,aQ,cQ</math> für <math>Z_p*</math> nur äußerst schwer (d.h. nicht effizient) möglich ist, den Wert <math>e(P,Q)^{abc}</math> zu berechnen.
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 <math>e : G_1 \times G_2 \longrightarrow G_3</math> in obigem Sinne und gegebenen Werten <math>P,Q,aP,bP,aQ,cQ</math> für <math>a,b,c \in Z_p^*</math> und <math>P \in G_1, Q \in G_2</math> nur äußerst schwer (d.h. nicht effizient) möglich ist, den Wert <math>e(P,Q)^{abc}</math> 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.
Diese Eigenschaft wird in den IBE Protokollen insbesondere für Sicherheitsbeweise benötigt.

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


== IBE ==
== IBE ==

=== Szenario ===

In der '''Identity Based Encryption''' (IBE) betrachtet man das Szenario, indem ein Sender A einem Empfänger B eine verschlüsselte Nachticht <math>m</math> zukommen lassen möchte. Des Weiteren besitze der Empfänger B eine eindeutige Identifikation <math>ID</math> (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 <math>P</math> und einen Master Key <math>s</math> (den sog. Secret Server Key). Mithilfe dieser Daten und der <math>ID</math> kann ein Sender A nun eine Nachricht <math>m</math> zu einem Kryptotext <math>c</math> verschlüsseln ('''Encrypt''') und an B senden. Damit der Empfänger diese Nachricht lesen kann, benötigt er einen privaten Schlüssel <math>K_{ID}</math>. Diesen erhält er vom PKG, welche den privaten Schlüssel auf der Basis von <math>P, s</math> und <math>ID</math> 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 <math>c</math> mithilfe seines privaten Schlüssels <math>K_{ID}</math> entschlüsseln ('''Decrypt''').<br>

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 <math>K_{ID}</math> anfordert.
* '''Input''': P, s, ID.
* '''Output''': <math>K_{ID}</math> (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, <math>K_{ID}</math>.
* '''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) ==
== 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 <math>G_1, G_2, G_3</math> Gruppen primer Ordnung <math>p</math> und <math>e : G_1 \times G_2 \longrightarrow G_3</math> ein Pairing. Des Weiteren sei <math>ID \in \{0,1\}^*</math> ein Identitätsstring des Empfängers A (etwa seine binär codierte E-Mailadresse) und <math>m \in \{0,1\}^n</math> 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:

* <math>H_1 : \{0,1\}^* \longrightarrow Z_p^*</math>
* <math>H_2 : G_3 \longrightarrow \{0,1\}^n</math>
* <math>H_3 : G_3 \times \{0,1\}^n \times G_1 \times G_1 \longrightarrow Z_p^*</math>

=== Primitiven ===

==== Generation ====
P-BB1-G(<math>M</math>)
* <math>r_0 \in_R Z_p^*</math>.
* <math>i := s_1s_2 + r_0(s_1M + s_3)</math>.
* <math>K_{0,M} := iQ_2</math>.
* <math>K_{1,M} := r_0Q_2</math>.
* return <math>(K_{0,M}, K_{1,M})</math>.

==== Encryption ====
P-BB1-E(<math>r</math>)
* <math>E_0 := rQ_1</math>.
* <math>E_1 := (rM)R + rT</math>.
* <math>B := V^r</math>.
* return <math>(E_0, E_1, B)</math>.

==== Decryption ====
P-BB1-D(<math>E_0, E_1, (K_{0,M}, K_{1,M}</math>)
* <math>B := e(E_0, K_{0,M}) \cdot e(E_1, K_{1,M})^{-1}</math>
* return <math>B</math>.

=== Algorithmen ===

==== Setup ====

1. PKG wählt einen master key
* <math>s := (s_1, s_2, s_3) \in_R Z_p^* \times Z_p^* \times Z_p^*</math>.
2. PKG generiert öffentliche Parameter <math>P := (Q_1, Q_2, R, T, V, G_1, G_2, e)</math>, wobei
* <math>Q_i</math> ist Erzeuger von <math>G_i</math>, <math>i = 1,2</math>, d.h. <math>\left\langle Q_i \right\rangle = G_i</math>,
* <math>R := s_1Q_1</math>,
* <math>T := s_3Q_1</math>,
* <math>V := e(R,s_2Q_2)</math>.

==== Extract ====

1. <math>M := H_1(ID)</math>.<br />
2. <math>K_{ID} := (K_{0,M}, K_{1,M}) \longleftarrow \texttt{P-BB1-G}(M)</math>.

<math>K_{ID}</math> ist der private Schlüssel des Empfängers B.

==== Encrypt ====

1. <math>r \in_R Z_p^*</math>.<br />
2. <math>(B, E_0, E_1) \longleftarrow \texttt{P-BB1-E}(r)</math>.<br />
3. <math>Y := H_2(B) \oplus m</math>.<br />
4. <math>t := r + H_3(B, Y, E_0, E_1)</math>.<br />
5. <math>c := (Y, E_0, E_1, t)</math>.

<math>c</math> ist der Kryptotext. <math>B</math> heißt blinding factor.

==== Decrypt ====

1. <math>B \longleftarrow \texttt{P-BB1-D}(E_0, E_1, K_{\rm ID})</math>.<br />
2. <math>r := t - H_3(B, Y, E_0, E_1)</math>.<br />
3. <math>\texttt{if} \ \neg(B == V^r \ \texttt{and} \ E_0 == rQ_1) \ \texttt{then} \ \texttt{exit} \ \texttt{with}</math> "`error"'.<br />
4. <math>m := Y \oplus H_2(B)</math>.

<math>m</math> ist der Klartext.


== Vor- und Nachteile ==
== 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 ==
== Quellen ==

* [http://grouper.ieee.org/groups/1363/IBC/material/P1363.3-D1-200805.pdf]: IEEE P1636.3/D1 Draft Standard for Identity-based Public-key Cryptography Using Pairings.

* [http://en.wikipedia.org/wiki/ID-based_encryption] 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.

Latest revision as of 15:08, 5 March 2010

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 Gruppen der primen Ordnung . Ein Pairing ist eine -bilineare Abbildung zwischen -Moduln für die die folgenden zwei Realismus-Bedingungen gelten:

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

Primitiven

Generation

P-BB1-G()

  • .
  • .
  • .
  • .
  • return .

Encryption

P-BB1-E()

  • .
  • .
  • .
  • return .

Decryption

P-BB1-D()

  • return .

Algorithmen

Setup

1. PKG wählt einen master key

  • .

2. PKG generiert öffentliche Parameter , wobei

  • ist Erzeuger von , , d.h. ,
  • ,
  • ,
  • .

Extract

1. .
2. .

ist der private Schlüssel des Empfängers B.

Encrypt

1. .
2. .
3. .
4. .
5. .

ist der Kryptotext. heißt blinding factor.

Decrypt

1. .
2. .
3. "`error"'.
4. .

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.