mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Zufallszahl in Assembler?


Autor: Takashi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich möchte eine Zufallszahl in Assembler erzeugen.
Ist sowas überhaupt möglich?

Danke im Vorraus

Autor: Olaf Kindel (olaf_k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"Echte" Zufallszahlen kann man z.B. durch ADC-Messung von
Rauschquellen erzeugen.

I.d.R. verwendet man aber Pseudozufallszahl-Generatoren (PNG) und
erzeugt nur die seed über echten Zufall (z.B. Messung der Zeit zwischen
mehreren Tastendrücken).
Ein gebräuchliches und auf µC gut implementierbares Verfahren sind LFSR
(Linear Feedback Shift Register).
PNG haben gegenüber echtem Zufall mehrere Vorteile: Sie sind effizient
zu programmieren, die Algorithmen sind wohluntersucht und erzeugen
statistisch nahezu ideal verteile Werte, und die Reproduzierbarkeit
(d.h. Verwendung der gleichen seed in mehreren Programmläufen) kann das
Debugging sehr erleichtern.

MfG Olaf

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

Bewertung
0 lesenswert
nicht lesenswert
Hallo Olaf,
Ein gebräuchliches und auf µC gut implementierbares Verfahren sind
LFSR
(Linear Feedback Shift Register).
PNG haben gegenüber echtem Zufall mehrere Vorteile: Sie sind effizient
zu programmieren, die Algorithmen sind wohluntersucht und erzeugen
statistisch nahezu ideal verteile Werte, und die Reproduzierbarkeit
(d.h. Verwendung der gleichen seed in mehreren Programmläufen) kann
das
Debugging sehr erleichtern.

Zu beachten ist aber, dass sie per Prinzip deterministisch sind und man
trotzdem einen zufälligen Startwert braucht. Sonst erhält man nach einem
Neustart immer die exakt gleichen "Zufallszahlenfolgen".

Jörg

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Manchmal will man genau das. Dann ist es ein Vorteil, daß sowas geht.

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Diese RNGs sind immer für uns von Vorteil gegenüber einem echten HW
RNG.

Denn beweise mir mathm. das der Output von zb. 1024 Nullen eines Dioden
Rauschens wirklich echter Zufall war.

D.h. wenn wir 2 RNGs haben, einmal ein Pseudo-RNG basierend auf einem
LFSR und damit per mathematischen Formeln exakt beweisebar und
reproduzierbar. Dieser wird verglichen mit einem echten HW-RNG wie dem
Rauschen einer Diode.

Nun produzieren wir durch "Zufall" zb. exakt 1024 mal hintereinander
mit beiden RNG immer nur die Zahl 0.

Gut, bei 1024 Bits ist die Wahrscheinlichkeit das man 1024 0'en
erzeugt mit 1 zu 2^1024 durchaus eine gültige aber sehr
unwahrscheinliche Sequenz von Bits.

Allerdings könnte man nun annehmen das lauter 0'Bits bei einer Diode
anzeigt das diese physikalisch nicht mehr funktioniert.

Da wir aber aus Sicht unserer Bits nur diese kennen und die Diode nicht
direkt prüfen können müssen wir annehmen das diese nicht defekt ist,
denn selbst Millionen von 0 Bits, also das ständige Low-Signal einer
Diode ist ein wahrscheinliches Resultat das zufällig sein könnte, denn
selbst unendlich viele 0'bits wären eine gültige Lösung als Sequenz
die per zufall erzeugt werden kann. Zwar ist es so das die
Wahrscheinlichkeit mit jedem erzeugten Bit weiter gegen unendlich klein
tendiert, aber sie wir eben niemals ganz gegen Null tendieren können.
So..., bei einem Pseudo-RNG nehmen wir den Startwert, und unser Freund
nimmt diesen auf seiner CPU implementation des gleichen Pseudo-RNGs und
wenn alles korekt war wird er die exakt gleiche Sequenz von Nullen
erzeugen wie unserer RNG. Dh. erst durch diese Reproduzierbarkeit
können wir nicht nur metaphysisch==imateriell=philosophisch
mathematisch, sondern ganz praktisch und technologisch beweisen das
unser RNG mit einem spez. Startwert unsere Sequenz aus 1024 Nullen
erzeugen muß.

Das heist: jeder mathem. Pseudo-Zufalls-Generator ist in seiner
Beweisbarkeit für uns Menschen jedem RNG, der auf "echten" externen
aber niemals beweisbaren Phenomänen basiert, vorzuziehen.

Die Fragestellung ob man beweisen kann das ein RNG wirklich
"zufällig" ist hängt also nur davon ab ob wir den einmal erzeugten
Zufallsstrom jeder Zeit reproduzieren können. Da wir bei echten RNGs
dies eben nicht können können wir auch nicht praktisch beweisen ob
dieser Zufall auch wirklich Zufällig ist.

Ergo: immer einen beweisbaren Pseudo-RNG benutzen und wenn dann nur den
Startwert dieses RNGs entsprechend zufällig initialisieren, ist aber aus
statistischer Sicht eigentlich nicht notwendig.

Die Zufälligkeit solcher PRNGs definiert sich nun aus der Komplexität
der math. Formel und die verwendete Datengröße. Würde man zb. einen
Quadratischen Reste Generator benutzen (Blum Blum Shub Generator) mit
entsprechend großen Paramatern > 1024 Bits, und wir erzeugen mit einem
Seed eine Sequenz von 1024 Bits dann ist:

1.) für uns dieser Zufallsstrom jederzeit deterministisch und
reproduzierbar da WIR den Startwert kennen

2.) für andere Personen die NICHT den Startwert kennen ist die
Komplexität derart hoch das er defato niemals in der Lage sein kann den
Zufallsstrom vorhersagen zu können. Unser Pseudo-RNG verhält sich damit
aus Sicht dieser Person wie ein echter Zufallsgenerator, für uns ist er
somit beweisbar sicher.

Es gibt also keine hinreichende Begründung keine Pseudo-RNGs benutzen
zu wollen und sich auf unbeweisbare physikalische Phenomäne zu
verlassen wie bei einer Diode.

Gruß Hagen

Autor: Pete Nerlinger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hagen, das ist mir zuviel Text.Kannst das nochmal in 1-2 Sätzen für mich
zusammenfassen?
Dankeschön schonma!

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn man die Wahl hat zwischen

- Pseudo RNGs basierend auf einer math. bewiesenen Formel, oder
- einem beliebigen Hardware RNG basierend auf physikalischen
Eigenschaften

dann ist es per logik beweisbar das man immer einen Pseudo RNG benutzen
sollte. Dies trifft auf die Anwendung in der Statistik, Mathematik und
auch Kryptographie zu.

Und warum?

Einfach weil man einen Hardware RNG niemals als 100%'tig korrekt
beweisen kann da man deren Zufallsoutput nicht reproduzieren kann. Das
ist aber eine wichtige Grundbedingung um zb. Fehler in Software oder
Hardware erkennen zu können.

Um math. die Korrekheit eines solchen HW RNGs beweisen zu können
benötigen wir 2 Dinge:
a) die Formel mit der dieser RNG arbeitet
b) alle Startparameter die der RNG benutzt

Kennen wir diese Formel und den Startwert dann degradiert dieser HW-RNG
defakto zu einem Pseudo-RNG, wir kennen ja bei beiden die Formeln und
Paramter, es existiert dann kein Unterschied mehr.

Kennen wir diese Formeln aber nicht so können wir auch niemals mit
Sicherheit beweisen/wissen das dieser HW-RNG auch wirklich zufällig
ist.

Der Große Unterschied des HW-RNG besteht eben darin das man sich auf
physikalische Annahmen stützt. Das ist ein grundsätzlicher Fehler im
Konzept. Denn defakto können wir nicht beeisen ob unser System in dem
wir leben auch wirklich so funktioniert wie wir es annehmen.

