fixpunktfreie Permutation < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Ein Text [mm] X=x_1x_2x_3... [/mm] über dem Alphabet A={A,B,..,Z} wurde zu dem Chiffrat [mm] Y=y_1y_2y_3... [/mm] verschlüsselt, indem auf die einzelnen Zeichen in X eine Abfolge von fixpunktfreien Permutationen [mm] \sigma_1\sigma_2\sigma_3...von [/mm] A angewendet wurde, d.h. [mm] Y=\sigma_1 (x_1)\sigma_2(x_2)\sigma_3(x_3)...
[/mm]
Das Chiffrat lautet APXTAPMOMF. Sie wissen, dass die Phrase HPTM irgendwo in dem Klartext vorkommt. Was können wie über die Position dieser Phrase HPTM im Klartext sagen?
bemerkung: fixpunktfreie Permutation wenn [mm] \sigma(x)\not= [/mm] x |
Kann mir jemand einen Tipp geben wie ich die Position von HPTM bestimmen kann?
MfG
Mathegirl
|
|
| |
|
Hallo mathegirl,
die genaue Position kannst du nicht bestimmen, aber du kannst eine weitreichende Aussage treffen.
> Ein Text [mm]X=x_1x_2x_3...[/mm] über dem Alphabet A={A,B,..,Z}
> wurde zu dem Chiffrat [mm]Y=y_1y_2y_3...[/mm] verschlüsselt, indem
> auf die einzelnen Zeichen in X eine Abfolge von
> fixpunktfreien Permutationen [mm]\sigma_1\sigma_2\sigma_3...von[/mm]
> A angewendet wurde, d.h. [mm]Y=\sigma_1 (x_1)\sigma_2(x_2)\sigma_3(x_3)...[/mm]
>
> Das Chiffrat lautet APXTAPMOMF. Sie wissen, dass die Phrase
> HPTM irgendwo in dem Klartext vorkommt. Was können wie
> über die Position dieser Phrase HPTM im Klartext sagen?
>
> bemerkung: fixpunktfreie Permutation wenn [mm]\sigma(x)\not=[/mm] x
>
> Kann mir jemand einen Tipp geben wie ich die Position von
> HPTM bestimmen kann?
Leg doch mal die Phrase an das Chiffrat und verschiebe sie buchstabenweise nach rechts. Dabei darf an keiner Stelle der Phrase das Chiffrat den gleichen Buchstaben aufweisen, da sonst gegen die Vorgabe der Fixpunktlosigkeit verstoßen würde.
Dann gibt es hier nur noch zwei Positionen, an denen die Phrase im Klartext gelegen haben kann.
Grüße
reverend
|
|
|
| |
|
Den Gedanken hatte ich ja auch schon, aber ich komme mit dem verschieben nicht klar bzw ich kriege das nicht so recht hin, das was sinnvolles bei heraus kommt.
MfG
mathegirl
|
|
|
| |
|
Hallo nochmal,
> Den Gedanken hatte ich ja auch schon, aber ich komme mit
> dem verschieben nicht klar bzw ich kriege das nicht so
> recht hin, das was sinnvolles bei heraus kommt.
Das verstehe ich nicht. Was ist denn hier etwas Sinnvolles? Du sollst doch nur die Positionen ausschließen, an denen die Klartextphrase nicht gelegen haben kann, z.B. hier:
APXTAPMOMF
HPTM
Da ist das P an der gleichen Stelle.
APXTAPMOMF
...HPTM
Da ist das M an der gleichen Stelle.
Also hat die Klartextphrase weder beim ersten noch beim vierten Zeichen begonnen. Die anderen fünf Positionen kannst Du ja jetzt mal überprüfen.
Grüße
reverend
|
|
|
| |
|
Das hab ich ja auch gemacht. Die Phrase kann beim 3.oder 7. Zeichen beginnen, und wie gehts jetzt weiter? Kann ich herausfinden bei welchem es nun genau beginnt? DAS ist ehr das Problem.
Sonst wäre die Aufgabe ja etwas sinnlos....
MfG
Mathegirl
|
|
|
| |
|
> Das hab ich ja auch gemacht. Die Phrase kann beim 3.oder 7.
> Zeichen beginnen, und wie gehts jetzt weiter? Kann ich
> herausfinden bei welchem es nun genau beginnt? DAS ist ehr
> das Problem.
> Sonst wäre die Aufgabe ja etwas sinnlos....
>
> MfG
> Mathegirl
mehr lässt sich anhand der gegebenen Information nicht rausfinden.
Die Lösung ist also genau das, was du oben stehen hast.
Sinnlos ist das nicht, denn du hast die Zahl der Möglichkeiten auf 2 eingegrenzt, was ein entschlüsseln schonmal leichter machen kann.
|
|
|
|
