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;
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
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.
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
iffalling_edge(TAKT)then
hinschreiben. (Warum auch immer Du die fallende Flanke verwendest...)
Duke
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-LFSRAid 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...
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
ifTAKT'eventandTAKT='0'then-- bei einer fallenden Flanke:
2
D(0)<=EINGANG;-- übernehme das was jetzt gerade am Eingang anliegt nach D(0)
3
endif;
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".
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;
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?
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.
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...
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?
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...
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.
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.
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
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.ä.
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.
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.
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), ... )
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
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
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.
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
