Cross-Plattform tauglicher GUID Generator

[Spawn84]

Dravere schrieb:

Nein, man kann dazu das Rauschen vom PC nehmen. Schau dir mal /dev/random bei Linux an:
http://en.wikipedia.org/wiki//dev/random

Wenn man alle Variablen kennt wodurch das rauschen erzeugt wird kann man die Zufallszahlen nachrechnen. Somit eine zwar sehr gute Zufallszahl aber keine echte weil berechenbar.

Das einzige was mir jetzt einfällt und wo man nur annimmt das es zufällig ist, währe der zerfall von radioaktiven Materialien (eventuell fehlt aber derzeit auch nur das Wissen dafür).

Dravere schrieb:

Wieso Google?

Das ist einfach.

2^128 = 340282366920938463463374607431768211456
340282366920938463463374607431768211456 * 128 = 43556142965880123323311949751266331066368 Bit

43556142965880123323311949751266331066368 / 8 = 5444517870735015415413993718908291383296 Byte

5444517870735015415413993718908291383296 / 1024 = 5316911983139663491615228241121378304 kB

5316911983139663491615228241121378304 / 1024 = 5192296858534827628530496329220096 MB

5192296858534827628530496329220096 / 1024 = 5070602400912917605986812821504 GB

5070602400912917605986812821504 / 1024 = 4951760157141521099596496896 TB
...

Darum Google
Und ja meine Aussage bezüglich Standard war nicht ernst gemeint (ich find nur die Ironie tags nicht ^^)

MfG Spawn84

[hustbaer]

Spawn84 schrieb:

Dravere schrieb:

Nein, man kann dazu das Rauschen vom PC nehmen. Schau dir mal /dev/random bei Linux an:
http://en.wikipedia.org/wiki//dev/random

Wenn man alle Variablen kennt wodurch das rauschen erzeugt wird kann man die Zufallszahlen nachrechnen. Somit eine zwar sehr gute Zufallszahl aber keine echte weil berechenbar.

Das einzige was mir jetzt einfällt und wo man nur annimmt das es zufällig ist, währe der zerfall von radioaktiven Materialien (eventuell fehlt aber derzeit auch nur das Wissen dafür).

Unfug.

[hustbaer]

Tachyon schrieb:

hustbaer schrieb:

Mit Boost.Random müsste sich was zusammenbasteln lassen.

Ja, UIDs lassen sich damit mehr oder weniger gut zusammenbasteln. Das Problem für mich ist eher das G im GUID.
(...)

???
Seede dir einen boost::mt19937 Generator über boost::random_device, dann kannst du dir GUIDs generieren soviel du willst.

[Keros]

hustbaer schrieb:

Unfug.

Begründung?

Ach ja und sorry wegen dem off topic gelabere hier ^^

[knivil]

Das einzige was mir jetzt einfällt und wo man nur annimmt das es zufällig ist, währe der zerfall von radioaktiven Materialien (eventuell fehlt aber derzeit auch nur das Wissen dafür).

In der c't gabs mal 'nen netten Artikel, wie das thermische Rauschen von Webcams genutzt wird, um Zufallszahlen zu generieren. Diese Einfluesse kannst weder messen noch nachbilden.

[Keros]

knivil schrieb:

In der c't gabs mal 'nen netten Artikel, wie das thermische Rauschen von Webcams genutzt wird, um Zufallszahlen zu generieren. Diese Einfluesse kannst weder messen noch nachbilden.

Kann ich mir ehrlich gesagt nicht vorstellen. Ich würde eher sagen es sind zu viele Einflussfaktoren als das man sie messen könnte (oder es fehlen derzeit noch die Mittel hierfür). Oder wurde auf eine besondere Komponente eingegangen die den absoluten Zufall erzeugt?
Ich bin mir fast sicher wenn man alle Umgebungsvariablen kennt (was in der Praxis derzeit nicht möglich ist) kann man auch das nachrechnen/simulieren.

Es geht hier um eine reine Theoriefrage die mit der Praxis fast nichts bis gar nix zu tun hat. Wenn wer nen Artikel oder sonst was hat wo dazu etwas steht (eventuell bewiesen ist das es sich hierbei um absolute Zufall handelt) nur her damit. Würde mich sehr interessieren

[theta]

Ich bin mir fast sicher wenn man alle Umgebungsvariablen kennt (was in der Praxis derzeit nicht möglich ist) kann man auch das nachrechnen/simulieren.

Das ist das alte Problem der Chaos Theorie...

[Dravere]

@Keros,
Nun fragt man sich aber mehr und mehr, was dein erster Beitrag eigentlich sollte. Der grösste Teil war ja gar nicht ernst gemeint und der mittlere Teil nicht umsetzbar. Sehr sinnvoller Beitrag...

Falls du etwas über Zufall lesen willst:
http://de.wikipedia.org/wiki/Zufall

Richtiger Zufall wird von der Newtonischen Mechanik (Physik) ausgeschlossen. Die Tendenz ist dort stark deterministisch:
http://de.wikipedia.org/wiki/Determinismus

In der Quantenphysik gibt es Theorien, dass es den Zufall tatsächlich gibt. Als Beispiel zu nennen, ist hier wohl die Kopenhagener Deutung:
http://de.wikipedia.org/wiki/Kopenhagener_Deutung

Damit solltest du bereits genügend Stoff haben, um Google oder eine andere Suchmaschine zu benutzen. Es gibt sicher genügend Artikel im Internet. Zudem findest du damit sicher auch Bücher.

Grüssli

[Keros]

Naja die Chaostheorie ist für mich haltbar da ich glaube das es den Zufall gibt (so viel Philosophie und das bei nem technischen Thema ).

Ich habe für mich eine Definition warum es den absoluten Zufall geben muss die mir reicht. Aber wie gesagt ist es im Computerbereich meiner Meinung nach sehr schwer bis gar nicht möglich echte Zufallszahlen zu erzeugen. Wobei das nicht nötig ist da Pseudozufallszahlen vollkommen ausreichen.

[Keros]

Ich leg mir jetzt nen Acc zu damit ich editieren kann ^^

Mein erster post:
1 -> War meine Meinung dazu (darf ich doch in nem Forum vertreten?)

2 -> MAC Adresse + Timestamp ist nicht umsetzbar?

3 -> Nen Spaß darf man sich doch mal erlauben (vor allem mit allwissenden google)

Die restlichen Beiträgen waren dann was sich aus der Diskussion ergeben hat -> Forum ist glaub ich auch so gedacht?

[Dravere]

Keros schrieb:

1 -> War meine Meinung dazu (darf ich doch in nem Forum vertreten?)

Doch, nur hat sie nichts mit dem Thema zu tun. Ich sagte damals, dass Pseudo Zufallszahlen verwendet werden, weil es in der Informatik eben auch andere Zufallszahlen gibt. Egal wie deine Meinung über Zufallszahlen aussieht:
- True Random Numbers
- Pseudo Random Numbers

http://en.wikipedia.org/wiki/Random_number_generation#.22True.22_random_numbers_vs._pseudorandom_numbers

Keros schrieb:

2 -> MAC Adresse + Timestamp ist nicht umsetzbar?

Habe ich dir schon zu deinem Ironie Standard gesagt. Eine GUID muss auch erstellt werden können, wenn keine Netzwerkkarte vorhanden ist. Wie du ohne Netzwerkkarte eine MAC Adresse holen willst, dass musst du mir mal zeigen...

Keros schrieb:

3 -> Nen Spaß darf man sich doch mal erlauben (vor allem mit allwissenden google)

Darf man, aber dann sollte es immerhin klar ersichtlich sein. Zum Beispiel hiermit:
Oder nimm [ironie] Tags.
Zudem sollte zumindest im restlichen Beitrag was sinnvolles stehen.

Keros schrieb:

Die restlichen Beiträgen waren dann was sich aus der Diskussion ergeben hat -> Forum ist glaub ich auch so gedacht?

Nur ist es Off-Topic.

(und ich bin aktuell schlecht gelaunt, weil ich das Problem hier nicht geregelt bekomme. Aber es ist nicht nett dem Tachyon gegenüber, dass wir seinen Thread so ins Off-Topic führen ;))

Grüssli

[Tachyon]

hustbaer schrieb:

[...]Seede dir einen boost::mt19937 Generator über boost::random_device, dann kannst du dir GUIDs generieren soviel du willst.

So, erstmal Danke für die ganzen Antworten.

Also das mit dem random_device werde ich mal testen. Das klingt erstmal recht vielversprechend.

Wegen vorangegangen Vorschlägen:
Einfach nur Pseudorandomnummern zu erzeugen, reicht leider nicht. Irgendwoher muss ein Seed kommen, und dafür benutzt man üblicherweise die Systemzeit. Auf dem System, auf dem die Anwendungen laufen soll, wird die Zeit auf allen Plattformen synchronisiert, wodurch eine recht hohe Wahrscheinlichkeit besteht, dass man gleiche Zufallssequenzen auf verschiedenen Clustern produziert. Das darf aber nicht passieren.

An die MAC-Addresse komme ich nicht plattformunabhängig ran (obwohl es überall eine gäbe, aber das System ist ziemlich heterogen und ich will möglichst wenig plattformspezifische Anteile in der Software haben).

Das Boost auch einen nicht-deterministischen Generator liefert, ist mir entgangen. Das könnte aber die Lösung sein.

Ansonsten werde ich wohl in den sauren Apfel beissen müssen, und die betriebssystemeigenen GUID-Funktionen wrappen. Das ist auf jeden Fall weniger aufwändig, als erst die MAC-Adresse oder ähnliches zu ermitteln, und dann daraus eine GUID zu erzeugen.

EDIT: Nein, boost::random_device unterstützt Windows leider nicht. Das Ding kompiliert nur unter BSD oder Linux, wegen

#if defined(__linux__) || defined (__FreeBSD__)

in random_device.cpp . Eine Windows-Variante gibts nicht.

[Keros]

Hat mit dem Thema schon was zu tun. Wenn das erzeugen von echten Zufallszahlen trivial währe (was ich behaupte das es nicht ist) hätte Tachyon das Problem nicht

Das eine GUID auch ohne Netzwerkkarte erzeugt werden muss ist klar aber das eine Vorhanden ist entnahm ich schon der Aussage das es mit den Timestamps ein Problem gibt -> läßt auf Synchonisierung schließen -> Netzwerkkarte sehr wahrscheinlich
Das die MAC auzulesen leider nicht Systemunabhängig ist hab ich mir fast gedacht, aber ne idee wars wert.

Das mit dem Clown werd ich mir merken für mich hatte xD bis jetzt ca die selbe Bedetung

Wenn mir wer "Unfug" vor den Kopf wirft ohne begründung muss ich nachfragen. Vielleicht weiß da wer was, dass ich noch nicht kenne.

[hustbaer]

Tachyon schrieb:

EDIT: Nein, boost::random_device unterstützt Windows leider nicht. Das Ding kompiliert nur unter BSD oder Linux, wegen

#if defined(__linux__) || defined (__FreeBSD__)

in random_device.cpp . Eine Windows-Variante gibts nicht.

Shit.
Obwohl es recht einfach zu implementieren wäre.
CryptGenRandom() is ja nu wirklich keine Hexerei.
Vielleicht sollte ich nen Patch einschicken...

[pumuckl]

Tachyon schrieb:

Wegen vorangegangen Vorschlägen:
Einfach nur Pseudorandomnummern zu erzeugen, reicht leider nicht. Irgendwoher muss ein Seed kommen, und dafür benutzt man üblicherweise die Systemzeit. Auf dem System, auf dem die Anwendungen laufen soll, wird die Zeit auf allen Plattformen synchronisiert, wodurch eine recht hohe Wahrscheinlichkeit besteht, dass man gleiche Zufallssequenzen auf verschiedenen Clustern produziert. Das darf aber nicht passieren.

Eine synchronisierte Systemzeit macht nur dann Probleme, wenn die Seeds alle zur gleichen Zeit genommen werden. Falls dem so ist hast du immernoch auf jedem Cluster irgendwo eine Kommunikationsschicht, die das Quatschen mit den anderen Rechnern übernimmt. Die Schicht ist eh schon Plattformabhängig, daher kannst du von ihr aus der Mac-Adresse oder IP-Adresse oder was auch immer eine plattformunabhängige Zahl generieren lassen, die von Cluster zu Cluster verschieden ist. Modifiziere die genommene Systemzeit in geeigneter Weise damit und du hast unterschiedliche Seeds, oder seh ich das falsch?

[Tachyon]

pumuckl schrieb:

...seh ich das falsch?

Ja, aus meiner Sicht ist das Netzwerk plattformunabhängig, weil ich boost.asio benutze. Darüber gibt es aber keine Möglichkeit, an die MAC-Adresse heranzukommen. An IPs schon eher, aber die sind im System nicht eindeutig.

[Tachyon]

Keros schrieb:

Hat mit dem Thema schon was zu tun. Wenn das erzeugen von echten Zufallszahlen trivial währe (was ich behaupte das es nicht ist) hätte Tachyon das Problem nicht.

Aus informationstechnischer Sicht echte Zufallszahlen zu erzeugen, ist eigentlich kein großes Problem mehr. Die meisten Betriebssysteme bieten Funktionen dafür an, sofern die unterliegende Plattform ausreichend Informationen liefert.
Das Problem ist, an diese Informationen heranzukommen. Außerdem kann sich die Repräsentation der Zufallszahlen sich von System zu System sehr stark unterscheiden.

[Dravere]

@Tachyon,
Kannst du nicht immer neue Seeds setzen, jedesmal wenn eine GUID erzeugt werden muss? Die GUID werden wohl kaum zur gleichen Zeit erzeugt. Zusätzlich könntest du std::clock aus <ctime> nehmen. Die Programmlaufzeit sollte sich wohl schon unterscheiden.
Oder erzeugst du die GUIDs gleich beim Start des Programmes? Dann würde die Systemzeit allerdings reichen, da du wohl kaum alle Programme zur gleichen Zeit starten kannst

Grüssli

[Tachyon]

Dravere schrieb:

@Tachyon,
Kannst du nicht immer neue Seeds setzen, jedesmal wenn eine GUID erzeugt werden muss? Die GUID werden wohl kaum zur gleichen Zeit erzeugt. Zusätzlich könntest du std::clock aus <ctime> nehmen. Die Programmlaufzeit sollte sich wohl schon unterscheiden.
Oder erzeugst du die GUIDs gleich beim Start des Programmes? Dann würde die Systemzeit allerdings reichen, da du wohl kaum alle Programme zur gleichen Zeit starten kannst

Grüssli

Leider ist das nicht so einfach. Es gibt etwa 40 synchronisierte Cluster, auf denen das Programm mehr oder weniger parallel gestartet wird. Außerdem kann es sein, dass das Programm auf einem Cluster mehrere Male gestartet wird.
In einer Monte-Carlo-Simulation habe ich herausbekommen, dass der clock + Zeitstempel auf einem Cluster sich immer mal wieder mit denen auf einem anderen Cluster überdeckt. Das ist also leider nicht ausreichend.
Ich bin jetzt dazu übergegangen, den Seed aus einem SHA1-Hash zu erzeugen, den ich mit diversen Dingen füttere, die mir auf den Systemen zur Verfügung stehen.
Drunter:

`

clock()

time()

/dev/urandom (falls vorhanden, ansonten den uninitialiserten Buffer in den ich normalerweise gelesen haette)

den Hostnamen

die Host IP (falls vorhanden)

`

Das scheint bis jetzt zu funktionieren. Ich muss das mal ein paar Tage laufen lassen.

[hustbaer]

Ich persönlich würde für Windows noch zusätzlich CryptGenRandom() statt /dev/urandom verwenden. Der Aufwand ist ja nicht gross (#ifdef WINDOWS + ein paar Zeilen Code).

Oder aber gleich wie du es schon angedacht hast die GUID Generatoren vom OS kapseln. Könnte man auch mixen, also das was du jetzt machst als Fallback verwenden falls du für das spezielle OS keinen GUID Generator kennst, und ansonsten eben die OS Funktionen verwenden.