Searching fast colisionfree one-way function

[Shadow992]

Heyho guys,

my question is quite easy but it seems like the answer is really hard (maybe impossible to solve at all?).

I am searching for a colisionfree fast one way function. This function does not have to be very secure. A simple "Factorization" of givens number would be enough if we could make it colisionfree.

It is really important that I can guarantee no colisions at all or just very very few colisions (if no colisions is not possible).
The second really important thing is speed. The function must be as fast as possible.
Security is nearly unimportant because if breaking one "hash" would take about 2-5mins this is enough. If you want to break the "complete Problem" you would have to calculate 100 to 200 hashes which then will take around 200 to 1000mins and this is really more than enough.
Even 10mins for 100 "succesfully breaks" would be enough.

I know there are several really good and fast perfect hashing algorithms.
But the problem is I dont know the set of inputs.

How exactly I want to use it, is this way:

1. Input of my program will be a set of strings (length can vary between few chars and 100 and more chars). They will all be given as plaintext. So at this moment I could use a perfect hash.
2. After hashing all strings I will write them to a file, each "hashed" value will get a new line.

Then Ive got a second program which I want to spread with my generated text file.

The input of the second program will be a concrete word.
This program now calculates the hash and searches for this hash in my generated text file.
The problem is, the user should be able to add new hashed values, too.
So at this moment I am not longer able to use a perfect hash.

Why cant I use an encrypted database or something similiar?
The answer is quite simpel:
The second programm will be open source, so if I use a fixed password/username/etc. for encryption/authentification everyone could easily read all hashes and their corresponding values of database or decrypt text file easily.

So does anyone know a fast and colisionfree (at least nearly colisionfree) one way function for strings (but for ints its ok too then ill group chars up to an int)?

What I thought about was something of that:
Just multiply the value of each character with a variable, e.g.:

PHP Code:

var=new BigNum();
for (i=0;i<stringLength;i++)
{
   factorized.push(DoFactorization(str[i]));
   var*=str[i];
}
// do something with factorized numbers
// solving factorization of calculated bignum is really hard
// but solving factorization for my small numbers is quite easy so it should be fast 


This function is not colisionfree at all. So I thought Ill use the generated value as key for an encryption algorithm.

But this wont guarantee me colisionfreeness, too.
Because 2 different key with different plaintext may result in the same "hashed" value.

So does anyone have got a good suggestion?
Will e.g. using SHA256 and appending length of original string give me enough "colisionfreeness" to securely do searching for strings in the way I want to do it? Even if it would fit my needs. Generating a 256Bit number for strings with only one character isnt what i really want to do, but ok if there are no other solutions. And even if this is the only solution there is one more problem:
I would need a copyrightfree/zlib-licensed version of this hash function.

Just to note:
There will be many of these text files generated (I think around 1.000.000 of these files and more when time goes on). So hash must be extremely good for nearly any combination of strings from around 1 char to 1000 chars. There will be around (when user used second program completely) 1000 words/hashed values in the generated text file.

Thanks in advance for any suggestion.

[warfley]

Ich bin jetzt mal ganz dreist und antworte in Deutsch.

Du suchst also schlicht und ergreifend eine Funktion die zwar Injektiv ist, aber nicht invertierbar, wie du schön am Anfang schon vermutet hast ist das unmöglich

Eine injektive Funktion f : M → N lässt sich invertieren, denn zu jedem y ∈ f(M) existiert genau ein x ∈ M mit y = f(x).

Das heißt du musst deine Bedürfnisse runter schrauben auf einen Hash (wie du selbst schon gemerkt hast). Und da verstehe ich nicht warum du kein bekanntes Hash verfahren verwenden willst/kannst. Etwas besseres was die Anzahl an Kollisionen betrifft wirst du wohl nicht finden können.

Jeder könnte hier jetzt versuchen ein Hashverfahren sich auszudenken, aber besser als aktuelles SHA Hashing wird nichts davon sein.

PS: Und bezeichne bekannte verfahren bitte nicht als perfect Hash, in ein paar Jahren sind die auch schon outdated, die Hash Algorithmen sind nur aktuell gut, das zeigt auch schön der Werdegang von MD5, dem Algorithmus von dem mal lange dachte er hätte keine Kollisionen, bis er nun in der Versenkung für unbrauchbare Hashs verschwunden ist.
Und auch heute läuft bereits die suche nach einem SHA 6 Algorithmus um den aktuellen SHA 5 abzulösen wenn dieser nicht mehr gut ist

