Public-Key Verschlüsselung

Question

Aufgabe:

Sei die natürliche Zahl g das Geheimnis, und seien p_A, p_B zwei Primzahlen, so dass g ∈ {0, 1, . . . , p_Ap_B − 1} gilt. Die Primzahlen p_A, p_B sind öffentlich bekannt. Adelheid erhält das Teilgeheimnis r_A = g mod p_A, und
Berta erfährt r_B = g mod p_B. Zeige, dass Adelheid und Berta das
Geheimnis nur zusammen entschlüsseln können.

a) Zusammen berechnen Adelheid und Berta Zahlen a und b mit ap_A + bp_B = 1.
Wie können Adelheid und Berta das machen?

(c) Zeige, dass dann g' = r_Abp_B + r_Bap_A eine Lösung ist, also g' ≡ r_A mod p_A und g' ≡ r_B mod p_B gilt.

Problem/Ansatz:

a) Hätte ich über den erweiterten euklidischen Algorithmus erklärt

b) Hier weiß ich leider nicht mehr weiter und würde gern um Rat bitten. Was muss ich hier konkret zeigen, bzw. wie gehe ich vor? Hilfestellungen wären super.

Danke!

Answer 1

(a) Adelheid und Berta können Zahlen a und b mit apA + bpB = 1 durch den erweiterten euklidischen Algorithmus berechnen. Dieser Algorithmus gibt die Werte von a und b zurück, die die Gleichung apA + bpB = ggT(pA, pB) erfüllen, wobei ggT(pA, pB) der größte gemeinsame Teiler von pA und pB ist. Da pA und pB als Primzahlen teilerfremd sind, ist ihr ggT gleich 1, und es gibt immer Zahlen a und b, die die Gleichung erfüllen. Adelheid und Berta können diese Zahlen dann durch Multiplikation mit g zu apA + bpB = g lösen.

(c) Wir wollen zeigen, dass g' ≡ rA mod pA und g' ≡ rB mod pB gilt. Wir beginnen mit der ersten Kongruenz g' ≡ rA mod pA. Da apA + bpB = 1 gilt, können wir b = (1 - apA)/pB setzen. Dann haben wir

g' = rAbpB + rBapA
= rA(1 - apA) + rBapA
= rA - rAapA + rBapA
= rA(1 - apA) + rBapA
≡ rA(1 - apA) mod pA

Da rA = g mod pA, können wir dies in die vorherige Kongruenz einsetzen, um

g' ≡ g(1 - apA) mod pA

zu erhalten. Da pA eine Primzahl ist, ist g durch g(1 - apA) modulo pA eindeutig bestimmt. Wir wissen auch, dass g' ≡ rA mod pA, also muss g' = g(1 - apA) + kpA für einige k ∈ ℤ sein. Da 0 ≤ g < pApB und 0 ≤ g(1 - apA) < pA, ist 0 ≤ kpA < pApB. Da pA und pB als Primzahlen teilerfremd sind, ist kpA + lpB = 1 für einige l ∈ ℤ. Wir können dies in die obige Gleichung einsetzen, um

g' = g(1 - apA) + kpA
= g(1 - apA) + lpBpA
= g(1 - apA) + l(pApB)
≡ g mod pApB

Da g ∈ {0, 1, . . . , pApB − 1} ist, ist g' ≡ g mod pApB und daher auch g' ≡ rA mod pA erfüllt.

Der Beweis für die zweite Kongruenz g' ≡ rB mod pB ist analog, und daher haben wir gezeigt, dass g' eine Lösung des Systems von Kongruenzen ist und damit das Geheimnis g ist.