Eine Frage an die Mathematiker unter euch (Zufallsgenerator bzw. RSA Verfahren)

[peat-ar]

Ich wusste ehrlich gesagt nicht wohin ich diese Frage posten sollte, da ich nicht weiß wo der Fehler eigentlich liegt, aber da mir hier schon einmal so toll geholfen wurde, habe ich mich für dieses Forum entschieden

Nun zum Problem Nr. 1: Der Zufallsgenerator (eigentlich "quadratischer Restgenerator", mit der Anleitung von Kuno Kohn) weist eine Schwäche auf (so wie ich ihn programmiert habe). Eigentlich sieht das ganze ja recht einfach aus (Vorkenntnisse nicht wirkich erforderlich), aber es ist folgende Eigenschaft, die für einen "Zufallsgenerator" eigentlich ziemlich unpraktisch ist und sich relativ leicht aus dieser Periode auslesen lässt:

10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 1

Die Periode ist ziemlich kurz und es kommen nicht alle Zahlen vor, aber das führe ich einfach mal auf meine nicht ganz optimal gewählten Parameter zurück (bessert mich bitte aus, falls es nicht so sein sollte); dass jede 2te Zahl aber die vorhergehende +1 ist, nervt allerdings schon ein bisschen. (Habs schon so programmiert dass nur jede 2te Zahl angezeigt wird, aber die ganz elegante Lösung ist das ja jetzt auch nicht)

Meine Frage dazu: was ist an diesem Code

PHP-Code:

var p:Number = 3;         //p mod 4 = 3; muss Primzahl sein!
var q:Number = 7;         //q mod 4 = 3; muss Primzahl sein!
var n:Number = p*q;       //"Blumsche Zahl"
var a:Number = 10;        //relativ prim zu n --> keine gemeinsamen Teiler
var x0:Number = (a^2)%n;   //Startwert x0 wird berechnet
var xi:Number;             //i-ter Zufallswert
var i:Number;             //Zähler

for (i=0; i<100; i++)
    {
        xi = x0^((2^i)%((p-1)*(q-1)));
        trace(xi);
    } 


falsch?


Nun zur zweiten Frage: Die RSA Verschlüsselung - Die funktioniert nicht einmal mit den in dem "Tutorial" gegebenen Zahlen... Die wieder entschlüsselte Nachricht ist nicht ganz diesselbe wie die originale.

Mein Code:

PHP-Code:

//Anmerkungen zum Code: phiN entspricht Phi(n)

var p:Number = 7;                //möglichst große Primzahl
var q:Number = 13;                //möglichst große Primzahl
var n:Number = p*q;                //
var phiN:Number = (p-1)*(q-1);    //Anzahl der teilerfremden Zahlen zu n (1 zählt dazu)
//Da eine Primzahl nur durch 1 und sich selbst teilbar ist, sind alle Zahlen, 
//die unterhalb von ihr liegen, zu ihr teilerfremd. 
//D. h.: Phi(p) = p − 1 bzw. Phi(q) = q − 1. Folglich gilt für Phi(n):
//Phi(n) = (p − 1)(q − 1) 
var e:Number = 77;                //ed mod phiN = 1 --> e beliebige Primzahl, größer phiN, zB eine Fermat-Zahl
var d:Number = 29;                //wird mit Hilfe des euklidischen Algorithmus berechnet
var m:Number = 10;                //geheime Message
var c:Number = (m^e)%n;            //Chiffre-Text

trace("Originale Nachricht:      " + m);
trace("Verschlüsselte Nachricht: " + c);
trace("Entschlüsselte Nachricht: " + (c^d)%n);
if (m == ((c^d)%n))
    {
        trace("Das RSA-Verfahren hat funktioniert.")
    }
else
    {
        trace("Das RSA-Verfahren hat nicht funktioniert.")
    }
if (((e*d)%phiN) == 1)
    {
        trace("d wurde richtig gewählt.")
    }
else
    {
        trace("d wurde nicht richtig gewählt.")
    } 


Also d wurde richtig gewählt, das RSA-Verfahren hat aber nicht wirklich funktioniert... Ich hab keine Ahnung was ich bei den beiden Beispielen falsch gemacht habe (kann mir nicht vorstellen dass Flash da was falsch macht )

Bitte um Hilfe, mfg Peter

PS.: Ich weiß, dass beide Systeme nicht wegen ihrer Schnelligkeit sondern wegen ihrer Sicherheit beliebt sind und das deshalb mit Flash ziemlich sinnlos ist (Decompiler?), aber ich habs trotzdem mal in Flash programmiert, weil ich es in einer Sprache programmieren wollte in der ich mich halbwegs auskenne.

[hgseib]

a)
kein zufall, dass da ein bisschen über zufälle steht
H.G.Seib
- Zufallszahlen selbst gemacht

b)
RSA Verschlüsselung muss ich selbst erstmal gucken.
so für den kleinen grenzverkehr langt auch
H.G.Seib
- Verschleiern (Cäsar-, Verschiebe-, Shift-chiffre)
- Verschleiern (XOR)


//möglichst große Primzahl
jaja, aber das dach
x0:Number = (a^2)%n
geht in flash wohl nur mit integerzahlen? eine nummer könnte dafür mal eine nummer zu gross werden.


"..Ich spreche Deutsch, Englisch, Französisch, Latein und Russisch... nur mit AS will's nicht so ganz hinhauen.."
lustig, bei mir ist es grad umgekehr :-)

[peat-ar]

Die gebräuchlichste Art, Zufalls*zahlen zu erzeugen ist:
x = (a * x + c) % m

Das steht auch bei "meiner Quelle", aber da steht auch dass das ziemlich unsicher wäre und auch schon mal ein Danke für den 2ten Link, das ist ein bisschen viel auf einmal da muss ich mich erst einmal reinarbeiten...Coole Website btw ^^ (PHP oder MySQL kann man aber nicht anklicken oder?)

Number oder Integer macht (zumindest bei meinen Größenordnungen) noch keine Probleme, werd's mir aber merken, falls es mal welche geben sollte

@ hgseib: Brauchst du Hilfe mit Latein, Französisch oder Russisch (das lern ich aber noch kräftig)? ^^ (In AS kann ich in diesem Forum ja iwie niemandem helfen :'( )

Hat sonst jmd Ideen warum das nicht wirklich funktioniert?

[hgseib]

"..aber da steht auch dass das ziemlich unsicher wäre.."
ja sicher doch, ganz unsicher! dann entschlüssle doch bitte einmal: qss33g89zu851

kommt halt immer darauf an, wofür man was benützen möchte. für aus flash heraus z.b. einen punktestand zum server zu senden, dafür langts allemal. für wirklich wichtige sachen wird kein mensch flash benützen (war auch nie deine absicht, habe ich verstanden).


".. Number oder Integer macht (zumindest bei meinen Größenordnungen) noch keine Probleme.."
so kann man sich täuschen. in diesem tutorial steht doch '10 hoch 77 mod 91'. das 'dach' ist der bitweise XOR operator und nicht zur berechnung von hochzahlen.

trace(10+" hoch "+77+" mod "+91+" = "+Math.pow(10,77)%91);
trace(Math.pow(10,77) +" und davon mod 91 ???");

flash ist nicht in der lage 77stellige zahlen so zu berechnen, da Number maximal 15 signifikante stellen ausweissen kann.
keine ahnung, wie und warum modula überhaupt zu einem ergebnis kommt. jedenfalls kann das mit so gerundeten zahlen nie und nimmer stimmen.
ich denke, dafür musst du schon eigene routinen schreiben, die 'unendlich' grosse zahlen vollständig berechnen. so einfach ist RSA dann doch nicht zu programmieren ;-)

[peat-ar]

So, kann leider nur zitieren, da ich mich selbst noch immer zu wenig auskenne und (leider) nicht Mathematik studiere

Lineare Kongruenzgeneratoren [...] Obwohl solche Generatoren gute statistische Eigenschaften aufweisen, sind sie leider nicht sicher, da sie vorhersagbar sind.

(Kryptographie - Zufallsgeneratoren, Stand: Datum des Beitrages)

Das meinte ich mit unsicher, dass da ein normalsterblicher Schüler wie ich sowieso nur Bahnhof versteht, weiß ich schon (könntest mir da jetzt auch sonst etwas hinwerfen, ich könnte dir wohl kaum widersprechen ^^)

Dass das "^"-Zeichen nicht für "hoch" steht wusste ich nicht, doch richtig gelegen dass ich das Thema in einem Flash-Forum und nicht in einem Mathematik-Forum gepostet habe (Offtopic: sonst ist das "^" aber schon auch für "hoch" in Verwendung, oder? Zumindest beim Google-Rechner is es so )

dafür musst du schon eigene routinen schreiben, die 'unendlich' grosse zahlen vollständig berechnen

Wie würde man so etwas in Flash realisieren? Dann wärs wahrscheinlich einfacher es in C++ zu programmieren (das wird doch hauptsächlich für derlei Dinge verwendet, bessert mich aus wenn nicht )

[hgseib]

"..leider nicht sicher.."
das ist so auch korrekt. nur, zum hacken benötigt man eine genügend grosse menge an daten um die z.b. statistisch auf den kopf stellen zu können. egal, wie unsicher meine verschlüsslung auch ist, den waren sinn des kurzen stücks, das ich angegeben hatte, den kann so noch nicht mal das pendagon entschlüsseln. einfach zu wenig informationen ;-)

"..Zumindest beim Google-Rechner is es so.."
den benutze ich jetzt weniger zum programmieren. aber du hast schon recht. bei C,C++ wird das dach anders interpretiert. irgendwie müssen sich die programmiersprachen ja unterscheiden :-)
C++ ist die einzig richtige antwort. da du es aber (so habe ich es wohl verstanden) nicht zum benützen, sondern zum verstehen machen willst, dafür finde ich flash sogar noch besser, eben weil man sehr einfach seine ergebnisse sichtbar machen kann.


meine mathe-kenntnisse beruhen auch nur auf volksschul-niveau und kontinuierliches nachhaken.

mit absolut genauen zahlen rechnen z.b. programme wie mumath u.ä. (steht auch auf meiner liste in der richtung mal etwas zu machen)
zahlen sind dann nur noch natürliche zahlen und als string gespeichert. nachkommazahlen gibts nicht. das wird alles als brüchen (zähler/nennen) behandelt. das ist die einzigste methode um z.b. 1/7 genau dar zu stellen. und z.b. wurzel aus 2 darf dabei nicht ausgerechnet werden, sondern muss als wurzel aus 2 berücksichtigt werden.
etwas schneller geht es, wenn man nicht im 10er-system rechnet, sondern z.b. im 100.000er system. dann ist jede ziffer ein symbol(zahl) von 0 .. bis 99999. also alle rechenregeln plus, minus, mal. geteilt usw. wie in der schule gelernt rechnen, nur das es 'gedanklich' nicht nur 10 unterschiedliche ziffern gibt, sondern 100.000

ansonsten denke ich, das es da tricks gibt (da werde ich bei gelegenheit auch mal nach googlen). bekannt ist z.b. wenn die quersumme einer zahl durch 3 teilbar ist, dann ist es die ganze zahl auch. sinngemäss, die werden NICHT wirklich 10^77%91 ausrechnen. da gibt es bestimmt möglichkeiten das modulo(?) eleganter zu ermitteln? 10%91, 100%91, 1000%91 da gibt es bestimmt irgend welche gesetzmässigkeiten, die auf das ergebnis von 10....00%91 schliessen lassen.

[Brei]

Algorithmus für Ausdrücke der Form a^b mod c wäre Square and Multiply.
Binäre Exponentiation ? Wikipedia

Das ganze liegt in O(log(c)) ist also extrem flott, egal in welcher Sprache .

Gruß

[hgseib]

ja, kommt auch demnächst dran ;-)

[OT]
mathe ist doch eine feine sache, gibt mir richtig spass und ist überhaupt nicht langweilig !!! habe gerade eben "Das Problem des Handlungsreisenden" mit dem "Ameisen-Algorithmus" programmiert.

[hgseib]

obwohl,

das ist nicht ganz das, was ich meine.
mit 'Square and Multiply' kann man das schneller berechnen, aber das problem 'zahlen mit mehr als 15 signifikante ziffern haben zu müssen' bleibt.

ich dachte mehr an sowas:

/*
trace(10%91);
trace(100%91);
trace(1000%91);
trace(10000%91);
trace(100000%91);
trace(1000000%91);
//
trace(10000000%91);
trace(100000000%91);
trace(1000000000%91);
trace(10000000000%91);
trace(100000000000%91);
trace(1000000000000%91);
////
10
9
90
81
82
1
10
9
90
81
82
1
*/
function moduloSerien(a,b) {
	trace("moduloSerie: "+a+"%"+b);
	var c=a;
	var i=0;
	do {
		trace(i+": "+(c%b));
		i++;
		c*=a;
	} while (c<99999999999999);
	trace(c);
}
moduloSerien(26,7);

in der potenzentwicklung gibt modulo eine sich wiederholende reihe aus. wenn man so eine reihe kennt, dann kann man das modulo jeder x-beliebigen (natürlichen) hochzahl sagen, ohne das wirklich ausrechnen zu müssen. das wärs gewesen ;-)
das problem ist jetzt: wie kommt man am elegantesten zu der jeweiligen reihe und vermutlich gibt es reihen mit extrem vielen werten bis es (wenn überhaupt) zu einer wiederholung kommt?

dann wäre noch diese überlegung möglich:
wie kann man den wert teilen, ohne die potenzen selbst ausrechnen zu müssen, um einen restbetrag zu erhalten (mit weniger als 15 ziffern) von dem auch flash das modulo berechnen kann
so in die richtung etwa:
10000%3 == 10000/3 rest X
(9999/3 + 1/3) == rest 0 + rest 1
vermutlich mit ständig wechselndem multiplizieren und teilen (damit es zu keiner übergrossen zahl kommt) und die berechnungen als bruch behandeln.

[peat-ar]

Ok........werd mich erst mal etwas reinlesen müssen, sieht recht kompliziert aus (zumal wir Logarithmen noch nicht gelernt haben ) Aber danke, sieht nach einem vielversprechenden Lösungsansatz aus...