Modulo Gleichung lösen

24.07.2013, 13:23

Tryndamere

Modulo Gleichung lösen

Meine Frage:
Hallo

Ich hoch schon seit ca 3 Stunde an folgendem Problem. (El Gamal Signatur)(Das System meinte ich solle es in Algebra posten ich hätte es doch eher in Sonstiges, bitte verschieben wenn es falsch liegt)

Es gelte folgende Formel:
$\begin{eqnarray*} s= (m-a\lambda)*r^{-1} mod(p-1) \end{eqnarray*}$

p = 53

2 Nachrichten gegeben
die erste
$\begin{eqnarray*} \lambda = 45 s = 49 m = 44 \end{eqnarray*}$
die zweite
$\begin{eqnarray*} \lambda = 45 s = 2 m = 17 \end{eqnarray*}$

Berechnung von a und r

Meine Ideen:
Also Die Annahme das r in beiden Fällen gleich ist, ist korrekt, da lambda den selben wert besitzt und dmait mit dem gleichen r berechnet worden ist.

Die 2 Gleichungen:
$\begin{eqnarray*} 49 = (44-45a)*r^{-1} mod 52 \end{eqnarray*}$
$\begin{eqnarray*} 2 = (17- 45a)*r^{-1} mod 52 \end{eqnarray*}$

Mein Ansatz wäre gewesen:

eine Gleichung nach r umzustellen und r einzusetzen und a zu berechnen.

Das Problem ist, dass am Ende einfach Kommawerte rauskommen und ich leider nicht verstehe wie ich das mod 52 "umkehre"

24.07.2013, 13:46

tryndamere

Auf diesen Beitrag antworten »

Kann es sein,

das für r = 59589 rauskommt?

ich habe nun umgestellt nach r

also $\begin{eqnarray*} r=\frac{27}{2207} mod 52 \end{eqnarray*}$

und mit "probieren" gelöst

Solange r keine gerade Zahl ist

$\begin{eqnarray*} r=\frac{(k*52+1)*2207}{27} \end{eqnarray*}$
k++

stimmt der weg?

24.07.2013, 14:06

tryndamere

Auf diesen Beitrag antworten »

ok langsam bin ich am verzweifeln ...

Wolfram meint es kommt 17 raus
(wegen url beschränkung wolframalpher selebr aufrufen und den input selber hinachen)
/input/?i=49%3D%2844-17-2x%29%2F%2845x%29+mod52

danach habe ich nochmal gerechnet und habe ienen Fehler beim umstellen gefunden

und folgendes für r gefunden

$\begin{eqnarray*} r=\frac{27}{49}mod52 \end{eqnarray*}$

und nach dem Schema ausgerechnet und es kommt 1269 raus.

Also ich brauch wirklich dringend mal einen Ansatz ... :<

24.07.2013, 14:34

tryndamere

Auf diesen Beitrag antworten »

Und noch einmal einen schritt weiter

a= 8
r=5

scheinen ja vernünftige Lösungen zu sein, wenn ich das aber durchteste

d.h. annehme s sei unbekannt und a,r einsetze kommt nicht das gesuchte s raus

24.07.2013, 14:36

HAL 9000

Auf diesen Beitrag antworten »

r=5 ist richtig, auch wenn ich deine Rechnungen reichlich abenteuerlich finde. a=8 ist jedenfalls falsch.

Zitat:

Original von Tryndamere
$\begin{eqnarray*} 49 = (44-45a)*r^{-1} mod 52 \end{eqnarray*}$
$\begin{eqnarray*} 2 = (17- 45a)*r^{-1} mod 52 \end{eqnarray*}$

Subtraktion ergibt

$\begin{eqnarray*} 47 \equiv 27 r^{-1} \bmod 52 \end{eqnarray*}$ ,

also

$\begin{eqnarray*} r \equiv 27\cdot 47^{-1} \equiv 27\cdot (-21) = -567 \equiv 5\bmod 52 \end{eqnarray*}$

Dies eingesetzt in die erste Gleichung erhält man

$\begin{eqnarray*} 45a = 44-49r \equiv -201 \equiv 7\bmod 52 \end{eqnarray*}$

$\begin{eqnarray*} a \equiv -1\bmod 52 \end{eqnarray*}$ .

24.07.2013, 14:56

tryndamere

Auf diesen Beitrag antworten »

Ja das ganze ist vl. etwas kaotisch, da ich nie gelernt habe wie man in moduloräumen rechnet.
Ich bin halt auch "nur" Informatiker und versuche mir halt alles über Algorithmen beizubringen.

Zitat:

Original von HAL 9000
$\begin{eqnarray*} r \equiv 27\cdot 47^{-1} \equiv 27\cdot (-21) = -567 \equiv 5\bmod 52 \end{eqnarray*}$

Den 2. schritt verstehe ich ehrlich gesgat nicht
$\begin{eqnarray*} 27\cdot 47^{-1} \equiv 27\cdot (-21) \end{eqnarray*}$

Wie kommt man auf so etwas? bloßes Hinsehen? Und wenn ja woran erkennt man es.

Und bei negativen werten wird dann anscheinend das negativ einfach weggelassen also im Beispiel

- 567 zu 567 und der daraus entstehende Wert vom modulo Operanden abgezogen

also im Beispiel 567 mod 52 = 47
52-47 = 5.

Habe ich das so richtig verstanden?

Zitat:

Original von HAL 9000
$\begin{eqnarray*} a \equiv -1\bmod 52 \end{eqnarray*}$ .

Und die Zeile verstehe ich auch nicht.

Ich dachte 7 sei nun mein a oder was übersehe ich gerade?

LG

24.07.2013, 15:16

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von tryndamere
Ja das ganze ist vl. etwas kaotisch, da ich nie gelernt habe wie man in moduloräumen rechnet.

Sowas hab ich schon geahnt und befürchtet, und leider schon sehr oft hier im Board beobachtet. Für mich ist es ein Unding, solche Verschlüsselungsalgorithmen (RSA, etc.) durchgehen zu wollen, ohne die notwendigen Grundlagen der Modulorechnung zu beherrschen. Das kann irgendwie nicht lange gutgehen. unglücklich

Zitat:

Original von tryndamere
Den 2. schritt verstehe ich ehrlich gesgat nicht
$\begin{eqnarray*} 27\cdot 47^{-1} \equiv 27\cdot (-21) \end{eqnarray*}$

Wie kommt man auf so etwas? bloßes Hinsehen? Und wenn ja woran erkennt man es.

Naja, z.B. ergibt der "Erweiterte Euklidische Algorithmus" (EEA)

$\begin{eqnarray*} 1 = 19\cdot 52 - 21\cdot 47 \end{eqnarray*}$ ,

was $\begin{eqnarray*} 1\equiv (-21)\cdot 47 \bmod 52 \end{eqnarray*}$ zur Folge hat, was ja nichts anderes ist als $\begin{eqnarray*} 47^{-1}\equiv -21\bmod 52 \end{eqnarray*}$ .

Zitat:

Original von tryndamere

Zitat:

Original von HAL 9000
$\begin{eqnarray*} a \equiv -1\bmod 52 \end{eqnarray*}$ .

Und die Zeile verstehe ich auch nicht.

Ich dachte 7 sei nun mein a oder was übersehe ich gerade?

Nein, wir waren bei $\begin{eqnarray*} 45a\equiv 7\bmod 52 \end{eqnarray*}$ . Und da $\begin{eqnarray*} 45\equiv -7\bmod 52 \end{eqnarray*}$ , ergibt sich $\begin{eqnarray*} -7a\equiv 7\bmod 52 \end{eqnarray*}$ , was dann offensichtlich zur Lösung $\begin{eqnarray*} a\equiv -1\bmod 52 \end{eqnarray*}$ führt.

Fazit: Du solltest dir unbedingt die Theorie und Beispiele zum Lösen einfacher linearer Kongruenzen $\begin{eqnarray*} ax\equiv b\bmod m \end{eqnarray*}$ mal ansehen, u.a. auch die Berechnung der Inversen $\begin{eqnarray*} a^{-1}\bmod m \end{eqnarray*}$ (so denn existent) per EEA. Ansonsten wird das für dich das blanke Stochern im Nebel.

24.07.2013, 15:59

tryndamere

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
was dann offensichtlich zur Lösung $\begin{eqnarray*} a\equiv -1\bmod 52 \end{eqnarray*}$ führt.

Das Problem ist nur das a = -1 keine Gültige Lösung ist, da per Definition des ElGamal

0 < a < p-2

D.h. es muss ein weiteres a geben für das es gilt das führt mich aber zur Frage, wenn es 2 Lösungen gibt, gibt es dann überhaupt eine eindeutige Lösung?

Zitat:

Original von HAL 9000
Fazit: Du solltest dir unbedingt die Theorie und Beispiele zum Lösen einfacher linearer Kongruenzen $\begin{eqnarray*} ax\equiv b\bmod m \end{eqnarray*}$ mal ansehen, u.a. auch die Berechnung der Inversen $\begin{eqnarray*} a^{-1}\bmod m \end{eqnarray*}$ (so denn existent) per EEA. Ansonsten wird das für dich das blanke Stochern im Nebel.

Hast du vl zufällig iwelche Seiten die das schön erklären mit Beispielen außer Wikipedia?

Naja HAL programmiertechnisch sit das ein klacks für mich zum umsetzen, bloß leider besitze ich in de rPrüfung kein python oder ähnliches zum lösen, ich finde es auch nicht gerade rosig ohne Vorkenntnisse da reingeworfen zu werden. Aber es wird halterwartet das wir das uns selbst anlernen. :-(

Wie gesagt deshalb habe ich mir schon die "kaotische" Lösung erarbeitet mit der Schleife. Da mien TR schnell Tabellen erzeugen kann, ist das ein durchscrollen der Liste, wobei mir die reguläre Lösung besser gefällt, da die auch ohne TR funktioniert.

Danke für deine Hilfe
LG

24.07.2013, 16:04

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von tryndamere
Das Problem ist nur das a = -1 keine Gültige Lösung ist, da per Definition des ElGamal

0 < a < p-2

D.h. es muss ein weiteres a geben

Nicht für dieses obige Gleichungssystem: Es gibt nur die eine Lösung

$\begin{eqnarray*} a\equiv -1 \equiv 51 \bmod 52 \end{eqnarray*}$ ,

wenn du denn unbedingt einen positiven Repräsentanten brauchst. Aber mit deinem $\begin{eqnarray*} p=53 \end{eqnarray*}$ ist damit $\begin{eqnarray*} a=p-2 \end{eqnarray*}$ , erfüllt also nicht deine Bedingung $\begin{eqnarray*} 0 < a < p-2 \end{eqnarray*}$ .

Diese Eindeutigkeit müsstest du auch erkennen, wenn, ja wenn das Vorwissen über $\begin{eqnarray*} ax\equiv b\bmod m \end{eqnarray*}$ denn da wäre...

24.07.2013, 16:21

tryndamere

Auf diesen Beitrag antworten »

ah entschuldigung der Raum ist nicht p-2 sondern p-1 (hatte ich gerade falsch im Kopf)

a element {1,...,p-2}: also ist 51 die exakte Lösung.

Ich bin bloß auch gerade glücklich das ich zur Not meine Algolösung habe die zwar nicht schön ist aber funktioniert und keinen Mehrauffwand für mich bedeutet.

Ich muss schließlich auch die Zeitsparenste Lösung finden.

Ich werde mir einmal die von dir angesprochenen Punkte anschauen und hoffentlich schnell verstehen.

Danke für deine Hilfe und Nerven.

MfG

25.07.2013, 11:03

RavenOnJ

Auf diesen Beitrag antworten »

Was nützt dir eine algorithmische Lösung, wenn du gar nicht verstehst, warum die Lösung eine Lösung ist? Natürlich kann man sehr einfach einen Brute-Force-Algo finden, der zumindest für kleine Zahlen eine Lösung findet. Das bringt dich nur im Verständnis überhaupt nicht weiter.

Neue Frage »

Antworten »

Modulo Gleichung lösen

Verwandte Themen