mikrocontroller.net

Forum: FPGA, VHDL & Co. Exponentiation


Autor: Andreas Auer (Firma: Embedded Microtec) (andi) Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Rick Dangerus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas Auer (Firma: Embedded Microtec) (andi) Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

kann dir das Buch Cryptographic Algorithms on reconfigurable Hardware 
vom Springer Verlag empfehlen.

Gruß

Peter

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas Auer (Firma: Embedded Microtec) (andi) Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für eure Hilfe!

Autor: Andreas Auer (Firma: Embedded Microtec) (andi) Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Rick Dangerus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jetzt ist mir erstmal klar, was Du willst: Potenzieren.
Das wird, fürchte ich, nicht so einfach zu optimieren sein.

Rick

Autor: anonymous (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.