Warum benutzt man bei der RSA Verschlüsslung Primzahlen?

Hallo, hab in der Schule grad das Thema RSA Verschlüsselung. Ich versteh nur nicht warum dort Primzahlen benutzt werden und nicht andere zahlen? kann mir bitte einer weiterhelfen...

2 Antworten

Sorbas48

22.11.2014, 17:55

Siehe Auszug aus Wikipedia:

Funktionen, bei denen eine Richtung leicht, die andere schwierig zu berechnen ist, bezeichnet man als Einwegfunktionen (engl. one-way function). Beispielsweise ist nach aktuellem Wissensstand die Faktorisierung einer großen Zahl, also ihre Zerlegung in ihre Primfaktoren, sehr aufwändig, während das Erzeugen einer Zahl durch Multiplikation von Primzahlen recht einfach ist. Spezielle Einwegfunktionen sind Falltürfunktionen (engl. trapdoor one-way function), die mit Hilfe einer Zusatzinformation auch rückwärts leicht zu berechnen sind. Die Verschlüsselung und die Signatur mit RSA basiert auf einer Einwegpermutation mit Falltür (engl. trapdoor one-way permutation, kurz TOWP), einer Falltürfunktion, die gleichzeitig bijektiv, also eine Permutation, ist. Die Einwegeigenschaft begründet, warum die Entschlüsselung (bzw. das Signieren) ohne den geheimen Schlüssel (die Falltür) schwierig ist.

https://de.wikipedia.org/wiki/RSA-Kryptosystem

Marie150998

03.04.2016, 18:55

Ist zwar schon älter, aber der Wikipedia-Auszug hilft ja überhaupt nicht...Hier ist eine gescheite Erklärung: http://crypto.stackexchange.com/a/10592

Ähnliche Beiträge

Primfaktorzerlegung bei 151 Stelligem Produkt aus 2 Primzahlen

Hallo erstmal :) In Informatik gab uns unser Lehrer seinen "RSA Public key", den man braucht um Nachrichten zu kodieren. Diese Zahl ist 151 Dezimalstellen lang und ist das Produkt von 2 Primzahlen. Die Aufgabe ist jetzt diese Beiden Primzahlen, welche die Faktoren der 151 stelligen Zahl sind herauszufinden. Hat jemand eine Idee, wie man das anstellen könnte, oder wie viele Bit die Verschlüsselung stark ist? Danke im Voraus! :) P,S; die Zahl lautet: 19149104522157777914518142786658323647594273709216144656238580509691987587413882641662966440441691453

...zum Beitrag

Große Primzahl als verschlüsselung?

Mal angenommen ich habe einen Quantencomputer der mir eine sehr große Primzahl berechnet die mit normalen Computern nicht auffindbar oder berechenbar ist. Könnte man dann nicht mit dieser Zahl ein PC System als "Unhackbar" (oder auch verschlüsselung) machen da niemand diese verschlüsselung knacken könnte?

...zum Beitrag

Facharbeit Kryptographie - RSA Verschlüsselung

Hallo, ich habe vor eine Facharbeit in Mathe zu schreiben, genauer gesagt im Teilbereich der Kryptographie, voraussichtlich mit Fokus auf die RSA -Verschlüsselung, soweit so gut. Jedoch stelle ich mir die Frage, wie ich das Thema direkt formulieren kann, welche Fragestellung ich abarbeiten soll, im Endeffekt, was ich mit dieser Facharbeit Herausarbeiten will.

Zusätzlich stehe ich vor dem Problem, dass ich dieses Thema auf die Thematik der Funktionen zurückführen kann, wenn wär da ne Idee hat wäre ich mehr als offen!

...zum Beitrag

Wie viele Bits/Dezimalstellen müssen die Primzahlen p und q haben bei einem RSA-Modul n mit 8192 Bit?

Hi! Kann mir jemand bitte erklären wie das funktionieren soll?

...zum Beitrag

Wie lange dauert es RSA 1024 und RSA 2048 zu entschlüsseln?

Hallo,

RSA basiert ja darauf, dass ein privater Schlüssel (p * q) - beides Primfaktoren - zu einer sehr großen Primzahl multipliziert werden (N) N ist gleichzeitig der öffentliche Schlüssel.