HW-RNGs basieren also nur auf Annahmen, SW-RNGs basieren ausschließlich
auf Mathematik und die kümmert sich einen Schit um unsere Realität. In
der Mathemtik existieren nur Axiome/Behauptungen und davon strikt
logisch abgeleitete Erkenntnisse. So lange das postulierte System der
Axiome gültig ist so lange können wir die Eigenschaften eines SW-RNGs
auch beweisen.


Gruß Hagen

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> dann ist es per logik beweisbar das man immer einen Pseudo RNG
> benutzen sollte. Dies trifft auf die Anwendung in der Statistik,
> Mathematik und auch Kryptographie zu.

Gerade in der Kryptographie setzt man aber lieber richtige
Zufallszahlen ein. Einigermaßen moderne PCs haben einen
Hardware-Zufallsgenerator, der dafür zuständig ist und bevorzugt dafür
eingesetzt wrid. Warum?

> da man deren Zufallsoutput nicht reproduzieren kann.

und genau das soll man auch nicht können, denn das wäre ein möglicher
Angriffspunkt zum Knacken der Verschlüsselung.

Autor: mr.chip (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Hagen: Ist es nicht vielleicht etwas gar philosophisch, was du
schreibst? Klar hast du grunsätzlich Recht, aber in der Praxis sollte
man einen HW-RNG doch so eingehend testen können, dass man danach seine
Eigenschaften ähnlich gut kennt, wie die eines SW-RNG. Wenn man mehrere
Millionen Zufallszahlen würfelt, und die den geforderten Bedingungen
entsprechen, dann sehe ich keinen Grund, warum man dem HW-RNG nicht
vertrauen soll, nur weil man ihn nicht vollständig versteht.

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vieleicht oder auch nicht. Ich vertrete hier nur meine Sichtweise der
Dinge und das dann vorrangig als Kryptograph.

Ich meine aber das es eine ganz praktisch und eben dogmatische
Sichtweise ist.

Man kann zwar bei einem HW-RNG dessen statistische Egenschaften
analysieren und dann postulieren -> ist Zufall. Aber das könnte ich
auch von einer 1 Gb großen und gepackten Datei behaupten -> statisch
ist es Zufall.

Bei einem PRNG kenne ich aber alle Fakten, ich kenne die Formel, ich
kenne die Komplexität des Verfahrens und damit dessen
Sicherheitsschranken und ich kenne für Reproduktions-zwecke auch den
Startwert.

Wenn alles stimmig ist dann ist
1.) das Verfahren math. beweisbar korrekt
2.) die Komplexität des Verfahrens math. beweisbar
3.) die Komplexität so hoch gewählt das man math. ausrechnen kann wie
sicher das Verfahren in der Anwendung sein wird, auch für die Zukunft

und als letzten Punkt eben

4.) durch das Geheimhalten der Startwerte haben wir nun eine Funktion
die entweder berechnebar ist oder aber nicht berechnbar sein kann. UNd
derjenige der das Geheimnis=Sartwert kennt der kontrolliert die
Verteilung und den Zugriff auf diese Daten. Und dies ist ja das Ziel
der Kryptographie -> Kontrolle durch Wissen oder Unwissen.

Es gibt aber auch ganz praktische Unterschiede:

Ein HW-RNG basierend auf zb. dem LSB eines ADCs. Wir werden niemals in
der Lage sein beweisen zu können ob dieser Zufallsstrom nun eine
Eigenschaft der EMV Strahlung oder Wärmestrahlung zu einem Zeitpunkt an
einem Ort sein kann, oder ob es nur Eigenrauschen auf Grund der
verwendeten technolgischen Struktren darstellt. All diese 3 Einflüsse
könnten für sich genommen statist zufällig wirken sind es aber defakto
nicht. Bewegen wir unser Board/Hardwrae an einen andern Ort zu einem
anderen Zeitpunkt dan wird er wenn er zb. auf EMV reagiert auch anderen
Zufall erzeugen. Ergo: in diesem Falle haben wir also keinen echten
Zufall mehr.

Aber bei einem PseudoRNG der ja als Formel in eine Software
impleemntiert wird können wir diesen auf ganz unterschiedlichen
Technologien integrieren. Mit gleichem Startwert unabhängig von Raum
und Zeit MUSS immer der gleiche Zufall erzeugt werden. Wir können als
bei PRNGs

1.) die Formel == ergo das Wissen was drinnensteckt
2.) den Ouput==Zufallsstrom weil gleicher Startwert
3.) unabhängig von Raum und Zeit
4.) unabhängig von der verwendeten Technologie=Hardware

das Ding reproduzieren und erlangen damit beweisbare
Veefahrenssicherheit.

Um einen RNG einschätzen/beweisen zu können reicht es eben nicht nur
eine statistische Analyse anzuführen.

Man muß sich das mal vorstellen. Wir konstruieren ein kryptographisches
System und beweisen das es sicher sein wird. Die einzigste Schwachstelle
sind also schlechte Passwörter oder notwendige
 Zufallsdaten. Und exakt an dieser Stelle bauen wir Technologie ein bei
der wir eben nicht wissen ob sie tatsächlich an jedem Ort und zu jeder
Zeit immer korrekt arbeiten wird.

Gut, das ich hier OT immer die Kryptograhie herranziehe hat einen
einfachen Grund. Es ist die einzisgte Wissenschaft die sich eben exatkt
mit solchen Dingen tiefgründiger auseinandersetzt. Sie ist sogar fast
die einzigste Wissenschaft der Mathematik die sich überhaupt mit
praktisch anwendbaren Dingen befasst und dabei aber rein ist, dh.
keinerlei physikalische Phenomäne berücksichtigen MUSS.

Gruß Hagen

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gut zurück zum Thema, denn praktisch gesehen heist dies:

Möchtest du von Anfang an sicher stellen das du guten Zufall erzeugst
oder willst du dich auf physikalische Eigenheiten einer Hardware
verlassen müssen. Der Aufwand wäre einerseits eine simples Stückchen
Software oder eben zb. eine Diode und ein ADC mit ihren in unserem
Bereich notwendigen Eigenrauschen.

Das erste ist unabhängig vom AVR und Diode immer reproduzierbar und
funktionabel, beim zweiten hängt es vom Produktionsprozess der
Technologie ab und wo/wann wir das Board dann einsetzen.

Ich meine: nimm einen Software-RNG dann weist du das es funktionen muß
und ersparst dir Ärger.

Gruß Hagen

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
""
> da man deren Zufallsoutput nicht reproduzieren kann.

und genau das soll man auch nicht können, denn das wäre ein möglicher
Angriffspunkt zum Knacken der Verschlüsselung.
""

Falsch, absolut falsch. Denn was wissen wir dann ? Wir wissen das wir
eben nicht wissen was da abläuft und somit existiert ein möglicher
Angriffspunkt in unserem Design. Das ist in der Kryptographie fatal
denn die Sicherheit in der Kryptographie basiert ausschließlich nur
darauf das wir WISSEN.

Ein möglicher Angriffspunkt in der Kryptographie zeichnet sich immer
dadurch aus das wir weniger Wissen besitzen als der Angreifer !! Also
müssen wir jeden Schritt beweisen können und das führt dazu das dieser
Beweis auch für einen Angreifer gültig ist. Können wir dies und setzen
die Schranken der Komplexität so enorm hoch dann kann auch ein
Angreifer mit gleichem Wissen nichts knacken. Wir können es ihm sogar
beweisen das es so sein wird.

Man muß es mal so betrachten: es geht darum mit hilfe der Mathematik
exakt beweisen zu können das ein Angeifer nicht die geringste Chance
haben kann an unsere Daten zu kommen. Um das beweisen zu können müssen
wir uns in unseren Technologien auf die Teilmenge beschränken die wir
absolut exakt verstehen und beweisen können. Das ist bei einem HW.RNG
eben nicht der Fall.

Gruß Hagen

Autor: Dominic R. (dominic)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ohne deinen ganzen Text gelesen zu haben (heb ich mir für's WE auf)
bleibt als Frage, wo der Startwert herkommt. Denn wie du ja so schön
erklärt hast, ist es mit Kenntnis des Startwertes möglich, die
komplette Folge zu berechnen (bei manchen Algorithmen sogar bestimmte
Elemente der Folge, ohne die vorhergehenden berechnen zu müssen). Also
muss ein zufälliger Startwert her -> nehmen wir nun hier einen P-RNG
oder einen HW-RNG?

Gruss,

Dominic

Autor: Läubi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Wahrscheinlichkeit bei einer (Normalverteilten) Zufallszahl 1024x
eine 0 zu erhalten ist bestimmt geringer als die Wahrscheinlichkeit das
ein Hardwaredefekt vorliegt.
Und wenn man nun nicht gerade staatsgeheimnisse verschlüsseln möchte
sondern vieleicht einfach nur "zufällig" ein neues Lied bei einem MP3
Player wählen will ist das doch in Ordnung.
Der Landläufige "Zufall" dekt sich eh nicht mit dem was man unter
Wahrscheinlichkeittheoretischen aspekten dadrunter versteht.

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
bei entsprechener Komplexität des RNGs ist das wurscht ;) Wichtig ist
nur das der Startwert geheim bleibt. Der Startwert ist ja nur wichtig
um eine andere Folge von Zufall zu erzeugen.

Ich mache es am liebsten so das ich eine Serialnummer und ein Startwert
Register benutze. Beim Powerup der CPU nehme ich beides und füttere
damit den RNG. Der RNG produziert nun ein par Bytes die so groß sind
wie das Startwert Register. Diese Bytes speichere ich dann als neuen
Startwert im Register. Die Serialnummer ist hardcoded im FLASH und das
Startwert Register das sich ja bei jedem Powerup verändert speichere
ich im EEPROM. Um sicher zu gehen das sich keine wiederholenden Folgen
von Startwerten einstellen besteht ein Teil dieses Startwert Register
aus einem Zähler. Bei jedem Powerup wird dieser Zähler um +1
inkrementiert. Formal entsteht sowas wie eine Hashfunktion aus der
Kryptographie bekannt. Zb. in Verfahren wie die KDF -> Key Derivation
Functions oder MGFs -> Mask Genration Function.

Gruß Hagen

Autor: Dominic R. (dominic)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tut mir echt leid, aber genau da beisst sich die Katze in den eigenen
Schwanz. Da dein Angreifer ja prinzipiell alles wissen könnte, was du
weisst, kann er auch deine Seriennummer und den Startwert wissen.
Kryptographische Verfahren beruhen aber eben genau darauf, dass Zufall
eine nicht-deterministische Komponente einführt. Da vollkommen
zufällige Systeme aufgrund physikalischer Randbedingungen nicht
realisierbar sind, beschränkt man sich auf beherrschbare Systeme ->
bekannte HW-RNG Systeme

Ob da nun ein Zwinkern ist oder nicht, die Kompexität des RNG spielt
beim Zufall keine Rolle, und "ernst" gemeint war meine Frage auch nie
;)

Autor: Florian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Um das Problem Takashi noch mal aufzugreifen und Olaf Kindels Antwort
auszuführen:
Wenn dein µC einen A/D-Wandler hat, dann hol' einfach ein paar analoge
"Meßwerte" von einem unbeschalteten Pin ab. An den offenen Pins tritt
genügend Rauschen auf, um zufällig zu sein. Das ist besser, als jedes
komplizierte mathematische Verfahren, da es echter Zufall ist.

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.