Generatorpolynome für PRNGs

Gast #751729 
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
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Langsamer Modus Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Melden Danke
Gast 
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
Antwort Zitieren Bearbeiten Löschen Melden Danke 
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
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
>> 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
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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.
Antwort Zitieren Bearbeiten Löschen Melden Danke 
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
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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 Zitieren Bearbeiten Löschen Melden Danke
Thread beobachten

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 18 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.