Generierung des public key

Wenn man das Untersummen-Problem zum Verschlüsseln nutzen möchte, muss man zunächst sicherstellen, dass stets eine eindeutige Lösung existiert. Zu diesem Zweck bedient man sich des folgenden Tricks: Jedes neue Element muss größer sein, als die Summe aller bisheriger Elemente. Mathematisch ausgedrückt:

$$g_{i + 1} > g_i + g_{i - 1} + g_{i - 2} + \dots + g_2 + g_1$$ (6)

Damit ist eine Lösung des Problems einfach und das Verfahren ähnelt dem Übertragen einer Dezimalzahl in das Binärsystem: Ist das Gesamtgewicht größer oder gleich dem schwersten Einzelgewicht, so muss sich dieses Gewicht im Rucksack befinden, da alle anderen Gewichte zusammen leichter als das schwerste Gewicht, demzufolge auch leichter als das Gesamtgewicht sind. Nun wird das schwerste Gewicht gegebenenfalls vom Gesamtgewicht abgezogen und das Verfahren für das nächstschwerere Gewicht wiederholt.

Das Problem ist, dass es für einen Angreifer ebenso einfach ist wie für den Empfänger, an die Nachricht heran zu kommen. Schliesslich kann er das selbe Prinzip verwenden. Deswegen wird aus dieser Menge $\{ g_1, g_2, \dots, g_i \}$ noch eine neue Menge $\{ G_1, G_2, \dots, G_i \}$ gebildet, bei der dieses Prinzip nicht mehr funktioniert. Eine algebraische Summe von Elementen der neuen Menge kann so umgewandelt werden, so dass sie sich aus Elementen der ursprünglichen Menge zusammensetzt.

Um $\{ G_1, G_2, \dots, G_i \}$ zu bilden wird noch eine beliebige Zahl $n$ benötigt, welche lediglich größer als die Summe aller $g_i$ sein muss. Ausserdem braucht man noch eine zu $n$ teilerfremde Zahl $e$. Nun berechnet man für jedes $g_i$ das zugehörige $G_i$ nach folgendem Algorithmus:

$$(g_i \cdot e) \bmod n = G_i$$ (7)

Die so gewonnene Menge $\{ G_1, G_2, \dots, G_i \}$ ist der public key.