[Shadow992]

Originally Posted by warfley

Ich bin jetzt mal ganz dreist und antworte in Deutsch.

Du suchst also schlicht und ergreifend eine Funktion die zwar Injektiv ist, aber nicht invertierbar, wie du schön am Anfang schon vermutet hast ist das unmöglich



Das heißt du musst deine Bedürfnisse runter schrauben auf einen Hash (wie du selbst schon gemerkt hast). Und da verstehe ich nicht warum du kein bekanntes Hash verfahren verwenden willst/kannst. Etwas besseres was die Anzahl an Kollisionen betrifft wirst du wohl nicht finden können.

Jeder könnte hier jetzt versuchen ein Hashverfahren sich auszudenken, aber besser als aktuelles SHA Hashing wird nichts davon sein.

PS: Und bezeichne bekannte verfahren bitte nicht als perfect Hash, in ein paar Jahren sind die auch schon outdated, die Hash Algorithmen sind nur aktuell gut, das zeigt auch schön der Werdegang von MD5, dem Algorithmus von dem mal lange dachte er hätte keine Kollisionen, bis er nun in der Versenkung für unbrauchbare Hashs verschwunden ist.
Und auch heute läuft bereits die suche nach einem SHA 6 Algorithmus um den aktuellen SHA 5 abzulösen wenn dieser nicht mehr gut ist

Mit Perfect Hash ist auch wirklich die Gruppe der "Perfect Hashes" gemeint.
Z.b.

Oder


Nur verbieten mir 90% der perfect Hashes den Eingaberaum dynamisch zu erweitern ohne alle ungehashten Strings zu haben, was ich ja eben vermeiden möchte.
Mir scheint aber wohl, dass das die Einzige sowohl umsetzbare als auch von der Geschwindigkeit her beste Lösung ist. Dann werde ich wohl auf das dynamischen Hinzufügen von neuen Strings verzichten müssen.

Mit der Injektivität hast du vollkommen recht. Tatsächlich geht es mir auch nicht um darum, dass die Funktion nicht invertierbar ist, sondern es ausreichend schwer ist die Invertfunktion zu finden.

Als Beispiel kann man hier die Multiplikation von x sehr großen Primzahlen hernehmen. Oder es reichen sogar 2, wobei die anschließende Aufgabe daraus besteht die Primfaktorzerlegung dieser entstehenden Zahl zu ermitteln.

Die Faktorisierung von einer sehr großen Zahl N lässt sich nur mit pseudopolynomiellen Aufwand finden.
Habe ich jedoch diese große Zahl N bereits vorfaktorisiert (auf Zahlen kleiner gleich 256) ist das Finden der endgültigen Faktorisierung ein Scherz.

Ähnliches gilt für die Rabin-Funktion x^2 % n, wobei n eine Zahl bestehend aus der Multiplikation zweier Primzahlen p und q ist.

Es gibt also mehr als genug solcher "Funktionen" das Einzige was ich suche ist eine Funktion, die kolisionsfrei ist.

Angeblich soll die folgende Funktion kolisionsfrei sein und schwer umkehrbar:
z^x mod n, wobei n wieder p*q ist und z bzw. x beliebig aber groß sein sollten. Aber mir erscheint auch nach längerem Nachdenken keine Variante einzufallen, welche nicht entweder zu einfach umzukehren ist (nämlich wenn n > z^x für alle z,x) oder aber es doch zu Kolisionen kommen kann (zumindest theoretisch und in meinem Kopf).

Die "Standard"-Hashes reichen mir nicht weil ich garantieren muss, dass in den 1000 gehashten Wörtern keine Hashes doppelt vorkommen. Da geht es nicht um "Naja dann dauert es halt ein paar Sekunden länger bei wenigen Ausnahmen" sondern da geht es um ein "2x derselbe Hash und das ganze Programm funktioniert nicht mehr". Tatsächlich will ich aber unbedingt vermeiden, dass der Hash ein möglicher Fehlerherd sein könnte. Das Programm soll nicht wegen 2x denselben Hash (und selbst wenn es nur bei jedem 100.000 mal ausführen ist) kaputt gehen.

