Diskussion:RSA-Kryptosystem/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:RSA-Kryptosystem/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:RSA-Kryptosystem/Archiv/1#Thema_1

Lange Nachrichten

In dem meisten Beispielen (auch hier) findet man immer nur Nachrichten, die kleiner als n sind. Da ist natürlich erstmal schön, weil diese Nachrichten sich ohne weitere ver- und entschlüsseln lassen. Aber was passiert, wenn die Nachricht größer als n wird? Wird sie in mehrere Teile geteilt, die für sich verschlüsselt werden?

ja in blöcke aufteilen IqayImlpI 17:43, 28. Sep. 2010 (CEST)

Meist verschlüsselt man hybrid, d.h. man verschlüsselt mit RSA einen symmetrischen Schlüssel, und mit diesem und euinem symmetrischen Verfahren den eigentlichen Klartext. Dann hat man dieses Prolem nicht. --Mojo1442 16:18, 9. Jul. 2011 (CEST)

Ja, praktisch immer, wird das sogenannte Hybridverfahren benutzt. Faktisch ist das aber nichts anderes als ein Schlüsselaustausch wie bei Diffie-Hellman und anschließender ganz normaler symmetrischer Verschlüsselung. Wozu also RSA? 109.90.224.162 11:40, 4. Okt. 2015 (CEST)

"Wozu also RSA?" Falls das eine Frage war: Der Schlüsselaustausch ist einfacher. Außerdem ist es nicht empfohlen eine Nachricht mit dem selben AES Schlüssel roh zu verschlüsseln. Für so etwas benötigt man einen Stream- oder Block-Cipher. Denn zu jeder Nachricht gibt es nur genau einen Ciphertext. Verschlüsselt man beispielsweise eine einfache Bitmap in der viel die Farbe weiß vor kommt, können wegen den wiederholten Daten (Farbe Weiß) wiedererkennbare Pattern entstehen (da gleicher Ciphertext als Ergebnis). Interpretiert man den Ciphertext wieder in eine Bitmap kann man Umrisse erkennen und somit den Inhalt des Bildes erkennen oder die Nachricht sogar entschlüsseln mithilfe von Analyse der sich wiederholenden Pattern. Googlet mal "aes encrypted picture of penguin". Da erkennt man den Pinguin "Tux", da sich Pattern und somit Umrisse im Bild erkennen lassen. Ein Stream-/Block-Cipher verschlüsselt mithilfe eines AES Schlüssels *und* des davor verschlüsselten Teil, sodass man eine lange Sequenz der Zahl 0 verschlüsseln kann ohne erkennbare Pattern erkennen zu lassen. Ich hoffe ich habe keinen M*st erzählt :) bitte ergänzt oder korrigiert. Wäre toll wenn das im Artikel stehen könnte. --Mike Wille (Diskussion) 14:29, 9. Mai 2018 (CEST)

Auch ohne Fragmentierung von Nachrichten ist die Aufgabe der Serialisierung/Deserialisierung von Intergerzahlen zu lösen und wie ein Text in so eine Bytefolge eingebettet wird.

Die Serialisierung einer Zahl als Bytestream ist typisch BigEndian oder LittleEndian.

Ein Text hat eine Byte-Kodierung als UTF-8-Bytestream oder UTF-16 oder anders

Der Text, wenn er die Kapazität des Moduls N nicht ausfüllt, kann von links oder rechts aufgefüllt werden, mit Nullen oder Zufallwerten -> Thema Padding

Schliesslich ist die Länge der Nachricht zu kodieren, entweder durch ein Längenpräfix oder mit einem Terminal-Metazeichen, z.B. 0

Bei längeren Nachrichten wird man sie in kleinere Pakete zerlegen, die jeweils in das Modul N passen. Auch hier muss ein Protokoll für Längenkodierung festgelegt sein. (nicht signierter Beitrag von Action127 (Diskussion | Beiträge) 17:11, 2. Apr. 2021 (CEST))

Bitanzahl in Dezimalstellen

hallo. ich frage mich gerade wie man von 640bit auf 193 dezimalstellen kommt? ein byte = 1 dezimalzahl/stelle = 8 bit also müsste doch 640bit/8=80 dezimalstellen ergeben. oyster-manu --87.193.15.61 22:48, 13. Apr 2006 Sig nachgetragen von Rat 03:42, 14. Apr 2006 (CEST)

Wenn man die Zahlen binär codiert, also als Folge von Nullen und Einsen, benötigt man für eine Dezimalstelle im Schnitt etwa 3,3 Bits. Mit 8 Bit kommt man bis 255, mit 16 bis 65535, mit 20 Bits bis etwa 1 Million, mit 30 bis etwa 1 Milliarde usw. --Rat 03:42, 14. Apr 2006 (CEST)

das musst du nochmal etwas genauer erklären. auf die 3,3 komme ich wenn man 640/193 rechnet, aber man kann ja schlecht 3,3 bit verwenden. außerdem müsste man ja deiner rechnung bei 640bits zillionen dezimalstellen verwenden können, es sind aber tatsächlich nur 193. oyster-manu 87.193.3.184 19:52, 14. Apr 2006 (CEST)

Du verwechselst "Anzahl der Dezimalstellen" und "Zahlenwert". Eine Zahl mit 193 Dezimalstellen ist tatsächlich ziemlich groß ("Zillionen"), hat aber eben doch "nur" 193 Dezimalstellen. Rechnet man die in eine Binärzahl um, so hat die Binärdarstellung der gleichen Zahl etwa 640 Bits. Wenn du 10000₁₀ (5 Stellen) nach binär umrechnest, kommt 10011100010000₂ (14 Stellen) raus. 99999₁₀ = 11000011010011111₂ (17 Stellen). Die Binärdarstellung einer 5 stelligen Dezimalzahl benötigt also 14 bis 17 Stellen. Allgemein benötigt eine Binärzahl durchschnittlich 3,3 ( = log(10)/log(2) ) mal soviele Stellen wie die gleichwertige Dezimalzahl. Näheres siehe Dualsystem. --Rat 23:29, 14. Apr 2006 (CEST)

ahh jetzt ist der groschen gefallen! danke für deine mühen :) oyster-manu 87.193.16.235 15:32, 15. Apr 2006 (CEST)

Versuch einer Antwort

Was ist denn das kleine n bei Punkt 1 unter "Schlüsselgenerierung"? Sicher, dass das stimmt?
--KullerhamPster 23:00, 26. Mär 2004 (CET)

Danke für den Hinweis. Ich habe den Halbsatz entfernt, da dieser IMHO eh überflüssig und nirgendwo vorgeschrieben ist.

--Qbi 23:36, 26. Mär 2004 (CET)

Das ging aber schnell :) Ich staune mehr und mehr über Wikipedia (bin noch recht neu hier)
--KullerhamPster

Oh, noch was: Den Abschnitt hier verstehe ich auch ned ganz, jedenfalls das mit dem n < N:

---

"Um eine Nachricht m zu veschlüsseln, muss sie zunächst durch eine zu vereinbarende reversible Kodierung in eine n < N umgerechnet werden."

Der Artikel muss IMHO noch überarbeitet werden. Ich habe hier beim Durchlesen schon einige Fehler entdeckt und ausgebessert. Allerdings muss noch mehr geschehen ...

--Qbi 21:56, 27. Mär 2004 (CET)

---

Und noch eine allgemeinere Frage: Müsste es bei diesen Modulo-Rechnungen nicht $\equiv$ anstatt $=$ heißen? Wir haben das zwar auch mal an der Uni gemacht, aber irgendwie weiß ich davon fast nix mehr. Hab's auch ned wirklich kapiert gehabt. Aber irgendwas mit "kongruent modulo" war da, jedenfalls war's glaub' ich kein Gleichzeichen.
--KullerhamPster

IIRC nicht

--Qbi 21:56, 27. Mär 2004 (CET)

---

Ich habe auch mal eine Frage:
Was wird denn in der Praxis genau als zu verschlüsselnde Nachricht aufgefasst? Ist das in der Formel als Nachricht bezeichnete m in der Praxis ein Byte oder die ganze Nachricht, die vielleicht aus tausenden von Bit besteht? GeorgGerber

I.d.R. meint man damit die gesamte Nachricht.

--Qbi 18:31, 29. Apr 2004 (CEST)

---

... und noch eine:
Wie bekomme ich denn die Primzahlen p und q? Beim eim Erzeugen meines Schlüsselpaares habe ich auf einem normalen PC ja nur ein paar Millisekunden Zeit.

Im Prinzip rät man eine Zahl (naja, mit ein paar Tricks) und testet, ob es tatsächlich eine Primzahl ist -- im Moment noch mit dem Miller-Rabin-Algorithmus, aber der könnte evtl. in absehbarer Zeit vom AKS-Algorithmus abgelöst werden (wurde 2002 entdeckt und ist der erste Primzahltest, der echt deterministisch in polynomieller Zeit arbeitet) -- Details bei Gelegenheit! --Pinguin.tk 18:16, 29. Apr 2004 (CEST)

'habe g'rad' mal gegoogelt:

http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/German/2.3.1.d.html

implementiert den Miller-Rabin-Algorithmus, dort steht aber, daß das Ergebnis nur aussagt, dass es sich höchstwahrscheinlich um eine Primzahl handelt. Was kann bei der Verschlüsselungsgeschichte passieren, wenn es sich einmal nicht um eine Primzahl handelt?

GeorgGerber 09:22, 30. Apr 2004 (CEST)

Wie du schon richtig erkannt hast, wird hier nur mit Wahrscheinlichkeiten gearbeitet. Eine Berechnung würde auf handelsüblichen Rechnern viel zu lang dauern. Demzufolge könnte es theoretisch auch passieren, dass man mal keine Primzahl erwischt.

--Qbi

Naja, das stimmt so nicht direkt: die Fehlerwahrscheinlichkeit von Miller-Rabin beträgt pro Durchführung des Algorithmus 1/4 -- das mag viel erscheinen, aber man muss berücksichtigen, dass die einzigen Zahlen, bei denen MR Fehler macht, sogenannte starke Pseudoprimzahlen sind. Und von denen gibt es "wenige", d.h. wenn man eine Zahl mehrmals (n-mal) mit Miller-Rabin testet, so ist die Wahrscheinlichkeit, dass sie jedesmal fälschlicherweise als Primzahl erkannt wird, nur noch 1/(4^n), und das ist ziemlich schnell sehr klein. Daher wird es auch realistisch betrachtet so gut wie nie passieren, dass Du in RSA eine Pseudoprimzahl verwendest. --Pinguin.tk 08:38, 3. Mai 2004 (CEST)

ok, danke GeorgGerber 13:09, 3. Mai 2004 (CEST)

---

Im Artikel ist ein Beispiel angegeben. Ehrlich gesagt verstehe ich es nicht so ganz: Die Nummerierung ist vermutlich um 1 verrutscht, sodass Punkt 4 zur Formel 3 gehört. Was allerdings in 4 und 5 berechnet wird, ist mir nicht klar. Ist das eine Probe, ob Teilerfremdheit (3) und die Formel von (4) tatsächlich vorliegen?
Vielleicht könnte man das Beispiel noch ein wenig erweitern, und nach dem Berechnen von P, n, e und d auch noch einen Wert m verschlüsseln und wieder entschlüsseln.
Wie gesagt, da ich die Rechnung nicht verstehe, traue ich mich nicht, da etwas zu ändern bzw. hinzuzufühgen. GeorgGerber 13:09, 3. Mai 2004 (CEST)

IMHO muss der gesamte Artikel nochmal überarbeitet werden. Wenn ich wieder genügend Zeit habe, werde ich das auch tun. Ich werde mal einen Blick auf das Beispiel werfen und das ggf. anpassen.

--Qbi 17:55, 3. Mai 2004 (CEST)

---

Danke für die Erweiterung, ich finde den Artikel jetzt gut und verständlich. In der Praxis werden im Internet immer wieder öffentliche Schlüssel in der Form

Type Bits/KeyID    Date       User ID
sec   512/6100B8FB 2003/12/01 myID  

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.3in
lQEAAz/LOX8AAAECAMLPa9PYZQq3TaS9X/MGV6ZxvBvrXnj+vi3Ph76kaxpCXcI4
q3TaS9X/MGV6ZxvBvrXnj+vi3Ph76kaxpCXcI4lQEAAz/LOX8AAAECAMLPa9PYZQ
...
=yeZ8
-----END PGP SECRET KEY BLOCK-----

veröffentlicht. Sollte man noch etwas schreiben, wie die Schlüssel in der Praxis z.B. in solchen Dateien gespeichert werden? GeorgGerber 11:32, 17. Mai 2004 (CEST)

Das GnuPG-Kommando, mit dem man sich seine Schlüsseldatei im Detail "ansehen" kann, lautet

gpg --list-packets --verbose <myID>.asc

--Ann (Diskussion) 15:28, 9. Feb. 2021 (CET)

Wie meinst du das genau? --Qbi 16:59, 17. Mai 2004 (CEST)

Ich dachte an folgendes: In der Praxis wird das beschriebene Verfahren ja beim Verschlüsseln/Signieren im EDV-Bereich angewendet. Dazu hat man sich ja auf gewisse Techniken / Datei-Formate geeinigt, wie die Schlüssel ausgetauscht, gespeichert bzw. in Zertifikaten verpackt werden.

In diesem Zusammenhang gibt es eine Reihe Begriffe und Informationen (X509, PGP, ...) die zum Teil bereits in Wikipedia beschrieben sind.

Ich fände es schön, wenn die Zusammenhänge zwischen diesen Artikeln erkennbar wären, z.B. durch einen Absatz der Art:

In der EDV werden in der Praxis die privaten bzw. öffentlichen Schlüssel, die ja jeweils aus 2 langen Zahlen bestehen, in Dateien gepackt. Folgende Formate sind gebräuchlich:

• *.pgp (binär)
• *.…. (ASCII, Radix64-codiert)
• ….

GeorgGerber 17:48, 17. Mai 2004 (CEST)

Es gibt in der Tat noch keine Beschreibung zum OpenPGP-Standard. Dies muss noch nachgeholt werden. Eventuell möchtest du den Anfang machen …

--Qbi 17:58, 17. Mai 2004 (CEST)

Ist OpenPGP dasselbe, wie GnuPG? - Da gibt es nämlich einen Artikel.

Ansonsten habe ich durch meinen Diskussionsbeitrag eher gehofft, hier etwas über dieses Thema zu erfahren, da ich mich leider selbst noch nicht richtig auskenne. Deswegen tue ich mich sehr schwer, da einen Artikel zu schreiben :=(

GeorgGerber 11:29, 18. Mai 2004 (CEST)

OpenPGP beschreibt das Format von PGP-Nachrichten. Da bei PGP immer mal wieder inkompatible Änderungen gemacht wurden, hat man sich hier mal auf einen Standard geeinigt. GnuPG setzt diesen Standard um. Details findest du im RfC 2440

--Qbi 16:47, 18. Mai 2004 (CEST)

P ungleich NP

Warum kann es Falltürfunktionen nur für P ungleich NP geben? Soweit ich weiß ist das ja auch noch nicht bewiesen. Stern 19:41, 20. Jun 2004 (CEST)

puh, den Beweis müsste ich suchen, aber wir hatten das in einer Vorlesung über Primzahltests... Pinguin.tk 20:13, 20. Jun 2004 (CEST)

ich vermute mal, die Idee ist folgende: wenn P=NP, dann kann man evtl. auch schwierige Probleme wie Faktorisierung effizient lösen (naja, ist nicht ganz so einfach, Faktorisierung ist zwar NP-hart, aber nicht NP-vollständig...) oder jedenfalls umgekehrt, wenn $P\neq NP$, dann kann man Faktorisierung nicht effizient lösen... offenbar bezieht sich das ganze Problem sogar auf Einwegfunktionen (siehe dort). Hm. --Pinguin.tk 20:26, 20. Jun 2004 (CEST)

In Ordnung. Leuchtet mir ein. Vielen Dank! Stern 20:28, 20. Jun 2004 (CEST)

In dieser Allgmeinheit ist diese Aussage natürlich nicht haltbar. Das Faktorisierungsproblem liegt in NP (ist aber nicht NP-hart und somit auch nicht NP-vollständig). Das bedeutet, daß wenn P==NP gilt das Faktorisierungsproblem auf jeden Fall effizient lösbar ist (und somit die Sicherheit von RSA dahin ist). Das bedeutet aber nicht, das es dann gar keine Falltürfunktionen mehr gibt. Es bedeutet nur, daß die Klassen P und NP zur Konstruktion einer Falltürfunktion ungeeignet sind. Es gibt aber noch deutlich mehr Komplexitätsklassen (die teilweise auch deutlisch schieriger sind als NP), die man dann nutzen kann. Komplexitätsklassen gibt aber leider nicht viel dazu her. Das P/NP-Problem hat jedenfalls nichts mit Falltürfunktionen zu tun, sondern allenfalls etwas mit der Sicherheit von RSA. MlaWU 21:10, 8. Okt 2004 (CEST)

Widerspruch die Aussage ist korrekt: Bei einer Falltürfunktion fordert man, dass sie sich mithilfe der geheimen Zusatzfunktion effizient (also in Polynomialzeit) berechnen lässt. Daher kommen nur Funktionen aus NP ion Frage. Diese wären bei P=NP aber immer auch ohne die Hilfsinformation effizient lösbar.--Mojo1442 16:30, 9. Jul. 2011 (CEST)

Verschiedene e und d

Zu einem φ ( N ) gibt es mehrere (viele) moegliche e und d, die entweder nicht funktionieren, oder identische Ergebnisse liefern, so in der Form k^e1 Mod N = k^e2 Mod N. Da scheint es irgendwie egal zu sein, welches e man dann nimmt. Man wuerde immer den gleichen Code zu einer bestimmten Zahl N produzieren. Stimmt das? Ich muss es spaeter mal durchtesten. Solange φ ( N ), p und q geheim sind, hat das ja keine grossen Auswirkungen. --Arbol01 11:59, 24. Jun 2004 (CEST)

Anmerkungen

Im folgenden, was mir beim Lesen so auf-/eingefallen ist:

• P <> NP: da muss mindestens ein Link dazu
• Schlüsselgenerierung: Vor die Vorgehensweise noch einen (kurzen?) Satz
• Verlinkung: das mod-Problem hast Du hier sehr elegant gelöst - Du solltest jedoch trotzdem noch Wikilinks setzen
• statt der Strukturierung mit a, b, c würde ich die normale numerierte Liste mit # bevorzugen - sieht m.E. durch die Einrückungen besser strukturiert aus
• zum Beispiel einer Ver- und einer Entschlüsselung: Vielleicht solltest Du noch erwähnen, was Du als Beispiel verwendest ;-)
• Die Abstände im Tex vor dem mod sind mir zu groß (auch bei Pseudoprimzahl), die solltest Du besser etwas kleiner halten (s. z.B. Rabin-Kryptosystem).
• Das Patent solltest Du noch erwähnen
• zum knacken: vielleicht noch ein Hinweis auf distributed.net?
• zur Anwendung: Du hast zwar die Telefonkarte schon drin - aber ist RSA nicht das bei weitem verbreitetste Verfahren? Da sollte vielleicht noch etwas mehr dazu.
• etwas Literatur wäre auch sinnvoll ;-)

Insgesamt gefällt es mir ganz gut - aber im Review werden sicherlich noch einige Hämmer kommen ;-) -- srb 12:55, 24. Jun 2004 (CEST)

Vielen Dank für die Blumen, aber, nur weil ich geholzt habe, heißt das noch lange nicht, daß ich für alles verantwortlich bin.

Zu P <> NP: Da habe ich gar keine Ahnung (Asche auf mein Haupt).

Die Telefonkarte stammt auch nicht von mir.

Ich hoffe nicht, daß RSA in das Review gestellt wird, aber das liegt nicht in meiner Hand.

Ich schau mir mal an, wie das Abstand-Problem in Rabin-Kryptosystem gelöst wurde. Ah ja! Nein, das kann ich nicht machen. In Rabin-Kryptosystem steht in der Mathe-Formel sinngemäß m*o*d, während ich \mod benutze. Da würden mir einige Puristen, wahrscheinlich zurecht) auf das Dach steigen.

Ist es denn wirklich so wichtig, daß ich die Nukleinsäuren Adenin, Cytosin, Guanin und T (Name ist mir im moment entfallen) in Form von Triplets verwendet habe? --Arbol01 14:14, 24. Jun 2004 (CEST)

P != NP Formulierung

Der Satz in der Klammer klingt so, als wäre es unwahrscheinlich, dass P != NP. Afaik ist das doch aber grade umgekehrt, es ist eher unwahrscheinlich, dass P = NP. Seh' ich da was falsch? --KullerhamPster 16:17, 18. Aug 2004 (CEST)

das siehst Du schon richtig -- welchen Satz im Artikel meinst Du denn? --Pinguin.tk 19:43, 20. Aug 2004 (CEST)

Ich bin auch eben hier drüber gestolpert: "Es sind aber nur Algorithmen, welche in NP und außerhalb von P liegen, bekannt.", das würde ja implizieren, dass P ungleich NP, was meines Wissens nach noch nicht bewiesen wurde... (oder versteh ich da was falsch?)

Schwierigkeit von Faktorisierung und Eulerfunktion

Die Zerlegung von N in die zufällig gewählten Primfaktoren p und q ist ebenfalls nicht effizient lösbar, aber einfacher als die Berechnung der φ-Funktion.

Stimmt das? Meiner Meinung nach sind die beiden Problem gleich schwer. MlaWU 22:04, 8. Okt 2004 (CEST)

Verschlüsselungsbeispiel

hallo!

kann mir vielleicht jemand erklären, warum bei dem Zahlenbeispiel für Verschlüsselung ACG=6, TCA=52 usw. ist? das wäre wirklich nett :-) andrea

Das ganze stellt ein Zahlensystem mit der Basis vier da. Hierbei stehen die verschiedenen Zeichen für die verschiedenen Ziffern: A=0; C=1; G=2; T=3. TCA entspricht also der Zahl 310 zur Basis 4. Wenn man das auf die Basis 10 umrechnet kommt man auf $3*4^{2}+1*4^{1}+0*4^{0}=3*16+1*4+0*1=52$. Ist also eigentlich ganz einfach. Ich persönlich finde das Beispiel aber nicht wirklich gelungen. Mir fehlte bisher aber die Zeit um den Artikel mal richtig zu überarbeiten. MlaWU 23:17, 15. Nov 2004 (CET)

Dazu möchte ich noch etwas schreiben: Die Nucleotide (A, C, G, T) habe ich aus mehreren Gründen mit Absicht gewählt. Einer Davon war, um von dem wahr-falsch Schema wegzukommen. Es gibt, grundsätzlich, keine falsche Nucleotid-Sequenz. Man kann sicher ein Beispiel finden, wo GOLFSCHLAEGER in Hex '4905EA6FCD3BE423A3DCFC5007' verschlüsselt wird, und bei falscher Anwendung irgend ein Blödsinn heraus. Das ist untransparent und irgendwie auch unehrlich. --Arbol01 23:45, 15. Nov 2004 (CET)

Mich stört an dem Beispiel nicht, daß Du da die Nucleotide verschlüsselst, sondern eher, daß Du eine Kodierung verwendet hast. Wenn ich ein Beispiel hätte konstruieren müssen, hätte ich einfach zwei oder drei Zahlen gewählt und diese verschlüsselt. Eventuell hätte ich in einen Nebensatz auch noch erwähnt, daß diese Zahlen natürlich auch irgendwelche Buchstaben repräsentieren können. Ich hätte das ganze also andersrum aufgezogen. MlaWU 16:25, 17. Nov 2004 (CET)

Signatur validieren

Im Abschnitt "Signieren von Nachrichten" steht: "Kommt keine vernünftige Nachricht dabei heraus, wird die Signatur abgelehnt." Wie entscheidet der Rechner nachher denn ob die Nachricht sinnvoll ist? Der Satz kommt mir inhaltlich nicht einwandfrei vor!

Beim Signieren wird die Nachricht (eigentlich ein Hashwert der Nachricht) mit dem privaten Schlüssel verschlüsselt. Sie kann nun mit dem öffentlichen Schlüssel wieder entschlüsselt werden. Dies kann jederman tun, da der öffentliche Schlüssel bekannt ist. Wenn eine verschlüsselte Nachricht nun aber mit einem öffentlichen Schlüssel entschlüsselt werden kann, weiß man, daß der Absender im Besitz des dazugehörigen privaten Schlüssels sein muß und die Nachricht somit authentisch ist.

In der Praxis wird nicht die Nachricht selbst signiert sondern ein Hashwert der Nachricht. Der Empfänger kann also einfach selbst den Hashwert berechnen und vergleichen ob er mit dem entschlüsselten Hashwert aus der Signatur übereinstimmt. Wenn das der Fall ist, kann er sich über den Absender sicher sein und er weiß, daß die Nachricht unterwegs nicht manipuliert worden ist. MlaWU 22:53, 14. Jan 2005 (CET)

Die Aussage bezog sich vermutlich auf die Korrektheit des Padding. --Mojo1442 16:30, 9. Jul. 2011 (CEST)

Im Abschnitt "Signieren von Nachrichten" steht ebenfalls: "H bildet nun mit codierten Informationen über den Hash-Algorithmus und einer definierten Bytefolge (Padding) die Nachricht K*, die wie oben beschrieben verschlüsselt wird. Beim Prüfen der Signatur erzeugt der Empfänger selbst das K* und vergleicht es mit dem empfangenen."

Das Ganze ist meiner Meinung nach etwas verwirrend, da der Empfänger nach der Entschlüsselung zwar K* erzeugt, danach aber in einem Zwischenschritt noch H erzeugen muss und diesen Wert mit dem empfangenen Hashwert vergleicht. Der obige Satz suggeriert aber, dass die erzeugte Nachricht K* mit der empfangenen verglichen wird, was völliger Blödsinn ist. 15:31, 2. Jan 2006 (CET)

Eigentlich ist es auch völlig unnötig in diesem Artikel über Hashes und ihre Verwendung in Signaturen zu sinnieren. Das hat mit dem RSA-Kryptosystem nunmal nicht viel zu tun. -- MlaWU 00:01, 3. Jan 2006 (CET)

Beweis des RSA unübersichtlich

Sitze grad an meiner Facharbeit und finde den Beweis nicht besonders übersichtlich, habe allerdings zwei gute Quellen gefunden, die das schöner beschreiben;

http://yimin.sinuslab.net/doc/mathematik_von_rsa.pdf - ca 20 seiten - offensichtlich eine facharbeit aus österreich http://www.perlguru.org/download/m3_zahlentheorie.pdf - ca 40 seiten - script eines matheprofs

beide über google gefunden

vielelicht findet jemand die zeit in anlehnung an diese beiden werke den beweis zu überarbeiten

Für die Wiener Quelle ist vermutlich Seite 16 am interessantesten. Stern 22:58, 14. Jan 2006 (CET)

Meiner Meinung nach sollten in Wikipedia überhaupt keine Beweise dargestellt werden! Dies gehört in ein Lehrbuch aber nicht in eine Enzyklopädie. --Mojo1442 16:30, 9. Jul. 2011 (CEST)

Der Beweis könnte vereinfacht werden

Warum mod p und mod q und dann über den chin. Restsatz, wenn es mittels Satz von Euler (statt kleinem Fermat) auch direkt modulo $n$ gehen würde?

$a^{(k\cdot \varphi (n))+1}\equiv 1^{k}\cdot a{\pmod {n}}$, wegen $a^{\varphi (n)}\equiv 1{\pmod {n}}$

Das Problem ist: falls $a$ und $n$ nicht teilerfremd sind, dann geht der Satz von Euler nicht. Über den chinesischen Restsatz sieht man: es geht auch in diesem Fall.

Nach dem kleinen Satz von Fermat gilt für alle zu $p$ teilerfremden Zahlen $a$ der Zusammenhang $a^{p-1}\equiv 1{\pmod {p}}$. Hier wird allerdings auch schon vorausgesetzt, dass $a$ und $p$ (und auch $q$) teilerfremd sind. Damit muss auch $n$ und $a$ teilerfremd sein und man kann wieder direkt den Satz von Euler nehmen.

Erstes Semester Mathestudium?

Also mal ehrlich, der Artikel liest sich wie von einem Studenten aus dem ersten Semester Mathestudium. Nichts für ungut, es ist natürlich super, wenn sich jemand die Zeit nimmt, das alles zu schreiben, aber wenn jemand keine Ahnung von kryptographischen Grundlagen hat, dann soll er die woanders lesen, und nicht in einem RSA-Artikel. 83.64.176.129 23:53, 27. Aug 2006 (CEST) PS: Werft mal einen Blick auf den englischen RSA-Artikel! 83.64.176.129 23:56, 27. Aug 2006 (CEST)

teilerfremd

hallo! hätte mal ne frage zu dem schritt: "Die Zahl e muss zu 120 teilerfremd sein. Wir wählen e = 23. Damit bilden e = 23 und N = 143 den öffentlichen Schlüssel" wieso wird die zahl 23 gewählt und nicht ein anderer teilerfremder wert? wird das per zufallsgenerator bestimmt oder wie ? würde mich über eine anwort freuen mfgvervv

die wahl von e ist wirklich zufällig. du kannst auch drei nehmen, was aber sicherheitskritisch ist. um sich aufwand beim verschlüsseln zu sparen nutzt man meist binärzahlen mit wenigen einsen, so z.b. 2^16 + 1. gruß --Murkel ^(anmurkeln) 23:35, 22. Nov. 2006 (CET)

ah so ist das, danke für die antwort mfg ehykey

Liste mathematischer Symbole????

Wieso wird in einem Artikel über ein asymetrisches Kryptosystem auf die Liste mathematischer Symbole verwiesen? Dieser Verweis hat meiner Meinung nach wenig mit RSA zu tun, nur weil gewisse Symbole zur Beschreibung und zum Beweis des Verfahrens verwendet wurden!

Verschlüsselungs- /Entschlüsselungsvorschrift: Kongruenzzeichen

Sollte es bei der Verschlüsselungsvorschrift nicht $C=K^{e}\mod N$ statt $C\equiv K^{e}\mod N$ heißen? Also Gleichheits- statt Kongruenzzeichen? Ebenso dann auch bei der Entschlüsselungsvorschrift. --Agent00 ~ Diskussion 18:47, 11. Feb. 2007 (CET)

ohne dass jetzt zu mathematisch auszuwalzen, nein die (mathematische) gleichheit gilt nicht, "nur" die (mathematische) äquivalenz. für weitere informationen siehe Kongruenz. gruss --Murkel ^(anmurkeln) 01:17, 12. Feb. 2007 (CET)

$C\equiv K^{e}\mod N$ Ist richtig. Die Form $a\equiv b\mod c$ ist an sich gleichbedeutend mit $(a\mod c)=(b\mod c)$.

Berechnung der Inversen zu e

Wie genau berechnet man nun das Inverse zu e? Wie wendet man den erweiterten euklidischen Algorithmus an? Diser Schritt fehlt meiner Meinung nach im Bespiel.

Bist du schon mal dem dort angegebenen Link gefolgt? --Stefan Birkner 18:26, 27. Mai 2007 (CEST)

Was ist k?

hallo, kann mir bitte jemand sagen, was k bei der berechnung der inversen ist? danke dq

die beiden zusammenhänge $ed\equiv 1\mod \phi (n)$ und $ed+k\phi (n)=1$ sind gleichwertig. erster ist die fragestellung bei rsa zur inversenbestimmung. zweiter bildet den ansatz für den erweiterten euklidischen algorithmus. gruß --Murkel ^(anmurkeln) 21:43, 14. Jun. 2007 (CEST)

Ich habe im Artikel ergänzt, dass $k$ nicht weiter wichtig ist. Dq, hätte dir die jetzige Formulierung geholfen? --Stefan Birkner 12:26, 15. Jun. 2007 (CEST)

Beweis unvollständig!

Der hier angegebene Beweis gilt nur für $x\in \mathbb {Z} _{n}^{*}$, also für alle $x$, die im Körper der Einheiten von $\mathbb {Z} _{n}$ sind. Das sind die Elememte für die gilt $ggT(a,n)=1$

Beispiel: $\mathbb {Z} _{10}=\{0,1,2,3,4,5,6,7,8,9\}$

$\mathbb {Z} _{10}^{*}=\{1,3,7,9\}$ (vergleiche $|\mathbb {Z} _{10}|$ mit $\phi (10)$)

Der kleine Satz von Fermat gilt nun für $x\in \mathbb {Z} _{10}^{*}$

$1^{4}=1\equiv 1{\bmod {1}}0$

$3^{4}=81\equiv 1{\bmod {1}}0$

$7^{4}=2401\equiv 1{\bmod {1}}0$

$9^{4}=6561\equiv 1{\bmod {1}}0$

nicht aber für Elemente $x\in \mathbb {Z} _{10}/\mathbb {Z} _{10}^{*}$:

$2^{4}=16\equiv 6{\bmod {1}}0$

$4^{4}=256\equiv 6{\bmod {1}}0$

$5^{4}=625\equiv 5{\bmod {1}}0$

$6^{4}=1296\equiv 6{\bmod {1}}0$

$8^{4}=4096\equiv 6{\bmod {1}}0$

Der RSA stimmt trotzdem! Nur muss man das ganze noch beweisen für $x\notin \mathbb {Z} _{n}^{*}$.

Sehr gut bemerkt. In der Tat vergisst man das oft zu erwähnen und stolpert dann darüber in der Prüfung. Aber ich konnte mich seinerzeit retten ;-).

Der RSA funktioniert, weil für alle $m$ die Kongruenz $m^{d\cdot e}\equiv m^{k\varphi (n)+1}\equiv m{\bmod {p}}$ und entsprechend für $q$ gilt.

