StartseiteAstrodicticum Simplex

Verschlüsselungsverfahren und ihre Sicherheit

Von / 16. September 2014 / 37 Kommentare / Seite 3 von 3 / Auf einer Seite lesen
Mehr

Die Sicherheit von Feistelnetzwerken kann gut eingeschätzt werden. Es existiert offenbar sogar ein Beweis von Luby und Rackoff aus dem Jahre 1988, der zeigt, dass es möglich ist, nach bereits vier Runden eine perfekt sichere Verschlüsselung zu haben. Die praktischen Anforderungen sind dabei allerdings so hoch, dass sie in der Realität nicht erfüllbar sind. Zudem ist die Sicherheit des Algorithmus von der Breite der Blöcke abhängig; je sicherer der Algorithmus sein soll, umso breiter müssen die Blöcke sein.

Vermutlich ist der momentan wichtigste Algorithmus für Verschlüsselung – AES[20] (oder auch Rijndael) – gerade aus diesem Grund kein Feistelnetzwerk. Bisher hat sich der Gewinner der AES-Wettbewerbs gegen alle Arten von Angriffen als ziemlich robust erwiesen. Auch die Gerüchte aus dem Herbst 2013, dass die NSA starke Verschlüsselung brechen kann, haben wohl nichts mit AES oder anderen starken Kryptoalgorithmen zu tun sondern eher mit der Zertifikats-Infrastruktur oder der Implementierung von kommerziellen Umsetzungen von AES. Es gibt jedoch die Kritik, dass der Sicherheitspuffer zu klein gewählt ist für ein Verfahren, welches die nächsten Jahrzehnte halten muss. Zudem ist AES eine der wenigen Chiffren (vielleicht sogar die einzige?), die durch geschlossene algebraische Formulierungen darstellbar ist[21]. Damit ist der Angriff auf den Algorithmus auf einmal von einer Seite der Mathematik möglich, die bisher wenig mit Kryptographie zu tun hat.

Ähnlich wie die Wiederverwendung von One-Time-Pads gibt es bei den Block-Chiffren Anwendungsfehler, die die Sicherheit unabhängig vom Algorithmus schmälern. Ein Block-Chiffre erlaubt es normalerweise nur Nachrichten zu verschlüsseln, die höchstens einen Block lang sind. Es gibt unterschiedliche Ideen („Betriebsarten“), wie man längere Nachrichten chiffriert. Alleine vom NIST, dem amerikanischen National Institute of Standards and Technology, werden ein Dutzend akzeptierte Betriebsarten beschrieben[21]. Sie reichen vom einfachen ECB („Ich verschlüssele jeden Block unabhängig voneinander“) bis hin zu Arten, die Sicherheit und Integrität ermöglichen, wie dem CCM („Ich verwende für jeden Block einen neuen Schlüssel und bilde zusätzlich eine kryptographisch sichere Prüfsumme mit Hilfe des Chiffres“). Die Frage nach der besten Betriebsart ist davon abhängig, wie genau die Anforderungen aussehen und kann nicht pauschal beantwortet werden.

Verschlüsselungsverfahren sind und bleiben ein spannendes Thema, bei dem der Forschungsbedarf hoch ist. Es gibt viele offene Fragen und durch die Tatsache, dass heute die kryptographische Sicherheit auf Vermutungen beruht, rückt die Kryptographie deutlich in die Nähe der Naturwissenschaften. Zudem wird das Spektrum der mathematischen Werkzeuge erweitert und lässt auf neue Analysemethoden und Ideen für Chiffren hoffen. Dagegen hält die Umsetzung und Benutzung der Algorithmen viele Tücken bereit und die jüngsten Skandale um Sicherheitslücken in populärer Software („goto fail“[23] und „heartbleed”[24]) zeigen, dass sogar Open-Source-Software nicht sicher vor Programmierfehlern oder Hintertüren ist. Wir können gespannt sein, wohin uns die Zukunft bringt.

Links:

[1] https://de.wikipedia.org/wiki/Cäsar-Chiffre
[2] https://www.gnupg.org/index.de.html
[3] https://tools.ietf.org/html/rfc5751
[4] https://www.kes.info/archiv/online/01-01-60-SMIMEvsOpenPGP.htm
[5] https://de.wikipedia.org/wiki/P-NP-Problem
[6] https://de.wikipedia.org/wiki/Rucksackproblem
[7] https://de.wikipedia.org/wiki/Primfaktorzerlegung
[8] https://cacr.uwaterloo.ca/hac/about/chap8.pdf (S. 300ff)
[9] https://de.wikipedia.org/wiki/RSA-Kryptosystem
[10] https://de.wikipedia.org/wiki/Elgamal-Verschlüsselungsverfahren
[11] https://de.wikipedia.org/wiki/Elliptic_Curve_Cryptography
[12] https://de.wikipedia.org/wiki/RC4
[13] https://twitter.com/ioerror/status/398059565947699200
[14] https://www.ecrypt.eu.org/stream/
[15] https://de.wikipedia.org/wiki/Twofish
[16] https://www.am.hs-mannheim.de/KryptoLern/feistel.php
[17] https://www.csshl.net/sites/default/files/downloadable/crypto/TEA_Cryptanalysis_-_VRAndem.pdf
[18] https://page.math.tu-berlin.de/~kant/teaching/hess/krypto-ws2006/des.htm
[19] https://crypto.junod.info/sac01.pdf
[20] https://de.wikipedia.org/wiki/Advanced_Encryption_Standard
[21] https://www.dpunkt.de/leseproben/3112/Kapitel%208.pdf (S. 136)
[22] https://csrc.nist.gov/groups/ST/toolkit/BCM/index.html
[23] https://gotofail.com
[24] https://heartbleed.com

1 / 2 / 3
Stichworte: , ,
Mehr

Kommentare (37)

  1. #1 Thomas
    16. September 2014

    Topp! Ich komme aus der Branche und muss sagen, dass du ein Talent hast Inhalte anschaulich zu erklären. Aber auch hier gilt: ein Bild zur Auflockerung zwischendrin wäre schön gewesen.

  2. #2 Alderamin
    16. September 2014

    @Dominic

    Schöner Artikel, allerdings etwas schwere Kost für Nicht-Informatiker (kennt jeder die Komplexitätsklassen P und NP? P ist mit polynomialem Aufwand (quadratisch, kubisch etc., z.B. Sortieren einer Menge von Zahlen) zu lösen, NP höchstwahrscheinlich nicht (exponentieller Aufwand oder noch höher). Ob ein Problem in die Klasse NP fällt, wird dadurch bewiesen, dass man das betreffende Problem auf ein anderes zurückführt, das als Element von NP bereits bekannt ist, wie z.B auf das genannte Rucksackproblem, also das optimale Füllen eines imaginären Rucksacks mit einer Menge von Objekten verschiedener Größe (z.B. Summe einer Teilmenge gegebener verschieden großer Zahlen unterhalb einer gegebenen Schranke), oder die Ermittlung des kürzesten Weges durch einen Graphen, das Traveling-Salesman-Problem).

    Vielleicht hätte man noch erwähnen sollen, dass bei den asymmetrischen Verfahren Primzahlen eine Rolle spielen: verschlüsselt wird mit dem Produkt zweier großer Primzahlen; dieses Produkt ist nur mit sehr großem Aufwand in seine Primfaktoren zerlegbar (jedenfalls NP; im wesentlichen muss man alle möglichen Prim-Divisoren durchprobieren, das kann ein Weilchen dauern), dies macht den Schlüssel sicher; entschlüsselt wird mit einem der Primfaktoren, die nur der Schlüsselinhaber kennt (wenn man sich zwei große Primzahlen generiert, hat man natürlich ganz leicht das Produkt aus zweien dieser Zahlen berechnet und somit den öffentlichen Schlüssel generiert).

  3. #3 Crazee
    16. September 2014

    Wirklich schön geschrieben. Ich wünsche mir jetzt einen zweiten Teil, der mir sagt, was vermutlich der praktikabelste/sicherste/mögliche Weg ist, mit dem ich in den nächsten 2 Jahren meine Mail verschlüsseln sollte.

  4. #4 Florian Freistetter
    16. September 2014

    Ein sehr interessantes Thema, aber für Laien vielleicht stellenweise ein wenig zu kompliziert… Die vielen Abkürzungen dürften nicht allen bekannt sein und Sätze wie “Ein echt zufälliger Strom von Einsen und Nullen wird mit der Binärdarstellung der Nachricht via XOR verknüpft (1 XOR 0=0 XOR 1=1, sonst 0). “ sind schon ein wenig heftig, wenn man unvorbereitet auf sie trifft.. 😉

    Konkrete Beispiele wären vielleicht hilfreich gewesen bzw. ein bisschen mehr Hintergrund zu den vielen verschiedenen Verfahren – oder die Konzentration auf ein einziges der Verfahren.

  5. #5 Andreas P
    16. September 2014

    In der Tat sehr schön geschrieben .. komme allerdings auch aus der Branche, weiss daher mit XORs was anzufangen 😉

  6. #6 Herbert
    16. September 2014

    Was ist eine “Zombiekalypse”?

  7. #7 Florian Freistetter
    16. September 2014

    @Herbert: “Was ist eine “Zombiekalypse”?”

    Wahrscheinlich weiß die NSA schon wieder mehr als wir…

  8. #8 Crazee
    16. September 2014

    @Herbert: Kofferwort aus Zombie und Apokalypse -> Der Tag an dem die Zombies die Weltherrschaft an sich reißen wollen. Hier: Wenn nur noch ein paar Leute eine Pandemie überlebt haben und die Infrastruktur langsam den Geist aufgibt.

  9. #9 volki
    16. September 2014

    @Alderamin

    dieses Produkt ist nur mit sehr großem Aufwand in seine Primfaktoren zerlegbar (jedenfalls NP; im wesentlichen muss man alle möglichen Prim-Divisoren durchprobieren, das kann ein Weilchen dauern)

    Da gibt es weit effizientere Methoden (quadratisches Sieb, Zahlkörpersieb, Elliptische Kurven Faktorisierung)

    Ob ein Problem in die Klasse NP fällt, wird dadurch bewiesen, dass man das betreffende Problem auf ein anderes zurückführt, das als Element von NP bereits bekannt ist

    Nein. Du meinst hier die Klasse NP-schwer bzw. NP-vollständig

    Ein Problem liegt in NP, wenn man eine Lösung des
    Problems schnell (in polynomieller Zeit) verifizieren kann. Z.B. Faktorisieren von Zahlen. Gibt mir jemand zwei Primzahlen p und q und behauptet N=pq kann ich das sofort nach prüfen. Wenn aber N groß ist (200 Dezimalstellen) dann ist es meistens praktisch unmöglich p und q zu bestimmen.

  10. #10 dude
    16. September 2014

    Vielen dank für diesen lesenswerten Artikel. War für mich als Laie zwar grenzwertig aber dennoch informativ auch wenn er mir einiges abverlangt hat.

    Was ist denn der Unterschied zwischen Zufallszahl & Pseudozufallszahl?

  11. #11 volki
    16. September 2014

    @dude:

    Was ist denn der Unterschied zwischen Zufallszahl & Pseudozufallszahl?

    Eine zufällige Zahl (sagen wir 0 oder 1) erzeugst du durch “echten” Zufall, indem du z.B. eine Münze wirfst (Kopf=0 und Zahl=1).

    Eine Pseudozufallszahlgenerator ist ein deterministischer Algorithmus, der eine Folge von 0en und 1en ausgibt, die zufällig aussieht, es aber nicht ist.

    Ein Pseudozufallszahlengenerator ist um so besser, um so schlechter man voraussagen kann welche Zahl – 0 oder 1- als nächstes kommt, wenn man den Algorithmus, der dahinter steckt nicht kennt. Kann zum Beispiel bei One-Time-Pads ein Angreifer berechnen, welche Zahl als nächstes kommt, ist der One-Time-Pad ziemlich nutzlos. Man geht natürlich davon aus, dass der Angreifer den Algorithmus der die Pseudozufallszahl erzeugt nicht kennt.

  12. #12 Alderamin
    16. September 2014

    @Volki

    Sorry, ist schon fast 30 Jahre her, die Feinheiten sind mir da etwas untergegangen (ja, unverzeihlich für einen Informatiker). 😳

    Also,

    – Die Klasse P beschreibt Probleme, die in polynomieller Zeit berechnet werden können (ein Polynom über der Problemgröße, z.B. O(n²) für einige einfache Sortieralgorithmen, die n Zahlen sortieren, indem sie immer wieder die ganze Liste durchsuchen, um den Platz für den nächsten Eintrag zu finden, oder O(n log n) für etwas geschickte Verfahren, die z.B. einen Suchbaum aufbauen).

    – Die Klasse NP beschreibt Probleme, die in polynomieller Zeit verifiziert werden können, egal wie groß der Aufwand zu ihrer Berechnung ist.

    – Die Klasse NP-schwer beschreibt Probleme, die eine hypothetische nichtdeterministische Maschine (die stets richtig rät, also etwa den richtigen Primfaktor) in polynomieller Zeit lösen könnte.

    – Die Klasse NP-vollständig beschreibt Probleme, die sowohl NP-schwer sind als auch in NP liegen, also von einer nichtdeterministischen Maschine in polynomieller Zeit berechnet und von einer deterministischen in polynomieller Zeit überprüft werden könnten.

    – P ist Teilmenge von NP und könnte sogar = NP sein, aber letzteres ist unbewiesen (und nicht wirklich wahrscheinlich).

    Ich hoffe, so war’s richtig.

  13. #13 Uli
    16. September 2014

    Das aktuelle Hauptproblem der Kryptografie ist, daß NSA und Konsorten die Standardisierungsgremien unterwandert haben.
    So waren sie in der Lage, Algorithmen und Parameter zu Standards zu erheben, die sie selber schon kancken konnten.

    Außerdem muss man eigentlich nach den Snowden-Enthüllungen davon ausgehen, daß sämtliche interessante Hardware, Software und Netzinfrastruktur durch die Geheimdienste komprommitiert sind.

    Der beste Verschlüsselungsalgorithmus hilft nichts, wenn das Betriebssystem jeden Tastendruck an die NSA schickt…

  14. #14 volki
    16. September 2014

    @Alderamin:

    Sieht gut aus!

    Zum Faktorisierungsproblem könnte man noch anmerken, dass es zwar in NP liegt aber sehr wahrscheinlich weder in P noch in NP-vollständig liegt.

    Stark vereinfacht gesagt: Sehr wahrscheinlich (wird vermutet ist aber noch nicht bewiesen) ist Primfaktorzerlegung leichter als das Rucksackproblem, aber schwerer als z.B. sortieren.

    Was aber für den Laien erstaunlich klingen mag ist, dass es polynomielle Algorithmen gibt um testen, ob eine Zahl eine Primzahl ist.

  15. #15 Alderamin
    16. September 2014

    @volki

    Was aber für den Laien erstaunlich klingen mag ist, dass es polynomielle Algorithmen gibt um testen, ob eine Zahl eine Primzahl ist.

    Ich hab’ mal ein Semester Numerik gehört, von daher kann ich mich noch an das Wort “Miller-Rabin-Test” erinnern (ohne das Verfahren noch zu kennen), und siehe da, der Aufwand ist O((log n)^4). Nein, hätte ich ohne Nachschlagen nicht gewusst.

  16. #16 volki
    16. September 2014

    @Alderamin: Da hast du aber nicht genau gelesen:

    Wenn angenommen wird, dass die Riemannsche Vermutung wahr ist […] ie Laufzeit dieses Algorithmus ist O((log n)^4).

    Der einzige polynomielle Algorithmus, den man kennt (bewiesen), ist der AKS-Test bzw. seine Verfeinerungen von Lenstra und Pomerance.

    Natürlich ist der Miller-Rabin-Test und ähnliche Tests für die Praxis viel relevanter.

  17. #17 DerMannMitHut
    16. September 2014

    @Florian: Ja, manchmal ist es ein wenig schwierig zu lesen, das gebe ich zu. 😉

    @Herbert: Zombikalypse=Zombie-Apokalypse … hier eine etwas flapsige Bezeichnung für eine Katastrophe, bei der viel Weltwissen leicht verloren gehen kann.

    @dude: was volki sagt. Pseudozufallszahlen sind solche, die aus einem möglichst guten Algorithmus stammen.

    @uli: Das mit der Standardisierung ist in meinen Augen nur teilweise ein Problem, da du nicht auf standardisierte Algorithmen angewiesen bist. Relevanter ist da das Problem, dass die NSA den Postweg für Hardware kontrolliert, vgl. den Vortrag von Appelbaum vom 30C3.

  18. #18 Dampier
    17. September 2014

    Puh. An dem Thema habe ich mich schon mehrfach versucht, aber ich finde es schwer zu verstehen. Diese Artikel erklärt das schon recht gut, wobei mir nicht alle verwendeten Begriffe geläufig sind (XOR etc.)

    Das Cryptonomicon von Neil Stephenson hat mir die Materie am besten nahegebracht (Ein Roman, kein Sachbuch). Das kann ich allen interessierten wärmstens empfehlen.

    Auch Klausis Krypto-Kolumne hier auf Scienceblogs ist lesenswert (wobei es da mehr um historische Verschlüsselungsverfahren geht als um Computer).

    Alles in Allem ein guter Artikel. Ich glaub, es ist fast unmöglich, das in der gebotenen Kürze für doofe wie mich zu erklären 😉

    Gruß
    Dampier

  19. #19 Florian Freistetter
    17. September 2014

    @Dampier: Das beste und verständlichste Buch zur Kryptografie ist Codes: Die Kunst der Verschlüsselung. Geschichte – Geheimnisse – Tricks von Simon Singh. Das ist echt super! (Und nebenan gibts bei SB sogar ein Kryptografie-Blog: https://scienceblogs.de/klausis-krypto-kolumne/

  20. #20 Dampier
    17. September 2014

    @Florian, danke für den Tipp! Singhs Fermats letzter Satz hat mir schon sehr gut gefallen. Wie er die ganze Geschichte ohne eine einzige Formel erzählt, ist schon meisterhaft.

    Klausi lese ich auch gern (hatte ihn oben auch empfohlen).

    grz
    Dampier

  21. #21 Stefan Wagner
    https://demystifikation.wordpress.com/2014/09/16/schariapolizei/
    23. September 2014

    Ein Pseudozufallszahlengenerator ist um so besser, um so schlechter man voraussagen kann welche Zahl – 0 oder 1- als nächstes kommt, wenn man den Algorithmus, der dahinter steckt nicht kennt.

    Ich bin nicht aus der Sicherheitsbranche, aber lege hier meine Stirn in Falten.

    Ich hätte behauptet, dass bei einem guten Pseudozufallszahlengenerator der Algorithmus bekannt sein darf, um ihn einzuschätzen vielleicht sogar bekannt sein muss, dass aber der aktuelle Zustand in dem er sich befindet, bzw. die Initialisierung unbekannt ist, und dann soll es einem Beobachter unmöglich oder schwer möglich sein das nächste Ergebnis sicher vorherzusagen.

    Für Laien vielleicht verständlich ausgedrückt: Ein Zufallsgenerator, der Würfelwürfe simuliert, also Zahlen von 1-6 muss im Mittel jede Zahl in 1/6tel der Fälle produzieren, aber natürlich nicht einfach 1,2,3,4,5,6 als Reihe wieder und wieder. Auch 1,3,6,5,2,4 und das wieder und wieder würde man vor Ende der zweiten Wiederholung erraten – die erste Reihe allerdings bereits nach der Hälfte der Reihe.

    Im wahren Leben kommen natürlich auch zwei Einsen hintereinander vor, und gar 3 oder 4 Sechsen (immer nur bei den anderen). Auch diese Ausreißer muss der Zufallszahlengenerator im erwartbaren Ausmaß liefern.

    Allerdings – hier begebe ich mich aber auf dünnes Eis – wiederholt sich jeder Pseudozufallszahlengenerator irgendwann. Wenn die Serie, nach der er sich wiederholt, aber lange genug ist, ist die Schwäche gering. So habe ich es bislang verstanden.

    Echte Zufallszahlengeneratoren arbeiten mit zufälligen Störeinflüssen, etwa mit radioaktivem Zerfall, der statistisch beschreibbar ist (Halbwertszeit) aber wann genau ein Teilchen sich spaltet ist nicht vorhersehbar. Es gibt aber auch eine Maschine im Internet, da werden wirklich Würfel per Förderband einen Turm hochgeschleppt, purzeln dann eine bucklige Rampe herab, landen unten in einem Körbchen vor einem Fenster, wo ein Bild von ihnen geschossen wird, also von 4 oder 5 Würfeln nebeneinander (5, 3, 3, 5, 1) und dieses per Mustererkennung analysiert, und ca. ein solches Quintupel pro Sekunde wird so erzeugt. Ob es die Daten auch wirklich an einen seriösen Nutzer liefert weiß ich nicht, die Übertragung wäre natürlich angreifbar und man könnte Videos statt Livebilder einspielen, um Kontrolleure auszutricksen, aber man könnte sich so ein Gerät ja neben die Maschine stellen, die den Zufall als Input braucht.

    Radio- und Audiosignale, Maus- und Tastaturbewegungen wurden schon als Hilfsmittel zum Verrauschen diskutiert und werden bei Linux auch (zum Teil?) benutzt, aber sind auch angreifbar/erratbar.

    Noch ein Wort zu großen Primzahlen: Für den Hausgebrauch ist 2011 eine hübsch große Primzahl. Das war aber sicher nicht gemeint. Nur – wie groß ist eine große Primzahl, wie sie bei PGP eingesetzt wird? 100 Stellen? 1000 Stellen?

  22. #22 PDP10
    24. September 2014

    @Stefan Wagner:

    “Nur – wie groß ist eine große Primzahl, wie sie bei PGP eingesetzt wird? 100 Stellen? 1000 Stellen?”

    In der Regel ein paar Hundert Stellen. Nach der Empfehlung des BSI mindestens 2048 Bit.

    Hier ist das am Beispiel des weit verbreiteten RSA Verschlüsselungssystems genauer beschrieben:

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

  23. #23 Hans
    24. September 2014

    Hängt die derzeit sichere Schlüssellänge nicht auch noch vom verwendeten Verfahren ab? – Ich meine, ich hab da mal was gelesen, dass die 2048 Bit langen Schlüssel zwar bei RSA nötig sind, dass man aber bei Verfahren, die auf elliptischen Kurven beruhen, mit wesentlich kürzeren Schlüsseln auskommt, ohne die Sicherheit zu gefährden.
    —
    Nebenbei: Ich hab mich gerade gefragt, wieviele Dezimalstellen eine 2048 Bit lange Zahl hat? – Dazu fiel mir dann was mit ‘nem Zweierlogarithmus ein, also mal kurz nachgerechnet: \frac{\ln 2048}{ln 2}. Da da kommt 11 raus, also 11 Dezimalstellen für eine 2048 bit lange Zahl?! – Das erscheint mir gerade vieeel zu kurz. Bliebe die Frage, wie man das genau ausrechnet, bzw. wo mein Fehler steckt?

  24. #24 volki
    24. September 2014

    @Hans

    Es sind 2048 \cdot \frac{\ln 2}{ln 10} \sim 617 Dezimalstellen. Man bekommt das heraus, wenn man folgende Gleichung löst:

    2^{2048}=10^x

    logarithmieren ergibt

    2048 \cdot \ln 2 = x \cdot \ln (10)

    und dann bekommt man für x die Anzahl der Dezimalstellen.

  25. #25 volki
    24. September 2014

    @Stefan Wagner:

    Ich hätte behauptet, dass bei einem guten Pseudozufallszahlengenerator der Algorithmus bekannt sein darf, um ihn einzuschätzen vielleicht sogar bekannt sein muss, dass aber der aktuelle Zustand in dem er sich befindet, bzw. die Initialisierung unbekannt ist, und dann soll es einem Beobachter unmöglich oder schwer möglich sein das nächste Ergebnis sicher vorherzusagen.

    Vollkommen richtig. Danke für die Ergänzung zu meiner Beschreibung.

    wiederholt sich jeder Pseudozufallszahlengenerator irgendwann.

    Bin da leider auch kein Experte, aber so weit ich es verstehe, ja. Aber ein guter Pseuduzufallsgenerator hat eine sehr große Periode, sodass dies paraktisch nicht relevant wird.

    Es gibt aber auch eine Maschine im Internet, da werden wirklich Würfel per Förderband einen Turm hochgeschleppt, […]

    Wirklich? Das kenne ich gar nicht. Kannst du bitte eine Quelle/Link nennen?

    Nur – wie groß ist eine große Primzahl, wie sie bei PGP eingesetzt wird? 100 Stellen? 1000 Stellen?

    Zu PGP beruht auf SHA (bzw. den neueren Varianten) und man braucht dafür keine Primzahlen.

    Wenn du RSA meinst, dann sind 100 Stellen definitiv zu wenig. Aber 1000 Stellen reichen – derzeit. Sieht man sich die RSA Factoring Challenge an bekommt man glaube ich einen ganz guten Eindruck, was derzeit machbar ist und was nicht.

  26. #26 Bullet
    24. September 2014

    @Hans, Volki:
    nich so kompliziert rechnen. 2^10 ≈ 10³.
    2^2048 sind etwa 205 mal 2^10 (genauer: (2^10)^205 🙂 ),
    also auch
    205 mal 10³ (genauer: (10³) ^205)
    Rechenregel:
    (a^b)^c = A ^ b*c
    In unserem Fall: 3*205 = 615,
    daher
    10^615 oder auch 616 Stellen. Ich glaube, die eine Zehnerstelle Unterschied zur exakten Berechnung ist bei derartigen Zahlen echt wurscht. Aber dafür braucht man auch keinen Rechner. Ich kenne jedenfalls niemanden, der beim log-, lg- oder ln-schrubben irjendwat mitm Kopp macht.
    (So zum Vergleich übrigens: ein Würfel mit einer Kantenlänge von 70 Mrd. Lichtjahren enthält nicht einmal 10^100 Kubikmikrometer-Würfelchen. Exponenten sind bitches.)

  27. #27 volki
    24. September 2014

    @Bullett:

    Rechne ich meistens für mich genau so, wenn kein Taschenrechner in der Nähe ist. Nur beim Kommentare schreiben sitze ich vor einem etwas größerem Taschenrechner und bin dann doch faul ;-).

  28. #28 StefanL
    24. September 2014

    Nicht doch @Bullet

    nich so kompliziert… niemanden, der beim log-, lg- oder ln-schrubben irjendwat mitm Kopp macht.

    2^3=8 ~ 10 also 3te-Wurzel 10 etwa 2 (+ ε ) also log(2)~0,3 (< 1/3)
    und so ( mit \frac{\ln{a}}{\ln{b}}=\log_b{a} 🙂 )
    ist 2^2048 ~ [ 0,3*2048 ] = 614 .
    ( Und ganz frech die 2 (= 10-8) hinzuaddiert = 616 😉 )

  29. #29 StefanL
    24. September 2014

    soll natürlich nicht 2^2048~ 614 heißen sondern Dezimalstellen(2^2048) …..

  30. #30 Bullet
    24. September 2014

    komisch, wie sich die Ergebnisse gleichen … *giggl*

  31. #31 DerMannMitHut
    24. September 2014

    @Stefan Wagner/volki: Ja, Pseudozufallszahlengeneratoren müssen sich zwangsläufig wiederholen, da der Speicher in einem Computer endlich ist und somit nur endlich viele Zustände abgebildet werden können. Damit muss irgendwann der Punkt kommen, dass ein Zustand dann wiederholt wird.

    Für die kryptographische Sicherheit will man haben:

    a) Eine große Periode, damit man viele Zufallszahlen raus bekommt. Denn sobald sich die Zahlen wiederholen, ist die One-Time-Pad-Sicherheit futsch.

    b) Eine Folge, die von echtem Zufall nicht unterscheidbar ist. Dummerweise kann man nicht sagen: „Genau so sieht eine zufällige Folge aus!“, denn dann wäre sie ja nicht mehr zufällig. Man kann nur Tests machen, die versuchen, bestimmte Fehler zu finden (z.B. Häufigkeiten von Teilfolgen auswerten, Längen von aufsteigenden Zahlenfolgen zählen und mit der erwarteten Längen vergleichen usw.) Wenn ein Generator alle Tests besteht, heißt das aber nicht, dass nicht morgen ein neuer Test entwickelt wird, der den Generator auffliegen lässt.

    c) Der Anfangszustand des Generators darf sich nicht aus der Folge ableiten lassen. Denn wenn das geht, dann könnte ein Angreifer relativ leicht die Folge reproduzieren.

  32. #32 Alderamin
    24. September 2014

    @DerMannMitHut

    Dazu fällt mir der Super Random Generator aus dem Buch von Donald E. Knuth (The Art of Programming – Vol. 2: Seminumerical Algorithms) ein. Da hatte jemand versucht, einen fantastisch guten Zufallsgenerator zu bauen, indem er mehrere Verfahren programmierte und dann unter anderem zufällig eines davon auswählen ließ. Aber lest selbst (ab dem Absatz vor Algorithm K)…

    Das hab’ ich mir damals eingehämmert und ich werde niemals versuchen, selbst einen Zufallsgenerator zu bauen, sondern stets auf einen Generator zurückgreifen, wie er dann in der Folge bei Knuth oder in anderen Fachquellen beschrieben ist.

    Die Zufallszahlen, die von Standardgeneratoren in C oder anderen Sprachen per Standard-rnd-Befehl geliefert werden, sind übrigens meistens nicht besonders gut. Da lohnt sich ein wenig Recherche.

  33. #33 rolak
    25. September 2014

    Standardgeneratoren .. nicht besonders gut

    Eindeutig…

  34. #34 DerMannMitHut
    25. September 2014

    @Alderamin: Jo. Selber ausdenken ist kritisch. Selbst Leute, die sich damit auskennen sollten, rennen da manchmal in Fallen, vgl. das klassische Beispiel von IBMs Algorithmus RANDU.

    Es gibt eine ganze Menge guter Pseudozufallszahlengeneratoren. Man kann z.B. jede gute Block-Chiffre verwenden: Denke dir einfach einen Block aus und verschlüssele diesen. Das Ergebnis sind dann einerseits Zufallszahlen, andererseits kannst du die wieder mit demselben Schlüssel chiffrieren und so die nächsten Zahlen generieren, usw.

    Das Ganze wird als Betriebsart OFB (Output Feedback Mode) bezeichnet. Auch die Betriebsart CTR (Counter Mode) ergibt gute Zufallszahlen – wenn die verwendete Ciffre gut ist.

  35. #35 Hans
    28. September 2014

    @volki, #24
    Auch wenn ‘s schon etwas spät ist…

    @Hans

    Es sind 2048 \cdot \frac{\ln 2}{ln 10} \sim 617 Dezimalstellen. Man bekommt das heraus, wenn man folgende Gleichung löst:

    2^{2048}=10^x

    Ah, danke! – Das hatte ich glatt vergessen.
    ——————

    @Bullet, #26

    2^2048 sind etwa 205 mal 2^10 (genauer: (2^10)^205 🙂 ),

    Äh… und wie kommst Du auf die 205?

  36. #36 PDP10
    28. September 2014

    @Hans:

    “Äh… und wie kommst Du auf die 205?”

    Berichtige den Tippfehler und es wird klarer:

    2^2048 ungefähr = 2^(10 * 205) = 2^10 * 2^205.

  37. #37 Hans
    28. September 2014

    Stunden später…
    @Bullet, #26 ; PDP10, #36:
    Was daran jetzt genau einfacher sein soll ist mir trotz nachrechnen zwar immer noch nicht klar, aber vielleicht fällt der Groschen ja noch…