Ich will den Leuten, die das Programm benutzen garantieren können, dass egal wie oft sie das Programm starten, solange sie nichts am Programm ändern es immer gleich funktionieren wird. Egal welche Strings jetzt gehasht wurden.

Edit:
Wäre ein Public-Key-Verfahren in welchem ich lediglich den privaten Schlüssel mitliefere nicht auch eine Möglichkeit? Ich bin mir gerade unsicher ob man auf Basis vom privaten Schlüssel den öffentlichen Schlüssel berechnen kann, ich gehe aber stark davon aus.

[ComputerBaer]

Originally Posted by Shadow992

Edit:
Wäre ein Public-Key-Verfahren in welchem ich lediglich den privaten Schlüssel mitliefere nicht auch eine Möglichkeit? Ich bin mir gerade unsicher ob man auf Basis vom privaten Schlüssel den öffentlichen Schlüssel berechnen kann, ich gehe aber stark davon aus.

Aus dem privaten Schlüssel kann man den öffentlichen erzeugen, aus dem öffentlichen aber nicht den privaten. Wenn du also den privaten Schlüssel auslieferst, kannst du auch gleich komplett auf die Verschlüsselung verzichten.

Deinem Open-Source-Programm würde auch der öffentliche Schlüssel reichen, es soll ja nur verschlüsseln können.

Allerdings darf dein anderes Programm entweder nicht auf dem PC des Nutzers laufen (also z.B. eine Webseite) oder zumindest nicht den privaten Schlüssel enthalten (das muss auf deinem Server geschehen). Ansonsten ist es möglich den privaten Schlüssel aus deinem Programm zu extrahieren und der ganze Schutz ist nutzlos. Edit: Das Programm verschlüsselt doch auch nur, es reicht also auch hier der öffentliche Schlüssel. Den privaten Schlüssel könntest du also im grunde wegwerfen, nachdem du ihn erstellt hast.

---

Ich weiß jetzt nicht genau worum es geht, also sage ich einfach was ich mir grade denke:
Der Benutzer auf dessen PC beide Programme laufen sollte den Inhalt der verschlüsselten Datei kennen, immerhin hat er sie eingegeben, soweit richtig? Und dein Schutz soll verhindern das jemand einfach an den Inhalt kommt, weil er als "Passwort" für das zweite Programm dient, oder? Jedenfalls irgendwas in der Richtung, ist auch egal.

Du könntest darüber nachdenken, vielleicht für jeden Benutzer ein eigenes Schlüsselpaar zu generieren, dass sich dann nur auf diesem PC befindet. Wenn du den privaten Schlüssel dann noch mit einem Passwort sicherst, das der Benutzer festlegt oder du zufällig erzeugst und dann wegwirfst, sollte nicht mehr viel geschehen können. Der Benutzer muss dann nur jedes mal wenn er Werte mit dem privaten Schlüssel hinzufügen will das Passwort eingeben, zur Überprüfung durch das zweite Programm mit dem öffentlichen Schlüssel ist das Passwort nicht notwendig. Edit: Der Benutzer muss dann in keinem der beiden Programme das Passwort eingeben, da ja beide Programme nur verschlüsseln, aber keines die Daten entschlüsselt.

Auf diese Art ist das Schlüsselpaar am Sichersten. Wenn das über einen Server von dir läuft, könnte jemand den Server knacken und den Schlüssel entwenden, ob der dann ein Passwort hat oder nicht spielt da keine Rolle, das steht da ja auch irgendwo.

Edit: Das war doch mal ein umfangreicher Denkfehler bei mir, dafür könnte es dein Problem gelöst haben.

[Shadow992]

Originally Posted by ComputerBaer

Aus dem privaten Schlüssel kann man den öffentlichen erzeugen, aus dem öffentlichen aber nicht den privaten. Wenn du also den privaten Schlüssel auslieferst, kannst du auch gleich komplett auf die Verschlüsselung verzichten.

Deinem Open-Source-Programm würde auch der öffentliche Schlüssel reichen, es soll ja nur verschlüsseln können.

