kleine theorie: komprimierung durch MD5 möglich?

[Bashar]

loki1985 schrieb:

ok, ich habe da nicht so den durchblick. nur eben bräuchte mann für so einen test ein system welches auf möglichst wenige gleiche hashes ausgelegt ist....

Das ist jeder vernünftige Hash-Algorithmus. Aber möglichst wenig heißt in deinem Fall immer noch 2^128 auf eins.

Ehrlich gesagt machst du ungefähr den Eindruck von einem, der ein Perpetuum Mobile bauen will.

[loki1985]

Bashar schrieb:

Ehrlich gesagt machst du ungefähr den Eindruck von einem, der ein Perpetuum Mobile bauen will.

ich weiss. aber manchmal gönne ich es mir einfach, etwas rumzuspinnen
nur bei dem PM bin ich schneller darauf gekommen, dass es nicht möglich ist (oder doch )

[Gerard]

wenn du weniger reden und mehr implementieren würdes, wärst du zu den gleichen schluss gekommen wie ich

man kann mit hashes schon komprimieren aber auch nicht mehr als man das mit normalen komprimierungs methoden kann

crc8 ist eine crc32 algo abgewandelt auf 8 bit und mit einer etwas anderen streung
next_pass und next_pass2 sind zwei funktion die ich mal benutz haben für brutforce verschlüsselung knacken

hier mein code (bevor er auf meiner hd versauert)

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iterator>
#include <string>
#include <cstring>
#include <bitset>
using namespace std;

#include <boost\cstdint.hpp>
using namespace boost;

template<typename Iterator>
uint8_t crc8(Iterator begin, Iterator end)
{
    uint8_t res = 0;
    for(;begin != end; ++begin)
    {
        res = *begin + (res << 3) - res;
    }
    return res;
}

void next_pass(string & str, size_t current = 0)
{
    if(current == str.size())
        str.push_back('a');
    else if(str[current] == 'z')
    {
        str[current] = 'a';
        next_pass(str, current + 1);
    }
    else
        str[current]++;
}

void next_pass2(string & str, size_t current = 0)
{
    if(current == str.size())
        str.push_back(char(0));
    else if(str[current] == 0xFF)
    {
        str[current] = char(0);
        next_pass2(str, current + 1);
    }
    else
        str[current]++;
}

template<typename Iterator>
std::bitset<32> to5bin(Iterator begin, Iterator end)
{
    std::bitset<32> res;
    res &= *begin - 'a';
    for(;begin != end; ++begin)
    {
        res <<= 5;
        res |= *begin - 'a';
    }
    return res;
}

std::string from5bin(std::bitset<32> & r)
{
    string s = "";
    for(int k = 0; k < 6; ++k)
    {
        s.push_back(char((r & 31).to_ulong() + 'a'));
        r >>= 5;
    }
    reverse(s.begin(), s.end());
    return s;
}

int main()
{
    srand(42);

    string ein;
    int count = 0;
    cin >> ein;

    std::bitset<32> r = to5bin(ein.begin(), ein.end());

    char topress[5] = { 0 };
    *(int*)topress = r.to_ulong();

    uint8_t crc = crc8(topress, topress + 4);

    cout << hex << *(int*)topress << endl;
    cout << hex << (int)crc << endl;

    char gen[5] = { 0 };
    while(*(int*)topress != *(int*)gen)
    {
        if(crc == crc8(gen, gen+4))
        {
            count++;
        }
        (*(int*)gen)++;
    }

    cout << hex << count << endl;

    string pw;
    int t[256] = {0};
    for(int i = 0; i < 0xFFF; ++i)
    {
        t[crc8(pw.begin(), pw.end())]++;     
        next_pass2( pw );
    }

   // copy(t, t + 256, std::ostream_iterator<int>( cout, "\n"));
    cin.get();

    return 0;
}

[Jester]

Gerard schrieb:

man kann mit hashes schon komprimieren aber auch nicht mehr als man das mit normalen komprimierungs methoden kann

Wie das? Eine Hash-Funktion soll doch eine große Datenmenge möglichst gut streuend auf eine kleine Datenmenge abbilden. Dabei ist es natürlich unumgäglich,daß verschiedene Ausgangsn den selben Wert erhalten.

Ein Kompressionsalgo soll ebenfalls eine Datenmenge auf eine andere abbilden. Dabei soll die Darstellung nach der Abbildung möglichst oft kürzer sein als vorher. Aber es soll (bei verlustfreier Komprimierung) aus den komprimierten Daten die ursprünglichen zu rekonstruieren, das geht aber nur, wenn immer höchstens ein Datensatz auf jeden komprimierten Datensatz abgebildet wird. Das ist etwas was eine Hash-Funktion aber per Definition nicht leistet.

Für Mathematiker: Hash-Funktion sind nicht injektiv, verlustfrei Kompressionsfunktionen müssen das aber sein.

MfG Jester

[TomasRiker]

Wenn ich Loki richtig verstanden habe, dann meint er es wie folgt:
Klar ist, dass ein einziger Hash-Wert nichts bringt.
Wenn man aber noch einen Zweiten hinzufügt (und zwar einen, den man mit Hilfe eines anderen Algorithmus generiert hat), dann könnte es möglich sein, die Originaldaten sicher zu rekonstruieren.

Beispiel:
Der Text "HALLO, ICH BIN EIN TEXT!" würde vom Hash-Algorithmus 1 auf den Wert 66123178 abgebildet. Natürlich gibt es noch viele weitere Texte, die ebenfalls auf diesen Wert abgebildet würden.
Jetzt generiert man mit einem anderen Algorithmus noch einen Hash-Wert: 381941.
Dann speichert man die Werte 66123178 und 381941. Das könnte jetzt eindeutig sein, sodass nur der Text "HALLO, ICH BIN EIN TEXT!" die richtigen Hash-Werte bei beiden Algorithmen liefert.
Wenn das noch nicht reicht, könnte man einen dritten, vierten ... Hash-Wert hinzufügen, jeweils mit einem anderen Algorithmus generiert.

[net 0]

TomasRiker schrieb:

Der Text "HALLO, ICH BIN EIN TEXT!" würde vom Hash-Algorithmus 1 auf den Wert 66123178 abgebildet. Natürlich gibt es noch viele weitere Texte, die ebenfalls auf diesen Wert abgebildet würden.
Jetzt generiert man mit einem anderen Algorithmus noch einen Hash-Wert: 381941.
Dann speichert man die Werte 66123178 und 381941. Das könnte jetzt eindeutig sein, sodass nur der Text "HALLO, ICH BIN EIN TEXT!" die richtigen Hash-Werte bei beiden Algorithmen liefert.

kann ich mir auch vorstellen, dass dadurch die mehrdeutigkeit sinkt. das problem ist aber: wie kriege ich die originaldaten wieder. alle hashwerte liefern eine übelst grosse menge an ausgangswerten die passen. alle zu berechnen und zu vergleichen würde wohl jahre dauern

[Gerard]

Jester schrieb:

Gerard schrieb:

man kann mit hashes schon komprimieren aber auch nicht mehr als man das mit normalen komprimierungs methoden kann

Wie das? Eine Hash-Funktion soll doch eine große Datenmenge möglichst gut streuend auf eine kleine Datenmenge abbilden. Dabei ist es natürlich unumgäglich,daß verschiedene Ausgangsn den selben Wert erhalten.

ich habe mir noch mal überlegt wie ich das gemacht habe:

sagen wir mal du hast ein 4 byte string, du errechnest dazu eine 2 byte hash,
jetzt haben wir aus 4 byte 2 byte gemacht, aber wir haben noch das problem das die hash nicht eindeutig diesen 4 bytes zu geordnet werden kann
die lösung des problem ist, per bruteforce gehst alle möglichen 4 byte strings durch, errechnest die hash und jeder kolision zählst du mit (kolZ)
am ende hast du eine 2 byte hash und ein 2 byte grosse zahl (kolZ)

um zu dekomprimieren hast du die hash und kolZ, du gehst wieder alle möglichen 4 byte strings durch, jedes mal wenn der 4 byte string die hash ergibt die dir übergeben wurde zählst du mit, das tust du solange bis kolZ mal der übergebene hash errechnet wurde,

(bis jetzt wurde aus einen 4 byte string, eine 2 byte hash und 2 byte zahl, also noch nix wurde eigentlich komrimiert)

kann man mir bisher folgen?

der trick wie man damit komrimiert ist, wenn man weiss das es ein Text ist der aus a-z A-Z besteht, dann probiert man nicht alle 4 byte strings aus die möglich sind (beim komprimieren und dekomrimieren), sondern nur 4 byte strings die aus a-z A-Z bestehen dadurch sinkt die anzahl der möglichen kolisionen und wir kommen mit nur 1 byte zahl aus, tada
und das interesante ist sogar das die kolZ immer eine bestimmte max größe hat

@TomasRiker
ob du ein algo oder zwei algos benutzt ist im grunde genommen egal, probiere es doch mit etwas kleiner massstab aus es sollte ja kein unterschied machen ob du "HALLO, ICH BIN EIN TEXT!" oder eine 16 bit zahl mit zwei 4 bit hashes zu komprimieren, ich kann dir sagen das es minimum 256 * doppel kolisionen geben wird (d.h. beide hash werte werden sagen das es die zahl ist aber sie wirds nicht sein).
wir brauchen erstmal ein beweis das es überhaupt möglich ist, das wir die hardware noch nicht zu haben ist ein anderes problem

*(je nach qualität der hash algos wird die zahl näher an die 256 kommen)

[Bashar]

TomasRiker schrieb:

