Potenzfunktion in VHDL

Student Gast #6248787
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
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Vancouver Gast #6248831
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Lothar M. Moderator (Firma: Titel) Persönliche Seite #6248935
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...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Gustl B. #6248971
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Weltbester FPGA-Pongo Gast #6248987
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Burkhard Gast #6249091
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 Zitieren Bearbeiten Löschen Beitrag melden
Weltbester FPGA-Pongo Gast #6290822
Lesenswert?
• ▲
▼ 
Student schrieb:
> ich untersuche gerade ob das RSA-Kryptosystem auf einem FPGA
> implementiert werden kann und bin jetzt an einer entscheidenden Frage
> dran...

"Kryptofunktion auf dem FPGA-Testen", riecht verdächtig nach einer 
Projektanfrage, die uns vor kurzem angetragen wurde.
@TE: Du arbeitest nicht zufällig für eine schwäbische Firma?
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren