lässt sich mein Algorithmus knacken?

[onnie]

Hallo Forum.

Ich hab mal einen eigenen Asymmetrischen Algorithmus erstellt. Ich befürchte aber, dass er nicht sicher ist.

Die Funktionsweise:
Der Schlüssel liegt in Form einer quadratischen Binärtabelle vor.
Bsp. mit 24 bit Seitenlänge:
0,1,1,1,0,0,1,1,1,0,0,0,0,1,0,1,0,0,1,0,1,1,0,0
0,1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0,1
0,0,0,1,0,0,1,1,0,1,1,0,0,0,0,0,0,1,1,0,0,1,0,1
0,0,1,0,1,1,1,0,0,0,0,1,0,0,0,1,1,1,1,1,0,0,1,1 <- 4. Zeile
0,0,0,0,1,0,1,0,1,0,0,1,0,0,1,1,1,1,0,1,1,1,0,0
1,1,0,1,0,1,1,1,1,0,1,0,1,1,0,0,1,0,0,1,1,0,1,0
0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,0,0,0,1,0,1,1,0 <- 7. Zeile
1,1,0,0,1,1,1,1,1,1,0,0,0,0,1,0,1,1,1,0,1,0,0,0
0,0,0,0,0,1,0,1,0,0,0,1,1,0,0,0,1,0,1,0,0,0,1,0
1,1,1,0,0,0,1,1,1,0,0,0,0,1,0,1,0,1,1,1,0,0,1,1
0,1,1,0,0,0,1,0,0,1,1,0,1,1,0,0,0,0,0,0,1,1,0,1
1,1,1,1,0,1,0,1,0,0,1,0,0,1,1,1,0,1,0,1,1,1,0,0
0,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,1,1,0,1,0,0
0,1,1,0,1,0,0,1,1,0,1,1,0,0,0,0,0,0,1,0,1,0,0,0
1,0,0,0,0,0,1,1,1,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0 <- 15. Zeile
0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,0,1,0,0,1
1,0,1,1,1,0,0,0,0,1,0,1,0,1,0,1,0,1,1,1,0,0,0,1
0,0,0,0,0,1,1,0,1,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1
1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,0,1,0,1,0,0,1,1,0
1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,1,1,1
0,0,0,1,1,0,1,0,0,1,1,1,1,1,0,1,0,1,0,0,0,1,1,1
1,0,1,0,1,1,0,0,1,1,1,1,0,1,1,0,0,0,1,0,1,1,1,0
1,0,0,1,1,1,0,1,0,0,0,1,1,1,0,0,1,0,0,1,0,0,1,0
1,0,1,1,0,0,0,0,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,0

Um nun eine 24 bit lange Nachricht zu verschlüsseln, schreibt man diese senkrecht links neben die Tabelle.
Dann wählt man alle Zeilen aus, bei denen in der Nachricht eine eins Steht und verknüpft sie mit XOR.
Wenn in der Nachricht z.B. nur das 4., 7. und 15. bit einsen sind und sonst Nullen, werden die 4., die 7. und die 15. Zeile der Tabelle XOR verknüpft.

0,0,1,0,1,1,1,0,0,0,0,1,0,0,0,1,1,1,1,1,0,0,1,1
0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,0,0,0,1,0,1,1,0
1,0,0,0,0,0,1,1,1,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0
--------------------------------------------
1,1,1,1,1,1,1,0,1,0,0,0,0,1,1,0,0,1,1,1,0,0,1,1

Kann man dieses Verfahren knacken?

lg Onnie

[Wernfried]

Grundsätzlich ist jedes Verfahren zu knacken, es ist nur eine Frage des Aufwands.

Du schreibst "Asymmetrischer Algorithmus", wo ist der zweite Schlüssel zum Entschlüsseln und wie ist das Verfahren?
Was machst du wenn die Nachricht grüsser als 24 Bit gross ist?

Ein allgemeiner Nachteil von asymmetrischen Verfahren ist, dass die Schlüssellänge recht lang sein muss, damit der Algorithmus als sicher gelten kann.
Bei RSA sind es z.B. 1024 Bit.

Ich bin zwar kein Experte in Sachen Kryptografie aber dein Ansatz funktioniert vermutlich nicht und ist nicht sicher.

Gruss

[Christian Marquardt]

24-Bit lange Nachricht 3 Zeichen? Ungemein praktisches Verfahren. Und sicherlich ist das Verfahren schnell zu knacken, da du immer den Code zum ver-/entschlüsseln in irgendeiner Form bereitstellen musst

[onnie]

Die Tabelle kann beliebig erweitert werden. Einziger Nachteil ist die Größe und damit der Speicherbedarf. (bei 512 bit Seitenlänge sind das 32 kB)
Entschlüsseln funktioniert genauso, nur mit einer anderen Tabelle. Die beiden Tabellen werden miteinander erstellt.

Edit: Funktionstüchtig ist das Verfahren.

[Ralf Jansen]

