kryptografischer, eindeutiger Zufallszahlengenerator ;)

scrontch

Suche einen Zufallszahlengenerator, der folgende Bedingungen erfüllt:
- Jede ausgespuckte Zahl kommt nur einmal vor (modulo des Wertebereichs natürlich, z.B. 2^32).
- aus erhaltener Folge ist es praktisch unmöglich/sehr aufwendig rauszubekommen welches die nächste Zahl sein wird.
(idealerweise darf der Algorithmus dabei sogar bekannt sein, nur ein vergleichsweise kleiner Teil von Information ("Schlüssel") soll geheim sein)
- Der zu speichernde Zustand des Algorithmus soll möglichst gering ausfallen.
- Natürlich soll die Verteilung der erhaltenen Zahlen möglichst gleichmässig über den Wertebereich sein. (Ist aber nicht von zentraler Wichtigkeit)

hat jemand Ideen zur Realisierung?

- Jede ausgespuckte Zahl kommt nur einmal vor (modulo des Wertebereichs natürlich, z.B. 2^32).

soll das heissen, dass z.B. bei 2^32 möglichen Zahlen erst alle diese 2^32 ausgespuckt werden sollen, bevor eine Zahl erneut drankommt?

Christoph

scrontch schrieb:

Suche einen Zufallszahlengenerator, der folgende Bedingungen erfüllt:
- Jede ausgespuckte Zahl kommt nur einmal vor (modulo des Wertebereichs natürlich, z.B. 2^32).

Das ist dann aber kein Zufallszahlengenerator.
Bei "echten" Zufallszahlen darf jede Zahl beliebig oft direkt hintereinander auftreten. Größere Sequenzen sind natürlich nicht sehr wahrscheinlich.

edit: 26 Sekunden zu langsam.

scrontch

Jo, das solls heissen.
Meinetwegen kann man den Zyklus auf << 2^32 begrenzen, ändert ja aber nix im Prinzip.
Und, nein, Zufallszahlen sind das dann nicht mehr richtig, der Begriff war falsch gewählt.
Ich meine damit, das die nächste Zahl nicht (oder nur mit immensem Aufwand) aus den bereits gezogenen errrechnet werden können soll, wenn man eine vergleichsweise kleine geheime Information nicht besitzt.

Jester

Hm, also angenommen ich hab so einen Generator. Dann würde ich den erstmal so lange laufen lassen, bis ne Zahl kommt, die ich schonmal hatte. Damit hab ich ne Liste aller Zahlen, die er liefern kann. Wenn jetzt eine Zahl rauskommt, dann weiß ich genau wo in der Liste der Generator gerade steht, denn jede Zahl kommt nur einmal vor. Damit kann ich in der Liste nachschaun, was als nächstes kommt. So ein Teil ist also prinzipiell nicht sicher.

MfG Jester

scrontch

Genau deshalb müsste der Generator mit einem geheimen Schlüssel initialisiert werden.
(der Schlüssel fliesst also in irgendeiner Form in den seed value ein)
Die Bedingung ist lediglich, dass ich *ohne* den Schlüssel die Folge nicht vorhersagen kann.

CMatt

hmm.. so auf anhieb würde ichs so machen (pseudocode):

Array vecZeichen;
// fülle das ding mit allen ziechen die verwenden werden dürfen
Array  vecResult;
for(int i=0;i<lenght;i++)
{
    RAND_MAX = vecZeichen.size()-1;
    int iZeichen = rand();
    ZEICHEN c = vecZeichen[iZeichen].
    vecZeichen.Remove(iZeichen);
    vecResult.add(c);
}

wenn vecZeichen.size() null wird musst ihn natürlich wieder nachfüllen.

RainerSp

Suche mal bei Wikipedia nach BBS (Blum Blum Shub). Das ist ein einfacher Zufallszahlengenerator, der 0 und 1 Bitfolgen produziert. Die Periodizität liegt auch bei etwa 2^32. Halt je nach Zahlenbereich.

mwoidt

Weiß ja nicht wie viele Zahlen du brauchst aber wenn es nur wenige sind, dann mach es über Mausbewegung oder miss die Zeiten zwischen zwei Tastaturanschlägen. Dass is auf jeden Fall zufälliger als irgendein Zufallszahlengenerator

Jester

@mwoidt:

Lies Dir mal durch, was er haben will.

scrontch

CMatt:
Bei der Methode muss ich tatsächlich alle Zeichen des Wertebereichs vorrätig haben.
Das sind mir zuviel.
Am besten wäre es, wenn nur der letzte ausgespuckte Wert (und evtl der Schlüssel) gespeichert werden müsste, um daraus den nächsten zu berechnen.

mwoidt:
jo, les nochmal von vorne.
Es geht nicht wirklich um Zufall sondern um Unvorhersagbarkeit+Eindeutigkeit.

RainerSp:
nach erstem überfliegen bringt BBS die nötige Unvorhersagbarkeit.
Aber wie garantier ich die Eindeutigkeit? bzw. wo liest du die Periodizität da raus?

SirLant

Wenn ich die Zahl 2^23-1 habe, weiß ich aber genau, dass die nächste 2^32 sein wird
und kann ich unter dieser annahme nicht den geheimen Schlüssel herausbekommen?

fubar

SirLant schrieb:

Wenn ich die Zahl 2^23-1 habe, weiß ich aber genau, dass die nächste 2^32 sein wird
und kann ich unter dieser annahme nicht den geheimen Schlüssel herausbekommen?

Ich behaupte mal: NEIN!
Schließlich gibt es noch (2^23-2)!≈('ne ganze Menge) verschiedene Möglichkeiten, die 2^23-2 verbleibenden Werte zu kombinieren...

RainerSp

scrontch schrieb:

CMatt:
RainerSp:
nach erstem überfliegen bringt BBS die nötige Unvorhersagbarkeit.
Aber wie garantier ich die Eindeutigkeit? bzw. wo liest du die Periodizität da raus?

Ich habe leider die Quelle nicht mehr gefunden. Zur Not mußt du selber mal nachrehcnen Eben habe ich aber noch gelesen, daß die notwendige Sicherheit erst mit einem sehr großen Produkt zweier Primzahlen kommt. Aber für Security by Obscurity reicht es auf jeden Fall.

Gruß,Rainer.