Das Problem des diskreten Logarithmus

Das eben beschriebene Kryptosystem kann gebrochen werden, wenn für tex2html_wrap_inline892 das folgende Problem des diskreten Logarithmus gelöst werden kann.

Es sei G eine abelsche endliche Gruppe, in der ein Element g fixiert ist. Es wird nun zu gegebenem tex2html_wrap_inline898 ein tex2html_wrap_inline900 gesucht mit

displaymath902

bzw., falls G additiv geschrieben wird, mit tex2html_wrap_inline906 .

Der Name kommt natürlich daher, daß in tex2html_wrap_inline908 für tex2html_wrap_inline910 die Zahl x der Logarithmus von y (zur Basis 10) ist. Dies Problem wurde zunächst für die multiplikative Gruppe tex2html_wrap_inline842 aufgeworfen. Hier gibt es unterdes Verfahren, die eine Lösbarkeit in der Zeit

displaymath920

vorhersagen. Für tex2html_wrap_inline892 sind die Lösungsalgorithmen bisher noch weniger erfolgreich, so daß dies Kryptosystem als möglicher Ersatz für das RSA-Verfahren in Betracht gezogen wird. Mehr dazu sowie über in diesem Kontext praktikabel erscheinende Signierverfahren findet man bei Koblitz [K 2], S.133.