matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieWarum benutzt man Primzahlen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Zahlentheorie" - Warum benutzt man Primzahlen
Warum benutzt man Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Warum benutzt man Primzahlen: Kryptographie
Status: (Frage) beantwortet Status 
Datum: 14:31 So 26.08.2018
Autor: pc_doctor

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.



        
Bezug
Warum benutzt man Primzahlen: Primzahlenzerlegung
Status: (Antwort) fertig Status 
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

Bezug
        
Bezug
Warum benutzt man Primzahlen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:54 So 26.08.2018
Autor: Al-Chwarizmi

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.  


Bezug
                
Bezug
Warum benutzt man Primzahlen: Ergänzung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:56 So 26.08.2018
Autor: HJKweseleit

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.

Bezug
                
Bezug
Warum benutzt man Primzahlen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:57 Di 28.08.2018
Autor: pc_doctor

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.

Bezug
                        
Bezug
Warum benutzt man Primzahlen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:41 Di 28.08.2018
Autor: HJKweseleit

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.


Bezug
        
Bezug
Warum benutzt man Primzahlen: Antwort
Status: (Antwort) fertig Status 
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 []Diplomarbeit schauen.

LG Felix



Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]