Programmieren - alles kontrollieren 4.941 Themen, 20.708 Beiträge

Verfolgung starten Optionen

Suche Algorithmus/Ideen zum String-Kodieren...

Mdl / 9 Antworten / Baumansicht Nickles

Suche Algorithmus/Ideen - vorzugsweise in C/C++ (aber nat. keine Vorraussetzung) - zum String-Kodieren...

mit einer wesentlichen Anforderung:

Wenn sich zwei Strings auch nur minimal unterscheiden, sollte die Ausgabe i.d.R. komplett unterschiedlich sein.

Obwohl ich eher eine Unkenntlichmachung, als eine wirksame Verschlüsselung benötige, habe ich, weil gerade greifbar, den DES-Algorithmus auf zwei ähnliche Strings - zwei Dateinamen mit unterschiedl. Extention - angewandt und festgestellt, dass der dafür nicht ideal ist. Grund: DES verschlüsselt in 8-Byte-Blöcken. Sind somit die ersten 8 Zeichen der Dateinamen identisch sind auch die ersten 8 Zeichen der Zielnamen identisch.

Also: Irgendwelche Ideen, Verweise, etc. ?

Vielen Dank,

Mdl

bei Antwort benachrichtigen
Borlander Mdl „Suche Algorithmus/Ideen zum String-Kodieren...“
Optionen

Brauchst Du auch eine Umkehrfunktion um den Ergebnisstring wieder in den ursprünglichen umzuwandeln?

Ansonsten könntest Du Dir (kryptographische) Hashfunktionen mit MD5 oder das noch sicherere  und längere noch SHA1 anschauen. Diese haben zudem die Eigenschaft, dass sie ein Ergebnis mit konstanter Länge zurückliefern unabhängig von der Eingabelänge.

Das Phänomen, dass Du beobachtet hast ist unter https://de.wikipedia.org/wiki/Electronic_Code_Book_Mode noch mal recht anschaulich beschrieben. Um es kurz zu machen: Bei Verfahren mit Blocklängen unterhalb der maximalen Stringlänge schaut es schlecht aus mit ECB.

Was mir spontan noch so als Idee kommt: Du könntest jeweils Teilstrings unterhalb der Blocklänge mit Zufallsdaten aufüllen (Also z.B. 6 Zeichen + 2 zufällige Bytes). Damit wäre die Encodierung allerdings nicht mehr eindeutig, Decodierung jedoch noch zweifelsfei möglich durch Verwerfen der Zufallsdaten. Also nur bedingt Alltagstauglich.

Was ist denn das übergeordnete Ziel des Ganzen?

Gruß
Borlander

bei Antwort benachrichtigen
Mdl Borlander „Brauchst Du auch eine Umkehrfunktion um den Ergebnisstring ...“
Optionen

Hallo Borlander,

ja, sie müsste umkehrbar sein. Hashfunktionalität reicht nicht.

Der konkrete Zweck war, die Dateinamen einiger Dateien, die ich auf einem FTP-Server speichern wollte auch zu kodieren. Ich wollte da aber absichtlich nicht zusehr darauf eingehen, da ich leicht einen Workaround basteln kann, so dass für meinen spezifischen Fall keine Ähnlichkeit der Zieldateien besteht.

Aber ich fand das Problem an sich recht interessant und war/bin neugierig, ob es dafür eine vielleicht eine ideale Lösung gibt. Ideal wäre natürlich ein eindeutiges (und gleichlangem) Ergebnis.

Die Idee mit dem zufälligen Auffüllen ist prima. Zwei ähnliche Ausgangsstrings bekommen damit die gewünschten unterschiedlichen Zielstrings, leider aber natürlich auch, wie Du schon gesagt hast, die zwei identische Ausgangsstrings...

Viele Grüße,

Mdl

bei Antwort benachrichtigen
Borlander Mdl „Hallo Borlander, ja, sie müsste umkehrbar sein. ...“
Optionen
Der konkrete Zweck war, die Dateinamen einiger Dateien, die ich auf einem FTP-Server speichern wollte auch zu kodieren.

Dann solltest Du beim Einsatz eines beliebigen Verschlüsselungsverfahrens wie z.B. DES noch drüber nachdenken das Ergebnis anschließend noch so nachzubearbeiten, dass nur in Dateinamen erlaubte Zeichen auftreten können. Also kein "*" oder "/", z.B. mit base64url siehe https://de.wikipedia.org/wiki/Base64.

Ideal wäre natürlich ein eindeutiges (und gleichlangem) Ergebnis.

Was meinst Du mit gleichlang? (Ausgabelänge = Eingabelänge?)

Sofern Du kein Verfahren hast mit einer Blocklänge die exakt der Eingabelänge entspricht wirst Du ein bisschen zusätzlichen Platz mit einplanen müssen. Gebräuchlicher als mein spontaner Vorschlag wäre die Verwendung eines Salt um für jeder Datei einen anderen Schlüssel zu versehen. Diesen Salt als Ergänzung des geheinem Schlüssels müsste man dann allerdings auch mit im Dateinamen ablegen. Hätte dann also erst mal ein Prefix im Dateinamen für den Salt.

die zwei identische Ausgangsstrings

Was meinst Du mit zwei Ausgangsstrings?

base64url

bei Antwort benachrichtigen
Borlander Mdl „Hallo Borlander, ja, sie müsste umkehrbar sein. ...“
Optionen

Auch Interessant könnte ggf. noch mal ein Blick auf das FUSE-Dateisystem EncFS sein. Dateinamen werden dort auch verschlüsselt und es gibt verschiedene Verfahren dafür:

https://en.wikipedia.org/wiki/EncFS#Filename_encoding

bei Antwort benachrichtigen
Mdl Borlander „Auch Interessant könnte ggf. noch mal ein Blick auf das ...“
Optionen
Dann solltest Du beim Einsatz eines beliebigen Verschlüsselungsverfahrens wie z.B. DES noch drüber nachdenken das Ergebnis anschließend noch so nachzubearbeiten, dass nur in Dateinamen erlaubte Zeichen auftreten können. Also kein "*" oder "/", z.B. mit base64url siehe https://de.wikipedia.org/wiki/Base64.

Ist klar. Danke für den Link.

Ich könnte meine 'Anforderung' ja auch verallgemeinern in dem Sinn:

Sei M eine Menge aus 'gültigen' Zeichen, S(M) (StringMenge) die Menge aller Strings, die aus M erstellt werden können, len(s) Fkt. die die Länge von string s bezeichnet.  Suche Funktionen/Algorithmen scramble()/unscramble(), für die gilt:

    scrample(s) €SM für alle s€S(M)

    s=unscramble(scramble(s)) € SM für alle s€S(M)

    len(s)==len(scamble(s)) für alle s€S(M)

    scamble(s1)==scramble(s2), falls s1==s2 (Eindeutigkeit)

und dann eben meine Spezialforderung:

   scramble(s1) nicht 'ähnlich' zu scramble(s2), falls s1,s2 ähnlich

wobei für ähnlich jetzt hier mal die intuitive Vorstellung stehen bleiben soll

(Sorry, konnte nicht widerstehen...) 

Ob ich damit jetzt Menge der am Posting potientiell Interessierten jetzt sprunghaft ansteigt? ;-)

Vereinfacht könnten wir aber (erstmal) davon ausgehen, dass M aus der Menge aller möglichen Zeichen (char-Werte, '\x00', ..., '\xff', 0-255) bestehen kann.

Was meinst Du mit gleichlang? (Ausgabelänge = Eingabelänge?)

Ja, genau.

Man beachte, dass es sich bei dem von mir gesuchtem Alg. eigentlich mehr um eine Umarrangierung bzw. einfache Kodierung handelt.

Und nicht um ein Verschlüsselungsverfahren, das theoretisch, z.B. mit DES ja noch danach erfolgen könnte. Kombiniert wären dann ja auch ähnliche Ausgangsstrings danach nicht mehr ähnlich, wie bei 'nur' DES.

Für diese Umarrangierung ist für mich nicht so recht ersichtlich, warum der Zielstring länger sein muss.

Sofern Du kein Verfahren hast mit einer Blocklänge die exakt der Eingabelänge entspricht wirst Du ein bisschen zusätzlichen Platz mit einplanen müssen. Gebräuchlicher als mein spontaner Vorschlag wäre die Verwendung eines Salt um für jeder Datei einen anderen Schlüssel zu versehen. Diesen Salt als Ergänzung des geheinem Schlüssels müsste man dann allerdings auch mit im Dateinamen ablegen. Hätte dann also erst mal ein Prefix im Dateinamen für den Salt.

Aha, neuen Begriff gelernt: 'Salt'. Auch interessant.

Was meinst Du mit zwei Ausgangsstrings?

s1, s2 von oben

Auch Interessant könnte ggf. noch mal ein Blick auf das FUSE-Dateisystem EncFS sein.

Interessant!

bei Antwort benachrichtigen
Borlander Mdl „Ist klar. Danke für den Link. Ich könnte meine ...“
Optionen
Sei M eine Menge aus 'gültigen' Zeichen, S(M) (StringMenge) die Menge aller Strings, die aus M erstellt werden können

Dafür gibt es übrigens auch schon einen Begriff: https://de.wikipedia.org/wiki/Alphabet_%28Kryptographie%29 und formale Definitionen https://de.wikipedia.org/wiki/Alphabet_%28Informatik%29 + https://de.wikipedia.org/wiki/Kleenesche_und_positive_H%C3%BClle ;-)

scrample(s) \in SM für alle s \in S(M)

Initutiv würde ich hier bei Alphabeten deren Symbolanzahl keine Zweiterpotenz ist Probleme sehen diese Anforderung zu erfüllen, zumindest bei den aktuell gängigen, sicheren und gut erforschten Kryptoverfahren. Mit ROT13 oder ähnlichem würde das aber natürlich gehen…

(Sorry, konnte nicht widerstehen...) 

Eine Definition mit Levenshtein-Distanz hätte dem ganzen aber vielleicht noch den letzten Schliff gegeben ;-)

Man beachte, dass es sich bei dem von mir gesuchtem Alg. eigentlich mehr um eine Umarrangierung bzw. einfache Kodierung handelt.

Du suchst also was in Richtung Transposition bzw. Permutation? Wobei Du nicht nur irgendeine suchst, sondern eine für beliebige Input-Längen. Beim Einsatz von Verschlüsselungsverfahren mit fester Blocklänge müsstest Du zusätzlich dann noch die Forderung stellen, dass bei ähnlichen Strings möglichst wenige identische Blöcke auftreten. Wenn sich die Eingabe allerdings nur in einem Bit unterscheidet (z.B. Ziffer 1 statt 0 im Dateinamen) dann werden nach reine Permuatiotion am Ende alle Blöcke außer einem identisch bleiben.

Gruß
Borlander

bei Antwort benachrichtigen
Borlander Nachtrag zu: „Dafür gibt es übrigens auch schon einen Begriff: ...“
Optionen

Ergänzung:

Durch ungünstige Permutationen könntest Du übrigens auch ungewollt die Verschlüsselung schwächen, weil den üblichen in Dateinamen vorkommenden Zeichen das höchste Bit jedes Byte häufig 0 ist. Wenn diese Bits nun alle auf einem Haufen landen dann könnte man u.U. "sehr leicht" den Schlüssel herausbekommen…

bei Antwort benachrichtigen
Mdl Borlander „Dafür gibt es übrigens auch schon einen Begriff: ...“
Optionen
Eine Definition mit Levenshtein-Distanz hätte dem ganzen aber vielleicht noch den letzten Schliff gegeben ;-)

Wieder was dazugelernt....

Nur, wenn ich jetzt schreiben würde:

Für alle s1, s2 mit s1 ungleich s2 muss gelten:

  Levenshtein-Distanz < ...

findet sich bestimmt das ein oder andere s1, s2,

  für das das nicht zutrifft.

;-)

Ok, ich glaub jetzt ist genug Theorie

und ich fang mal mit der Implementierung an, bzw. verfeinere sie ein bisschen

Gruß und Danke,

Mdl

bei Antwort benachrichtigen
Borlander Mdl „Wieder was dazugelernt.... Nur, wenn ich jetzt schreiben ...“
Optionen
Für alle s1, s2 mit s1 ungleich s2 muss gelten:   Levenshtein-Distanz < ... findet sich bestimmt das ein oder andere s1, s2,   für das das nicht zutrifft. ;-)

Statt der recht komplex definierten Levenshtein-Distanz könnte man auch einfach den Hamming-Abstand als Abstandsmaß nutzen. Auf Basis Deiner obigen Definition und  dist() wäre es natürlich schon eine Funktion zu haben die nachfolgende Bedingung erfüllt:

dist(scramble(s1) ; scramble(s2)) >> dist(s1 ; s2)

Das wird sich aber so in der Tat nicht garantieren lassen wie Du schon festgestellt hast. Und spontan würde ich hier nicht mal für >= meine Hand ins Feuer legen. Wobei Einzelfälle auch nicht weiter tragisch wären.

Dann mach Dich mal ans werk. Würde mich natürlich interessieren, wie Deine Lösung am Ende ausschaut.

Gruß
Borlander

bei Antwort benachrichtigen