www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Zufallszahl beim Start des AVR gewinnen


Autor: ChristophK (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich suche nach einer Möglichkeit, beim Einschalten des AVR (tiny2313) 
eine (32 bit) Zufallszahl zu ermitteln, mit der ich einen bestimmten 
nachgeschalteten Algorithmus starte.

Was gibt es da für preiswerte Möglichkeiten? Eine Forderung ist übrigens 
noch, daß die Wahrscheinlichkeit gleichverteilt sein soll, also nicht 
schon durch das Verfahren bereits eine Tendenz für bestimmte Gruppen von 
Zahlen da sein sollte. (Man könnte sich vorstellen, man hat ein stark 
temperaturabhängiges Bauelement, das die Ladezeit eines Kondensators 
bestimmt. Zähle ich jetzt beim Einschalten schnell bis 2^32-1 komme ich 
vielleicht immer nur in die Gegend von 10 Mio.) Man könnte das zwar noch 
verwirbeln, indem man die Werte dann als Startwerte für einen 
Pseudo-Random-Generator nimmt, aber das wäre dann doch wieder irgendwie 
korreliert.

Also langer Rede, kurzer Sinn, was für ein Bauelement, Algorithmus, was 
immer, nimmt man dafür?

Grüße
Christoph

Autor: Wolfgang Horn (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tja, Christoph,

der 2313 hat keinen AD-Wandler.

Damit werden die bestimmenden Fragen:
a) hast Du 2 Pins frei? Vielleicht gar die des Analog-Komparators?
b) hast Du eine Brummquelle in der Nähe?
c) Wieviele zusätzliche Bauteile darfst Du spendieren? Beispielsweise 
Photodiode, Photowiderstand, Kondensator zum aufladen und Zeitmessen.

Der Rest ist Arbeit - die verfügbare Quelle unsicherer Information zu 
nutzen.

Eine Kollege hatte mal das Rauschen einer Zenerdiode verstärkt.


Ciao
Wolfgang Horn

Autor: MisterMime (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du kannst auch den Ram(Register auch) auslesen und alle Bytes 
miteinander xoren, die sind alle zufällig. Das funktioniert aber nur 
beim Power Up, nicht beim Reset!

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
AVRs haben DIL-Gehäuse mit 2.54mm Pin-Abstand, nicht? Das ist etwas 
viel.

Also ich benutze zur Initialisierung des Zufallszahlengenerators meines 
DSPs den Tunneleffekt zwischen 2 Leiterbahnen mit 2/1000" Abstand. Die 
Tunnelwahrscheinlichkeit liegt zwar <50%, aber mit geeigneter 
Kalibrierung kann ich vollkommen gleichverteilte Bits bekommen, ich 
erzeuge 128 Bit in ca. 1,2 Sekunden. Ohne Quanteneffekte kannst du keine 
echte Zufälligkeit erreichen!

Autor: Jörg Rehrmann (Firma: Rehrmann Elektronik) (j_r)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Also ich benutze zur Initialisierung des Zufallszahlengenerators meines
>DSPs den Tunneleffekt zwischen 2 Leiterbahnen mit 2/1000" Abstand.

Das würde mich jetzt aber auch interessieren, wo und wie genau da ein 
Tunneleffekt auftritt.

Jörg

Autor: holzi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Quanteneffekte bei 2 mil Abstand ? Wow. Hut ab. Andere muessen eine 
ultrafeine Spitze mit Piezos auf nanometer nahe an eine Oberflaeche 
bringen.

holzi

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Holzi, man muß nicht immer von anderen auf sich selbst schließen. Die 
Versuche zum Tunneleffekt an Nanometerstrukturen zielen auf ganz andere 
Ergebnisse als es für eine simple Zufallsfolge nötig ist.

Autor: Florian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Forumssuche nutzen!
Mann kann es auch komplizierter lösen, aber einfachgeht auch:
http://www.elektor.de/default.aspx?tabid=29&view=t...

Autor: Florian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ups. Ich sehe gerade, welchen µC Du nehmen willst. Also müßtest Du einen 
externen A/D Wandler nehmen.

Autor: Läubi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oder lass den Timer einfach frei durchlaufen und werte das erste 
zufällige externe ereigneis aus (z.B. Tastendruck einen nutzers).
Der Beweis das das ganze gleichverteilt ist könnte zwar schwer werden 
aber das problem wirst du immer haben ;)

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
All die Vorschläge, einen Timer bis zu einem "zufälligen" Ereignis 
hochzuzählen, gehen etwas an der Realität vorbei. Mit wieviel MHz 
arbeitet ein AVR, 8MHz? Dann braucht er ca. 500 Sekunden, um bis 2^32 zu 
zählen. Geht man davon aus, dass das erste Ereignis in der ersten Minute 
nach dem Booten eintritt, sind diese Zählerstände niemals nicht 
gleichverteilt.

Holzi sagt bestimmt gleich, dann lassen wir eben einen zweiten Zähler 
mit der halben Frequenz laufen und haben zwei unabhängige 16-Bit Zahlen 
in Bruchteilen einer Sekunde...

Wem der Aufbau zum Tunneleffekt zu hoch ist, der kann auch einen 
Geigerzähler benutzen und ein paar Zerfälle abwarten. Mit kosmischer 
Strahlung braucht es ca. 10s um mit 8MHz Zählrate 32 Zufallsbits zu 
erhalten. In Londoner Sushiläden deutlich schneller.

Autor: Marvin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Tiny2313 hat doch auch den analogen Komparator? Vielleicht lässt 
sich damit etwas anstellen.

Das mit dem Tunneleffekt hört sich gleichermaßen interessant wie 
durchgeknallt an.
Gibts da für Laien verständliche Informationen? Schaltpläne, Layouts, 
Softwareschnipsel?

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
mein Geigerzählrohr macht etwa alle 2 sec einen Knacks. Wie generiert 
man damit 32 Bits in 10 sec? ich kann die Dauer zwischen zwei Knacksen 
mit 8 MHz also 125nsec Auflösung messen, das wären dann 16 Millionen 
oder 2 hoch 24 mögliche Abstände, wobei das Zählrohr nach einem Knacks 
eine gewisse Erholzeit benötigt.

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Marvin
Alles was du zum Tunneleffekt wissen musst, steht eigentlich auf 
Wikipedia. Die Idee ist, dass du zwei Leiterbahnen spitz zulaufend eng 
zusammenführst. Auf der einen erzeugst du ein hochfrequentes Signal, auf 
der anderen samplest du das gleichgerichtete Signal (Diode nach GND, 
dann zum ADC reicht aus).
Mittels Korrellation zum erzeugten HF-Signal kannst du die kapazitive 
Einkopplung herausfiltern (schafft ein AVR nicht ganz in Echtzeit) und 
übrig bleibt das -nach heutigem Wissen vollkommen zufällige- 
Tunnelsignal.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... wrote:
> All die Vorschläge, einen Timer bis zu einem "zufälligen" Ereignis
> hochzuzählen, gehen etwas an der Realität vorbei. Mit wieviel MHz
> arbeitet ein AVR, 8MHz? Dann braucht er ca. 500 Sekunden, um bis 2^32 zu
> zählen. Geht man davon aus, dass das erste Ereignis in der ersten Minute
> nach dem Booten eintritt, sind diese Zählerstände niemals nicht
> gleichverteilt.


Das sehe ich ganz genau so.

Wenn Du wirklich riesige 32 Bit brauchst (wozu auch immer), dann mußt Du 
notgedrungen stunden- oder tagelang irgendwas externes zufälliges 
messen. Alles andere ist nur Lügen in die eigene Tasche.

Nimm nen Pseudo-Zufallsgenerator, dessen nächster Startwert im EEPROM 
abgelegt wird und der erste Startwert wird durch nen 1-Wire-Adresschip 
erzeugt.


Peter

Autor: Bri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@...
Mit deinem Verfahren bekommt man doch normalverteilte Zufallszahlen und 
keine gleichverteilten, oder?

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Für das Schieberegister hab ich mal in der McMos-Tabelle nachgeschaut:
http://www.mikrocontroller.net/attachment/13236/Ps...
sie reicht bis 2hoch34.
Der einfachste brauchbare Pseudozufallsgenerator maximaler Länge wäre 
damit ein 33-Bit-Schieberegister mit EXOR am 13. und 33. Ausgang, (die 
34 oder 32 brauchen ein EXOR mit 4 Eingängen). Peters Vorschlag wäre 
damit machbar.

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Bri
Du hast recht, da viele Einflüsse auf die -nicht ideale- Messung 
einwirken, tendiert die Verteilung in Richtung Gausskurve, allerdings 
mit asymmetrischen Ausläufern. Eine einfache Transformation erzeugt 
daraus wieder eine Gleichverteilung. Von der Genauigkeit, mit der die 
-empirisch ermittelte- pdf bekannt ist, hängt natürlich ab, wie gut die 
Forderung nach Gelichverteilung letztlich erfüllt ist.

@Peter
Das tagelange warten kann man sich sparen, wenn man den Benutzer nach 
dem Start auffordert z.B. 4x kurz nacheinander eine Taste zu drücken und 
aus der Zeit zwischen zwei Ereignissen jeweils 8bit bekommt. Allerdings 
sind solche Verfahren manipulierbar, wenn ein "Angreifer" den Taster 
mechatronisch auslöst. Selbst bei einigen MHz Zählrate.

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Christoph
>Der einfachste brauchbare Pseudozufallsgenerator maximaler Länge wäre
>damit ein 33-Bit-Schieberegister

Aha, und wie initialisiert man den?

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sag ich doch, zum Beispiel mit Peters Vorschlag
> Nimm nen Pseudo-Zufallsgenerator, dessen nächster Startwert im EEPROM
> abgelegt wird und der erste Startwert wird durch nen 1-Wire-Adresschip
> erzeugt.

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was ist ein 1-Wire-Adresschip? Verknüpft der irgendwelche Daten aus dem 
Speicher? Leute, informiert euch mal über grundlegende Zahlentheorie, 
wenn ihr zu solchen Themen antwortet. Was ist an der generierten Folge 
aus Peters Schieberegister zufälliger als diese 1-Wire-Adresschip-Zahl?
Entweder die 1-Wire-Adresschip-Zahl IST zufällig, dann hat ChristophK 
seinen Seed, oder die ganze Schieberegisterfolge ist es auch nicht.