Es ist in relevanter Zeit nicht möglich p und q aus N zu ermitteln. Aber da stelle ich mir die Frage, wenn es so sicher ist, wieso es 2010 gelungen ist einen RSA-768 zu entschlüsseln, in etwa 2000 Prozessorjahren.

Ist es dann nicht eine Frage der Zeit, bis man auch RSA 1024 bzw RSA 2048 entschlüsselt? Wie lange bräuchte man theoretisch mit einem Rechnerverbund aus Superleistungs PCs?

Stellen Quantencomputer womöglich eine Gefahr dar?

Und wieso sind Quantencomputer kein Sicherheitsrisiko für symmetrische Verschlüsselung wie AES? Einen 256 Bit Schlüssel durch brute force zu knacken (2^256) dauert ja 3 * 10^57 Jahre, dies sind etwa 3 Nonilliarden Jahre, wenn man einen PC-Cluster mit 800 Milliarden Schlüssel pro Sekunde Rechenleistung nutzt,

wie lange bräuchte ein Quantencomputer dafür?

Und wieso sind Quantencomputer aufgrund der Superposition überhaupt schneller als Hochleistungs PCs?

...zum Beitrag

Java Unterprogramm Primzahl?

Hallo zusammen,

kann mir jemand dabei helfen, ein Java Unterprogramm zur Berechnung der Primzahl zu entwickeln ? Die Fragestellung lautet wie folgt:

a) Der Benutzer kann eine Zahl x > 1 eingeben. Ist die Zahl größer als 1 wird ausgeben, ob es sich bei der Zahl um eine Primzahl handelt oder nicht. Eine Zahl x ist KEINE Primzahl, wenn eine Zahl zwischen 2 und x–1 existiert durch die sich x ohne Rest teilen lässt. Je nachdem, ob x eine Primzahl ist wird genau folgender Text ausgegeben (x ist durch die eingegebene Zahl zu ersetzen):  x ist eine Primzahl  x ist keine Primzahl

In dem Programm sollen geschachtelte Schleifen benutzt werden.

...zum Beitrag

Primzahl - Möglichkeiten um eine Zahl zu überprüfen (Nur bis wurzel(x))?

Hi,

ich habe mir grade ein C++ Code angeschaut womit man Zahlen ueberpruefen kann ob sie eine Primzahl sind oder nicht.

Der Code funktioniert...

Wenn die Zahl n zu überprüfen ist, prüft der code ob die Zahlen in den Grenzen von 2 bis wurzel(n) durch eine andere Teilbar ist. Wenn ja => Keine Primzahl, wenn nicht => Primzahl.

Meine Frage ist, warum reicht es aus wenn man die Grenzen von 2 bis wurzel(n) überprüft. Warum muss man nicht 2 bis n überprüfen?

...zum Beitrag

Was passiert wenn das multiplikative Inverse für RSA-negativ ist?

Hallo Leute,

Ich habe gerade zum vorbereiten auf meine Abschlussarbeit, wie gelernt, den erweiterten euklidischen Algorithmus angewendet um das multiplikative Inverse für eine RSA-Verschlüsselung zu berechnen.

p=7 q=13 N=91 Phi(N) = 73

e habe ich willkürlich auf 23 bestimmt

Jetzt habe ich wie gesagt den Algorithmus angewendet und komme für das multiplikative Inverse aber auf -25, das verträgt sich aber als negative Zahl nicht mit dem RSA Algorithmus. Ich habe versucht eine Lösung zu finden, alles mehrfach nachgerechnet, aber komme einfach nicht weiter. Wie gehe ich mit der Situation um?

Anderes e? Ich dachte e muss nur größer als 1 und kleiner als Phi(N) sein? Ist eine negative Zahl doch verwendbar?

Danke im Vorraus,

Liebe Grüße Lenny :)

...zum Beitrag

Zahlen in Primzahlen zerlgen. (Casio fx-991 ES)

Hey Leute.

Ich habe da mal so ne Frage.

Ich mache ein Examen (nachträglich :D ), und zwar in Mathe.

Taschenrechner darf benutzt werden, und ich habe mal gehört, dass der Casio fx-991 es Zahlen in Primzahlen zerlegen kann.

Leider weiß ich nicht wie das funktioniert. :(

Freue mich auf hilfreiche Antworten. :)

Liebe Grüße.

PS: Falls ihr nicht wisst was ich meine: 100 = 2x2x5x5

...zum Beitrag

Java Primzahlen Programm

Hey Leute, ich habe mal wieder eine Java-Aufgabe, bei welcher ich den Fehler nicht finde. Ich hoffe ihr könnt mir irgendwie weiterhelfen.

public class PrimeNumbers {

static int x = 1000;
private static boolean[] Primes = new boolean[x];

// Hier ist der "statische Konstruktor"
static {
}

private static boolean checkPrime(int number) {

    return false;
}

public static boolean isPrime(int number) {
    int limit=1000;
    int zahl;      
    int zaehler;   
    boolean primzahl; 

    for (zahl = 2; zahl <= limit; zahl++) {
        primzahl = true;

        for (zaehler = 2; zaehler <= zahl/2; zaehler++) {
            if (zahl % zaehler == 0) {
                primzahl = false;
              break;
            }

        }

        if (primzahl) {
            return true;
        }
    }
    return false;
}

Die Primzahlen, welche zu überprüfen sind werden in einer anderen Methode übergeben und abefragt. Ich habe hier das Problem, dass er mir entweder immer true oder immer false returned, egal ob es nun eine Primzahl ist oder nicht. Ich komme einfach nicht weiter, egal wie ich es drehe und wende. Ich hoffe ihr könnt mir weiterhelfen.

Grüße Dubsepp

...zum Beitrag

Gartenzaun Verschlüsselung entschlüsseln mit Java?

Hi!

Ich soll in Java ein Programm schreiben, welches einen mit der Gartenzaun- Methode verschlüsselten Text wieder entschlüsselt.

Leider verstehe ich das überhaupt nicht. Kann mir jemand weiterhelfen?

...zum Beitrag

Zufällige Primzahl in C generieren?

Hi,

da ich in der Schule gerade C lerne und mich selber weiterbilden möchte, wollte ich ein RSA-Verschlüsselungsprogramm programmieren. Doch ich wusste nicht, wie genau ich nun eine zufällige Primzahl generiere. Ich hatte zwar den Einfall es mit der Funktion rand zu programmieren und dann so oft eine Zahl zu generieren bis es eine Primzahl ist. Doch irgendwie kam mir das zu lang vor und wollte fragen ob das nicht ein wenig einfacher ginge?

Danke im Voraus!

...zum Beitrag

Sieb des Eratosthenes - Anzahl der Primzahlen finden ohne bestimmtes Intervall?

Hallo meine Freunde,

Ich muss für die Schule eine bestimmte Anzahl an Primzahlen angeben können und daraus wird Länge des Intervalls berechnet. Sonst ist ja immer das Intervall bzw. die Zahl bis zu der gesucht werden soll. Kann mir jemand eine Formel dafür nennen, ich bin zu dumm dafür was gescheitets umzustellen. Würde mich sehr über eine Antwort freuen.

Grüße

...zum Beitrag

Hilfeeee Matheeee ( Wahrscheinlichkeit )!

Hallo Leute viele sagen das dieses Thema eigentlich sehr leit ist aber ich verstehe das irgendwie garnicht. Sorry ich bin nicht dumm aber Mathe ist halt nicht meine stärke. Unser Lehrer hat uns eine Hausaufgabe aufgegeben. Ich wollte sie gerade machen doch ich verstehe sie nicht kann mir da mal bitte helfen und erklären ?

Hausaufgabe :

Wie hoch ist die Wahrscheinlichkeit mit einem Dodekaeder Würfel dreimal hintereinander .... a) ... eine 4 zu würfeln b)... eine Primzahl zu würfeln c) ... eine gerade Zahl zu Würfeln d) ... erst eine Primzahl dann eine gerade Zahl, dann eine 4 zu würfeln ( P1=P2=P3 )

Ich möchte es verstehe und morgen richtig punkten :))) danke im voraus

Laura

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen