• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    Ein Zufallszahlengenerator umfasst eine Mehrzahl von seriell angeordneten Speicherzellen (100, 101, 102, 103, 104), eine Rückkopplungseinrichtung (105) zum Erzeugen eines Rückkopplungssignals und zum Einspeisen des Rückkopplungssignals in eine (104) der Speicherzellen und eine Zufallszahlenausgabeeinrichtung (106), die ausgebildet ist, um Zustände einer Gruppe von wenigstens zwei Speicherzellen zu kombinieren, um eine Ausgabefolge zu erhalten. Durch Erzeugen mehrerer Ausgabefolgen AF¶0¶, AF¶1¶, AF¶2¶, ..., AF¶k¶ durch Kombination von Zuständen verschiedener Speicherzellen können untereinander stark unterschiedliche Folgen erzeugt werden, deren Anzahl größer als die Anzahl der Speicherzellen ist, so dass eine sichere und effiziente Busverschlüsselung erreichbar ist.
    公开号:DE102004013480A1
    申请号:DE200410013480
    申请日:2004-03-18
    公开日:2005-10-13
    发明作者:Berndt Gammel；Rainer GÖTTFERT
    申请人:Infineon Technologies AG；
    IPC主号:G06F7-58
    专利说明:
    [0001] Dievorliegende Erfindung bezieht sich auf Pseudozufallszahlengeneratorenund insbesondere auf Pseudozufallszahlengeneratoren, die für Schlüsselgeneratorenbei der Busverschlüsselunggeeignet sind.
    [0002] Einbekannter Zufallszahlengenerator ist in 12 dargestellt. Der Pseudozufallszahlengeneratorvon 12, der auch alslineares rückgekoppeltesSchieberegister bezeichnet wird, umfasst eine Mehrzahl von Speicherelementen 51, 52, 53, 54,die in 12 von 0 bisn durchnumeriert sind. Die Speicherzellen sind über eine Initialisierungseinrichtung 55 aufeinen Startwert initialisierbar. Die Speicherzellen 51–54 bildeninsgesamt eine Vorwärtskopplungseinrichtung,währenddas lineare Schieberegister, das durch die Speicherzellen 51–54 gebildetist, durch eine Rückkopplungseinrichtungrückgekoppelt ist,die zwischen einen Ausgang 56 der Schaltung und der Speicherzellen gekoppelt ist. Die Rückkopplungseinrichtungumfasst im einzelnen eine oder mehrere Kombinationseinrichtungen 57, 58,die von jeweiligen Rückkopplungszweigen 59a, 59b, 59c so gespeistwerden, wie es in 12 beispielhaftdargestellt ist. Der Ausgangswert der letzten Kombinationseinrichtung 58 wirdin die Speicherzelle n, die in 12 mit 54 bezeichnetist, eingespeist.
    [0003] Dasin 12 gezeigte linearerückgekoppelteSchieberegister wird von einem Takt betrieben, so dass in jedemTaktzyklus die Belegung der Speicherzellen um eine Stufe Bezug nehmendauf 12 nach links geschobenwird, so dass in jedem Taktzyklus der in der Speichereinrichtung 51 gespeicherte Zustandals Zahl ausgegeben wird, währendgleichzeitig der Wert am Ausgang der letzten Kombinationseinrichtung 58 indie erste Speichereinheit n der Folge von Speichereinheiten eingespeistwird. Das in 12 dargestelltelineare rückgekoppelteSchieberegister liefert somit eine Folge von Zahlen ansprechendauf eine Folge von Taktzyklen. Die am Ausgang 56 erhalteneFolge von Zahlen hängtvon dem Startzustand ab, der durch die Initialisierungseinrichtung 55 vorInbetriebnahme des Schieberegisters hergestellt wird. Der durchdie Initialisierungseinrichtung 55 eingegebene Startwertwird auch als Keim oder Seed bezeichnet, weshalb solche in 12 dargestellte Anordnungenauch als Seed-Generatoren bezeichnet werden.
    [0004] Diean dem Ausgang 56 erhaltene Folge von Zahlen wird als pseudozufällige Folgevon Zahlen bezeichnet, da die Zahlen scheinbar zufällig aufeinanderfolgen, aber insgesamt periodisch sind, obgleich die Periodendauergroß ist.Darüberhinaus ist die Folge von Zahlen eindeutig wiederholbar und damit pseudozufällig, wennder Initialisierungswert, der durch die Initialisierungseinrichtung 55 denSpeicherelementen zugeführtwird, bekannt ist. Solche Schieberegister werden beispielsweiseals Key-Stream-Generatoren eingesetzt, um einen von einem speziellenInitialisierungswert (Seed) abhängigenStrom von Ver-/Ent-Schlüsselungsschlüsseln zu liefern.
    [0005] Solchein 12 dargestelltenSchieberegister haben den Nachteil einer geringen linearen Komplexität. So genügen beieinem n-Bit-LFSR (LFSR = Linear Feedback Shift Register) 2 n Bitsder Ausgabefolge, um die gesamte Folge zu berechnen. Der Vorteilsolcher in 12 dargestelltenbekannten LFSRs besteht jedoch darin, dass der Hardwareaufwand sehrgering ist.
    [0006] Darüber hinausexistieren unregelmäßig getakteteLFSRs. Diese zeigen einen etwas erhöhten Hardwareaufwand bei einermeist geringeren Periode. Die lineare Komplexität kann jedoch deutlich höher sein.Ein Nachteil solcher unregelmäßig getakteterVorrichtungen ist jedoch die Tatsache, dass aufgrund der unregelmäßigen Taktungdurch Strommessung im Rahmen einer SPA (SPA = Simple Power Analysis)prinzipiell auf die Ausgabefolge geschlossen werden könnte. Indemdie Schieberegistervorrichtungen als Teile von Schlüsselgeneratorenverwendet werden, die inhärentgeheim zu haltende Daten, also Schlüsseldaten, erzeugen, ist esbei ihnen besonders wichtig, dass sie gegen jegliche Art von kryptographischenAngriffen sicher sind.
    [0007] Andererseitsbesteht jedoch bei solchen Vorrichtungen insbesondere dann, wennsie auf Chipkarten untergebracht werden sollen, die Anforderung,dass der Hardwareaufwand gering sein muss. In anderen Worten ausgedrückt mussdie Chipfläche, diesolche Vorrichtungen in Anspruch nehmen, so klein als möglich sein.Dies liegt daran, dass in der Halbleiterherstellung die Chipfläche einergesamten Vorrichtung letztendlich den Preis und damit die Gewinnmargedes Chipherstellers bestimmt. Ferner ist besonders bei Chipkarten üblicherweiseeine Spezifikation so, dass ein Kunde sagt, dass ein Prozessorchipeine maximale Flächein Quadratmillimetern haben darf, auf der verschiedenartigste Funktionalitäten untergebrachtwerden müssen.Daher liegt es an dem Schaltungshersteller, diese kostbare Fläche auf dieeinzelnen Komponenten zu verteilen. Im Hinblick auf die immer komplexerwerdenden kryptographischen Algorithmen ist eine Anstrengung desChipherstellers dahingehend gerichtet, dass der Chip möglichstviel Speicher hat, um auch Arbeitsspeicher-intensive Algorithmenin ver tretbarer Zeit berechnen zu können. Die Chipfläche für Schlüsselgeneratorenund andere derartige Komponenten muss daher so klein als möglich gehaltenwerden, um auf der gegebenen Chipfläche mehr Speicher unterbringenzu können.
    [0008] Diegenerelle Anforderung an Schlüsselgeneratorenbzw. Vorrichtungen zum Erzeugen einer pseudozufälligen Folge von Zahlen bestehtsomit darin, einerseits sicher zu sein und andererseits möglichstwenig Platz zu benötigen,also einen möglichst geringenHardware-Aufwand zu haben.
    [0009] Zufallszahlengeneratorenkönnenbeispielsweise zur Busverschlüsselungeingesetzt werden. Hierzu wird auf 13 Bezuggenommen, welche ein herkömmlichesBusverschlüsselungskonzept zeigt.An einem Busanfang muss ein überden Bus zu übertragendesBit mi verschlüsselt werden, um während der Übertragungauf der Busleitung geschützt zusein. Dann, am Busende muss das verschlüsselte Bit wieder zurück in dasunverschlüsselteBit gebracht werden, damit das Bit mi weiterverarbeitet werdenkann. Der Busanfang kann beispielsweise der Ausgang eines Prozessorssein, währenddas Busende der Eingang in einen Speicher sein kann, in dem dasBit dann typischerweise in eine „härtere" Verschlüsselungsart umverschlüsselt wird,um schließlichim Speicher gespeichert zu werden. Alternativ kann der Busanfangnatürlichauch eine Speicher-Ausgabeschnittstellesein, und kann das Busende ein Eingang eines Prozessors sein.
    [0010] Generellgeht man davon aus, dass Bits, die auf Busleitungen übertragenwerden, dort besonders gefährdetsind, so dass die Busverschlüsselungeingesetzt wird. Als typische Verschlüsselungseinrichtung wird einXOR-Gatter verwendet, das an seinem ersten Eingang ein zu verschlüsselndesNachrichtenbit mi ent hält, und das an seinem zweitenEingang ein Schlüsselbitki erhält,das typischerweise von einem Zufallszahlengenerator erzeugt wird.Typischerweise ist die zeitliche Folge von Schlüsselbits ki,wobei i der Zeitindex ist, eine Pseudozufallszahlenfolge,also eine Zahlenfolge, die wie ein Zufallszahlenfolge aussieht,die jedoch insofern deterministisch ist, dass sie reproduzierbarist. Typische Zufallszahlengeneratoren sind, wie es später nochausgeführtwird, rückgekoppelteSchieberegister, die ausgehend von einem definierten Anfangszustand(Seed) eine definierte Ausgangsfolge erzeugen, die eine bestimmtePeriodendauer hat.
    [0011] Beider Busverschlüsselungwird somit, wie es in 13 gezeigtist, am Anfang und am Ende des Busses der selbe Schlüsselfolgengeneratoridentischer Bauart eingesetzt, wobei die Schlüsselfolgengeneratoren – abgesehenvon einer oft vernachlässigbarenVerzögerung,die das verschlüsselteBit ci aufgrund der Übertragung über einen Bus einer bestimmtenLänge „erleidet" – synchron laufen.
    [0012] Bisherwurde als Schieberegister ein Schlüsselfolgengenerator verwendet.Da ein Bus aus mehreren Busleitungen besteht, wie beispielsweiseaus 32 Busleitungen, soll jede Busleitung mit einer Schlüsselfolgeversorgt werden. Dieses Problem kann dadurch gelöst werden, dass für jede Busleitungeine Speicherzelle in einem rückgekoppelten Schieberegistervorgesehen und dass der Zustand jeder Speicherzelle – über derZeit betrachtet – zum Verschlüsselungseingangeiner Busverschlüsselungseinrichtung/Busentschlüsselungseinrichtung geliefertwird. Dies bedeutet, dass beispielsweise der Zustand der siebtenSpeicherzelle überder Zeit als Schlüsselfolgezur Verschlüsselungder achten Busleitung dient, dass beispielsweise der Zustand der sechstenSpeicherzelle überder Zeit als Schlüs selfolgezum Verschlüsselnder siebten Busleitung verwendet wird, etc.
    [0013] JedeZelle des Schieberegisters wird somit ausgegeben, wobei diese Ausgabefolgedann fürdie Verschlüsselungeiner entsprechenden Busleitung verwendet wird.
    [0014] Diesbedeutet jedoch, dass im wesentlichen immer die selbe Schlüsselfolgezur Verschlüsselung allerBusleitungen verwendet wurde, da die einzelnen Schlüsselfolgenja nur verschobene Versionen ein und derselben Schieberegisterfolgesind.
    [0015] AusSicherheitsaspekten ist dies natürlich dahingehend nachteilhaft, dass der Angreifer dann, wenn er eine Schlüsselfolgeermittelt hat, mit dieser einen Schlüsselfolge durch zeitliche Verschiebung sozusagenalle weiteren Schlüsselfolgen,mit denen die anderen Busleitungen verschlüsselt sind, automatisch erhält.
    [0016] Einweiterer Nachteil besteht darin, dass Schieberegister benötigt werden,die wenigstens so viel Zellen haben, wie Busleitungen zu versorgen sind.Für einen32 Bit breiten Bus wird also ein Schieberegister mit wenigstens32 Schieberegisterzellen benötigt.
    [0017] Zusammenfassendist das beschriebene Konzept somit dahin gehend nachteilhaft, dassdie Sicherheit der Verschlüsselungkritisch ist, nachdem alle Busleitungen mit der selben – nur zeitlichverschobenen – Folgeverschlüsseltsind, und dass zudem ein Effizienzproblem im Hinblick auf den Chipflächenverbrauchexistiert, da immer mindestens so viel Speicherzellen benötigt werden,wie Busleitungen vorhanden sind.
    [0018] Insbesondereim Hinblick auf den Chipflächenbedarfsei darauf hingewiesen, dass dieser für in hohen Stückzahlenangebotene Produkte einen ganz erheblichen Kostenfaktor darstellt.
    [0019] Nebendem Kostenfaktor existieren jedoch insbesondere auch für Chipkartenanwendungenweitere restriktive Anforderungen an den Chipflächenbedarf, da die Größe einesChips durch den Anwender, also den Chipkartenhersteller vorgegebenist. Typischerweise hat der Chiphersteller die Möglichkeit, nach seinen Bedürfnissendie zur Verfügungstehende Chipflächeauf Logikelemente, Speicherelemente etc. aufzuteilen. Aufgrund hoherRechenleistungen wird daher immer ein möglichst hoher Anteil an Arbeitsspeicherund Rechenpower benötigt,so dass, um insgesamt die Chipflächenkriterienzu erfüllen, jedeEinsparung an jedem Element, wie beispielsweise einem Schieberegister-Pseudozufallszahlengeneratorvon großerBedeutung ist.
    [0020] DieAufgabe der vorliegenden Erfindung besteht darin, ein sicheres undeffizientes Konzept um Erzeugen von Zufallszahlen zu schaffen.
    [0021] DieseAufgabe wird durch einen Zufallszahlengenerator nach Patentanspruch1, ein Verfahren zum Erzeugen von Zufallszahlen nach Patentanspruch17 oder ein Computerprogramm nach Patentanspruch 18 gelöst.
    [0022] Dervorliegenden Erfindung liegt die Erkenntnis zugrunde, dass die Speicherzellen-Ausgabefolgennicht einfach gewissermaßen „so wiesie sind" zur Busverschlüsselungeingesetzt werden dürfen, sonderndass Ausgabefolgen einer Gruppe von wenigstens zwei Speicherzellenkombiniert werden müssen,so dass eine Ausgabefolge aus einer Folge von wenigstens zwei (zeitverschobenen)Ausgabefolgen der zwei Speicherzellen entsteht.
    [0023] Wirdferner eine andere Ausgabefolge durch eine Kombination zweier unterschiedlicherSpeicherzellen oder durch eine andere Kombination der selben Speicherzellenerzeugt, so sind die beiden erhaltenen Ausgabefolgen nicht nur zweizueinander zeitverschobene, jedoch ansonsten identische Folgen, sondernvoneinander deutlich unterschiedliche Pseudozufalls-Bitfolgen. Ermitteltein Angreifer in diesem Fall eine Schlüsselfolge für eine Busleitung, so ist er nochlange nicht so weit, alle anderen Busleitungen entschlüsseln zukönnen,da er nicht weiß,aus welchen ursprünglichenSpeicherzellen-Zuständendie Folge erzeugt worden ist, und welche Kombinationseinrichtungeingesetzt worden ist. Ein Angreifer kann somit nicht mehr ohneweiteres von einer dechiffrierten Folge auf die anderen dechiffriertenFolgen durch einfache Zeitverschiebung schließen wie im Stand der Technik,sondern er wird ermitteln müssen,welche Speicherzellen kombiniert worden sind, und wie kombiniertworden ist.
    [0024] Nachdemes beliebige Möglichkeitender Kombination durch ein beliebiges System an Logikgattern gibt,ist diese „Rückverfolgung" zur Entschlüsselungeiner zweiten Ausgabefolge aufgrund einer irgendwie entschlüsseltenersten Ausgabefolge beliebig kompliziert.
    [0025] Darüber hinausist das erfindungsgemäße Konzeptwesentlich effizienter, da die Anzahl der Speicherzellen nicht gleichdie Anzahl der Busleitungen sein muss, sondern da die Anzahl derSpeicherzellen kleiner als die Anzahl der Busleitungen sein kann.So kann ohne weiteres ein Bus mit z. B. acht Busleitungen aus einemSchieberegister mit lediglich fünfSpei cherzellen versorgt werden. Dies stellt im Vergleich zum Standder Technik, bei dem fürdie acht Busleitungen acht Speicherzellen benötigt wurden, bereits eine Einsparungum drei Speicherzellen dar, wobei zusätzlich noch die erzeugten achtAusgabefolgen voneinander deutlich unterschiedlich sind und nicht,wie im Stand der Technik, zeitverschobene Versionen der selben Schieberegisterfolgesind.
    [0026] Erfindungsgemäß werdenalso Ausgabefolgen der Zellen des vorzugsweise nicht-linearen maximalperiodischen Schieberegisters nicht direkt zur Busverschlüsselunggenutzt, sondern es werden einige wenige dieser Ausgabefolgen miteinanderaddiert (termweise, modulo 2), und die so gebildeten Summenfolgenwerden dann fürdie Busverschlüsselunggenutzt. Es sei darauf hingewiesen, dass die Summenfolgen unterrein kontrollierbaren Bedingungen, beispielsweise wenn die Anzahlder Schieberegisterzellen eine Primzahl ist, eine maximale Periode,eine maximale lineare Komplexität,ein ausgewogenes Null-1-Verhältnis undeine erhöhtepolynomiale Komplexitäthaben.
    [0027] Fernerist es nun möglich,einen z. B. 32 Bit breiten Bus mit beispielsweise einem Schieberegisterzu versorgen, das nur 11 Zellen hat, und zwar so, dass jede der32 Busleitungen eine eigene Verschlüsselungsfolge bekommt, unddass keine zwei Verschlüsselungsfolgenverschobene Versionen voneinander sind.
    [0028] Damitkann Hardware eingespart werden, nachdem in typischen Bussystemendieser Zufallszahlengenerator nicht nur an einen einzigen Stelle vorkommt,sondern beispielsweise zehnmal oder noch häufiger an verschiedenen Stellenin identischer Form in einem Prozessor-Bussystem vorkommt.
    [0029] BevorzugteAusführungsbeispieleder vorliegenden Erfindung werden nachfolgend Bezug nehmend aufdie beiliegenden Zeichnungen detailliert erläutert. Es zeigen:
    [0030] 1 einBlockschaltbild eines erfindungsgemäßen Zufallszahlengenerators;
    [0031] 2a einBlockschaltbild einer Komponente der Zufallszahlenausgabeeinrichtunggemäß einembevorzugten Ausführungsbeispielder vorliegenden Erfindung;
    [0032] 2b einverallgemeinertes Blockschaltbild einer alternativen Zufallszahlenausgabeeinrichtunggemäß einembevorzugten Ausführungsbeispiel dervorliegenden Erfindung;
    [0033] 3 einBlockschaltbild eines bevorzugten Ausführungsbeispiels für einenZufallszahlengenerator mit umschaltbarer nichtlinearer Rückkopplungsfunktion;
    [0034] 4 einZufallszahlengenerator gemäß einemAusführungsbeispielder vorliegenden Erfindung im Kontext einer Busverschlüsselung;
    [0035] 5a einePrinzipdarstellung einer bekannten Busverschlüsselung am Beispiel einer einzigenBusleitung;
    [0036] 5b einePrinzipdarstellung einer bekannten Busverschlüsselung am Beispiel mehrerer Busleitungen;
    [0037] 6 einenbevorzugten Aufbau eines Elementarschieberegisters mit nicht-linearerRückkopplung;
    [0038] 7 einenalternativen Aufbau fürein Elementarschieberegister mit nicht-linearer Rückkopplung;
    [0039] 8 einenalternativen Aufbau fürein Elementarschieberegister mit nicht-linearer Rückkopplung;
    [0040] 9 einenalternativen Aufbau fürein Elementarschieberegister mit nicht-linearer Rückkopplungseigenschaft;
    [0041] 10 einenbeispielhaften Aufbau fürein Elementarschieberegister mit nicht-linearer Rückkopplung;
    [0042] 11 eineallgemeine Darstellung eines Elementarschieberegisters mit Speicherzellenin der Vorwärtskopplungseinrichtungund einer RückkopplungsfunktionF;
    [0043] 12 einbekanntes lineares Schieberegister zur Erzeugung einer Zufallszahlenfolge;und
    [0044] 13 einePrinzipskizze der Busverschlüsselung.
    [0045] Bevordetailliert anhand der 1 bis 4 auf bevorzugteAusführungsbeispieleder vorliegenden Erfindung eingegangen wird, sei zunächst anhandder 5a, 5b das bekannte, im Hinblick aufdas sicherheitsproblematische und im Hinblick auf die Effizienzebenfalls problematische bekannte Konzept noch einmal dargestellt.So zeigt 5a eine Folge von SpeicherzellenD0, D1, D2, ..., D5 sowie eineBusverschlüsselungseinrichtung 500,die bei dem Ausführungsbeispielals XOR-Gatter ausgeführt ist.So spielt es keine Rolle, ob das Eingangsbit auf der Leitung linksvom XOR-Gatter 500 ein verschlüsseltes oder ein unverschlüsseltesBit ist. Ist es ein unverschlüsseltesBit, so ist das Gatter 500 eine Verschlüsselungseinheit. Ist das Bitdagegen ein verschlüsseltesBit, so ist das Gatter 500 eine Entschlüsselungseinrichtung, der andem Schlüsseleingang 502 derZustand der Speicherzelle D3 – über derZeit betrachtet – zugeführt wird,um die Schlüsselfolge 502 zuerhalten, um das Bit am Ausgang der Einrichtung 500 inverschlüsselterbzw. entschlüsselter Formzu haben, je nachdem, wie es gewünschtist.
    [0046] Werdenverschiedene Busleitungen benötigt,wie beispielsweise acht Busleitungen 504, so könnte dasin 5b gezeigte Konzept verwendet werden, bei demviele Busleitungen fürdie eine Verschlüsselungseinheitvorgesehen sind, wie beispielsweise die Verschlüsselungseinheit 508 für die achte Busleitung,wobei jede Verschlüsselungseinheit 500, 508 eineeigene Verschlüsselungsleitung 502, 504 umfasst.
    [0047] Dasin 5b gezeigte Schieberegister umfasst acht Schieberegisterzellensowie eine Rückkopplungseinheit 8,welche typischerweise ein lineares Rückkopplungspolynom umfasst.
    [0048] Erzeugtdas Schieberegister, das in 5b gezeigtist, somit am Ausgang der Speicherzelle D0 dieFolge σ0 = k0, k1, k2, k3,..., dann erzeugt die Speicherzelle d1,die in Verarbeitungseinrichtung hinter der Speicherzelle D0 ist, eine zeitverschobene Schieberegisterfolgemit k–1,k0, k1, k2, ...
    [0049] DieAusgabefolge der Speicherzelle d1 ist somiteine um ein Bit verschobene Version der Ausgabefolge der SpeicherzelleD0, so dass die einzelnen Schlüsselfolgenzum Verschlüsselnder einzelnen Busleitungen sehr leicht voneinander ableitbar sind.
    [0050] Erfindungsgemäß wird daher,um diese Nachteile zu unterbinden, das in 1 gezeigteKonzept verwendet. 1 zeigt einen Zufallszahlengenerator,der eine Mehrzahl von seriell angeordneten Speicherzellen 100, 101, 102, 103, 104 aufweist,wobei eine Verarbeitungsrichtung existiert, wie sie durch die Pfeilein 1 gezeigt ist. So ist die Speicherzelle 103 inVerarbeitungsrichtung hinter der Speicherzelle 104, jedochin Verarbeitungsrichtung vor der Speicherzelle 102 angeordnet.
    [0051] Fernerist eine Rückkopplungseinrichtung 105 vorgesehen,wobei die Rückkopplungseinrichtungzum Erzeugen eines Rückkopplungssignals dient,das auf der rechten Seite der Rückkopplungseinrichtung 105 erzeugtund ausgegeben wird und in die Speicherzelle 104 eingespeistwird. Das erfindungsgemäße Zufallszahlengeneratorkonzeptzeichnet sich durch eine Zufallszahlenausgabeeinrichtung 106 aus,die ausgebildet ist, um Zuständevon einer Gruppe von wenigstens zwei Speicherzellen zu kombinieren,um eine oder mehrere Ausgabefolgen AF0, AF1, AF2, ... zu erhalten.
    [0052] Einebeispielhafte Version der Zufallszahlenausgabeeinrichtung 106 istz. B. in 2a gezeigt. Hierbei werden dieAusgabefolgen, die sich durch die zeitlich aufeinanderfolgendenZuständeder Speicherzellen D4 und D3 ergeben,mit einem XOR-Gatter kombiniert, um die Ausgabefolge Afi zuerzeugen, die einer Busverschlüsselungseinheit 500 zugeführt wird,um ein Klartextbit links von der Verschlüsselungseinheit 500 zuverschlüsseln,um es auf die Busleitungen übertragenzu können.Ist dagegen das zu bearbeitende Bit ein verschlüsseltes Bit, so ist die Einrichtung 500 eineEntschlüsselungseinrichtung, unddie SchlüsselfolgeAfi dient zur Entschlüsselung eines Bits, das miteiner irgendwo anders auf dem Chip ange ordneten und erzeugten identischenFolge Afi verschlüsselt worden ist.
    [0053] 2b zeigteine alternative Ausführungsformder Zufallszahlenausgabeeinrichtung 106, wobei die Gruppevon Speicherzellen, deren Zustände kombiniertwerden, nunmehr, im Gegensatz zu 2a, nichtdie Speicherzellen D4 und D3 umfasst, sondernnunmehr die Speicherzellen D2, D3 und D5 umfasst.Wieder ist die Kombinationseinrichtung in der Zufallszahlenausgabeeinrichtungals XOR-Gatter ausgeführt,das nun jedoch, im Gegensatz zu 2a, dreiEingängehat.
    [0054] Essei darauf hingewiesen, dass als Kombinationseinrichtung beliebigeKombinationen eingesetzt werden können, die nicht nur XOR-Gattersein müssen,sondern auch alle anderen logischen Gatter, wie z. B. UND-Gatter,NAND-Gatter, OR-Gatter, NOR-Gatter, XNOR-Gatter etc., solange dieAusgabefolgen von wenigstens zwei Speicherzellen irgendwie kombiniertwerden, um eine kombinierte Ausgabefolge zu erzeugen.
    [0055] Fernerwird im Hinblick auf einen hohen Sicherheitsaspekt bevorzugt, dassder erfindungsgemäße Zufallszahlengeneratormehrere Ausgabefolgen liefert, die voneinander unterschiedlich sindund somit nicht durch zeitliche Verschiebung aus ein und derselbenSchieberegisterfolge abgeleitet sind. Dies wird dadurch erreicht,dass, wie es in 2a und 2b gezeigtist, unterschiedliche Gruppen von Speicherzellen im Hinblick aufihre Ausgabefolgen kombiniert werden. Unterschiedliche Ausgabefolgen können auchdurch eine unterschiedliche Kombination erreicht werden. So könnte beispielsweiseeine zweite Ausgabefolge Afi mit der in 2a gezeigten Schaltungauch dazu verwendet werden, um eine Ausgabefolge Afi+1 zuerzeugen, bei der die Zustandsfolgen der Speicherzel len D4 und D3 nicht XOR-verknüpft werden,sondern z. B. UND-verknüpft werden.Selbstverständlichkönntestatt XOR auch XNOR etc. verwendet werden.
    [0056] Vorzugsweiseist die Ausgabeeinrichtung 106, wie sie in 1 dargestelltist, somit ausgebildet, um alle Ausgabefolgen AF0 ...,AFk so zu erzeugen, dass alle Folgen voneinanderunterschiedlich sind, und zwar dahin gehend, dass entweder die Gruppevon Speicherzellen, aus der die Ausgabefolge durch Kombination hervorgeht,für jedeAusgabefolge unterschiedlich ist, und/oder dass die Kombinationsvorschrift,mit den Zustandsfolgen einer Gruppe von Speicherzellen kombiniertwerden, fürunterschiedliche Ausgabefolgen unterschiedlich ist.
    [0057] Darüber hinausist das erfindungsgemäße Konzeptdahin gehend vorteilhaft, dass, wie es ebenfalls in 1 gezeigtist, die Anzahl der Ausgabefolgen AFk wesentlichgrößer seinkann als die Anzahl von Speicherzellen, was bei dem in 5b gezeigtenVergleichskonzept nicht der Fall war.
    [0058] Erfindungsgemäß wird alsoder Nachteil, dass im wesentlichen die selbe Folge zur Verschlüsselungder einzelnen Busleitungen verwendet wird, wie nachfolgend dargelegt überwunden.
    [0059] Essei ein rückgekoppeltesSchieberegister mit N Zellen D0, D1, ...,D1–1 betrachtet.Ferner sei σ0 die Ausgabefolge der vordersten Zelle D0. Es sei σ1 dieAusgabefolge der zweiten Zelle D1, ...,und es sei σN–1 dieAusgabefolge der letzten Zelle DN–1.
    [0060] Fernerwird bevorzugt, dass das zugrunde liegende Schieberegister nicht-linearist, also eine nicht-lineare Rückkopplungseinrichtunghat, und dass es eine maximal periodische Folge generieren kann,wobei die Periode dann gleich 2N–1 ist .Dann haben alle Folgen σ0, σ1, ...,σN–1 diemaximale Periodenlänge2N–1,und es kann gezeigt werden, dass die Folgen alle die selbe lineareKomplexitäthaben. Die lineare Komplexitätkann den Wert 2N–2 annehmen. Sie ist aber immermindestens 2N–1.
    [0061] Essei beachtet, dass die Folgen σ1, ...,σN–1 nurverschobene Versionen der Folge σ0 sind.
    [0062] Echtandere Folgen erhältman aber, wenn die einzelnen Folgen von σ0, σ1,...,σN–1 z.B. miteinander addiert werden, wie z. B. σ0 + σ1 oder σ2 + σ5 + σ7,etc.
    [0063] EineAusführungsformder Addition ist die gliedweise Addition modulo 2. Dies bedeutetfolgendes: σ1 = 0011010... und σ6 =1011100..., dann gilt fürdie Addition modulo 2 von σ1 und σ6 = 100110 ...
    [0064] Umdie Ausgabefolgen im Falle einer Addition modulo 2 voneinander starkunterschiedlich zu machen, wird es bevorzugt, dass das zugrundeliegende Schieberegister eine nicht-lineare Rückkopplung hat. Hier liefertdie Addition vollständigneue Folgen. Daher wird es bevorzugt, dass der Busverschlüsselungnicht-lineare Schieberegister zugrunde liegen.
    [0065] Nachfolgendwird ausgeführt,wieso durch Addition erzeugte Folgen günstige Eigenschaften aufweisen.So seien σ0, σ1, ..., σN–1 Ausgabefolgen auseinem nicht-linearen Schieberegister, das Folgen maximaler Perioded.h. der Periode = 2N–1, erzeugen kann. Die Folgen σ0, σ1,..., σN–1 habenjeweils die Periode 2N–1. Sei L die lineare Komplexität von σ0,so ist L auch die lineare Komplexität von σ1, σ2,..., σN–1. WennN eine Primzahl ist, wenn also die Anzahl der Zellen des zu zugrundeliegenden Schieberegisters eine Primzahl ist, dann gilt folgendes: JedeFolge τ,die durch Addition von Folgen aus {σ0, σ1,..., σN–1}entsteht, hat ebenfalls die Periodenlänge 2N–1 und dielineare KomplexitätL.
    [0066] Darüber hinauskommen innerhalb einer vollen Periode von r fast gleich viele Nullenund Einsen vor. Genauer gesagt, kommen 2N–1–1 Nullenund 2N–1 Einsenvor.
    [0067] Für das BeispielN = 7 gilt folgendes: σ0, σ1, ..., σ6 haben die Periode 27–1 = 127und die lineare KomplexitätL = 126. Die Folge τ = σ2 + σ3 hat danndie Periode 127 und die lineare Komplexität 126.In einer vollen Periode von τ kommensomit 63 Nullen und 64 Einsen vor.
    [0068] Daserfindungsgemäße Konzept,also die Idee, die Ausgabefolgen aus den einzelnen Schiebergisterzellennicht direkt den einzelnen Busleitungen zuzuführen, sondern sie vorher untereinanderz. B. durch eine Addition modulo 2 zu kombinieren, hat eine wichtigeKonsequenz. Es ist nunmehr möglich, alleBusleitungen mit unterschiedlichen Verschlüsselungsfolgen zu versorgen,wobei die unterschiedlichen Verschlüsselungsfolgen von einem Schieberegisterabgeleitet werden können,das weniger Speicherzellen enthältals es Busleitungen gibt. Z. B. wird ein 32-Bit-breiter Bus einesChips von einem Schieberegister versorgt, das nur 11 Speicherzellenenthält.
    [0069] DieseIdee sei nachfolgend anhand von 4 dargestellt.Das in 4 gezeigte Schieberegister hat fünf Zellenund versorgt acht Busleitungen mit unterschiedlichen Schlüsselfolgen.Für jedeBusleitung ist wieder eine eigene Verschlüsselungs- bzw. Entschlüsselungseinrichtung 500 vorgesehen,wobei an dem Schlüsseleingangjeder Verschlüsselungs- bzw.Entschlüsselungseinrichtungeine Ausgabefolge AF1 bis AF8 anliegt.Wie es aus 4 ersichtlich ist, wird zumErzeugen der Ausgabefolgen AF1 die Gruppevon Speicherzellen, die die Speicherzellen D0 undD1 umfassen, verwendet. Darüber hinauswird zum Erzeugen der Ausgabefolge AF2 dieGruppe von Speicherzellen verwendet, die die Speicherzellen D0 + D1 + D2 umfasst. Zum Erzeugen der Ausgabefolge AF3 wird die Gruppe von Speicherzellen verwendet, diedie Speicherzellen D0 und D2 umfasst.
    [0070] DieGruppe von Speicherzellen fürdie Ausgabefolge AF4 ist die Gruppe, diedie Speicherzellen D0, D1 undD3 umfasst.
    [0071] Analoghierzu wird die Ausgabefolge AF5 durch Kombinationder Speicherzellen der fürdie fünfteBusleitung vorgesehenen Gruppe erzeugt, die die Speicherzellen D0 und D3 umfasst.
    [0072] Ähnlich wirdauch die Ausgabefolge AF6 aus den Speicherzellenerzeugt, die als D0, D1 undD4 eine Gruppe bilden.
    [0073] Wiederanalog wird die Ausgabefolge AF7 für die Busverschlüsselungder siebten Busleitung durch die Gruppe von Speicherzellen erzeugt,die D0 und D4 umfasst.
    [0074] Schließlich wirddie Ausgabefolge AF8 aus der Kombinationder Zuständeder Gruppen von Speicherzellen erzeugt, die die Speicherzelle D0, D2 und D4 erfasst.
    [0075] WeitereAusgabefolgen könntenin 4 erzeugt werden, und zwar z. B. die Ausgabefolge,bei der als Gruppe von Speicherzellen alle Speicherzellen D0, D1, D2,D3 und D4 verwendetwerden.
    [0076] Fernerwerden auch alle Gruppen von Speicherzellen, die jeweils vier Speicherzellenumfassen, bei dem in 4 gezeigten Ausführungsbeispiel nichtverwendet. Daher ist zu sehen, dass aus den fünf Speicherzellen D0 bis D4 noch wesentlichmehr als acht Ausgabefolgen erzeugt werden können, wobei jede Folge dannunterschiedlich zu einer anderen Folge ist, wenn die Rückkopplungseinrichtung 105 einenicht-lineare Rückkopplungseigenschaftumfasst, wie es späternoch ausgeführtwird.
    [0077] 3 umfasstneben den Speicherzellen x0, ...,x10 ein erstes UND-Gatter 212, einzweites UND-Gatter 213, ein erstes XOR-Gatter 214,ein zweites XOR-Gatter 218 sowie einen Invertierer 216, umdie beiden alternativen Funktionen F(x) und G(x) wie sie in 3 dargestelltsind, abhängigvon der Stellung des Umschalters 203 zu implementieren. DasErgebnis des Umschalters 203 wird mit einem weiteren XOR-Gatter 221 indie Rückkopplunggewissermaßen „eingekoppelt". Der Umschalterhat den Steuereingang 204, an dem das Steuersignal z angelegtwird. Der Steuereingang 204 ist mit einem externen Zufallszahlengenerator 210 bzw.einer externen Steuerung in dem externen Zufallszahlengenerator(RNG) zum Liefern des Steuersignals z verbunden.
    [0078] Nachfolgendwird Bezug nehmend auf die 6 bis 10 eineAnzahl von verschiedenen Ausführungsbeispielenzur Ausgestaltung der einzelnen Elementarschieberegister 101–111 inden 6 bis 9 gegeben. Es sei darauf hingewiesen,dass nicht unbedingt alle Schieberegister, beispielsweise in 5 die Schieberegister 101–111,denselben Aufbau haben müssen,sondern dass sie unterschiedliche Aufbauten haben können, solange wenigstens eines, und vorzugsweise alle Schieberegister einenicht-lineare Rückkopplungseigenschafthaben.
    [0079] 6 zeigtein Elementarschieberegister mit nichtlinearer Rückkopplung zum Erzeugen einer pseudozufälligen Folgevon Zahlen mit einer Vorwärtskopplungseinrichtung 1,die eine Folge von Speichereinheiten 2 bis 5 aufweist,und die ferner einen Eingang 6 sowie einen Ausgang 7 umfasst,der dem Ausgang der Vorrichtung zum Ausgeben der Folge von Pseudozufallszahlenentspricht. Es sei darauf hingewiesen, dass die Folge von Pseudozufallszahlendurch weitere Einrichtungen, die in 6 nichtgezeigt sind, ergänztwerden kann, um Folgen von Zufallszahlen zu puffern, auf irgendeineandere Art und Weise zu kombinieren etc.
    [0080] Diein 6 gezeigte Vorrichtung umfasst ferner eine Rückkopplungseinrichtung 8,die eine veränderbareRückkopplungseigenschaftaufweist und zwischen den Eingang 6 und den Ausgang 7 der Vorwärtskopplungseinrichtung 1 geschaltetist. Die veränderbareRückkopplungseigenschaftder Rückkopplungseinrichtung 8 istin 6 dahingehend dargestellt, dass die Rückkopplungseinrichtung 8 eine ersteRückkopplungseigenschaft 9 odereine zweite Rückkopplungseigenschaft 10 annehmenkann, wobei zwischen der ersten Rückkopplungseigenschaft 9 undder zweiten Rückkopplungseigenschaft 10 durch eineUmschalteinrichtung 11 z. B. hin- und hergeschaltet werdenkann. Das Steuersignal fürdie Umschalteinrichtung 11 wird lediglich beispielhaftvon der vierten Speichereinrichtung SE2 geliefert, wie es durcheinen Signalpfad 12 symbolisch dargestellt ist. Die ersteRückkopplungseigenschaft 9 unddie zweite Rückkopplungseigenschaft 10 unterscheidensich bei einem in 6 gezeigten Ausführungsbeispiel dadurch,dass im Falle der ersten Rückkopplungseigenschaftder Zustand der Speichereinrichtung 1 (Nr. 3) in die Rückkopplungeingeht, währendim Falle der zweiten Rückkopplungseigenschaftder Zustand der Speichereinrichtung 5 (SEn) zur Rückkopplungbeiträgt.
    [0081] Alternativoder zusätzlichkann die Rückkopplungseinrichtung 8 derartausgebildet sein, dass in der Rückkopplungseigenschaft,die den Wert am Ausgang 7 der Vorwärtskopplungseinrichtung miteinem inneren Zustand der Vorwärtskopplungseinrichtungkombiniert, je nach ausgewählterRückkopplungseigenschafteine andere Kombinationsvorschrift eingesetzt wird. So könnte beispielsweisein der ersten Rückkopplungseigenschaftzur Kombination des Werts am Ausgang 7 mit dem Wert derRegisterzelle 3 eine UND-Kombination eingesetzt werden,währenddie zweite Rückkopplungseigenschaftsich von der ersten Rückkopplungseigenschaftdadurch unterscheidet, dass zur Kombination der beiden genanntenWerte nicht eine UND- sondern eine OR-Kombination eingesetzt wird.Für Fachleuteist es klar, dass verschiedene Arten von unterschiedlichen Kombinationsvorschrifteneingesetzt werden können.
    [0082] Darüber hinausmüssenWerte der Speichereinrichtungen SE1 bzw. SEn nicht unmittelbar einer Kombinationseinrichtungin der Rückkopplungseinrichtungzugeführtwerden, sondern diese Werte könnenz. B. invertiert werden, miteinander kombiniert werden oder aufirgend eine andere Art und Weise z. B. nichtlinear verarbeitet werden,bevor dann sie verarbeiteten Werte einer Kombinationseinrichtungzugeführtwerden.
    [0083] Darüber hinausist es nicht wesentlich, dass die Umschalteinrichtung 11 direktvon dem Zustand der Speichereinheit SE2 gesteuert wird. Statt dessen könnte derZustand der Speichereinrichtung SE2 invertiert werden, auf irgendeine andere Art und Weise logisch oder arithmetisch verarbeitetwerden oder sogar mit dem Zustand einer oder mehrerer weiterer Speichereinrichtungenkombiniert werden, so lange eine Vorrichtung zum Erzeugen einerpseudozufälligenFolge von Zahlen erhalten wird, die eine Rückkopplungseinrichtung aufweist,deren Rückkopplungseigenschaftnicht statisch ist, sondern dynamisch abhängig von der Vorwärtskopplungseinrichtungund insbesondere von einem oder mehreren Zuständen in Speichereinheiten derVorwärtskopplungseinrichtungvariierbar ist.
    [0084] Inder Vorwärtskopplungseinrichtung 1 von 6 istferner eine Steuereinrichtung 13 eingebracht, die zwischenzwei Speicherelementen angeordnet ist, nämlich bei dem in 6 gezeigtenBeispiel den Speicherelementen 4 und 5. Nachdem ein Signalflussvon dem Speicherelement 0 bis zum Speicherelement n in 6 stattfindet,ist das Speicherelement 4 das signalflußmäßig vor der Steuereinrichtungangeordnete Speicherelement, während dasSpeicherelement 5 das signalflußmäßig nach der Steuereinrichtungangeordnete Signal ist. Die Steuereinrichtung 13 hat einenSteuereingang 13a, der mit einem Steuersignal beaufschlagbarist, das prinzipiell ein beliebiges Steuersignal sein kann.
    [0085] DasSteuersignal kann beispielsweise eine echte Zufallszahlenfolge sein,so dass die Ausgabefolge der Schieberegisteranordnung eine Zufallszahlenfolgeist. Das Steuersignal kann auch ein deterministisches Steuersignalsein, so dass ausgangsseitig eine Pseudozufallszahlenfolge erhaltenwird.
    [0086] Vorzugsweiseist der Steuereingang 13a jedoch, wie es durch die in 6 gezeigteentsprechende gestrichelte Linie dargestellt ist, mit der Rückkopplungseinrichtung 8 verbunden,derart, dass ein Signal in der Rückkopplungseinrichtungdas Steuersignal fürdie Steuereinrichtung 13 liefert, das Steuersignal alsoein deterministisches Signal ist.
    [0087] Obgleichbei dem in 6 gezeigten Ausführungsbeispieldie Rückkopplungseinrichtung 8 alsvariable Rückkopplungseinrichtungbezeichnet ist, kann die Rückkopplungseinrichtungauch eine Rückkopplungseinrichtungmit konstanter Rückkopplungseigenschaftsein, wie es durch eine gestrichelte Linie 14 angedeutetist. In diesem Fall würdedas Steuersignal fürden Steuereingang 13a von einem Verzweigungspunkt 14a abgeleitetwerden, wie es in 6 schematisch dargestellt ist,und zwar durch die gestrichelte Linie vom Punkt 14a zudem Steuereingang 13a der Steuereinrichtung 13.
    [0088] Fernerwird, um die Effizienz zu steigern, der in 6 gezeigteElementar-Zahlenfolgengenerator dazu verwendet, um z. B. nicht nureine Folge an dem Ausgang 7 zu erzeugen, sondern um einezweite Folge von vorzugsweise Pseudozufallszahlen an einem weiterenAusgang 15 zu erzeugen, wobei beide Folgen oder nur eineFolge der beiden folgen in die Kombinationseinrichtung eingespeistwerden kann. Das Einfügender Steuereinrichtung 13 bewirkt, dass die an dem Ausgang 7 ausgegebeneFolge tatsächlichunterschiedlich zu der am Ausgang 15 ausgegebenen Folgeist, wobei die beiden Folgen nicht nur zueinander verschoben sind,sondern, wie es ausgeführtworden ist, tatsächlichunterschiedlich sind, da sie signalflußmäßig vor bzw. hinter der Steuereinrichtung 13 „abgezapft" werden.
    [0089] 7 zeigtein 8-Bit-Schieberegister, bei dem abhängig von dem Zustand der Speichereinrichtungmit der Nr. 4 ein Multiplexer 20 über einen Steuereingang 20a angesteuertwird. Ist der Steuereingang 20a auf einem Null-Zustand,d. h. liegt in der Speicherzelle mit der Nr. 4 ein Null-Zustandvor, so wird der Multiplexer derart gesteuert, dass er den Zustandder Speichereinrichtung mit der Nr. 7 an einer ersten Eingangsleitung 20b desselbenmit einer Ausgangsleitung 20d verbindet. Dies würde derWirkung eines linearen Schieberegisters mit dem folgende Rückkopplungspolynomentsprechen: x8 + x7 + 1
    [0090] Istder Steuereingang 20a dagegen auf einem Eins-Zustand, sowird der Zustand der Speichereinrichtung mit der Nr. 6 an einemzweiten Eingang 20c mit der Ausgangsleitung 20d desMultiplexers 20 verbunden. Die Ausgangsleitung 20d istmit einer Kombinationseinrichtung 21 verbunden, der ferner beidem in 7 gezeigten Ausführungsbeispiel der Wert amAusgang 7 der Vorwärtskopplungseinrichtung,der gleichzeitig den Ausgang der Vorrichtung zum Erzeugen einerpseudozufälligenFolge von Zahlen bildet, zugeführt.Das Ergebnis, das durch die Kombinationseinrichtung 21 berechnetwird, wird wiederum der ersten Speichereinrichtung mit der Nr. 7in 7 zugeführt.
    [0091] Istdaher der Inhalt der Speicherzelle mit der Nr. 4 gleich 1, so liegtfolgendes Rückkopplungspolynomvor: x8 + x6 +1
    [0092] Ausdem vorstehenden wird ersichtlich, dass zwischen den beiden genanntenRückkopplungspolynomenumgeschaltet wird, und zwar abhängigvon dem Inhalt der Speicherzelle mit der Nr. 4 der Vorwärtskopplungseinrichtung 1.
    [0093] Eshat sich herausgestellt, dass die linearen Komplexitäten vonerfindungsgemäß erhaltenenSequenzen hoch sind, nämlichzwischen 234 und 254, wenn das Schieberegister 8 Flip-Flopshat. Es sei darauf hingewiesen, dass die Periodenlänge einer Sequenz,die durch ein beliebiges achtstufiges Schieberegister erzeugt wird,maximal 255 betragen kann. Der maximale Wert für die lineareKomplexität einersolchen Sequenz beträgt 254.
    [0094] Daseinfachste von allen achtstufigen Elementarschieberegistern, dieeine Sequenz erzeugen können,ist das in 7 dargestellte Schieberegister mitden beiden in 7 dargestellten Rückkopplungspolynomen.Im Hinblick auf die Theorie der linearen Schieberegister als Vergleichsbeispielsei darauf hingewiesen, dass es 16 primitive Polynome des Grads 8 gibt.Jedes derartige Polynom beschreibt ein lineares Schieberegisterdas eine Sequenz der Periodenlänge 255 undder linearen Komplexität 8 erzeugenkann. Demgegenüberexistieren viel mehr Schieberegister – nämlich 2020 – gemäß der vorliegenden Erfindung,die Sequenzen der Periodenlänge 255 gemäß der vorliegendenErfindung erzeugen können.
    [0095] Darüber hinaushaben die Sequenzen, die durch die erfindungsgemäßen Schieberegister erzeugtwerden, viel größere lineareKomplexitätenals ihre analogen Ausführungengemäß dem Standder Technik. Wie es ausgeführtworden ist, wird unter allen untersuchten Möglichkeiten für ein 8-Bit-Schieberegistermit Rückkopplungseinrichtungdie in 7 gezeigte Ausführungsform bevorzugt, da sieden einfachsten Hardware-Aufwand mit sich bringt, gleichzeitig einemaximale Periodendauer hat und ferner eine maximale lineare Komplexität aufweist.
    [0096] In 7 istferner wieder eine Steuereinrichtung 13 zwischen zwei Speicherelementenangeordnet, wobei dies die Speicherelemente 1 und 2 sind. Die Steuereinrichtung 13 wirdmit einem Steuersignal versorgt, das aus der Rückkopplungseinrichtung 8 mitvariabler Rückkopplungseigenschaftabgezapft wird. Selbstverständlichkönntedas Signal fürdie Steuereinrichtung auch signalflußmäßig nach dem XOR-Gatter 21 „abgezapft" werden. Darüber hinaus kanndie Steuereinrichtung 13 selbstverständlich auch zwischen zwei beliebigenanderen Speicherzellen ausgebildet sein, wie z. B. zwischen denSpeicherzellen 5 und 6 oder zwischen den Speicherzellen 0 und 7,also entweder in Signalflussrichtung hinter der Speicherzelle 0,so dass unmittelbar das Signal am Ausgang der Speichereinrichtungan dem Ausgang 7 ausgegeben wird, oder unmittelbar vorder Speicherzelle 7.
    [0097] AusSignalverarbeitungsgründenwird es jedoch bevorzugt, dass sämtlicheSignale, wie z. B. Ausgangsfolgen, Steuersignale und Datensignalefür denMultiplexer etc. am Ausgang von Schieberegistern abgegriffen werden,so dass das Schieberegister neben seiner Funktionalität zum Erzeugender Zahlenfolge auch dazu dient, stabile Signale für Logikgatterzu liefern. Damit müssenkeine entsprechenden Ausgangsstufen für Logikgatter erzeugt werden, wennvon den Ausgängender Logikgatter selbst Steuersignale oder Ausgangssignale abgezapftwerden.
    [0098] Nachfolgendwird auf 8 Bezug genommen, um eine spezielleImplementierung der Multiplexereinrichtung 20 von 7 darzustellen.Der Multiplexer 20 kann ohne weiteres durch zwei UND-Gatter 40a, 40b implementiertwerden, die beide mit seriell geschalteten ODER-Gattern (oder XOR-Gattern) 41a, 41b soverbunden sind, wie es in 8 gezeigt ist.Im einzelnen wird der Zustand der Speicherzelle 4 dem ersten UND-Gatter 40a zugeführt, während derinvertierte Zustand der Speicherzelle 4 dem zweiten UND-Gatter 40b zugeführt wird.Zur Bestimmung des entsprechenden Rückkopplungspolynoms wird derInhalt der Speicherzelle 6 dem ersten UND-Gatter 40a alszweiter Eingang zugeführt,währendder Inhalt der Speicherzelle 7 dem zweiten UND-Gatter 40b alszweiter Eingang zugeführtwird. Ferner sei darauf hingewiesen, dass die beiden hintereinander geschaltetenODER-Gatter 41a, 41b alternativ implementiertwerden können.Wenn jedoch Implementierungen benötigt werden, bei denen jedeslogische Gatter zwei Eingängeund einen Ausgang hat, ist die in 8 gezeigtebeispielhafte Darstellung vorteilhaft.
    [0099] Beieinem Verfahrens zum Erzeugen einer pseudozufälligen Folge von Zahlen auseinem Elementarschieberegister unter Verwendung einer Vorwärtskopplungseinrichtung 1 miteiner Mehrzahl von Speichereinrichtungen, die einen Eingang undeinen Ausgang zum Ausgeben der Folge von Zahlen aufweist, und einerRückkopplungseinrichtung,die eine veränderbareRückkopplungseigenschaftaufweist und zwischen den Eingang und den Ausgang geschaltet ist,wird zunächstein Schritt des Initialisierens der Speichereinrichtung in der Vorwärtskopplungseinrichtungauf einen vorbestimmten Startwert ausgeführt.
    [0100] Ansprechendauf einen Zustand einer Speichereinrichtung der Mehrzahl von Speichereinrichtungender Vorwärtskopplungseinrichtungwird dann in einem weiteren Schritt die Steuerungseinrichtung abhängig vondem Rückkopplungssignalgesteuert. Hierauf wird ein Zustand einer Speichereinrichtung, diemit dem Ausgang der Vorwärtskopplungseinrichtung 1 verbundenist, ausgegeben, um eine Zahl der Folge von Zufallszahlen zu erhalten.Hierauf wird in einem Entscheidungsblock untersucht, ob weitere Zufallszahlenbenötigtwerden. Wird diese Frage mit nein beantwortet, so wird das Verfahrenbeendet. Wird dagegen festgestellt, dass weitere Zahlen benötigt werden,so wird der Entscheidungsblock mit „ja" beantwortet, woraufhin ein weiterenSchritt folgt, in dem die Mehrzahl von Speichereinrichtungen basierendauf einem vorherigen Zustand der Speichereinrichtung und auf einerAusgabe der Rückkopplungseinrichtungneu belegt werden. In einer Schleife werden die Schritte des Steuernsder Steuerungseinrichtung, Ausgebens und Neubelegens so oft wiegewünschtwiederholt, um schließlichdie pseudozufälligeFolge von Zahlen zu erhalten.
    [0101] Essei darauf hingewiesen, dass dieses Verfahren unter Verwendung einesregelmäßigen Takts durchgeführt werdenkann, oder auch unter Verwendung eines unregelmäßigen Takts, obgleich die Variantemit regelmäßigem Taktim Hinblick auf eine bessere Sicherheit gegenüber Leistungs- oder Zeit-Attackenbevorzugt wird.
    [0102] ImFalle des in 7 dargestellten linearen Schieberegisterswird darauf hingewiesen, dass das Neubelegen der Mehrzahl von Speichereinrichtungenseriell erfolgt, und zwar basierend auf dem vorherigen Zustand derSpeichereinrichtungen, der – insgesamtgesehen – umeinen Schritt nach links verschoben wird, so dass ausgangsseitigein Zustand der Speichereinrichtung 0 „herausfällt". Dieser „herausgefallene" Wert ist die Zahl,die ausgegeben wird. Durch das Links-Verschieben des insgesamt betrachtetenZustands der gesamten Speichereinrichtungen kann die ganz rechteSpeichereinrichtung mit der Nr. 7 in 7 neu belegtwerden. Die Mehrzahl von Speichereinrichtungen und insbesonderedie Speichereinrichtung 7 wird daher abhängig voneiner Ausgabe der Rückkopplungseinrichtungzum aktuellen Taktzeitpunkt neu belegt.
    [0103] 9 zeigtein alternatives Ausführungsbeispiel,bei dem die in 6 mit dem Bezugszeichen 14 bezeichneteAlternative der Rückkopplungseinrichtungdargestellt ist. Insbesondere ist die Rückkopplungseinrichtung 14 in 9 derartausgebildet, dass sie keine variable Rückkopplungseigenschaft hat,sondern eine konstante Rückkopplungseigenschafthat. Die erfindungsgemäßen Vorteilewerden dadurch erreicht, dass in der Vorwärtskopplungseinrichtung zumindesteine Steuereinrichtung 13 und vorzugsweise eine weitereSteuereinrichtung 60 angeordnet sind.
    [0104] Beidem in 9 gezeigten Ausführungsbeispiel wird die Steuereinrichtung 13 miteinem Steuersignal gesteuert, das direkt von der Rückkopplungseinrichtung 14 abgeleitetwird. Bei der in 9 gezeigten Vorwärtskopplungseinrichtungsind lediglich zwei Speichereinrichtungen 2 und 3 vorgesehen,wobei die erste Steuereinrichtung 13 zwischen der Speicherzelle2 und 3 geschaltet ist, währenddie zweite Steuereinrichtung 60 zwischen der Speicherzelle3 und (überdie Rückkopplungseinrichtung 14)der Speicherzelle 2 geschaltet ist. Ferner ist in 9 ein Signalflussdurch einen Pfeil 61 markiert, der den Signalfluss in derVorwärtskopplungseinrichtungdarstellt, der sich bei dem in 9 gezeigtenAusführungsbeispielvon rechts nach links erstreckt. Ein Bit gelangt zunächst indie Speichereinrichtung D2. Damit wird das in D2 gespeicherte Bitausgegeben und bildet ein Bit der ersten Folge. Gleichzeitig wirddas von der Speichereinrichtung 2 ausgegebene Bit mit einemgerade auf der Rückkopplungseinrichtung 14 anliegendenBit bei dem in 9 gezeigten Aus führungsbeispielXOR-verknüpft,um an einem Ausgang der XOR-Verknüpfung einErgebnisbit zu erhalten, das dann beim nächsten Zyklus in das Speicherelement 3 eingetaktetwird. Damit wird das gerade in dem Speicherelement 3 befindlicheBit aus dem Speicherelement 3 herausgetaktet und stelltdamit ein Bit der zweiten Pseudozufallsfolge von Zahlen dar. DasBit am Ausgang der Speicherzelle 3 wird dann mit einemSteuersignal fürdie zweite Steuereinrichtung 60 XOR-verknüpft, wobeidas Steuersignal aus dem Signal an der Rückkopplungseinrichtung 14 unddem Ausgangssignal der ersten Steuereinrichtung 13 mittelseiner Kombinationseinrichtung erzeugt wird. Die Kombinationseinrichtung 62 istvorzugsweise ein logisches Gatter und insbesondere bei dem in 9 gezeigtenAusführungsbeispielein UND-Gatter. Die erste Folge wird über einen Ausgang 7 ausgegeben,währenddie zweite Folge über einenAusgang 15 ausgegeben wird. Die beiden über die Ausgänge 7 und 15 ausgegebenenFolgen sind tatsächlichunterschiedlich und nicht nur phasenverschoben zueinander.
    [0105] Umdie Implementierung des XOR-Gatters 60 zu vereinfachen,wird bei einem anderen bevorzugten Ausführungsbeispiel in Signalflussrichtung hinterdem XOR-Gatter 60 noch ein weiteres Speicherelement vorgesehen,wobei dann, am Ausgang dieses Speicherelements, eine Folge ausgegeben wird,die lediglich phasenverschoben zu der ersten Folge am Ausgang 7 ist,die jedoch grundsätzlichunterschiedlich zur zweiten Folge am Ausgang 15 ist.
    [0106] 10 zeigtein 8-Bit-Elementarschieberegister mit Flip-Flops D0 – D7, die seriell zueinander geschaltetsind, wobei ferner zwischen dem vierten und dem dritten Flip-Flopdie zweite Steuereinrichtung 60 vorgesehen ist, während zwischendem siebten und dem sechsten Flip-Flop die erste Steuerein richtung 13 vorgesehenist. Die erste Steuereinrichtung 13 wird wieder direktmit dem Rückkopplungssignalauf der Rückkopplungseinrichtung 14 versorgt, während diezweite Steuereinrichtung 60 mit dem Ausgangssignal desUND-Gatters 62 versorgt wird, das wiederum von der Rückkopplungseinrichtung 14 einerseitsund dem Ausgangssignal der fünftenZelle D5 andererseits versorgt wird. In Analogie zu dem in 9 gezeigtenAusführungsbeispielstellt die Ausgangsfolge der vierten Zelle D4 die zweite Pseudozufallszahlenfolgedar, währenddie Ausgangsfolge der siebten Zelle D7 die erste Zufallszahlenfolgedarstellt.
    [0107] Diein den 9 und 10 gezeigten Ausführungsbeispielefür einElementarschieberegister unterscheiden sich dahingehend, dass zwischenden beiden Steuereinrichtungen zwei weitere Registerzellen D5, D6geschaltet sind, und dass am Ausgang der XOR-Steuereinrichtung 60 weitereSpeicherzellen D0 – D3ausgebildet sind, so dass ein 8-Bit-Schieberegister entsteht. Beieinem Ausführungsbeispiel wird,um einen besonders effizienten Pseudozufallszahlengenerator zu erhalten,an dem Ausgang von jeder Speicherzelle D0 – D7 eine Pseudozufallszahlenfolgeabgezapft und einer Kombinationseinrichtung zugeführt. Insbesonderesind die beiden Folgen, die von den Zellen D4 und D5 ausgegebenwerden, verschobene Versionen der Folge, die von der Zelle D6 ausgegebenwird. Ferner sind die vier Folgen, die von den Zellen D2, D1, D0und D7 ausgegeben werden, verschobene Versionen der Folge, die vonder Zelle D3 ausgegeben wird. Damit ist jede Folge der Zellen D7,D0, D1, D2, D3 zu einer Folge der Zellen D4, D5, D6 essentiell verschieden.
    [0108] Essei darauf hingewiesen, dass der Anfangszustand, mit dem das Schieberegisterinitialisiert wird, als der sogenannte Seed oder Keim, der Bezugnehmend auf 7, Element 55, erläutert wordenist, dahingehend gestaltet sein soll, dass er zumindest einen Wertfür einSpeicherelement umfasst, der ungleich Null ist, damit das Schieberegister gewissermaßen „anläuft" und nicht an denacht Ausgängenacht Nullfolgen ausgibt. Dann, wenn diese Bedingung erfüllt ist,sind alle acht Folgen maximal periodisch, d. h. haben eine Periodenlänge von 255. Fernerhat jede der acht ausgegebenen Folgen bei dem in 10 gezeigtenAusführungsbeispieldie maximale lineare Komplexität 254.Darüberhinaus sind, wie es ausgeführtworden ist, die beiden Folgen, die von den Zellen D3 und D6 ausgegebenwerden, essentiell verschieden.
    [0109] Wiees aus 10 ferner ersichtlich wird,ist hier die Speicherzelle D5 die Steuerungszelle. Wenn die ZelleD5 eine Null enthält,dann wird die Wirkung der Steuereinrichtung 60 zwischenden Zellen D3 und D4 unterdrückt.Nur das XOR zwischen den Zellen D6 und D7 findet dann Anwendung.Wenn die Zelle D5 dagegen eine 1 umfasst, kommen beide XOR-Einrichtungen 13 und 60 zurAnwendung.
    [0110] 11 zeigtein allgemeines rückgekoppeltesSchieberegister mit Speicherzellen D0, ...,Dn–1 mit einerVorwärtskopplungseinrichtungsowie mit einer Rückkopplungseinrichtung,die mit F (x0, x1,..., xn–1) bezeichnetist.
    [0111] Betrachtetsei ein allgemeines n-stufiges (oder n-zelliges) rückgekoppeltesSchieberegister überdem GrundkörperGF(2) = {0,1}. Das Schieberegister besteht aus n Speicherzellen(Flip-Flops) D0, D1,..., Dn–1 undder (elektronischen) Realisierung einer Rückkopplungsfunktion F(x0, x1, ...,xn–1).Die Rückkopplungsfunktionordnet jedem n-Tupel bestehend aus n Bits, einen eindeutigen Wertaus GF(2) zu, also den Wert 0 oder 1. In mathematischer Terminologieist F eine Funktion mit Definitionsbereich GF(2)n undZielbereich GF(2).
    [0112] DasSchieberegister wird von einer äußeren Uhrgesteuert. Mit jedem Uhrentakt wird der Inhalt der SpeicherzelleDj in die linke benachbarte Zelle Dj–1 verschoben.1 ≤ j ≤ n – 1. DerInhalt der Speicherzelle D0 wird ausgegeben.Seien die Inhalte der Speicherzellen D0,D1, ... Dn–2,Dn–1 zumZeitpunkt t gegeben durch St, St+1 ..., St+n–2,St+n–1.
    [0113] Dannenthalten die Speicherzellen einen Uhrentakt später, also zum Zeitpunkt t +1, die Bits St+1, St+2,..., St+n–1,St+n, wobei der in der Zelle Dn–1 eingeflosseneWert st+n gegeben ist durch St+n = F(St, St+1, ..., St+n–1)
    [0114] Dasn-Tupel (st, st+1,..., st+n–1)beschreibt den Zustand des Schieberegisters zum Zeitpunkt t. Das n-Tupel(s0, s1, ..., sn–1)heißtder Anfangszustand. Als Abkürzungfür dasallgemeine rückgekoppelteSchieberegister mit RückkopplungsfunktionF wird FSR(F) verwendet (FSR steht für feedback shift register). 12 zeigtein allgemeines rückgekoppeltesSchieberegister.
    [0115] Mitjedem Takt der äußeren Uhrgibt das Schieberegister ein Bit aus. Auf diese Weise kann das Schieberegistereine periodische Bitfolge S0, s1, s2, ... produzieren, eine sogenannte Schieberegisterfolge.Es seien s0, s1,..., sn–1 dieAnfangswerte der Schieberegisterfolge. Die Rückkopplungsfunktion F(x0, x1, ..., xn–1)und die Anfangswerte s0, s1,..., sn–1 bestimmendie Schieberegisterfolge vollständig.Da es nur 2n verschiedene Zustände für das Schieberegistergibt, beträgtdie Periodenlängeder Schieberegisterfolge s0, s1,s2, ... höchstens 2n.
    [0116] Einallgemeines rückgekoppeltesSchieberegister FSR(F) heißthomogen, wenn seine RückkopplungsfunktionF homogen ist, d. h. wenn F(0, 0, ..., 0) = 0 gilt. Ein homogenes,in den Anfangszustand s0 = s1 =... = sn–1 =0 versetztes Schieberegister produziert die Nullfolge. Daraus folgt,dass die Periodenlängeder Ausgabefolge eines n-stufigen homogenen Schieberegisters höchstens2n – 1betragen kann. Wenn die Periodenlänge den maximalen Wert 2n – 1 annimmt,dann nennt man die Schieberegisterfolge eine M-Folge und das Schieberegistermaximal. Es ist eine wichtige Aufgabe maximale Schieberegister zufinden.
    [0117] ZweiSpezialfälledes allgemeinen rückgekoppeltenSchieberegisters FSR(F) sind von besonderem Interesse. Der Fallbei dem die RückkopplungsfunktionF die Form
    [0118] Derandere Spezialfall liegt vor, wenn die Rückkopplungsfunktion F linearist. Dann hat F die Form F(x0,x1, ..., xn–1)= a0x0 + a1x1 + ... + an–1xn–1, wobeidie auftretenden Koeffizienten ai wiedergleich 0 oder 1, also Elemente aus GF(2) sind. In diesem Fall sprichtman von einem linearen oder linear rückgekoppelten Schieberegisterund verwendet fürdieses die AbkürzungLFSR (linear feedback shift register). Beachte, dass sowohl dielinear rückgekoppeltenals auch die quadratisch rückgekoppeltenSchieberegister homogen sind.
    [0119] Einn-stufiges linear rückgekoppeltesSchieberegister wird üblicherweisedurch ein binäresPolynom f(x) vom Grad n in einer Variablen x charakterisiert. Mannennt dieses Polynom f das charakteristische Polynom des linearrückgekoppeltenSchieberegisters. Fürdas Schieberegister schreibt man dann LFSR (f).
    [0120] DieRückkopplungsfunktionF(x0, x1, ..., xn–1) eineslinear rückgekoppeltenSchieberegisters ist ein Polynom in n Variablen x0,x1, ..., xn–1 undvom Grad 1. Demgegenüberist das charakteristische Polynom f(x) desselben linearen Schieberegistersein Polynom nur einer Variablen, nämlich der Variablen x, abervom Grad n. Es gilt f(x) = xn +F(1, x, x2, ..., xn–1).
    [0121] DieNichtlinearitätder Rückkopplungsfunktionkann somit durch relativ beliebige Ausgestaltungen der RückkopplungsfunktionF durchgeführtwerden. Hierzu wird es prinzipiell genügen, lediglich die Ausgangssignalevon zwei Speicherzel len Di und Di+1 miteinander zu multiplizieren, worausein quadratisches Schieberegister entstehen würde. Selbstverständlich können auchmehr als zwei Speicherzellenausgängemiteinander multipliziert oder irgendeiner nicht-linearen Funktionunterzogen werden. Prinzipiell kann jedoch auch eine Rückkopplungmit nur einem Ausgangssignal einer einzigen Speicherzelle durchgeführt werden,indem z. B. lediglich das Ausgangssignal der Speicherzelle D0 rückgekoppeltwird, in die Funktion F(x0) eingespeistwird und das Ausgangssignal dieser Funktion z. B. in die Speicherzelle Dn_1 eingangsseitigeingespeist wird. Eine solche nicht-lineare Funktion mit nur einemeinzigen Wert wärebeispielsweise eine Inversion, also eine logisch NOT-Funktion. Dienicht-lineare Funktion könntejedoch auch irgendeine andere Funktion sein, beispielsweise einenicht-lineare Zuordnungsfunktion oder eine kryptographische Funktion.
    [0122] Abhängig vonden Gegebenheiten kann das erfindungsgemäße Verfahren zum Erzeugen vonZufallszahlen in Hardware oder in Software implementiert werden.Die Implementierung kann auf einem digitalen Speichermedium, insbesondereeiner Diskette oder CD mit elektronisch auslesbaren Steuersignalenerfolgen, die so mit einem programmierbaren Computersystem zusammenwirkenkönnen,dass das Verfahren ausgeführtwird. Allgemein besteht die Erfindung somit auch in einem Computer-Programm-Produkt mit einemauf einem maschinenlesbaren Trägergespeicherten Programmcode zur Durchführung des erfindungsgemäßen Verfahrens, wenndas Computer-Programm-Produkt auf einem Rechner abläuft. Inanderen Worten ausgedrückt kanndie Erfindung somit als ein Computer-Programm mit einem Programmcodezur Durchführung desVerfahrens realisiert werden, wenn das Computer-Programm auf einemComputer abläuft.
    1 Vorwärtskopplungseinrichtung 2 Speichereinrichtung 3 Speichereinrichtung 4 Speichereinrichtung 5 Speichereinrichtung 6 Eingangder Vorwärtskopplungseinrichtung 7 Ausgangder Vorwärtskopplungseinrichtung 8 Rückkopplungseinrichtung 9 ersteRückkopplungseigenschaft 10 zweiteRückkopplungseigenschaft 11 Auswahleinrichtung 12 Steuerleitungfür dieAuswahleinrichtung 13 ersteSteuereinrichtung 13a Steuereingangder ersten Steuereinrichtung 14 Rückkopplungseinrichtung 14a Abzweigungspunkt 15 Ausgangfür diezweite Folge 20 Auswahleinrichtung 20a Steuereingang 20b ersterEingang 20c zweiterEingang 20d Ausgang 21 Kombinationseinrichtung 40a erstesUND-Gatter 40b zweitesUND-Gatter 41a erstesODER-Gatter 41b zweitesODER-Gatter 51 Speicherzelle 52 Speicherzelle 53 Speicherzelle 54 Speicherzelle 55 Initialisierungseinrichtung 56 Ausgang 57 ersteODER-Verknüpfung 58 zweiteODER-Verknüpfung 59a ersteRückkopplungsleitung 59b zweiteRückkopplungsleitung 59c dritteRückkopplungsleitung 60 zweiteSteuereinrichtung 61 Signalflussrichtungin der Vorwärtskopplungsein richtung 62 Kombinationseinrichtung 100 ersteSpeicherzelle 101 ZweiteSpeicherzelle 102 DritteSpeicherzelle 103 VierteSpeicherzelle 104 Fünfte Speicherzelle 105 Rückkopplungseinrichtung 106 Zufallszahlenausgabeeinrichtung 203 Umschalter 204 Steuereingang206 Ausgang 210 externeSteuereinrichtung 212 UND-Gatter 213 UND-Gatter 214 XOR-Gatter 216 Invertierer 218 XOR-Gatter 221 Einkoppel-XOR-Gatter 500 Busverschlüsselungs/Entschlüsselungs-Einheit 502 Steuerleitung 504 Steuerleitung 508 Busverschlüsselungs/Entschlüsselungs-Einheit
    权利要求:
    Claims (18)
    [1] Zufallszahlengenerator mit folgenden Merkmalen: einerMehrzahl von seriell angeordneten Speicherzellen (100, 101, 102, 103, 104); einerRückkopplungseinrichtung(105) zum Erzeugen eines Rückkopplungssignals und zumEinspeisen des Rückkopplungssignalsin eine der Speicherzellen; und einer Zufallszahlenausgabeeinrichtung(106), die ausgebildet ist, um Zustände einer Gruppe von wenigstenszwei Speicherzellen zu kombinieren, um eine Ausgabefolge zu erhalten.
    [2] Zufallszahlengenerator nach Anspruch 1, bei dem dieZufallszahlenausgabeeinrichtung (106) ausgebildet ist,um Zuständevon einer zweiten Gruppe von Speicherzellen zu kombinieren, um einezweite Ausgabefolge zu erhalten, wobei sich die zweite Gruppe vonder ersten Gruppe unterscheidet.
    [3] Zufallszahlengenerator nach Anspruch 1, bei dem dieZufallszahlenausgabeeinrichtung (106) ausgebildet ist,um Zuständeder Gruppe von wenigstens zwei Speicherzellen gemäß einerersten Kombinationsvorschrift zu kombinieren, um die Ausgabefolge zuerhalten, und um die Zuständeder Gruppe von Speicherzellen ferner gemäß einer zweiten Kombinationsvorschriftzu kombinieren, wobei sich die zweite Kombinationsvorschrift vonder ersten Kombinationsvorschrift unterscheidet.
    [4] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche, beidem eine Anzahl N von Speicherzellen vorgesehen ist; und beidem die Zufallszahlenausgabeeinrichtung (106) ausgebildetist, um eine Anzahl M von Ausgabefolgen zu erzeugen, wobei die AnzahlM größer alsdie Anzahl N ist, und wobei sich die M Ausgabefolgen voneinanderaufgrund der ihnen zugrunde liegenden Gruppen von Speicherzellenoder der ihnen zugrunde liegenden Kombinationsvorschriften voneinander unterscheiden.
    [5] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,bei dem die Rückkopplungseinrichtung(105) eine nicht-lineare Rückkopplungscharakteristik hat.
    [6] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,bei dem die Rückkopplungseinrichtung(105) wenigstens ein UND-Gatter zum UND-Verknüpfen vonZuständenvon zwei der Speicherzellen aufweist, oder bei dem die Rückkopplungseinrichtungwenigstens ein XOR-Gatter zum XOR-Verknüpfen von Zuständen vonzwei der Speicherzellen aufweist.
    [7] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,der ferner folgendes Merkmal aufweist: eine Takteinrichtungzum Takten der Speicherzellen, so dass bei einem Takt ein Zustandin in einer Verarbeitungsrichtung hinten angeordneten Speicherzelle ineine in der Verarbeitungsrichtung vorne angeordnete Speicherzelleeingespeist wird, so dass sich an einem Ausgang einer Speicherzelleansprechend auf eine Folge von Taktpulsen eine Folge von Speicherzellenzuständen ergibt.
    [8] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,bei dem die Rückkopplungseinrichtung(105) mit der Mehrzahl von Speicherzellen so gekoppeltist, dass die Rückkopplungseinrichtung(105) als Eingabe einen Zustand einer in Verarbeitungsrichtungvorne angeordneten Speicherzelle enthält, und das Rückkopplungssignalin eine in Verarbeitungsrichtung hinten angeordnete Speicherzelleeinspeist.
    [9] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,bei dem ein durch die Mehrzahl von Speicherzellen und die Rückkopplungseinrichtunggebildetes Schieberegister nicht-linear ist und ausgebildet ist,um eine maximal periodische Folge zu generieren.
    [10] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,bei dem die Anzahl von Speicherzellen eine Primzahl ist.
    [11] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,bei dem die Zufallszahlenausgabeeinrichtung (106) wenigstensein Logikgatter zum Kombinieren von Zuständen einer Gruppe von Speicherzellenaufweist.
    [12] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,bei dem die Zufallszahlenausgabeeinrichtung (106) ausgebildetist, um eine modulo 2-Addition mit Zuständen von Speicherzellen einerGruppe von Speicherzellen durchzuführen.
    [13] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,bei dem die Zufallszahlenausgabeeinrichtung (106) ein XOR-Gatterzum Kombinieren von Zuständenvon Speicherzellen einer Gruppe aufweist.
    [14] Zufallszahlengenerator nach einem der vorhergehendenAnsprüche,bei dem die Rückkopplungseinrichtungfolgende Merkmale aufweist: eine erste Kombinationseinrichtung(9) zum Kombinieren von Zuständen von Speicherzellen, umeine erste Rückkopplungseigenschaftzu erreichen; eine zweite Kombinationseinrichtung (10)zum Kombinieren von Zuständenvon Speicherzellen, um eine zweite Rückkopplungseigenschaft zu erreichen;und einen Umschalter zum Aktivieren der ersten Rückkopplungseigenschaftin einem ersten Umschaltzustand und zum Aktivieren der zweiten Rückkopplungseigenschaftin einen zweiten Umschaltzustand, wobei der Umschalter einen Steuereingangzum Erhalten eines Steuersignals von einer externen Steuerung aufweist,und wobei der Umschalter ausgebildet ist, um ansprechend auf dasSteuersignal in den ersten oder den zweiten Umschaltzustand versetztzu werden.
    [15] Zufallszahlengenerator nach Anspruch 14, bei demdas Steuersignal eine Steuerperiodendauer hat, und bei dem der Zufallszahlengeneratorferner folgendes Merkmal aufweist: eine Takteinrichtung zumTakten der Mehrzahl von seriell angeordneten Speicherzellen miteinem Takt, der eine Taktperiodendauer hat, wobei die Taktperiodendauerkleiner als die Steuerperiodendauer ist.
    [16] Busverschlüsselungsvorrichtungmit folgenden Merkmalen: einem Bus mit einer Anzahl N von parallelenBusleitungen; fürjede Busleitung, eine Verschlüsselungs- oderEntschlüsselungseinrichtungzum Verschlüsselnoder Entschlüsselneines Signals auf der Busleitung unter Verwendung eines Schlüssels für die Busleitung; einenZufallszahlengenerator mit einer Mehrzahl von seriell angeordnetenSpeicherzellen, einer Rückkopplungseinrichtungzum Erzeugen eines Rückkopplungssignalsund zum Einspeisen des Rückkopplungssignalsin eine der Speicherzellen und einer Zufallszahlenausgabeeinrichtung(106), wobei die Zufallszahlenausgabeeinrichtung (106)ausgebildet ist, um fürjede Busleitung durch Kombination von Zuständen einer Gruppe von Speicherzelleneine Ausgabefolge zu erzeugen und zu einer Einrichtung zum Entschlüsseln oderVerschlüsselnfür dieBusleitung zuzuführen,wobei die Zufallszahlenausgabeeinrichtung (106) ausgebildetist, so dass fürjede Busleitung eine Gruppe von Speicherzellen vorgesehen ist, diesich von einer Gruppe von Speicherzellen unterscheidet, die für eine andereBusleitung vorgesehen ist.
    [17] Verfahren zum Erzeugen von Zufallszahlen mit einemZufallszahlengenerator, der eine Mehrzahl von seriell angeordnetenSpeicherzellen und einer Rückkopplungseinrichtung(105) zum Erzeugen eines Rückkopplungssignals und zumEinspeisen des Rückkopplungssignalsin eine der Speicherzellen aufweist, mit folgendem Schritt: Kombinierenvon Zuständeneiner Gruppe von wenigstens zwei Speicherzellen, um eine Ausgabefolge zuerhalten.
    [18] Computerprogramm mit einem Programmcode zum Durchführen desVerfahrens gemäß Patentanspruch17, wenn das Computerprogramm auf einem Computer abläuft.
    类似技术:
    公开号 | 公开日 | 专利标题
    US9363078B2|2016-06-07|Method and apparatus for hardware-accelerated encryption/decryption
    Zimmermann et al.1994|A 177 Mb/s VLSI implementation of the international data encryption algorithm
    Barenghi et al.2012|Fault injection attacks on cryptographic devices: Theory, practice, and countermeasures
    CA2244337C|2009-01-20|Encryption processor with shared memory interconnect
    Karri et al.2002|Concurrent error detection schemes for fault-based side-channel cryptanalysis of symmetric block ciphers
    DE60222052T2|2008-05-21|Verschlüsselung gesichert gegen Angriffe durch die Analyse der Leistungsaufnahme |
    US7995749B2|2011-08-09|Cryptographic system configured for extending a repetition period of a random sequence
    US7295671B2|2007-11-13|Advanced encryption standard | hardware cryptographic engine
    EP1246389B1|2005-01-05|Vorrichtung zur wählbaren Ver- bzw. Entschlüsselung von Daten
    US6253223B1|2001-06-26|Robust random number generator
    US6691921B2|2004-02-17|Information processing device
    CA2723405C|2013-06-25|Cryptographic system including a random number generator using finite field arithmetics
    US4860353A|1989-08-22|Dynamic feedback arrangement scrambling technique keystream generator
    US7567668B2|2009-07-28|Calculating unit and method for performing an arithmetic operation with encrypted operands
    EP0855642B1|2003-05-28|Pseudozufallsgenerator mit Taktauswahl
    KR100628280B1|2007-01-31|데이타시퀀스의암호화또는해독방법
    JP4828068B2|2011-11-30|コンピュータで効率的な線形フィードバック・シフト・レジスタ
    US5077793A|1991-12-31|Residue number encryption and decryption system
    JP2013242584A|2013-12-05|暗号乱数発生器にシードを与えるための方法及び装置
    US7058178B2|2006-06-06|Synchronous stream cipher
    Nandi et al.1994|Theory and applications of cellular automata in cryptography
    Wollinger et al.2004|Security on FPGAs: State-of-the-art implementations and attacks
    TWI374649B|2012-10-11|Digital random number generator based on digitally-controlled oscillators
    JP5822970B2|2015-11-25|擬似ランダム生成、データ暗号化、およびメッセージ暗号化ハッシングのための暗号化デバイス
    Guo et al.2013|Recomputing with permuted operands: A concurrent error detection approach
    同族专利:
    公开号 | 公开日
    DE102004013480B4|2013-01-24|
    FR2868628A1|2005-10-07|
    US20050207207A1|2005-09-22|
    FR2868628B1|2007-10-12|
    US7979482B2|2011-07-12|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2005-10-13| OP8| Request for examination as to paragraph 44 patent law|
    2012-09-19| R018| Grant decision by examination section/examining division|
    2013-06-25| R082| Change of representative|
    2013-08-01| R020| Patent grant now final|Effective date: 20130425 |
    2021-10-01| R119| Application deemed withdrawn, or ip right lapsed, due to non-payment of renewal fee|
    优先权:
    申请号 | 申请日 | 专利标题
    DE200410013480|DE102004013480B4|2004-03-18|2004-03-18|Zufallszahlengenerator und Verfahren zum Erzeugen von Zufallszahlen|DE200410013480| DE102004013480B4|2004-03-18|2004-03-18|Zufallszahlengenerator und Verfahren zum Erzeugen von Zufallszahlen|
    US11/084,725| US7979482B2|2004-03-18|2005-03-18|Random number generator configured to combine states of memory cells|
    FR0502689A| FR2868628B1|2004-03-18|2005-03-18|Generateur de nombres aleatoires et procede de production de nombres aleatoires|
    [返回顶部]