Allerdings darf dein anderes Programm entweder nicht auf dem PC des Nutzers laufen (also z.B. eine Webseite) oder zumindest nicht den privaten Schlüssel enthalten (das muss auf deinem Server geschehen). Ansonsten ist es möglich den privaten Schlüssel aus deinem Programm zu extrahieren und der ganze Schutz ist nutzlos. Edit: Das Programm verschlüsselt doch auch nur, es reicht also auch hier der öffentliche Schlüssel. Den privaten Schlüssel könntest du also im grunde wegwerfen, nachdem du ihn erstellt hast.

Oh das klingt nach einer ziemlich geilen Lösung.
Ich glaube den Weg sollte ich tatsächlich weiterverfolgen. Ich hatte in Erinnerung, dass man den privaten Schlüssel zum Verschlüsseln braucht und den öffentlichen zum Entschlüsseln.

Originally Posted by ComputerBaer

Ich weiß jetzt nicht genau worum es geht, also sage ich einfach was ich mir grade denke:
Der Benutzer auf dessen PC beide Programme laufen sollte den Inhalt der verschlüsselten Datei kennen, immerhin hat er sie eingegeben, soweit richtig? Und dein Schutz soll verhindern das jemand einfach an den Inhalt kommt, weil er als "Passwort" für das zweite Programm dient, oder? Jedenfalls irgendwas in der Richtung, ist auch egal.

Sowohl das Erste als auch das Zweite Programm sollen open source werden.
Das triffts relativ gut. Genaugenommen geht es darum, dass es einen Benutzer geben wird, der mit Programm #1 die Text-Datei generiert und in diese Datei bestimmte "Namen/Wöter/Funktionen" eingeben kann.
Anschließend kann er Programm #2 mit der generierten Datei weiterverbreiten, sodass andere Leute (ohne Wissen/Erfahrung) dieses "Pack" einfach verwenden können.
Daher ist es auch enorm wichtig, dass der Fehlerherd auf keinen Fall die Text-Datei ist, weil den "Entwicklern" kann ich vielleicht noch erklären was eine Kolision ist bzw. warum es nicht funktioniert.
Aber erkläre das mal Laien, die einfach nur das Programm benutzen wollen, mehr nicht.
Die "Verschlüsselung"/das "Hashing" soll verhindern, dass man "einfach so" den Klartext der Textdatei kopieren kann und es in seine eigenen Projekte verwendet.
Da ich bei dieser Datei nichts "parsen" muss, sondern nur schauen muss ob die vom (Laien-)Benutzer eingegebene Funktionen/etc. existieren und herausfinden muss an welcher Stelle sie existieren, muss ich das Ganze nie wieder entschlüsseln, nicht einmal zum Bearbeiten (im besten Falle).

Da das Ganze nur ein "relativ" einfacher Schutz sein soll reicht mir sowohl eine geringe Sicherheitsstufe als auch Komplexität des Algorithmuses aus.
Das Ganze soll es einfach nicht mehr lohnenswert machen, dass man den Inhalt kopiert, weil man für eine einzige Datei 10min aufwärts braucht.
Diese Text-Datei ist nämlich nur ein relativ unbedeutender Teil des Ganzen, weswegen man dann lieber mit den "kryptischen" (sprich den gehashten Values) weiterarbeitet als da 10min auf ein Ergebnis zu warten.

Originally Posted by ComputerBaer

Du könntest darüber nachdenken, vielleicht für jeden Benutzer ein eigenes Schlüsselpaar zu generieren, dass sich dann nur auf diesem PC befindet. Wenn du den privaten Schlüssel dann noch mit einem Passwort sicherst, das der Benutzer festlegt oder du zufällig erzeugst und dann wegwirfst, sollte nicht mehr viel geschehen können. Der Benutzer muss dann nur jedes mal wenn er Werte mit dem privaten Schlüssel hinzufügen will das Passwort eingeben, zur Überprüfung durch das zweite Programm mit dem öffentlichen Schlüssel ist das Passwort nicht notwendig. Edit: Der Benutzer muss dann in keinem der beiden Programme das Passwort eingeben, da ja beide Programme nur verschlüsseln, aber keines die Daten entschlüsselt.

Auf diese Art ist das Schlüsselpaar am Sichersten. Wenn das über einen Server von dir läuft, könnte jemand den Server knacken und den Schlüssel entwenden, ob der dann ein Passwort hat oder nicht spielt da keine Rolle, das steht da ja auch irgendwo.

Edit: Das war doch mal ein umfangreicher Denkfehler bei mir, dafür könnte es dein Problem gelöst haben.

Direkt speichern auf dem PC geht auf Grund meiner Erklärung weiter oben natürlich nicht. Aber das macht nichts, ich kann einfach in meine "Konfigurations"-Datei, die mit verschickt/generiert wird den public Key speichern lassen, damit hat jeder Benutzer einen anderen private/public Key (oder zumindest viele) und damit würde auch das Herausfinden eines einzigen private Keys nicht automatisch die Sicherheit aller im Umlauf befindlichen Dateien beeinflussen.

Ich denke tatsächlich, dass das die Beste Lösung ist.
Danke für eure Hilfe, vielleicht fällt jemanden (nur Interessehalber) doch noch eine gute dafür geeignete One-Way-Funktion ein.

Edit:
Ein tolles Feature daran ist auch noch, dass der Entwickler jetzt mit Hilfe des private Keys seine Text-Datei wieder herstellen kann, sollte er die original Wörter/Funktionen verloren haben.
Top das gefällt mir sehr gut.

[MrSm!th]

Angeblich soll die folgende Funktion kolisionsfrei sein und schwer umkehrbar:
z^x mod n, wobei n wieder p*q ist und z bzw. x beliebig aber groß sein sollten. Aber mir erscheint auch nach längerem Nachdenken keine Variante einzufallen, welche nicht entweder zu einfach umzukehren ist (nämlich wenn n > z^x für alle z,x) oder aber es doch zu Kolisionen kommen kann (zumindest theoretisch und in meinem Kopf).

Da RSA auf diesem Problem aufbaut, kannst du davon ausgehen, dass es schwierig genug ist. Allerdings müssen die Primzahlen dafür verdammt groß sein (RSA Keys sind mind. 2048 Bit lang, um als sicher/unknackbar zu gelten). Es ist allerdings auch verdammt langsam im Vergleich zu symmetrischen Verfahren wie AES.

Prinzipiell ist es aber durchaus korrekt. Man nehme ein beliebiges Public-Key-Verfahren (wie z.B. RSA), teile den Private-Key niemandem mit (offenbar ist Entschlüsselung keine Anforderung) und fertig ist die kollisionsfreie Einwegfunktion. Ein Hash ist das dann nicht mehr, weil die Ausgabedaten genau so groß sind wie die Eingabedaten, aber das ist auch der einzige Weg, wie es absolut kollisionsfrei bleiben kann.

Die "Standard"-Hashes reichen mir nicht weil ich garantieren muss, dass in den 1000 gehashten Wörtern keine Hashes doppelt vorkommen. Da geht es nicht um "Naja dann dauert es halt ein paar Sekunden länger bei wenigen Ausnahmen" sondern da geht es um ein "2x derselbe Hash und das ganze Programm funktioniert nicht mehr". Tatsächlich will ich aber unbedingt vermeiden, dass der Hash ein möglicher Fehlerherd sein könnte. Das Programm soll nicht wegen 2x denselben Hash (und selbst wenn es nur bei jedem 100.000 mal ausführen ist) kaputt gehen.

Für SHA-512 (und das ist gerade mal SHA2) sind bisher keine Kollisionen gefunden worden und damit wird weltweit ein Vielfaches der Datenmenge von ein 100.000 Wörtern gehasht. Unzählige Anwendungen bauen auf der Annahme auf, dass kein Hash doppelt vorkommt und funktionieren bis heute. Wenn du eine Kollision für SHA2 finden solltest, kannst du dich auf diverse Interviewanfragen der Fachpresse gefasst machen. Damit dürftest du recht schnell sehr bekannt im Gebiet der Kryptologie werden.

Entweder behältst du die Länge der Eingabedaten bei, dann hast du de facto eine Verschlüsselung anstatt einer Hashfunktion. Oder du hashst die Daten, hast dann aber die - theoretisch vorhandene, aber sehr unwahrscheinliche - Möglichkeit einer Kollision. Eine bessere Hashfunktion mit geringerer Kollisionswahrscheinlichkeit als aktuelle Standards wirst du wahrscheinlich nicht einfach mal so finden. Falls doch, siehe meine Aussage zu den Interviewanfragen.

Ein asymmetrisches Verschlüsselungsverfahren passt eigentlich am besten zu deinen Anforderungen, wäre jedoch vergleichsweise langsam (wobei es bei dir auch keine >2048 Bit Keys sein müssten, 1024 reichen locker). Einen SHA-Hash zu berechnen geht dagegen recht schnell, denn auf Geschwindigkeit sind derartige Verfahren ausgelegt, da hast du dann aber wieder das geringe Restrisiko, dass es Kollisionen geben wird.

Wäre ein Public-Key-Verfahren in welchem ich lediglich den privaten Schlüssel mitliefere nicht auch eine Möglichkeit? Ich bin mir gerade unsicher ob man auf Basis vom privaten Schlüssel den öffentlichen Schlüssel berechnen kann, ich gehe aber stark davon aus.

Umgekehrt, du teilst nur den öffentlichen Schlüssel mit und verwirfst den privaten. Das ist dann das, was ich oben geschildert habe.


Edit:

Meh, ich hätte erst zuende lesen sollen. Ich lasse die teilweise redundanten Informationen trotzdem mal stehen.

Ich glaube den Weg sollte ich tatsächlich weiterverfolgen. Ich hatte in Erinnerung, dass man den privaten Schlüssel zum Verschlüsseln braucht und den öffentlichen zum Entschlüsseln.

Es spielt für das Verfahren keine Rolle. Du kannst sowohl den öffentlichen als auch den privaten Schlüssel zur Verschlüsselung verwenden, solange dann der jeweils andere Schlüssel zur Entschlüsselung verwendet wird. Das funktioniert in beide Richtungen.
Es ist nur wichtig, dass der private Schlüssel privat bleibt, da man aus ihm den öffentlichen berechnen kann. Ob du nun willst, dass die Öffentlichkeit nur entschlüsseln oder nur verschlüsseln kann, hängt vom Anwendungsfall ab (bei Zertifikaten würdest du z.B. mit dem privaten Schlüssel verschlüsseln bzw. signieren und mit dem öffentlichen entschlüsseln bzw. die Signatur überprüfen).

[Serraniel]

Was das private public Key Verfahren angeht kann man mit beiden Schlüssen "verschlüsseln", je nachdem was man braucht.
Ich will jetzt nicht mit Alice und Bob anfangen da ich denke, dass dir die Kurzform ausreicht bei deinen Kenntnissen:
Wenn du eine Nachricht verschlüsseln willst, dass nur der Empfänger sie lesen kann, verschlüsselst du die Nachricht mit dem public key des Empfängers.
Wenn es dir um Authentizität/Signatur geht, kannst du die Nachricht mit deinem private key verschlüsseln. Diese kann man dann mit deinem public key entschlüsseln (und zwar jeder). Damit stellt man sicher, dass auch wirklich du der Absender warst, da nur du deinen private key kennst.

Und beide Anwendungen haben gemeinsam, dass der private key nur dir bekannt ist.

[Shadow992]

Originally Posted by MrSm!th

Da RSA auf diesem Problem aufbaut, kannst du davon ausgehen, dass es schwierig genug ist. Allerdings müssen die Primzahlen dafür verdammt groß Sein (RSA Keys sind mind. 2048 Bit lang, um als sicher zu gelten). Es ist allerdings auch verdammt langsam im Vergleich zu symmetrischen Verfahren wie AES.

Prinzipiell ist es aber durchaus korrekt. Man nehme ein beliebiges Public-Key-Verfahren (wie z.B. RSA), teile den Private-Key niemandem mit (offenbar ist Entschlüsselung keine Anforderung) und fertig ist die kollisionsfreie Einwegfunktion. Ein Hash ist das dann nicht mehr, weil die Ausgabedaten genau so groß sind wie die Eingabedaten, aber das ist auch der einzige Weg, wie es kollisionsfrei bleiben kann.

Für SHA-512 (und das ist gerade mal SHA2) sind bisher keine Kollisionen gefunden worden und damit wird weltweit ein Vielfaches der Datenmenge von ein 100.000 Wörtern gehasht. Wenn du eine Kollision für SHA2 finden solltest, kannst du dich auf diverse Interviewanfragen der Fachpresse gefasst machen. Damit dürftest du recht schnell sehr bekannt im Gebiet der Kryptologie werden.

Ich weiß nicht, wie du darauf kommst, dass du etwas Besseres finden wirst als alle anderen Kryptoanalytiker der Welt, aber du kannst von Folgendem ausgehen:

Entweder du verzichtest auf die Einweg-Eigenschaft oder auf die geringere Kollisionswahrscheinlichkeit.
Heißt: Entweder behältst du deine eindeutigen Werte, indem du diese direkt oder verschlüsselt (und eben nicht gehasht) in deine Datei schreibst oder du machst deine eigene Hashfunktion, die dann aber eine höhere Kollisionswahrscheinlichkeit haben wird.
Den dritten Fall, nämlich, dass du eine ausreichend sichere Einwegfunktion mit geringerer Kollisionswahrscheinlichkeit als die der aktuellen Standards findest, wird es höchstwahrscheinlich nicht geben. Wenn doch, siehe oben.

Aktuell klingt es für mich danach, dass ein Verschlüsselungsverfahren hier angebrachter wäre, weil es keine Hashfunktion geben kann, die beliebige Daten in einen Hash aus einer begrenzten Wertemenge umwandeln, ohne dass Kollisionen auftauchen. Allerdings müsstest du dafür den Schlüssel verfügbar machen, es sei denn, du entscheidest dich für ein asymmetrisches Verfahren. Das würde alle bisher von dir genannten Anforderungen erfüllen, wäre jedoch vergleichsweise langsam. Einen SHA-Hash zu berechnen geht dagegen recht schnell, denn auf Geschwindigkeit sind derartige Verfahren ausgelegt (da hast du dann aber wieder die - wenn auch sehr sehr unwahrscheinliche - Möglichkeit, dass es Kollisionen geben wird).

Darf man nach mehr Details zu deinem Anwendungsfall fragen? Vielleicht lässt sich dein Problem anders lösen.

Umgekehrt, du teilst nur den öffentlichen Schlüssel mit und verwirfst den privaten. Das ist dann das, was ich oben geschildert habe.

Naja 95% der Hashe reizen ja einen "Weg" komplett aus.
Entweder sie sind auf enorme Geschwindigkeit ausgelegt (wie z.B. Hashing-Verfahren für Hashtables) oder auf enorme Sicherheit und dennoch einigermaßen schnell (SHA2, etc.) oder aber auf Kolisionsfreiheit+Geschwindigkeit (für große Datenbanken z.B. perfect Hashing).
Was ich aber brauche ist etwas, das weder besonders sicher sein muss (aber auch nicht in Bruchteilen einer Millisekunde umkehrbar ist), noch außerordentlich schnell sein muss (klar je schneller desto besser, aber es gibt kein "Totschlag"-Kriterium bei der Zeit), dafür aber Kolisionsfreiheit garantieren kann.
Anwendungsgebiete für derartige Algorithmen gibt es meiner Meinung nach relativ wenige, weswegen es dazu wohl auch nur wenige Leute geben wird, die sich mit den Anforderungen näher beschäftigen.
Daher war ich eigentlich davon überzeugt, dass ich mir zumindest teilweise selbst etwas einfallen lassen muss (und bisher kennt ja auch niemand eine derartige Funktion oder kann mir gewiss sagen, dass es soetwas nicht gibt, was meine Vermutung wohl bestätigt).

Konkret geht es um eine Art Schutz für meinen Interpreter.
Dem Problem, welchem ich momentan gegenüber stehe ist folgendes:

Ich möchte, dass man Befehle von einem Server empfangen kann und diese mein Interpreter anschließend auch ausführen kann. In PseudoCode-C++ also in etwa so:

PHP Code:

void myOwnFunc(int param1)
{
  // Do something
}

int main()
{
  string str=DownloadCommands("http ...");
  // in str könnte z.b. folgendes drin stehen: "myOwnFunc(21)"
  interpretCommand(str);
} 


Mein Interpreter läuft einmalig bevor er einen Befehl ausführt über das komplette Skript und schreibt sich die Zeile+Namen der Funktion in eine Map, damit wenn jemand später "interpretCommand" aufruft die Zuordnung eindeutig und schnell passiert.

Es ist also wichtig, dass der Interpreter auch Funktionen, die als String gegeben sind interpretieren kann. Gleichzeitig möchte ich aber eigentlich ein "Umbenennen" der Funktionen durchführen, damit Rückschlüsse auf den Funktionsnamen nicht mehr einfach so möglich ist.

Für die Strings, die fest in den zu interpretierenden Code integriert sind ergibt sich dadurch keinerlei Probleme, die könnte ich einfach mit umbenennen Probleme gibt es nur wenn mein Pseudo-C++-Code von oben in das umgewandelt wird:

PHP Code:

void asdiuhuawdkjasdj(int param1)
{
  // Do something
}

int main()
{
  string str=DownloadCommands("http ...");
  // in str könnte z.b. folgendes drin stehen: "myOwnFunc(21)"
  interpretCommand(str);
} 


In meiner Interpreter-Map wird jetzt anschließend nur der Eintrag "asdiuhuawdkjasdj" existieren, der Programmierer hatte seine Funktion aber "myOwnFunc" gennant weswegen er auch erwartet, dass er sie von außen per Texteingabe o.ä. mit diesem Namen aufrufen kann.

Dem Programmierer jetzt aber die Last auf zu erlegen, dass er die umbenannten Funktionen benutzt anstatt der normalen fände ich mehr als unangenehm.

Deswegen brauche ich ein Mapping von "Normal" -> "Umbenannt".
Da ich sowohl den Interpreter als auch den Compiler Open-Source machen will kann ich die Schiene "Security by Obscurity" zumindest bezogen auf meinen Compiler/Interpreter-Code vergessen.

Ich denke jetzt erkennt man auch warum die Sicherheitsstufe nicht sehr wichtig ist. Denn wenn jemand 10 oder mehr Minuten wartet bis er alle Funktionen "zurückgewandelt" hat, dann hat er es wirklich mehr als verdient die original Funktionen zu sehen. Vor allem weil die original Namen natürlich nur einen relativ kleinen Teil des Codes darstellen. Die restlichen Hürden, wie variablen Umbenennungen etc. sind unumkehrbar gemacht, das heißt effektiv gesehen bringt es nicht so gigantisch viel 10min in das reversen der Namen zu stecken.

Dass jedoch SHA2 bisher so "kolisionsfrei" ist, wusste ich nicht. Dennoch würde da das Problem bestehen bleiben, dass Namen mit 2 Buchstaben plötzlich 256Bit und mehr lang sind (je nach Version), was sich natürlich negativ auf die Datei-Größe auswirkt und ich deswegen umgehen will.

Mir scheint also die asymmetrische Verschlüsselung als perfekt. Garantierte Kolisionsfreiheit und variable Länge sind genau die 2 Sachen, die mir enorm wichtig sind. Selbst wenn es bei SHA2 bisher noch keine Kolisionen gab und man auch noch ewig nach welchen sucht, ist mir die Garantie doch viel mehr Wert.

Vor allem weil bei einem Hash, der definitionsgemäß eine feste Länge besitzen muss, immer Kolisionen vorhanden sind, ob man es schafft genau diese Eingaben zu generieren ist natürlich eine andere Sache, aber es gibt sie theoretisch.

Originally Posted by Serraniel

Was das private public Key Verfahren angeht kann man mit beiden Schlüssen "verschlüsseln", je nachdem was man braucht.
Ich will jetzt nicht mit Alice und Bob anfangen da ich denke, dass dir die Kurzform ausreicht bei deinen Kenntnissen:
Wenn du eine Nachricht verschlüsseln willst, dass nur der Empfänger sie lesen kann, verschlüsselst du die Nachricht mit dem public key des Empfängers.
Wenn es dir um Authentizität/Signatur geht, kannst du die Nachricht mit deinem private key verschlüsseln. Diese kann man dann mit deinem public key entschlüsseln (und zwar jeder). Damit stellt man sicher, dass auch wirklich du der Absender warst, da nur du deinen private key kennst.

Und beide Anwendungen haben gemeinsam, dass der private key nur dir bekannt ist.

Dankeschön für die kurze Aufklärung.