Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

nagradni zadatak
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Kriptografija
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
duje
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol: muško
Sarma = la pohva - posuda
338 = 339 - 1

PostPostano: 21:10 uto, 20. 3. 2007    Naslov: nagradni zadatak Citirajte i odgovorite

Na prvim predavanjima sam spomenuo mogucnost
da se tijekom semestra na Forumu postavi nekoliko
zadataka cijim rjesavanjem bi se dobili dodatni
bodovi koji bi se pribrojili onima dobivenima
rjesavanjem zadaca.
Slijedi prvi takav zadatak.
Onaj tko prvi posalje rjesenje ovdje na Forum,
dobit ce dodatnih 10 bodova.
(Zadatak je iz knjige
A. Dujella, M. Maretic: Kriptografija,
cije je pisanje pri kraju.)


[b]Zadatak 1:[/b] Cesto se kaze da za dekriptiranje nije nuzno poznavanje
jezika na kojem je pisan otvoreni tekst, jer svaki govorni
jezik (i skoro svaka njegova transkripcija na medjunarodni alfabet)
posjeduje dovoljno zakonitosti da tekst na tom jeziku mozemo
razlikovati od slucajnog niza slova. Pokusajte se u to uvjeriti
tako da dekriptirate sifrat
[code:1]
WBKYXHFX HXKQFQXQB YXQBK FORAFX BAL PFKYLILX AX
[/code:1]
dobiven Cezarovom sifrom (ovaj puta smo iznimno ostavili razmake na
onim mjestima na kojima se javljaju i u otvorenom tekstu).
Pritom je otvoreni tekst recenica na
jeziku za kojeg vjerujemo da ga velika vecina posjetitelja Foruma ne razumije.
Na prvim predavanjima sam spomenuo mogucnost
da se tijekom semestra na Forumu postavi nekoliko
zadataka cijim rjesavanjem bi se dobili dodatni
bodovi koji bi se pribrojili onima dobivenima
rjesavanjem zadaca.
Slijedi prvi takav zadatak.
Onaj tko prvi posalje rjesenje ovdje na Forum,
dobit ce dodatnih 10 bodova.
(Zadatak je iz knjige
A. Dujella, M. Maretic: Kriptografija,
cije je pisanje pri kraju.)


Zadatak 1: Cesto se kaze da za dekriptiranje nije nuzno poznavanje
jezika na kojem je pisan otvoreni tekst, jer svaki govorni
jezik (i skoro svaka njegova transkripcija na medjunarodni alfabet)
posjeduje dovoljno zakonitosti da tekst na tom jeziku mozemo
razlikovati od slucajnog niza slova. Pokusajte se u to uvjeriti
tako da dekriptirate sifrat
Kod:

      WBKYXHFX HXKQFQXQB YXQBK FORAFX BAL PFKYLILX AX
     

dobiven Cezarovom sifrom (ovaj puta smo iznimno ostavili razmake na
onim mjestima na kojima se javljaju i u otvorenom tekstu).
Pritom je otvoreni tekst recenica na
jeziku za kojeg vjerujemo da ga velika vecina posjetitelja Foruma ne razumije.




Zadnja promjena: duje; 9:59 čet, 27. 9. 2007; ukupno mijenjano 1 put.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Melkor
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 10. 2004. (18:48:00)
Postovi: (291)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
140 = 152 - 12
Lokacija: Void

PostPostano: 22:37 uto, 20. 3. 2007    Naslov: Citirajte i odgovorite

Ja bih rekao: [i]Zenbakia kantitate baten irudia edo sinboloa da.[/i]

Naime, gledao sam međusobni indeks koincidencije engleskog teksta i šifrata s abecedom pomaknutom redom za 0, 1, 2, ..., 25.

Evo rezultata:
[code:1]0 0.025
1 0.037
2 0.030
3 0.042
4 0.042
5 0.044
6 0.038
7 0.038
8 0.036
9 0.044
10 0.043
11 0.029
12 0.046
13 0.036
14 0.032
15 0.033
16 0.041
17 0.034
18 0.039
19 0.058
20 0.043
21 0.023
22 0.037
23 0.067
24 0.038
25 0.027[/code:1]

Uočavamo da je indeks 0.067 najveći za pomak 23. Dakle, ako pomaknemo abecedu šifrata za 23, dobijemo (najvjerojatnije) originalni tekst, ili ako pomaknemo originalni tekst za 3, dobijemo šifrat.

To je zapravo obična Cezarova šifra iz davnih vremena. A->D, B->E, ...

Evo i koda u C-u koji izbacuje gornji rezultat:
[code:1]/* Autor: Filip Niksic */

#include <stdio.h>

double freq_engl[] = {
0.082, 0.015, 0.028, 0.043, 0.127, 0.022, 0.020, 0.061, 0.070, 0.002,
0.008, 0.040, 0.024, 0.067, 0.075, 0.019, 0.001, 0.060, 0.063, 0.091,
0.028, 0.010, 0.023, 0.001, 0.020, 0.001
};

int main(int argc, char **argv) {
FILE *in;
int pomak,i,n;
int freq[26];
char c;
double mic;

if (argc<2 || (in=fopen(argv[1],"r"))==NULL) {
printf("Couldn't open input file!\n");
return 0;
}

for (i=0,n=0;i<26;freq[i++]=0);

while (!feof(in)) {
fscanf(in,"%c",&c);
if (c>='a' && c<='z') c-='a'-'A';
if (c>='A' && c<='Z') {
c-='A';
freq[c]++;
n++;
}
}

for (pomak=0;pomak<26;pomak++) {
mic=0.0;
for (i=0;i<26;i++)
mic+=freq_engl[i]*(double)freq[(i+pomak)%26];
mic/=(double)n;
printf("%d %.3lf\n",pomak,mic);
}

fclose(in);
return 0;
}[/code:1]
Ja bih rekao: Zenbakia kantitate baten irudia edo sinboloa da.

Naime, gledao sam međusobni indeks koincidencije engleskog teksta i šifrata s abecedom pomaknutom redom za 0, 1, 2, ..., 25.

Evo rezultata:
Kod:
0 0.025
1 0.037
2 0.030
3 0.042
4 0.042
5 0.044
6 0.038
7 0.038
8 0.036
9 0.044
10 0.043
11 0.029
12 0.046
13 0.036
14 0.032
15 0.033
16 0.041
17 0.034
18 0.039
19 0.058
20 0.043
21 0.023
22 0.037
23 0.067
24 0.038
25 0.027


Uočavamo da je indeks 0.067 najveći za pomak 23. Dakle, ako pomaknemo abecedu šifrata za 23, dobijemo (najvjerojatnije) originalni tekst, ili ako pomaknemo originalni tekst za 3, dobijemo šifrat.

To je zapravo obična Cezarova šifra iz davnih vremena. A→D, B→E, ...

Evo i koda u C-u koji izbacuje gornji rezultat:
Kod:
/* Autor: Filip Niksic */

#include <stdio.h>

double freq_engl[] = {
    0.082, 0.015, 0.028, 0.043, 0.127, 0.022, 0.020, 0.061, 0.070, 0.002,
    0.008, 0.040, 0.024, 0.067, 0.075, 0.019, 0.001, 0.060, 0.063, 0.091,
    0.028, 0.010, 0.023, 0.001, 0.020, 0.001
};

int main(int argc, char **argv) {
    FILE *in;
    int pomak,i,n;
    int freq[26];
    char c;
    double mic;

    if (argc<2 || (in=fopen(argv[1],"r"))==NULL) {
        printf("Couldn't open input file!\n");
        return 0;
    }

    for (i=0,n=0;i<26;freq[i++]=0);

    while (!feof(in)) {
        fscanf(in,"%c",&c);
        if (c>='a' && c<='z') c-='a'-'A';
        if (c>='A' && c<='Z') {
            c-='A';
            freq[c]++;
            n++;
        }
    }

    for (pomak=0;pomak<26;pomak++) {
        mic=0.0;
        for (i=0;i<26;i++)
            mic+=freq_engl[i]*(double)freq[(i+pomak)%26];
        mic/=(double)n;
        printf("%d %.3lf\n",pomak,mic);
    }

    fclose(in);
    return 0;
}



_________________
I don't know half of you half as well as I should like; and I like less than half of you half as well as you deserve.


Zadnja promjena: Melkor; 23:19 uto, 20. 3. 2007; ukupno mijenjano 1 put.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
duje
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol: muško
Sarma = la pohva - posuda
338 = 339 - 1

PostPostano: 22:50 uto, 20. 3. 2007    Naslov: Citirajte i odgovorite

[quote="Melkor"]Ja bih rekao: [i]Zenbakia kantitate baten irudia edo sinboloa da.[/i]
Filip Niksic
[/quote]
Bravo! Odgovor je tocan. Dobili ste 10 bodova.

Andrej Dujella
Melkor (napisa):
Ja bih rekao: Zenbakia kantitate baten irudia edo sinboloa da.
Filip Niksic

Bravo! Odgovor je tocan. Dobili ste 10 bodova.

Andrej Dujella


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
duje
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol: muško
Sarma = la pohva - posuda
338 = 339 - 1

PostPostano: 21:18 čet, 5. 4. 2007    Naslov: 2. zadatak Citirajte i odgovorite

[b]Zadatak 2:[/b] Neka je [i]p[/i] neparan prost broj.
Koliko ima involutornih [latex]2 \times 2[/latex] matrica nad prstenom [latex]\mathbb{Z}_{2p}[/latex] ?
Zadatak 2: Neka je p neparan prost broj.
Koliko ima involutornih matrica nad prstenom ?


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Smith
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 30. 10. 2004. (23:30:23)
Postovi: (178)16
Spol: muško
Sarma = la pohva - posuda
12 = 18 - 6
Lokacija: {Tamo Gore}^{TM}

PostPostano: 23:37 čet, 5. 4. 2007    Naslov: Citirajte i odgovorite

Izgleda da dosta tu teorije stoji u pozadini... :shock:

Uglavnom, radi se o problematicnom smanjivanju prostora kljuceva zahtijevanjem involutornosti matrice kod Hillove sifre koje je spomenuto na predavanjima.

[url=http://jeff.over.bz/papers/undergrad/on-the-keyspace-of-the-hill-cipher.pdf]Ovdje [/url] se nalaze kljucni rezultati za shvacanje o cemu se tu tocno radi.

Nazalost, nemam gdje u ovo kasno doba posuditi brdo knjiga potrebnih za dublje razumijevanje materije u koju se upustam, pa sam se morao posluziti gotovim kuharicama u gorenavedenom dokumentu za nalazenje rjesenja. :oops:

Trebat ce nam izrazi oznaceni [latex]g_t[/latex] u Teoremu 3.1.1., pa ih najbolje izracunajmo odmah:
[latex]g_0=1[/latex]
[latex]g_1=p-1[/latex]
[latex]g_2=(p^2-p)(p^2-1)=p(p-1)^2(p+1)[/latex]

Nadalje, koristimo redom Teorem 3.2.1., Teorem 3.1.3. i Teorem 3.1.1. kako bismo izracunali T(2,2p) (trazeni broj involutornih matrica u prstenu):
[latex]T(2,2p)=T(2,2)\cdot T(2,p)=[/latex]
[latex]=\left(g_2\sum_{t=0}^1\frac{2^{-t(4-3t)}}{g_tg_{2-2t}}\right)\left(\sum_{t=0}^2\frac{g_2}{g_tg_{2-t}}\right)=[/latex]
[latex]=g_2^2\left(\frac{1}{g_0g_2}+\frac{1}{2g_0g_1}\right)\left(\frac{1}{g_0g_2}+\frac{1}{g_1^2}+\frac{1}{g_2g_0}\right)=[/latex]
[latex]=\left(1+\frac{g_2}{2g_1}\right)\left(2+\frac{g_2}{g_1^2}\right)=[/latex]
[latex]=\left(1+\frac{p(p-1)^2(p+1)}{2(p-1)}\right)\left(2+\frac{p(p-1)^2(p+1)}{(p-1)^2}\right)=[/latex]
[latex]=\left(1+\frac{(p-1)p(p+1)}{2}\right)\left(2+p(p+1)\right)=[/latex]
[latex]=2+p(p+1)+(p-1)p(p+1)+\frac{(p-1)p^2(p+1)^2}{2}=[/latex]
[latex]=2+p^2(p+1)+\frac{(p-1)p^2(p+1)^2}{2}=[/latex]
[latex]=p^2(p+1)\left(1+\frac{p^2-1}{2}\right)+2[/latex]

Nemam dovoljno maste za kompaktniji zapis...

Nadam se da je racun tocan, ipak sam racunao olovkom i papirom. :D
Izgleda da dosta tu teorije stoji u pozadini... Shocked

Uglavnom, radi se o problematicnom smanjivanju prostora kljuceva zahtijevanjem involutornosti matrice kod Hillove sifre koje je spomenuto na predavanjima.

Ovdje se nalaze kljucni rezultati za shvacanje o cemu se tu tocno radi.

Nazalost, nemam gdje u ovo kasno doba posuditi brdo knjiga potrebnih za dublje razumijevanje materije u koju se upustam, pa sam se morao posluziti gotovim kuharicama u gorenavedenom dokumentu za nalazenje rjesenja. Embarassed

Trebat ce nam izrazi oznaceni u Teoremu 3.1.1., pa ih najbolje izracunajmo odmah:




Nadalje, koristimo redom Teorem 3.2.1., Teorem 3.1.3. i Teorem 3.1.1. kako bismo izracunali T(2,2p) (trazeni broj involutornih matrica u prstenu):










Nemam dovoljno maste za kompaktniji zapis...

Nadam se da je racun tocan, ipak sam racunao olovkom i papirom. Very Happy



_________________
We only have one candle
To burn down to the handle...
- Sonata Arctica, Weballergy
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
duje
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol: muško
Sarma = la pohva - posuda
338 = 339 - 1

PostPostano: 1:02 pet, 6. 4. 2007    Naslov: Citirajte i odgovorite

[quote="Smith"][latex]=p^2(p+1)\left(1+\frac{p^2-1}{2}\right)+2[/latex]
[/quote]
Konacan rezultat je naravno jako prevelik (inace bi Hillov savjet koristenja involutornih matrica bio i vise nego izvrstan - ispalo bi da se prostor kljuceva povecao, a ne smanjio). Ali postupak je dobar (i puno opcenitiji nego sto se u zadatku trazilo), pa se nadam da ce biti lako naci gresku i dobiti tocan rezultat.
Smith (napisa):


Konacan rezultat je naravno jako prevelik (inace bi Hillov savjet koristenja involutornih matrica bio i vise nego izvrstan - ispalo bi da se prostor kljuceva povecao, a ne smanjio). Ali postupak je dobar (i puno opcenitiji nego sto se u zadatku trazilo), pa se nadam da ce biti lako naci gresku i dobiti tocan rezultat.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Smith
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 30. 10. 2004. (23:30:23)
Postovi: (178)16
Spol: muško
Sarma = la pohva - posuda
12 = 18 - 6
Lokacija: {Tamo Gore}^{TM}

PostPostano: 10:12 pet, 6. 4. 2007    Naslov: Citirajte i odgovorite

Mah, bas sam blesav... :D :oops:

U [latex]T(2,2)[/latex] racunam s [latex]p[/latex] umjesto s dvojkom...

U slucaju [latex]T(2,2)[/latex] brojevi [latex]g_i[/latex] su sljedeci (mislim da nema potrebe uvoditi sad nove oznake ili indekse, bit ce jasno o cemu pricam):

[latex]g_0=1[/latex]
[latex]g_1=1[/latex]
[latex]g_2=6[/latex]

Dakle, [latex]T(2,2)=6\cdot\left(\frac{1}{1\cdot 6}+\frac{1}{2\cdot 1\cdot 1}\right)=4[/latex], pa ima puuno manje za racunati. :oops:

[latex]T(2,2p)=T(2,2)\cdot T(2,p)=[/latex]
[latex]=4\cdot \left(\frac{g_2}{g_0g_2}+\frac{g_2}{g_1^2}+\frac{g_2}{g_2g_0}\right)=[/latex]
[latex]=4\cdot \left(\frac{2}{g_0}+\frac{g_2}{g_1^2}\right)=[/latex]
[latex]=4\cdot \left(2+\frac{p(p-1)^2(p+1)}{(p-1)^2}\right)=[/latex]
[latex]=4\cdot (p(p+1)+2)[/latex]

Sad je prostor kljuceva nesto manji nego prosli put. :D :oops:
Mah, bas sam blesav... Very Happy Embarassed

U racunam s umjesto s dvojkom...

U slucaju brojevi su sljedeci (mislim da nema potrebe uvoditi sad nove oznake ili indekse, bit ce jasno o cemu pricam):





Dakle, , pa ima puuno manje za racunati. Embarassed







Sad je prostor kljuceva nesto manji nego prosli put. Very Happy Embarassed



_________________
We only have one candle
To burn down to the handle...
- Sonata Arctica, Weballergy
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
duje
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol: muško
Sarma = la pohva - posuda
338 = 339 - 1

PostPostano: 10:51 pet, 6. 4. 2007    Naslov: Citirajte i odgovorite

[quote="Smith"][latex]4\cdot (p(p+1)+2)[/latex]
[/quote]
Ovo je tocan odgovor. Dobili ste 10 bodova.

Andrej Dujella
Smith (napisa):


Ovo je tocan odgovor. Dobili ste 10 bodova.

Andrej Dujella


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Kriptografija Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Možete otvarati nove teme.
Možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan