Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Grad k - 1 beschreiben, wobei die Koeffizienten 0 oder 1 sind. Die Addition wird durch Polynomaddition beschrieben, wobei das Ergebnis modulo 2 genommen wird. Bei der Multiplikation wird das Ergebnis (das ein Polynom vom Grad 2k ergeben kann) durch ein festgewahltes irreduzibles Polynom dividiert and der entstehende Rest modulo 2 geteilt. In Tabelle 11.1 ist die Multiplikationstabelle fur F[4] angegeben.

    Die Einzelheiten dieser Berechnung sind hier von nachrangiger Bedeutung (hierfur siehe Seite 261). Im Moment ist es vollig ausreichend zu berucksichtigen, dass man in diesen Zahlenraumen wie in den bekannten Zahlenraumen rechnen kann.
    Man kann nun eine Ebene im n-dimensionalen Raum beschreiben durch das Produkt VT . X = A, wobei V and A feststehende Vektoren sind and X der Koordi- natenvektor ist. Wenn man nun n dieser Gleichungen kombiniert, erhalt man die Gleichung M • X = T fur zwei Matrizen M and T, die aus den Einzelvektoren zu- sammengefasst wurden. Der gesuchte Vektor bestimmt sich dann aus M-1T, wobei M genau dann invertierbar ist, wenn die Ebenen paarweise unabhangig sind. Man kann zeigen, dass in einem endlichen Feld der GroBe 2k bis zu 2k-1 voneinander unabhangige Ebenen existieren konnen.
    Eine Alternative ist die Methode von Shamir [91], die auf den Stutzstellen eines Polynoms beruht.
Dining Cryptographers
    Mit der Methode der Dining Cryptographers wird ein einfaches Verfahren beschrieben, den Urheber einer Nachricht zu verschleiern. Wir wollen zuerst ein anderes Problem and seine Losung als EinfUhrung vorstellen: Die Bestimmung des Gesamt- gehalts einer Gruppe von mindestens drei Leuten, ohne dass einer sein Gehalt preis- geben muss.
    Hierzu ordnet man n Mitspieler kreisformig an. Zuerst wahlt der erste Mitspieler eine vollig willkurlich gewahlte (zufallige) Zahl r. Auf diese addiert er sein Gehalt hi and gibt sie Spieler 2. Nun addiert jeder folgende Spieler jeweils sein Gehalt auf die Summe and gibt diese dem nachsten. Hierbei ist zu beachten, dass zwei benachbarte Spieler die Weitergabe der Zahl unbeobachtet von den anderen Spielern durchfuhren. (Ansonsten konnen diese naturlich durch Bestimmung der Differenz der ausgehenden Zahl mit der eingehenden Zahl das geheimzuhaltende Gehalt auf- decken.) Wenn these Summe jetzt beim ersten Spieler ankommt, so sieht der die Zahl r + hi + h2 + ... + hn, = g. Er zieht fur sich die Zahl r, die nur er kennt, ab and erhalt die gesuchte Summe g - r.

    Mochte man das Ergebnis den anderen auch mitteilen, so addiert jeder abermals sein Gehalt auf g and gibt these Summe wieder reihum durch. Die Differenz der beiden empfangenen Werte entspricht dem Gesamtgehalt aller Spieler. Diese erhalt jetzt jeder Spieler ohne ein einziges Einzelgehalt zu kennen, siehe auch Abbildung 11.1.
    Abb. 11.1. Private Computing: Addition von n Zahlen.
    Diese Technik, eine Berechnung ohne Kenntnis der Einzelergebnisse durch- zufuhren, nennt man auch Private Computing, ein Teilgebiet der Kryptographie and des Verteilten Rechnens (Distributed Computing).
    Das Verfahren der Dining Cryptographers funktioniert nun ganz ihnlich. Die Aufgabe ist, dass einer der n Teilnehmer eine Nachricht veroffentlichen mochte. Diese wird am Ende alien bekannt sein, es soil aber unklar sein, wer die Nachricht ursprunglich verschickt hat. Hierzu ordnet man die Teilnehmer wieder kreisformig an einem Tisch an and fordert, dass samtliche Kommunikation nur zwischen zwei benachbarten Teilnehmern stattfindet and dass der Inhalt zwischen den Beteiligten geheim gehalten wird.

    Zu Beginn bestimmt jeder Teilnehmer i unabhangig eine zufallige Zahl xi. Jeder Teilnehmer gibt diese Zahl seinem rechten Tischnachbarn. Dieser berechnet die Differenz aus seiner Zahl and der eben erhaltenen Zahl and erhalt x2 - xi-1. Mochte nun einer der Teilnehmer eine Nachricht m veroffentlichen, so addiert er diese auf die Differenz and erhalt xi - xi_1 + in, siehe Abbildung 11.2.
    Nun veroffentlicht jeder Teilnehmer das Ergebnis dieser Rechnung, wobei naturlich m and die ursprunglichen Werte xi weiterhin geheim gehalten werden. Jetzt kann jeder die Summe aller Werte aufaddieren, and da jeder Term xi einmal positiv and einmal negativ auftauchten, fallen all these heraus and es bleiben nur noch die Summen der Nachrichten ubrig.
    Hat nun niemand eine Nachricht senden wollen, so ist das Ergebnis 0. Hat nur einer eine Nachricht senden wollen, so konnen alle diese Nachricht sehen and keiner kann den Erzeuger identifizieren, solange nicht die