Beispiel:
Der Text "HALLO, ICH BIN EIN TEXT!" würde vom Hash-Algorithmus 1 auf den Wert 66123178 abgebildet. Natürlich gibt es noch viele weitere Texte, die ebenfalls auf diesen Wert abgebildet würden.
Jetzt generiert man mit einem anderen Algorithmus noch einen Hash-Wert: 381941.
Dann speichert man die Werte 66123178 und 381941.

Das heißt, die Kompression wird schlechter. Man könnte auch sagen, dass Hash-Algorithmus 3 den Wert 66123178381941 generiert, und damit sind wir in der gesamten Betrachtung back to square one.

Das könnte jetzt eindeutig sein, sodass nur der Text "HALLO, ICH BIN EIN TEXT!" die richtigen Hash-Werte bei beiden Algorithmen liefert.

"Könnte"? Es ist frühestens in dem Moment eindeutig, in dem nicht mehr komprimiert wird. Das sind absolute Grundlagen der Informationstheorie, was ist daran so schwierig?

[Sgt. Nukem]

TomasRiker schrieb:

Wenn ich Loki richtig verstanden habe, dann meint er es wie folgt:
Klar ist, dass ein einziger Hash-Wert nichts bringt.
Wenn man aber noch einen Zweiten hinzufügt (und zwar einen, den man mit Hilfe eines anderen Algorithmus generiert hat), dann könnte es möglich sein, die Originaldaten sicher zu rekonstruieren.

Das nennt man Double Hashing und ist doch gängige Methode bei Hashtabellen und Co.?!

[ness]

Hä? Ich verstehe den Gedankengang nicht, wie ihr komprimieren wollt. Sagen wir mal, wir wollen ein universell anwendbares Programm schreiben. Dieses müsste also so viele hashes erzeugen, bis es eindeutig ist. Erfinden wir mal eine Algorithmus, der aus 4 bytes ein ein byte hash generiert. Da wir 2³²=4294967296 Möglichkeiten auf 2⁸=256 Möglichkeiten abbilden, werden im Durchschnitt 16777216=2²⁴ Werte den selben hash ergeben. Ergo: wir haben exakt soviel ungenauigkeit erzeugt wie wir komprimiert haben. Toll! Aber OK, dann halt der nächste hash-algo. Bildet 3 bytes auf eines ab. Überschneidungen: 65536=2¹⁶ Weiter! Unsere 3. hash-funktion bildet 2 bytes auf eins ab. Überschneidungen: 256=2⁸ So, jetzt können wir das letzte byte direkt abbilen, haben von 4 auf 4 bytes komprimiert. Aber wir haben unser pulver noch nicht verschossen. Wir könnten ja einfach einen anderen hash algorithmus als 2. benutzen, der die Werte möglichst anders verteilt. Sagen wir mal, der erste algo sah so aus:

unsigned char hash_1(unsigned l)
{
    return l/16777216;
};

Dann sind die Wert 0-16777216,16777217-33554432 und so weiter.
Eine andere Funktion könnte sein:

char hash_2(unsigned l)
{
    return l%256;
};

Bei ihr allein sind 0,256,512,768,1024 sowie 1,257,513,769,1025 usw. mehrdeutig.
Zusammen sind jetzt noch 0,256,512,768,1024 usw. bis 65536*256 sowie 1,257,513,769,1025 bis 65536*256+1 mehrdeutig.Also exakt 65536/256*256=65536=2¹⁶ mehrdeutig, genau soviel wie wir gespart haben. Wie bashar schon als quintessenz festgestellt hat: Es ist frühestens in dem Moment eindeutig, in dem nicht mehr komprimiert wird. Man müsste nur passende hasg_3 und hash_4 finden.

[TomasRiker]

Bashar schrieb:

"Könnte"? Es ist frühestens in dem Moment eindeutig, in dem nicht mehr komprimiert wird. Das sind absolute Grundlagen der Informationstheorie, was ist daran so schwierig?

Ist ja schon gut, ich hatte da einen Denkfehler.

[Gerard]

Bashar schrieb:

Das könnte jetzt eindeutig sein, sodass nur der Text "HALLO, ICH BIN EIN TEXT!" die richtigen Hash-Werte bei beiden Algorithmen liefert.

"Könnte"? Es ist frühestens in dem Moment eindeutig, in dem nicht mehr komprimiert wird. Das sind absolute Grundlagen der Informationstheorie, was ist daran so schwierig?

wo wären wir heute wenn unsere vorfahren sich auf absolute grundlagen verlassen hätten

[Jester]

Vielleicht schon ein gutes Stück weiter.

[the_alien]

Genau, weil Grundlagenforschung garnichts bringt!

[Walli]

the_alien schrieb:

Genau, weil Grundlagenforschung garnichts bringt!

Ja ne, is klar!

[evilissimo]

Walli schrieb:

the_alien schrieb:

Genau, weil Grundlagenforschung garnichts bringt!

Ja ne, is klar!