Warum benutzt man Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
im Rahmen meiner Bachelor-Arbeit behandle ich das Thema Kryptographie und kryptographische Hashfunktionen.
Deswegen befasse ich mich auch mit elliptischen Kurven auf endlichen Körpern, insbesondere mit der Gleichung
[mm] y^2 [/mm] = [mm] x^3 [/mm] +7
bzw. [mm] y^2 [/mm] = [mm] x^3 [/mm] +7 mod p
wobei p eine Primzahl ist, mit p = [mm] 2^{256} [/mm] - [mm] 2^{32} [/mm] - [mm] 2^{9} [/mm] - [mm] 2^{8} [/mm] - [mm] 2^{7} [/mm] - [mm] 2^{6} [/mm] - [mm] 2^{4} [/mm] -1
Das ist eine riesengroße Primzahl. Die Frage ist nun, warum man unbedingt Primzahlen benötigt. Warum bei elliptischen Kurven oder sogar allgemeiner: Warum sind Primzahlen in der Kryptographie so beliebt?
Vielen Dank im Voraus.
P.S.: Literaturreferenzen sind gerne erwünscht, um die Wissenschaftlichkeit für die Bachelor-Arbeit beizubehalten.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:16 So 26.08.2018 | | Autor: | Infinit |
Hallo pc_doctor,
die Vorliebe für Primzahlen hat, soweit mir bekannt, einen praktischen Hintergrund. Bei den Public-Key-Verfahren, wo es einen privaten und einen öffentlichen Schlüssel gibt, veröffentlicht man zur Kontrolle seinen eigenen öfentlichen Schlüssel. Wenn nun eine weitere Person in verschlüsselte Nachrichten einbrechen wollte, benötigte sie noch den privaten Schlüssel. Berechnet man diese Schlüssel mit Hilfe von Primzahlen, so muss man eine Primzahlenzerlegung durchführen. Dies ist bei kleinen Primzahlenprodukten zwar direkt möglich ( bei einem Produkt von 77 kommt man sehr schnell auf die Primzahlen 7 und 11), je größer aber die Zahlen sind, umso aufwendiger ist solch eine Primzahlenzerlegung und damit kann man durchaus behaupten, dass die Sicherheit einer verschlüsselten Nachricht mit der Länge der dabei verwendeten Primzahlen steigt.
Viele Grüße,
Infinit
|
|
|
| |
|
Hallo pc_doctor
in der Kryptographie geht es darum, vorgegebene Texte oder Datenpakete auf rationelle Weise (also mit wenig Aufwand) so zu verschlüsseln, dass ein nicht allzu großes Datenpaket entsteht, das man an einen Empfänger versenden kann. Dieser soll aus dem verschlüsselten Datenpaket mit ebenfalls vertretbarem Aufwand die Originaldaten rekonstruieren können.
Wer immer aber das effektiv über die Datenleitung fließende Paket abfangen oder abhören kann, soll die Originaldaten gar nicht oder nur mit unermesslichem Aufwand entziffern und also verstehen können.
Für dieses Rätsel: "wenig Aufwand für die Verschlüsselung, aber ein unermesslicher Aufwand für die umgekehrte Aufgabe des Entschlüsselns" gibt es nun eben in der Zahlentheorie ein im Prinzip ganz einfaches Modell: Aus zwei ganzzahligen Faktoren das Produkt zu berechnen, ist ein ganz einfach zu realisierender Rechenprozess. Die Umkehrung, nämlich die Frage, aus welchen ganzzahligen Faktoren eine riesengroße Zahl zusammengesetzt ist, ist nachweislich eine sehr komplexe Aufgabe, die ab einer gewissen Größe der Ausgangszahl praktisch unlösbar ist.
Deshalb haben sich die kryptologischen Verfahren sehr auf diese Grundidee konzentriert.
LG , Al-Chw.
|
|
|
| |
|
Im Normalfall geschieht die Codierung mit Hilfe der Modul-Rechnung. Da im Körper [mm] \IZ_p [/mm] jedes Element ein Inverses hat, falls p prim ist, sind damit die Codierung und Decodierung besonders einfach. Man muss nicht noch untersuchen, welche Zahlen ein Inverses haben und welche nicht.
So sind z.B. in [mm] \IZ_9 [/mm] 1 und 8 jeweils zu sich selbst invers, 2 und 5 zueinander, 4 und 7 zueinander, aber 3 und 6 haben kein Inverses.
Dagegen sind z.B. in [mm] \IZ_7 [/mm] 1 und 6 jeweils zu sich selbst invers, 2 und 4 zueinander und 3 und 5 zueinander.
|
|
|
| |
|
Hallo,
und vielen Dank für die zahlreichen Antworten.
Damit ich es richtig verstehe: Soweit ich weiß, ist eine Division auf elliptischen Kurven nicht möglich. Ein öffentlicher Schlüssel wird folgendermaßen berechnet:
öffentlicher Schlüssel = privater Schlüssel * Basispunkt
(So wird in Bitcoin beispielsweise der private Schlüssel generiert)
Es ist also jetzt nicht möglich, dass ich öffentlicher Schlüssel geteilt durch Basispunkt errechne, da eine Division nicht möglich ist.
Warum ist das nicht möglich? Der private Schlüssel ist eine zufällig ausgewählte Zahl zwischen 1 und $ [mm] 2^{256} [/mm] $ - $ [mm] 2^{32} [/mm] $ - $ [mm] 2^{9} [/mm] $ - $ [mm] 2^{8} [/mm] $ - $ [mm] 2^{7} [/mm] $ - $ [mm] 2^{6} [/mm] $ - $ [mm] 2^{4} [/mm] $ -1
Jetzt gibt es ja ein Problem für den Angreifer, oder ?
Möchte er den privaten Schlüssel mithilfe vom öffentlichen Schlüssel und dem Basispunkt errechnen, muss er erstmal die Nichtmöglichkeit der Division überwinden. Ich verstehe noch nicht so ganz, wo jetzt das Problem mit der Primzahlenzerlegung hier afutaucht? Insbesondere wird in diesem Kontext oft das Problem des diskreten Logarithmus erwähnt. Wobei ich den Zusammenhang auch nicht verstehe.
|
|
|
| |
|
Eine übliche Verschlüsselung sieht z.B. so aus:
Suche zwei (sehr große) Primzahlen p und q.
Veröffentliche die Zahl n=p*q (aus der sich aber p und q nicht wieder extrahieren lassen, weil p, q und n sehr groß sind).
Suche eine beliebige Zahl e<n, die zu (p-1)(q-1) teilerfremd ist (das geht ganz schnell).
Suche zu e den Partner d<n, so dass e*d=1 mod (p-1)(q-1) ist. Das geht auch schnell, aber nur, wenn man p und q kennt.
e ist nun der öffentliche Schlüssel für den Empfänge, der in einer Art Telefonbuch steht. d ist der private Schlüssel des Empfängers, den nur dieser kennt. n ist allen bekannt.
Um nun eine verschlüsselte Nachricht zu übersenden, gehst du wie folgt vor:
Du stellst den Text auf allen bekannte Weise als Zahl dar (z.B. ASCII-Code) und zerlegst diese in Ziffernblöcke, deren Wert kleiner als n ist.
Sei nun m <n eine solche Zahl.
Daraus machst du die Geheimzahl g = [mm] m^e [/mm] mod n < n und sendest sie an den Empfänger.
Der decodiert sie mit d durch folgende Berechnung:
[mm] g^d [/mm] mod n = [mm] (m^e)^d [/mm] mod n [mm] =m^{ed} [/mm] mod n = [mm] m^1 [/mm] mod n = m <n.
Das funktioniert, weil [mm] a^{k(p-1)(q-1)} [/mm] mod n = a ist, wenn p,q prim sind und n=pq ist.
Bemerkung1:
Hier wird nicht davon Gebrauch gemacht, dass [mm] \IZ_p [/mm] ein Körper ist und jedes Element ein Inverses hat (im Gegensatz zu meinem vorherigen Beitrag). Das kommt bei anderen Verfahren zum Tragen. Tatsächlich muss man e so suchen, dass es teilerfremd zu (p-1)(q-1) ist.
Bemerkung 2:
Durch diese Verschlüsselungsart kann man auch noch sicherstellen, dass der Empfänger Testen kann, ob die Nachricht wirklich vom angegebenen Absender kommt.
Wenn e und d der öffentliche bzw. private Schlüssel des Empfängers und a und b die entsprechenden des Absenders sind, verschlüsselt der Absender die Nachricht so:
[mm] g=(m^b)^e [/mm] = [mm] m^{be} [/mm] und teilt dies dem Empfänger mit. b ist geheim, e nicht.
Der Empfänger entschlüsselt zunächst mit seinem privaten d:
[mm] g^d=(m^{be})^d =m^{bed}=(m^b)^{ed}= m^b [/mm] (alles mod n)
Das kann er nicht lesen. Da er weiß, dass die Nachricht vom ihm bekannten Absender kommt, wendet er nun dessen öffentlichen Schlüssel a darauf an:
[mm] (g^d)^a [/mm] = [mm] (m^b)^a [/mm] = [mm] m^{ab} [/mm] = m (alles mod n).
Nun ist die Nachricht lesbar. Wäre der Absender ein anderer, würde nun die Anwendung von a zu Buchstabensalat führen, und der Empfänger wüsste, dass ein anderer die Nachricht verschickt hätte.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:03 So 09.09.2018 | | Autor: | felixf |
Moin,
> Deswegen befasse ich mich auch mit elliptischen Kurven auf
> endlichen Körpern, insbesondere mit der Gleichung
> [mm]y^2[/mm] = [mm]x^3[/mm] +7
>
> bzw. [mm]y^2[/mm] = [mm]x^3[/mm] +7 mod p
>
> wobei p eine Primzahl ist, mit p = [mm]2^{256}[/mm] - [mm]2^{32}[/mm] - [mm]2^{9}[/mm]
> - [mm]2^{8}[/mm] - [mm]2^{7}[/mm] - [mm]2^{6}[/mm] - [mm]2^{4}[/mm] -1
>
> Das ist eine riesengroße Primzahl. Die Frage ist nun,
> warum man unbedingt Primzahlen benötigt. Warum bei
> elliptischen Kurven
weil [mm] $\IZ/n\IZ$ [/mm] nur für $n$ prim ein Körper ist.
Man kann elliptische Kurven auch allgemein über [mm] $\IZ/n\IZ$ [/mm] anschauen, wenn $n$ keine Primzahl ist. Ist etwa $n = [mm] n_1 \cdot n_2$ [/mm] mit zwei teilerfremden Zahlen [mm] $n_1$ [/mm] und [mm] $n_2$ [/mm] (und man kennt diese Zerlegung), so lässt sich das diskrete Logarithmusproblem über [mm] $\IZ/n\IZ$ [/mm] einfach in zwei diskrete Logarithmusprobleme über [mm] $\IZ/n_1\IZ$ [/mm] und [mm] $\IZ/n_2\IZ$ [/mm] zerlegen. Das DLP über [mm] $\IZ/n\IZ$ [/mm] ist also höchstens so schwer wie das über [mm] $\IZ/n_1\IZ$ [/mm] und das über [mm] $\IZ/n_2\IZ$.
[/mm]
(Das diskrete Logarithmusproblem bei elliptischen Kurven: gegeben einen Punkt $P$ sowie ein Vielfaches $m P$ von $P$, finde die Zahl $m$.)
Wenn $n = [mm] p^k$ [/mm] eine Primzahlpotenz ist, kann man das DLP über [mm] $\IZ/p^k\IZ$ [/mm] in ein DLP in [mm] $\IZ/p^{k-1}\IZ$ [/mm] umwandeln und eine Lösung davon zu einer Lösung modulo [mm] $p^k$ [/mm] umbauen (mit etwas Aufwand).
Damit ist das DLP auf einer elliptischen Kurve modulo $n$ also am schwersten, wenn $n$ prim ist.
Literatur: im Buch von Washington (Elliptic Curves: Number Theory and Cryptography) steht sicher was dazu, ansonsten kannst du auch in meine ![[]](/images/popup.gif) Diplomarbeit schauen.
LG Felix
|
|
|
|
