Affine Chiffre

26.01.2025, 20:40

Malcang

Affine Chiffre

Da bin ich wieder Big Laugh

Ich beschäftige mich gerade mit dieser Aufgabe:
[attach]58082[/attach]

Nun, affine Chiffre ist ja definiert über die Verschlüsselungsfunktion $\begin{eqnarray*} e( (a,b), m) = am+b \end{eqnarray*}$ . Ich wähle also den Ansatz:
$\begin{eqnarray*} \begin{vmatrix} 100a+b = 208 \\ 176a+b = 164 \end{vmatrix} \Leftrightarrow \begin{vmatrix} 100a + b &= 208 \\ 76a &= 212 \end{vmatrix} \end{eqnarray*}$

Aber nun sind $\begin{eqnarray*} 76 \end{eqnarray*}$ und $\begin{eqnarray*} 212 \end{eqnarray*}$ nicht teilerfremd, wie mache ich denn nun weiter verwirrt

Ich habe das allerdings mit python über Brute-Force lösen können, es kommen die Paare $\begin{eqnarray*} (23, 212), (87, 212), (151, 212), (215,212) \end{eqnarray*}$ in Frage.

Aber wie löse ich das rechnerisch?

27.01.2025, 07:46

HAL 9000

Auf diesen Beitrag antworten »

Wer sagt denn, dass die teilerfremd sein müssen? Die Bedingung für die Lösbarkeit einer Kongruenz $\begin{eqnarray*} ax\equiv b\bmod m \end{eqnarray*}$ ist nicht $\begin{eqnarray*} \operatorname{ggT}(a,b)=1 \end{eqnarray*}$ , sondern $\begin{eqnarray*} \operatorname{ggT}(a,m) \mid b \end{eqnarray*}$ .

In letzterem Fall kann man die Kongruenzgleichung durch den ggT dividieren. Im vorliegenden Fall $\begin{eqnarray*} 76a \equiv 212\bmod 256 \end{eqnarray*}$ ist $\begin{eqnarray*} \operatorname{ggT}(76,256) = 4 \end{eqnarray*}$ und es gilt $\begin{eqnarray*} 4\mid 212 \end{eqnarray*}$ , wir dividieren durch 4 und erhalten $\begin{eqnarray*} 19a \equiv 53\bmod 64 \end{eqnarray*}$ . Diese Kongruenz ist dann eindeutig lösbar $\begin{eqnarray*} a\equiv a_0\bmod 64 \end{eqnarray*}$ , und hat dann modulo 256 genau vier Lösungen zur Folge, und das sind $\begin{eqnarray*} a_0+64k \end{eqnarray*}$ für $\begin{eqnarray*} k=0,1,2,3 \end{eqnarray*}$ .

Zur Zusatzfrage: Der zusätzliche Chiffretext zur 28 bringt keinen zusätzlichen Informationsgewinn. Was man benötigt ist ein Chiffretext zu einem zu 256 teilerfremden Wert, sprich: Der muss ungerade sein.

Allgemein: Zur eindeutigen Bestimmung der Parameter $\begin{eqnarray*} a,b \end{eqnarray*}$ der Chiffre $\begin{eqnarray*} e(x) = ax+b\bmod m \end{eqnarray*}$ genügen zwei Chiffretext-Paare $\begin{eqnarray*} \left(x_1,y_1\right) \end{eqnarray*}$ und $\begin{eqnarray*} \left(x_2,y_2\right) \end{eqnarray*}$ derart, dass $\begin{eqnarray*} x_2-x_1 \end{eqnarray*}$ teilerfremd zu Modul $\begin{eqnarray*} m \end{eqnarray*}$ ist:

Denn dann ist $\begin{eqnarray*} y_2-y_1\equiv a\left(x_2-x_1\right)\bmod m \end{eqnarray*}$ eindeutig nach $\begin{eqnarray*} a \end{eqnarray*}$ auflösbar.

27.01.2025, 17:30

Malcang

Auf diesen Beitrag antworten »

Super, HAL, vielen Dank, das hat mir sehr geholfen! Freude

Zitat:

Original von HAL 9000
Zur Zusatzfrage: Der zusätzliche Chiffretext zur 28 bringt keinen zusätzlichen Informationsgewinn. Was man benötigt ist ein Chiffretext zu einem zu 256 teilerfremden Wert, sprich: Der muss ungerade sein.

Hier hatte ich mich auch verrechnet. Ich hatte die Ergebnisse $\begin{eqnarray*} \pmod{26} \end{eqnarray*}$ statt $\begin{eqnarray*} \pmod{256} \end{eqnarray*}$ betrachtet. Mit der richtigen Betrachtung wäre immer das gleiche herausgekommen und ich ich hätte die Lösung eingesehen.

Deine Argumentation ist mir natürlich viel lieber Big Laugh

28.01.2025, 08:39

HAL 9000

Auf diesen Beitrag antworten »

