Die Primitivwurzel history menue Letztmalig dran rumgefummelt: 12.07.25 02:55:34

RSA-Verfahren & Einwegfunktionen

Grafische Darstellung der Primitivwurzel

Als Primitivwurzeln werden in der Zahlentheorie, einem Teilgebiet der Mathematik, bestimmte Elemente von primen Restklassengruppen bezeichnet. Die definierende Eigenschaft einer Primitivwurzel ist, dass jedes Element der primen Restklassengruppe als Potenz der Primitivwurzel dargestellt werden kann.
MODULO-Wurzel Primitivwurzel für gegebene Ausdrücke suchen ... Defintion ... beliebiger Teilnehmer entnimmt ein Schloss samt Teilschlüssel

 

Primitivwurzel

Primitivwurzel berechnen Uni Mannheime

 

Definition Primitivwurzel

Fertigstellung des Sclüssels zum öffentlichen Schloss

 

Generieren des Schlüssels

Ein Angreifer kennt zwar g, p, A, B, aber nicht a oder b. Die Berechnung des privaten Schlüssels aus dem öffentlichen ist aufgrund des diskreten Logarithmusproblems sehr schwer – genau das macht den Algorithmus sicher.
... gesucht ist der Funktionswert, welcher auf die unten angegebene Funktion möglichst viele verschiedene Ergebnisse erzielt.


Modulo-Funktionswert-Palette auf 19
  • f (x) = gx mod p mit den Parametern g (Generator, Basis) und p (Primzahl)
  • Bps.: 3 ist  Primitivwurzel  mod 19, d.h. bei den Funktionswerten sind alle x wieder vertreten (große Vielfalt ➔ sehr gut)
    30 mod 19 = 1 35 mod 19 = 15 310 mod 19 = 16 315 mod 19 = 12
    31 mod 19 = 3 36 mod 19 = 7 311 mod 19 = 10 316 mod 19 = 17
    32 mod 19 = 9 37 mod 19 = 2 312 mod 19 = 11 317 mod 19 = 13
    33 mod 19 = 8 38 mod 19 = 6 313 mod 19 = 14 318 mod 19 = 1
    34 mod 19 = 5 39 mod 19 = 18 314 mod 19 = 4
  • Bps.: 7 ist keine Primitivwurzel mod 19. Es gibt nur die Funktionswerte 1, 7, 11 (geringe Vielfalt ➔ sehr schlecht)
    70 mod 19 = 1 75 mod 19 = 11 710 mod 19 = 7 715 mod 19 = 1
    71 mod 19 = 7 76 mod 19 = 1 711 mod 19 = 11 716 mod 19 = 7
    72 mod 19 = 11 77 mod 19 = 7 712 mod 19 = 1 717 mod 19 = 11
    73 mod 19 = 1 78 mod 19 = 11 713 mod 19 = 7 718 mod 19 = 1
    74 mod 19 = 7 79 mod 19 = 1 714 mod 19 = 11
  • f (x) = gx mod p ist eine  Einwegfunktion, d.h. es gibt keine Umkehrfunktion.
  • Die Suche nach dem Exponenten x wird als  Diskretes Logarithmusproblem  bezeichnet. Dieses ist bei großen Primzahlen sehr schwer zu lösen (nur mit Brute Force).
  • 1024 Bit Primzahl (309 Dezimalstellen):
    17854200324581121127416722829736119230388632103607 42768891456915226345258201856142784995625921341889 95169731066418203258297035264969457638591284906658 91240831976315691295148602076106909913261919448900 68751082172475137152719743832961428058464057838451 70862140174184507256128825312324419293575432423822703857091
  • Modulo-Division mit dem Casio Classpad: Aktion ➔ Berechnungen ➔ mod ➔ mod(9^7,11)



zur Hauptseite
© Samuel-von-Pufendorf-Gymnasium Flöha © Frank Rost 16. April 2025 um 17.17 Uhr

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)