Hilfe bei RAS-Schema

[Frank]

Hey, leut, ich hab sone richtig dumme Aufgabe in Mathe aufbekommen und ich blick da net durch.

THEMA asynchrone Verschlüsselung (RAS)
AUFGABE

ALLICE und BOB wollen sich verschlüsselte Nachrichten zukommen lassen.
Sie einigen sich auf die Einwegfunktion

y^x mod p

Sie wählen öffentlich y = 7 und p = 11.

den Wert für x denken sie sich im geheimen aus ohne dem anderen diesen mitzuteilen.
ALLICE setzt 3 ein und bekommt 2 als Ergebnis
BOB setzt 6 ein und bekommt 4 als ergebnis

Sie teilen sich diese Ergebnisse (2;4) mit.

Was müssen sie nun tun, um die Verschlüsselte Nachricht nun wieder zu entschlüsseln?

Hab bereits gegooglet aber da nichts gefunden, nur formeln zum knacken von RAS und da blick ich echt nicht mehr durch.
Ich wäre euch echt für jede Hilfe dankbar

 

[Prophet]

Ich habe hin und her überlegt aber keine Lösung gefunden.

Wenn r = y^x mod p

Dann ist r, y und p bekannt.

y^x = p * k + r

Wobei k unbekannt ist.

x = logy(p * k + r)

k kann nur aufgelöst werden wenn x bekannt ist. Also habe ich mich im kreis gedreht, aber vielleicht hilft es dir.

Ich habe auch Wikipedia dazu diesen Artikel zum Diffie-Hellman-Schlüsselaustausch gefunden. Der ist ganz interessant und erinnert mich an deine Problematik.

Im übrigen nennt es sich nicht umsonst einwegverschlüsselung. Eine gleichung mit zwei unbekannten lässt sich so nicht lösen.

Wenn es eine umkehrfunktion zu mod gäbe wäre es lösbar aber da dessen umkehrfunktion immer das unbekannte k verlangt ist das nicht möglich.

Sag wenn du die lösung weist, würde mich sehr interessieren.

 

[Frank]

danke, ich habe die lösung mittlerweile gefunden
man muss mit dem Euklidischen Algorithmus arbeiten, dann rn = r(n-2)+(-qn-1)*rn-1
dann hat man rn ggT(a,b)

und dadurch kommt man später iwann auf

x = 1^k * M mod p*q



Hatte zum glück jemand in meiner ICQ der Mathe studiert. Hab zwar nix davon verstanden, aber ausrechnen kann ichs jetzt ^^