Forum: FPGA, VHDL & Co. Pseudenzufallsgenerator mittels VHDL


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Aid (Gast)


Angehängte Dateien:

Lesenswert?

Ich möchte pseudenzufallsgenerator mittels VHDL entwerfen.

irreduzibles Polynom: x^6 + x^5 + x^3 + x^2 + 1 (1101101)

Aber irgendwie scheint es falsch zu sein. Was ist denn falsch?

VHDL-CODE:

entity pseudenzufallsgenerator is
  port( TAKT    : in bit;
        EINGANG : in bit );
      end pseudenzufallsgenerator;

architecture arch of pseudenzufallsgenerator is
  signal Z       : bit;
  signal D       : bit_vector(5 downto 0);
  begin

    FF: process(TAKT)
    begin

    if TAKT'event and TAKT='0' then

    Z <= D(5);
    D(5) <= D(4) xor Z;
    D(4) <= D(3);
    D(3) <= D(2) xor Z;
    D(2) <= D(1) xor Z;
    D(1) <= D(0);
    D(0) <= EINGANG xor Z;

    end if;

  end process FF;

    end arch;

von Der Besucher (Gast)


Lesenswert?

Probiere es mal mit Z als Variable und die Zuweisung von Z auch etwas 
modifiziert (jedenfalls wird das so bei einem CRC gemacht):

 Z := EINGANG xor Z;
    D(5) <= D(4) xor Z;
    D(4) <= D(3);
    D(3) <= D(2) xor Z;
    D(2) <= D(1) xor Z;
    D(1) <= D(0);
    D(0) <= Z;

Der Besucher

von Noch ein B-sucher (Gast)


Lesenswert?

Du verwendest in Deinem Code Z nicht simultan, obwohl die Gleichung es 
fordert. Entweder Du baust das in einem Takt oder Du klopfst Z in eine 
pipeline. Du kannst auch die Suche bemühen und den Zufallsgenerator 
nehmen:

http://www.mikrocontroller.net/articles/Digitaler_Zufallszahlengenerator_in_VHDL

von Fetz (Gast)


Lesenswert?

Oder er verwendet Variable statt Signal in den Prozessen. Dann ändert 
sich das <= zu := und die Zuweisungen können gleich in der nächsten 
Code-Zeile gleich wieder zurückgelesen werden.

von Fetz (Gast)


Lesenswert?

Quasi:
1
  begin
2
3
    FF: process(TAKT)
4
      variable Z       : bit;
5
      variable D       : bit_vector(5 downto 0);
6
    begin
7
8
    if TAKT'event and TAKT='0' then
9
10
    Z := D(5);
11
    D(5) := D(4) xor Z;
12
    D(4) := D(3);
13
    D(3) := D(2) xor Z;
14
    D(2) := D(1) xor Z;
15
    D(1) := D(0);
16
    D(0) := EINGANG xor Z;
17
18
    OUTPUT <= D; 
19
20
    end if;
21
22
  end process FF;

von Duke Scarring (Gast)


Lesenswert?

Fetz schrieb:
> FF: process(TAKT)
>       variable Z       : bit;
>       variable D       : bit_vector(5 downto 0);
>     begin
>
>     if TAKT'event and TAKT='0' then
Wie alt ist denn das Buch, aus dem Du diesen Code hast?

Prinzipiell sind die Typen bit und bit_vector nicht falsch, aber 
alle Welt verwendet std_logic und std_logic_vector. Damit lassen 
sich undefinierte Signale, Tri-States (für externe Pins) und 
"Kurzschlüsse" (zwei Quellen treiben geleichzeitig verschiedene Werte) 
simulieren.

Und für den Takt kannst Du viel lesbarer
1
if falling_edge(TAKT) then
hinschreiben. (Warum auch immer Du die fallende Flanke verwendest...)

Duke

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Fetz schrieb:
> Oder er verwendet Variable statt Signal in den Prozessen. Dann ändert
> sich das <= zu := und die Zuweisungen können gleich in der nächsten
> Code-Zeile gleich wieder zurückgelesen werden.
Mit unzähligen anderen Nebeneffekten, die so ein Anfänger dann mit 
Variablen (insbesondere mit speichernden Variablen) sofort an der Backe 
hat....
Der Klassiker zum Thema: Beitrag "Variable vs Signal"

> Ich möchte pseudenzufallsgenerator mittels VHDL entwerfen.
> irreduzibles Polynom: x^6 + x^5 + x^3 + x^2 + 1 (1101101)
Sieh dir mal meine Implementation eines LFSR an:
http://www.lothar-miller.de/s9y/categories/38-LFSR

Aid schrieb:
> Ich möchte pseudenzufallsgenerator mittels VHDL entwerfen.
> Aber irgendwie scheint es falsch zu sein. Was ist denn falsch?
Die Richtung, in der deine XOR wirken...

von aid (Gast)


Angehängte Dateien:

Lesenswert?

Warum kommt das Eingangssignal eine Taktperiode verspätet?

von aid (Gast)


Angehängte Dateien:

Lesenswert?

Warum kommt das Eingangssignal eine Taktperiode verspätet?

von Duke Scarring (Gast)


Lesenswert?

aid schrieb:
> Warum kommt das Eingangssignal eine Taktperiode verspätet?
Es gibt ein Leben vor der Taktflanke und eins danach:
1
  process
2
  begin
3
    if TAKT'event and TAKT='0' then -- Flanke
4
      danach <= davor; -- Leben
5
      Z      <= D(5);
6
      D(5)   <= D(4) xor Z;
7
      D(4)   <= D(3);
8
      D(3)   <= D(2) xor Z;
9
      D(2)   <= D(1) xor Z;
10
      D(1)   <= D(0);
11
      D(0)   <= EINGANG xor Z;
12
    end if;
13
  end process;

Duke

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Duke Scarring schrieb:
> Es gibt ein Leben vor der Taktflanke und eins danach:
Mein Motto ist: Nach dem Takt ist vor dem Takt...  ;-)

aid schrieb:
> Warum kommt das Eingangssignal eine Taktperiode verspätet?
Das kommt doch genau rechtzeitig, denn du schreibst doch selber:
1
    if TAKT'event and TAKT='0' then -- bei einer fallenden Flanke:
2
      D(0)   <= EINGANG;            -- übernehme das was jetzt gerade am Eingang anliegt nach D(0)
3
    end if;
Alles, was mit einem Takt beschrieben ist, ergibt ein Flipflop. Und 
dieses Flipflop übernimmt eben durch die passende Taktflanke die Daten 
am Eingang und speichert sie. Diese Denkweise mußt du dir 
verinnerlichen, sonst klemmts bald wieder...


Noch'n Tipp: such mal nach "Latency".

von aid (Gast)


Angehängte Dateien:

Lesenswert?

Ich möchte das Eingangssignal und das erste flip flop ergebnis 
gleichzeitig auftreten. (Siehe Timing Simulation). Geht das?

Flip Flop process:

    FF: process(TAKT)
      variable Z       : bit;
      variable D       : bit_vector(5 downto 0);
    begin

    if TAKT'event and TAKT='0' then

    Z := D(5);
    D(5) := D(4) xor Z;
    D(4) := D(3);
    D(3) := D(2) xor Z;
    D(2) := D(1) xor Z;
    D(1) := D(0);
    D(0) := EINGANG xor Z;

    OUTPUT <= D;

    end if;

  end process FF;

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

aid schrieb:
> Siehe Timing Simulation
Ist das nicht eine ordinäre Verhaltenssimulation?

> Ich möchte das Eingangssignal und das erste flip flop ergebnis
> gleichzeitig auftreten. (Siehe Timing Simulation).
Nein. Das kann nicht gehen, denn ein Flipflop wird die Daten erst mit 
der nächsten aktiven Tkatflanke übernommen werden.

> Geht das?
Wozu?

von Duke Scarring (Gast)


Lesenswert?

aid schrieb:
> Geht das?
Klar.

Ungefähr so:
1
D(-1) <= EINGANG;

Duke

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Duke Scarring schrieb:
> Ungefähr so:
Da bin ich aber mal gespannt... ;-)

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

:-) :-)

von Peter Eiching (Gast)


Lesenswert?

http://www.hs-merseburg.de/~8ckaehle/dateien/ind_BA/Bericht_Ind.pdf

da findest du verschiedene Generatoren. Erschreckend, wie viele Leute 
das in letzter Zeit machen. ;-)

von Weltbester FPGA-Pongo (Gast)


Lesenswert?

Irgendwas müssen sie ja machen :-)

Pseudozufallsgeneratoren gibt es wie Sand am Meer. Entscheidend ist, ob 
sie sich für FPGAs eigenen. Das ist nicht immer der Fall. Denn da da 
gibt es ja noch ein Kostenthema. Warum soll man einen FPGA verschwenden, 
um Pseudozufall zu bekommen? Entweder richtiger Zufall oder richtige 
generische Werte. Für das eine nimmt man Analoges für das andere einen 
einfachen Algorithmus, den man kostengünstig in VHDL giessen kann. Da 
nimmst Du einfach ein 256 Bit SR und irgendeinen der bekannten 
Verschlüsselungscodes, wenn die Gegenstelle es als 
Entschluesselungs-Code braucht, oder irgendeinen selbst ausgedachten, 
den man nicht erraten können soll.

Das Allerbeste ist, sein Geräte mit einer 128 Bit Verschlüsselung zu 
bewerben und eine 256er einzusetzen. Dann können die Chinesen lang raten 
und Codes knacken.

von Peter Eiching (Gast)


Lesenswert?

wenn man einfach nur Pseudozufallszahlen benötigt, dann ist doch ein 
LFSR das einfachste. Mit genügend großer Bitbreite des SR wirds dann 
schon schwierig die Periode zu finden... Wir haben das an der Uni 
Magdeburg aus Spaß mal mit dem Bericht von der Hochschule Merseburg 
nachvollzogen. Bei mehr als 31 Bit wirds dann schon richtig schön 
(pseudo)zufällig mit ausreichend langer Periode...

von FPGA-Expert (Gast)


Lesenswert?

Was ist denn "schön zufälig" in Zahlen?

Repetitionsrate?
Wiederholwahrscheinlichkeit zweier gleicher Werte?
Rauschspektrum?

Gibt es da Ergebnisse?

> Wir haben das an der Uni Magdeburg aus Spaß
seriöse Wissenschaft?

von Peter Eiching (Gast)


Lesenswert?

aus Spaß bedeutet, dass das nur mal kurz nachvollzogen wurde. Natürlich 
keine ernsthafte Wissenschaft mit Bericht usw.

von Peter Eiching (Gast)


Lesenswert?

PS.:

FPGA-Expert schrieb im Beitrag #2513432:
> Repetitionsrate?
> Wiederholwahrscheinlichkeit zweier gleicher Werte?
> Rauschspektrum?

dafür musst du einfach nur den Bericht lesen... Vielleicht bringt es dir 
auch etwas mit dem Autor in Kontakt zu treten...

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Zwischenfrage zum Nachdenken: Wozu braucht ein Pseudozufallsgenerator 
überhaupt einen so lange Wiederholungsrate?

Das Einsatzgebiet ist doch das der Encryption etc, da ist es nur 
bedeutend, dass man den Code nicht erraten kann.

von Lattice User (Gast)


Lesenswert?

J. S. schrieb:
> Zwischenfrage zum Nachdenken: Wozu braucht ein Pseudozufallsgenerator
> überhaupt einen so lange Wiederholungsrate?
>
> Das Einsatzgebiet ist doch das der Encryption etc, da ist es nur
> bedeutend, dass man den Code nicht erraten kann.

Wenn der Code durch ein LFSR erzeugt wird, ist er leicht zu erraten, je 
kürzer das LFSR desto schneller. Ein 16 bit LFSR hat ja maximal nur 
65535 Zustände, d.h. der Angreifer braucht auch nur 65535 Möglichkeiten 
durchzuprobieren, da reicht auch ein PC aus der Gründerzeit.

von Hagen R. (hagen)


Lesenswert?

Lattice User schrieb:
> J. S. schrieb:
>> Zwischenfrage zum Nachdenken: Wozu braucht ein Pseudozufallsgenerator
>> überhaupt einen so lange Wiederholungsrate?
>>
>> Das Einsatzgebiet ist doch das der Encryption etc, da ist es nur
>> bedeutend, dass man den Code nicht erraten kann.
>
> Wenn der Code durch ein LFSR erzeugt wird, ist er leicht zu erraten, je
> kürzer das LFSR desto schneller. Ein 16 bit LFSR hat ja maximal nur
> 65535 Zustände, d.h. der Angreifer braucht auch nur 65535 Möglichkeiten
> durchzuprobieren, da reicht auch ein PC aus der Gründerzeit.

Nichts wird bei LFSR durchprobiert. Mit 
http://en.wikipedia.org/wiki/Berlekamp-Massey_algorithm kann man aus den 
65535 Zuständen mit 100% Sicherheit das Polynom ermitteln. Das ist der 
Grund warum man LFSRs nicht in der Kryptographie benutzen sollte, wenn 
es sich vermeiden lässt.

Gruß Hagen

von Peter Eiching (Gast)


Lesenswert?

für die Kryptogr. gibt es deutlich "sicherere" Methoden. Das LFSR eignet 
sich zum Beispiel zur Erzeugung eines "zufälligen" Testsignals zum Test 
eines Nachrichtenkanals o.ä.

von B. (Gast)


Lesenswert?

Peter Eiching schrieb:
> zur Erzeugung eines "zufälligen" Testsignals zum Test
> eines Nachrichtenkanals o.ä.
Wieso braucht man ein "zufälliges" Signal? Beim Testen habe ich doch 
eine Strategie im Sinn. Analogverarbeioter z.b. sweept man einmal 
komplett durch. Digitalverarbeiter sollen bestimmte Genauigkeiten 
erzielen. Da brauche ich definierte Wertemengen.

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Lattice User schrieb:
> Wenn der Code durch ein LFSR erzeugt wird, ist er leicht zu erraten, je
>
> kürzer das LFSR desto schneller.
schon klar. ich wollte aber eigentlich mehr auf das andere Thema 
Rauschen hinaus. Zum Thema EnCodieren:

>den 65535 Zuständen mit 100% Sicherheit das Polynom ermitteln.
sofern es konstant bleibt, was ja nicht der Fall sein muss.

Man überträgt einfach willkürlich zwsischen den Daten per Steuercodes 
neue Polynomwerte, aktiviert sie mit einem Steuerzeichen und hat sofort 
eine neu Codierung, deren Werte in keinem Bezug zu den vorangegangenen 
stehen. Die Triggerung der Coderung erfolgt durch einen 
Zufallsgenerator.

Das kann man so ohne Weiteres nicht entschlüsseln!

Man kann gfs noch den "Bruch" in den codierten Daten sehen, hat aber zu 
kurze Sequenzen, um sie zum Dekodieren zu nutzen. Wie und in welcher 
Weise die Polynomwerte manipuliert werden, kann man auch nur erahnen, 
weil man nicht weiss, welche Werte vorher dafür verantwortlich sein 
müssen und dies codiert sind.

von Hagen R. (hagen)


Lesenswert?

wenn Du meinst ist das so ;)

von Lattice User (Gast)


Lesenswert?

J. S. schrieb:
>....

Das sind dann genau die hausgemachten Verschlüsselungsverfahren über die 
sich die Kryptologen lustig machen. Egal was du machst, ohne eine 
ausgiebige Kryptoanalyse kannst du gar nichts über die Sicherheit 
aussagen.

Es gibt genüg Beispiele von solchen Flops, (Mifar, CSA (DvD), ... )