Allgemein kann man sagen, dass bei bekanntem $\begin{eqnarray*} m \end{eqnarray*}$ zur eindeutigen Bestimmung der Parameter $\begin{eqnarray*} a,b \end{eqnarray*}$ der Chiffre $\begin{eqnarray*} e(x)=ax+b\bmod m \end{eqnarray*}$ zwei Chiffretext-Paare $\begin{eqnarray*} \left(x_1,y_1\right) \end{eqnarray*}$ und $\begin{eqnarray*} \left(x_2,y_2\right) \end{eqnarray*}$ genügen, sofern $\begin{eqnarray*} x_2-x_1 \end{eqnarray*}$ und $\begin{eqnarray*} m \end{eqnarray*}$ teilerfremd sind:

Denn dann ist die durch Subtraktion entstehende Kongruenz $\begin{eqnarray*} a\left(x_2-x_1\right) = y_2-y_1\bmod m \end{eqnarray*}$ eindeutig nach $\begin{eqnarray*} a \end{eqnarray*}$ lösbar, und daraus ableitend $\begin{eqnarray*} b= y_1-ax_1\bmod m \end{eqnarray*}$ ist ohnehin klar.

29.01.2025, 19:18

Malcang

Auf diesen Beitrag antworten »

Das kommt sofort bei meinen Notizen dazu. HAL, ich danke dir vielmals!

06.02.2025, 10:44

Malcang

Auf diesen Beitrag antworten »

HAL, ich muss das hier gerade nochmal rauskramen:

Zitat:

Original von HAL 9000
Wer sagt denn, dass die teilerfremd sein müssen? Die Bedingung für die Lösbarkeit einer Kongruenz $\begin{eqnarray*} ax\equiv b\bmod m \end{eqnarray*}$ ist nicht $\begin{eqnarray*} \operatorname{ggT}(a,b)=1 \end{eqnarray*}$ , sondern $\begin{eqnarray*} \operatorname{ggT}(a,m) \mid b \end{eqnarray*}$ .

Du sagst die Bedingung. Aber wenn $\begin{eqnarray*} \operatorname{ggT}(a,m) = 1 \end{eqnarray*}$ gilt, so ist $\begin{eqnarray*} a \end{eqnarray*}$ invertierbar und die Kongruenz ist ebenfalls lösbar.
Natürlich gilt $\begin{eqnarray*} \operatorname{ggT}(a, m)=1 \Rightarrow \operatorname{ggT}(a, m)|b \end{eqnarray*}$ . Aber wie oben gesehen gilt nicht die Rückrichtung. Wie ist da genau der Zusammenhang? Geht es um die eindeutige Lösbarkeit?

06.02.2025, 11:38

HAL 9000

Auf diesen Beitrag antworten »

Zum einen geht es um $\begin{eqnarray*} \operatorname{ggT}(a,m) \end{eqnarray*}$ statt um $\begin{eqnarray*} \operatorname{ggT}(a,b) \end{eqnarray*}$ - vielleicht hast du dich bei letzterem auch nur verschrieben, jedenfalls hat dieser ggT nun überhaupt keine Bedeutung.

Zum anderen gibt $\begin{eqnarray*} \operatorname{ggT}(a,m) \end{eqnarray*}$ auch gleich die Anzahl der Lösungen dieser Kongruenzgleichung an, sofern wie gesagt $\begin{eqnarray*} \operatorname{ggT}(a,m) \mid b \end{eqnarray*}$ gilt. Gilt es nicht, so ist die Lösungsanzahl natürlich Null.

Im Spezialfall $\begin{eqnarray*} \operatorname{ggT}(a,m)=1 \end{eqnarray*}$ ist die Bedingung natürlich automatisch erfüllt, und es gibt hier genau eine Lösung der Kongruenz.

Im Fall $\begin{eqnarray*} g=\operatorname{ggT}(a,m)>1 \end{eqnarray*}$ kann man so vorgehen, wie ich es oben getan hatte: Division von $\begin{eqnarray*} ax\equiv b\bmod m \end{eqnarray*}$ durch $\begin{eqnarray*} g \end{eqnarray*}$ ergibt Kongruenz $\begin{eqnarray*} a'x\equiv b'\bmod m' \end{eqnarray*}$ mit $\begin{eqnarray*} a'=\frac{a}{g} \end{eqnarray*}$ , $\begin{eqnarray*} b'=\frac{b}{g} \end{eqnarray*}$ und $\begin{eqnarray*} m'=\frac{m}{g} \end{eqnarray*}$ . Hier ist dann $\begin{eqnarray*} \operatorname{ggT}(a',m')=1 \end{eqnarray*}$ , es gibt daher genau eine Lösung $\begin{eqnarray*} x_0\bmod m' \end{eqnarray*}$ , welche dann die genau $\begin{eqnarray*} g \end{eqnarray*}$ Lösungen $\begin{eqnarray*} x_0 + km'\bmod m \end{eqnarray*}$ mit $\begin{eqnarray*} k=0,1,\ldots,g-1 \end{eqnarray*}$ zur Folge hat.

Das war im Schnelldurchlauf die Theorie zu linearen Kongruenzgleichungen in einer Variable (bis auf das eigentliche Finden der Lösung). Augenzwinkern

06.02.2025, 20:02

Malcang

Auf diesen Beitrag antworten »

Wie immer was gelernt, Danke HAL! smile

Neue Frage »

Antworten »

Affine Chiffre

Verwandte Themen