Das Wort Zufall drückt aus, daß es aktuell keine kausale Erklärung für das Auftreten oder Zusammentreffen von Ereignissen gibt.
Meister Eckhart, (1260 - 1327): Alle Zufälle stiften ein "Warum".
Zu dem Mangel an kausalen Erklärungen sagt Baruch de Spinoza (1632 - 1677): Was wir Zufall nennen, ist der Zufluchtsort der Unwissenheit. Zufälle können auch bei sorgfältigen Planungen auftreten. Friedrich Dürrenmatt sagt es so: Je planmäßiger die Menschen vorgehen, desto wirksamer vermag sie der Zufall treffen.
Deterministische Zufallszahlengeneratoren erzeugen Pseudozufallszahlen. Pseudozufallszahlen können z.B. mit lineare rückgekoppelte Schieberegistern erzeugt werden. Siehe z.B. en.wikipedia List of random number generators , code.google crypto-js random number generators Linear-feedback-shift-register . Besonders strenge Anforderungen werden an kryptographisch sichere Zufallszahlengeneratoren gestellt. Pseudozufallszahlengenerator mit Mersenne-Twister
Ein idealer Zufallszahlen-Generator erzeugt Zufallszahlen ( truly random numbers ) mit den folgenden Eigenschaften:
Es gibt unterschiedliche Methoden, um quasi Zufallszahlen zu erzeugen. Welche Zufallszahlengeneratoren gibt es? Liste von Zufallszahlengeneratoren , List of random number generators . Ein One-Time-Pad wird i.a. lediglich einmal verwendet.
Einige unsortierte Weblinks zu Multiply-with-carry, Zufallszahlengeneratoren: Xorshift , Multiply-with-carry , Random number generation , Linear rückgekkoppeltes Schieberegister , Linear congruential generator ,
Zu ECMAScript gehört eine Methode var x = Math.random(), die einen (Nachkomma-) pseudo Zufallswert 0.0 <= x < 1.0 liefert und eine genäherte Gleichverteilung (uniform distribution) hat. Der Generator wird mit Hilfe der aktuellen zeit initialisiert (random number generator is seeded from the current time). ECMAScript legt kein verbindliches Erzeugungsverfahren fest.
Wie erfolgt die Erzeugung von Zufallszahlen bei ECMAScript?
Zu ECMAScript gehört die Methode random(), die an das Math-Objekt gebunden ist: var x = Math.random(). ECMAScript legt für die Erzeugung von Zufallszahlen kein verbindliches Verfahren fest. Die Methode random() kann mit
Number.prototype.random = function() {
return Math.random(this);
};
an das Number-Objekt gebunden werden.
Wie können (näherungsweise gleichverteilte) Zufallszahlen erstellt werden, die in ein bestimmtes Intervall fallen? Grob etwa:
function random_bereich(min,max) {
return min + (max-min) * Math.random();
}
Dies kann für eine ECMAScript-Bibliothek "zuf" verwendet werden. Beispiele:
var zuf = (function (rnd) {
function gfloat(min, max) { return min + (max - min) * rnd(); }
function gint ( min, max ) { return Math.floor( min + (max - min) * rnd() ); }
function gchar ( min, max ) { return String.fromCharCode( gint(min, max) ); }
function gint_arr( o ) { // o = { anz:50, min:100, max:200, max_eq:0/1 }
var i, r = []; if(o.max_eq){o.max += 1;}
for( i = 0; i < o.anz; i += 1 ) {
r.push(gint(o.min,o.max ));
} return r;
}
function gchar_arr( o ) { // o = { anz:50, min:'A', max:'Z', max_eq:0/1 }
var i, r=[];
if(typeof o.min==='string'){o.min=o.min.charCodeAt(0);}
if(typeof o.max==='string'){o.max=o.max.charCodeAt(0);}
if(o.max_eq){o.max += 1;}
for( i = 0; i < o.anz; i += 1 ) {
r.push(String.fromCharCode(Math.floor( o.min + (o.max - o.min) * rnd() ) ));
} return r;
}
function gstring( o ) {
var i, j,k, w, esum = 0, gsum = 0, h = [],
max_eq = 1, len = o.min.length; if(!o.em){ o.e = [];}
for( i = 0; i < len; i += 1 ) {
if(typeof o.min[i]==='string'){o.min[i]=(o.min[i].charCodeAt(0));}
if(typeof o.max[i]==='string'){o.max[i]=(o.max[i].charCodeAt(0));}
if(max_eq){o.max[i] += 1;}
w = o.max[i] - o.min[i]; h.push(w); gsum += w;
}
for( i = 0; i < len; i += 1 ) { esum += h[i]/gsum; o.e[i] = esum;}
h = [ ];
for (j = 0; j < o.anz; j += 1) { w = rnd();
for (i = 0; i < len; i += 1) {if (w < o.e[i]) { k = i; break; } }
h.push(String.fromCharCode(
Math.floor(o.min[k]+(o.max[k]-o.min[k])*rnd())
));
} return h.join("");
}
return { gfloat:gfloat, gint:gint, gchar:gchar,
gint_arr:gint_arr, gchar_arr:gchar_arr, gstring:gstring};
}( Math.random ));
Wie kann ein Zufallsstring aus Base32-Zeichen nach Crockford erzeugt werden? ECMAScript verwendet zur base32-Erzeugung mit .toString(32) das erweiterte Hex Alphabet mit den Zeichen 0-9a-v Crockford schlägt (bessere Lesbarkeit) den Zeichentausch key = { 'i': 'w', 'l': 'x', 'o': 'y', 'u': 'z'} vor. Hier eine Funktion, die n Zufallszahlen generiert und in einen base32-Crockford-Zufalls-String umwandelt. Bei unterschiedichen Browsern liegt eine unterschiedliche Math.random()-Implementierung vor, d.h. erstellte Zufalls-Strings sind Browser abhängig.
function random_base32_str(n) {
var i, x, str = '', key = { 'i': 'w', 'l': 'x', 'o': 'y', 'u': 'z'},
for(i = 0; i < n; i += 1) {
x = Math.floor( Math.random() * 1e9 );
str += x.toString(32).replace(/[ilou]/, function (c) { return key[c]; });
} return str;
}
Wie können ganze Zufallszahlen mit quasi Normalverteilung erstellt werden? Gauß-verteilte, ganze Zufallszahlen liefert (näherungsweise) etwa:
function random_uniform(mean, stdev) {
return Math.round(mean + stdev * my_rnd() );
}
Wie werden einmalige Identitäten erzeugt? Bei PHP gibt es z.B. die Funktion uniqid(), die eine eindeutige ID erzeugt. uniqid() basiert auf der aktuellen Zeit in Mikrosekunden. Aufruf etwa
$pre = chr(rand(97,121));
$uniqid = $pre. uniqid();
$timestamp = substr( uniqid(), 0, -5);
echo $uniqid.' '.date('r', hexdec($timestamp));
In ECMAScript können die folgenden Funktionen verwendet werden.
var z = pre + (Math.random() + '').replace('0.', '');
var t = (new Date().getTime()).toString(16);
HTML-Farben werden mit #rrggb dargestellt, wobei r, g, b hex-Ziffern bedeuten. Mit den folgenden Funktionen können Strings für HTML-Zufallsfarben erzeugt werden.
function random_color() {
return '#'+('00000'+(Math.random()*(1<<25)).toString(16)).slice(-6);
//return '#' + ('00000' + (Math.random() * 16777216 << 0).toString(16)).slice(-6);
}
function random_color_mit_6hex() {
var i, c = '#', hex = '0123456789ABCDEF'.split('');
for (i = 0; i < 6 ; i+=1) { c += hex[Math.floor(Math.random() * 16)];}
return c;
}
function random_color_rgb() {
var r = ('0' + Math.floor(Math.random() * 256).toString(16)).slice(-2),
g = ('0' + Math.floor(Math.random() * 256).toString(16)).slice(-2),
b = ('0' + Math.floor(Math.random() * 256).toString(16)).slice(-2);
return '#' + r + g + b;
}
Pseudozufallszahlen können mit Kongruenzgeneratoren deterministisch erzeugt werden. Kongruenzgeneratoren sind (alt-) bekannt ( rekursiv, arithmetisch ). Siehe z.B. de.wikipedia Zufallszahl , Kongruenzgenerator , Blum-Blum-Shub-Generator en.wikipedia Multiply-with-Carry , Random-Number-Generation , Linear Congruential Generator
Lineare Kongruenzgeneratoren ( Linear congruential generator )
y[i] = ( a * y[i-1] + b ) mod m
erreichen nach dem Satz von Knuth genau ihre maximal mögliche Periodenlänge m, wenn b zu m teilerfremd ist, jeder Primfaktor von m teilt a-1, und falls m durch 4 teilbar ist, auch a-1 durch 4 teilbar ist. In diesem Fall erzeugt der Generator jede Zahl von 0 bis m-1 genau einmal und beginnt dann wieder von vorn.
Bei einem Der multiplikative Kongruenzgenerator ist b=0. Ist z.B. m > 3 eine Primzahl, dann ergibt sich die maximal mögliche Periodenlänge (m-1), wenn für alle Primfaktoren q von m-1 gilt: a^((m-1)/q) mod m != 1 und der Startwert y[0] != 0 ist.
Hier ist ein experimenteller Kongruenzgenerator y[i] = ( a * y[i-1] + b ) mod m
var kongruenz_simple = (function () {
var i, m = 256, a = 1, b = 7, y = 0; //
function zahl() { // y[i] = ( a * y[i-1] + b ) mod m
y = ( a * y + b ) % m; return y;
}
function init(y0, m0, a0, b0) {
m = m0 || 256;
a = a0 || 1;
b = b0 || 7;
m = m0;
y = y0 % m;
}
return { init: init, zahl: zahl };
} ());
Die C-Funktion get_random() liefert eine quasi 32-bit-Zufallszahl.
m_w = choose-initializer; /* must not be zero */
m_z = choose-initializer; /* must not be zero */
uint get_random() {
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w; /* 32-bit result */
}
George Marsaglia (1924-2011) beschäftigte sich mit Zufallszahlen und Kryptologie und entwickelte die Polar-Methode zur Erzeugung normalverteilter Zufallszahlen. Weite Verbreitung hat seine "easy to remember" multiplier 69069 erlangt, die für x = 69069 * x + 1 >>> 0 eine Periode von 2^32 aufweist. Siehe de.wikipedia Xorshift , KISS (Zufallszahlengenerator).
Beispiel:zufall.init() und zufall.next()
z.B. zufall.init({ seed: 4711 }) oder z.B.
zufall.init({ mod: 'bereich', von: 32, bis: 256, seed: 4711 }) setzt private Variablen.
Die Zufallszahlen x1,x2,x3 werden erhalten, etwa mit
x1 = zufall.next();
x2 = zufall.next();
x3 = zufall.next();
var zufall = (function () {
var r, mod = 0, von = 0, bis, seed = 12345679, x = seed;
return {
init: function (o) { if (!o['seed']) { seed = 12345679; }
if (o['mod']) { von = o.von; bis = o.bis; mod = o.mod; }
},
next: function () {
x = (69069 * x + seed) >>> 0; r = x;
if (mod) { r = von + r % (bis - von); } return r;
}
};
} ());
Nun ein weiteres Beispiel zum Versclüsseln mit 69069 ( Periode 2^32 ). Das Paßwort ( UTF-8 ) generiert einen "verborgenen" Startwertwert des 69069-Generators. Die Verschlüsselung erfolgt durch das zeichweise xor des Textes ( UTF-8 ) mit der Passwortfolge.
var crypt_utf8_base64 = (function () { var seed_pw = 362436069, seed_str = 123456789;
function set_seeds(str_seed, pw_seed) {seed_str = str_seed; seed_pw = pw_seed; }
function crypt_bytes(str_bytes, key_bytes) {
var str_len = str_bytes.length, key_len = key_bytes.length, str_char, key_char, i, xx, r = '';
seed_pw = seed_pw || 362436069; seed_str = seed_str || 123456789;
xx = seed_pw;
for (i = key_len - 1; i >= 0; i -= 1) {
xx = (69069 * (xx + key_bytes.charCodeAt(i)) + seed_pw) >>> 0;
}
for (i = 0; i < str_len; i += 1) {
xx = (69069 * xx + seed_str) >>> 0; key_char = xx % 256;
str_char = str_bytes.charCodeAt(i);
if (key_char && key_char !== str_char) { str_char ^= key_char; }
r += String.fromCharCode(str_char);
} return r;
}
function encrypt(str_utf8, key_utf8) {
var str_bytes, key_bytes, str_base64;
try {
str_bytes = window.unescape(window.encodeURIComponent(str_utf8));
} catch (e1) { str_bytes = 'ERR1: ' + e1; }
try {
key_bytes = window.unescape(window.encodeURIComponent(key_utf8));
} catch (e2) { key_bytes = 'ERR2: ' + e2; }
str_bytes = crypt_bytes(str_bytes, key_bytes);
try { str_base64 = btoa(str_bytes); } catch (e3) { key_bytes = 'ERR3: ' + e3; }
return str_base64;
}
function decrypt(str_base64, key_utf8) { var str_bytes, key_bytes, str_utf8;
try { key_bytes = window.unescape(window.encodeURIComponent(key_utf8));
str_bytes = atob(str_base64);
} catch (e4) { key_bytes = 'ERR4: ' + e4; }
str_bytes = crypt_bytes(str_bytes, key_bytes);
try {
str_utf8 = window.decodeURIComponent(window.escape(str_bytes));
} catch (e5) { str_utf8 = 'ERR5: ' + e5; }
return str_utf8;
}
return { set_seeds: set_seeds, crypt_bytes: crypt_bytes,
encrypt>:encrypt, decrypt: decrypt };
} ());
Teste:
Array mit Zufalls-Generatoren:
<script>
var zuf = (function () {
var idx = 0, x, G = []; // G = Array für Zufalls-Generatoren
function zahl(idx) {
if (parseInt(idx, 10) === 'NaN') { idx = 0; }
G[idx] = 69069 * G[idx] + 1234567 >>> 0;
return G[idx];
}
function init(idx, x_start, n_runden) {
var i;
n_runden = n_runden || 3;
if (!idx) { idx = 0; } x = parseInt(x_start, 10);
if (isNaN(x)) { G[idx] = (new Date()).getTime() >>> 0;
} else { G[idx] = x; }
for (i = 0; i < n_runden; i += 1) { zahl(idx); }
}
return { /* infos:G, */init: init, zahl: zahl };
} ());
</script>
Teste:
Zunächst ein einfaches, übersichtliches Verfahren, das den Faktor 69069 verwendet:
function pseudo_hash_str(s, max) {
var i, d, c = 0, len = s.length-1, a = s.charCodeAt(len-1), r="";
s = "äöüß" + s; max = max||36;
for ( i = len; i >= 0; i -= 1 ) {
c += s.charCodeAt(i);
d = 69069 * c + a >>> 0;
r += d.toString(36); if(r.length > max){return r;}
} return r;
}
Der Aufruf alert([pseudo_hash_str("AA"), pseudo_hash_str("AAA"), pseudo_hash_str("AAAA"), pseudo_hash_str("AAAAA") ].join('\n') ); liefert die Ergebnisstrings ( Base 36 ).
s = "AA" liefert "a46dbjhpeb" s = "AAA" liefert "ad24tkh8gbturhb" s = "AAAA" liefert "964lwjj6owtnd0e130w1e" s = "AAAAA" liefert "2o85qbucptm7estwbl4b15p45b"
Aus einem Passwort, wie z.B. o.key='geheim' soll ein Hash-String mit
o.nchar = 80 Zeichen erstellt werden.
Jedes Hash-Code-Zeichen ist ein base36-Zeichen [0-9a-z], d.h. die Basis ist o.bas=36.
o.zuf = 101 ist eine Start-Seed-Zahl zum Generieren von Zufallszahlen ( mit Hilfe von 69069 ).
Mit
var o = {key:'geheim', zuf:0, nchar:80, bas:32}
gibt dann der Aufruf zuf_hash(o) in o.hash den erstellten Hash-String zurück.
function zuf_hash(o) { var sk = o.key, nk = sk.length,
zuf = o.zuf || 69069,
nc = o.nchar || 32,
bas = o.bas || 16,
next = function (zuf) { return 69069 * zuf >>> 0; },
cd = function (k) { return sk.charCodeAt(k); }, // interne func
i, j, k = 0xfffff, arr = [], nr, r = '';
if (nk < 1) { return { hash: '', zuf: zuf, nchar: nc }; }
for (i = 0; i < nk; i += 1) { k += cd(i); }
zuf = next(zuf + k); i = 0; r = '';
while (i < nc) {
j = zuf % nk; i += 1;
zuf = next(zuf); zuf = next(zuf + cd(j));
r += zuf.toString(bas); nr = r.length;
if (nr > nc) { return { hash: r.slice(nr - nc), zuf: zuf, nchar: nc }; }
} return { };
}
Hier ein Test:
Einige grobe Tests sind im Quelltext. Teste Periodenlänge des Zufallsgeneratores ( Braucht STUNDEN! )