Schrittfolge von Algorithmen

Question 1

Schrittfolge ElGamal Algorithmus

Answer 1

1. Alice generiert eine zufällige Zahl
2. Alice generiert den Schlüssel A = g^a mod p
3. Alice berechnet das Chiffrate C = B^a * m mod p = (g^b)^a * m mod p = g^a * b * m mod p = A^b * m mod p
4. Alice sendet eine Nachricht(A,C) an Bob
5. Bob entschlüsselt die Nachricht mit A^-b * C = (g^a)^-b * (g^a * b * m) = g^-a * b + a * b * m = g^0 * m = 1 * m = m

Question 2

Schrittfolge ElGamal Signatur

Answer 2

1. Alice generiert eine Zufallszahl k mit 0 < k < p-1 und k und p-1 sind teilerfremd
2. Alice berechnet r = g^k mod p
3. Es gilt also a * r + s * k = H(M) mod (p-1)
4. Alice schickt m zusammen mit der Signatur (r,s) an Bob
5. Bob überprüft nun ob 0 < r < p, 0 < s < p-1 und g^H(m) = g^a * r + s * k = g^a * r * g^s * k = (g^k)^r * (g^k)^s = A^r * r^s mod p

Question 3

Schrittfolge Shamir’s No-Key Algorithmus

Answer 3

1. Alice wählt einen geheimen Verschlüsselungsschlüssel s und den dazugehörigen geheimen Entschlüsselungsschlüssel t. Sie verschlüsselt die Nachricht m und schickt das Chiffrat E(s,m) an Bob.
2. Bob wählt einen geheimen Verschlüsselungsschlüssel p und den dazugehörigen geheimen Entschlüsselungsschlüssel q. Er verschlüsselt die Nachricht empfangene Nachricht erneut und schickt das Ergebnis E(p,E(s,m)) zu Alice.
3. Alice nimmt die empfangene Nachricht und entschlüsselt diese mit ihrem Entschlüsselungsschlüssel t. Sie sendet das Ergebnis D(t, E(p,E(s,m))) = E(p,m) an Bob.
4. Bob entschlüsselt die empfangene Nachricht mit seinem Entschlüsselungsschlüssel q und erhält den Klartext D(q,E(p,m)) = m.

Question 4

Schrittfolge Massey-Omura Algorithmus

Answer 4

1. Alice und Bob einigen sich auf eine Primzahl p. Alice wählt eA und dA und Bob wählt eB und dB, so dass eA * dA mod (p-1) = 1 und eB * dB mod(p-1) = 1
2. Alice verschlüsselt die Nachricht m und sendet das Ergebnis m^eA mod p an Bob
3. Bob verschlüsselt die empfangene Nachricht erneut und sendet das Ergebnis m^eA * eB mod p an Alice.
4. Alice entschlüsselt die empfangene Nachricht und sendet das Ergebnis m^(eA * eB * dA) = m^eB mod p an Bob.
5. Bob entschlüsselt die empfangene Nachricht und erhält den Klartext m^eB * dB mod p = m^1 mod p = m

Question 5

Schrittfolge zu Fiat-Shamir-Zero-Knowledge Protokoll

Answer 5

1. Eine vertrauenswürdige dritte Partei wählt RSA-Modul n = p * q für zwei große Primzahlen p und q
2. Alice wählt eine geheime Zahl s (teilerfremd zu n), berechnet s * q = s^2 mod n und registriert s * q als “öffentlichen Schlüssel” bei der dritten Partei.
3. Alice wählt eine Zufallszahl r, berechnet r * q = r^2 mod n und sendet r * q an Bob.
4. Bob wählt e aus {0,1} und sendet es an Alice.
5. Alice berechnet y = r * s^e mod n und sendet das Ergebnis zurück. (Nur Alice kann s kennen, denn s kann nicht einfach aus sq berechnet werden).
6. Bob überprüft, ob y^2 = (r * s^e)^2 = rq * sq^e mod n gilt.