Elliptische Kurven: Berechnung von k * P = O |
| 19.01.2014, 14:44 | Tatsu | Auf diesen Beitrag antworten » | ||||||
| Elliptische Kurven: Berechnung von k * P = O Ich habe im Anhang stehende Aufgabe und bräuchte dabei etwas Hilfe. Leider habe ich kaum Ahnung von elliptischen Kurven und weiß nicht so ganz wo ich ansetzen soll. Meine Ideen: Aufgabe a) habe ich bereits gelöst und das war auch kein Problem. Nun steht aber noch Aufgabe b) an. Hier habe ich einfach keine Ahnung wo ich anfangen soll. Ginge es darum den dritten Punkt auf einer Gerade durch 2 Punkte zu berechnen, wäre die Lösung ja klar (mit der Addition und der passenden Formel wie im Bildschirmfoto zu sehen). Wie finde ich allerdings nun k? Gibt es dafür eine Formel? Scheinbar kann man k*P=Q mit verschiedenen Algorithmen (Babystep-Giantstep u.a.) berechnen. Aber es ist ja kein Q gegeben, oder sehe ich das falsch? Hat jemand einen Tipp, wonach ich suchen kann oder wie ich auf eine Lösung kommen kann? |
||||||||
| 19.01.2014, 16:04 | Captain Kirk | Auf diesen Beitrag antworten » | ||||||
Hallo, dein Problem bei der b) liegt wohl weniger am mangelndem Verständnis von Elliptischen Kurven sondern am mangelndem Verständnis von Gruppentheorie. Was du hier bestimmen sollst ist die Ordnung von P bzw. Q. Nach dem Satz von Lagrange ist diese ein Teiler der Gruppenordnung, die du ja in a) berechnet hast. Man berechnet schrittweise alle Vielfachen von P bzw. Q bis das erste . Nach dem obigen genügt es sogar sich Teiler der gruppenordnung anzuschauen.
Es gibt nicht für alles und jeden eine Formel in der Mathematik. Wenn dem so wäre, könnte wir Mathematik bleiben lassen und allers Rechnern überlassen. Aber es gibt einige nützliche Formeln dazu, zumeist es der Gruppentheorie.
Das hat mit der Aufgabe gar nichts zu tun. |
||||||||
| 19.01.2014, 17:17 | Tatsu | Auf diesen Beitrag antworten » | ||||||
Danke für die Antwort! Ich habe mich nun in Gruppentheorie etwas eingelesen, aber so richtig viel verstanden habe ich leider noch nicht. Ist ein komplett neues Thema, damit hatte ich bisher noch nie etwas zu tun. Wie berechnet man denn Vielfache von P? Und stimmt es, dass die Ordnung der Gruppe 33 ist, wenn die Gruppe 32 Elemente hat? Ich denke, ich brauche einfach nochmal einen Schubs in die richtige Richtung, und ich denke, dass das Problem auch ist, dass ich noch nicht zu 100 Prozent verstanden habe, was in der Aufgabenstellung gefordert ist. |
||||||||
| 19.01.2014, 17:29 | Captain Kirk | Auf diesen Beitrag antworten » | ||||||
Wieso beschäftigst du dich mit elliptischen Kurven? Ich würde mal vermuten aufgrund der kryptographischen Anwendungen. Dann ist aber Gruppentheorie essentiell, insbesondere zum Verständnis symmetrischer Verfahren.
Mittels der Definitionen aus der Aufgabenstellung, z.B. ist 2P=P+P.
Wie bitte? Der Ordnung einer Gruppe ist die Anzahl der Gruppenelemente. Wieso addierst du also 1? |
||||||||
| 19.01.2014, 18:00 | Tatsu | Auf diesen Beitrag antworten » | ||||||
Ich beschäftige mich mit elliptischen Kurven, weil ich das für eine einzige Aufgabe in meinem Kryptographie-Kurs an der Uni brauche. Insofern ist sicherlich auch nicht vorgesehen, dass ich mich umfassend in Gruppentheorie einlese, weil es einfach mal nur 5% der Gesamtleistung im Kurs ausmachen soll. Eine Anwendung ist überhaupt nicht geplant, nur die Lösung der Übrungsaufgabe. Wie man das Vielfache von einem Punkt ausrechnet, ist mir leider immer noch nicht klar. Wenn jetzt nun z. B. mein Punkt (8,12) ist, was ist denn dann 2P? Und wie berechnet man das? Es ist ja sicherlich nicht "einfach" jeweils das doppelte, also (16,24), oder? |
||||||||
| 19.01.2014, 18:07 | Captain Kirk | Auf diesen Beitrag antworten » | ||||||
Natürlich nicht. Ernsthafte Frage: Liest du die Angabe nicht? Mehr als die Hälfte des Textes behandelt wie man Punkte addiert. |
||||||||
| Anzeige | ||||||||
|
|
||||||||
| 19.01.2014, 18:35 | Tatsu | Auf diesen Beitrag antworten » | ||||||
Ok, ich hab den Fehler nun erkannt. Ich hab nun die Formel unter 3.2 angewendet, aber Dezimalzahlen herausbekommen. Als 2P habe ich nun (20,56|16,25) errechnet. Ich habe als P (2|6) genommen, wie in Aufgabe b) gefordert. Kann das so stimmen? Oder mach ich irgendwas falsch? Wenn ich das nun weiterrechne (3P), kommen recht hohe Zahlen raus. Irgendwie habe ich das Gefühl, dass das so nicht stimmt. Mein Rechenweg ist: P (2|6) » = (3x^2 + 3) / (2y) mod 23 = (3*2^2 + 3) / (2*6) mod 23 = 5/4 xr = (5/4)^2 - 2*2 mod 23 = 20,56 ≈ 21 yr = - 5/4 (21 - 2) - 6 = 16,25 |
||||||||
| 19.01.2014, 18:49 | Captain Kirk | Auf diesen Beitrag antworten » | ||||||
Dann hast du die Formel falsch angewandt. Im Körper GF(23) gibt es keine Dezimalzahlen. Bitte insbesondere Invertieren modulo 23 nachschlagen. (Das gehört übrigens zu den Grundlagen der Gruppentheorie) So als Tipp: |
||||||||
| 19.01.2014, 21:11 | Leopold | Auf diesen Beitrag antworten » | ||||||
@ Chef der Enterprise Ich komme auch auf die Gruppenordnung 33, wenn auch aus anderem Grund als Tatsu. Neben den 32 Lösungspaaren der Gleichung gibt es ja noch das Element O. |
||||||||
| 19.01.2014, 23:57 | Captain Kirk | Auf diesen Beitrag antworten » | ||||||
@Leopold Mein Rechner kriegt das auch raus. Fun Fact: 33 ist die maximale Anzahl an Punkten für eine elliptische Kurve in GF(23) nach Hasse: Es gilt: Also |
||||||||
| 20.01.2014, 17:22 | RavenOnJ | Auf diesen Beitrag antworten » | ||||||
Dieser Haskell-Code liefert die 32 Paare (x,y) (sortiert nach x):
|
||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
