Elgamal-Korrektheit

13.03.2015, 13:44

Dani_ela

Auf diesen Beitrag antworten »

Elgamal-Korrektheit

Hallo

Wink

Meine Aufgabe ist zu beweisen, dass die Elgamal-Verschluesselung korrekt ist.
Korrekt wurde in der Vorlesung wie folgt definiert:
Eine Chiffre ist korrekt, wenn $\begin{eqnarray*} m= D_{k}(E_{k}(m)) \end{eqnarray*}$ wobei m die Nachricht ist, $\begin{eqnarray*} E_{k} \end{eqnarray*}$ die Verschluesselung und $\begin{eqnarray*} D_{k} \end{eqnarray*}$ die Entschluesselung.
Soweit ist mir alles klar.
In einer vorangegangenen Aufagbe haben wir bewiesen, dass die Shift-Cipher korrekt ist.
Dabei hatten wir aber $\begin{eqnarray*} E_{k}(m)=a*m + b mod 26 = c \end{eqnarray*}$ und $\begin{eqnarray*} D_{k}(c)=a^{-1} (c-b) mod 26 \end{eqnarray*}$ gegeben.
Hier haenge ich nun fuer ElGamal.
Denn dadurch dass zwei Personen (Alice und Bob) mit unterschiedlichem Wissenstand beteiligt sind
komme ich nicht drauf wie ich die zwei Funktionen E und D aufstellen soll.

Mein Versuch:
Jeder kennt den oeffentlichen Schluessel (p,g,A) [p ist prim, $\begin{eqnarray*} A=g^{a} mod p \end{eqnarray*}$ , wobei nur Alice klein a kennt]
Bob will eine Nachricht m verschluesseln. Also $\begin{eqnarray*} c=m*k mod p \end{eqnarray*}$ [wobei $\begin{eqnarray*} k=A^{b} mod p \end{eqnarray*}$ und nur Bob kennt klein b].
Hier ist nun der springende Punkt, weil ich eine Funktion fuer die Entschlusselung aufstellen soll und nicht weiss wie...

13.03.2015, 13:49

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

Bob verschickt c und $\begin{eqnarray*} R=g^b \end{eqnarray*}$ .

13.03.2015, 13:53

Dani_ela

Auf diesen Beitrag antworten »

Ok, ich glaub ich bin jetzt drauf gekommen.... ein bisschen bloed, nachdem ich kurz vorher die Frage gestellt hab, aber egal.
Ich wollte jetzt nicht alles loeschen, sondern poste meinen Versuch hier.

Ich habe einfach mal das Problem mit dem unterschiedlichen Wissenstand ignoriert und folgendes bewiesen:

$\begin{eqnarray*} A^{b}=(g^{a})^{b}=g^{ab}=(g^{b})^{a}=B^{a} \end{eqnarray*}$

Damit ergab sich

$\begin{eqnarray*} D_{k}(E_{k}(m))= D_{k}(m*A^{b}) mod p= (m*A^{b}*k^{-1})mod p= (m*A^{b}*(B^{a})^{-1}) mod p= (m*A^{b}*(A^{b})^{-1}) mod p= m mod p \end{eqnarray*}$

Kann ich die Unwissenheit einfach ausser Acht lassen?
Und muss ich fuer g und m irgendwelche Einschraenkungen machen?

LG Dani

13.03.2015, 13:54

Dani_ela

Auf diesen Beitrag antworten »

Hallo Captain Kirk,
danke fuer deine Antwort. Was ist R?

Edit: R ist mein B, richtig?

13.03.2015, 13:58

Shalec

Auf diesen Beitrag antworten »

Hallo Dani_ela,
die Elgamal Verschlüsselung funktioniert ja wie folgt:

Schlüsselerzeugung:
Wähle $\begin{eqnarray*} x\in\mathbb{Z} \end{eqnarray*}$ zufällig, jedoch kleiner als die Ordnung der zyklischen Gruppe, in der du operierst.
Berechne: $\begin{eqnarray*} y=g^x \end{eqnarray*}$ für den Erzeuger g
Der geheime Schlüssel ist: x, der öffentliche: y.
Verschlüsselung
Wähle $\begin{eqnarray*} r\in\mathbb{Z} \end{eqnarray*}$ zufällig
Berechne $\begin{eqnarray*} u=g^r \end{eqnarray*}$ und $\begin{eqnarray*} v=my^r \end{eqnarray*}$
Der Chiffretext ist dann: (u,v)
Entschlüsselung
$\begin{eqnarray*} m=vu^{-x} \end{eqnarray*}$

Die Kommunikationspartner müssen also r nicht kennen. Bob verschlüsselt mit dem öffentlichen Schlüssel und erzeugt einen randomisierten Wert. Alice hingegen kann dies, ohne Kenntnisse von r, entschlüsseln. Die Korrektheit kannst du dann einfach nachrechnen. :-)

Achso: Rechnungen innerhalb der jeweiligen Gruppe.

13.03.2015, 14:02

Dani_ela

Auf diesen Beitrag antworten »

Zitat:

Original von Dani_ela
$\begin{eqnarray*} A^{b}=(g^{a})^{b}=g^{ab}=(g^{b})^{a}=B^{a} \end{eqnarray*}$

Damit ergab sich

$\begin{eqnarray*} D_{k}(E_{k}(m))= D_{k}(m*A^{b}) mod p= (m*A^{b}*k^{-1})mod p= (m*A^{b}*(B^{a})^{-1}) mod p= (m*A^{b}*(A^{b})^{-1}) mod p= m mod p \end{eqnarray*}$

Kann ich die Unwissenheit einfach ausser Acht lassen?
Und muss ich fuer g und m irgendwelche Einschraenkungen machen?

LG Dani

Stimmt das dann so?
Und muss ich Einschraenkungen machen?

Danke fuer deine Hinweise smile

smile

Anzeige

13.03.2015, 14:30

Shalec

Auf diesen Beitrag antworten »

Deine Verschlüsselung beruht also darauf, dass du den öffentlichen Schlüssel des jeweils anderen nutzt und diesen mit dem privaten Schlüssel potenzierst. (erste Zeile). Dies kann man so machen. Frage ist hier dann nach der Sicherheit berechtigt :-) (Ist es noch von einer echt zufälligen Ziffernfolge nicht unterscheidbar?) Auch könnte es ja sein, dass Alice egtl. Eva ist und zufällig einen effektiven Algorithmus mit signifikanter Wahrscheinlichkeit nutzen kann, womit Eva eine Fälschung für den öffentlichen Schlüssel erzeugt. Dann kann die gemeine Eva den privaten Schlüssel von Bob in Erfahrung bringen.

Unabhängig davon:

Wenn A und B nicht =0 sind, dann sind deine Berechnungen korrekt. (Man vermeidet diesen Fall allerdings..)

Besser wäre aber folgendes:
Voraussetzung: Beide kennen die Gruppe, in der verschlüsselt wird. Also den Erzeuger g und die Ordnung. Sonst wird es schwierig eine sichere Verschlüsselung zu bewerkstelligen.

Alice veröffentlicht ihren öffentlichen Schlüssel A und hält den Privaten "a" geheim.
Bob möchte mit Alice kommunizieren und verschlüsselt: $\begin{eqnarray*} E_r(m)=(g^r,m*A^r)=c \end{eqnarray*}$ wobei r eine echt zufällige ganze Zahl beliebiger Größe ist.
Alice entschlüsselt dann: $\begin{eqnarray*} D_a(c)=mA^r\cdot \left(g^r\right)^{-a} = m\cdot g^{a\cdot r}\cdot g^{-r\cdot a} = m \end{eqnarray*}$

Ohne die zufällige Zahl r zu kennen.

Wie wurde denn bei euch die ElGamal Verschlüsselung eingeführt?

13.03.2015, 14:51

Captain Kirk

Auf diesen Beitrag antworten »

@Dani_ela

Zitat:

Stimmt das dann so?
Und muss ich Einschraenkungen machen?

- Ja, wobei die Formulierung des ganzen noch durchaus ausbaufähg ist.
- Nein.

@shalec:

Zitat:

Original von Shalec
Deine Verschlüsselung beruht also darauf, dass du den öffentlichen Schlüssel des jeweils anderen nutzt und diesen mit dem privaten Schlüssel potenzierst. (erste Zeile). Dies kann man so machen.

Ja, und nennt sich dann ElGammal-Verschlüsselungsverfahren.

Zitat:

Frage ist hier dann nach der Sicherheit berechtigt :-) (Ist es noch von einer echt zufälligen Ziffernfolge nicht unterscheidbar?) Auch könnte es ja sein, dass Alice egtl. Eva ist und zufällig einen effektiven Algorithmus mit signifikanter Wahrscheinlichkeit nutzen kann, womit Eva eine Fälschung für den öffentlichen Schlüssel erzeugt. Dann kann die gemeine Eva den privaten Schlüssel von Bob in Erfahrung bringen.

was hat das mit der Fragsetellung hier zu tun? Oder auch nur mit dem ElGammal-Verfahren?

Zitat:

Wenn A und B nicht =0 sind, dann sind deine Berechnungen korrekt. (Man vermeidet diesen Fall allerdings..)

Dieser Fall kann nicht eintreten, dann die betrachtest ein multiplikativ geschriebene Gruppe. Da gibt's kein 0.

Zitat:

Besser wäre aber folgendes:
Voraussetzung: Beide kennen die Gruppe, in der verschlüsselt wird. Also den Erzeuger g und die Ordnung. Sonst wird es schwierig eine sichere Verschlüsselung zu bewerkstelligen.

Dazu um Eröffnungspost:

Zitat:

Jeder kennt den oeffentlichen Schluessel (p,g,A)

was wohl heißt: Die Gruppe ist $\begin{eqnarray*} (\mathbb Z / p \mathbb Z )^* \end{eqnarray*}$ mit Erzeuger g.
Das heißt was du als besser forderst ist bereits da.

13.03.2015, 15:02

Shalec

Auf diesen Beitrag antworten »

Zitat:

Original von Captain Kirk

Zitat:

Original von Shalec
Deine Verschlüsselung beruht also darauf, dass du den öffentlichen Schlüssel des jeweils anderen nutzt und diesen mit dem privaten Schlüssel potenzierst. (erste Zeile). Dies kann man so machen.

Ja, und nennt sich dann ElGammal-Verschlüsselungsverfahren.

So habe ich es noch nie gesehen. Vermutlich weil es so Probleme bietet? Nochmal deutlich: Die Verschlüsselung nutzt A und B. Außerdem den geheimen Schlüssel von Bob und Alice, wie es Dani_ela notiert hatte.

Siehe: Wikipedia dort ist auch die mir bekannte Version veröffentlicht.

Zitat:

Original von Captain Kirk

Zitat:

Frage ist hier dann nach der Sicherheit berechtigt :-) (Ist es noch von einer echt zufälligen Ziffernfolge nicht unterscheidbar?) Auch könnte es ja sein, dass Alice egtl. Eva ist und zufällig einen effektiven Algorithmus mit signifikanter Wahrscheinlichkeit nutzen kann, womit Eva eine Fälschung für den öffentlichen Schlüssel erzeugt. Dann kann die gemeine Eva den privaten Schlüssel von Bob in Erfahrung bringen.

was hat das mit der Fragsetellung hier zu tun? Oder auch nur mit dem ElGammal-Verfahren?

Mit der Fragestellung soweit nichts. Man sollte nur stets die Sicherheit mit beachten. (Schon von Anfang an im Auge behalten und entsprechende kognitive Bahnen bilden. Alles hinterfragen.) Es sollten nur Hinweise auf Problemstellen sein. :-)

Zitat:

Original von Captain Kirk

Zitat:

Wenn A und B nicht =0 sind, dann sind deine Berechnungen korrekt. (Man vermeidet diesen Fall allerdings..)

Dieser Fall kann nicht eintreten, dann die betrachtest ein multiplikativ geschriebene Gruppe. Da gibt's kein 0.

Genau. Daher "Man vermeidet diesen Fall allerdings". Ich hätte mir das natürlich auch sparen können Big Laugh

Big Laugh

Zitat:

Original von Captain Kirk

Zitat:

Besser wäre aber folgendes:
Voraussetzung: Beide kennen die Gruppe, in der verschlüsselt wird. Also den Erzeuger g und die Ordnung. Sonst wird es schwierig eine sichere Verschlüsselung zu bewerkstelligen.

Dazu um Eröffnungspost:

Zitat:

Jeder kennt den oeffentlichen Schluessel (p,g,A)

was wohl heißt: Die Gruppe ist $\begin{eqnarray*} (\mathbb Z / p \mathbb Z )^* \end{eqnarray*}$ mit Erzeuger g.
Das heißt was du als besser forderst ist bereits da.

Ah. Gut, wenn das gegeben ist, dann sind meine Forderungen egal.

Im großen und ganzen würde es aber funktionieren. :-)

Wink

Wink

13.03.2015, 15:03

Shalec

Auf diesen Beitrag antworten »

doppelpost..

13.03.2015, 15:20

Dani_ela

Auf diesen Beitrag antworten »

Zitat:

Original von Captain Kirk
was wohl heißt: Die Gruppe ist $\begin{eqnarray*} (\mathbb Z / p \mathbb Z )^* \end{eqnarray*}$ mit Erzeuger g.
Das heißt was du als besser forderst ist bereits da.

Meint die Notation $\begin{eqnarray*} (\mathbb Z / p \mathbb Z )^* \end{eqnarray*}$ und $\begin{eqnarray*} (\mathbb Z_{p} )^\times \end{eqnarray*}$ das gleiche? Das zweite ist die Notaton, die ich in meinem Skript gefunden habe.

13.03.2015, 15:24

Captain Kirk

Auf diesen Beitrag antworten »

Ja.
Ich verwende die zweite Notation allerdings nie, da sie sich mit einer Notation aus der Zahlentheorie überschneidet.
de.wikipedia.org/wiki/P-adische_Zahl#Algebraische_Konstruktion

13.03.2015, 15:30

Dani_ela

Auf diesen Beitrag antworten »

Ok. Koennte daran liegen dass ich im Ausland bin, moeglicherweise ist diese Notation hier gebraeuchlicher.
Danke fuer eure Erklaerungen.

13.03.2015, 15:36

Dani_ela

Auf diesen Beitrag antworten »

Nochmal zu moeglichen Einschraenkungen:

Ich hab die Befuerchtung, wenn ausdruecklich gefragt wird
"Do you need any restrictions on the generator g or the message m?"
dass es Einschraenkungen gibt verwirrt

verwirrt

Habt ihr ne Idee was gemeint sein koennte?

13.03.2015, 15:43

Captain Kirk

Auf diesen Beitrag antworten »

p darf kein Teiler von m sein.

Ansonsten lassen sich solche potentiell sehr spitzfindigen Sachen ohne die exakte Aufgabenstellung und u.U. sogar Vereinbarungen aus der Vorlesung nur schwer beantworten.

13.03.2015, 15:48

Dani_ela

Auf diesen Beitrag antworten »

Ok, danke.
Ja, das verstehe ich.

Fuer solche potentiell sehr spitzfindigen Sachen gibt es Gott seiu Dank dann auch nicht so viele Punkte Big Laugh

Big Laugh

.

13.03.2015, 16:02

Shalec

Auf diesen Beitrag antworten »

Zitat:

Original von Dani_ela
Ok. Koennte daran liegen dass ich im Ausland bin, moeglicherweise ist diese Notation hier gebraeuchlicher.

Es ist sogar tatsächlich so, dass es innerhalb Deutschlands an verschiedenen Unis entsprechende Unterschiede in der Notation gibt.

Aber ich denke, dass fast alle Zahlentheoretiker, aus dem Grund von Captain Kirk, die erste Notation bevorzugen. Den Algebraikern (die, die ich kenne jedenfalls) scheint die zweite mehr zu liegen. Es tritt wohl gleichermaßen häufig auf. (Ist mir persönlich so aufgefallen. Die Zahlentheoretiker nutzen erstere Notation.)

Kennst du den kleinen Satz von Fermat? Oder den Satz von Euler? Darüber könnten dir noch mehr Forderungen auffallen. (Bzw. spezielle Konstruktionsmerkmale bewusst werden). Wenn euer Skript oder das Aufgabenblatt entsprechendes zulassen könnte. Also hier wirklich nochmal nachlesen. Möglicherweise bringen dir die drei Inhalte auch nichts. :-)

[Diese werden dir übrigens auch Informationen über den RSA liefern. (Ausblick: $\begin{eqnarray*} \exists k\ s.d.\ m^{(e^k)} \equiv m\ mod\ n \end{eqnarray*}$ )]

@Captain Kirk: Ich wollte nun schon mindestens 2 Beiträge von dir mit "gefällt mir" kennzeichnen. Das Forum kann da ruhig mal nachrüsten. Big Laugh

Big Laugh

13.03.2015, 16:10

Dani_ela

Auf diesen Beitrag antworten »

Zitat:

Original von Shalec

@Captain Kirk: Ich wollte nun schon mindestens 2 Beiträge von dir mit "gefällt mir" kennzeichnen. Das Forum kann da ruhig mal nachrüsten. Big Laugh

Big Laugh

Gefaellt mir Big Laugh

Big Laugh

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »