Wie kann der Angreifer nun aus Kenntnis von x1, x2, y1, y2 den geheimen Schlüssel(t, e) ermitteln?

Question

Aufgabe:

Frage zur Chosen Plaintext Attack:

affine Chiffre:
y = (t · x + e) mod n

Problem/Ansatz:

Angenommen ein Angreifer kann Alice dazu bringenm zwei von ihm gewählte Klartextbuchstaben x1, x2 zu verschlüsseln und ihm die entstandenen Geheimtextbuchstaben y1 bzw. y2
zu nennen. Wie kann der Angreifer nun aus Kenntnis von x1, x2, y1, y2 den geheimen Schlüssel(t, e) ermitteln?

& woruaf müsste der Angreifer achten, wenn er x1 und x2 auswählt?

Answer 1

Du erhältst also folgendes Gleichungssystem
\( \left\{\begin{array}{l} y_{1} \equiv_{n} t x_{1}+e \\ y_{2} \equiv_{n} t x_{2}+e \end{array} \quad \Longrightarrow y_{1}-y_{2} \equiv_{n} t\left(x_{1}-x_{2}\right)\right. \)
Jetzt musst du also lediglich das modulare Inverse von \( x_{1}-x_{2} \) in \( \mathbb{Z}_{n} \) berechnen. Dieses existiert genau dann, wenn \( \operatorname{gcd}\left(n, x_{1}-x_{2}\right)=1 \), was dir schonmal ein Kriterium gibt, wie du \(\ x_{1} \) und \( x_{2} \) wählen solltest. Damit haben wir schonmal \( t \) gefunden, wobei nun \( e \) durch
\( e=y_{2}-t x_{2} \)
gegeben ist.