Wieviel bzw welche Gruppen(Abelsche)- definitionen sind bekannt?

28.09.2024, 15:06

Protolus

Wieviel bzw welche Gruppen(Abelsche)- definitionen sind bekannt?

Kontext:

Um ein algebraisches Gebilde in Form eine (Abelschen) Gruppe zu erhalten, sind zwei Dinge nötig:

Eine wohldefinierte Menge von Elementen
$\begin{eqnarray*} M=\left\{ .... \right\} \end{eqnarray*}$
und
eine Verknüpfung der Elemente, die den 4(5) Axiomen einer Gruppe gehorcht;

$\begin{eqnarray*} \text{ Assoziativität: } \forall a,b,c \in M : a + (b+ c) =(a + b)+ c \end{eqnarray*}$
$\begin{eqnarray*} \text{ Neutrales Element: }\exists e\in M\forall a : a+ e = e+ a =a \end{eqnarray*}$
$\begin{eqnarray*} \text{ Inverses Element }\forall a \in M\exists a^{ -1 }\in M: a+ a^{ -1 }=e \end{eqnarray*}$
$\begin{eqnarray*} \text{ Abgeschlossenheit: }\forall a,b \in M : a+ b \in M \end{eqnarray*}$

Zusätzlich für Abelsche Gruppe:

$\begin{eqnarray*} \text{ Kommutativität }\forall a,b \in M : a+ b =b+ a \end{eqnarray*}$

Anmerkung:
Aus irgendeinem Grund zeigt der Latex-Interpreter hier im Forum das Latex-Verknüpfungszeichen ("\comp" einen Kringel) nicht an.

Daher repräsentiert das "+" hier nicht die einfache arithmetische Addition, sondern die spezielle Gruppenoperation bzw Verknüpfung.

Problem:
Als ich tiefer in die Gruppentheorie einstig und erforschte, welche mathematisch/logischen Eigenschaften eine Menge und eine Verknüpfung besitzen müssen, um
die 4(5) Axiome einer Gruppe zu erfüllen und nach Beispielen suchte, stellte ich zu meinem Erstaunen fest: Außer der Definition einer Gruppe auf einer elliptischen
Kurve (Kryptographie) konnte ich kein weiteres Beispiel einer Gruppe (Menge, Verknüpfung) finden.

Ich kann nur im Internet also Google, Youtube Beiträge und Vorlesungen, Wikipedia usw recherchieren und da kann man unzählige Erklärungen finden, was
eine algebraische Gruppe ist, aber keine einzige, weitere Menge und Verknüpfung für eine Gruppe.

Daher meine Frage an die Spezialisten:
Wie viele bzw welche Mengen und Verknüpfungen, die den 4(5) Axiomen einer Gruppe gehorchen, sind bekannt?

Sind Mengen und Verknüpfungen, die den 4(5) Axiomen einer Gruppe gehorchen, einfach oder schwer zu finden (bzw zu definieren)?

28.09.2024, 18:46

Elvis

Auf diesen Beitrag antworten »

Mehr als genug abelsche Gruppen sind z.B. Vektorräume (V,+), Körper (K,+) und (K\{0},*) und Algebren, z.B. Martixalgebren (M,+). Eine Liste kleiner Gruppen findest du bei Wikipedia, wenn du dort nach Liste kleiner Gruppen suchst. Es gibt dicke Bücher über Lineare Algebra, Algebra und Zahlentheorie, da findest du unendlich viele interessante Beispiele.
Der Kringel ist ein kleiner Kreis und schreibt sich \circ

29.09.2024, 14:30

Protolus

Auf diesen Beitrag antworten »

Danke zunächst für die Antwort.
Die angesprochene Liste ist meinem Eindruck nach eine Typisierung der Gruppen aber leider nicht das, was ich suche.

Vielleicht hilft ein Beispiel:
In der ECC (Elliptic Curve Cryptography) kommt eine Gruppe, die auf einer elliptischen Kurve definiert wird, zum Einsatz.

Alle Punkte auf der Kurve sind die Elemente einer Menge M{}.
Die Elemente(Punkte auf der Kurve) werden definiert durch die polynomiale Funktionsgleichung:

$\begin{eqnarray*} y^2 =x^{ 3 }+ax+b \end{eqnarray*}$

In dieser Gruppe existieren zwei additive Verknüpfungen der Elemente, einmal für
die Addition eines Punktes mit sich selbst (Punktverdoppelung) und einmal die
Addition zweier verschiedener Punkte:

