Hallo ich arbeite gerade an einem Projekt, bei dem ich ein "Elliptisches Kurven Kryptographie" Verfahren in Hardware implementiere. Und momentan bin ich gerade auf der Suche nach einem Algorithmus, der die Exponentiation einer Zahl implementiert (ich weiß, dass es hier um Square and Multiply geht). Jedoch hab ich hier einen Spezialfall und zwar besitzt mein Exponent fast auschließlich einsen (binär gesehen). Und ich weiß, dass ich mal einen Algorithmus gesehen habe, der für diesen Fall schneller arbeitet als der normale "Square and Multiply" Algorithmus. Nur find ich den nicht mehr bzw. weiß ich nicht mehr wie sich der nennt. Vielleicht kann mir ja jemand weiterhelfen! Danke, Andreas
Gast
#846475
Eine (Shift-)Multiplikation mit 7 (binär = 0111) wäre ja x + x*2 + x*2*2. Genausogut kannst Du aber auch x*2*2*2 - x rechnen. Also ein Shift (3 Bit) und eine Subtraktion. Ich hoffe Du kannst Dir das für Dein Problem entsprechen anpassen. Rick
Gast
#846507
Wie Rick Dangerus schon gesagt hat, kannst du für eine Multiplikation von x mit einem Muster von N mit Nullen durchsetzten Einsen auch eine Multiplikation mit 2^N (Shift) durchführen und dann für jede Null im Muster und einmal am Ende das x abziehen (jeweils mit entsprechendem Shift). Wichtig ist, dass die Nullen im Muster durch blockweises überspringen der Einsen passiert. Ein Detektor für bis zu mehreren zig Einsen am Stück müsste ohne Probleme in einem einzigen Takt ablaufen können; falls eine oder mehrere Nullen kommen, wird immer nur die erste bearbeitet. Genau genommen kannst du mit etwas mehr Hardware sogar im Voraus die Position der Nullen blockweise bestimmen, dann geht die Überprüfung noch schneller - je nachdem wieviele Nullen wirklich vorkommen.
Danke schonmal... so hab ich mir das auch schon überlegt, aber ich dachte, dass es da vielleicht noch was anderes gäbe... Konkret gehts bei mir um eine 192 bit Zahl bei der 3 Nullen vorkommen (wobei ich sogar im Voraus weiß wo die Nullen liegen - 2^192-2^64-3). Also die Detektion müsst ich demnach gar nicht durchführen (denk ich mal). Danke nochmal, Andreas
Gast
#846575
Naja dann sinds ja nur 3 Subtrahierer in Reihe, mit entsprechend geshifteten x-Werten. Vergiss nicht, einmal x selbst (ungeshiftet) abzuziehen, damit aus (100000...0) auch (01....1) wird.
Gast
#846631
Hallo, kann dir das Buch Cryptographic Algorithms on reconfigurable Hardware vom Springer Verlag empfehlen. Gruß Peter
Gast
#846637
Guckst du hier: http://en.wikipedia.org/wiki/Addition-chain_exponentiation Da in deinem Fall der Exponent fest ist (2^192-2^64-3), könntest du versuchen, mit Hilfe deines PCs die minimale Additionskette zu dieser Zahl zu finden. Damit könntest du die Exponentiation mit der minimalen Anzahl von Mulitiplikationen durchführen. Ich kann auf die Schnelle aber nicht abschätzen, ob die minimale Additionskette für diese 58-stellige Zahl überhaupt in vernünftiger Zeit gefunden werden kann. Wahrscheinlich eher nicht. Interessant sind deswegen auch die beiden Links in den References. Beide enthalten eine Übersicht über suboptimale Exponentiations- algorithmen, so dass du nach den entsprechenden Begriffen weiter- googeln kannst.
Danke für eure Hilfe!
Hi nochmal, und zwar bin ich bei der Implementierung auf einen Fehler gestoßen, der sich bei der ganzen Überlegung irgendwie eingeschlichen hat! Um bei dem Beispiel von "Rick Dangerus" zu bleiben... eine Exponentiation mit (0111) ist nicht gleich x + x*2 + x*2*2 (das wäre die reine Multiplikation mit 0111). Bei der Exponentiation (bescheuertes Wort) mit dem Exponenten 0111 muss vielmehr x*x²*x³... also ist das ganze leider nicht mit reinen Shift Operationen gelöst. Wollte das noch richtig stellen. Falls aber jemand noch irgendwelche Ideen hat, nur her damit! mfg Andreas
Gast
#847946
Jetzt ist mir erstmal klar, was Du willst: Potenzieren. Das wird, fürchte ich, nicht so einfach zu optimieren sein. Rick
Gast
#849963
Hey, letzte Woche hat Optngn ein open-source release gemacht. In dem package sind verschiedene Mathematik Operatoren vorhanden. Das vorhandene VHDL package rechnet zwar mit floating point, die verwendeten algorithmen sollten die gleichen sein. http://www.us.design-reuse.com/news/18062/floating-point-vhdl-library-open-source.html
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.