Zufallszahlen/Chiffrierung < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:43 So 09.09.2007 | | Autor: | michaa |
Hallo allerseits,
nach längerer Zeit (musste mich neu anmelden) mal wieder eine Frage.
Mein mathematischer Background wird durch das Problem, dem ich gegenüberstehe, leider deutlich überschritten,
bitte entschuldigt alle Ungenauigkeiten oder falls ich die Frage im falschen Forum stelle,
ich werde auf Nachfrage auch gerne versuchen meine Aussagen/Fragen zu spezifizieren..
Zuerst die eigentliche Frage:
Ich habe in einem Buch folgende Funktion gefunden, Zitat:
Man beginne mit einer Zahl zwischen 0 und 1.
Man addiere zu dieser Zahl die Kreiszahl p (etwa 3,14159265...).
Das Ergebnis potenziere man mit 8 (umgangssprachlich: Das Ergebnis »hoch 8« nehmen).
Der Nachkommaanteil des Ergebnisses ist die nächste Zufallszahl.
Mit dem Nachkommateil starte man den Algorithmus erneut, um eine weitere Zufallszahl zu erhalten.
Es ist mathematisch nachgewiesen, dass dieser Algorithmus die (mathematischen) Bedingungen für einen Zufallsgenerator erfüllt; die entstehende Zahlenfolge ist tatsächlich zufällig.
Ich verstehe hier "zufällig" so, dass die Ergebnisse nicht Periodisch und gleichmässig verteilt sind (?),
da ich der Quelle etwas misstraue, ist das richtig ?
Ich habe versuchsweise
a) Mit verschiedenen Startwerten eine Reihe von 10.000 Zahlen erzeugt und die Verteilung der Zahlen untersucht.
Mit meinen bescheidenen Mitteln sah die Verteilung ziemlich gleichmässig aus..
Hier die beiden in Perl geschriebenen Einzeiler:
perl -e '$n = 0.242;for(0..10000){$n = $n+3.14159265;$n = $n**8; $n = $n - int($n);print [mm] int($n*255),"\n";}' [/mm] > numbers.dat
Erzeugt eine Datei numbers.dat mit einer Folge von 10000 Zahlen 0<=x<255.
perl -e 'my %h;while(<>){chomp; $h{$_}++;};for (0..255){ print "$_ : $h{$_} [mm] \n";}' [/mm] numbers.dat
Gibt aus wie oft jede Zahl zwischen 0 und 255 vorkommt.
b) mit einem in C geschrieben Programm nach einer Periode gesucht.
bis ca 1,5 Milliarden konnte ich keine Periode finden.
Allerdings hat es mich etwas skeptisch gemacht, dass bei einer Erzeugung von Zahlen 0<=x<10 immer wieder 4 mal die gleichen Zahlen
in Reihe auftauchen, jedoch NIEMALS 5 Zahlen in Reihe.
Hier der Hintergrund für meine Frage:
Interessehalber möchte ich einenChiffrieralgorithmus implementieren.
Nachdem ich da eine Zeitlang drüber nachgedacht habe, bin ich auf folgenden Punkt gekommen:
Das Chiffrieren und besonders Dechiffrieren muss rechenintensiv sein, d.h. möglichst viel Rechenzeit und Speicher benötigen.
Je länger das Dechiffrieren benötigt, desto schwieriger, bzw. langwieriger, wird es über eine Brute-Force Attacke (simples Ausprobieren)
das zum Verschlüsseln benutzte Passwort zu finden.
Also habe ich mir in etwa folgenden Algorithmus ausgedacht:
Nehme das Passwort und erzeuge zunächst für jedes Zeichen eine Zahl nach obiger Funktion.
Beginne mit b = 1;
A:
Multipliziere die Zahl an der Stelle b mit der Anzahl der erzeugten Zahlen.
Der ganzzahlige Anteil des Ergebnisses sei a.
Addiere die Zahl an der Stelle a zu der Zahl an der Stelle b, teile das Ergebnis durch zwei.
Das Ergebnis ist die neue Zahl an der Stelle b.
Wiederhole die Funktion und hänge das Ergebnis an die Reihe der Zahlen an.
Fang wieder bei A an, bis 10 Millionen Zahlen erzeugt sind, b = 2; ...
Anschliessend will ich nach einem ähnlichen Algorithmus die 10 Millionen Zahlen untereinander "durchmischen",
bis die ganze Sache hinreichend rechenintensiv geworden ist...
Mit den erzeugten 10 Millionen Zahlen lässt sich nun der zu verschlüsselnde Text verschlüsseln.
Um die Sicherheit der Verschlüsselung zu gewährleisten, darf es natürlich keine "Abkürzungen" geben,
d.h. ein potentieller Angreifer darf keine Möglichkeit haben über einen einfacheren Algorithmus verschiedene Passwörter auszuprobieren.
Womit ich eben bei meiner eigentlichen Frage bin, ob die Ergebnisse der obigen Funktion wirklich gleichmässig verteilt sind und keine Periode aufweisen..
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Vielen Dank,
Micha
|
|
| |
|
Hi,
schon ne recht komische Idee den Algorithmus so rechenintensiv wie möglich zu machen xD
So kannst du deinen Algorithmus ja nur auf Rechner benutzen nicht z.B.
auf SmartCards (da will der User ja nicht 10minuten auf ne Verschlüsselung warten).
Ausserdem gibt es doch schon sehr gute symmetrische und asymmetrische
Verfahren bei denen noch kein guter Angriff bekannt ist, der in
polynomieller Zeit läuft.
Zum Beispiel AES, RSA, Elliptische Kurven etc...
Die Schlüsselräume können auch beliebig hoch gewählt werden,
so dass Brute-Force-Attacken nicht klappen.
Bei deiner Idee hab ich direkt schon ideen wie man das knacken kann ;p
erstens ist dein algorithmus nur ein erzeuger von pseudozufallszahlen,
da alles ja nur vom ersten Wert abhängt (genau wie z.B. bei einem LFSR).
Du kannst zwar festlegen, wie lang der nachkommaanteil ist, aber du darfst ihn nicht zufällig jedes mal wählen, da man ja auch alles wieder entschlüsseln muss.
Du darfst die generierten "Zufallszahlen" ja auf keinen Fall wie z.B. bei einer hash-funktion vermischen, sondern nur mit operationen, die man auch wieder zurückrechnen kann (für die entschlüsselung).
Ich habe nun ein Klar/-Geheimtext Paar [mm] (m_{1} [/mm] und [mm] c_{1})
[/mm]
Ich weiss ja nicht was du mit den 10Mil Zahlen machen willst.
Entweder XOR mit der Nachricht oder irgendwas...auf jeden Fall
eine operation, die eine inverse besitzt.
So kommt man mit [mm] (m_{1} [/mm] und [mm] c_{1}) [/mm] auf die 10Mil erzeugten Zahlen.
Nun entsteht einfach ein gleichgungssystem welches nach der spezifikation
deines algorithmuses aufgestellt werden kann.
Und ein Gleichungsystem ist in polynomieller Zeit lösbar.
Ich meine man hat nun die endergebnise und muss nun gucken wie man auf die verschiedenen startwerte kommt die diese Zahlen erzeugt haben.
Das geht bestimmt viel schneller als Brute Force.
Aber alles nur Gedanken, man weiss ja nichts richtiges über dein Vorhaben.
Aber ich bin mir sicher, dass man ein solches Verfahren in denen nur lineare
Operationen mit Zahlen ausgeführt werden sehr schnell brechen wird ;p
Jedenfalls denke ich, dass so etwas auch unnötig ist, da es wie gesagt genug gute Verfahren gibt.
Warum langsam, wenn es auch schnell und sicher geht? ;p
Aber schön, dass sich noch leute gedanken über Datensicherheit machen ;p
Machs gut.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:57 Mo 10.09.2007 | | Autor: | michaa |
> Hi,
Hallo !
> schon ne recht komische Idee den Algorithmus so
> rechenintensiv wie möglich zu machen xD
> So kannst du deinen Algorithmus ja nur auf Rechner
> benutzen nicht z.B.
> auf SmartCards (da will der User ja nicht 10minuten auf ne
> Verschlüsselung warten).
Mit SmartCards ist die ganze Vorgehensweise natürlich wieder anders.
Der Haken bei Smartcards ist allerdings, das sich etwa über Trojaner relativ einfach rumpfuschen lassen sollte.
Klar, absolute Sicherheit gibt es nicht, und über Keylogger lässt sich auch ein Passwort ausspähen,
ich könnte mir aber auch vorstellen z.B. eine mit der Maus zu bedienende Tastatur zu benutzen.
> Ausserdem gibt es doch schon sehr gute symmetrische und
> asymmetrische
> Verfahren bei denen noch kein guter Angriff bekannt ist,
> der in
> polynomieller Zeit läuft.
> Zum Beispiel AES, RSA, Elliptische Kurven etc...
> Die Schlüsselräume können auch beliebig hoch gewählt
> werden,
> so dass Brute-Force-Attacken nicht klappen.
>
Davon abgesehen dass bspw. AES faktisch nur bis 256 bit existiert.
Stärkere Verschlüsselungen sind in einigen Ländern verboten bzw. zum Export verboten,
allen voran Amerika. - Was mich wiederum mit Skepsis erfüllt..
Inzwischen sind auch Ansätze zum Aushebeln von AES mit relativ wenigen Ressourcen bekannt geworden,
Ob oder inwieweit AES-256 als geknackt gezählt werden kann, ist natürlich wieder eine andere Frage.
Klar ist, dass jeder Algorithmus knackbar ist, was allerdings ab einer bestimmten Komplexität ziemlich lange dauern kann -
daher der gedanke das ganze möglichst komplex zu gestalten.
Elliptische Kurven zum Verschlüsseln sind mir jetzt neu, werd ich mich drüber schlau machen.
Naja, ist schon eine Spielerei da was eigenes zu machen, hab mich aber schon etwas festgebissen.
> Bei deiner Idee hab ich direkt schon ideen wie man das
> knacken kann ;p
>
> erstens ist dein algorithmus nur ein erzeuger von
> pseudozufallszahlen,
> da alles ja nur vom ersten Wert abhängt (genau wie z.B.
> bei einem LFSR).
> Du kannst zwar festlegen, wie lang der nachkommaanteil
> ist, aber du darfst ihn nicht zufällig jedes mal wählen, da
> man ja auch alles wieder entschlüsseln muss.
>
> Du darfst die generierten "Zufallszahlen" ja auf keinen
> Fall wie z.B. bei einer hash-funktion vermischen, sondern
> nur mit operationen, die man auch wieder zurückrechnen kann
> (für die entschlüsselung).
>
> Ich habe nun ein Klar/-Geheimtext Paar [mm](m_{1}[/mm] und [mm]c_{1})[/mm]
>
> Ich weiss ja nicht was du mit den 10Mil Zahlen machen
> willst.
> Entweder XOR mit der Nachricht oder irgendwas...auf jeden
> Fall
> eine operation, die eine inverse besitzt.
> So kommt man mit [mm](m_{1}[/mm] und [mm]c_{1})[/mm] auf die 10Mil erzeugten
> Zahlen.
>
> Nun entsteht einfach ein gleichgungssystem welches nach der
> spezifikation
> deines algorithmuses aufgestellt werden kann.
> Und ein Gleichungsystem ist in polynomieller Zeit lösbar.
>
> Ich meine man hat nun die endergebnise und muss nun gucken
> wie man auf die verschiedenen startwerte kommt die diese
> Zahlen erzeugt haben.
>
> Das geht bestimmt viel schneller als Brute Force.
So wie ich Dich verstehe, gehst Du davon aus das der Angreifer den erzeugten Schlüssel besitzt.
Was allerdings nicht der Fall sein sollte, da der Schlüssel mit den zu chiffrierenden Daten -weiss noch nicht- zusammenaddiert wird, oder so.
Insofern würde ich davon ausgehen, falls die Werte des Schlüssels "zufällig" genug verteilt sind,
keine Rückschlüsse auf Schlüssel oder die chiffrierten Daten möglich sind,
da etwa Häufigkeitsanalysen (z.B. die Suche nach dem E als häufigsten Buchstaben in der deutschen Sprache)
fehlschlagen sollten. ?
Daher auch meine ursprüngliche Frage ob die erzeugten Zahlen der beschriebenen Funktion "zufällig" verteilt sind,
also keine Periode aufweisen und gleichmäßig verteilt sind.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:16 Mo 10.09.2007 | | Autor: | rainerS |
Hallo!
> Mit SmartCards ist die ganze Vorgehensweise natürlich
> wieder anders.
> Der Haken bei Smartcards ist allerdings, das sich etwa
> über Trojaner relativ einfach rumpfuschen lassen sollte.
Dann taugt die SmartCard nichts. Eine gute Implementierung erlaubt kein Herunterladen beliebiger Software.
> Klar, absolute Sicherheit gibt es nicht, und über Keylogger
> lässt sich auch ein Passwort ausspähen,
> ich könnte mir aber auch vorstellen z.B. eine mit der Maus
> zu bedienende Tastatur zu benutzen.
Genauso anfällig. Weswegen normalerweise der Kartenleser eine eigene Tastatur hat. Nicht umsonst sind Geldautomaten ziemlich raffiniert gegen Abhören geschützt.
> > Ausserdem gibt es doch schon sehr gute symmetrische und
> > asymmetrische
> > Verfahren bei denen noch kein guter Angriff bekannt
> ist,
> > der in
> > polynomieller Zeit läuft.
> > Zum Beispiel AES, RSA, Elliptische Kurven etc...
> > Die Schlüsselräume können auch beliebig hoch gewählt
> > werden,
> > so dass Brute-Force-Attacken nicht klappen.
> >
>
> Davon abgesehen dass bspw. AES faktisch nur bis 256 bit
> existiert.
Warum ist das ein Problem? Das sind [mm]2^{256}\approx 10^{77}[/mm] verschiedene Schlüssel. Selbst wenn ich pro Sekunde eine Milliarde Schlüssel durchprobieren kann, brauche ich immer noch mehr als [mm]10^{60}[/mm] Jahre zum Knacken. Da stirbt das Universum vorher.
> Stärkere Verschlüsselungen sind in einigen Ländern
> verboten bzw. zum Export verboten,
> allen voran Amerika. - Was mich wiederum mit Skepsis
> erfüllt..
>
> Inzwischen sind auch Ansätze zum Aushebeln von AES mit
> relativ wenigen Ressourcen bekannt geworden,
Nein, das siehst du falsch, so etwas gibt es bisher nicht. Es gibt begründeten Zweifel an der Sicherheit von AES, aber keine "Ansätze zum Aushebeln von AES mit relativ wenigen Ressourcen".
Wem AES nicht sicher genug erscheint, kann ja Twofish oder Blowfish nehmen.
> Ob oder inwieweit AES-256 als geknackt gezählt werden
> kann, ist natürlich wieder eine andere Frage.
> Klar ist, dass jeder Algorithmus knackbar ist, was
> allerdings ab einer bestimmten Komplexität ziemlich lange
> dauern kann -
> daher der gedanke das ganze möglichst komplex zu
> gestalten.
Ich glaube, du machst dir falsche Vorstellungen. Die theoretische und damit endgültige Grenze für jeden symmetrischen Algorithmus ist die Länge des Schlüsselworts, da jeder Algorithmus durch Ausprobieren aller möglichen Schlüssel zu knacken ist. Die Qualität eines Verschlüsselungsalgorithmus besteht darin, dass es nicht möglich ist (sein sollte), mit weniger Aufwand als dem theoretischen Maximum auszukommen. Gute Algorithmen (wie DES) haben diese Eigenschaft. Bei AES ist die Diskussion noch offen.
Aber selbst wenn es möglich sein sollte, AES256 statt mit [mm]2^{256}[/mm] zum Beispiel mit [mm]2^{200}[/mm] Versuchen zu knacken, sind das immer noch so viele, dass es für die üblichen Anwendungen kein Problem darstellt.
Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:00 Mo 10.09.2007 | | Autor: | michaa |
Hallo Rainer
>
> > Mit SmartCards ist die ganze Vorgehensweise natürlich
> > wieder anders.
> > Der Haken bei Smartcards ist allerdings, das sich etwa
> > über Trojaner relativ einfach rumpfuschen lassen sollte.
>
> Dann taugt die SmartCard nichts. Eine gute Implementierung
> erlaubt kein Herunterladen beliebiger Software.
Ich würde generell sagen, dass die einzig sichere Möglichkeit ein Rechner nur zum Verschlüsseln/signieren etc. wäre,
der KEINE Daten austtauscht -was natürlich sinnlos wäre,
der also die zu verschlüsselnden Daten nach einem möglichst strengen Protokoll austauscht.
Naja, auf jeden Fall bin ich nicht von der Sicherheit einer Smartcard überzeugt.
> > Klar ist, dass jeder Algorithmus knackbar ist, was
> > allerdings ab einer bestimmten Komplexität ziemlich lange
> > dauern kann -
> > daher der gedanke das ganze möglichst komplex zu
> > gestalten.
>
> Ich glaube, du machst dir falsche Vorstellungen. Die
> theoretische und damit endgültige Grenze für jeden
> symmetrischen Algorithmus ist die Länge des Schlüsselworts,
> da jeder Algorithmus durch Ausprobieren aller möglichen
> Schlüssel zu knacken ist. Die Qualität eines
> Verschlüsselungsalgorithmus besteht darin, dass es nicht
> möglich ist (sein sollte), mit weniger Aufwand als dem
> theoretischen Maximum auszukommen. Gute Algorithmen (wie
> DES) haben diese Eigenschaft. Bei AES ist die Diskussion
> noch offen.
>
> Aber selbst wenn es möglich sein sollte, AES256 statt mit
> [mm]2^{256}[/mm] zum Beispiel mit [mm]2^{200}[/mm] Versuchen zu knacken, sind
> das immer noch so viele, dass es für die üblichen
> Anwendungen kein Problem darstellt.
>
> Grüße
> Rainer
>
Wenigstens DES soll auch unsicher sein bzw. ist von AES abgelöst worden. (http://en.wikipedia.org/wiki/Data_Encryption_Standard..
Bei AES wird der derzeit wohl wahrscheinlichste Angriff eine BruteForce Attacke sein.
Wenn ich jetzt mal von einer Passwortlänge von 20 Zeichen ausgehe, und weiter dass jedes Zeichen aus kleinen und großen Buchstaben sowie den Zahlen besteht, komme ich auf [mm]20^{58}[/mm] mögliche Kombinationen.
Na gut, bei einem durchprobieren von 1 Milliarde Kombinationen pro Sekunden dauert das Knacken immer noch ca. [mm]10^{17}[/mm] Jahre...
Wenn ich mal davon absehe, dass sich etliche Kombinationen wohl zunächst ausschliessen lassen sollten,
wie etwa "asdfh2p3u4z2fasdkjh28cae9p8chcas98" oder so.
Wer sucht realistisch gesehen schon so ein Passwort aus, im Allgemeinen werden doch eher Kombinationen aus Wörtern und Zahlen,d.h. meist Datumsangaben, ausgewählt..
Womit ich allerdings nicht sagen will, dass AES deswegen unsicher sei, selbst wenn ein Angreifer "nur" 1000 Jahre rechnen müsste und könnte, wären bis dahin die verschlüsselten Informationen uninteressant..
Ist halt wie schon gesagt hauptsächlich eine Spielerei..
Aber eigentlich geht's mir ja auch um diese Spielerei,
d.h. ob der von mir beschriebene Algorithmus sich mit weniger als dem theoretischen Maximum berechnen lässt.
Ich glaube ich muss meine ursprüngliche Frage noch einmal revidieren - bzw. überdenken..
Grüße,
Michael
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:52 Di 11.09.2007 | | Autor: | rainerS |
Hallo Michael,
> Wenigstens DES soll auch unsicher sein bzw. ist von AES
> abgelöst worden.
Ja klar, weil der Schlüssel nur 56 Bit lang ist, es also nur eta [mm]10^{17}[/mm] verschiedene Schlüssel gibt. Deswegen ist es immer noch ein guter Algorithmus. Wenn du DES dreimal hintereinander mit verschiedenen schlüsseln benutzt, hast du eine sehr gute Verschlüsselung.
> Bei AES wird der derzeit wohl wahrscheinlichste Angriff
> eine BruteForce Attacke sein.
Die damit wegen [mm]2^{256}[/mm] sinnlos ist.
> Wenn ich jetzt mal von einer Passwortlänge von 20 Zeichen
> ausgehe, und weiter dass jedes Zeichen aus kleinen und
> großen Buchstaben sowie den Zahlen besteht, komme ich auf
> [mm]20^{58}[/mm] mögliche Kombinationen.
> Na gut, bei einem durchprobieren von 1 Milliarde
> Kombinationen pro Sekunden dauert das Knacken immer noch
> ca. [mm]10^{17}[/mm] Jahre...
>
> Wenn ich mal davon absehe, dass sich etliche Kombinationen
> wohl zunächst ausschliessen lassen sollten,
> wie etwa "asdfh2p3u4z2fasdkjh28cae9p8chcas98" oder so.
> Wer sucht realistisch gesehen schon so ein Passwort aus,
> im Allgemeinen werden doch eher Kombinationen aus Wörtern
> und Zahlen,d.h. meist Datumsangaben, ausgewählt..
Was hat das mit AES zu tun?
Du verwechselst Passworte mit den Schlüsseln symmetrischer Algorithmen. Das sind zwei verschiedene Dinge! Passworte dienen zur Authentisierung, Schlüssel zur Verschlüsselung. Warum solltest du die Schlüssel auf Folgen von Buchstaben und Zahlen einschränken?
Grüße
Rainer
|
|
|
| |
|
Hi,
erstmal: Absolute Sicherheit gibt es doch. xD
z.B. One-Time-Pad bei dem Schlüssel so lang wie Nachricht, Schlüssel echt
zufällig erzeugt (z.B. radioaktiver Zerfall) und Schlüssel nur einmal verwendet. So gibt es zu einem Geheimtext immer einen anderen Schlüssel,
der einen anderen Sinvollen Klartext ergibt, und der Angreifer weiss nicht, welcher der richtige Schlüssel und somit auch Klartext ist.
und nun zu deinem "Zufallszahlengenerator"....
Sagen wir mal es reicht aus für unsere Zwecke und wir rechnen mit 50
Nachkommastellen.
Das Problem ist doch jetzt, die erste Zahl (zwischen 0 und 1) muss doch nun echt zufällig gewählt werden (z.B. Radioaktiver Zerfall). Die daraus
resultierenden Zahlen werden ja alle nach deinem Algorithmus generiert
und sind somit nicht mehr echt zufällig.
Stell dir die generierung der Zahlen doch mal als LFSR vor.
Dein Startwert zwischen 0 und 1 ist dann der Initialisierungsvektor
des LFSR. Beides, der Startwert und der Init.Vektor werden aus dem Passwort generiert. Jede neu generierte Zahl ist dann wie ein neu generiertes Bit eines LFSR. Beides ist pseudo-zufällig.
Und dein Algorithmus hat auch keine unendlich lange Periode, da wir
ja nur mit 50 nachkommastellen rechnen.
Kurz rechnen...
50 Nachkommastellen a 10 Ziffern pro Stelle macht eine Max Periode 10^50
Ein einfaches LFSR mit 192 Bit init.Vektor hat max Periode 2^192-1
Nun kann man die Perioden bei beiden erhöhen, bei deinem Algo durch die
erhöhung der Nachkommastellen. Beim LFSR durch die verlängerung des Initvektors etc..
Beide Verfahren sind pseudozufallsgeneratoren mit perioden endlicher länge, wie hier schon jemand bemerkte begrenzt durch rechnerarithmetik.
Deine Methode ist halt nur viel rechenintensiver, aber nicht sicherer.
Beide Verfahren (LFSR und dein Generator) sind völlig äquivalent und es
gibt genug analytische angriffe die das Passwort (startwert oder init.vektor) sehr schnell herausfinden. Rückschlüsse möglich
wenn z.B. wenige Bits klar und geheimtext bekannt.
Aber das ist auch nicht der Punkt, du musst dir klarmachen,
dass es nicht darum geht, alles rechenintensiv zu machen.
Wenn du dir einen Algorithmus überlegen willst, dann würde ich mir
erstmal angucken wie die anderen Algorithmen entworfen wurden.
Es gibt ja auch gewisse Designkriterien.
z.B. beruhen Asymmetrische Verfahren wie RSA oder D-H-Schlüsselaustausch immer auf sog. NP-hard Problemen.
Das heisst Probleme die nicht in polynomieller Zeit lösbar sind.
bei RSA wie gesagt Faktorisierung und bei D-H-Schlüsselaustausch das
diskrete Logarithmus Problem.
Bei symmetrischen Verfahren wie AES oder DES sind es eine Reihe von
linearen Operationen wie Permutationen oder Rotationen.
Und dann eine nicht lineare Operation, die sog. SBOX , in welcher die
gesamte Sicherheit des Algorithmus liegt.
Ein Verfahren gilt ja wirklich erst als sicher, wenn es keinen besseren Angriff als Brute-Force gibt und dieser nicht in akzeptabler Zeit durchzuführen ist.
Ferner werden auch alle Daten des Verfahrens offen gelegt.
Das heist, dass die Sicherheit wirklich nur auf der grösse des
Schlüsselraums beruht, und selbst z.B. der autor des verfahrens ohne den Schlüssel einen text nicht entschlüsseln kann (obwohl nur er weiss, wie das verfahren funktioniert).
Bei AES kannst du die Schlüssellänge ganz leicht auf 768bit erhöhen.
Der Schlüssel wird erstmal in 3*256 bit Teile aufgeteilt.
Key = K1 || K2 || K3
|| bedeutet angehangen...K1,K2,K3 jeweils 256bit
AES768 = AES(K1,AES(K2,AES(K3, TEXT)))
und das kann so beliebig weiter getrieben werden.
Bei RSA erhöht man einfach auf 8192 bit und ist glücklich usw...
Deswegen ist es wichtig einen SCHNELLEN Algorithmus zu haben,
da der Schlüssel beliebig vergrössert werden kann. (IMMER!!!)
Da kommen wir auch schon zu den SmartCards ;p
SmartCards generell würde ich schon als sicher empfinden.
Da wird ja auch alles weiterentwickelt, damit diese karten z.B. nciht mehr so leicht nachzumachen "Clonen" sind oder man die karte einfach öffnet und guckt was so über den Datenbus läuft oder das passwort einfach ausliest oder ähnliches.
Aber es entstehen neue Problematiken...
Vor einiger Zeit wurde z.B. ein Angriff bekannt, wie man über den Stromverbrauch der Karte Hypothesen über Schlüssel machen konnte und
so den Schlüssel ziemlich schnell gefunden hat.
Es sollte ja klar sein, dass eine Potenzierung mehr Strom braucht als eine
Multiplikation oder eine Multiplikation mehr Strom als eine Addition.
Hier ist es nötig ein verfahren so zu implementieren, dass ein solcher
angriff nicht mehr funktioniert.
Und nun zu deinem Verschlüsselungsalgo...
Nein, ich gehe nicht davon aus, dass der Angreifer den Schlüssel kennt.
Das wäre ja sinlos und der angreifer könnte alles ver- und entschlüsseln.
Du verwendest deinen Algortihmus mit deinen Freunden um eure chatnachrichten zu verschlüsseln. ihr habt euch auf ein passwort geeinigt
als ihr euch persönlich getroffen habt (sicherster weg ;p) . Damit ihr euch nicht nach jeder nachricht neu treffen müsst benutzt ihr das Passwort öfters. (ihr einigt euch z.B. jeden tag in der schule auf ein neues PW)
Wenn der Angreifer aber nun ein Geheimtext hat und den dazugehörigen Klartext kennt (sei es weil der header des Datenpaketes immer gleich aussieht oder so ;p), kann er leicht auf das passwort kommen, wenn deine
Verschlüsselung keine beweisbar sichere Operation beinhaltet.
Er kann dann den ganzen tag eure kommunikation mithören.
Ich meine ich weiss ja nicht wie dein Algorithmus aussehen wird, aber ich
weiss, dass ein Verfahren auf einer beweisbaren sicheren Operation beruhen sollte (damit auch wirklich nur Brute-Force-Attacken laufen)
und dann reicht es wenn der Algo so schnell wie möglich ist, man vergrössert einfach den Schlüsselraum ;p
Bitte versteh mich jetzt nicht falsch, ich freu mich echt wenn leute sich für
Sicherheit interessieren (viele denken ja garnicht darüber nach),
aber ich hoffe ich konnte dich ein wenig animieren die sache etwas anders
zu sehen. Sichere Verfahren gibt es genug, es kommt auf die sichere
Implementierung an (Siehe SmartCard -> Stromverbrauch).
Und mal angenommen du entwickelst ein absolut sicheres Verfahren,
welches aber super rechenintensiv ist. Wie soll es dann die breite
Masse verwenden können? Stell dir mal vor alle Firmen die jetzt ihre Daten
verschlüsseln würden nun dein Verfahren benutzen. Stell dir mal vor
was für ein gewaltiger Energieanstieg das wäre.
Was wirklich interessant wäre, wäre z.B. ein Asymmetrisches Verfahren für
SmartCards welches schneller(weniger Energie) ist als Elliptische Kurven bei gleicher Sicherheit.
Oder z.B. ein Symmetrisches Verfahren mit 768bit Schlüssellänge welches
schneller ist als die simple verschachtelung dreier AES256 (unser AES768)
Oder du machst dir Gedanken, wie du ein schon existierendes sicheres
Verfahren so für deine Zwecke einsetzt, dass wirklich nur
Brute-Force-Attacken laufen. (Bei Datenverkehr über Internet (unsicherer Kanal) ist das ja so eine Sache ;p Da sollte man auch sicherstellen, dass
die richtige Person die Daten erhält und ähnliches.
Kannst ja mal dein Verfaren hier veröffentlichen (+ implementierung für deine Zwecke) mit zugehörigem
Klar und Geheimtext. Mal gucken wer als erster den Schlüssel findet ;p
Also ich bin da auch nicht so der Crack aber bin mir sicher, dass
hier schnell einige Ansätze stehen werden.
Machs gut.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:41 Mo 10.09.2007 | | Autor: | rainerS |
Hallo Micha!
> Zuerst die eigentliche Frage:
>
> Ich habe in einem Buch folgende Funktion gefunden, Zitat:
> Man beginne mit einer Zahl zwischen 0 und 1.
> Man addiere zu dieser Zahl die Kreiszahl p (etwa
> 3,14159265...).
> Das Ergebnis potenziere man mit 8 (umgangssprachlich: Das
> Ergebnis »hoch 8« nehmen).
> Der Nachkommaanteil des Ergebnisses ist die nächste
> Zufallszahl.
> Mit dem Nachkommateil starte man den Algorithmus erneut,
> um eine weitere Zufallszahl zu erhalten.
> Es ist mathematisch nachgewiesen, dass dieser Algorithmus
> die (mathematischen) Bedingungen für einen Zufallsgenerator
> erfüllt; die entstehende Zahlenfolge ist tatsächlich
> zufällig.
>
> Ich verstehe hier "zufällig" so, dass die Ergebnisse nicht
> Periodisch und gleichmässig verteilt sind (?),
> da ich der Quelle etwas misstraue, ist das richtig ?
Das ist eine gute Frage. Ich vermute, etwas in der Art ist gemeint: Gleichverteilung sicherlich, aber sonst...
Es gibt eine (weder bewiesene noch widerlegte) Vermutung, dass die Nachkommastellen von [mm]\pi[/mm] eine zufällige Folge bilden. Offensichtlich ist bisher kein Gegenbeispiel bekannt (sonst wäre die Vermutung ja widerlegt).
Jede irrationale Zahl kann als Basis für einen solchen Zufallszahlengenerator dienen (siehe: ![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Arithmetischer_Zufallszahlengenerator).
Aber der Algorithmus hat einen entscheidenden Haken: Jede Rechnerarithmetik arbeitet mit endlich vielen Stellen. Der Beweis, dass er "die mathematischen Bedingungen für einen Zufallsgenerator erfüllt" wird ohne diese Einschränkung geführt. Damit ist er aber für die reale Arithmetik auf dem Rechner nicht gültig.
Der Algorithmus ist auch nicht sonderlich schnell; wenn ich ein paar Milliarden Zufallszahlen brauche, ist die Geschwindigkeit ein sehr wichtiger Faktor.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:24 Mo 10.09.2007 | | Autor: | michaa |
> Hallo Micha!
Hallo Rainer, und Danke !
Ich dachte schon ich hätte meine Frage einfach gänzlich verkehrt gestellt..
> > Zuerst die eigentliche Frage:
> >
> > Ich habe in einem Buch folgende Funktion gefunden, Zitat:
> > Man beginne mit einer Zahl zwischen 0 und 1.
> > Man addiere zu dieser Zahl die Kreiszahl p (etwa
> > 3,14159265...).
> > Das Ergebnis potenziere man mit 8 (umgangssprachlich:
> Das
> > Ergebnis »hoch 8« nehmen).
> > Der Nachkommaanteil des Ergebnisses ist die nächste
> > Zufallszahl.
> > Mit dem Nachkommateil starte man den Algorithmus
> erneut,
> > um eine weitere Zufallszahl zu erhalten.
> > Es ist mathematisch nachgewiesen, dass dieser
> Algorithmus
> > die (mathematischen) Bedingungen für einen
> Zufallsgenerator
> > erfüllt; die entstehende Zahlenfolge ist tatsächlich
> > zufällig.
> >
> > Ich verstehe hier "zufällig" so, dass die Ergebnisse nicht
> > Periodisch und gleichmässig verteilt sind (?),
> > da ich der Quelle etwas misstraue, ist das richtig ?
>
> Das ist eine gute Frage. Ich vermute, etwas in der Art ist
> gemeint: Gleichverteilung sicherlich, aber sonst...
>
> Es gibt eine (weder bewiesene noch widerlegte) Vermutung,
> dass die Nachkommastellen von [mm]\pi[/mm] eine zufällige Folge
> bilden. Offensichtlich ist bisher kein Gegenbeispiel
> bekannt (sonst wäre die Vermutung ja widerlegt).
>
> Jede irrationale Zahl kann als Basis für einen solchen
> Zufallszahlengenerator dienen (siehe:
> http://de.wikipedia.org/wiki/Arithmetischer_Zufallszahlengenerator).
>
> Aber der Algorithmus hat einen entscheidenden Haken: Jede
> Rechnerarithmetik arbeitet mit endlich vielen Stellen. Der
> Beweis, dass er "die mathematischen Bedingungen für einen
> Zufallsgenerator erfüllt" wird ohne diese Einschränkung
> geführt. Damit ist er aber für die reale Arithmetik auf dem
> Rechner nicht gültig.
>
> Der Algorithmus ist auch nicht sonderlich schnell; wenn ich
> ein paar Milliarden Zufallszahlen brauche, ist die
> Geschwindigkeit ein sehr wichtiger Faktor.
Ich habe den Algorithmus versuchsweise in C mit dem Datentyp float implementiert,
d.h. mit ca 50 Nachkommastellen gerechnet.
Wenigstens mit der Geschwindigkeit gabs da keinerlei Probleme, und die Verteilung erschien mir regelmäßig
(mit meinen bescheidenen Mitteln eben), eine Periode konnte ich bis zu einer Iteration von [m]10^{7}[/m] auch nicht finden.
Wobei das dann aufgrund der begrenzten Genauigkeit wohl weniger mit pi zu tun hat, sondern mit der Potenz ?
d.h. es würde wohl ausreichen den Nachkommaanteil der Achten Potenz zu betrachten.. ?
Im speziellen will ich ja den eigentlichen Schlüssel durch Kombination der aus dem Passwort erzeugten Zahlen berechnen.
Ich habe da eben die Hoffnung,
dass sich aufgrund der Anzahl der möglichen Kombinationen der untereinander multiplizierten/dividierten/addierten usw. Zahlen
die Berechnung des Schlüssels nicht abkürzen lässt..
Also in etwa:
-Die erste Zahl des Arrays (also der Menge der erzeugten Zahlen) sei x
-wenn [m]x<0.1[/m] dann: wende obige Funktion an, nehme das Ergebnis mal die Länge des Arrays, das Ergebnis sei die Zahl y
-Addiere x und y, teile das Ergebnis durch zwei.
-das Ergebnis ist die neue Zahl an der ersten Stelle.
Fahre mit der Zahl an der zweiten Stelle fort.
Das liesse sich dann varieren, d.h. wenn [m]0.1
Vorraussetzung wäre aber wohl eben, dass die Funktion zum erzeugen der Zahlen hinreichend "zufällige" zahlen erzeugt.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:34 Di 11.09.2007 | | Autor: | DirkG |
> Es ist mathematisch nachgewiesen, dass dieser Algorithmus die (mathematischen)
> Bedingungen für einen Zufallsgenerator erfüllt; die entstehende Zahlenfolge
> ist tatsächlich zufällig.
Diese Einschätzung hat wohl eher ein an Lügen - Verzeihung: kreativer Wahrheit - gewohnter Werbe- bzw. Marketingfachmann verfasst, aber kein seriöser Mathematiker.
Es ist nämlich folgendes festzuhalten:
Kein einziger Pseudozufallszahlen-Generator (und um einen solchen handelt es sich hier) erfüllt alle Bedingungen an einen "echten" Generator von Zufallszahlen - das sieht man schon daran, dass die Folge deterministisch erzeugt wird.
In den meisten Fällen macht das aber nichts, da es genügt, wenn die Folge gewisse wichtige statistische Eigenschaften zeigt, die auch eine echte Zufallszahlenfolge zeigen würde. Was nun diese "gewissen" Eigenschaften betrifft, so gibt es durchaus verschiedenste Anforderugen, basierend auf Histogrammen, Autokorrelationen usw.
Gruß,
Dirk
|
|
|
|