Christoph Kessler, bist du der OP ChrisophK?

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
nein, das ist ein anderer
Die 1-wire-Chips von Dallas/Maxim http://www.maxim-ic.com enthalten ab 
Werk jeder eine individuelle Adresse, deshalb könnte man das als 
Startwert benutzen, die ist quasi zufällig und wiederholt sich nie. Ist 
auf jeden Fall weniger aufwendig als einen Geiegerzähler einzubauen. Die 
eigentliche Funktion des Chips wird garnicht ausgenutzt.

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Lieber Christoph Kessler,
ChristophK schrieb
>Ich suche nach einer Möglichkeit, beim Einschalten des AVR (tiny2313)
>eine (32 bit) Zufallszahl zu ermitteln
Es geht nicht darum, dass jedes aufgebaute Gerät dem AVR eine neue 
Seriennummer liefert, sondern dass dieser bei jedem NEUEN Einschalten 
eine NEUE Zufallzahl bekommt. Ansonsten kann ChristophK beim 
Programmieren des AVR ein paar mal würfeln und hat eine hervorragend 
zufällige Seriennummer. Aber ich sehe schon, man könnte 2^32 Adresschips 
benutzen, die nacheinander abgefragt werden.
Wie schon andere geschrieben haben, die Antworten von Christoph 
Kessler&Co darf man nicht nach Inhalt, sondern nur nach Quantität 
bewerten. So gesehen werten sie diese Foren ungemein auf. Warum nur habe 
ich den Verdacht, dass viele Hilfesuchende besser beraten wären, wenn 
Kessler&Co nur 1% ihrer Beiträge abschicken und stattdessen mal ein 
kleines bisschen nachdenken, was eigentlich gefragt wurde?

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... wrote:

> ... und stattdessen mal ein
> kleines bisschen nachdenken, was eigentlich gefragt wurde?


Da hat sich aber jemand ganz schön in die Nesseln gesetzt.

Du bist nämlich mit Abstand bisher derjenige, der am wenigsten 
nachgedacht hat.

Schon ganz richtig, daß Du anonym bleibst.



Mit einem zufälligen Startwert ist ein Pseudo-Zufall verdammt nahe am 
echten Zufall.
Deshalb spielen sie ja auch eine so große Rolle in der Praxis.

Die 1Wire Chips liefern eine weltweit einmalige 48Bit-Nummer.

Die restlichen 16 Bits kann man also noch mit dem Pseudozufall exoren.


Peter

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie gut muss die Qualität des Zufallsgenerators sein? Geht es um 
kryptographische Verfahren, steht du bei allen Verfahren zunächst vor 
dem Problem, erstens diese Qualität vorneweg zu beweisen, zweitens sie 
im Betrieb auch langfristig sicherzustellen und zu überprüfen. Das 
dürfte bei allen physikalischen Verfahren ein recht interessanter Aspekt 
sein. Denn beispielsweise Verfahren, die auf Rauschen basieren, besitzen 
u.U. Fehlerquellen, die, ohne dass dies im Bettieb ersichtlich ist, 
irgendwann an Qualität verlieren lassen.

Auch kann relevant sein, inwiefern Beeinflussung von Aussen bedacht 
werden muss. Irgendwelche thermischen- oder Antenneneffekte 
beispielsweise sind darauf naturgemäss empfindlich.

Sind die Randbedingungen nicht ganz so kritisch, kann eine individuelle 
Pseudozufallsfolge auch interessant sein, solange nur deren Startpunkt 
individuell ist. Da käme beispielsweise eine solche in einfachem Tiny 
mit permanentem Batteriebetrieb in Frage, der den Hauptcontroller bei 
dessen Start mit der Seed versorgt. Dieser Tiny ist dann "ab Werk" 
individuell. Das ist zwar streng genommen kein bischen zufällig, aber in 
der Praxis u.U. einfacher und sicherer als analoge Verfahren.

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Peter: 1-Wire-Chips sorgen für Individualität, aber nicht für Zufall. 
Die Qualität von Pseudozufallszahlen steht und fällt mit dem 
Anfangswert. Ist der immer der gleiche, ist es auch die Sequenz. Wenn 
dann noch ein Zusammenhang besteht, zwischen dem Einschalten des 
Controllers und dem Zeitpunkt zu dem die Zufallszahl genutzt wird, hält 
sich der Zufall in recht engen Grenzen.

Was dabei allerdings helfen könnte: Der interne R/C-Oszillator, 
unkalibriert. Nachteil: Muss man die Qualität mathematisch erfassen, 
muss man eine ziemlich Halde von Tinys durchprobieren.

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Einfachste und anpruchsloseste Variante: Pseudozufallszahl mit EEPROM 
als Zwischenspeicher, Startwert "ab Werk" individualisiert. Dank EEPROM 
begrenzte Lebensdauer, aber 100000x dürfte oft ausreichen. Nur sollte 
dann bei den Einschaltvorgängen kein zyklisches Raster drin sein.

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>@Peter: 1-Wire-Chips sorgen für Individualität, aber nicht für Zufall.
>Die Qualität von Pseudozufallszahlen steht und fällt mit dem
>Anfangswert. Ist der immer der gleiche, ist es auch die Sequenz.

Ja, leider ist das den Christoph Ks und pedas schon zu hoch. Schade, 
dass sich hier aufgrund dolcher Beiträge keine sinnvolle Diskussion 
entwickeln kann.

Autor: Läubi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man man immer dieser gegenseitige aufeinader rumgehacke und wem was zu 
hoch ist ... muß sowas sein?

Der Thread ersteller hat sich ja leider nicht wirklich gemeldet was er 
nun wirklich haben will..

Trozallem was spricht dagegen sons Serienummerchip zu nehmen, und den 
lezten Wert der ermittelt wurde im EEProm zu speichern?
Dann hat
a) jeder AVR nen anderen (zufälligen) Startwert
b) beim Einschalten wird halt der Alte wert mit der Serienummer ver XOR 
und man hat eine neune Zufälligen Startwert bei jedem einschalten.

Das ist das praktikabelste es sei den irgenwas spricht dagegen weil noch 
irgenwelche anderen Randbedingungen gelten müssen.

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was bringt der Seriennummerchip denn dabei? Statt dessen kannst du 
genausogut jeden ausgelieferten Controller am Werk mit einem 
individuellen Startwert im EEPROM ausstatten. Und eine dafür brauchbare 
Quelle liefert jedes Linux als /dev/random.

Autor: Läubi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Na wenn man z.b. keine lsut hat jeden AVR mit ner eigene Numemr zu 
versorgen ;)

Autor: fra (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zum Thema Seriennummer sowie Zufallsgenerator.

Fast jeder Kontroller, der Ausgeliefert wird, hat eine
Produkt-ID, eine Seriennummer, sowie eine Zufallszahl (seed).
Die Produkt-ID ist dafür da, um den Seed bei Produktautentifizierungen
zu machen, um sich ev. gegenseitig zu authentisieren. Weiters wird sie
Für Updates usw. gebraucht. Die Seriennummer hat gewisse Funktionalität
bez. timeoutzeiten, usw. Sie wird einfach als datum, zeit,prod_id,rand
zusammengesetzt und ist garantiert eindeutig, wobei man daraus auch
hashes und CRC für übdates und verschiedene Features rausholt.
Hinzu kommen noch einige bytes error-correction code sowie checksum.
Die Produkt-ID ist teil der 32bit Seriennummer, hat aber eine gesonderte
Behandlung. Weiters hat jeder Kontroller einen eigenen 32bit Seed für 
einen
den randomgenerator. Bei den meisten Systemen reicht es aus, durch 
externes
timing, wie startwert des Timers, oder timeout des WDT beim start, oder 
...
usw eine 8-12 bit zahl rauszubekommen, die einfach die iterazionen sowie
einen kleinen Teil des seeds ausmachen, also z.b.
bei Starten checksum über Ram machen, der mit einem hardcodeten init
(getestet,verifiziert) startet, nicht mit 0, das ist meistens fatal.
Dann lass diesen 8bit checksum den random timer x mal laufen,
welcher zuvor mit der 32bit seed initialisiert wurde.
wenn er fertig ist, nimm noch einen timer, der irgenwo vor sich hinläuft
und extrahiere da auch eine 8bit zahl. Nun hast du einen hardcodeten 
seed,
einen generierten, normalerweise 16bit, den du dann mit den zwei 8bit 
werten
und ein bisschen mischen von bits, ev mit einigen xor iterationen des
bereits x-mal durchgelaufenen random algorithm und dann hast du eine
neue Seed, die bei jedem Start anders ist, ohne eeprom.
Damit hast du im Prinzip drei Seeds, die Serial-number, die 
Random-number,
sowie die generierte. Du kannst sie dann abwechselnd nehmen, oder auch
z.b. mit bestimmten events das Random iterieren, um keine Sequenz zu 
generieren.  Der Grund des Random-numer, zusätzlich zur Produktnumber 
ist,
daß diese Geheim ist, d.h. nur der Hersteller kennt die Assotiation 
zwischen Random und Seriennummer, sodaß sichere Authentifizierungen für
Features usw. gemacht werden können, ohne Probleme zu haben, wenn die
Nummer bekannt werden, sowie daß jedes Gerät eine von einem HW-RNG 
erzeugten Seed, welche zuvor auf Statistische Verteilung getestet wurde,
hat. Viele PC Motherboards haben HW-RNG.  Auch kann keiner dann mit
hilfe der Seriennummer den Seed errechnen.

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich hatte Peters Vorschlag genau so verstanden, wie es jetzt nochmal 
vorgeschlagen wurde: Der allererste Wert wird irgendwoher genommen, ob 
1-wire-Chip oder Linux random völlig egal, und dann speichert der AVR 
öfters mal eine der ständig neu erzeugten Pseudozufallszahlen im EEPROM 
ab, um die zuletzt vor dem Ausschalten abgespeicherte als Startwert beim 
nächsten Einschalten zu benutzen.

Was noch stört: das Schieberegister hat zwar 33 Bit, aber 
aufeinanderfolgende Werte sind ja um je eine Stelle verschoben die alte 
Zahl, also wirklich neu ist erst jede 32. Zahl

Autor: fra (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Random Funktion hat nichts mit 32bit schieberegister zu tun, wo
nur ein paar stellen verschoben werden. (im weitesten sinne, bestimmt
aber nicht so einfach wi oben fälschlicherweise angedeutet.)
Ein beispiel unten:

Weiters ist, wenn du dauernd seed wechselst, die Funktion garantiert 
nicht
mehr random, sondern richtig Vorhersehbar. !!! Teste es mal.
Das einzige, was man tun kann, ist die Sequenz ein paar mal intern zu
erhöhen, oder mehrere Randoms gleichzeitig zu verwenden, und 
intervallieren, sodaß die Sequenz nicht mehr ersichtlich wird, muß dann
aber auch getestet werden usw.


[C]

static long s1 = 1;
static long s2 = 1;

#define MODMULT(a, b, c, m, s) q = s/a; s = b*(s-a*q)-c*q; if (s < 0) s 
+= m;

double combinedLCG(void)
{
    long q, z;

    MODMULT(53668, 40014, 12211, 2147483563L, s1)
    MODMULT(52774, 40692, 3791, 2147483399L, s2)
    z = s1 - s2;
    if (z < 1)
        z += 2147483562;
    return z * 4.656613e-10;
}

void initLCG(long init_s1, long init_s2)
{
    s1 = init_s1;
    s2 = init_s2;
}
[/]

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich stimme Peter voll zu und verstehe das Problem nicht warum alles so 
kompliziert gesehen wird.

Wenn man 2 Shiftregister benutzt dann muß man nur beim Reset des AVRs 
einen Seed aus dem EEPROM laden. Mit diesem Seed wird 1. LFSR gestartet 
und dann mit diesem ein neuer Seed berechnet. Dieser ersetzt den alten 
im EEPROM.

Jetzt hat man schonmal eine Pseudo-Zufallsfolge die sich bei jedem Reset 
des AVRs kontinuierlich entwickelt. Das ist normalerweise exakt die 
gleiche Sequenz die sich ergeben würde wenn man diesen LFSR nur einmalig 
initialisiert und dann ständig neue Werte sequientiell erzeugt.

Ein zweiter LFSR mit einem anderen Polynom als der erste wird nun mit 
diesem Seed gefüttert und produziert den Zufall für den laufenden 
Betrieb.

Das ganze Vorgehen hat nur Vorteile gegenüber jeder Hardware Lösung:

1.) es ist mathematisch beweisbar
2.) es ist mit bekannten Seed / Polynomen reproduzierbar, und damit 
letztendlich auch technisch beweisbar Verfahrenssicher
3.) die Komplexität der Seeds/Polynome/math. Verfahren kann fast 
beliebig erhöht werden, auf alle Fälle so enorm hoch das bei unbekannten 
Parametern der erzeugte Zufallsstrom nicht mehr von echten Zufall zu 
unterscheiden ist. Das bedeutet es wird kryptographisch sicher.

Ein HW RNG hat immer ein gewaltiges Problem, man kann nicht die 
Startparameter beeinflussen noch kennt man diese. Das bedeutet mit einem 
HW RNG können wir keine exakt gleiche Sequenz von Zufall erzeugen. Wir 
können also Nichts real reproduzieren, noch das Verfahren auf andere 
Medien übertragen um es als korrekt zu verifizieren.

Es ist also ein leichtes eine einfache Behauptung aufzustellen: "Beweise 
mir das dein HW RNG, der auf einer Diode/Radioaktivem Zerfall oder 
sonstwas basiert, wirklich Zufall produziert !" Diese Frage kann man mit 
einem HW RNG nicht mathematisch sicher beantworten, weil ein HW RNG 
nicht reproduzierbaren Zufall erzeugt.

Bei einem guten Pseudo-RNG ist das aber enorm einfach. Man kennt die 
Formel, man kennt die benutzten Seeds und schwups kann man das auf einem 
AVR, auf dem PC, mit einem Taschenrechner, auf dem Blatt Papier oder 
sogar im Kopf nachrechnen. Es würde bei allen Wegen immer das gleiche 
Resultat rauskommen. Ergo: es entsteht Verfahrenssicherheit weil wir 
alles reproduzieren können und auf alle Parameter Einfluß nehmen können.

Die Frage ob man nun als Aussenstehender nun in der Lage ist aus dem 
Zufallstrom irgendwas "Pseudo-zufälliges" zu erkennen, also ob der 
Zufall nicht wirklich zufällig ist, kann man nun per purer Mathematik 
und den Parametern wie Seeds, Polynome, Verfahren und Zahlenbereiche 
vorrausberechnen. Dh. mit entsprechend gut gewählten Parametern kann man 
einen Pseudozufall nicht mehr von echtem Zufall unterscheiden !

Gruß Hagen






Autor: Fra ncisca (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Ein HW RNG hat immer ein gewaltiges Problem, man kann nicht die
>Startparameter beeinflussen noch kennt man diese. Das bedeutet mit einem
>HW RNG können wir keine exakt gleiche Sequenz von Zufall erzeugen.

Wenn du mit HN RWG echte Zufallszahlengeneratoren (basierend auf z.B. 
radioaktivem Zerfall wie von '...' angedeutet) meinst, so sind genau die 
eben zufällig! Weiters sind Generatoren wie von dir erwähnt, die 
reproduzierbare Folgen erzeugen, kein bißchen zufällig. Weiters hat ein 
Angreifer mit einer einzigen solchen Zufallszahl oder einem daraus 
generierten verschlüsselten Textsegment jegliche Verschlüsselung in 
deinem System ohne jedwede Anstrengung zunichte gemacht.

>Wir können also Nichts real reproduzieren,
Weiters hast du ein Realitätsproblem. Weiters gehörst du sicher zu den 
Leuten, die, falls die Welt nicht die modellierte Klimakatastrophe 
mitmacht, der Meinung ist, dass mit der Welt etwas nicht stimmt. 
Physikalisch zufällige Prozesse sind zufällig! Natürlich kann man dies 
nicht beweisen, sonst gäbe es in der Quantenmechanik nicht die Theorie 
der versteckten Parameter. Weiters kannst du aich die 
Schieberegisterzufälligkeit nur für Spielzeugfolgen beweisen, indem du 
die ganze Folge durchrödelst. Weiters siehst du alt aus, wenn du z.B. 10 
Jahre lang jede Nanosekunde eine neue Zufallszahl brauchst, einen 
solchen Generator wirst du kaum in weniger als 10 Jahren "mathematisch 
beweisen können".
Weiters finde ich das Wort weiters ziemlich furchtbar, vor allem, wenn 
jemand sich angewöhnt, es alle 1-2 Sätze irgendwo einzuwerfen.

Fra ncisca

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>Wenn du mit HN RWG echte Zufallszahlengeneratoren (basierend auf z.B.
>>radioaktivem Zerfall wie von '...' angedeutet) meinst, so sind genau die
>>eben zufällig!

Ja, auf diese Aussage habe ich schon gewartet ;)

Dann beweise das doch mal !
Und bitte beweise mir das der Zufall den wir mit einer noch zu 
vereinbarenden Hardware zu einem bestimmmten Zeitpunkt erzeugt haben 
auch wirklich Zufall war !

Du machst da nämlich einen Denkfehler. Echter Zufall ist nur deshalb 
echter Zufall weil wir annehmen das die zugrunde liegenden physkalischen 
Prozesse für niemenden reproduzierar sind. Weil wir zb. nich die 
Startparameter die beim Urknall vorlagen oder eben die dahinterliegenden 
Prozesse nicht exakt kennen. Desweiteren nehmen wir einfach an das wir 
das alles auch in Zukunft nicht kennen könen. Also alles Annahmen, 
Vermutungen aber keinerlei wirkliche Beweise -> Wissen.

Ich kann dir aber beweisen das ich mit einem einfachen Feuerzeug an zb. 
deiner Diode die ein Zufallsrauschen erzeugt physikalisch die 
Eigenschaften dieses Zufalls direkt beeinflussen und manipulieren kann. 
Kannst du mit deiner Hardware nun wirklich sicherstellen das zu jedem 
Zeitpunkt mit jeder Kopie deines Gerätes auch wirklich Zufall produziert 
wird ? Nein, kannst du nicht. Du wirst also immer noch mathematische 
Verfahren hintendrab setzen, um zb. die Entropie des Zufalls zu 
verbesseren, um ihn mathem. beweisbar sicher zu machen wirst du eine 
kypto. Hashfunktion hintendran setzten. Und vielleicht wirst du dir dann 
sagen, wozu die fu..ing Hardware noch wenn ich gleich einen sehr guten 
Pseudo-RNG benutzen kann der bei für den Benutzer unbekannten 
Startwerten eine Zahlenfolge erzeugt die mathematisch/statistisch 
betrachtet exakt identisch zu echten Zufall ist. Zumindestens aus der 
begrenzten Sichtweise und Lebenszeit der Menschheit betrachtet ?


Gruß Hagen

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>Weiters hat ein
>>Angreifer mit einer einzigen solchen Zufallszahl oder einem daraus
>>generierten verschlüsselten Textsegment jegliche Verschlüsselung in
>>deinem System ohne jedwede Anstrengung zunichte gemacht.

dummes Gelaber. Sehr viele kryptographische Verfahren besieren heute auf 
Stromverschlüsselungen. Das sind nichts anderes als 
Pseudo-Zufallsgeneratoren. Diese wurden mathematisch bewiesen als sicher 
eingestuft, eben weil es praktisch nicht möglich ist deren Zufallsfolgen 
vorherzusagen. Logisch, sonst wären sie ja sinnlos in der Kryptographie. 
Du widersprichst mit deiner Aussage der heutigen Lehrmeinung und dem 
annerkannten Wissen der Mathematik.

Denken wir mal so wie du weiter !
Wir müssen also echten Zufall benutzen um Nachrichten sicher zu 
schützen. Ähm, echter Zufall ist nicht reproduzierbar. Wie willst du 
dann die Schlüssel erzeugen, sie sicher im Netz übertragen, sie 
ebenfalls sicher schützen ohne Sicherheitsverlust ? Komme mir nicht mit 
dem OTP -> One Time Pad. Ja, das ist das mathematisch bewiesenermaßen 
sicherste Verfahren und basiert auf echten Zufallsschlüsseln. Allerdings 
absolut unpraktiabel, eben auf Grund der Schlüsselverteilung.

Wird damit zwar leicht OffTopic, allerdings zeigt dies sehr schön einen 
wichtigen Sachverhalt. Ich diskutiere hier nicht über philosophische 
Dinge, so wie du, sondern schlage praktisch realiserbare, praktisch 
verifizierbare und reproduzierbare Methoden vor, die zusätzlich noch 
einfach in Software zu lösen sind. Jeder Programmierer kann diese 
umsetzen und leicht verifizieren indem er sie auf anderer Hardware mit 
identischen Verfahren und gleichen Startbedinungen reproduzieren kann. 
Das ist das was du jeden Tag machst: Wenn irgendwas mehrmals 
funktioniert dann hast du irgendwas reproduziert, wiederholt und somit 
eine Verfahrenssicherheit. Wir diskutieren also nicht mehr nur über den 
Zufallsgenerator, sondern auch über dessen Implementierung, Testphase 
und dem Beweis das das auch immer sauber funktioniert.

Der einzigste Unterschied zwischem "echten/natürlichem" Zufall und 
künstlich produziertem besteht darin ob wir die benutzten Seeds kennen 
oder in Zukunft eventuell kennen könnten.
Würden wir theoretisch betrachtet alle Ereignisse im Universum seit dem 
Urknall wissen so würden wir auch deinen echten Zufall reproduzieren 
können. Vorrausgesetzt unser System "Universum" ist insich absolut 
geschlossen. Wovon fast alle Wissenschaftler ausgehen. In diesem Moment 
wäre dein achso echter Zufall absolut identisch zu Pseudo-Zufall.

Der Vorteil besteht darin das wir bei Pseudo-Zufall alle Eigenschaften 
des Systemes kennen und mathematisch beweisen können. Auch logisch, da 
alle diese Generatoren reine Gebilde der Mathematik sind, also von 
Menschen in allen Einzelheiten erdacht wurden. In der Physik sind wir 
quasi nur Beobachter und haben nur die Chance hinter die Zusammenhänge 
per Beobachtung zu kommen. Und das ist auch der Grund warum wir an 
Grenzen stoßen müssen wie die Heisenbergsche Unschärfe Relation oder auf 
Quanteneffekte. Aus diesem "Unwissen" heraus und der "Vermutung" das es 
kein Lebewesen jemals schaffen könnte mehr Erkenntniss zu erlangen als 
wir selber, könen wir behaupten das echter Zufall nicht reproduzierbar, 
also berechnenbar sein wird. Diese Annahme ist unbewiesen und sehr naiv, 
ergo: HW-RNG stützen sich im Grunde auf Halbwissen. Jede Erkentiss mehr 
die wir in der Physik erlangen wird also auch dazu führen das immer mehr 
HW-RNG-Typen quasi vorhersagbar oder zumindestens ungeeignet werden. Das 
kann bei auf purer Mathematik basierenden und einmal bewiesenen 
Pseudo-RNGs nur in einem Falle eintreten: nämlich wenn man grundlegende 
Axiome unserer Mathematik widerlegen würde. Das bedeutet dann aber auch 
das fast immer die gesammte Mathematik zusammenbrcht wie ein Kartenhaus. 
Das ist in den letzten Jahrunderten der Mathematik meines Erachtens 
nicht eingetreten.


Gruß Hagen

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja die reine Mathematik mit ihren sauberen Modellen ist viel präziser 
als die reale Welt mit ihren Dreckeffekten.
Ich bezweifle wie gesagt, dass der Geigerzähler gleichverteilte Zahlen 
liefert, weil zum Beispiel die Röhre nach einem Ereignis für ein paar 
Mikrosekunden "blind" ist, deshalb werden diese kleinen Zahlen nicht 
vorkommen.

Autor: Markus Gronotte (happyhippo4u)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein hochempfindliches Mikrophon mit Verstärkungsfaktor um die 100000 und 
dann schmitttriggern und damit einen Interrupt triggern und die 
zeitlichen Abstände nutzen (50Hz unbedingt wegfiltern). Die Ergebnisse 
werden vll Ähnlichkeiten aufweisen aber ganz klar nie gleich sein.. 
Alternativ eignet sich das Rauschen eines Transistors dafür, dann kann 
man evtl. auf den 50Hz filter verzichten.

MfG,

   Markus

Autor: ChristophK (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein nein, der ChristophK bin ich :)
Nicht Christoph Kessler.

Das mit dem Hochzaehlen hatte ich ja schon erwaehnt, dass das nicht so 
einfach geht. (Dauer). Aber wie waer's denn, wenn ich 4 bytes 
nacheinander bis 256 zaehlen lasse. Das ginge ja viel schneller. Also 
reduziert sich das Problem doch schon mal auf die Forderung, eine 
moeglichst gleichverteilte 8-bit Zufallszahl zu generieren. (wobei der 
zeitl. Zwischenraum zwischen den 4 Einzelermittlungen natuerlich 
unkorreliert sein sollte.

Christoph

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die vier Byte müssen dann aber von vier statistisch voneinander 
unabhängigen Ereignissen stammen, wenn derselbe Timer oder was auchimmer 
sie auslöst sind sie nicht unabhängig

da hatte oben schon  ... verspottet:
> Holzi sagt bestimmt gleich, dann lassen wir eben einen zweiten Zähler
> mit der halben Frequenz laufen und haben zwei unabhängige 16-Bit Zahlen
> in Bruchteilen einer Sekunde...

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei Kryptographie gibt es keine Alternative zu ECHTEN Zufallszahlen. 
Egal wie toll euer PRNG-Algorithmus ist, wo 32 Bit Entropie reingehen, 
da kommen maximal 32 Bit Entropie raus, und das ist nicht ausreichend um 
einen Schlüssel zu erzeugen oder einen Stromchiffre-Generator zu 
initialisieren.

Geigerzähler: dass man nicht die Zeit zwischen zwei Impulsen einfach als 
Zufallszahl nehmen kann ist offensichtlich. Aber wenn zwischen den 
Impulsen in der Größenordnung von 100.000 Zählschritte vergehen und man 
das modulo 2 nimmt sieht die Sache schon anders aus.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Andreas,
Sind die Impulse eines Geigerzählers wenigstens gleichverteilt? Mir 
scheint es doch extrem selten, dass sie z.B. mal eine ganze Minute 
ausbleiben, während Abstände in Sekunden normal sind. Rein gefühlsmäßig 
würde ich auf eine irgendwie (asymetrisch) glockenförmige Kurve tippen. 
Das weiße Rauschen ist ja auch Fiktion, jedes natürliche Rauschen geht 
zu hohen Frequenzen hin gegen Null

Autor: ChristophK (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Die vier Byte müssen dann aber von vier statistisch voneinander
> unabhängigen Ereignissen stammen, wenn derselbe Timer oder was auchimmer
> sie auslöst sind sie nicht unabhängig

Entschuldige, das schrieb ich doch (Ausrufezeichen) (Nichtkorreliertheit 
zwischen den Einzelmessungen).

Christoph (K)

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie die Zeit zwischen dem Impulsen verteilt ist - keine Ahnung, aber 
wenn man mit hoher Auflösung zählt und nur ein paar Bit von jedem 
Zählwert verwendet spielt das ja kaum eine Rolle.

Autor: ein anderer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein GM-Zählrohr ist Gott sei dank kein Zufallsgenerator, sondern ist und 
bleibt ein Sensor zum detektieren von Radioaktiver Strahlung. Da die 
natürliche Hintergrundstrahlung in Deutschland um den Faktor 1000 
Schwanken kann ist klar, das du damit unterschiedliche Ergebnisse an 
unterschiedlichen Orten bekommen würdest. Einfaches Beispiel auf einem 
Berg  hast du immer erhöhte Höhenstrahlung. Dazu kommen natürliche 
Schwankungen (Sonnenaktivität etc.).  Neben der von Christop 
beschriebenen Totzeit  haben GM Zählrohre auch einen Eigeneffekt - also 
Impulse deren  Ursache nicht in ionisierender Strahlung liegt. Dieser 
wird in der Regel vom Hersteller angegeben. Ich vermute das zur 
„Labormäßigen Zufallsgenerierung“ der Zerfall eines einzelnen Isotops 
(definierter Masse) verwendet wird der entweder die Hintergrundstrahlung 
deutlich überlagert, oder besser noch das nur die Strahlung dieses 
bestimmten Isotops ausgewertet wird. Mit entsprechender  Laborausrüstung 
ist das kein Problem da der Energiebereich der Strahlung  dem Isotop 
zugeordnet werden kann (siehe Gamma-Spektroskopie). In wieweit das dem 
eigentlich Fragendem oder sonst jemandem hier nützt wage ich zu 
bezweifeln – aber diese Diskussion ist ja ohnehin schon längs in Theorie 
und .... abgeglitten.
Gruß

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für die Aufklärung. Ist also nicht so einfach mit dem 
naturbelassenen Zufall. Auch das niedrigste Bit eines ADC halte ich 
nicht für zufällig genug, das kann gut zu einer Seite hin tendieren. Der 
Vorschlag von Andreas klingt aber gut, irgendwelche (mittlere? das 
modulo2 hab ich nicht verstanden) Bits aus so einer nicht idealen 
naturerzeugten Zahl zu benutzen.

Autor: Idee (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man muss generell so vorgehen, daß man eine Eingangsgöße findet, die zu 
einem gleichverteilten (= 50:50) Fall führt und diesen entsprecht oft 
aufsummiert. Nimmt man z.B. Speicherinhalte her, so kann man diese 
aufsummieren und auf gerade/ungerade prüfen. Um es sicher zu machen, 
invertiert man jede zweite Adresse, damit sich keine Pegel-Präferenzen 
durchsetzen. Somit hat man nach dem Ersten Durchlauf zunmindest ein bit, 
das zu 100% zufällig ist und 50:50 links und rechts liegt. Nun summiert 
man mehrere solcher Einheiten auf (z.B. 10.000 Werte) um eine 
Normalverteilung um (10.000 x 0,5) = 5000 zu erhalten. Dies führ man 
zweimal parallel durch, bildet die Differenz und hat einen extrem 
empfindlichen Wert, der durch Weglassen der oberen Hälfte der Bits 
limitiert wird. Dies sorgt indirekt dafür, daß man dieselbe Architketur 
erhält wie bei einem exhten Zufallszähler, der genügend häufig hat 
überlaufen können (8 Bits , 256 x übergelaufen, sodaß Gleichverteilung 
herrscht). Der Zähler besteht nur hier aus dunteren Bits - der Überlauf 
sind die oberen Bis.

Die unteren Bits, bringen wie gesagt, die gleichverteilte Zufallszahl -> 
hier wäre es wegen ca 4096 -> 12/2 = 6 Bits. Mit mehreren solcher 
Architekturen erhält man dann 12,18 etc Bits.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>Bei Kryptographie gibt es keine Alternative zu ECHTEN Zufallszahlen.

Falsch. Es gibt keine Alternative zu Pseudo-RNGs. Denn Kryptographie 
muss sich sicher sein und das geht nur mit Dingen die man zu 100% 
mathematisch als sicher beweisen kann.

>>Egal wie toll euer PRNG-Algorithmus ist, wo 32 Bit Entropie reingehen,
>>da kommen maximal 32 Bit Entropie raus, und das ist nicht ausreichend um
>>einen Schlüssel zu erzeugen oder einen Stromchiffre-Generator zu
>>initialisieren.

Stimmmt absolut, aber wer redet davon das ein 32Bit RNG kryptographisch 
sicher ist ? Vergleicht man Soft-RNGs mit HW-RNGs so vereinfacht man 
erstmal diese Analyse indem man davon ausgeht das beide Verfahren die 
gleiche mathematische Komplexität besitzen, also NP-vollständige 
Probleme darstellen. Der einzigste Unterschied in der Sicherheit besteht 
dann darin das man die Startparameter kennt oder nicht. Das Wissen um 
diese Startparameter bei Soft-RNGs macht diese dann sicherer. Denn je 
nach Verteilung dieser Startparameter == Schlüsselverteilung gibt es 
Personenkreise die diesen RNG quasi reproduzieren können und andere die 
es mathematisch beweisbar nicht können. RNGs stellen in der 
Kryptographie eine Algortihmenklassse dar die die gleichen Anforderungen 
erfüllen muß wie zb. symmetrische/asymmetrische Verschlüsselungen oder 
die Einweg-Algorithmen. Bei allen diesen Verfahren konstruiert man 
immmer eine Funktion=Formel die mit einem Geheimnis direkt berechnenbar 
sind, aber ohne dieses nicht mehr praktikabel invertierbar sein dürfen.

Die Schranken ab wann nun ein solches Verfahren sicher sein muß 
definieren sich dann im Aufwand,technologisch wie auch zeitlich, um eine 
Invertierung ohne Startparameter hinzubekommen. Das Mittel um diese 
Schranken hochzusetzen ist die Schlüsselgröße in Bits und die 
Verarbeitungsbreite in Bits intern im Algorithmus, sprich die 
Zahlengrößen mit dennen man rechnen muß.

Und da sind 32 Bit bei weitem nicht ausreichend. Das trifft aber auch 
auf einen HW-RNG zu. Denn wenn ich mit diesem nur 32Bit Passwörter 
erzeuge dann sind diese ebenfalls nicht vor Brute Force Attacken sicher. 
Das bedeutet das das nachfolgende Prozessing solcher Schlüssel ebenfalls 
minimal 128 Bit breit sein muß. Wenn dies insich schon notwendig ist so 
kann man auch einen Soft-RNG mit 128 Bit Komplexität benutzen und 
erreicht eine höhere Sicherheit als mit einem HW-RNG, da wir nun exakte 
Beweise durchführen können.

Es geht also garnicht darum ob ein HW-RNG sicherer wäre, als Quelle von 
Zufall, sondern es geht darum bei welchem der uns zur Verfügung 
stehenden Verfahren können wir am meisten beeinflussen, wissen wir am 
meisten und können mit dem geringsten Aufwand das System als wirklich 
sicher beweisen.
Kryptographie ist also eine Wissenschaft die versucht mathematisch 
beweisbare unfaire Systeme zu konstruieren, der Geheimnisträger bestimmt 
was der Nicht-Geheimnissträger machen kann, und das muß absolut 
beweisbar unknackbar sein.

Kryptographie ist pure Mathematik, und jede Benutzung von nicht 
eindeutig beweisbaren Mitteln (eben aus der Physik) macht einen echten 
mathem. Beweis zur Sicherheit des Systemes unmöglich.

Ich rede hier also nicht mehr davon welcher Zufall der beste als 
Verfahren sein sollte, sondern wie man vorgehen muß, in seiner logischen 
Argumentation, wenn man ein sicheres System konstruieren und beweisen 
muß. Und HW-RNGs machen angewendet in der Kryptographie alle 
nachflogenden Bemühungen von vornherein zu nichte da sie eine Variable 
in das System einschleusen die nicht mehr im Rahmen der Kryptographie 
beweisbar ist.

Bricht man dieses Wissen nun runter so ergibt sich:

1.) es gibt RNGs in Software die statistisch betrachtet genausoguten 
Zufall produzieren wie echte RNGs.
2.) es gibt RNGs die wir als Menschen konstruiert haben und die durch 
schlaue Köpfe per math. Beweisen und Analysen als sehr gut eingestuft 
sind, bzw. gleichguten Zufall erzeugen
3.) es gibt RNGs die reproduzierbare Ergebnisse liefern können.

Also warum zum Teufel, frage ich mich, sollte man noch HW-RNGs benutzen 
wenn man mit Pseudo-RNGs das gleiche Resultat viel besser erreichen kann 
?

Die Antwort: weil bei gleicher Komplexität der Verfahren aus unserem 
heutigen Wissenstand heraus wir

a.) eine MCU benötigen die mit unendlich großen Zahlen rechnen können 
muß, wenn wir Soft-RNGs benutzen wollen
b.) eine simple Diode als HW-RNG eine NP-vollständige Zufallsfolge 
erzeugen kann ohne das wir eine MCU benötigen die selber NP-vollständige 
Probleme berechnen kann (was es ja praktisch nicht geben kann).

Stellt sich nur die Frage warum benötigt man so guten Zufall ?

Für einen stinknormalen elektronischen Würfel, für ein Game auf dem AVR 
benötigt man sowas nicht. Da reichen 32 Bit Komplexität egal ob Software 
oder Hardware vollkommen aus. Aber wir benötigen nach Möglichkeit ein 
Verfahren das zu Testzwecken immer die gleichen Zufallsfolgen erzeugen 
kann, einfach um eine reproduzierbare Simulation unserer Software 
durchführen zu können. Und das geht mit HW-RNGs nicht.

Per logischer Analyse kann man also feststellen das man fast nie echten 
Zufall benötigt, sondern ganz andere Anforderungen viel mehr ins Gewicht 
fallen.

Einen echten (physikalsichen) Zufall benötigt man nur zwingend in 
physikalischen Prozessen/Experimenten die die gleiche Eigenschaften 
haben müssen wie das Untersuchungsobjekt. Also eigentlich nur bei der 
Untersuchung von physikalischen Prozessen. Dort ist ein Pseudo-RNG fehl 
am Platz. Aber ansonsten ?!?

Gruß Hagen


Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich versuche einfach nicht mehr, dich zu überzeugen, dass nur 
physikalische Zufallsgeneratoren zuverlässig für kryptographische Zwecke 
sind. Es wäre aber auch wünschenswert, dass du dein Zehntelwissen 
(Halbwissen wäre übertrieben) nicht duch Wiederholung als fundiert 
darzustellen versuchst.

>1.) es gibt RNGs in Software die statistisch betrachtet genausoguten
>Zufall produzieren wie echte RNGs.
KEINE der RNGs mit logischen Verknüpfungen wurde als zuverlässig 
"bewiesen". Sie werden nur nach und nach mittels ICA (Independent 
Component Analysis, Verallgemeinerung der Hauptkomponentenanalyse) 
falsifiziert.

>2.) es gibt RNGs die wir als Menschen konstruiert haben und die durch
>schlaue Köpfe per math. Beweisen und Analysen als sehr gut eingestuft
>sind, bzw. gleichguten Zufall erzeugen
Nein. Oder basieren diese Beweise auch auf oft genug wiederholten 
Behauptungen?

>3.) es gibt RNGs die reproduzierbare Ergebnisse liefern können.
Ja. Z.B. x(i+1)=x(i). Nicht optimale Zufallseigenschaften, aber gut 
reproduzierbar. Vorausgesetzt man kennt den Startwert. Aber da der ja so 
schwer herauszufinden ist, wäre dies soch ein guter Kandidat für deine 
Kryptographie. Mannomann.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ ... (Gast)

Informiere dich bitte über

- BBS-RNG, Blum Blum Shub Generator oder auf deutsch den Quadratischen 
Reste Generator
- den Micalli Schnorr Generator

beides sind zahlentheoretische Pseudo Zufallsgeneratoren die mathem. 
bewiesen wurden, vollständig wohlgemerkt. Natürlich sind es nur die 
bekanntesten Vertreter kryptographisch relevanter PRNGs. Ein andere sehr 
guter Vorschlag stammt von B.Schneier und heist YARROW, dieser benutzt 
Hashfunktionen.

Im Gegensatz zu dir versuche ich nämlich nicht durch argumentative 
Tricks eine grundsätzlich falsche Meinung richtiger darzustellen.

Wir reden von der allgemeinen Klasse der Pseudo Zufallsgeneratoren, und 
wenn du nur die "KEINE der RNGs mit logischen Verknüpfungen.." als 
einzigste Klasse von solchen Generatoren kennst, ausgerechnet diejenige 
Gruppe der PRNGs die schon immer nur Krücken waren, dann ist das ein 
stark begrenztes Sichtfeld.

Ein guter, und auch mit begrenztem Wissen begreifbarer, Einstieg in zb. 
den BBS Generator ist das Buch

"Angewandte Kryptographie" von B.Schneier ISBN 3-89319-854-7

weitergehend und tiefgreifender behandlen

"Handbook of applied Cryptography", Menezes, van Oorschot, Vanstone ISBN 
0-8493-8523-7

"A Course in Computational Algebraic Number Theory", Henri Cohen, ISBN 
0-387-55640-0

die Theorie. Die letzteren beiden sind leider nur in englisch verfügbar. 
Ansonsten kann ich auch noch ne Menge PostScripts mit zb. Dissertationen 
und akademsichen Abhandlungen zur Verfügung stellen. Diese sind meist 
wesentlich moderner und neueste Forschungsergebnisse, allerdings immer 
englisch und natürlich nur noch mit mathm. Kenntnissen verständlich.

Gruß Hagen

PS: auch in D.Kuth's Standardwerk kann man einiges nachlesen. Alledings 
bekommt man dieses nur noch beim Trödler. Die deutsche Übersetzung vom 
Kapitel "Arithmetics" gibts aber noch. ISBN 3-540-66745-8


Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hagen,
kann man die von Dir genannten Generatoren in einem einfachen 
Mikrocontroller unterbringen, wie die Anfangsfrage ja war, oder ist der 
Speicherbedarf oder Rechenaufwand zu groß?

Autor: Kragenplatzer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Beachtlicher Umgangston, wenn professionelle Besserwisser 
aufeinanderstoßen ... ;-)

