Primzahlen: Libary gesucht



  • Das Problem mit vorberechneten Listen wäre, dass es bis 296 gut 1027 Primzahlen gibt. Mit "naiven" Primzahlgeneratoren kommt man in dieser Größenordnung auch nicht weit.

    Eine Möglichkeit wäre, einen zufällig gewählten Bereich auf wahrscheinliche Primzahlen durchzusieben (beispielsweise, indem man das Sieb des Erasthotenes mit einer Liste von vorberechneten Primzahlen < 65536 darauf anwendet) und die verbliebenen Kandidaten mit einem geeigneten Primzahltest (beispielsweise AKS) zu überprüfen.

    Da könnten allerdings viele Wege nach Rom führen. Ich würde mal im Mathematik-Forum nachfragen, ob sich jemand mit Zahlentheorie auskennt.



  • Nachtrag: Ich meine natürlich das Sieb des Eratosthenes.

    Ich geh das jetzt hundert mal in eine Textdatei tippen.



  • Hallo,

    seldon schrieb:

    Eine Möglichkeit wäre, einen zufällig gewählten Bereich auf wahrscheinliche Primzahlen durchzusieben (beispielsweise, indem man das Sieb des Erasthotenes mit einer Liste von vorberechneten Primzahlen < 65536 darauf anwendet)

    Das ist aber doof, weil meine Primzahl 96 Bit lang sein soll. So wird sie maximal 16 Bit lang. Vielleicht sollte ich die doch einfach ein paar Primzahlen hart einprogrammieren.
    [/quote]

    Vielen Dank
    lg, freakC++



  • Nein, ich meinte, einen Bereich irgendwo in der Nähe von 296 zu nehmen und den mit den ersten paar Primzahlen quasi teilweise zu sieben. Danach bleiben nicht nur Primzahlen übrig, aber die meisten Nicht-Primzahlen hast du damit schonmal aussortiert. Deshalb brauchst du danach auch noch den weiteren Test.

    Es geht dabei vor allem darum, das Vorhaben auf einen vertretbaren Rechenaufwand runterzudrücken.



  • freakC++ schrieb:

    Das ist aber doof, weil meine Primzahl 96 Bit lang sein soll. So wird sie maximal 16 Bit lang. Vielleicht sollte ich die doch einfach ein paar Primzahlen hart einprogrammieren.

    Vorallem dir ueberlegen ob du wirklich eine echte primzahl brauchst. idR reicht naemlich eine pseudo primzahl. Und die sind viel viel viel schneller zu finden als echte primzahlen.



  • Shade Of Mine schrieb:

    Vorallem dir ueberlegen ob du wirklich eine echte primzahl brauchst. idR reicht naemlich eine pseudo primzahl. Und die sind viel viel viel schneller zu finden als echte primzahlen.

    Das musst du mir erklären. Krypto mit Pseudoprimzahlen (egal in Bezug auf welchen Primzahltest) scheint mir keine gute Idee, und das dürfte die idR-Fälle größtenteils schon erschlagen.

    Allerdings mag es im konkreten Fall um etwas anderes gehen - 296 wäre für Krypto ziemlich mager.



  • Doch, ShadeOfMine hat da recht. PseudePrimzahlen sind hier häufig ausreichen.

    Ich habe übrigens eine Lösung gefunden. Ich soll einfach ein Kryptographieverfahren implementieren. Bevor ich mir jetzt den Kopf über diese nebensächliche Angelegenheit mache, habe ich mich entschieden, alles in Java zu schreiben, weil es standardgemäß eine Methode "probablePrime" gibt, die als Parameter die Bitzahl erwartet. Einfacher gehts nicht 😃

    Natürlich schäme ich mich für diesen Sprachenausrutscher, doch für diese Anforderung gehts einfach schneller. 🙂

    Vielen Dank
    LG, freakC++



  • seldon schrieb:

    Shade Of Mine schrieb:

    Vorallem dir ueberlegen ob du wirklich eine echte primzahl brauchst. idR reicht naemlich eine pseudo primzahl. Und die sind viel viel viel schneller zu finden als echte primzahlen.

    Das musst du mir erklären. Krypto mit Pseudoprimzahlen (egal in Bezug auf welchen Primzahltest) scheint mir keine gute Idee, und das dürfte die idR-Fälle größtenteils schon erschlagen.

    Man verwendet bei so grossen Zahlen idR nur Pseudo Primes, weils einfacher ist. Primzahlen mag man ja verwenden weil sie bestimmte Eigenschaften haben, nicht weil es Primzahlen sind.

    Und Pseudoprimes sind halt nah genug dran um gut genug zu sein.
    Siehe zB http://en.wikipedia.org/wiki/Pseudoprime

    Wenn man sich eine zahl frei aussuchen kann, kann man natuerlich einfach aus einer vordefinierten Liste eine Primzahl auswaehlen - aber oft ist es so, dass man nur einen ungefaehren Wertebereich hat und dort haette man gerne eine Primzahl. Eine echte primzahl zu finden, dauert aber. Dagegen sind pseudo primes sehr schnell zu finden. Man kann, je nach Eigenschaften die man haben will, den passenden Algo waehlen.
    Eine oft verwendete Pseudoprime Klasse ist zB Fermat: http://en.wikipedia.org/wiki/Fermat_pseudoprime

    Ein weiteres Keyword nach dem man hier googlen kann ist: probable prime.



  • Ja, gut, das ist mir alles soweit bekannt (wobei Fermat-Pseudoprimzahlen weniger eine Klasse von Pseudoprimzahlen als mehr eine Klasse von Pseudoprimzahlklassen sind; es stellt sich ja die Frage nach der Basis). Aber wenn du eine Pseudoprimzahl in RSA wirfst, fliegen die Annahmen, die der Algorithmus macht, trotzdem auseinander. Es ist ja auch so, dass ein "probable prime"-Algorithmus die meiste Zeit Primzahlen ausspuckt. Man verlässt sich dann halt auf das Glück, keine Pseudoprimzahl zu erwischen, aber das macht Pseudoprimzahlen nicht für Krypto geeignet.

    Die Idee mit der vordefinierten Liste scheint mir übrigens nicht schlüssig. Wie ich schon sagte, schon bei 296 reden wir von gut 1027 bzw. knapp 290 Primzahlen -- soviel Speicherplatz gibt es auf dem ganzen Planeten nicht. Und 296 sind für Krypto wirklich mager - bei handelsüblichen 2048-Bit-RSA ist man noch in ganz anderen Größenordnungen unterwegs.



  • Und dennoch nimmt man fuer RSA idR eine pseudo prime Zahl.



  • Man nimmt keine Pseudoprimzahlen her. Man rät (möglichst geschickt) ein paar Zahlen und lässt einen (Pseudo-)Primzahltest (etwa Miller-Rabin) darüber laufen. Dann hofft man inständig, dass - wenn der Test "ja" sagt, es sich auch um eine echte Primzahl handelt. Und nicht nur um eine Pseudoprimzahl (oder eigentlich sogar "wahrscheinliche Primzahl"). Glücklicherweise geht die Wahrscheinlichkeit, dass das so ist, sehr schnell (d.h. exponentiell schnell in der Anzahl der durchgeführten Testläufe) gegen 1 und alle sind froh.

    Wenn man für RSA keine echten Primzahlen verwendet geht von Anfang bis Ende so ziemlich alles schief, was bei RSA überhaupt schief gehen kann. Sämtliche Annahmen auf denen das Verfahren basiert sind dann ungültig. Schreibt ja auch seldon.



  • freakC++ schrieb:

    Ich habe übrigens eine Lösung gefunden. Ich soll einfach ein Kryptographieverfahren implementieren.

    Au weia! Sowas implementiert man nicht selbst! Wahrscheinlich hast du auch noch nichts von Seitenkanal-Attacken gehört. Vernünftige Bibliotheken schützen sich auch davor. Das hat schon alles so seinen Sinn, wenn man sagt "sowas implementiert man nicht selbst"; denn es ist sehr unwahrscheinlich, dass du so den Qualitätsstand erreichst, den andere Bibliotheken jetzt schon bieten.

    Shade Of Mine schrieb:

    Und dennoch nimmt man fuer RSA idR eine pseudo prime Zahl.

    Ich wüsste nicht, wie RSA mit Pseudoprimzahlen funktionieren sollte. Bei RSA brauchst du

    e * d = 1 mod phi(n)

    wobei phi(n) leicht berechenbar ist, falls die Primfaktoren von n bekannt sind. Ist n=p*q und sind p und q prim, gilt phi(n) = (p-1)(q-1). Wenn p und q nicht prim sind, dann gilt phi(n) != (p-1)(q-1). Man würde also in dem Fall, wo p und/oder q doch keine Primzahl ist, phi(n) falsch berechnen. Wenn man phi(n) aber falsch berechnet, berechnet man auch ein falsches d bei der Schlüsselerzeugung -- also ein private Key, der nicht zum public key passt. Dann kann man die Nachrichten nicht mehr entschlüsseln bzw keine gültigen Signaturen erzeugen. Oder übersehe ich da etwas? Erklär es mir...




Anmelden zum Antworten