Homomorphe Verschlüsselung! Was? Wie?

Letztens gelesen: Cloud-Dienste können mit Werten rechnen, die homomorphe Merkmale aufweisen und gesicherte Daten müssen praktischerweise vor Benutzung nicht entschlüsselt werden? Und das soll gehen? Spannend! Ich war sofort neugierig auf das Verfahren und das Ergebnis.

Begriff: Homomorphe Verschlüsselung

Homo, aus dem Griechischem für „gleich“ oder „ähnlich“ und Morph ebenfalls griechisch für Form bedeutet, dass ein Symbol, z.B. eine Zahl bzw. mehrere Zahlen das Ergebnis eines Prozesses gleicher Schritte sind. Die Symbole sind sozusagen  vergleichbar, weil sie mit ähnlichen Ausgangswerten auf identische Art und Weise entstanden sind…. interessant. Und weiter noch: rechnet man mit den so entstandenen Ergebnissen, dann erhält man selbiges Resultat, das auch aus den Ur-Werten entstanden wäre. Dann liegt Homomorphismus vor. Dann die Verschlüsselung: es geht also um Retsultate von Operationen (z.B. der RSA-Verschlüsselung) die im Verhältnis zu den Ur-Werten identisch sind. OK!? Probieren wir es aus.

Ausgangssituation

Daten, die per asymetrischer Verschlüsselung (z.B. mit RSA) gesichert sind, sollen verschlüsselt werden. Dazu geht man in etwa so vor: Der Klartext t wird mit einer großen Primzahl p als Key und einer großen Zufallszahl r nach der Formel t‘ = t + p * r verschlüsselt.

Angenommen, der Klartext t sei 5 und 2. Die große Primzahl p sei für beide (!) Klartexte 1234567 und die Zufallszahl r ist 48. Die Primzahl p sollte an dieser Stelle wesentlich größer sein. Zudem ist r ebenfalls recht klein – sollte aber an dieser Stelle ausreichen. p und r müssen für beide Ur-Werte gleich sein da sonst die Ergebnisse nicht mehr „im Verhältnis“ identisch sind – es wäre kein Homomorph mehr.

Rechnung

t1′ für 5 wäre demnach t‘ = 5 + 1234567 * 48 = 59.259.221 und t2′ für 2 wäre t‘ 2 + 1234567 * 48 = 59.259.218.  Um es spannend zu machen, multiplizieren wir, um das (Achtung!: verschlüsselte) Ergebnis zu erhalten: 59.259.221 * 59.259.218 = 3.511.655.095.749.178 – wir definieren das Produkt weiter mit e.

Prüfung

Multiplizieren wir die Ur-Faktoren 2 und 5, erhalten wir das Produkt 10. Und ebenfalls sollen wir dieses Ergebnis 10 erhalten, wenn wir obiges Produkt per Modulo aufgreifen? Probieren wir es: wir kommen zurück mit Ergebnis t = e mod p.  Wenn wir keinen mod-fähigen Taschenrechner zur Hand haben, kommen wir mit e geteilt durch p, dann die Ganzzahl des Ergebnisses (ohne den Werten rechts vom Komma: 2.844.442.704) mal nehmen mit p 1234567 und wir bekommen einen um 10 verminderten Wert als wir mit obigen Verschlüsselten Werten erhalten haben.

Faszinierend

… und im Nachhinein verständlich. Aber: Passt. Prima. Anwendungsfälle bitte? Rechnen mit Geo-Koordinaten,  Umsatz- oder Budgetberechnungen für sensible Bereiche. Datum- und Zeitoperationen – Praktisch alle Berechnungen, wobei der Rechenweg selbst nicht geheim, wohl aber die Parameter oder den Bezug niemand kennen soll.