Kryptographie per Matrizenmultiplikation

Wissenschaft Mathematik
#1

Hallo Allerseits,

Mir ist gerade die Idee für folgendes Verschlüsselungsverfahren gekommen:

  • Man nehme einen Text und wandle ihn zunächst in eine Zahlenfolge um (z.B. in ASCII-Code).

  • Die Zahlen werden in eine n×n-Matrix M geschrieben, wobei in zufälligen Abständen Lücken gelassen werden.

  • Die Lücken werden so mit sinnlosen Zahlen gefüllt, dass det(M):=0 gilt. „Sinnlos“ heißt dabei, dass die Zahlen keinen kodierbaren Zeichen entsprechen (eventuell unter Berücksichtigung eines bestimmten Vertrauensintervalls, um Rundungsfehler auszugleichen).

  • Es wird eine zufällige n×n-Matrix A mit det(A)0 erzeugt.

  • Das Produkt A·M wird an den Empfänger geschickt.

  • Der Empfänger erzeugt eine zufällige n×n-Matrix B mit det(B)0.

  • Das Produkt A·M·B wird an den Sender zurück geschickt.

  • Der Sender entfernt seinen Schlüssel mittels A-1·A·M·B und schickt das Ergebnis M·B wieder zum Empfänger.

  • Der Empfänger entfernt seinen Schlüssel mittels M·B·B-1 und ist nun im Besitz der unverschlüsselten Matrix M.

  • Die sinnlosen Zahlen werden entfernt.

  • Die Zahlenfolge wird wieder in Text verwandelt.

Dazu habe ich zwei Fragen:

  1. Gibt es das schon?
  2. Kann eine dritte Person, die außer dem oben beschriebenen Verfahren ledigilich die verschlüsselten Matrizen A·M, A·M·B und M·B kennt, mit vertretbarem Aufwand (also nicht mittels Brute-Force) die unverschlüsselte Matrix M ermitteln? Und wenn ja, wie?

Viele Grüße,
DrStupid

#2

Hi,

Trifft dieses Beispiel auf Deine Frage zu?

A=(20), M=(10), B=(01), A^(-1)=(0,5 0), B^(-1)=B
(02) (00) (10) (0 0,5)

Damit wird M=(10) zu AM=(20) zu AMB=(02) zu MB=(01) zu M=(10)
(00) (00) (00) (00) (00)

Das Verfahren ist ziemlich unsicher:

M sei die Botschaft:

Du willst drei mal senden, und zwar A*M, A*M*B und M*B

Aus den abgefangenen Botschaften A*M und A*M*B kann man B^(-1) also die Inverse zu B berechnen.
Danach genügt es M*B*B^(-1)=M zu berechnen.

Sorry, das ist leider keine geeignete Verschlüsselungsmethode.

Der Ansatz ist aber nicht sooo schlecht.

LG CF

#3

Du willst drei mal senden, und zwar A*M, A*M*B und M*B

Aus den abgefangenen Botschaften A*M und A*M*B kann man B^(-1)
also die Inverse zu B berechnen.

Nope, das geht nicht weil det(M)=0 det(AMB)=0 impliziert und dadurch die Gleichungssysteme AMB * X = AM nicht (eindeutig) lösbar werden.

#4

Hi,

leider hat es meine Matritzen etwas zerwürfelt, wie man sieht.

Mit etwas Fantasie, und das hast Du bestimmt als Kryptologe, erkennst
Du die Ursprüngliche Nachricht sicher.

LG CF

#5

M sei die Botschaft:

Du willst drei mal senden, und zwar A*M, A*M*B und M*B

Aus den abgefangenen Botschaften A*M und A*M*B kann man B^(-1)
also die Inverse zu B berechnen.

Wie? (Beachte dabei den Hinweis von Timo Waechtler)

#6

Aus den abgefangenen Botschaften A*M und A*M*B kann man B^(-1)
also die Inverse zu B berechnen.

Wie? (Beachte dabei den Hinweis von Timo Waechtler)

Durch Ausprobieren bin ich jetzt selbst auf eine Lösung gekommen. Wenn man die Matritzen A·M, A·M·B und M·B durch Addition mit einer geeigneten Marix C (z.B. einem kleinen Bruchteil der Einheitsmatrix) invertierbar macht, kann man die ursprüngliche Matrix M mittels

M ≈ [(A·M·B+C)·(M·B+C)-1]-1·(A·M+C)

oder

M ≈ (M·B+C)·[(A·M+C)-1·(A·M·B+C)]-1

mit so geringen Fehlern zurückgewinnen, dass eine Dekodierung des Textes möglich ist. Schade, aber irgend einen Haken musste die Sache ja haben.

1 Like
#7

Ja, die Chiffre gibt es schon, ist eine der ersten die man in der Kryptographievorlesung hört.

In der Kryptographievorlesung macht man das lediglich mit einer Streamchiffre statt mit einer Blockchiffre, wie Du sie verwendest.

Problem der Chiffre ist halt, dass 3Kommunikationen statt finden müssen für einen einzigen Nachrichtenaustausch. Dies kann man zB machen um einen Schlüssel für eine synchrone Verschlüsselung aus zu machen(gemeinsames Geheimnis).

Der Algorithmus ist jedoch hochgradig anfällig für Man-in-the-middle-attacks.

#8

Hab gerad mal nachgeschlagen: bei der Streamchiffre ist der Rechenfehler sogar noch offensichtlicher:

A generiert Nachricht
A generiert Geheimnis
B generiert Geheimnis

A codiert Nachricht mit eigenem Geheimnis

von A an B: M xor A

B fügt sein Geheimnis hinzu

von B an A: M xor A xor B

A berechnet M xor A xor B xor A = M xor B

von A an B: M xor B

B entfernt sein Geheimnis und hat die Nachricht.

abgefangene Nachrichten bei einer „man in the middle attack“:

MxorA
MxorAxorB
MxorB

Berechnung:
MxorAxorB xor MxorB ergibt A. Ich kenne jetzt A’s Geheimnis

MxorA xor A ergibt M. Ich kenne jetzt die Nachricht.

Geil, mir ist gerade ein Rätsel für meinen nächsten Geocach eingefallen.