Eine mehrdimensionale Einweg-Funktion

Knacken von Verschlüsselungen bei den Projekten RC5-72, RSAttack und anderen

Eine mehrdimensionale Einweg-Funktion

Unread postby bik » 07.09.2017 16:03

Einweg-, Falltür- oder trapdoor-Funktionen werden in der asymmetrischen Verschlüsselung zum Schutz eines Geheimnisses verwendet.
So soll sich z.B. aus dem Ergebnis einer solchen Funktion R=Pk(P,k,m) aus den bekannten R, k und m das Geheimnis P nicht ableiten,
sondern nur durch Ausprobieren ermitteln lassen.

Es sei P=[p_0,.. p_i, ...] ein n-dimensionaler Punkt, n>=2, dessen Komponenten p_i ganzzahlig sind und sich, zumindest
teilweise, voneinander unterscheiden. Weiterhin sei m eine Primzahl, % die Modulo-Division und k>1 ein ganzzahliger Faktor.
Dann wird die Funktion R=Pk(P,k,m) durch folgenden Java-Kode beschrieben:

import java.util.BitSet;
public class PK {
public int[] Pk(int[] P, int k, int m) { // written as R=P°k with m in mind
int[] R=new int[P.length], N=new int[P.length];
BitSet bitset=BitSet.valueOf(new long[] {k});
int i, bitlength=bitset.length();

int tmp=P[0]; for(i=0;i<P.length-1;i++) N[i]=P[i+1]; N[P.length-1]=tmp;

for(int bit=0; bit<bitlength; bit++) {
if(bitset.get(bit)) {
tmp=R[P.length-1]; for(i=P.length-1;i>0;i--) R[i]=(R[i-1]+N[i-1])%m; R[0]=(tmp+N[R.length-1])%m;
}
tmp=N[P.length-1]; for(i=P.length-1;i>0;i--) N[i]=(3*N[i-1])%m; N[0]=(2*tmp)%m;
}

return R;
}
}
Beispiele:
P=[3,4], k=12, m=19 -> R=[10,17]
P=[9,2,5], k=3, m=13 -> R=[2,1,6]
P=[210,134,45,65,123,40], k=191, m=997 -> R=[404,427,47,882,117,318]

Wenn r und p die jeweiligen Komponentensummen von R und P bezeichnen, dann gilt r%m= (k*p)%m. Aus der diophantischen Gleichung r=p*k+z*m kann dann für bekannte Werte r,k und m=Prim! die Unbekannte p<m ausgerechnet werden. Deshalb muss n>=2 sein, und die Komponenten von P müssen sich zumindest teilweise unterscheiden. Um singuläre R=0 zu vermeiden, muss darüberhinaus p%m!=0 sein.

Für Werte pi, k und m mit mit mehreren hundert Binärstellen kann dann diese Funktion bis zum Nachweis des Gegenteils als kryptografisch sicher angesehen werden.

Eine weitere Eigenschaft dieser Funktion ist ihre Kommutativität, d.h. die Reihenfolge der Faktoren spielt bei der
mehrfachen Anwendung keine Rolle:
P=[15, 6], m=19
R=(P°6)°7=[3,5]
R=(P°7)°6=[3,5]

Durch die zweifache Anwendung ist es nicht mehr möglich, aus r,p und m die beiden Faktoren zu errechnen. In diesem Sinne
ist die mehrfache Anwendung auch eine Einweg-Funktion.

Mit dieser Einweg-Funktion können im Unterschied zur unterhttps://www.rechenkraft.net/forum/viewtopic.php?f=4&t=16693 beschriebenen Einweg-Funktion mit dem Public-Key Verfahren RAKE auch höher-dimensionale Schlüssel erstellt werden, die eine entsprechend höhere Sicherheit gewährleisten:

1. Authentifizierung und Signatur

Es seien A und B die Kommunikationspartner. Für die Authentifizierung wird von A ein n-dimensionaler Schlüssel VK erstellt

VK = CS°t, t>1

wobei t ganzzahlig beliebig ist und die n geheimen Komponenten von CS aus Zufallszahlen so bestimmt werden, dass die Komponentensumme modulo m ungleich 0 ist. VK wird zusammen mit dem Modul m und dem Faktor 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 Faktor s aus CS die Signatur SIG:

SIG = (CS°h)°s

Der Faktor 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°h1)°s dann und nur dann, wenn h1 == h, weil
(CS°h°s)°t = ((CS°t)°h1)°s

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 im Bereich von 1/(m hoch (n-1)).


2. Schlüsselaustausch

Der Herausgeber bzw. Eigner A erstellt aus dem oben ermittelten VK und zwei Faktoren einen Schlüssel EK

EK = VK°u°v, Bedingung: u,v>=2, EK != VK°(u*v%m)

Die Faktoren u und v werden bei Einhaltung der Bedingung mittels Zufallsprozeß bestimmt und geschützt als privater Schlüssel von A aufbewahrt. EK wird als Kodierungs-Schlüssel von A veröffentlicht. Die Bedingung schließt aus, dass EK durch nur einen Faktor aus VK erhalten werden kann.

Der Kommunikationspartner B erstellt 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.

IK = VK°a°b, Bedingung: a,b>=2, IK != VK°(a*b%m)
G = EK°a°b -> entspricht -> (VK°u°v)°a°b

Die Faktoren a und b werden bei Einhaltung der Bedingung von B mittels Zufallsprozeß bestimmt und können anschließend vergessen werden. Aus G wird ein Key für die symmetrische Verschlüsselung gebildet, indem die Komponenten von G aneinander gefügt werden. Damit erhält der Key etwa die n-fache Bitlänge des Moduls m.

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 Faktoren und dem Info-Key von B

G = IK°u°v == (VK°a°b)°u°v

Wegen der kommutativen Eigenschaften der Funktion sind nun A und B im Besitz eines gemeinsamen Schlüssels G bzw. Key, ohne die geheimen Faktoren 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 des geheimen Faktoren einer der beiden das G nicht ermitteln. Die Erfolgs-Wahrscheinlichkeit, u und v aus EK und VK, oder a und b aus IK und VK durch Ausprobieren zu finden, liegt im Bereich von 1/(m hoch 2).
bik
Idle-Sammler
Idle-Sammler
 
Posts: 6
Joined: 18.06.2017 11:35

Re: Eine mehrdimensionale Einweg-Funktion

Unread postby bik » 20.10.2017 17:11

Im Java-Kode hat sich ein Schreibfehler eingeschlichen. Es muss natürlich an der entsprechenden Stelle N[i]=(2*N[i-1])%m; heißen und nicht N[i]=(3*N[i-1])%m;
bik
Idle-Sammler
Idle-Sammler
 
Posts: 6
Joined: 18.06.2017 11:35


Return to Kryptographie

Who is online

Users browsing this forum: No registered users and 7 guests