BigNum

BigNumber oder Super Long Integer ist ein Rechner der über Ganzzahl Arithmetik sehr große Integer-Zahlen exakt berechnen kann (Auch Multiple- oder Arbitrary-Precision Arithmetic genant). Dies funktioniert so das die Zahlen aufgeteilt und in ein Array gespeichert werden um sie so in Long stücke schrittweise zu berechnen.
Eine Erweiterung für BigFloat also für Super Long Float Fliespunkt-Zahlen wäre auch möglich.

Die komplett in Visual-Basic geschriebenen Routinen sind um einiges langsamer als entsprechende die komplett in Assembler geschrieben wurden. Aber es lassen sich in vertretbarer Zeit immerhin noch Primzahlen in der Größe von 1024 Bit suchen.

Über [Resultate Speicher] können alle Ergebnisse in der Datei BinNum.txt gesammelt werden.

Das Programm ist Freeware und liegt im Download.

Um den Test zu beschleunigen werden zuerst Divisions-Test mit kleinen Primzahlen, der Fermat-Test und dann erst der RabinMiller-Test durchgeführt.

Der RabinMiller-Test ist der gleiche Algorithmus der auch für RSA und in PGP verwendet wird. Er kann aber eine Zahl nicht 100% sicher auf Primzahl testen sondern nur mit einer bestimmten Wahrscheinlichkeit, deshalb können nur sogenannte probabilistische Primzahlen gefunden werden. In der Praxis werden solche Zahlen getestet ob sie in allen Fällen korrekte Resultate liefern. Die Wahrscheinlichkeit das es sich nach dem RabinMiller-Test nicht um eine Primzahl handelt ist aber sehr klein. Dieser Algorithmus benutzt Zufallszahlen, und bei jedem Durchlauf reduziert sich die Wahrscheinlichkeit das es sich nicht um eine Primzahl handelt um die Hälfte. Es werden 50 Tests durchgeführt daraus ergibt sich 1:8.881E-16 = (1/2)^50, aber eben nicht 0.

Auch RSA ist kein 100% sicher Primzahltest da der Algorithmus auch zum Tiel mit Carmichael-Zahlen oder Pseudo-Primzahlen funktioniert die den Fermat-Test bestehen. Die beiden Basiszahlen P und Q müssen also nicht ausschließlich Primzahlen sein damit RSA funktioniert. Und die Sicherheit von RSA wird schwach wenn es sich bei P und Q nicht um echte Primzahlen handelt.

Der recht neue AKS-Primzahltest kann eine Zahl 100% auf Primzahl testen und schafft das in Polynomialzeit. Das Verfahren ist aber immer noch viel langsamer als der RabinMiller-Test und wird in BigNum noch nicht unterstützt.

Für die beiden speziellen Primzahlen Fermat-Zahlen und Mersenne-Zahlen gibt es spezielle Algorithmen, für Fermat-Zahlen den Pepin-Test (noch nicht enthalten) und für Mersenne-Primzahl den LucasLehmer-Test. Beide liefern ein 100% sicheres Ergebnis. Auf der suche nach der größten bekannten Primzahl werden weltweit Mersenne-Primzahlen gesucht.

Per Definition ist 1 keine Primzahl, der Grund für diese Definition hat hauptsächlich mathematische Gründe. Dennoch ist 1 unteilbar und wird deshalb in BigNum als Primzahl (oder eben unteilbare Zahl) ausgegeben.