• Für die $m$, die nun zu $p$ oder $q$ teilerfremd sind, folgt das aus dem Kleinen Fermat.

• Die $m$, die nicht zu $p,q$ teilerfremd sind, müssen durch $p,q$ teilbar sein (nicht vergessen, sind ja beides Primzahlen). In diesen Fällen wird aber die Kongruenz zu $0\equiv 0$ und gilt damit auch.

Wenn eine Kongruenz $m^{d\cdot e}\equiv m$ jetzt modulo zweier teilerfremder Primzahlen $p$ und $q$ gilt, dann gilt sie auch modulo $p\cdot q$ (Chinesischer Restsatz).

Fertig!

Meiner Meinung nach sollten in Wikipedia überhaupt keine Beweise dargestellt werden! Dies gehört in ein Lehrbuch aber nicht in eine Enzyklopädie. --Mojo1442 16:30, 9. Jul. 2011 (CEST)

Deshalb habe ich den Beweis ja auch nur auf der Diskussionsseite angegeben.--Ann (Diskussion) 23:37, 3. Feb. 2021 (CET)

Weblink -> PHP Code

@Jesi:

"entfernt, genügend allgemeine vorhanden"

- Eine nicht-wahrheitsgemäße Behauptung nennt man Lüge.

"Weblink, siehe WP:WEB"

- Das habe ich mir durchgelesen und konnte keinen Grund feststellen,
  warum es falsch ist, den Link zu dem Quelltext einer RSA implementierung
  in PHP zu posten.
  Links zu Weblogs vermeiden. Gut. Die Website ist kein Weblog, nur ähnlich aufgebaut.
  Dass der Code nicht hilfreich ist, stimmt schlichtweg nicht.

Ich bitte dich jetzt, nicht noch ein drittes mal grundlos meinen Link zu löschen. Danke.

(nicht signierter Beitrag von 78.50.206.58 (Diskussion) 04:18, 27. Mär. 2008)

Immer locker bleiben.

Bitte schaue dir doch einmal die anderen Links an. Warum soll dieser Link für eine Enzyklopädie sinnvoll sein? Weil man eine PHP-Klasse runter laden kann? Oder weil man einen völlig unkommentierten Quelltext lesen darf? Ich halte diesen Link auch nicht für sehr sinnvoll. Warum sollte dieser Link hilfreich sein? Beachte bitte, dass dies eine Enzyklopädie ist und keine Link-Sammlungs-Seite für Informatiker, welche es einfach haben möchten und zu jeder Sprache eine Umsetzung hier finden wollen. In den anderen Links ist um einiges mehr erklärt und sogar ein Informatik-Grundkursler schafft es seinen Quelltext ordentlich in seiner Facharbeit zu kommentieren (-> http://www.basement-softworks.de/files/Facharbeit_DDieckelmann.pdf ). Das sollte völlig ausreichen. Die Anforderungen an Weblinks sind klar und deutlich: Aussagekräftig, weitere oder ergänzende hilfreiche Informationen, nützlich und nicht überflüssig müssen sie sein. Ich erkenne nicht, dass dein Link irgendeine Anforderung erreicht. Ich hätte dich auch revertiert. Grüße --Srvban 04:38, 27. Mär. 2008 (CET)

Das meiste ist ja schon gesagt. Und wenn du dir WP:WEB von Anfang bis Ende wirklich genau durchliest, wirst du sicher weitere Erkenntnisse gewinnen. -- Jesi 05:00, 27. Mär. 2008 (CET)

-Nagut-

• sigh*

(Der vorstehende, nicht signierte Beitrag stammt von 78.50.206.58 (Diskussion • Beiträge) 5:24, 27. Mar 2008) Srvban 07:21, 27. Mär. 2008 (CET)

Ich danke dir für deine Einsicht. Es zeugt von Größe! Ich hoffe, dass wir dich nicht deshalb hier abgeschreckt haben. Neue Autoren sind in der Wikipedia immer gesucht. Ich würde mich freuen, wenn wir dich hier behalten könnten. Grüße --Srvban 07:21, 27. Mär. 2008 (CET)

Zurücksetzen von änderung 46162910 von NiTeChiLLeR

Ich habe entgegen der Behauptung von NiTeChiLLeR, keine Belege angegeben zu haben, wohl deutlich genug auf Kerckhoffs’ Maxime verwiesen. Diese Doktrin ist in moderner Kryptographie völlig anerkannt und steht an dieser Stelle nicht zur Diskussion. "Die Teilschlüssel [...] zu unterschiedlichen Zeiten und mit höchst unterschiedlichen Methoden [auszutauschen]" wiederspricht einerseits völlig diesem Prinzip, da ihre Sicherheit rein auf dem -geheimgehaltenen- Austauschmuster basiert. Außerdem wäre die beschriebene Methode wohl Definitionsgemäß kein kryptographisches Verfahren, sondern eher eine Enkodierung, da ein kryptographischer Schlüssel nicht Teil von ihr ist. Bitte um Erlaubnis den fehlerhafen Absatz wieder zu streichen --79.208.250.216 13:45, 18. Mai 2008 (CEST)

Du bist mit deiner Änderung im Recht und ich habe sie dehalb wiederhergestellt (bzw. den Absatz wieder gelöscht). --Stefan Birkner 14:55, 18. Mai 2008 (CEST)

kann mir jemand erklären, warum das auf der seite nicht dichtbar ist? bei der letzten änderung ist der fehlerhafte absatz defintiv schon gelöscht, "gesichtet" ist die Version auch. Trotzdem ist auf der Artikel-Seite der Absatz immer noch vorhanden. Warum wird hier nicht die neuste Version angezeigt? --79.208.218.254 00:09, 21. Mai 2008 (CEST)

Missverständlichkeit im zweiten Absatz beim Punkt Verfahren

Zitat: "Nur der Empfänger kann diese entschlüsseln, da nur er die „Zusammensetzung“ des von ihm erzeugten (öffentlichen) Schlüssels kennt."

Das klingt so als bräuchte man zum Entschlüsseln mehr als nur den privaten Schlüssel, irgendwelche Zusatzinformationen oder gar den öffentlichen Schlüssel selbst. Dass ist jedoch nicht richtig, oder? Beide Schlüssel sind gleichwertig. Der private Schlüssel reicht aus, um Nachrichten zu entschlüsseln, die mit dem öffentlichen Schlüssel verschlüsselt wurden, und umgekehrt funktioniert es genauso.

Daher sollte es an der fraglichen Stelle vielleicht eher lauten:

"Wenn nun eine Nachricht einem Empfänger verschlüsselt zugeleitet werden soll, generiert dieser einen öffentlichen und einen privaten Schlüssel. Der Nachrichtenabsender verwendet den öffentlich bekanntgemachten Schlüssel, indem er damit seine Botschaft verschlüsselt. Nur der Empfänger kann diese entschlüsseln, da nur er den dafür erforderlichen privaten Schlüssel kennt."

Ich schreibe dies hier, weil mir beim Lesen der Widerspruch aufgefallen ist, dass man beim Verifizieren einer Signatur nur den öffentlichen Schlüssel benötigt, beim Entschlüsseln einer Nachricht aber scheinbar mehr als den privaten (s. Zitat oben). (nicht signierter Beitrag von 89.59.170.244 (Diskussion | Beiträge) 19:49, 22. Okt. 2009 (CEST))

„262626“

Wenn man genug von der Materie verstanden hat, stolpert man wahrscheinlich nicht diese über 262626. Aber wenn nicht, wenn man die kurz zuvor auftauchende Passage „Dazu verwendet man in der Praxis zum Beispiel den ASCII-Code.“ nicht schon wieder vergessen hat … Jedenfalls ist die größte darstellbare, natürliche und dreistellige, Zahl aus einem 27er-Zahlensystem $27^{3+1}-1$. Also (dezimal) 531440 – (tendenziell steigend) etwas mehr als 26⋅10101. (nicht signierter Beitrag von 87.163.49.101 (Diskussion | Beiträge) 03:40, 6. Feb. 2010 (CET))

Meiner Meinung sollten alle Bepsiele aus dem Artikel entfernt werden. Dies hier ist kein Lehrbuch. --Mojo1442 16:30, 9. Jul. 2011 (CEST)

Stimmt aber nicht. Im Stellenwertsystem werden die Stellen von der 0-ten Potenz aus berechnet. Also in einem 27er System hat die 1. Stelle $27^{0}$. Dies lässt sich auch anhand des 2er Systems veranschaulichen: Die höchste 2 Stellige Zahl ist dort $2^{0}\cdot 1+2^{1}\cdot 1=11_{2}=3$. Also erhält man mit $n=2$: $2^{n}-1=2^{2}-1=3$. Entsprechend erhält man im 27er System mit $n=3$: $27^{3}-1=27^{0}\cdot 26+27^{1}\cdot 26+27^{2}\cdot 26=19682_{10}=262626_{27}$. Du hast also eine 4 Stellige Zahl berechnet. --84.170.157.10 18:04, 15. Jan. 2019 (CET)

Einleitungssatz

Der Einleitungsabsatz ist meiner Meinung nach im Ausdruck nicht ganz glücklich. Ich schlage mal einen neuen vor, allerdings wollte ich ihn nicht gleich übernehmen, da er vielleicht auch noch etwas ausgereifter sein könnte.

Alt: RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten verwendet wird, und einem öffentlichen Schlüssel, mit dem man verschlüsselt oder Signaturen prüft. Der private Schlüssel wird geheim gehalten und kann nicht oder nur mit extrem hohem Aufwand aus dem öffentlichen Schlüssel berechnet werden.

Vorschlag: RSA (benannt nach seinen Entwicklern Ronald L. Rivest, Adi Shamir und Leonard Adleman) ist ein asymmetrisches Kryptosystem, zum Verschlüsseln von Nachrichten und zum Erstellen digitaler Signaturen. Mit einem geheimgehaltenen privaten Schlüssel können Nachrichten entschlüsselt oder signiert werden. Ein öffentlicher Schlüssel ermöglicht es Nachrichten zu verschlüsseln oder Signaturen zu prüfen.

Verbesserungsvorschläge? Vielleicht das „geheimgehalten“ noch weglassen? --Bananenfalter 18:08, 9. Aug. 2010 (CEST)

Kryptosystem

der begriff kryptosystem fuehrt leider immer wieder zu verwirrung [1]. ich finde, wir sollten uns muehe geben, ihn zu vermeiden und verschluesselung und signatur klarer zu trennen. RSA ist eigentlich eine TOWP und wird in der form weder fuer verschluesselung noch fuer signaturen eingesetzt. der begriff "RSA-Kryptosystem" kann als historisch gewachsen beibehalten werden, wir sollten uns aber muehe geben, verwirrung zu vermeiden. --Mario d 15:24, 7. Jul. 2011 (CEST)

Kannst du bitte erläutern, warum der Begriff Kryptosystem zu Verwirrung führt? --Mojo1442 16:37, 9. Jul. 2011 (CEST)

RSA ist kein Algorithmus, es ist mehr und eigentlich auch abstrakter. Im einfachsten Fall umfasst RSA mehere Algorithmen (z.B. zur Verschlüsselung und zur Entschlüsselung), zusammen mit ganz bestimmten Relationen zwischen den Parametern und Schlüssen. Dazu kommen noch die Algorithmen zur digitalen Signatur (Signierung, Verifikation). In vielen Veröffentlichungen werden Verschlüsselungs- oder digitale Signaturverfahren als Menge von 3 Algorithmen (GEN, ENC, DEC) bzw. (GEN,SIG,VER) dargestellt, wobei die Generierung von Parametern und Schlüsseln der 3. Algorithmus ist.

Außerdem hat ein Kryptosystem eine andere Abstraktionsstufe als üblicherweise ein Algorithmus. So werden z.B. bei der RSA-Signatur ein Padding und eine Hashfunktion verwendet, ohne dass diese festgelegt werden. Bei einem Algorithmus müsste man dies tun, weil sonst die Handlungsvorschrift nicht eindeutig wäre. Siehe Algorithmus. Bei einem Algorithmus müssste man also RSA + Padding + Hshfunktion genau festlegen (z.B. RSA + PSS + SHA-256), aber selbst dann bleiben die modulare Arithmetik und die Methode der modularen Exponentiation (z.B. Nutzung des chinesischen Restsatzes. Window-Methode) zu spezifizieren. Sicherlich kann man Algorithmen auch abstrakter definieren und Details auf der Implementierungsebene offen lassen, aber im Fall von RSA (und anderen kryptosystemen) werden bestimmte Bestandteile (z.B. Hashfunktion) überhaupt nicht festgelegt.

Wenn dir der Begriff Kryptosystem nicht gefällt, käme noch kryptographisches Verfahren in Frage.--Mojo1442 15:09, 9. Jul. 2011 (CEST)

Ich gebe zu, dass in Deutschland verschiedene öffentliche Stellen und Regelwerke von "kryptographischen Algoithmen" sprechen. Z.B. der Algorithmenkatalog der Bundesnetzagentur. Deswegen muss das aber noch nicht korrekt sein. Außerdem werden in diesen Dokumenten i.d.R. auch alle Bestandteile des Verfahrens (inkl. Padding und Hashfunktion) behandelt.--Mojo1442 16:35, 9. Jul. 2011 (CEST)

deine antwort zeigt ja schon deutlich, wo es zu verwirrungen kommt. es gibt die RSA TOWP, die kann auch direkt als signatur oder verschluesselung eingesetzt werden, was wegen des determinismus bzw. der homomorphie-eigenschaft allerdings ueberhaupt keinen sinn macht. jedes bessere lehrbuch warnt vor der verwendung von "textbook-RSA". wenn ich eine signatur brauche, nehme ich RSA-PSS oder ein aehnliches verfahren, fuer die verschluesselung RSA-OAEP oder aehnliche. beide wuerde ich hier keinesfalls nur als "RSA" bezeichnen, weil das eben zu verwirrung fuehrt. was davon ist jetzt das "RSA-Kryptosystem"? schon der begriff wird ganz unterschiedlich verwendet, wie die einzelnachweise bei Kryptosystem zeigen. eigentlich sollten wir konsequent sein und das lemma in "RSA" o. ae. umbenennen, so wie es die englische WP gemacht hat.

zum thema "algorithmus": es ist technisch kein problem, aus drei algorithmen einen zu machen, indem man am anfang eine fallunterscheidung trifft. die multipliktion koennen wir durchaus als atomare operation definieren. wie sie dann spaeter implementiert wird, ist voellig nebensaechlich, beim Euklidschen alg. ist es ja auch egal, wie meine subtraktion aussieht. hashfunktionen kommen bei RSA erstmal nicht vor, und in der regel wird auf der abstraktionsebene auf der wir uns hier bewegen sollten nur spezifiziert, welche eigenschaften sie erfuellen sollen. spaeter koennen dann gerne noch hinweise auf spezielle cipher-suites kommen, aber einem artikel, der so allgemein ist wie dieser, sollten wir ganz oben anfangen. --Mario d 12:12, 11. Jul. 2011 (CEST)

Also ich benutze RSA für Hash-Funktionen, für Verschlüsselung und Entschlüsselung, speziell Authentifizierung und Signierung.

Weil ich das Konzept nicht auf eine der Anwendungen reduzieren wollte, finde ich den Begriff Krypto-System treffend.

Im Kern haben wir eine Einweg-Funktion. --Action127 (Diskussion) 15:32, 10. Dez. 2021 (CET)

Beispiele entfernen

Wikipedia ist kein Lehrbuch. Ich sehe daher nicht ein, warum der Artikel mit Beispielen gespickt sein muss. Dies macht ihn sehr unübrsichtich und verhindert die für eine Enzyklopädie erforderliche Prägnanz. Bevor ich das alles lösche, sollten wir aber darüber diskutieren. Ich habe auch mal eine allgemeine Frage zur Zulässigkeit von Rechenbeispielen in den Hilfeseiten gestellt. --Mojo1442 16:55, 9. Jul. 2011 (CEST)

beispiele tragen fuer anfaenger sehr zum verstaendnis bei, und das ist ja unser ziel. ich wuerde aber verweise auf "square-and-multiply" mindestens auf das vollstaendige beispiel unten verschieben, das muss an der stelle nicht kommen. --Mario d 12:15, 11. Jul. 2011 (CEST)

modul/modulo

meines wissens nach wird die funktion modulo genannt, die zahl hingegen modul(us). --Mario d 09:30, 30. Okt. 2011 (CET)

So ist das. --Bananenfalter 12:21, 30. Okt. 2011 (CET)

RSA-Schlüssel nicht so zufällig wie wünschenswert

Aktuelle Meldung: http://www.heise.de/security/meldung/RSA-Schluessel-nicht-so-zufaellig-wie-wuenschenswert-1435304.html (nicht signierter Beitrag von 77.49.181.124 (Diskussion) 13:52, 16. Feb. 2012 (CET))

die frage ist, was wir aus dem artikel fuer dieses lemma rausziehen koennen. das problem ist ja eher ein praktisches (schlechter zufall); die autoren scheinen nahezulegen, dass RSA da ein bischen anfaelliger ist als DLOG-basierte verfahren, weil mehrere zufallswerte generiert werden muessen und ein angreifer schlechte schluessel leichter erkennen kann. --Mario d 17:34, 17. Feb. 2012 (CET)

Ist zu erwarten, dass nicht offengelegte Schlüsselgeneratoren Hintertüren eingebaut haben; da ist zu viel Druck durch den Ausspionierungszwang diverser Branchen. Deswegen baue ich Zufalls- und Schlüsselgeneratoren selber. Z.B. https://www.random.org/ ist eine unabhängige sinnvolle Zusatz-Quelle. Bei den als hochsicher geltenenden Elliptischen Verschlüsselungsverfahren hat die NSA von vorneherein festgelegt, welche Schlüssel zu verwenden sind; das ist auch sowas ...! Spätestens, wenn Quantencomputer kombinatierische Probleme von mehreren hundert Bit lösen können, sind die elliptischen Verfahren tot, ebenso AES. Von Sicherheitsexperten, z.B. NIST, werden jetzt schon RSA-Schlüssel mit mindestens 4096 Bit empfohlen. --Action127 (Diskussion) 15:48, 10. Dez. 2021 (CET)

Verifikation (Entschlüsselung mit dem öffentlichen Schlüssel)

Bei der binäre Exponentiation scheint sich ein Fehler eingeschlichen zu haben: Sollte es nicht heißen ...7 hoch 7 mod 143 = 2 statt wie jetzt ... 7 mod 143 = 2? (nicht signierter Beitrag von 89.144.206.235 (Diskussion) 14:35, 16. Mai 2013 (CEST))

der punkt vor der 7 ist ein malpunkt. --Mario d 16:25, 16. Mai 2013 (CEST)

RSA & NSA

Wie siehts jetzt wegen der Zusammenarbeit zwischen RSA und NSA bezüglich Sicherheit aus? Die RSA hat dies am 26.02.2014 öffentlich bestätigt. Zu den 10 Millionen für ein Backdoor schweigen sie noch immer. Gehört zu dieser Thematik nichts in den Artikel? http://www.golem.de/news/rsa-security-chef-coviello-verteidigt-zusammenarbeit-mit-der-nsa-1402-104817.html (nicht signierter Beitrag von 2A02:120B:2C27:A930:AC3E:3300:1183:6241 (Diskussion | Beiträge) 19:19, 26. Feb. 2014 (CET))

nein, zu dieser thematik gehoert nichts in den artikel. es gibt keinen hinweis darauf, dass das RSA-kryptosystem von diesen geschichten betroffen ist. --Mario d 20:09, 26. Feb. 2014 (CET)

Kann man p, q aus N, e, d berechnen?

Wenn ich das richtig verstanden habe, ist es nur eine Erleichterung zum Verschlüsseln, dass man p, q, d_p, d_q und q_inv mit im "Private Key" abspeichert. Es würde ja d alleine reichen (und N, das man aus dem Public Key holt). Richtig? Falls ja: Wie kann man p und q dann aus N, e und d berechnen? --RokerHRO (Diskussion) 21:46, 26. Aug. 2014 (CEST)

richtig, d alleine reicht zum entschluesseln. um p und q zu berechnen gibt es einen algorithmus, z. B. in NIST SP 800-56B, appendix C. --Mario d 18:29, 28. Aug. 2014 (CEST)

Danke. Ich schau mal, ob OpenSSL das kann. Dort sind die "RSA private Keys" nämlich aufgrund von p und q usw. deutlich größer als die Public Keys, was mich schon irgendwie wurmt. Laut OpenSSL-Doku kommt die Lib auch mit Private Keys zurecht, in denen diese Werte fehlen, nur rechnet es dann langsamer. Drum wäre es ja evtl. wünschenswert, diese fehlenden Werte wieder zu ermitteln, wenn OpenSSL das nicht selber kann/macht. :-) --RokerHRO (Diskussion) 11:16, 29. Aug. 2014 (CEST)

hier gibt es ein tool dafuer: http://rsaconverter.sourceforge.net/ --Mario d 12:58, 29. Aug. 2014 (CEST)

Man kann $p$ und $q$ aus $N$ und $d$ berechnen, wenn $e$ hinreichend klein ist. Aber in OpenSSL gibt es solche Funktion nicht. Sondern das geht so: $N=p*q$ und $e*d\equiv 1{\bmod {(}}p-1)(q-1)$. Ist $e$ klein, so ist $e*d=1+k(pq-p-q+1)$ und $k$ kann durch $(e*d-1)/N$ abgeschätzt werden. Hat man das richtige $k$ gefunden, so ist $p*q=N$ und $p+q=N+1-(e*d-1)/k$. Der Rest geht mit dem Vietaschen Wurzelsatz.--Ann (Diskussion) 23:13, 1. Feb. 2021 (CET)

Verwechslung e/d?

Im Abschnitt zur Erzeugung eines Schlüsselpaars steht der folgende Satz: "Bei Wahl eines d mit weniger als einem Viertel der Bits des RSA-Moduls kann d – sofern nicht bestimmte Zusatzbedingungen erfüllt sind – mit einem auf Kettenbrüchen aufbauenden Verfahren effizient ermittelt werden." Müsste dort nicht "Bei Wahl eines e..." stehen? --Trebuh~dewiki (Diskussion) 12:07, 1. Aug. 2015 (CEST)

nein, d ist richtig. den beleg dazu (leider nur auf englisch) erhältst du, wenn du auf die hochgestellte kleine zahl hinter dem satz klickst und dann dem dort angegebenen link folgst. --Mario d 16:28, 4. Okt. 2015 (CEST)

Kenne auch die Darstellung mit (N,d) als öffentlichen Schlüssel. Wesentlich ist, dass der "kleine" Exponent im öffentlichen Schlüssel vorkommt und so tut das der Artikel:

"e kleiner als die Fermat-Zahl F 4 = 2 16 + 1 = 65537..." --Action127 (Diskussion) 11:23, 4. Apr. 2021 (CEST)

Warum ist die 5. Fermat-Zahl üblich?

... üblich ist die 5. Fermat-Zahl 2¹⁶+1=65537 Warum ? (nicht signierter Beitrag von 79.220.12.106 (Diskussion) 17:22, 11. Nov. 2016 (CET))

Die Diskrete Exponentialfunktion kann schneller berechnet werden, wenn der Exponent ein niedriges Hamming-Gewicht hat. Wenige Einsen -> schnellere Verschlüsselung bzw. Verifikation einer Signatur. Andere Fermat-Zahlen sind ebenfalls üblich, aber 65537 dürfte wohl am weitesten verbreitet sein. --Matthäus Wander 19:45, 11. Nov. 2016 (CET)

Das Potenzieren geht bei Fermat-Zahlen (oder allgemeiner bei Zahlen der Form 2^k+1) deshalb so schnell, weil man, um für eine natürliche Zahl m die Potenz m^2k+1 zu berechnen, m nur k mal quadrieren und am Ende noch einmal m hinzumultiplizieren muss. Dies ist das sogenannte Square-and-Multiply-Verfahren. Zum Beispiel kann man m⁶⁵⁵³⁷ nach nur 17 Multiplikationen (und 17 mal modulo rechnen) erhalten. Zudem ist 65537 die größte bekannte Fermatsche Primzahl (und damit die größte bekannte Primzahl der Form 2^k+1). Die Primzahleigenschaft macht es einfacher, einen RSA-Modul mit teilerfremder eulerscher Funktion zu finden. --87.160.20.88 16:57, 13. Nov. 2016 (CET)

Die Wahrscheinlichkeit bei $e=2^{32}+1$ auf eine Primzahl zu stoßen, die nicht zu $e$ teilerfremd ist, ist allerdings auch nicht sehr groß ($2^{32}+1=641*6700417$). ] (nicht signierter Beitrag von Annie Yousar (Diskussion | Beiträge) 22:55, 1. Feb. 2021 (CET))

3DES "sehr sicher"?

"Als sehr sicher eingestufte Algorithmen zur symmetrischen Verschlüsselung gelten 3DES und AES." -> finde ich gewagt. Das Crypto-Poster der Westfälischen Hochschule listet 3DES schon 2014 als unsicher: https://www.internet-sicherheit.de/crypto-poster/ --91.44.78.147 10:55, 28. Dez. 2016 (CET)

ich habe 3DES entfernt, die blockgröße ist mittlerweile zu gering (sweet32-angriff). gedeckt ist das durch die aussage "Insgesamt wird hier empfohlen, Triple-DES nicht in neuen Systemen zu verwenden" der BSI-richtlinie zu kryptographischen verfahren [2] (Abschnitt 1.4, 1.). --Mario d 13:56, 5. Jan. 2017 (CET)

Schnelligkeit

Angeblich langsamer als symm. Verschlüsselung, sagt der Artikel. Das ist Unsinn und gilt nur für Simulationen auf Standard-CPUs. Es kommt immer auf die konkrete Realisierung der Hardware an. Wenn du bei RSA die Register nur groß genug definierst, kommst du locker auf eine höhere Geschwindigkeit als ein DES-Chip. WIr lagen vor Madagaskar (Diskussion) 12:20, 5. Jan. 2017 (CET)

Ja, auf real existierender Hardware ist RSA-2048 und selbst ein unsicheres RSA-1024 deutlich langsamer als AES-128 oder andere symmetrische Chiffren mit 128-Bit. Klar, mit einem speziellen RSA-Chip sähe es vielleicht anders aus, aber die existieren meines Wissens nicht.

Wenn du aber eine Quelle hast, dass auf einer bestimmten, real existierenden Hardware ein RSA-2048 schneller oder etwa genauso schnell ist wie AES-128, dann darf das natürlich gerne in den Artikel. --RokerHRO (Diskussion) 12:41, 6. Jan. 2017 (CET)

Selbstverständlich gibt es spezielle RSA-Chips. Und selbstverständlich sind die um Größenordnungen langsamer als Vergleichbare für AES oder DES. Grund. Für RSA brauchst du halt schon alleine 2·lb(n)≃2048 Multiplikatioen. Für AES-128 bzw. 256 10 bzw. 14 Runden a ~16 Operationen. IM Worst Case ist man da bei 224 Operationen. Bei DES wäre man bei 16 Runden a ~10 Operationen ≃ 160 Operationen. Selbst auf dem Theoretischen Modell der Registermaschine die beliebige Operationen auf beliebig großen Register Registern ausführen kann, ist man da um den Faktor 10 schneller. Real ist eine Multiplikationen bei weitem nicht so schnell wie ein XOR oder Shift und vor allem: Auf realer Hardware gilt: Wenn man sowas wie Multiplikationen ausführen will, wo wirklich alle bits miteinander was zu tun haben, dann wird die Hardware langsamer, weil über größere Strecken kommuniziert werden muss. Je größer das Register wird. Ein 1024 Register wird in echt nie so schnell multiplizieren wie eines mit 128. (Das gilt explizit nicht für Für xor oder shift.) --Fabiwanne (Diskussion) 02:52, 17. Jul. 2017 (CEST)

Denke, RSA hat wesentlich mehr Elementaroperationen, konkret: Potenzieren einer großen Zahl ist komplexer als ein paar Schieberegister durchzuiterieren.

Wenn es wirklich um Sicherheit geht, dann ist mangelnde Performance ein guter Faktor! --Action127 (Diskussion) 15:56, 10. Dez. 2021 (CET)

Bedeutung "Bits" bei Schlüssellänge

Wenn z.B. von einem 2048-Bit-RSA-Zertifikat die Rede ist, worauf bezieht sich diese Zahl? Auf N oder jeweils auf p und q? Und was genau ist mit 2048 Bit gemeint? Ich kann ja jede Zahl von 0 bis 2^2048-1 als 2048-stellige Binärzahl schreiben (mit entsprechend vielen führenden Nullen). Oder soll damit ausgedrückt werden, daß das höchstwertige Bit immer 1 ist?

Die Frage ist berechtigt. Es steht in der Tat nirgends im Text. :-o

Nun, gemeint ist hier stets die Länge von N, also p und q haben in dem Beispiel jeweils 1024 Bit Länge.

Die "Länge" ist dabei wirklich so zu verstehen, dass das höchste Bit (also Bit 1023, wenn man bei 0 anfängt zu zählen) gesetzt ist. Beim Generieren eines RSA-Schlüssels wird p und q jeweils erzeugt, indem 1024 Zufallsbits genommen werden, dann das höchste und das niedrigste Bit auf 1 gesetzt werden und dann ein Primzaltest gemacht wird, so oft, bis man eine "höchstwahrscheinliche Primzahl" gefunden hat.

Hm, aber wo baut man das am besten im Artikel ein? *grübel*

--RokerHRO (Diskussion) 12:30, 9. Jul. 2017 (CEST)

Alles klar, danke. Wie viele solcher Primzahlpaare gibt es denn, die die im Artikel angegebene Bedingung $0{,}1<|\log _{2}p-\log _{2}q|<30$ erfüllen? Primzahlen werden doch mit wachsender Größe immer seltener. Wenn man dann noch eine Bedingung stellt, bleiben evtl. nur noch so wenige Primzahlen übrig, daß man sie vorberechnen könnte und nur noch darauf warten müßte, daß ein Server das entsprechende N verwendet.

Zuerstmal: Für den Angriff ist völlig irrelevant, wieviele es gibt. Du musst den gesamten Suchraum durchsuchen, um alle solchen Paare zu finden.

Da du auch für das generieren btw. so ein paar finden musst, kann es nicht so selten sein. Drauf kommt man auch beim nachrechnen: Laut Primzahl ist in dem Bereich etwa jede 1500. Zahl Prim. Trotzdem hier mal für die Anzahl: Da die Primzahlen etwa gleich verteilt sind ist die Untere Schranke ziemlich Wurst. Die obere Schranke sorgt maximal einen Anteil von 2⁻²⁰ gar keinen passenden Partner findet. Du hast also ca. 2^(1024-10)=2^1014 p für die es mindestens ein passendes q gibt. Weit mehr als es beispielsweise mögliche AES Schlüssel gibt. Und das sind nur die, für die es mindestens einen Partner gibt. Die Kombinationsmöglichkeiten dürften nochmal deutlich größer sein. Es ist spät. ICh hoffe ich habe da jetzt nirgends ganz grundsätzlich falsch gedacht. --Fabiwanne (Diskussion) 03:20, 17. Jul. 2017 (CEST)

Verschlüsseln von Nachrichten

ME fehlt hier ein wichtiger Hinweis:

Zitat: Die Zahl $m$ muss dabei kleiner sein als der RSA-Modul $N$

Diese Bedingung reicht aber nicht aus: Vielfache von p und q lassen sich damit zwar verschlüsseln, aber nicht wieder entschlüsseln, weil dafür $(m,N)=1$ nicht erfüllt ist, und damit die Voraussetzung für die Anwendung des Verfahrens: $m^{\varphi (N)}\equiv 1{\bmod {N}}$ nicht gilt. Oder übersehe ich hier etwas?

Vorschläge zur Korrektur? --Wolfgang (Wolfk.wk) (Diskussion) 14:09, 23. Okt. 2017 (CEST)

Die angeblich notwendige Voraussetzung $m^{\varphi (N)}\equiv 1{\bmod {N}}$ ist zwar nicht erfüllt, aber das Entschlüsseln funktioniert trotzdem, denn: $m^{d\cdot e}\equiv m{\bmod {N}}$ auch für Vielfache von $p$ oder $q$.--Ann (Diskussion) 23:22, 1. Feb. 2021 (CET)

Berechnung des RSA-Moduls

Soll für die Berechnung von d wirklich $\varphi (N)$ genutzt werden? Warum wird für die Verschlüsselung/Entschlüsselung N verwendet, wenn e und d mit $\varphi (N)$ berechnet wurden? In dem Beispiel wurde e und d zu 143 berechnet, aber 120 für die Verschlüsselung berechnet? Wie soll das funktionieren, die beiden Zahlen haben doch keinen Zusammenhang außer dass sie Teilerfremd sind. --84.170.157.10 17:36, 15. Jan. 2019 (CET)

Ja. Denn das ist gerade der Knaller von RSA, dass nur die den Zusammenhang von $N$ und $\varphi (N)$ kennt, die auch $p$ und $q$ kennt. Solange sie nur $N$ und $e$ hat, bleibt ihr die Berechnung von $d$ verwehrt.

RSA mit chinesischem Restsatz

Es fehlt der explizite Hinweis, dass die komponentenweise Potenzierung nur in eine Richtung anwendbar ist, also beim Entschlüsseln. Wenn der öffentliche Schlüssel ebenfalls p und q enthielte, liesse sich der private Schlüssel aus N,p,q,e leicht ermitteln. --Action127 (Diskussion) 11:22, 4. Apr. 2021 (CEST)