Forum: FPGA, VHDL & Co. Potenzfunktion in VHDL


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


Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

ich untersuche gerade ob das RSA-Kryptosystem auf einem FPGA 
implementiert werden kann und bin jetzt an einer entscheidenden Frage 
dran...

Soweit mir bekannt ist, sind Potenzfunktionen (a^b) nur dann 
synthesefähig, wenn entweder die Basis (a) oder der Exponent (b) ein 
Vielfaches von 2 sind. Das gleiche gilt für die Modulo-Funktion
Sehe ich das soweit richtig?
Gibt es gegebenenfalls eine andere Möglichkeit eine Potenzfunktion zu 
realisieren, sodass diese nicht nur in der Simulation funktioniert, 
sondern auch auf einem echten FPGA?

Ich kann das leider nicht testen, da ich kein FPGA-Board besitze..

Hinweis:
Beim RSA Kryptosystem wird ein Text durch folgende Funktion 
verschlüsselt:
c = m^e mod n

Danke und Grüße

von Vancouver (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Du kannst jede beliebige Potenz in Hardware rechnen, z.B. durch 
wiederholte Multiplikation. Alles eine Frage des Aufwandes. Wobei RSA in 
einem endlichen Körper rechnet, oder? Da gibt es noch ganz andere 
Möglichkeiten.

Btw, du brauchst keine FPGA-Hardware zum testen. Ein HDL-Simulator 
reicht, zb. GHDL, Icarus, oder Verilator.

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Vancouver schrieb:
> Ein HDL-Simulator reicht
Er "reicht" nicht nur, sondern er ist im Grunde der erste logische 
Schritt zum lauffähigen Design.

Student schrieb:
> Ich kann das leider nicht testen, da ich kein FPGA-Board besitze..
Ein FPGA-Designer testet sein Design ganz ohne Zielhardware im 
Simulator. Der Simulator ist der Debugger für HDL-Code.

> Beim RSA Kryptosystem wird ein Text durch folgende Funktion
> verschlüsselt:
> c = m^e mod n
"mod n" könnte je nach 'n' wesentlich spannender werden als "m^e". Denn 
fertige Multiplizierer gibts auf einem FPGA. Aber keine Dividierer...

von Gustl B. (-gb-)


Bewertung
0 lesenswert
nicht lesenswert
Student schrieb:
> ich untersuche gerade ob das RSA-Kryptosystem auf einem FPGA
> implementiert werden kann und bin jetzt an einer entscheidenden Frage
> dran...

Implementieren ist sehr ungenau. Prinzipiell kann man in einem FPGA 
alles machen was man mit einer Turingmaschine eben machen kann. Die 
Frage ist dann aber wie lange ein Durchlauf dauert, wie viele Ressourcen 
man für die unterschiedlich schnellen Implementierungen braucht, ob man 
eine Pipeline bauen kann, ...

Was soll denn das RSA-Kryptosystem machen? Quasi wie ein RSA Token nur 
ab und zu mal was berechnen was dann auch gerne einige viele ms dauern 
darf oder ist das eine akademische Überlegung?

a^b kannst du zur Not in b-1 Multiplikationen berechnen, das braucht nur 
sehr wenige Ressourcen, dauert aber möglicherweise lange.

von Weltbester FPGA-Pongo (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Student schrieb:
> ich untersuche gerade ob das RSA-Kryptosystem auf einem FPGA
> implementiert werden kann
Wie möchtest du eine solche Aufgabe lösen, wenn du nicht einmal in der 
Lage bis, die einfachsten Möglichkeiten der digitalen Rechenverfahren zu 
googlen?

Selbstredend kann man mit einem FPGA alles machen, was ein Prozessor 
kann. Also auch Real-Berechnung, Iterationen, Rekursionen. Man muss es 
nur implementieren.

Das einzige, was jeweils zu diskutieren gibt, ist der Aufwand und wie 
man es im Detail löst.

von Burkhard (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Student schrieb:
> Beim RSA Kryptosystem wird ein Text durch folgende Funktion
> verschlüsselt:
> c = m^e mod n

Schon mal Die Suchmaschine Deiner Wahl bemüht? Mit "RSA + FGPA" finden 
sich zahlreiche  Paper zu dem Thema, z.B. 
http://www.ajer.org/papers/v4(06)/Q04601440151.pdf. Die Abb. 2 in diesem 
Paper zeigt eine mögliche Implementation mit 3 Multiplikator- plus einem 
"modular exponential"-Blöcken.

Bin kein Mathe-Crack, aber obige Formel sieht aus, als ob für eine 
effiziente Implementation eh erst mal umfaktoriert werden muss, 
insbesondere bei erforderlichen Wort-Breiten von 64bit.

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.

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