Kryptografie oder Kryptologie sind Verfahren Daten durch Verschlüsselung zu schützen.
Die wichtigsten Verfahren der lassen sich in zwei Kategorien aufteilen, die sogenannten Symmetrischen Verschlüsselungsalgorithmen und die Asymmetrischer Verschlüsselungsalgorithmen. Der wesentliche Unterschied liegt darin, das symmetrische Verfahren das gleiche Paßwort zum Verschlüsseln und zum Entschlüssen verwendet werden muß, bei asymmetrischen Verfahren hingegen muß für das Verschlüsseln ein anderer Schlüssel verwendet werden als für das Entschlüsseln. Wobei man dabei dem Schlüssel zum Verschlüsseln nicht ansehen kann, welchen Schlüssel man zum Entschlüsseln braucht.
In der Praxis bedeutet daß das man Daten in der privaten Umgebung mit symmetrischen Verfahren geschützt werden. Bei der Kommunikation aber hat man das Problem, das dieses symmetrische Paßwort verabredet sein müßte, also beide Kommunikationparnter das Paßwort kennen müssen. Besonders dann wenn sich die Kommunikationspartner nicht kennen ist es fast unmöglich ein Paßwort auf einem sicheren Kanal zu verabreden, denn sogut wie jeder Kommunikationskanal ist nicht sicher, bis auf die Quantenkryptografie, diese ist aber noch keine heute übliche Technologie. Asymmetrische Verfahren ermöglichen es die Schlüssel zu spalten und dabei einen öffentlich und einen geheim zu halten, so ist es möglich das zwei Kommunikationspartner sich privat Nachrichten senden können ohne über ein sicheren Kanal ein Paßwort zu verabreden
Asymmetrischer Verschlüsselungsalgorithmen sind meistens sehr langsam und deshalb ungeeignet um große Datenmengen zu bearbeiten. Deshalb wird asymmetrisch nur ein Paßwort das meistens aus Zufallsdaten besteht verschlüsselt, und die Daten selbst mit Symmetrischer Verschlüsselungsalgorithmen verschlüsselt. Beide Verfahren müssen also sicher sein da eine Schwäche in nur einem der beiden Verfahren den Schutz schwächt. Dieses nennt man deshalb Hybride Verschlüsselung.

RSA wie DH (so wie alle Informations-Tauch Verfahren ohne sichere Leitung) sind schwach gegen ein "Man in der Mitte Angriff", der die Kommunikation zu sich umleitet, die Schlüssel austauschen und so die Kommunikation abfangen und Belauschen kann. Auf diese weise wird das Brechen des Codes umgangen. Ein solcher Angriff kann nicht 100% abgewehrt werden. Es besteht eine Möglichkeit einen Signatur/Hash (Sichere Checksumme) zu tauschen und diese im Text zu Verstecken so das ein Lauscher diese nicht verändern kann weil er nicht erkennt wo oder wie, dann müssen sich aber die beiden Kommunikationspartner auf eine solche Tarnung einigen, was dem gleichkommt das ein Paßwort sicher vereinbart werden müßte. Zertifizeirungstsellen die den Schlüsseltausch und die Signaturen überwachen können ebenfalls Abhilfe schaffen, aber auch diese könnten korrumpiert werden.
Mit der Quantenkryptografie gibt es allerdings eine Möglichkeit zur sicheren Kommunikation, welche Quantenzustände verwendet um Informationen zu übermitteln. Diese erkennt einen "Man in der Mitte Angriff", da jede Beobachtung den Quantenzustand der übertragenen Information verändert und damit entdeckt wird. Erkennt man einen solchen Angriff, kann man die aktuelle Übertragung abbrechen und eine neu starten. So könnte die Kommunikation also nur noch gestört aber nicht mehr unbemerkt belauscht oder manipuliert werden.
Eigentlich muß man ganz grundsätzlich davon ausgehen das es überhaupt keine 100% sichere Technologie gibt, da nie ausgeschlossen ist das ein findiger Geist ein kreative Lösung für ein scheinbar unlösbares Problem findet. Aber nur deshalb weil man in auch ein Haus einreisen kann würde natürlich auch Niemand auf ein Hausschlüssel verzichten.

Sogut wie jeder Verschlüsselungs-Algorithmus basiert auf einem mathematisch "noch" nicht gelösten Problem, was aber nicht bedeutet das es keine Lösung gibt und diese auch irgend wann gefunden werden könnte. Es gibt aber ein symmetrischer Algorithmus der auch mathematisch beweisbar 100% sichereren ist, nämlich der OTP Algorithmus. Es ist ein Verfahren in welchen das Paßwort aus Zufallszahlen besteht die genauso lang sind wie die Nachricht selbst und nur einmal verwendet wird. In der Praxis ist dies aber nicht verwendbar und bedarf eine sichere Übertragung oder ein verabredete Datenmenge. Zusammen mit der Quantenkryptografie könnte OTP aber interessant werden.
Für sehr sichere Kryptografie-Kommunikation könnten mehrere Verfahren ineinander verschachtelt werden, und jedes müßte möglichst große Schlüssel verwenden. Ein Angreifer der den Code mathematisch brechen will, müßte dann zu jedem der verwendeten Algorithmen eine Lösung kennen. Besteht nämlich kein mathematischer Weg die Kryptoanalyse zu beschleunigen, müßte er einen Bruteforce-Angriff durchführen, und der Rechen-/Zeit-/Speicher-Aufwand steigt dramatisch je länger die Schlüssel sind. Quantencomputer könnten das bis zu einem gewissen Grad erreichen und Codes knacken die als sicher gelten, wenn die Schlüssellängen zu klein oder die Algorithmen zu schwach sind.
In er Praxis wird deshalb die Kryptoanalyse wenn es irgendwie geht umgangen, und die Informationen ungeschützt abzufangen, zB. über "Man in der Mitte Angriff", Tempest-Angriff, Hintertüren in Software oder ein Generalschlüssel, bewußt schwache Algorithmen (Snakeoil) oder Insider-Informationen und Social-Engineering.

Der Vollständigkeit halber sei noch erwähnt das es neben symmetrischen und asymmetrischen Verschlüsselungsverfahren auch noch andere Möglichkeiten gibt Daten zu schützen von, zB. die Steganographie welche es ermögliche Informationen innerhalb anderer Information (zB. Bilder Musik Videos) so zu verstecken das man gar nicht erkennen kann das überhaupt neben der sichtbaren Haupt-Information noch zusätzlich geheime versteckte Informationen darin existieren. Die Schwierigkeit liegt dabei darin, die Träger-Information so zu verändern das man die Veränderungen nicht erkennen kann (zB. über Statistiken Datenmuster oder spezialisierter/intelligenter Analyse). Und es können im Verhältnis zu den Träger-Daten nur wenige Geheime-Daten eingefügt werden. Sichere nicht erkennbare Steganographie ist schwierig, aber wenn dann besteht der beste Schutz allerdings dann darin, das die Daten nicht nur verschlüsselt sind, sondern man gar nicht erkennen kann das überhaupt geschützte Daten existieren.
Spreu-und-Weizen Algorithmus (Chaffing-and-Winnowing) ist ein weiteres Verfahren Daten zu schützen. Dabei werden die eigentlichen Daten nicht verschlüsselt sondern es werden andere Informationen hinzu gemischt so das am Ende nicht mehr erkennbar ist welche Daten zur eigentlichen Nachricht gehören und welche hinzugefügt wurden. Das Verfahren hat also Ähnlichkeiten mit der Steganographie. Da die Nachricht selbst aber eben nicht geschützt ist, ist auch die Sicherheit geringer.

Verschlüsselungsalgorithmen die als sicher gelten und gut erforscht sind:
Symmetrisch: Blowfish, Twofish, CAST, 3DES, IDEA, RC6, Serpent, Rijndael
Asymmetrisch: RSA, DH, Elgamal
Steganographie: (Da gibt es noch kein Algorithmus in dem Sinne sondern Kombinationen verschiedener Analyse und einfüge Verfahren. zB. F5)

RSA (Rivest Shamir Adleman) ist ein Asymmetrischer Verschlüsselungsalgorithmus und ermöglichst es ein Paßwort aus Zufallsdaten mit einem öffentlichen Schlüssel zu verschlüsseln, das nur mit einem privaten geheimen Schlüssel wieder entschlüsselt werden kann.

• Ein Kommunikationspartner generiert 2 Primzahlen P und Q.
• Daraus berechnet er N und Phi und dann E und D.
• P Q und Phi könnten vernichtet werden oder zusammen mit dem Privaten Schlüssel D geschützt/verschlüsselt aufbewahrt werden.
• Nun gibt er die beiden Zahlen N und E bekannt, gemeinsam bilden sie den öffentlichen Schlüssel
• Zahl D hält er geheim, und zusammen mit N bilden sie den privaten Schlüssel

• Ein zweiter Kommunikationspartner benutzt nun N und E um eine Nachricht zu schützen, er kann die nur in eine Richtung rechnen, an Hand der beiden Zahlen die er kennt kann er die Nachricht nicht mehr zurück rechnen. Normalerweise wird dazu eine Zufallszahl verwendet die als Paßwort für einen Symmetrischen Algorithmus verwendet wird, da RSA zu langsam ist um große Datenmengen zu verschlüsseln. Die tatsächlichen Daten sendet er zusammen mit dem über RSA geschützten Paßwort an den Empfänger.
• Der Empfänger benutzt nun N und D um die geschützte Zahl zu rekonstruieren und damit die Daten zu entschlüsseln.

• Auf diese weise kann ein Schlüssel öffentlich gestellt werden damit zwei Kommunikationspartner die sich nicht kennen und kein geheimes Paßwort auf einem sicheren Kanal vereinbaren können miteinander privat kommunizieren können.
• Die Sicherheit von RSA basiert auf dem mathematischen Problem, das große multiplizierte Primzahlen nicht leicht wieder in ihre Faktoren zerlegt werden können, an Hand von N und E kann man also nicht leicht P Q oder D ermitteln. Je größer diese Zahlen sind um so sicherer ist RSA. Die Bit-Länge von N gibt die Sicherheit an, also P und Q = 1024 Bit, dann ist es ein RSA-2048. Der Code basiert also auf einem mathematisch "noch" nicht gelösten Problem, was aber nicht bedeutet das es keine Lösung gibt und diese auch irgend wann gefunden werden könnte.

DH (Diffie Hellman) ist eigentlich kein Asymmetrisches-Verschlüsselungs-Verfahren sondern eher ein Schlüssel-Vereinbarungs-Verfahren, das es ermöglicht über öffentliche Zahlen eine geheime Zahl zu verabreden.

• Zwei Kommunikationspartner (A) und (B) einigen sich auf eine Primzahl P, und auf Zufallszahl G.
• Beide Partner erzeugen jeweils eine geheime Zufallszahl A und B.
• Beide berechnen jeweils PA und PB über die bekannten Zahlen P und G, und geben die einander bekannt.
• Nun kann jeder eine gemeinsame Geheime Zahl berechnen, KA und KB sind gleich.

• Ein Kommunikationspartner benutzt die öffentlichen Zahlen P G und PA, und berechnet mit Hilfe seiner eigenen Geheimzahl B daraus PB und KB. Die tatsächlichen Daten verschlüsselt er symmetrisch mit KB und sendet diese zusammen mit PB an den Empfänger.
• Der Empfänger benutzt nun P G und PB um daraus KA zu berechnen und kann mit dieser Zahl die Daten entschlüsseln.

• KA und KB sind gleich jede sieht also das gleiche Ergebnis. Aber an Hand der bekannten Zahlen P G und PA PB kann ein Lauscher weder die beiden geheimen Zahlen A und B und auch nicht das Ergebnis KA und KB ermitteln. Auf diese weise können zwei Partner eine geheime Zahl austauschen, ohne ihre geheimen Zahlen preis zu geben.
• Die Sicherheit von DH beruht auf dem Problem das diskreter Logarithmen (Ganzzahl Logarithmen) nicht einfach zu berechnen sind. Je größer die Zahlen sind um so sicherer ist DH. Wie RSA basiert der Code also auf einem mathematisch "noch" nicht gelösten Problem, was aber nicht bedeutet das es keine Lösung gibt und diese auch irgend wann gefunden werden könnte.