RAKE - ein neues und effektives Public-Key Verfahren

Knacken von Verschlüsselungen bei den Projekten RC5-72, Enigma@Home und anderen
Nachricht
Autor
bik
Taschenrechner
Taschenrechner
Beiträge: 9
Registriert: 18.06.2017 11:35

RAKE - ein neues und effektives Public-Key Verfahren

#1 Ungelesener Beitrag von bik » 01.08.2017 11:11

Im vorangegangenen Beitrag viewtopic.php?f=4&t=16693 wurde eine kommutative skalare Punktmultiplikation R = R(P,k,m,f) vorgestellt, die als Einwegfunktion Grundlage des von mir zur Evaluierung veröffentlichten Public-Key Verfahrens RAKE ist.

Mit dem Formfaktor f=3 für die einfache bzw. f=2 für die zweifache Punktmultiplikation und dem Weglassen des Moduls m=Prim! wird diese dann zu R = P#k, bzw. R = P°k umgeschrieben, wobei P und R zweidimensionale Punkte mit ganzzahligen Koordinaten x, y und k ein ganzzahliger skalarer Multiplikator sind.

Authentifizierung, Signatur und Schlüsselaustausch werden dann folgendermaßen ermöglicht:


1. Authentifizierung und Signatur

Es seien A und B die Kommunikationspartner. Für die Authentifizierung wird von A ein Schlüssel VK nach den Bedingungen der einfachen Punktmultiplikation erstellt,

VK(x,y) = CS(x,y)#t, mit 0 <= x, y < m und 2 <= t
Ausschlußpunkte: CS.x == CS.y, CS.x + CS.y == m
VK.x == VK.y, VK.x + VK.y == m
VK.x == 0, VK.y == 0, VK == CS
Ausschlusspunkte werden zur Berechnung nicht zugelassen bzw. als unzulässiges Ergebnis verworfen

wobei der geheime Ausgangspunkt CS und t aus Zufallszahlen bestimmt werden. VK wird zusammen mit dem Modul m und dem Multiplikator t als Bestandteil des Schlüssels von A öffentlich gemacht.

Um eine Nachricht zu signieren, erstellt A zunächst den Hash der Nachricht h und daraus zusammen mit einem weiteren Multiplikator s aus CS die Signatur SIG:

SIG = (CS#s)#h

Der Multiplikator s wird aus einem Zeitstempel gebildet. Somit unterscheiden sich verschiedene Signaturen der gleichen Nachricht voneinander. SIG und s werden zusammen mit der Nachricht an B übermittelt.

Der Empfänger B erstellt nun ebenfalls aus der empfangenen Nachricht ihren Hash h1 und überprüft mit den öffentlichen Schlüsseln von A (VK, t und m) die Echtheit der Signatur:

SIG#t = (VK#s)#h1
(CS#s#h)#t = ((CS#t)#s)#h1 dann und nur dann, wenn h1 == h

Die Gleichheit ist wegen der kommutativen Eigenschaften nur gegeben, wenn die beiden Hash-Werte h und h1 übereinstimmen, die Nachricht also unverfälscht ist und von A signiert wurde.

Weil CS geheim ist, kann es aus VK und t nur durch Ausprobieren gefunden werden. Auch aus SIG, h und s kann CS nur so ermittelt werden. Die Erfolgs-Wahrscheinlichkeit des Schlüsselbrechens liegt bei 2*m-2.


2. Schlüsselaustausch

Der Herausgeber bzw. Eigner A erstellt aus dem oben ermittelten VK und drei Multiplikatoren nach den Bedingungen der
zweifachen Punktmultiplikation einen Schlüssel EK

EK(x,y) = (VK(x,y)°u)°v, mit 0 <= x, y < m und 2 <= u,v < m
Ausschlußpunkte: VK.x == VK.y, VK.x + VK.y == m
EK.x == EK.y, EK.x + EK.y == m
EK.x == 0, EK.y == 0, EK == VK
EK == VK°k, mit k = (u*v)% m
Ausschlusspunkte werden als unzulässiges Ergebnis verworfen

Die Multiplikatoren u, v werden mittels Zufallsprozeß bestimmt und geschützt als private Schlüssel von A aufbewahrt. EK wird als Kodierungs-Schlüssel von A veröffentlicht.

Der Kommunikationspartner B erstellt ebenfalls unter den Bedingungen der zweifachen Punktmultiplikation aus den öffentlichen Schlüsseln von A (hier VK, EK und m) einen Info-Key IK und einen zweiten Schlüssel G, den er als gemeinsames Geheimnis (shared secret) für eine symmetrische Verschlüsselung einsetzt. Die Multiplikatoren a, b bestimmt B mittels Zufallsprozeß und kann sie anschließend vergessen. Aus G(x,y) wird ein key für die symmetrische Verschlüsselung gebildet, indem die Bitketten von G.x und G.y aneineander gefügt werden. Damit erhält key etwa die doppelte Bitlänge des Moduls m.

IK = (VK°a)°b
G = (EK°a)°b -> entspricht -> (((VK°u)°v)°a)°b

Den Info-Key IK schickt B zusammen mit der mit Hilfe von G veschlüsselten Nachricht über einen offenen Weg an A.

Der Eigner A errechnet das gemeinsame Geheimnis G mit Hilfe seiner geheimen, nur ihm bekannten Multiplikatoren und dem Info-Key von B

G = (IK°u)°v -> entspricht -> (((VK°a)°b)°u)°v

Wegen der kommutativen Eigenschaften der Punktmultiplikation sind nun A und B im Besitz eines gemeinsamen Schlüssels G bzw. key, ohne die geheimen Multiplikatoren des jeweils anderen zu kennen. A kann somit die von B verschlüsselte Nachricht entschlüsseln. Ein Dritter kann aus den ihm zugänglichen öffentlichen Schlüsseln VK, m und EK von A und dem Info-Key IK von B ohne Kenntnis der geheimen Multiplikatoren einer der beiden das G nicht ermitteln. Die Erfolgs-Wahrscheinlichkeit des Schlüsselbrechens durch Ausprobieren liegt hier bei etwa 3,3*m-2.


3. Vorteile des neuen Public-Key Verfahrens

Das hier beschriebene Public-Key Verfahren zur Authentifizierung, Signatur und Schlüsselaustausch ist einfach zu implementieren und damit leicht überprüfbar. Die dem zugrundeliegenden Prinzipien sind intuitiv und allgemeinverständlich.

Zur Einordnung wird aufhttps://www.keylength.com/en/compare/ zu perspektivisch sicheren minimalen Schlüssellängen verwiesen. Darin wird von der NSA für die höchste Sicherheitsstufe bei der symmetrischen Verschlüsselung die Schlüssellänge von 256 Bit angegeben. Für die gleiche Sicherheit müssen die bekannten asymmetrischen Public-Key Verfahren Bitlängen von 384 (Elliptische Kurven) und 3.072 (RSA) aufweisen. Das hier beschriebene Public-Key Verfahren erreicht das bereits mit einer Bitlänge des Moduls von 128, benötigt also weniger Ressourcen und Rechenzeit als die bekannten Verfahren bei gleicher Sicherheit.

Benutzeravatar
Lasse Kolb
Vereinsvorstand
Vereinsvorstand
Beiträge: 1355
Registriert: 03.12.2002 21:06
Wohnort: Braunschweig/Hondelage
Kontaktdaten:

Re: RAKE - ein neues und effektives Public-Key Verfahren

#2 Ungelesener Beitrag von Lasse Kolb » 01.08.2017 16:49

Das ganze als Alternative zu DiffiHellman oder RSA?
(ich weiß gar nicht, wie zeitgemäss RSA noch ist, weil da glaube ich kein Forward Secrecy geht, oder?)

Bin da aber auch nicht soo der Experte ;-)
Blog: https://lassejulius.wordpress.com
Threema ID: THNUM86Z · Twitter/Skype: lassejulius

bik
Taschenrechner
Taschenrechner
Beiträge: 9
Registriert: 18.06.2017 11:35

Re: RAKE - ein neues und effektives Public-Key Verfahren

#3 Ungelesener Beitrag von bik » 02.08.2017 09:51

RAKE kann als Alternative zu RSA, Diffie-Hellman, ElGamal und Elliptic Curves Cryptography(ECC) basierten Public-Key Verfahren betrachtet werden.
In den Materialien unter https://bik-host.de/RAKE/ ist die Motivation für die Entwicklung von RAKE dargelegt.
Hinzu kommt, dass es bei der Anwendung der bekannten Verfahren begründete Sicherheitsbedenken bezüglich staatlicherseits verlangter Hintertüren gibt, bei ECC sind es darüberhinaus z.T. unklare patentrechtliche Fragen. Mit RAKE sollen diese Unsicherheiten genommen werden.

bik
Taschenrechner
Taschenrechner
Beiträge: 9
Registriert: 18.06.2017 11:35

Re: RAKE - ein neues und effektives Public-Key Verfahren

#4 Ungelesener Beitrag von bik » 23.12.2017 15:31

Die unter viewtopic.php?f=4&t=16693 beschrieben Funktion wurde von mir zwischenzeitlich erweitert mit der Folge, dass auch das Public-Key Verfahren RAKE unter https://bik-host.de/RAKE entsprechend aktualisiert wurde.

Antworten

Zurück zu „Kryptographie“