Modulo Problem bei elliptischen Kurven

Neue Frage »

Klingone Auf diesen Beitrag antworten »
Modulo Problem bei elliptischen Kurven
Hallo,

ich befasse mich gerade mit Elliptischen Kurven im Bereich der Kryptografie, also endliche Körper.

Vom Prinzip her verstehe ich die Thematik, allerdings verstehe ich die Anwendung des Modulos nicht so ganz.

Angenommen folgende elliptische Kurve:
über F101

Es sollen die Punkte P+Q=R für P=(2,0) und Q(1,3) auf diese Kurve hinzugefügt werden.

Also wende ich diese Formeln an:
s = (yP – yQ) / (xP – xQ) mod p
xR = s2 – xP – xQ mod p
yR = -yP + s*(xP – xR) mod p

Setze ich nun bei s folgendes ein:
s = (yP – yQ) / (xP – xQ) mod p = (0 – 3) / (2 – 1) mod 17 = -3

Kommt bei mir -3 raus. Laut Lösung soll aber 14 rauskommen, also der Ausdruck (0 – 3) / (2 – 1) mod 17 = 14

Ich verstehe nicht wie man hier auf 14 kommen soll. Ich dachte erst dass die Lösung falsch sei, aber bei einer anderen elliptischen Kurve habe ich das gleiche Problem.

Wie muss man das hier rechnen, damit 14 rauskommt?


Oder anderes Beispiel

der Ausdruck


ergibt bei mir 1,608181


Laut Lösung soll aber raus kommen. Das hat was mit dem erweiterten Euklidischen Algorithmus zu tun, ich verstehe aber nicht, warum ich den da anwenden muss. Wieso darf man dass nicht einfach ausrechnen?
tatmas Auf diesen Beitrag antworten »

Hallo,

es gilt , denn die Differenz der beiden Werte ist ja gerade 17.
Aber wieso rechnest du überhaupt modulo 17? Davor schreibst du was von , also modulo 101.



Das sind keine rationalen Zahlen. Du sollst das Inverse von 88 modulo 101 berechnen.
Also diejenige Zahl berechnen mit .

Zitat:
Wieso darf man dass nicht einfach ausrechnen?

Doch darf man. Du machst es halt nur komplett falsch. Da bist du auch nicht allein, ist ein klassischer Anfängerfehler.
Klingone Auf diesen Beitrag antworten »

Mist das mit 101 ist ein Tippfehler, das bezieht sich auf das untere Beispiel. Beim oberen ist F17.

Wie muss ich das denn richtig rechnen?
tatmas Auf diesen Beitrag antworten »

Zitat:
Wie muss ich das denn richtig rechnen?

Was ist das?
Das Inverse modulo n?

Das dürfte in deinen Unterlagen stehen, da wo auch das mit dem erweuterten eukl. Algorithmus steht.
Klingone Auf diesen Beitrag antworten »

Mein Problem ist, dass ich nie weiß, wann was äquivalent ist. Hier ein Beispiel:



Woher weiß ich, dass äquivalent zu ist?

Wie kommt man darauf? Gibt es hierfür eine Formel oder irgendwas, durch ausprobieren finde ich es jedenfalls nicht.
tatmas Auf diesen Beitrag antworten »

15*60^2=54000=504*107 + 72
also
oder z.B. (das letzte geht im Kopf; bedenke 2*107=214)

Ich rate dir dazu dir die Grundlagen der Modulorechnnng nochmal abzuschauen.
 
 
Klingone Auf diesen Beitrag antworten »

Ah danke, die erste Version ist recht angenehm mit dem Taschenrechner lösbar.

Ich meine mich dunkel daran zu erinnern, dass man das auch mit dem kleinen Satz von Fermat lösen kann. Aber ich verstehe nicht so recht, wie ich da ansetzen soll.



Die Form ist auch ganz anders wie . Weiterhin hat man ja dann auch das Problem mit den Carmichael Zahlen.
tatmas Auf diesen Beitrag antworten »

Der kleine Fermat bringt hier gar nichts.
Und mit Carmichaelzahlen hat auch nichts zu tun.
Klingone Auf diesen Beitrag antworten »

Ok, gut zu Wissen Big Laugh .

Eine letzte Ungewissheit habe ich noch beim Modulo. Woher weiß ich, wann ich den Modulo direkt (also z.B per Taschenrechner) berechnen kann und wann ich den erweiterten Euklid anwenden muss?

Das kann man auch einfach per Taschenrechner berechnen.


ABER



kann ich nicht direkt berechnen, hier muss ich den erweiterten Euklid anwenden. Ich meine auch auf andere Probleme gestoßen zu sein, bei denen das nicht so einfach ging.

Wieso ist das so? Liegt das an der Division? Wenn ja, gilt das immer bei Divisionen?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »