Pohlig-Hellman-Algorithmus "c" und weitere Verständnisfragen |
06.12.2011, 21:59 | .txt | Auf diesen Beitrag antworten » | ||
Pohlig-Hellman-Algorithmus "c" und weitere Verständnisfragen Liebes Forum ich arbeite gerade an meiner Fachbereichsarbeit (elliptische Kurven und ihre Anwendung in der asymmetrischen Kryptographie) und bin bei den Attacken (zu denen auch der Pohlig Hellman Algorithmus gehört) ziemlich an meine Grenzen gestoßen (sind ein neusprachliches Gymnasium und sind in Mathe nicht allzu weit gekommen) Ich habe also recht lange gegoogelt und die Erklärung bei der ich noch am meisten zu verstehen scheine ist diese hier: http://www-math.ucdenver.edu/~wcherowi/courses/m5410/phexample.pdf 1) allerdings stehe ich schon bei der Einteilung in x_2, x_3, x_5 an. Wie/als was kann man sich diese x vorstellen? 2) warum ist x_2 = c_0 + c_1 (2). 3) den rest verstehe ich dann ohnehin nicht, da der ja ziemlich darauf aufbaut... die betreuerin der fba hat gesagt ich müsse das nicht unbedingt machen, allerdings hat mich jetzt der ehrgeiz gepackt und ich würde das gerne verstehen, allerdings habe ich keine ahnung wo ich beginnen soll/was ich lernen könnte um das zu verstehen, wäre für jede antwort dankbar Meine Ideen: ad 1) sind die x zwischenergebnisse um das Berechnen zu vereinfachen, die dann am ende mit diesem chinesischen restsatz wieder zusammengesetzt werden? |
||||
07.12.2011, 23:46 | parkerstone | Auf diesen Beitrag antworten » | ||
Hallo, ich möchte dir nicht zu Nahe treten, aber zu behaupten das Du etwas am meisten verstehst, wenn du schon bei der 2. oder 3. mathematischen formel aussteigst halte ich für sehr bedenklich. zu 1) x ist eine natürliche Zahl, die man hier modulo der drei primzahlen-potenzen in 8100 betrachtet und den Index mit der entsprechenden Primzahl kennzeichnet. zu 2) x_2 \in \{0,1,2,3\} Ich halte dieses Thema für sehr schwierig, auch aufgrund dessen solltest Du Dich zuerst mit Grundlagen beschäftigen. Und das ist in diesem Fall modulo-Rechnung. Ich hege z.B den Verdaacht, dass Du keine Ahnung hast was der chin. Restsatz ist. (was als Schüler keinesfalls verwerflich ist.) |
||||
08.12.2011, 00:20 | chrizke | Auf diesen Beitrag antworten » | ||
Ich habe zwar keine Ahnung von Kryptografie und dass ich mich mit Zahlentheorie beschäftigt habe, ist auch schon einige Semester her, aber ich habe mal das PDF überflogen und mir die Theorie vom diesem Algorithmus angeschaut. Du brauchst, wie mein Vorposter schon sagte, auf jeden Fall Grundlegendes Wissen über die Modulo-Operation und die sich daraus ergebenden Restklassen. Ebenso scheint mir Wissen über Zyklische Gruppen für unabdingbar. Das geht schon weit über den Schulstoff hinaus. Wenn du jetzt aber schreibst, dass du über elliptische Kurven was machen willst, von denen ich zwar mal gehört, sie aber im Studium weder kennengelernt noch näher betrachtet habe (bin aber auch kein Algebra-Mensch, die beschäftigen sich damit schon), zweifele ich ein wenig an dem Sachverstand deines Betreuers. |
||||
08.12.2011, 13:13 | .txt | Auf diesen Beitrag antworten » | ||
naja, am meisten verstehen hieß in diesem fall auch: das gefühl haben das noch am ehesten zu verstehen ^^ hier verstehe ich wenigstens die notation und es ist ausführlicher erklärt (vor allem anhand eines beispiels ) als sonstwo. ja ich habe mir auch schon gedacht dass mir hier gewisse grundlagen fehlen, dachte (bevor ich mich mit diesem algorithmus beschäftigt habe) mit 4≡14mod5 etc sei's getan :/ wüsste vllt jemand eine seite wo ich mich in dieses thema noch weiter einlesen könnte (wo der chinesische restsatz/allgemeine basics von deren existenz ich noch nicht weiß) halbwegs anschaulich erklärt werden? bin durchaus bereit da auch zeit zu investieren ad 1&2) ok, ich schätze einmal da fehlen mir wirklich grundlagen über restklassen, etc., aber danke für den versuch @chrizke: doch das stimmt schon, elliptische kurven haben durchaus etwas mit dem pohlig hellman algorithmus zu tun (bei einer attacke gilt es ja eine spezielle form des DLP zu knacken (ECDLP, das multiplizieren von punkten auf EC gleicht dem modularen exponentieren) (hoffe wir reden da nicht aneinander vorbei |
||||
10.12.2011, 08:52 | chrizke | Auf diesen Beitrag antworten » | ||
Nein nein, das meine ich nicht. Mir geht es vielmehr darum, dass du die Aufgabe erhalten hast überhaupt damit zu arbeiten, ohne die nötigen Grundkenntnisse zu haben. |
||||
10.12.2011, 09:19 | .txt | Auf diesen Beitrag antworten » | ||
achso, entschuldige, aber nein: mein betreuer hat mir eh gesagt dass ich das nicht machen muss, mich hätte es nur sehr interessiert, die schuld liegt da also ganz bei mir gibt es vllt vorschläge womit ich da beginnen könnte? |
||||
Anzeige | ||||
|
||||
10.12.2011, 09:39 | galoisseinbruder | Auf diesen Beitrag antworten » | ||
Hi, ich geb auch mal meinen Senf dazu. Was Du auf jeden Fall brauchen wirst ist folgendes, aufeinander aufbauendes brauchen: (und das ist umfangreich genug): -(abelsche ) Gruppen - Restklassenringe ("modulo-Rechnung") -(einfache) endliche Körper; Charakteristik - Def. einer elliptischen Kurve; was passiert in char=2,3? K-rationale Punkte - Ganz wichtig: Def. der Gruppenstruktur auf E[K] , am besten geometrisch-anschaulich und algebraisch-rechnerisch. Und damit bist Du schon beschäftigt genug ohne Dich in Untiefen von Attacken gegen asymetrische Verschlüsselungsverfahren zu begeben- ich bin der Meinung man sollte erst versuchen zu verstehen wie etwas funktionuert bevor mans kaputt machen will. |
||||
10.12.2011, 11:20 | .txt | Auf diesen Beitrag antworten » | ||
auf abelsche gruppen, resklassenringe und endliche Körper und deren charakteristik, ... bin ich schon eingegangen, aber das hilft mir bei diesem algorithmus leider nur mäßig da ich mich mit diesem gebiet aber erst im zuge meiner fba beschäftigte weiß ich natürlich nicht, was ich ausgelassen habe :/ und die fba ist schon zu groß um hier als dateianhang mitgeliefert zu werden |
||||
10.12.2011, 11:33 | galoisseinbruder | Auf diesen Beitrag antworten » | ||
Deine ursprünglichen Fragen 1) und 2) wurden doch hier schon beantwortet. Hast Du Dir dazu schon Gedanken gemacht? Kommuniziert hast Du diese noch nicht. Desweiteren frage ich mich ernsthaft was Du damit bezweckst die Pohlig-Hellman-Reduktion in Deine Facharbeit aufzunehmen. Diese müsste,wenn Du alles sauber aufschreibst schon deutlich mehr als 10 Seiten haben, wenn Du überhaupt erst einmal ein ECC-System definieren willst, die Assoziativität der Punkt-Addition allein ist Dank der sinnvollerweise zu verwendenden Bildchen 2-3 Seiten lang. Ist Dir denn klar was P-H. für Auswirkungen auf Dein System hat? Wenn Du konkrete Fragen hast kann ich Dir gerne dabei helfen, rumgeflenne hilft da nicht. |
||||
10.12.2011, 12:12 | .txt | Auf diesen Beitrag antworten » | ||
gedanken habe ich mir schon dazu gemacht, viel weitergekommen bin ich allerdings nicht ^^ meine fba ist (nur über ECC, ohne angriffe, etc) schon ~22 seiten lang naja, ich denke schon, der der kurve zugrundeliegende körper sollte modulo irgendeiner primzahl P sein, für die gilt dass der größte teiler von P-1 groß ist. stimmt das? eben deshalb wollte ich mir ja den algorithmus noch mal genauer anschauen... und wie gesagt, meine fba wäre ohnehin schon lang genug, es treibt mich jetzt eig nur noch das persönliche interesse wollte nicht rumflennen, sondern nur fragen ob jemand so nett wäre mir zu sagen was ich zum verständnis des PH algorithmus so alles brauche. im moment macht das ganze einfach keinen sinn weil ich nicht verstehe warum man einfach so die teiler von p-1 nehmen kann (chineischer restsatz..?) und warum man diese in c's zerlegen kann und aufgrund welcher mathematischen grundlagen man diese berechnet. da das eine ganze menge ist und ich ja niemanden dazu nötigen will mir da die grundlagen zu erklären habe ich nach anfängen gesucht mfg |
||||
10.12.2011, 13:42 | galoisseinbruder | Auf diesen Beitrag antworten » | ||
Das ist falsch. P-1 hat hier gar nichts zu suchen, das kommt von der eulerschen phi-Funktion, die man in RSA verwendet. (man ganz abgesehen davon dass in diesem Kontext P als Bezeichnung für einen Punkt der Kurve "reserviert" ist.) Der Alg. zeigt, dass man einem Punkt P wählen muss, so dass die von P erzeugte Gruppe einen großen Prim(!)teiler hat. P.S.: Weil ich´s hier grad lese: Man multipliziert keine Punkte auf einer elltptischen Kurve man addiert sie. |
||||
11.12.2011, 17:06 | .txt | Auf diesen Beitrag antworten » | ||
achso, ich dachte weil man ja die primzahl - 1 in primzahlpotenzen zerlegt und so... ok, werds mir merken mit der notation steh ich noch etwas auf kriegsfuß ^^ jaa, schlampig geschrieben: skalare multiplikation halt (3xP = P+P+P, dass es dafür keine eigene funktion gibt, weiß ich schon) ich schätze mal ich lasse das thema, solange ich keine watscheneinfache einführung in restklassenringe etc finde :/ |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|