[quote=Ishka,05.08.2004, 16:45]Die von dir angesprochene Lösung setzt vorraus, daß ich ein Programm hab, was in einer Blackbox läuft und Daten raussendet.[/quote]
deine randbedingungen kenn ich nicht...
im grunde hast du aber keine chance: da ein g(x), mit x nicht in f, ja immer irgendwie berechnet werden muss, und auf Grund der Vorbedingung g(m) = g(n) mit m = n, auch von von x abhängt. da du aber keine blackbox hast, kann man g(x) immer nachrechnen.

kannst denn an f was drehen?
wenn f ein argument bekommt, das unbekannt ist, wird ein zufälliges erzeugt; gleichzeitig muss sich f dann aber merken, dass der wert generiert und nicht gespeichert wurde

[quote=esskar,05.08.2004, 17:03][quote=renee,05.08.2004, 16:56]kannst du nicht rsa dafür benutzen??[/quote]
dann bräuchte er ja public und private key für.[/quote]
kann er doch berechnen... der algorithmus ist doch bekannt...

[quote=Ishka,05.08.2004, 17:08]oder er vergleicht die verschlüsselten Werte[/quote]
Anmerkung:

c := Verschlüsselungsfunktion
k := Schlüssel
x := Wert
y := Wert

es gilt:

[quote=renee,05.08.2004, 17:12]der algorithmus ist doch bekannt...[/quote]
[color=Red]NEVER WRITE YOUR OWN CRYPTO CODE![/color]

[color=Red]NEVER ROLL YOUR OWN RSA ROUTINES![/color]

er kann zwar die cpan module nutzen; dann bekommt er aber probleme mit windows, weil sich z.B. die RSA sachen von dort nicht auf windows bauen lassen!

Deine Anmerkung stimmt bei RSA aber nicht.

Ich hab das, wofür ich diesen Algo gebraucht hätte, inzwischen anders gelöst, aber die Lösung dieses Problems finde ich trotzdem noch interessant.

Wenn g nur zum Lesen gedacht ist, kann man wie folgt vorgehen:
1) Zunächst wähle man eine (fast) beliebige Funktion p, die jeder natürlichen Zahl eine Position in einem Datenpuffer fester Größe zuordnet.
2) Nun fülle man den Datenpuffer mit Zuffalsbits
3) Man prüfe, ob für alle bekannten Paare (m,n) in f jeweils an der Position p(m) im Datenpuffer n steht (ein p und eine Zufallsfolge, die dieser Bedingung genügen, existieren für hinreichende Puffergrößen immer, edit: es sei denn, man hat p so blöd gewählt, dass sich Überlappungen in den Daten ergeben, die wegen der Originaldaten in f nicht möglich sind)
4) falls Schritt 3 nicht erfolgreich war, kehre zu Schritt 2 zurück
5) Die gesuchte Funktion g ist diejenige, welche ihrem Parameter mittels p eine Position im Datenpuffer zuordnet und den dort liegenden Wert zurückliefert.

Diese Methode ist bei geschickt gewählter Puffergröße sicherlich sehr ätzend für den Angreifer, da sich alle echten und falschen Werte im Datenpuffer beliebig überlappen dürfen! Außerdem braucht man eventuell nicht ganz so viel Speicher, wie wenn man die Datenbank f mit Dummy-Werten auffüllt. Allerdings ist die Generierung von g nach dem oben angegebenen Algorithmus natürlich maximal ineffizient, zumal man hier tunlichst echte Zufallsbits verwenden sollte, da man bei Pseudozufallszahlen hier schnell Opfer einer Seed-Rate-Attacke werden könnte. Ferner sollte man die "echten" Werte noch überschlüsseln, und zwar mit einem Verfahren, dass möglichst gut die Bithäufigkeitsverteilung der Zufallsquelle in seiner Ausgabe reproduziert, damit statistische Angriffe schwieriger werden (edit: bzw. damit man überhaupt eine vernünftige Chance hat, in endlicher Zeit eine passende Zufallsfolge zu finden).

Generell muss man aber sagen, dass die Sicherheit eines Algorithmus, der Ishkas Problem löst, auf jeden Fall abnimmt, wenn die resultierende Datenbank g viel weniger Daten enthält als ein mit Dummy-Werten aufgefülltes f. Da f aber nicht komplett mit Dummy-Werten aufgefüllt werden kann (dann bräuchte man abzählbar unendlich viele), wage ich zu vermuten, dass es keine mit endlichem Aufwand durchführbare sichere Lösung des Problemes geben kann.\n\n

<!--EDIT|murphy|1091724168-->

danke, ich denke das ist ne gute Idee :)
klar - definitv sicher geht es nie ;)

Allerdings denke ich, daß man bei der Funktion p vergleichsweise geschickt vorgehen muß, um kein exponentielles Wachstum (gegen die Anzahl der Eingangswerte) seiner Datenbank zu erzwingen.

Ja, p sollte am besten geschickt gewählt werden!
Müsste ich sowas programmieren, würde ich vermutlich so vorgehen:
1) Daten der Datenbank komprimieren und verschlüsseln
2) Die verschlüsselten Daten mit einem modifizierten LZW-Algorithmus nach überlappungen durchsuchen.
3) Mir eine gute Größe für den Datenpuffer ausdenken -- vermutlich ungefähr doppelt so groß wie die verschlüsselten Daten (! Genauere Analyse täte hier Not)
4) Die verschlüsselten Daten werder mit maximaler noch mit minimaler Überlappung, sondern in schöner Gleichverteilung in den Puffer quetschen
5) Den Rest des Puffers mit Zufallsbits ausfüllen
6) p als interpolierendes Polynom bestimmen (! Auch hier täte genauere Analyse Not. Gut wäre es vielleicht, eine "schlechtere" Approximation als ein interpolierendes Polynom zu bestimmen, bei der die Ableitung überall höllisch groß ist, damit p dem Angreifer möglichst wenig Informationen gibt)

Allerdings muss ich zugeben, dass ich nicht genügen Ahnung von Mathe habe, um mir so etwas in "Produktionsqualität" zuzutrauen...

btw: RSA ist ja auch nur ein Algorithmus, der den Verschlüsselungsalgorithmus umschliesst\n\n

<!--EDIT|esskar|1091729683-->

[quote=Ishka,05.08.2004, 17:48]Deine Anmerkung stimmt bei RSA aber nicht.[/quote]
hmmm

dieser Text wurd 2 mal verschlüsselt (S/MIME conform)







ist nicht wirklich gleich! :P
nur die ersten bytes; dass ist aber das zertifikat, das benutzt wurde!\n\n

<!--EDIT|esskar|1091728653-->

Dann ist das kein reines RSA. Schon durch das padden mit einigen Zufallsbits kriegt man natürlich was völlig anderes, was hier wohl gemacht wurde.

Aber selbst mit dieser Erweiterung ist RSA nicht sinnvoll, weil man dann selbst im Falle eines existierenden f(i) bei g(i) keine Antwort erhielte - es sei denn wiederum, man hat den Schlüssel zum entschlüsseln, dann hilft das aber auch nicht sonderlich weiter.