Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Erweiterter linearer Kongruenzgenerator

Erweiterter linearer Kongruenzgenerator

Universität / Fachhochschule

Kryptologie

Tags: Kongruenzgenerator, Kryptologie, Zufallszahl

anonymous

01:08 Uhr, 05.11.2023

Hallo,
ich habe eine Aufgabe bekommen und weiß nicht genau, wie ich diese lösen soll.
zur Aufgabe:

Diesen Link wollen Sie natürlich sofort entschlüsseln.
Sie wissen, dass ein erweiterter linearer Kongruenzgenerator (LCG) zur Erzeugung eines Schlüsselstroms genutzt wurde. Außerdem wissen Sie, dass der Schlüsselstrom

s_{i}

dazu verwendet wurde, den
Link in UTF-8 Kodierung zeichenweise zu verschlüsseln,

d

h

. das Chiffrat

y_{i}

ergibt sich für jedes
UTF-8 Klartext-Zeichen

x_{i}

als bitweises XOR mit

s_{i}

. Die erweiterte Variante des LCG berechnet jedes neue Schlüsselstromsymbol

s_{i + 1}

aus den beiden vorherigen Elementen

s_{i}

und s_

{

i−1} . In diesem Fall
benötigt der LCG aber auch zwei seed Werte

s_{0}

und

s_{1}

sowie insgesamt drei Schlüsselparameter

A, B

und

C

und den Modulo

m

. Die entsprechende Gleichung ist gegeben als:

s_{i + 1} = A

s_{i} + B

· s_

{

i−1}

+ C mod m

mit

i = 1, 2,

. . .
Aufgrund des 8-Bit-ASCII kodierten Klartextes verwenden wir für den erweiterten LCG den Modulus

m = 257

. Die abgefangene Nachricht in hexadezimaler Darstellung lautet wie folgt:
5F23C8EED2078FE00EDC300372DEFC376260BC1DAFC434BF9
Berechnen Sie die Parameter

A, B

und

C

durch Aufstellen eines linearen Gleichungssystems.
Außerdem wissen Sie, dass es sich um einen Link, der mit der Zeichenkette “ ”
beginnt, handelt.
Die Zeichenkette " " habe ich in Hex umgewandelt und dann ein Xor auf die Abgefangene Nachricht durchgeführt, so dass ich die Schlüssel von

s_{0} - s_{7}

erhalte.
als Hexcode:

68747470733 A 2 F 2 F

Die Schlüssel in Dezimal:

55, 87, 188, 158, 161, 61, 160, 207

Ich habe die Parameter bereits über eine andere Methode selber bestimmt(A=37,B=67,C=223).
Jedoch erhalte ich andere Werte ,wenn ich versuche ein LGS aufzustellen und dieses nach

A, B

und

C

umstelle.
Kann bitte jemand erklären wie man die Werte von

A, B

und

C

über ein LGS erhält.
viele Grüße

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

HAL9000

11:17 Uhr, 05.11.2023

Ich verstehe nicht, wie du

s_{0} \dots s_{7}

(also 8 Byte) erhalten konntest, wenn du nur den Anfang " " (das sind bei mir 3 Byte) Klartextnachricht kanntest: Nach meiner Logik kannst du dann durch die XOR-Operation auch nur

s_{0} \dots s_{2}

erhalten - oder was verstehe ich hier falsch?

anonymous

11:30 Uhr, 05.11.2023

Jedes Klartextzeichen wurde mit 2 Hexadezimalzeichen codiert. Jedes Hexadezimalzeichen kann mit 4 Bits (also 2 Zeichen-Hex dann mit 8 Bits oder 1 Byte) dargestellt werden. Zum Beispiel:

5 F

ist die verschlüsselte Hex Folge (und das erste Zeichen der abgefangenen Nachricht "h").

h

in unicode entspricht

68

.
wenn man nun die beiden Hex werte in Binär umwandelt und die xor operation durchführt bekommt man:

5 F : 01011111

68 : 01101000

s_{0} : 00110111

sprich ein Byte.
In dezimal umgerechnet ergibt das

55

.
Das kann man für die weiteren 7 Zeichen wiederholen und bekommt somit die Schlüssel von

s_{0} - s_{7}

HAL9000

11:37 Uhr, 05.11.2023

Ich bin nicht so blöd, dass du mir die Hexadezimalkodierung erklären musst, oder die XOR-Operation. Auf meine Frage bist du nicht wirklich eingegangen - nochmal:

" " sind bei mir 3 ASCII-Zeichen oder wenn man so will auch UTF-8-Zeichen, hexadezimal 222022. Auch nach der XOR-Operation sind das immer noch 3 Byte statt 8 Byte.

> Außerdem wissen Sie, dass es sich um einen Link, der mit der Zeichenkette " " beginnt, handelt.

Da steht nichts von 8 Zeichen.

anonymous

11:43 Uhr, 05.11.2023

sorry, wir haben aneinander vorbei gesprochen, ich habe die Nachricht in " " gesetzt, aber das Mathe Forum hat sie dadurch nicht angezeigt. Der Klartext den ich habe besteht aus hatatapasa:a/a/ (ignoriere die

a s

ich kann sonst den klartext nicht schrieben)
und nicht aus " ". Danke fürs darauf aufmerksam machen, wollte dich nicht für blöd verkaufen.

HAL9000

11:47 Uhr, 05.11.2023

Keine Ahnung, warum du Probleme hast den Code zu posten, an sich ist das Forum hier in der Lage, Юникод darzustellen.

anonymous

11:49 Uhr, 05.11.2023

Ich glaube es liegt daran, dass es der Anfang eines Links ist und es deswegen als so einer erkannt wird. Aber wenn ich den Klartext normal schreibe wird er eben nicht angezeigt.

HAL9000

11:50 Uhr, 05.11.2023

Mal testen:

In der Vorschau klappt es noch.

EDIT: Hast Recht, ist verschwunden.

anonymous

12:12 Uhr, 05.11.2023

Um auf meine Aufgabe zurück zu kommen, ich habe bereits versucht es in ein normales LGS zu überführen, mit 3 Gleichungen und 3 Unbekannten und es mit der Addition dieser Gleichungen aufzulösen. Aber ich bekomme andere Ergebnisse für die Parameter raus.

1) 188 = A \cdot 87 + 55 \cdot B + C mod 257

2) 158 = A \cdot 188 + 87 \cdot B + C mod 257

3) 161 = A \cdot 158 + B \cdot 188 + C mod 257

1)

mit

- 1

multipliziert

- 188 = - A \cdot 87 - 55 \cdot B - C mod 257

Addition von

1)

und

2)

a) - 30 = - 101 \cdot A + 32 \cdot B mod 257

Addition von

1)

mit

- 1

multipliziert und

3)

b) - 27 = A \cdot 71 + 33 \cdot B mod 257

a)

mit

(- 33)

multiplizieren

990 = 3333 \cdot A - 1056 \cdot B mod 257

b)

mit

32

multiplizieren

- 864 = 216 \cdot A + 1056 \cdot B mod 257

Addition von

a)

und

b)

126 = 3549 \cdot A mod 257

modulo anwenden.

126 = 208 \cdot A mod 257

mit

208^{- 1}

multiplizieren (multiplikatives Inverses bilden)

126 \cdot 236 = A mod 257

29736 = A mod 257

181 = A

HAL9000

12:24 Uhr, 05.11.2023

Ohne deine Rechenschritte nachvollzogen zu haben, komme ich auf eine andere Lösung des Gleichungssystems in

ℤ / 257 ℤ

A = 37, B = 67, C = 223

anonymous

12:26 Uhr, 05.11.2023

Das sind die richtigen Parameter, mich würde dennoch interessieren wo mein Fehler liegt. Könntest du entweder meinen Fehler zeigen oder deinen Rechenweg teilen? Damit ich das nachvollziehen kann?

HAL9000

12:26 Uhr, 05.11.2023

EDIT: Einen Fehler sehe ich schon. 188-87=101 statt -101.

Es geht weiter mit 188-55=133 statt 33.

Übrigens: War dein Name gestern noch "Ascorbin", oder gibt es jetzt tatsächlich zwei Leute, die sich zeitnah für Gleichungssysteme modulo 257 interessieren?

www.onlinemathe.de/forum/LGS-mit-3-Variablen-und-Modulo

anonymous

12:40 Uhr, 05.11.2023

es kann sein, dass wir an der gleichen Übungsaufgabe scheitern :-) aber das ist jemand anderes

anonymous

13:09 Uhr, 05.11.2023

Danke, für deine Hilfe, mit der Korrektur habe ich es geschafft auch auf

A = 37

zu kommen. Vielen Dank. Ich versuche den Rest jetzt erstmal alleine zu lösen, falls ich Hilfe brauceh komme ich wieder. Nochmal Danke

Maikiii22 aktiv_icon

17:23 Uhr, 05.11.2023

kannst du bitte zeigen wie du A ausgerechnet hast

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1577975

1577908

	Status: nicht eingeloggt	Noch nicht registriert?