Modulo < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 13:49 Sa 30.05.2009 | | Autor: | uecki |
Hallo,
ich lerne gerade für Kryptographie und habe folgendes:
Ich habe die Verschlüsselungsfunktion [mm] f_{a,b}(x)=a*x+b [/mm] wobei 0 [mm] \le [/mm] a,b [mm] \le [/mm] 255 und a ungerade wegen der Bijektivität sein soll.
Erste Frage: Warum muss a dafür ungerade sein?
Weiter gehts:
Nun habe ich zwei folgende Verschlüsselungsfunktionen angegeben:
[mm] f_{a,b}(32)=159, f_{a,b}(101)=74.
[/mm]
Als Lösung habe ich da schon stehen, dass a=47 und b=191 ergibt.
Und da komme ich überhaupt nicht drauf.
Ich habe mir das folgendermaßen gedacht:
1. Aufstellen der beiden Gleichungen:
32*a + b= 159
101*a + b= 74
Danach habe ich dann eine von der anderen abgezogen, sodass ich nur noch eine Gleichung habe:
69*a=-85
Und ab hier weiß ich nicht mehr weiter. Wenn ich die -85 modulo 256 rechne kommt auf der rechten Seite 171 raus. Und 171/69 ist nicht 47....
Hoffe mir kann da jemand helfen. Danke schon mal 
LG Uecki
|
|
| |
|
Hallo Uecki,
> Hallo,
>
> ich lerne gerade für Kryptographie und habe folgendes:
>
> Ich habe die Verschlüsselungsfunktion [mm]f_{a,b}(x)=a*x+b[/mm]
> wobei 0 [mm]\le[/mm] a,b [mm]\le[/mm] 255 und a ungerade wegen der
> Bijektivität sein soll.
>
> Erste Frage: Warum muss a dafür ungerade sein?
>
> Weiter gehts:
> Nun habe ich zwei folgende Verschlüsselungsfunktionen
> angegeben:
> [mm]f_{a,b}(32)=159, f_{a,b}(101)=74.[/mm]
> Als Lösung habe ich da
> schon stehen, dass a=47 und b=191 ergibt.
> Und da komme ich überhaupt nicht drauf.
>
> Ich habe mir das folgendermaßen gedacht:
> 1. Aufstellen der beiden Gleichungen:
> 32*a + b= 159
> 101*a + b= 74
> Danach habe ich dann eine von der anderen abgezogen,
> sodass ich nur noch eine Gleichung habe:
> 69*a=-85
> Und ab hier weiß ich nicht mehr weiter. Wenn ich die -85
> modulo 256 rechne kommt auf der rechten Seite 171 raus. Und
> 171/69 ist nicht 47....
Doch, ist es : [mm] 171/69 \equiv (2*69+33) /69 \equiv 2+(11/23) \pmod{256}[/mm]; nun ist ja [mm]253=11*23 \equiv -3 \pmod{256}[/mm], anders gesagt [/mm] 11 [mm] \equiv [/mm] -3/23 [mm] \pmod{256}[/mm]. [/mm] Wenn Du das benutzt (oder mit einem geeigneten Vielfachen von 256 weiterrechnest, oder mit dem Erw. Euklidischen Algorithmus...), kommts raus: Ich habs sowohl von Hand als auch mit 'em CAS nachgerechnet. (Andererseits: Wird in der Aufgabe ... verlangt, das die Lösung ohne Hilfe eines Computers/Taschenrechners bestimmt werden soll > ?).
Gruß
zahlenspieler
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:42 Mi 03.06.2009 | | Autor: | uecki |
Hey,
danke schon mal.
Allerdings verstehe ich das nicht so ganz...
171/69 [mm] \equiv (2\cdot{}69+33) [/mm] /69
das verstehe ich, aber wozu braucht man dann:
[mm] \equiv [/mm] 2+(11/23) [mm] \pmod{256} [/mm] ?
Das ist doch das gleich wie vorher.
Und warum aufeinmal $ [mm] 253=11\cdot{}23 \equiv [/mm] -3 [mm] \pmod{256} [/mm] $ und 11 $ [mm] \equiv [/mm] $ -3/23 $ [mm] \pmod{256} [/mm] $ ???
Also wie du siehst hab ich es garnicht verstanden...Sorry.
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:51 Mi 03.06.2009 | | Autor: | abakus |
> Hey,
>
> danke schon mal.
> Allerdings verstehe ich das nicht so ganz...
> 171/69 [mm]\equiv (2\cdot{}69+33)[/mm] /69
> das verstehe ich, aber wozu braucht man dann:
> [mm]\equiv[/mm] 2+(11/23) [mm]\pmod{256}[/mm] ?
> Das ist doch das gleich wie vorher.
>
> Und warum aufeinmal [mm]253=11\cdot{}23 \equiv -3 \pmod{256}[/mm]
> und 11 [mm]\equiv[/mm] -3/23 [mm]\pmod{256}[/mm] ???
Hallo,
[mm] 253\equiv [/mm] -3 mod 256 gilt offensichtlich.
Da sich 253 als Produkt 11*23 darstellen lässt, kann man also auch
[mm] 11*23\equiv [/mm] -3 mod 256 schreiben.
Das wurde im nächsten Schritt durch 23 geteilt.
Gruß Abakus
> Also wie du siehst hab ich es garnicht
> verstanden...Sorry.
> LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:00 Mi 03.06.2009 | | Autor: | uecki |
Ja Ok. Danke.
Aber wie komme ich nun auf die Ergebnisse a und b ?
|
|
|
| |
|
Hallo uecki,
> Ja Ok. Danke.
> Aber wie komme ich nun auf die Ergebnisse a und b ?
Siehe diesen Artikel.
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:56 Mi 03.06.2009 | | Autor: | uecki |
Ok. Ich denke ich habe es verstanden. Hab es mit dem erweiterten euklidischen Algorithmus gelöst. Also aufgrund der Gleichung 69*a=171 mod 256 dann von 69 die Inverse bestimmt, und zwar 141.
Dann rechne ich doch [mm] 171*a^{-1} [/mm] also 171*141=24111=94*256+47 und somit ist dann 24111 [mm] \equiv [/mm] 47 mod 256 und 47 somit mein a.
Ist das so richtig?
LG
|
|
|
| |
|
Hallo uecki,
> Ok. Ich denke ich habe es verstanden. Hab es mit dem
> erweiterten euklidischen Algorithmus gelöst. Also aufgrund
> der Gleichung 69*a=171 mod 256 dann von 69 die Inverse
> bestimmt, und zwar 141.
> Dann rechne ich doch [mm]171*a^{-1}[/mm] also
> 171*141=24111=94*256+47 und somit ist dann 24111 [mm]\equiv[/mm] 47
> mod 256 und 47 somit mein a.
> Ist das so richtig?
Ja. ![[ok]](/images/smileys/ok.gif "[ok]")
> LG
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:30 Mi 03.06.2009 | | Autor: | uecki |
Vielen Dank
|
|
|
|