von Hagen Franz (Gast)


Lesenswert?

jetzt gehts an Eingemachte... Definieren sie "sicher"...

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Hagen Franz schrieb:
> Definieren sie "sicher"...
Rente = sicher

von Hagen R. (hagen)


Lesenswert?

Das Problem ist doch folgendes:

Statt die kryprographische Sicherheit des einen LFSRs mathematisch 
sicherer zu machen benutzt er trotzig LFSRs und erhöht ausschließlich 
nur die Komplexität des mathm. Beweises indem er die Verwendung der 
LFSRs verkompliziert. Er führt in seine Beweis-Formel neue Variablen ein 
die er nun ebenfalls in seinem Beweis berücksichtigen muß. Diese 
Vorgehensweise entspricht "Security trough Obscurity" und nicht der 
eines Kryptographen.

Wenn man beweisen kann das ein LFSRs kryprographisch unsicher ist, das 
ein Wolkenkratzer gebaut auf Sandsteinen im Fundament nicht 
funktionieren kann, dann gibt es nur eine richtige Entscheidung: 
Verzicht auf Sandsteine im Fundament, Verzicht auf LFSRs.

Kryptrographie ist das exakte Gegenteil von "sich die Umwelt schön 
reden".

Gruß Hagen

von Hagen R. (hagen)


Lesenswert?

Hagen Franz schrieb:
> jetzt gehts an Eingemachte... Definieren sie "sicher"...

kryptographisch heist dies:

Liefern Sie einen mahtematischen Beweis das die minimale Komplexität 
eines Verfahrens mit bekannten Mitteln brechen zu können so hoch ist das 
dem Angreifer nur eine Brute Force Attacke als einzigst praktisch 
durchführbarer Angriff übrig bleibt. Wähle die rechnerische Komplexität 
einer Brute Force Attacke so hoch das sie undurchführbar wird in einem 
frei definierbarem Zeitraum.

Nichts kann sicher sein wenn man davon ausgehen könnte das der Angreifer 
unendliche Resourcen in unendlich kurzer Zeitspanne aktivieren kann.

Dies ist aber in Realität nicht so und somit heist es: sicher ist das 
von dem wir heutzutage mathematisch beweisen können das der Aufwand zum 
Brechen heutzutage mehrere 100'e Jahre dauert.

Sicher wird das alles also nur wenn man Wissen hat, wenn man exakt weiß 
was man konstruiert hat, wenn man es beweisen kann, wenn man in der Lage 
ist die mathematische Komplexität eines Verfahrens ausrechnen zu können, 
wenn man mit seinem Wissen über die Angriffsmöglichkeiten auf dem 
aktuellsten Stand ist.

Gruß Hagen

von B. (Gast)


Lesenswert?


von Lattice User (Gast)


Lesenswert?

B. schrieb:
> Wie sicher wäre denn dann der hier:
> http://de.wikipedia.org/wiki/Well_Equidistributed_...

Steht doch im verlinktem Artikel:
Bei vergleichsweise kurzer Beobachtung seiner Ausgaben kann sein 
interner Zustand ermittelt werden und so alle zukünftigen Zahlen 
vorhergesagt werden.

Inwieweit das Nachschalten einer sicheren Hashfunktion wie im Artikel 
beschrieben hilft kann ich nicht beurteilen, dazu musst du schon Bruce 
Schneier oder eines seiner Kollegen befragen. Und da ich es nicht weiss, 
lass ich besser die Finger davon.

Zudem ist AFAIK SHA256 in Hardware aufwändiger als AES.

von Hagen R. (hagen)


Lesenswert?

Der einzige PRNG den ich kenne der mathematisch vollständig bewiesen 
sicher ist ist der BBS = Blum Blum Shub Generator, ist aber unpraktisch 
auf schwacher Hardware. Der math. Beweis ist der gleiche wie bei RSA.

Gruß Hagen

http://en.wikipedia.org/wiki/Blum_Blum_Shub

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.