Bei längeren Nachrichten würdest du den Schlüssel immer wiederholen, also je n bit? Dann würden gleiche Nachrichtenmuster immer das selbe Verschlüsselungsmuster erzeugen und damit potentiell leicht knackbar sein. Ich vermute mal das mit genügend verschlüsseltem Material dein Entschlüsselungschlüssel leicht ermittelbar ist. Wenn dein Schlüssel immer länger (oder zumindest gleichlang) wie die Nachricht sein muss dann wäre es aus alleine aus diesem Grund potentiell sicher (wenn du den Schlüssel nur einmal verwendest). Das wären andere wesentlich einfacher handhabbare Verfahren aber auch. Dein Verfahren ist also eventuell sicher aber definitiv nicht praktibel.

Wie zufällig ist eigentlich der Schlüssel? Zeilen dürfen sich sicher nicht wiederholen aber steckt da noch mehr Struktur drin? Dann wäre das auch wieder ein potentieller Angriffspunkt.

[Wernfried]

Kleiner Nachtrag, ich mache mal ein paar Vermutungen.

Zum Entschlüsseln werden die Bits erneut mit den 24 Zeilen via XOR verknüpft und man bekommt die Zeilen welche in der orginalen Nachricht "1" waren.
Das wäre dann "normales" CDMA Verfahren, ein typisch symetrischer Algorithmus.

Wie hast du die 24 Zeilen des Schlüssels erzeugt? Wenn es zufällige Zahlen sind, funktioniert dein Verfahren nicht, da die verschlüsselte Nachricht auch mit einer anderen Kombination herauskommen könnte, (fiktives Beispiel: Zeile 5,9,20,23). Es funktioniert nur wenn wenn die 24 Codes streng orthogonal zueinander sind. Eine Liste aus orthogonalen Codes kann man z.B. mit der Walsh-Funktion erzeugen. Die Anzahl möglicher Codes ist dann aber erheblich kleiner als "2 hoch 24", es sind nur ein paar wenige welche sich jeder selbst erzeugen und durchprobieren kann.

Gruss

[onnie]

Wie zufällig ist eigentlich der Schlüssel? Zeilen dürfen sich sicher nicht wiederholen aber steckt da noch mehr Struktur drin? Dann wäre das auch wieder ein potentieller Angriffspunkt.

Die Zahlen sind komplett zufällig, unter der Voraussetzung, dass das ganze noch eindeutig lösbar ist.
Wenn sich Zeilen wiederholen würden, wäre es nicht mehr eindeutig.

[Wernfried]

Die Tabelle mit dem Codes zu rekonstruieren ist doch fast schon trivial:

Einfach diese Nachrichten
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
usw.
verschlüsseln und die verschlüsselten Nachrichten entsprechen der Code-Tabelle.

Gruss

[Ralf Jansen]

verschlüsseln und die verschlüsselten Nachrichten entsprechen der Code-Tabelle.

Die Codetabelle hattest du doch eh schon zum verschlüsseln benutzt. Die kennst du also bereits.

[onnie]

Um es vollständig zu machen, hier die Entschlüsseltabelle:

1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0
0,0,1,1,0,1,1,0,1,0,1,0,1,1,1,0,1,1,0,1,0,0,1,1
1,0,1,0,0,0,0,1,1,1,0,1,0,0,0,1,0,0,1,1,0,0,0,1
0,1,1,1,0,0,1,1,0,1,1,0,1,1,0,1,0,0,1,1,1,0,0,0
1,0,1,1,1,0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,1,0,0,0
0,0,0,0,0,0,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,0,1,1
0,0,1,1,1,0,1,1,1,1,0,0,0,0,0,0,0,1,0,1,1,0,1,0
1,1,0,0,0,1,0,1,0,1,1,1,0,0,0,1,0,0,0,1,1,1,1,1
1,1,0,0,0,0,0,1,1,0,0,1,1,1,0,1,1,0,0,1,0,1,1,0
1,0,1,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
1,1,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,0,0,1,1
1,1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,0,1,1,0,1,0,0,0
0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,1,0,1,0,0,1,0,1,1
0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0
0,1,1,0,0,1,1,0,0,0,0,1,0,1,0,0,1,0,1,0,1,0,0,0
0,1,1,1,1,0,0,0,1,1,1,0,1,0,0,0,1,1,0,1,0,1,0,0
1,1,0,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1
0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,0,0,0,1,0,0
0,1,0,1,1,0,1,1,0,1,1,0,0,1,0,0,0,1,1,1,0,1,1,0
0,0,0,1,1,0,0,0,0,0,1,1,0,0,1,1,0,1,1,1,1,0,0,0
0,1,0,1,0,1,1,1,0,0,0,1,1,0,1,0,1,0,1,0,1,1,1,0
0,0,0,0,1,0,1,1,1,0,1,1,1,1,0,1,0,1,0,1,0,1,1,1
1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,0,1,1,0,0
1,0,1,1,1,1,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,1,1,1

lässt sich die irgendwie aus der anderen berechnen?

[Wernfried]

Um es vollständig zu machen, hier die Entschlüsseltabelle:

1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0
0,0,1,1,0,1,1,0,1,0,1,0,1,1,1,0,1,1,0,1,0,0,1,1
1,0,1,0,0,0,0,1,1,1,0,1,0,0,0,1,0,0,1,1,0,0,0,1
[...]
lässt sich die irgendwie aus der anderen berechnen?

Aus deiner Frage entnehme ich, dass die Tabelle zum Entschlüsseln ebenfalls aus zufälligen Werten besteht.
Ist das dein Ernst, du hast eine verschlüsselte Nachricht und kannst diese mit einem zufälligen (d.h. jeden beliebigen) Schlüssel wieder entschlüsseln?

Gruss

[Ralf Jansen]

lässt sich die irgendwie aus der anderen berechnen?

Merkwürdige Frage - du solltest es doch auch berechnet haben. Wenn es ein sinnvolles asymetrisches Kryptographieverfahren sein soll muss es berechenbar sein. Nur ohne weiteres Wissen wie das Schlüsselpaar entstanden ist sollte es eben schwer sein es zu berechnen. So schwer das es möglichst praktisch (also mit endlicher Rechenkapazität und endlicher Zeit) nicht zu lösen ist.

Hast du dieses Verfahren tatsächlich geschrieben oder ist das eine verklausulierte 'Lös mir meine Hausaufgaben'-Frage in der du das Schlüsselpaarerstellungsverfahren raus bekommen sollst?

[Wernfried]

Ich habe nach wie vor Zweifel, dass der Algorithmus überhaupt funktioniert wenn der Schlüssel aus zufälligen Ziffern besteht (mit der Randbedingung, dass keine Zeile doppelt vorkommen darf).

Verknüpfe mal die ersten beiden Zeilen des Schlüssel mit XOR.
0,1,1,1,0,0,1,1,1,0,0,0,0,1,0,1,0,0,1,0,1,1,0,0
0,1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0,1

Wenn das Ergebnis "zufällig" der 3. Zeile entspricht, geht es nicht mehr.

Die Nachricht
1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
würde verschlüsselt das gleiche geben wie
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Eine eindeutige Entschlüsselung ist damit nicht mehr möglich. - Oder sollte ich besser schon im Bett liegen?

Abgesehen davon ist es keine grosse Kunst eine 24 Bit lange Nachricht mit einem 24*24Bit langen Schlüssel zu verschlüsseln - sinnvoll dürfte das kaum sein.
Aber das wurde hier ja bereits erwähnt.

Gruss

[onnie]

Schlüsselgenerierung:
Grundlage sind zwei Tabellen mit dem Inhalt
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
...
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1

Die eine Tabelle ist der öffentliche Schlüssel, die andere der Private.
Das Verfahren würde an dieser Stelle schon "funktionieren", denn die Nachricht wird nicht verändert.
"Eis" wird verschlüsselt zu "Eis" -> der Empfänger entschlüsselt "Eis" zu "Eis" (ich habe noch nichts von sicher gesagt.)



Danach folgt eine Schleife. Wie oft sie mindestens durchlaufen werden soll, weiß ich noch nicht genau, aber zu oft schadet auch nicht.
Zellenangaben in (Zeile,Spalte)
es werden zwei Zufallszahlen x und y im Bereich 1 bis 24 erstellt.
In der Verschlüsseltabelle muss die Zelle (y,x)=0 sein, sonst neue Zahlen generieren.
In der Entschlüsseltabelle wird die Zelle (x,y) verändert also aus 0 wird 1 und aus 1 wird 0.
Danach werden in der Verschlüsseltabelle alle Zeilen, die an Stelle x eine 1 stehen haben mit Zeile y XOR verknüpft.
Schleifenende

[Wernfried]

Du kannst mit der Schleife ja mal nur wenige Durchläufe machen, evtl. erkennst du dann eine Beziehung.

Der Algorithmus hat (abgesehen von der Passwortlänge welche quadratisch zur Nachricht wächst) sicher eine Schwäche: Wenn die Nachricht aus 24x0 besteht, ist die verschlüsselte Nachricht ebenfalls 24x0.
Gibt es in der Nachricht nur eine einzige "1", muss man nur schauen mit welcher Zeile der Verschlüsseltabelle die verschlüsselte Nachricht übereinstimmt. Bei zwei "1" kann man die verschlüsselte Nachricht mit jeder Zeile der Verschlüsseltabelle XOR verknüpfen. Wenn die Zeile passt, bleibt wieder eine übereinstimmende Zeile über.
Wenn die Nachricht zwei "1" enthält muss man das ganze in einer Schleife 24 mal machen.

Falls die Nachricht nur aus 24x1 besteht oder nur eine einzige "0" enthält, kann man alle Zeilen der Verschlüsseltabelle mit XOR verknüpfen und macht dann so weiter wie oben.

Anders aufgedrückt kann man feststellen: Wenn die zu verschlüsselnde Nachricht nicht mindestens 5 mal "Eins" und mindestens 5 mal "Null" enthält ist sie in wenigen Sekunden geknackt - unabhängig vom gewählten Passwort.

Gruss