Ohne es den Kontrahenten gleichtun zu wollen, nur folgendes zur 
Richtigstellung:

1. "HW-RNG stützen sich im Grunde auf Halbwissen." Es ist ein 
verbreiteter Irrtum (eher: Wunschdenken), dass der "Zufall" der 
Quantenphysik nur vorläufigen Charakter hat, bis neuere Erkenntnisse ihn 
erklären bzw. bis die vollständigen Eingangsparameter bekannt sind. Aber 
in Wirklichkeit ist es Konsens, dass dieser "Zufall" physikalisches 
Prinzip ist, dass Qunanteneffekte unabhängig vom zur Verfügung stehenden 
Wissen nicht voraussagbar sein können. Dessen ist man sich so sicher, 
dass man es für Quantenverschlüsselungsverfahren einsetzt. Kommt bei 
schnöden physikalischen Zufallszahlengeneratoren aber ebenso zum Einsatz 
(wenn sie denn auf diese Prinzipien aufsetzen) und das lässt sich dort 
auch mathematisch/physikalisch beweisen.

2. Weder physikalische noch mathematische Zufallszahlengeneratoren 
liegen "ab Werk" in einer Form vor, wie man sie z.B. für 
kryptographische Verfahren benötigt. In beiden Fällen werden die 
Ausgangsdaten des RNG noch mathematisch behandelt, um die benötigte 
Zufallsverteilung zu erhalten. Eher absurd, hier das eine Verfahren 
gegen das andere ausspielen zu wollen.

3. Kein kryptographisches Verfahren wurde durch zu schwache 
physikalische Zufallsquellen geknackt (etwa, weil jemand raffinierte 
physiologische Erkenntnisse über den zeitlichen Abstand zweier 
Tastendrücke gewonnen hätte, die zur Seed-Bildung in Kryptosoftware 
benutzt worden wäre. Sondern, weil mathematische Verfahren in der 
Kryptographie eben doch nicht mathematisch bewiesen unumkehrbar sind. 
Während niemand ernsthaft mit dem Zusammenbruch der Quantenphysik durch 
neue Erkenntnisse rechnet, kann man nicht ausschließen, dass neue 
Erkenntnisse über Primazahleigenschaften nicht plötzlich große Teile des 
Standes der Technik in der Kryptographie obsolet machen.


Also: die Diskussion um die Beschaffenheit des RNG geht am eigentlichen 
Problem vorbei. Sowohl für physikalische wie für numerische Verfahren 
stehen jeweils beweisbar sichere Quellen zur Verfügung. Klar haben 
numerische Verfahren einen Vorteil durch die Reproduzierbarkeit und 
physikalische durch die einfachere Realisierbarkeit am µC, aber für 
einen Glaubenskrieg unter selbsternannten Sicherheitsexperten taugt das 
absolut nicht.

Autor: Ruhigbleiber (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>3. Kein kryptographisches Verfahren wurde durch zu schwache
>physikalische Zufallsquellen geknackt (etwa, weil jemand raffinierte
>physiologische Erkenntnisse über den zeitlichen Abstand zweier
>Tastendrücke gewonnen hätte,
Solche Verfahren wurden vermutlich nicht geknackt, weil sie nie 
ernsthaft eingesetzt wurden.

>Sondern, weil mathematische Verfahren in der
>Kryptographie eben doch nicht mathematisch bewiesen unumkehrbar sind.
Wie z.B. die WEP-Verschlüsselung? Wurde je bahauptet, dass die sicher 
wäre?

>Während niemand ernsthaft mit dem Zusammenbruch der Quantenphysik durch
>neue Erkenntnisse rechnet, kann man nicht ausschließen, dass neue
>Erkenntnisse über Primazahleigenschaften nicht plötzlich große Teile des
>Standes der Technik in der Kryptographie obsolet machen.
Dafür braucht es keine neuen Erkenntnisse über Primazahleigenschaften, 
sondern ein einfacher 1000-Qubit-Quantencomputer (wenn es ihn denn in 
ein paar Jahrzehnten gibt) entschlüsselt jeden RSA-Schlüssel in 
Nullkommanichts.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Christoph:

ja kann man und wird sogar auch. Du kannst im Grunde jeden guten 
Verschlüsselungsalgo. in einen RNG umwandeln, zb. AES. Oder du benutzt 
wie beim YARROW eine Hashfunktion. Jede Crypto Karte kann dies, zb. die 
alten BasicCards basierten auf 8Bit-AVRs.

@ Kragenplatzer (Gast)

Frage: Wie entstehen die zufälligen Quanteneffekte ? Laut meinem Wissen 
entstehen sie weil der Zusammenhang zwischen "Ursache und Wirkung" also 
die Kausalität für einen Beobachter nicht mehr gilt. Das heist man kommt 
an eine Grenze in der quasi die Physik unscharf wird. Aber bisher wurde 
eben nur bewiesen das unsere Möglichkeit der Beobachtung unscharf wird, 
wir sehen also aus unserem Blickwinkel heraus nur das sich unsere 
gewohnte Physik auflösst. Das heist aber noch lange nicht das sie es 
auch wirklich tut, das es keine Kausaltitäten hinter der uns nicht mehr 
erfassbaren Umwelt gibt. Und wir werden es niemals so richtig 
experimentel wissen können. Das besagt ja die Heisenbergsche Theorie, 
wie auch die Quantenphysik. Wir stoßen an eine Grenze die wir nicht 
überschreiten können. Diese Grenze ist eine Wissensgrenze. Dh. wenn wir 
daraus Zufall erzeugen dann wissen wir eben nicht welche tatsächlichen 
Eigenschaften er hat.

Wenn nun ein Verfahren der Mathematik geknackt wurde dann hat das 2 
mögliche Ursachen:

1.) es lag nie ein starker Beweis vor das das Verfahren wirklich sicher 
ist. Siehe eben WEP Verschlüsselungen, das schon vor seiner Einführung 
stark kritisiert wurde.

2.) durch neues Wissen hat man Methoden entwickelt die nun ein bis dato 
schwer lösbares Problem einfacher lösbar werden lässt.

Das ist gut so, denn nun wissen wir das alle Verfahren die wir benutzt 
haben unsicher sein müssen und werden sie durch neue ersetzen. Dh. durch 
unseren Wissens-schaffens-Prozess in der Mathrematik erlangen wir auch 
eine Sicherheit in der Kryptographie (solange Wissen frei ist 
wohlgemerkt, aber das ist Politik).

>>Dafür braucht es keine neuen Erkenntnisse über Primazahleigenschaften,
>>sondern ein einfacher 1000-Qubit-Quantencomputer (wenn es ihn denn in
>>ein paar Jahrzehnten gibt) entschlüsselt jeden RSA-Schlüssel in
>>Nullkommanichts.

Tja das sind solche Aussagen die ich nicht sonderlich mag.
Mit einem hypotetischem Quantencomputer lassen sich tatsächlich alle RSA 
Schlüsel die man heute benutzt in Nullkommanichtds knacken. Und? Dann 
benutzen wir RSA Schlüssel die so groß sind das sie eben nicht mehr in 
NullKommanNichts knackbar sind. Ja, ich weiß ein Quantencomputer ist 
superparellel und lösst alles in NullKommaNichts. Also auch die Frage 
wer sind wird, was wollen wir, wer ist Gott usw. usw. wozu dann noch 
irgendwas verschlüsseln ?

Wichtig ist doch nur eines: Der mathematische Aufwand einen RSA 
Schlüssel zu erzeugen ist um vieles weniger komplex als diesen Schlüssel 
knacken zu wollen. Das ist ja die Basis jedes Verfahrens der 
Kryptographie. Man kennt zwei Wege eine Berechnung durchzuführen. Einen 
leichten sehr schnellen wenn man ein Geheimnis kennt und einen super 
schweren Weg das gleiche zu erreichen. Das heist die Komplexität, also 
der Aufwand, unterscheidet sich  mathem. beweisbar enorm. Natürlich 
immer nur ausgehend vom aktuellen Wissensstand, das ist logisch. Nun, 
auch mit einem hypothetischen Quantencomputer wird sich an diesen 
Komplexitäten nichts ändern können.

Die Annahme das ein Quantencomputer alles ohne Aufwand in 
NullKommaNichts berechnen kann ist nämlich falsch. Das wäre nämlich 
gleichzusetzen mit einer Singularität, 0 Energie rein -> unendlich 
Energie raus oder umgekehrt. Ergo, auch ein Quantencomputer benötigt 
Resourcen und diese sind  in einem geschlossenen System wie unser 
Universum immer begrenzt und nicht unendlich.

Das sind aber alles Betrachtungen die unendlich weit von 8 Bit AVRs 
entfernt sind und damit so ziemlich offtopic. Meine Standpunkte habe ich 
lang und breit dargelegt ;) Wenn sollte man einen separaten Thread in 
Allgemeines aufmachen.

Gruß Hagen

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hübsch, wie sich hier über Verschlüsselungen gestritten wird.

Dabei hat der Fragesteller mit keinem Wort erwähnt, was er mit der 
32Bit-Zahl überhaupt machen will.

Von Verschlüsselung war nie die Rede.


In der Bundeswehr hatten sie früher mal einen Paßwortgenerator mit 
hunderten von Rauschdioden, ein riesen Schrank.
Die Bedienung war aber so umständlich und der Output so gering, daß nur 
die allerwichtigsten Dienststellen mit einem täglichen Paßwort versorgt 
werden konnten.

Das Ding war daher nur wenige Jahre in Betrieb.
Danach wurde auf stinknormale Rechner mit Softwaregeneratoren 
umgestellt.

Soviel zum Thema natürliche Zufallsquellen.


Peter

Autor: Kragenplatzer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>3. Kein kryptographisches Verfahren wurde durch zu schwache
>>physikalische Zufallsquellen geknackt (etwa, weil jemand raffinierte
>>physiologische Erkenntnisse über den zeitlichen Abstand zweier
>>Tastendrücke gewonnen hätte,
>Solche Verfahren wurden vermutlich nicht geknackt, weil sie nie
>ernsthaft eingesetzt wurden.

Das ist absolut üblich, die für die Schlüsselerzeugung nötige Entropie 
auf diese Art zu gewinnen!

>>Sondern, weil mathematische Verfahren in der
>>Kryptographie eben doch nicht mathematisch bewiesen unumkehrbar sind.
>Wie z.B. die WEP-Verschlüsselung? Wurde je bahauptet, dass die sicher
>wäre?

Welches Verfahren ist denn bitte schön von der RNG bis zum fertigen Code 
bewiesenermaßen sicher? "Bewiesen" ist etwas anderes als "nach heutigem 
Kenntnisstand nur durch Brute-Force zu knacken)!

>Dafür braucht es keine neuen Erkenntnisse über Primazahleigenschaften,
>sondern ein einfacher 1000-Qubit-Quantencomputer (wenn es ihn denn in
>ein paar Jahrzehnten gibt) entschlüsselt jeden RSA-Schlüssel in
>Nullkommanichts.

Mag sein, ist mir egal. Die neue Erkenntnis über Primzahleigenschaften 
kann aber schon morgen vorliegen, nicht erst in ein paar Jahrzehnten.

>Wir stoßen an eine Grenze die wir nicht
>überschreiten können. Diese Grenze ist eine Wissensgrenze.

Eben. Und das reicht. Denn diese Grenze ist keine weiter verschiebbare 
wie jene mathematischen Grenzen, auf die wir trauen.

>1.) es lag nie ein starker Beweis vor das das Verfahren wirklich sicher
>ist. Siehe eben WEP Verschlüsselungen, das schon vor seiner Einführung
>stark kritisiert wurde.

>2.) durch neues Wissen hat man Methoden entwickelt die nun ein bis dato
>schwer lösbares Problem einfacher lösbar werden lässt.

Die Grenze verstehe ich nicht. "Ein starker Beweis" umfasst für mich den 
Beweis, dass es keine alternativen Methoden geben kann, mit denen sich 
das Problem weiter vereinfacht.

Und, worauf ich hinaus wollte: davon ist man betroffen, egal ob man auf 
physikalische RNG setzt oder nicht (pathologische Ausnahme wie immer das 
One-Time Pad).

>Das ist gut so, denn nun wissen wir das alle Verfahren die wir benutzt
>haben unsicher sein müssen und werden sie durch neue ersetzen.

Was insbesondere im Bereich der Signaturen natürlich ein Problem 
darstellt: wenn sich eine Methode mit Ihrer Entdeckung bereits ausnutzen 
lässt (und nicht erst mit der übernächsten Hardwaregeneration), lässt 
sich die Echtheit eines Vertrages ja schon nicht mehr beweisen, um ihn 
mit einem neuen Verfahren bestätigen zu können.

Autor: Nichtmehrsoruhigbleiber (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Frage: Wie entstehen die zufälligen Quanteneffekte ? Laut meinem Wissen
>entstehen sie weil der Zusammenhang zwischen "Ursache und Wirkung" also
>die Kausalität für einen Beobachter nicht mehr gilt. Das heist man kommt
>an eine Grenze in der quasi die Physik unscharf wird.

Ich denke hier setzt dein von ... festgestelltes Zehntelwissen ein.

>Aber bisher wurde
>eben nur bewiesen das unsere Möglichkeit der Beobachtung unscharf wird,

In der Physik wird nichts bewiesen, sondern nur Hypothesen mit einer 
gewissen Wahrscheinlichkeit verifiziert.

>wir sehen also aus unserem Blickwinkel heraus nur das sich unsere
>gewohnte Physik auflösst. Das heist aber noch lange nicht das sie es
>auch wirklich tut, das es keine Kausaltitäten hinter der uns nicht mehr
>erfassbaren Umwelt gibt. Und wir werden es niemals so richtig
>experimentel wissen können.

>Das besagt ja die Heisenbergsche Theorie,
>wie auch die Quantenphysik.

nein.

>Wir stoßen an eine Grenze die wir nicht
>überschreiten können. Diese Grenze ist eine Wissensgrenze. Dh. wenn wir
>daraus Zufall erzeugen dann wissen wir eben nicht welche tatsächlichen
>Eigenschaften er hat.

Die Zufallsverteilungen sind, wenn man die Axiome der Quantenmechanik 
voraussetzt, berechenbar. Und die Axiome wurden tausendfach verifiziert, 
z.B. in TeraByte von Daten am Cern.

>Mit einem hypotetischem Quantencomputer lassen sich tatsächlich alle RSA
>Schlüsel die man heute benutzt in Nullkommanichtds knacken. Und? Dann
>benutzen wir RSA Schlüssel die so groß sind das sie eben nicht mehr in
>NullKommanNichts knackbar sind.

Und was sagst du dazu, dass für einen QC das Finden und das Knacken 
eines RSA-Codes Probleme gleicher ORdnung sind?

>Wichtig ist doch nur eines: Der mathematische Aufwand einen RSA
>Schlüssel zu erzeugen ist um vieles weniger komplex als diesen Schlüssel
>knacken zu wollen.

Was ist ein "mathematischer Aufwand"?? Wenn du ihn in Operationen wie 
Summe und Multiplikation misst, lass dir gesagt sein, dass ein QC im 
Fall der Primzahlfaktorisierung um so viel effzienter ist, wie diese 
Faktorisierung "aufwendiger" ist als der Primzahltest zur Generierung.

Und nein, der QC ist keine Maschine zur Suche nach der Frage zu 42, aber 
im Fall von Primzahlfaktorisierung wurde seine Effizienz mathematisch 
BEWIESEN! http://en.wikipedia.org/wiki/Shor's_algorithm

>Das ist ja die Basis jedes Verfahrens der
>Kryptographie. Man kennt zwei Wege eine Berechnung durchzuführen. Einen
>leichten sehr schnellen wenn man ein Geheimnis kennt und einen super
>schweren Weg das gleiche zu erreichen. Das heist die Komplexität, also
>der Aufwand, unterscheidet sich  mathem. beweisbar enorm. Natürlich
>immer nur ausgehend vom aktuellen Wissensstand, das ist logisch.

>Nun,
>auch mit einem hypothetischen Quantencomputer wird sich an diesen
>Komplexitäten nichts ändern können.

Föllig flasch!
Sieh mal ein winziges Stück über deinen mathematischen Tellerrand, und 
du wirst wahnsinnig viel interessante Physik entdecken. Auch viel weiter 
entfernt erstreckt sich immer noch das Reich der Physik. Und wenn du 
bereit bist, noch viel viel weiter in der Welt des Wissens zu reisen, 
kommst du irgendwann zu den Grundzügen der Chemie, dann der Biologie, 
und schließlich kämst du im wirklichen Leben an. Öh, äh, ok ich verstehe 
warum du vor deinem Bücherregal stehen bleibst, da weiß man, was man 
hat.

>Die Annahme das ein Quantencomputer alles ohne Aufwand in
>NullKommaNichts berechnen kann ist nämlich falsch. Das wäre nämlich
>gleichzusetzen mit einer Singularität, 0 Energie rein -> unendlich
>Energie raus oder umgekehrt. Ergo, auch ein Quantencomputer benötigt
>Resourcen und diese sind  in einem geschlossenen System wie unser
>Universum immer begrenzt und nicht unendlich.

Wie lautet der schöne Spruch? Diskutiere nie mit einem Idioten. Erst 
zieht er dich auf sein Niveau herab, und dann schlägt er dich mit 
Erfahrung.

Auch wenn ... unberechtigterweise die Pseudozufallsgeneratoren 
verurteilt, hat er es bei der Beurteilung deines Argumentationsstils 
ganz gut getroffen.

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hagen Re wrote:
>>>Bei Kryptographie gibt es keine Alternative zu ECHTEN Zufallszahlen.
>
> Falsch.
...
> "Angewandte Kryptographie" von B.Schneier ISBN 3-89319-854-7

S. 482:
"Für manche Anwendungen sind kryptographisch sichere 
Pseudozufallsfolgengeneratoren nicht gut genug. Oft braucht man in der 
Kryptographie echte Zufallszahlen. Das wichtigste Beispiel dafür ist die 
Erzeugung von Schlüsseln."

Wie gesagt: egal wie gut deine Algorithmen sind, wenn du einen Schlüssel 
erzeugen willst brauchst du IMMER echten Zufall, da führt kein Weg dran 
vorbei.

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> "Angewandte Kryptographie" von B.Schneier ISBN 3-89319-854-7

>S. 482:
>"Für manche Anwendungen sind kryptographisch sichere
>Pseudozufallsfolgengeneratoren nicht gut genug. Oft braucht man in der
>Kryptographie echte Zufallszahlen. Das wichtigste Beispiel dafür ist die
>Erzeugung von Schlüsseln."

Den Ausschnitt verstehe ich so nicht. "Für manche Anwendungen sind 
kryptographisch sichere Pseudozufallsfolgengeneratoren nicht gut genug." 
impliziert doch, dass Pseudozufallsfolgengeneratoren für Kryptographie 
ausreichen können. "Oft braucht man in der Kryptographie echte 
Zufallszahlen." besagt für mich das Gegenteil.

Autor: Ruhigbleiber (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>- BBS-RNG, Blum Blum Shub Generator oder auf deutsch den Quadratischen
>Reste Generator
>- den Micalli Schnorr Generator

>beides sind zahlentheoretische Pseudo Zufallsgeneratoren die mathem.
>bewiesen wurden, vollständig wohlgemerkt.

Was ist der Mathematische Beweis eines Zufallsgenerators?

Wird bewiesen, dass die Zahlenfolge die maximale Periode besitzt? Wenn 
ja, was sagt der Beweis über die Zufälligkeit aus? Dann wäre ja auch 
x->x+1 modulo 2^32 ein geeigneter 32-Bit RNG.

Wird bewiesen, dass Gleichverteilung, Varianz etc. den Vorgaben 
entsprechen? Wie wird ausgeschlossen, dass das zugrundeliegende Muster 
nicht für bestimmte Anwendungen die Zufälligkeit zunichte macht?

Wird bewiesen, dass die Rekonstruktion des Algorithmus aus der 
Zahlenfolge NP-vollständig ist? Dies wäre der einzig interessante 
Beweis. Wenn ja, wie sieht das Beweisprinzip aus?

Autor: Bernd S (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Wird bewiesen, dass die Rekonstruktion des Algorithmus aus der
>Zahlenfolge NP-vollständig ist? Dies wäre der einzig interessante
>Beweis. Wenn ja, wie sieht das Beweisprinzip aus?

Genau. Unter der gleichen Annahme, die der RSA-Kodierung zugrundeliegt, 
dass das Faktorisieren eines n-stelligen Produktes aus zwei Primzahlen 
eine Komplexität größer als O(n^k) für jedes k besitzt, ist die 
Vorhersage der nächsten Pseudozufallszahl aus allen vorherigen Zahlen 
von gleicher Komplexität. Über Gleichverteilung usw. macht der Beweis 
ersteinmal keine Aussage.
Wenn Hagen dies als Beweis eines RNG definiert, ist der RNG also 
bewiesen. Qed.

Bernd

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Korrekt. Und die "pseudozufällige Gleichverteilung" entsteht dadurch das 
man zb. in modulare Ringen arbeitet. Wenn man nicht die Kardinalität 
dieser Menge faktorisieren kann, die 1 oder 2 Primzahlen die als Modul 
benutzt werden, dann entsteht eine gleichverteilte aber nicht 
vorhersagbare noch zurückrechenbare Folge von Bits, wenn man einfach 
immer ein Register modulo rechnet. Das wird sehr oft schon impliziert 
und als trivial erachtet und deshalb nicht explizit beschrieben.

Wobei man hier abhängig vom Verfahren analysieren muß. Die Folge der 
Zahlen ist also so komplex das sie statistisch betrachtet identisch mit 
echtem Zufall ist (aus mathematischer Sicht), nur eben mit dem Vorteil 
das derjenige der alle Startparameter kennt diese Folge eben doch 
vorausberechnen/zurückberechnen kann. In diesem Moment habe wir das was 
wir suchen: ein absichtlich unfaires System.

Gruß Hagen

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man rechnet dabei eben nicht f(x) = x +1, das wäre idiotisch. Sondern 
immer Multiplikativ zb. f(x) == x^y mod N. Bei der Operation x^y erzeugt 
man ein Element eines modularen Ringes das immer größer als N ist. Mit 
der modulo Operation erzeugt man dann ein dazu in diesem Ring 
kongruentes Element. Man muß nun aber das Modul N faktoriesieren können 
damit man dies Folge f(x) berechnen kann. Wenn diese Faktorisation aber 
praktikabel undurchführbar ist, wohlgemerkt nach heutigem 
Wissens-/Technologie Stand, dann ist das beweisbar sicher. Wichtig dabei 
ist dann eben der Punkt das wir exakt wissen woher unsere 
pseudo-Zufallsfolge stammt, welche Mathematik zugrunde liegt und das man 
das beweisen kann.

Gruß Hagen

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>S. 482:
>"Für manche Anwendungen sind kryptographisch sichere
>Pseudozufallsfolgengeneratoren nicht gut genug. Oft braucht man in der
>Kryptographie echte Zufallszahlen. Das wichtigste Beispiel dafür ist die
>Erzeugung von Schlüsseln."

Diese Aussage ist ja auch korrekt, das bestreitet ja keiner. Die Frage 
ist unter welchem Betrachtungsstandpunkt das stimmt. In einem offenen 
System kann man keinen sicheren PRNG benutzen da man ja die geheimen 
Startparameter nicht schützen kann. Dann muß man notgedrungen echten 
Zufall benutzen, da dieser nicht geschützt werden muß. In einem 
abgechlossenen und "einbruch sicheren" System erübrigt sich diese 
Forderung aber, und man sollte dann meiner Meinung nach eben sichere 
PRNGs benutzen.

Gruß Hagen

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hagen Re wrote:
>>S. 482:
>>"Für manche Anwendungen sind kryptographisch sichere
>>Pseudozufallsfolgengeneratoren nicht gut genug. Oft braucht man in der
>>Kryptographie echte Zufallszahlen. Das wichtigste Beispiel dafür ist die
>>Erzeugung von Schlüsseln."
>
> Diese Aussage ist ja auch korrekt, das bestreitet ja keiner. Die Frage
> ist unter welchem Betrachtungsstandpunkt das stimmt. In einem offenen
> System kann man keinen sicheren PRNG benutzen da man ja die geheimen
> Startparameter nicht schützen kann. Dann muß man notgedrungen echten
> Zufall benutzen, da dieser nicht geschützt werden muß. In einem
> abgechlossenen und "einbruch sicheren" System erübrigt sich diese
> Forderung aber, und man sollte dann meiner Meinung nach eben sichere
> PRNGs benutzen.

Und was verwendet man als Startparameter für diese PRNGs? Genau: 
Zufallszahlen. Echte Zufallszahlen. Du kannst das drehen und wenden wie 
du willst, um den Zufall kommst du nicht herum.

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und um das nochmal zu betonen: du kannst keine 32 Bit langen 
Zufallszahlen als Startparameter verwenden und daraus z.B. einen 128 Bit 
langen Schlüssel erzeugen. Die Unsicherheit die ein Angreifer über den 
Schlüssel hat kann nie größer werden als das was du an ECHTEM Zufall in 
die Erzeugung reinsteckst.

Autor: Bernd S (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Und was verwendet man als Startparameter für diese PRNGs? Genau:
>Zufallszahlen. Echte Zufallszahlen.

In dem Zusammenhang habe ich eine Frage zur Praxis des RSA-Verfahrens 
bzw. des BBS-Generators, deren Theorie mir halbwegs bekannt ist. Beide 
benötigen ein Paar p,q mittelgroßer (im Vergleich zu pq) Primzahlen. Wie 
werden diese erzeugt?

Wählt man Zufallszahlen im gewünschten Wertebereich von p und q, solange 
bis z.B. der Miller-Rabin-Test ergibt, dass sie prim sind? Kann man die 
Wahl der Zufallszahlen intelligenter gestalten als bloss z.B. gerade 
Kandidaten ohne MR-Test zu verwerfen?

Und wie findet man Zufallskandidaten für p und q? Ohne ein Paar p,q zu 
haben kann man kein BBS- oder ähnlich sicheres Verfahren anwenden, um 
eine Folge von Kandidaten zu berechnen (Henne-Ei-Problem). Braucht man 
also eine große Menge echte Zufallszahlen, bis man ein Paar p,q gefunden 
hat?

Und ist es ratsam, aus einem Schlüsselpaar (wenn also eine Henne bzw. Ei 
existiert) neue zu generieren? Schlüssel KÖNNEN mit sehr viel Rechenzeit 
geknackt werden, und dann wären alle abgeleiteten Schlüssel ebenfalls 
unsicher, nicht?

Bernd

Autor: ChristophK (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Eigentlich spielt es ja keine Rolle, was der OP mit seiner 32bit 
Zufallszahl machen wollte. Vielleicht hätten's auch 16bit getan. Er ist 
jedenfalls überwältigt, von der Kaskade von Beiträgen, die seine 
unscheinbare Frage ausgelöst hat. Eine kryptographische Anwendung steht 
jedenfalls nicht dahinter.

ChristophK wünscht schöne Weihnachten und eine besinnliche Zeit zwischen 
den Jahren.

Autor: Wolfgang (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Timer starten (Presc 1), WDT starten (auf genügend hohe Zeit stellen); 
beim Interrupt des WDTs den Timer Wert holen! WDT läuft auf einem 
eigenen Oszillator -> fertisch! Ob sie für deine Anwendung gut genug 
sind, weiß ich nicht!

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>WDT läuft auf einem eigenen Oszillator -> fertisch
Schon mal ausprobiert? Du meinst nicht, dass die Oszillatoren 
hinreichend stabil sind, dass der Timerwert immer in einem sehr engen 
Wertebereich landet? Vor allem wenn er 32 UNABHAENGIGE bits braucht.

Anderer Vorschlag: vom AVR per ethernetmodul folgenden Text an 
www.mikrocontroller.net/topic/new schicken:
Betreff "C Compiler kaputt"
Text "Ich habe meinen Compiler auf deutsche Bedienung eingestellt, aber 
dieses Programm
>int main(){printf("Hello world");}
produziert immer noch englischen Text. Was ist am Compiler kaputt?"

Erste Anwort abwarten (30-60sec) und die eingehenden Zeichen zu 4 Byte 
verknüpfen.

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wolfgang wrote:
> Timer starten (Presc 1), WDT starten (auf genügend hohe Zeit stellen);
> beim Interrupt des WDTs den Timer Wert holen! WDT läuft auf einem
> eigenen Oszillator -> fertisch! Ob sie für deine Anwendung gut genug
> sind, weiß ich nicht!

Hätt ich auch so gemacht. Zwecks "Gleichverteilung" etc:
einfach 32 mal durchführen, und jedes mal nur das LSB verwenden.

Danach kann man die 32Bit als Startwert für einen PRNG verwenden.

/Ernst

Autor: Wolfgang (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wenn du mit 8MHz unterwegs bist, dann braucht der Timer ca. 32us für 
einen Durchlauf! Wenn du den WDT auf 32ms stellst, dann sind das ca. 
1000 Durchläufe! Da es verschiedene Oszillatoren sind mit verschiedenen 
Toleranzen wie auch Temperaturabhängigkeiten, schauts so aus, als ob 
sehr brauchbare Zahlen herauskommen! Man kann das aber sicher auch noch 
verbessern, wie eben schon erwähnt nur gewisse Bits verwenden; 
aufrechnen; nur als Basis für einen PRNG verwenden, usw....

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>dann sind das ca. 1000 Durchläufe!

äh, unterbrich mich, wenn ich was falsches schreibe. Das heißt wenn die 
Oszillatoren relativ zueinander von einem Start zum nächsten um 1% 
auseinanderdriften (was sehr hoch gegriffen ist), ändert sich das 
Ergebnis um ca. 10, wohlwollend aufgerundet also 4 verwertbare Bits. Und 
dann wartest du 10min, damit du die nächsten 4 "Zufallsbits" erhältsts, 
gut macht schon einmal 8 Bits. Nun hat sich die Temperatur eingeregelt, 
beide Oszillatoren haben ein festes Frequenzverhältnis, und wo kommen 
die restlichen 24 Bits her?

Suchen ein Mikrocontrollerprogrammierer, ein reiner Mathematiker und ein 
Ingenieur eine Zufallszahl...

Autor: ChristophK (OP) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Tiny2313 hat keinen A/D-Wandler, gelle? Also brauche ich 
wahrscheinlich etwas mehr externe Bauelemente, aber es sollte doch mit 
einem Bauelement, das Rauschen produziert (Zenerdiode, Rauschdiode?)
und einer S/H-Schaltung möglich sein, Zählerwerte von 0 bis 255 zu 
produzieren. Die Werte für die drei weiteren Bytes wären statistisch 
unabhängig. Bleibt nur die Aufgabe, den Analogteil der Schaltung so zu 
gestalten, daß sich keine Häufung der S/H-Werte am Nullpunkt oder am 
Maximum bildet.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.