Addition zweier verschiedener Punkte: (P(x,y),Q(x,y)

$\begin{eqnarray*} s=\frac{ y_{ P }-y_{ Q } }{ x_{ P }-x_{ Q } } \end{eqnarray*}$
$\begin{eqnarray*} x_{ R }:= s^2 -x_{ P } -x_{ Q } \end{eqnarray*}$
$\begin{eqnarray*} y_{ R } := -y_{ P }+s(x_{ P }-x_{ R }) \end{eqnarray*}$

Punktverdoppelung: P(x,y)

$\begin{eqnarray*} s=\frac{ 3 x^2_{p }+a }{ 2y_{ P } } \end{eqnarray*}$

Das "a" wird aus der Kurvengleichung entnommen!!

$\begin{eqnarray*} x_{ R } :=s ^2-2x_{ P } \end{eqnarray*}$
$\begin{eqnarray*} y_{ R } := -y_{ P }+s(x_{ P }-x_{ R }) \end{eqnarray*}$

Ich suche Abelsche Gruppen außerhalb von Vektor und Matrizen,
bei denen die Definition der Menge und die Gruppenoperation(en)
in arithmetischer Form (wie im oben genannten Beispiel) angegeben sind.

Fals Du da eine Tipp (Internet oder Buch bzw ISBN) hättest, wäre ich Dir sehr verbunden.

29.09.2024, 17:37

Elvis

Auf diesen Beitrag antworten »

In der Algebra interessiert man sich für Strukturen, z.B. Gruppen, meist nur bis auf Isomorphie. Wenn Du mehr über konkrete Gruppen wissen willst, dann nimm konkrete Ringe wie die ganzen Zahlen $\begin{eqnarray*} \mathbb (Z,+,*) \end{eqnarray*}$ oder endliche Restklassenringe $\begin{eqnarray*} (\mathbb Z/m\mathbb Z,+,*) \end{eqnarray*}$ . Für m=p eine Primzahl sind das endliche Körper $\begin{eqnarray*} (\mathbb F_p,+,*) \end{eqnarray*}$ , die man algebraisch durch Adjunktion einer Nullstelle eines irreduziblen Polynoms vom Grad n zum Körper $\begin{eqnarray*} \mathbb F_q,q=p^n \end{eqnarray*}$ erweitern kann. Damit sind im Prinzip alle endlichen Körper bekannt, in jedem der unendlich vielen Einzelfälle kann man ganz konkret rechnen. Beachte auch den Hauptsatz über endlich erzeugte abelsche Gruppen. (Siegfried Bosch, "Algebra") Beachte auch den Klassifikationssatz für endliche einfache Gruppen. https://www.spektrum.de/kolumne/endliche...-beweis/2137146
Für galoische Körpererweiterungen L/K besteht die Galoisgruppe aus Körperisomorphismen von L nach L, die K punktweise fest lassen. Vielleicht ist der Gruppenbegriff im 19. Jahrhundert gerade aus diesen Gruppen entstanden, jedenfalls steht die Galoistheorie heute im Zentrum der modernen Algebra. Der Hauptsatz der Galoistheorie beschreibt die Verbandsantiisomorphie zwischen dem Untergruppenverband der Galoisgruppe und dem Teilkörperverband von L/K. Nicht nur die Algebra sondern auch die Arithmetik galoischer Zahlkörper wird maßgeblich durch die Galoisgruppe bestimmt, wie David Hilbert, ich und tausend andere Zahlentheoretikerinnen im 20. Jahrhundert gezeigt und angewendet haben - konkreter kann man nicht rechnen. (Jürgen Neukirch, "Algebraische Zahlentheorie") In diesem Zusammenhang trifft man auch auf algebraische Funktionenkörper, die sich manchmal ähnlich, manchmal anders als algebraische Zahlkörper verhalten. Funktionentheorie und Riemannsche Flächen sind notwendige Hilfsmittel und eigenständie Forschungsgebiete. Ganz wichtig seit Kurt Hensel und Helmut Hasse sind auch die p-adischen Zahlkörper und ihre Analysis. (Um das alles zu verstehen, wirst du ca. 50 Jahre brauchen, in diesem Zeitraum wirst du auch in der Lage sein, selbständig nach Literatur zu suchen.)

Die grundlegenden physikalischen Theorien, Relativitätstheorie und Quantentheorie(QM, QED, QCD, QFT), kann es ohne passende Gruppen gar nicht geben. Jeder Physiker rechnet heute mit Gruppen, in der Quantentheorie hat anfangs überrascht, dass die Gruppen, die unsere Naturgesetze beschreiben, oft nicht abelsche sind, aber inzwischen hat man sich daran gewöhnt, dass die Welt nicht so simpel sein muss, wie man sie sich vorstellt.

Du hattest auch eingangs gefragt, wie viele Gruppen bekannt sind. Es sind richtig viele, denn die Gesamtheit der Gruppen (bis auf Isomorphie) ist so übermächtig groß, dass sie in der Mengenlehre keine Menge sondern eine echte Klasse ist.

29.09.2024, 20:36

Elvis

Auf diesen Beitrag antworten »

Wikipedia ist wie immer als Ergänzung nützlich: https://de.wikipedia.org/wiki/Gruppe_(Mathematik)

30.09.2024, 21:06

Protolus

Auf diesen Beitrag antworten »

Vielen Dank für die ausführliche Antwort, aber mein Problem ist damit leider
noch nicht gelöst.

Mit der in der ECC benutzten Gruppe kann man den Kern jedes kryptographischen
Systems erstellen:

Eine, mit einem Geheimnis verbundene, mathematische "Einwegfunktion".

Bei der ECC besteht die Einwegfunktion aus der Skalarmultiplikation eines "Generators" G
mit einem sehr großen Faktor p >= 256 bit.

Die Einwegfunktion kommt dabei dadurch zu Stande, dass die Berechnung des Produktes P = G * p mittels wiederholter
Addition des Punktes P(x,y) mit Hilfe des "Verdoppeln und addieren"-Algorithmus effizient gelöst werden
kann, während für die Bestimmung des Faktors p selbst bei bekannten Generator G und bekanntem P keine
geschlossene Mathematik und keine iterative Lösung bekannt ist.
"p" ist zB in der ECDSA (Elliptic Curve Digital Signature Algorithm) der private, geheime
Schlüssel, während "P" den öffentlichen Schlüssel darstellt.

Die additive Gruppenoperation der in ECC verwendeten Gruppe hat aber einen Nachteil:
ECC wird im Bereich Restklassen angewandt und es kommt daher die Modulo-Arithmetik
zur Anwendung.
In der Modulo-Arithmetik gibt es Algorithmen für Addition, Subtraktion und Multiplikation aber
keinen Algorithmus für die Division.
Man ersetzt die Division durch die Multiplikation mit dem "multiplikativen Inversen".
Doch dieses "Inverse" muss aufwändig iterativ (erweiterter Euklid..) ermittelt werden.

Die Punkt-Addition der in ECC verwendeten Verknüpfung enthält aber je Verknüpfung zwei Divisionen
Dies macht einen großen Rechenaufwand bei der ECC und beschränkt sehr deren Einsatzgebiete.

Meine Überlegung war nun, dass die Tatsache, dass diese Gruppe in ECC trotz ihres schweren "Handicaps"
immer noch verwendet wird, dafür spricht, dass keine Abelsche Gruppe bekannt ist, in deren
Verknüpfungen keine Division enthalten ist.
Ansonsten würde diese längst in zB ECC angewandt, um das "Handicap" des hohen Rechenaufwandes zu beseitigen.

Ich machte mich an´s Werk und habe tatsächlich eine Abelsche Gruppe abgeleitet, in deren
Verknüpfungen keine Division enthalten ist.

Und ich bin jetzt ehrlich:

Ich möchte eigentlich nur wissen, ob mir da mit der Ableitung dieser speziellen Abelschen Gruppe etwas
besonderes gelungen ist oder ob, wenn ich zB Dir als Zahlentheoretiker den Auftrag gebe, mir
eine Abelsche Gruppe zu liefern, in deren Verknüpfung keine Division enthalten ist, ob Du mir aus
dem Stehgreif so eine Gruppe nennen kannst.

Wenn es so einfach wäre, warum wurde die in der ECC eingesetzte Gruppe nicht längst ersetzt?

Die Gruppe der ganzen Zahlen (Z,+,*) zählt nicht, da man mit ihr keine Einwegfunktion erstellen
kann, die die in der Kryptographie geforderte Sicherheit gewährleisten kann.

Da man Algorithmen, die ein praktisches Problem lösen, neuerdings patentieren kann, lass ich gerade
die Patentfähigkeit prüfen.
Daher bitte ich um Verständnis dafür, dass ich diese Gruppe hier nicht öffentlich machen kann.

01.10.2024, 09:59

Elvis

Auf diesen Beitrag antworten »

Spezielle Anwendungen mathematisch-naturwissenschaftlicher Theorien interessieren mich nicht sonderlich. Das bisschen Zeit, das ich noch habe, verwende ich auch weiterhin auf reine Mathematik und Philosophie.
Zu einer Gruppe gehört genau eine Operation, was man auf welchen Strukturen algorithmisch machen kann, ist eine ganz andere Frage. Wenn in einer bestimmten Struktur jede Rechnung algorithmisch leicht durchgeführt werden kann, dann eignet sie sich wohl eher nicht für die Kryptographie.

01.10.2024, 13:59

URL

Auf diesen Beitrag antworten »

Mir ist jetzt nicht ganz klar, was du gefunden hast. Eine abelsche Gruppe, in der das Problem diskreter Logarithmen hart ist? (Sowas haben wir schon eine Weile, letztlich El Gamal auf endlichen Körpern.)
Oder eine Gruppe mit einer andersartigen Einwegfunktion? In jedem Fall stellt sich die Frage nach einem Beweis für deren Härte.

Die Effizienz der EC-Algorithmen ist so schlecht nun auch wieder nicht, bei vergleichbarem Sicherheitsniveau sind sie trotz der aufwendigeren Arithmetik effizienter als RSA, einfach weil die Schlüssellängen deutlich kleiner sind. Hängt natürlich auch von der verwendeten Kurve ab, aber hauptsächlich, weil für manche die Arithmetik in Hardware gegossen wurde.

Grundsätzlich stellt sich die Frage, ob man das DL-Problem strategisch noch verfolgen will, wenn alle über Postquantenalgorithmen reden.

01.10.2024, 15:27

Protolus

Auf diesen Beitrag antworten »

Hallo Elvis,

Meine ursprüngliche Frage hätte lauten müssen:
Wie viele Abelsche Gruppen sind für den Einsatz in der Kryptographie geeignet?

Daß Sie das als reinen Zahlentheoretiker nicht so sehr interessiert kann ich nachvollziehen.
Dank Ihnen trotzdem für Ihre Antworten.

Zum Abschluss:

Aus der Tatsache, dass die in der ECC verwendete Abelsche Gruppe, die den großen
Nachteil eines hohen Rechenaufwandes besitzt, bisher noch immer nicht ersetz
wurde, schließe Ich, dass diese, auf einer elliptischen Kurve definierten Gruppe
die bisher einzige Abelsche Gruppe war, die in der Kryptographie eingesetzt werden konnte.

Ich habe dem Zufolge eine weitere Abelsche Gruppe gefunden, die in der Kryptographie
eingesetzt werden kann und die bei gleicher Sicherheit einen um Größenordnungen niedrigeren
Rechenaufwand benötigt.

Diese Entdeckung besitzt großes "monetäres" Potential.

Ich habe diese Gruppe im Rahmen von ECDSA bereits in Software gegossen und es
"funktioniert" alles einwandfrei.

Für Sie als Theoretiker dürfte interessant sein, dass meine Abelsche Gruppe auf einem seit
gut 200 Jahren bekannten mathematischen Problem beruht und die Sicherheit in Bezug auf
Kryptographie aus der Tatsache zieht, daß dieses Problem besten untersucht aber bisher
nicht gelöst ist.

Sollte sich mein Gruppenalgorithmus als nicht patentierbar oder zu vulnerabel
herausstellen, werde ich diesen hier veröffentlichen.

Ansonsten muss die Welt bis zur Patentoffenlegung warten:-))

Viele Grüße

01.10.2024, 16:45

URL

Auf diesen Beitrag antworten »

ECDSA, also tatsächlich diskreter Logarithmus.
Hast du mal die bekannten Berechnungsmethoden Babystep-Giantstep, Pohling-Hellmann, Pollard-rho mit deiner neuen Gruppe probiert?

01.10.2024, 18:43

Protolus

Auf diesen Beitrag antworten »

URL hat geschrieben:

Zitat:

Mir ist jetzt nicht ganz klar, was du gefunden hast.

Ich habe eine Funktion (Kurve in einem zweidimensionalen Koordinatensystem) gefunden, die eine
Menge M = {P(x,y)....} Punkte definiert und die eine Verknüpfung der Elemente ermöglicht, die allen 5 Axiomen einer Abelschen Gruppe gehorcht.

Die Funktionsgleichung ist nicht polynomial !!!

Seien:

P und Q zwei Punkte
P = (xp,yp)
Q = (xq,yq)
R = (xr,yr)
+ die Addition zweier Punkte
0 das neutrale Element
. die skalare Multiplikation

Für die Gruppen-Operation gelten folgende Rechenregeln:

P + Q = Q + P
P + P = 2 x P (keine extra Operation für Punktverdopplung)
P + 0 = P
0 - P = -P
0 + (- P) = - P
P + (- Q) = P - Q
(P + Q) + R = P + (Q + R)
(P + Q) . x = P . x + Q . x

Die skalare Multiplikation eines Punktes P erfolgt durch wiederholte Addition:

P . x = P + ... + P

Die zwei zentralen Punkte in der Kryptographie sind ja Sicherheit und Performance.
Die Einführung eines neue kryptographischen System wird durch die Frage der Sicherheit sehr erschwert.
Denn um diese bewerten zu können, muss das neue System ausgiebig studiert und analysiert werden.
Dies ist mit großem Aufwand an Zeit und Geld verbunden und immer eine Kosten- Nutzenfrage.

Die Problematik der Feststellung der Sicherheit entfällt bei meiner Gruppe gänzlich.
Der Grund:
Meine Gruppe baut auf einem seit mehr als 200 Jahren bekannten mathematischen
Problem auf, das immer noch nicht gelöst worden ist.

Das DLP meiner Gruppe ist definitiv "härter" als das in der ECC, da die Sicherheit
(DLP-härte) meiner Gruppe darauf beruht, dass ein mathematisches Problem seit
mehr als 200 Jahren von unzähligen Mathematikern eingehend studiert und
analysiert aber nicht nicht gelöst worden ist.
Dahin gegen ist erst Seit ungefähr 1985 (40 Jahren) bekannt, dass das Elliptische
Kurven DL-Problem für die Kryptographie genutzt werden kann.

Die "DLP-Härte" meiner Gruppe ist also bereit mehr als ausgiebig erforscht und es
bedarf keines weiteren Aufwandes mehr, um mein System einzuführen.

Performance:

Hier eine Gegenüberstellung der nötigen Rechenschritte zwischen ECC und meiner Gruppe.

Arithmetische Operation ECC versus HM (meine)
---------------------------------------------------------------
Additionen ECC = 1 , HM = 2

Subtraktionen ECC = 6, entfällt = 0

Multiplikationen ECC = 4, HM = 3

Divisionen ECC ?, HM entfällt = 0

Man beachte, dass in meiner Gruppenoperation keine Division enthalten ist, so dass die
aufwändige mit Hilfe des erweiterten Euklidschen Algoriithmus = EEA Ermittlung der
multiplikativen Inversen entfällt.

Die Anzahl arithmetischer Operation für die "Division" kann bei ECC nicht angegeben
werden, da die Laufzeit des EEA nicht konstant ist.

Da meine Gruppe die gleichen Funktionen aufweist wie die ECC-Gruppe, kann ECC durch mein
System direkt ohne große Umprogrammierung ersetzt werden.
Es müsste lediglich eine einzige Softwarefunktion ausgetauscht werden.

Müßig zu erwähnen, dass ich mein System bereits in Software gegossen und ausgiebig
getestet habe und alles "funktioniert" perfekt.

Falls Du weitere Fragen haben solltest, stehe ich dir gerne zur Verfügung.

02.10.2024, 14:39

Protolus

Auf diesen Beitrag antworten »

URL hat geschrieben:

Zitat:

Hast du mal die bekannten Berechnungsmethoden Babystep-Giantstep, Pohling-Hellmann, Pollard-rho mit deiner neuen Gruppe probiert?

Wenn man in der ECDSA-Chiffre die beiden Funktionen zur Punktverdopplung bzw Punktaddition einfach eins zu eins durch meine Gruppenoperation ersetzt, erhält man HMDSA.

"HM", das bin bei aller Bescheidenheit Ich. :-))

Die von dir genannten Algorithmen führen nur bei kryptographischen Systemen, die auf der einfachen, arithmetischen Multiplikation beruhen zum "Erfolg".

Bei meiner Gruppe wird aber, wie bei der ECC auch, die skalare Multiplikation durch mehrfache, rekursive Addition realisiert.

Zudem ist diese Addition (Gruppenoperation) bei meiner Gruppe keine einfache arithmetische Addition sondern wie bei der ECC auch, eine spezielle Funktion.

"Meine Gruppe" ist also gegen Angriffe mit den von Dir genannten Algorithmen genauso immun wie die ECC.

Dazu kommt, dass meine Gruppe, wie schon erwähnt, auf einem ungelösten Problem der Mathematik beruht.

Die Mathematiker suchen seit 2oo Jahren bis heute nach einer geschlossenen Mathematik und einem Algorithmus zur Lösung dieses speziellen Problems (Nein, es ist nicht das Faktorisierungsproblem).

03.10.2024, 11:23

URL

Auf diesen Beitrag antworten »

Die von mir genannten Methoden kann man doch bei beliebigen abelschen Gruppen zur Lösung des DL-Problems anwenden. Ich verstehe deinen Einwand also nicht verwirrt

Neue Frage »

Antworten »

Wieviel bzw welche Gruppen(Abelsche)- definitionen sind bekannt?

Verwandte Themen