www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Generatorpolynome für PRNGs


Autor: ChrisV (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

über rückgekoppelte Schieberegister kann ich ja Pseudozufallszahlen 
generieren.
Wie ich das Schieberegister aufbaue sagt mir das Generatorpolynom.

Nun möchte ich beispielsweise ein PRNG aus 20 Registern aufbauen, das 
mir alle Werte durchläuft (bzw. (2^20)-1 Werte).

Die Frage ist nun, wie komme ich an die Generatorpolynome, also an den 
Aufbau der Schieberegister, die die Forderung erfüllen.

Ziel ist es nicht, eine möglichst gute Folge an Zufallszahlen zu 
bekommen, sondern eine berechenbare Folge zu bekommen, deren Geheimnis 
der Aufbau des PRNG ist.

Grüße,
Christof

Autor: Zacc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Siehe Appnote 110 oder so bei Xilinx.

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
110 ist die Polizei.

http://www.xilinx.com/support/documentation/applic...

Cheers
Detlef

Autor: Tassilo Böhr (big_t)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: ChrisV (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ha!

Perfekt. Danke für die links.

Grüße,
Christof

Autor: ChrisV (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sooo...

eine Frage hätte ich da noch an die Kryptologen bzw. Mathematiker unter 
euch.

Angenommen ich bin Eve und höre mir einen Bitstrom an.
Weiterhin habe ich die Vermutung, dass dieser von einem PRNG generiert 
wird.

Wie lange muss ich zuhören um rauszubekommen wie der PRNG aussieht, 
sprich ab wann bin ich in der Lage die Folge selber zu berechnen.

Gruß Christof

Autor: Jakob Lell (jakob)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

bei einem 20 bit Schieberegister kann man durch Brute Force mit 
vertretbaren Aufwand alle möglichen Generatorpolynome (ca. 2^20 
Möglichkeiten) mit allen möglichen Anfangszustände ( ebenfalls 2^20 
Möglichkeiten ) ausprobieren. Der Aufwand ist insgesamt etwa 2^40. Auf 
einem PC dauert das je nach Implementierung wahrscheinlich nicht mehr 
als ein paar Stunden. Durch Vergleichen mit dem abgehörten Bitstrom kann 
man überprüfen, ob das Ergebnis stimmt. Um aus den 2^40 Möglichkeiten 
mit hoher Wahrscheinlichkeit die richtige Lösung auszuwählen, muss man 
nur wenig mehr als 40 bit abhören.

Wenn du etwas mehr Sicherheit willst und 256 Byte freien Ram hast, dann 
kannst du auch RC4 verwenden. Dieser Algorithmus ist bei korrekter 
Verwendung trotz der Einfachheit immer noch relativ sicher.

Gruss
Jakob

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

Bewertung
0 lesenswert
nicht lesenswert

Autor: ChrisV (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> Wenn du etwas mehr Sicherheit willst und 256 Byte freien Ram hast, dann
>> kannst du auch RC4 verwenden. Dieser Algorithmus ist bei korrekter
>> Verwendung trotz der Einfachheit immer noch relativ sicher.

Stimmt. Das wäre auch eine Möglichkeit. Ist die generierte Zufallsfolge 
bei RC4 denn zyklisch?

Hat für mich den Nachteil, dass ich dann noch eine Schlüsselaushandlung 
implementieren müsste. Das wird vermutlich zu viel Aufwand für meinen 
Zweck.

Auf jeden Fall danke für den Tip.

Gruß Chris

Autor: Zacc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Aufwand steigt schnell an. Ich hab hier eine LFSR mit 32bit am 
Testen.
Eine Erweiterung auf 40, oder 48 bit waere schnell moeglich. Man muss 
sich fragen ob sich Leute mit Geheimdienst-Wissen, -Ausruestung (und 
-Vorgaben) mit einem Bootloader oder sonst einer embedded Uebertragung 
herumschlagen.

Autor: Jakob Lell (jakob)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

RC4 ist wie jeder andere PRNG natürlich zyklisch. Allerdings ist die 
Länge eines Zykluses so gross, dass man in der Praxis niemals einen 
kompletten Zyklus durchlaufen kann. Mit Schieberegistern grösserer Länge 
kann man den Aufwand für einen Brute-Force-Angriff natürlich enorm 
steigen. Allerdings ist Brute-Force bei so etwas nicht unbedingt der 
effektivste Angriff.

Gruss
Jakob

Autor: ChrisV (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> Allerdings ist Brute-Force bei so etwas
>> nicht unbedingt der effektivste Angriff.

Sind denn (dir) da andere Angriffsmöglichkeiten bekannt?

Autor: Zacc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sehr effektiv ist der Differentialangriff, wenn man den denn machen 
kann. Der Beruht darauf, dann der angreifer, die zu verschluesselnden 
Daten aendern kann. Dann kann man untersuchen, welche Aenderung am 
Eingang zu welcher Aenderung am Ausgang fuehrt.
Sehr effektiv ist die Korrelation, dh den Vergleich mit Erwartetem. Wenn 
ich zB weiss, dass ein Brief immer mit 'Sehr geehrter ..' beginnt, oder 
dass ein Bootloader zuerst die Interrupt tabelle mit Jumps enthaelt, so 
schraenkt das den Coderaum stark ein.
Gibt noch weitere Methoden, je nach Randbedingungen.

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.