3. Schnelles erzeugen vieler Zufallswerte

Schnelles erzeugen vieler Zufallswerte


  • cooky451 schrieb:

    hustbaer schrieb:

    und wie gut ist so ein "AES-Counter-Generator".

    Perfekt. Bessere Pseudo-Zufallszahlen wirst du nicht bekommen. Das ist ja der Sinn der Sache, dass man verschluesselte Daten nicht von random Noise unterscheiden kann.

    Öhm.
    Der Sinn dahinter ist es schon. Heisst aber nicht dass es deswegen so ist. Der Sinn von MD5 ist auch dass man keine krummen Sachen machen kann, trotzdem gibt es Attacken die mit durchaus realistischem Rechenaufwand auskommen.

    Ich würde das also nicht einfach als gegeben annehmen, so lange nicht jmd. ne Test-Suite ala DIEHARD drauf losgelassen hat. Ist das bereits geschehen? Vermutlich ja, aber ich weiss es einfach nicht, daher meine Frage. Und wenn ja, kann man sich die Ergebnisse davon irgendwo ansehen?

    0
  • P

    Der Counter-Modus generiert so seine Pseudo-Zufallszahlenfolge. Die Sicherheit von AES-CTR ist somit abhängig von der Qualität dieser Zufallszahlen. Da AES-GCM auf den CTR-Mode aufbaut und AES-GCM in TLS 1.2 enthalten ist und sogar empfohlen wird, denke ich doch, dass das recht sicher ist.

    MD5 dagegen ist schon lange gebrochen und wird heute eigentlich nicht mehr verwendet. Aktuelle Browser sehen MD5-Zertifikate sogar automatisch als ungültig an. Nur noch als HMAC ist MD5 zu gebrauchen.

    Edit: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf CTR_DRGB (S. 49, 57 im PDF) ist ein Zufallsgenerator, der auf einem Blockcipher im Counter-Mode aufbaut.

    0

  • @patrick246
    Die Theorie dahinter ist mir schon klar.
    Ich würde es trotzdem in der Praxis ausprobieren wollen.

    Speziell bei so Sachen wie der Frage in wie vielen Dimensionen die Zahlen gleichverteilt sind würde ich so einem Generator nicht einfach blind vertrauen. Wenn ich also ne Anwendung habe wo das wichtig wäre, dann würde ich wohl bei 'nem Twister bleiben.

    @cooky451
    Und nochmal was die 3,3 GB/s angeht...
    Hab jetzt keinen Vergleich mit MT, aber so richtig viel kommt mir das nicht vor. Gerade mal ein Byte/Cycle. Würde mich zumindest wundern wenn ein MT das unter gleichen Voraussetzungen (gleiche CPU, Thread-Anzahl etc.) nicht überbieten könnte. Bzw. XORSHIFT's Variante.

    0
  • C

    hustbaer schrieb:

    Speziell bei so Sachen wie der Frage in wie vielen Dimensionen die Zahlen gleichverteilt sind würde ich so einem Generator nicht einfach blind vertrauen.

    Ich bin mir relativ sicher dass die Zahlen so ziemlich jeden statistischen Test den es gibt erfuellen muessen damit AES nicht als broken gilt.

    hustbaer schrieb:

    Und nochmal was die 3,3 GB/s angeht...

    Ich hab das mal getestet:

    #include "utility/stopwatch.hpp"

#include <cstring>
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <random>

template <typename RNG>
RNG make_rng()
{
	std::random_device rd;
	std::array<typename RNG::result_type, RNG::state_size> seed_data;
	std::generate(seed_data.begin(), seed_data.end(), std::ref(rd));
	std::seed_seq seq(seed_data.begin(), seed_data.end());
	return RNG(seq);
}

template <typename RNG>
void test_rng(RNG& rng, void* buffer, std::size_t size)
{
	while (size >= sizeof(decltype(rng())))
	{
		auto r = rng();
		std::memcpy(buffer, &r, sizeof r);
		buffer = static_cast<char*>(buffer) + sizeof r;
		size -= sizeof r;
	}
}

int main()
{
	const std::size_t mb = 512;
	std::vector<char> buf(mb * 1024 * 1024);
	default_stopwatch sw;
	double t;
	auto rng1 = make_rng<std::mt19937>();
	auto rng2 = make_rng<std::mt19937_64>();
	auto rng3 = std::minstd_rand((std::random_device()()));

	sw.reset();
	test_rng(rng1, buf.data(), buf.size());
	t = float_cast<double>(sw.elapsed());
	std::cout << "mt19937: " << t << " - " << mb / t << " MB/s\n";

	sw.reset();
	test_rng(rng2, buf.data(), buf.size());
	t = float_cast<double>(sw.elapsed());
	std::cout << "mt19937_64: " << t << " - " << mb / t << " MB/s\n";

	sw.reset();
	test_rng(rng3, buf.data(), buf.size());
	t = float_cast<double>(sw.elapsed());
	std::cout << "minstd_rand: " << t << " - " << mb / t << " MB/s\n";
}

    ideone: http://ideone.com/ui7upc

    Ergebnis bei mir (x64, 3570k, VS2015 Preview)

    mt19937: 0.432911 - 1182.69 MB/s
mt19937_64: 0.218933 - 2338.62 MB/s
minstd_rand: 0.48124 - 1063.92 MB/s

    Ist wohl stark implementierungsabhaengig. Bei mir waere zumindest mt19937_64 ueber 4 threads deutlich schneller als AES. Aber wie schon vorher erwaehnt, jede dieser Varianten sollte vermutlich locker fuer den TE reichen.

    0
  • Mod 

    sizeof(decltype(rng()))

    😃

    0
  • Mod

    cooky451 schrieb:

    Aber wie schon vorher erwaehnt, jede dieser Varianten sollte vermutlich locker fuer den TE reichen.

    Bin ich der einzige, der noch immer auf eine Antwort auf die allererste Gegenfrage wartet?

    DarkShadow44 schrieb:

    Wie kommst du darauf dass das erzeugen der Zufallswerte das Problem ist ? Bei mir geht das in unter einer Sekunde.

    Ich gehe davon aus, dass der Threadersteller gar kein Problem mit Zufallszahlen hat, bis nicht das Gegenteil bewiesen wurde.

    0
  • ?

    Mein Testprogramm (teil einer groesseren Suite und die RNG sind stdlib kompatibel aber firmenintern, der XOR Shift AVX Code ist im Kern aber der gepostete):

    core i7 4670k 3.5GHz, single threaded:
    XOR_SHIFT AVX Generation performance for 5.36871e+008 random numbers of 4 byte sized uints is 2.03028e-010s/number <=> 4.92542e+009numbers/s. Total time used = 109ms

    Also:512MB 32bit in 109ms, bei den 8 bit von cooky also <27ms.

    Wobei ich den Ansatz immer noch nicht fuer richtig halte. Da es nur um 8 bit Zufallszahlen geht reicht die 2^31-1 sequenz von XOR-Shift locker aus. Mmn sollte es aber auch eine wesentlich kuerzere Sequenz und damit ein kuerzerer Vektor schon tun (das muss der TO aber mal sagen, sofern er noch mitliest).

    0
Anmelden zum Antworten