Seminarski rad iz Operacijskih sustava II

Ime i prezime: Tomislav Novosel

Matični broj: 0036378507

 

A5 algoritam kriptiranja podataka

 

A5 je naziv za algoritam kriptiranja podataka koji se koristi u GSM-u, tj. mobilnoj telefonskoj mreži. Ima dvije verzije, A5/1 i A5/2. Zadatak algoritma je da kriptira podatke koji se razmjenjuju između mobilnog telefona i bazne stanice.

Algoritam se zasniva na upotrebi triju posmačnih registara, duljine 32 bita. Međutim, od te se duljine koristi samo 19 bitova u prvom, 21 bit u drugom i 23 bita u trećem registru. Podaci koje je potrebno kriptirati se moraju razdijeliti u blokove od 8 bitova, tj. jednog bajta. Ključ koji se koristi kod kriptiranja je duljine 64 bita. Ta je vrijednost u izravnoj vezi s duljinom posmačnih registara jer je zbroj njihovih efektivnih duljina upravo jednak 64 bita. To omoguæava da se ključ upiše u registre, što se i izvršava na početku algoritma. Bajtovi ključa se redom upisuju u registre R1, R2 i R3. Nadalje, bajtovi s nižim indeksom se upisuju na mjesta u registrima s višim indeksom. Budući da su duljine registara različite i nisu višekratnik broja 8, to znači da će se neki bajtovi jednim dijelom zapisati u jedan registar, a drugim u drugi registar. Na kraju te procedure imat ćemo 64- bitni kljuè zapisan u posmačne registre. Registri s upisanim ključem su prikazani na slici 1.

 

 

 


                                                           

R1: 19- bitni registar

 

 

 


R2: 22- bitni registar

 

 

 


R3: 23- bitni registar

 

Slika 1.

 

Nakon toga možemo početi sa samim kriptiranjem podataka. Procedura koja to izvršava koristi pomoćni niz od 8 bitova. U taj niz se za svaki bajt podataka posebno zapisuju bitovi od kojih svaki ovisi o trenutnom stanju posmačnih registara. Između bajta izvornog podatka i pomoćnog bajta se izvršava operacija XOR i rezultat toga je kriptirani bajt. U pomoćni se bajt u osam koraka zapisuje bit po bit. U svakom koraku bajt se posmakne za jedno mjesto ulijevo. Time ostaje na njegovom najnižem bitu “prazno” mjesto na koje možemo upisati drugi bit. Da li će taj bit biti veličine 0 ili 1 ovisi o vrijednostima u posmačnim registrima, što provjerava posebna procedura. U svakom registru točno je definiran poseban bit koji će se koristiti kod te procedure. U prvom registru je to deveti bit, a u ostala dva registra se radi o jedanaestom bitu. Najprije se provjerava kod tih triju bitova ima li koji vrijednost 1. Nakon provjere algoritam može razmatrati dva slučaja. Prvi slučaj je da dva ili sva tri od spomenutih bitova imaju vrijednost 1. Drugi je slučaj da samo jedan ima, ili nijedan bit nema tu vrijednost. Osim kontrole tih bitova, promatraju se isto tako još neki i to, također, za svaki registar posebno. Za registar 1 su to 18., 17., 16. i 13 bit. U registru 2 se radi o 21., 20., 16. i 12. bitu. U trećem registru kontroliraju se 22., 21., 18. i 17. bit. Zasebno se za svaki registar koristi još jedan pomoćni niz od 32 bita koji je rezultat operacije XOR između spomenutih bitova. Taj se niz naziva feeback. Konkretno, feedback ima vrijednost koja je rezultat te operacije između nekoliko 32- bitnih vrijednosti, ali mu je zato bit na najnižoj poziciji jednak toj operaciji između točno spomenutih bitova. U prvom slučaju, što se odnosi na kontrolu triju bitova, ako je dotični bit vrijednosti 1, taj registar će se posmaknuti za jedno mjesto ulijevo. Nadalje, ako je 0. bit u feedback- u 1, izvršit će se XOR operacija između prvog bita u dotičnom registru i vrijednosti 1. Rezultat operacije će se upisati na isto mjesto u tom registru. U drugom slučaju isti princip će se primijeniti na one registre čiji kontrolni bitovi imaju vrijednost 0. Nakon svih tih provjera izvrši se još jedanput operacija XOR između svih triju posmačnih registara. Bit na 0. poziciji kod rezultata operacije je bit koji se upisuje na “prazno” mjesto pomoćnog niza koji je spomenut na početku same procedure kriptiranja. Dekriptiranje se izvršava identičnom procedurom kao i kriptiranje. Registri sa  svojim kontrolnim bitovima su prikazani na slici 2.

 

 

 

 


R1

 

 

 


R2

 

 

 


R3

 

Slika 2.

 

Operacije između bitova koje su potrebne za računanje podatka u feedback-u su prikazane na 3. slici.

 

 

 

 

 

 


                                         R1

 

 

 

 

 

 


XOR
 
                                   R2

 

 

 

 

 

 

 

 


                                  R3

 

Slika 3.

 

Ostvarenje ovog algoritma mogli bismo prikazati sljedećim pseudokodom:

 

            definiraj podatke koji se kriptiraju kao niz bajtova

            definiraj ključ koji se koristi u kriptiranju kao niz od osam bajtova

            definiraj tri posmačna registra ,R1, R2 i R3, duljine 19, 22 i 23 bita

            upiši bajtove ključa u te registre na način da najprije upisuješ u R1 i to od njegovih viših pozicija prema nižima

            ponavljaj za svaki bajt podataka

                        formiraj pomoćni bajt, čiji bitovi ovise o stanjima posmačnih registara

                        izvrši operaciju XOR između bajta podatka i pomoćnog bajta

            kraj ponavljanja

 

 

Pseudokod za formiranje pomoćnog bajta koji se koristi kod kriptiranja:

 

            ponavljaj osam puta

                        napravi posmak pomoćnog bajta za jedno mjesto ulijevo

                        odredi koja će biti vrijednost bita koja će se upisati na najnižu poziciju                            pomoćnog bajta

            kraj ponavljanja

 

 

Pseudokod za proceduru koja će odrediti koji će se bit upisati na najnižu poziciju pomoćnog bajta:

 

            odredi vrijednosti 9. bita u prvom registru te 11. bita u drugom i trećem registru

            ako dva ili tri bita imaju vrijednost 1, kontrola=1, inače kontrola=0

            ako je kontrola=1

                        ponavljaj za svaki registar

                                    ako dotični bit ima vrijednost 1

                                                ako se radi o prvom registru(R1)

                                                            pronađi rezultat operacije XOR između 18., 17., 16.   i 13. bita                                   

ako se radi o drugom registru(R2)

                                                            pronađi rezultat operacije XOR između 21., 20., 16. i 12. bita

                                                ako se radi o trećem registru(R3)

                                                            pronađi rezultat operacije XOR između 22., 21., 18. i 17. bita

                                                posmakni registar za jedno mjesto ulijevo

                                                ako je rezultat XOR operacije 1, na najnižu poziciju registra upisi 1, inače upiši 0

                        kraj ponavljanja

           

 

 

ako je kontrola=0

                        ponavljaj za svaki registar

                                    ako dotični bit ima vrijednost 0

                                                ako se radi o prvom registru(R1)

                                                            pronađi rezultat operacije XOR između 18., 17., 16.   i 13. bita                                   

ako se radi o drugom registru(R2)

                                                            pronađi rezultat operacije XOR između 21., 20., 16. i 12. bita

                                                ako se radi o trećem registru(R3)

                                                            pronađi rezultat operacije XOR između 22., 21., 18. i 17. bita

                                                posmakni registar za jedno mjesto ulijevo

                                                ako je rezultat XOR operacije 1, na najnižu poziciju registra upisi 1

                        kraj ponavljanja

            izvrši XOR operaciju između triju registara i nakon toga odredi bit na najnižoj poziciji dobivenog rezultata         

            dobiveni bit upiši u pomoćni bajt kod kriptiranja

 

 

Funkcija dekriptiranja je identična funkciji kriptiranja pa joj je i pseudokod identičan ovom već navedenom.

 

 

A5-IZVRŠNA VERZIJA                     A5-kod u C-u

 

 

Materijali i literatura:

            http://www.funet.fi/pub/crypt/cryptography/symmetric/a5/

            http://www.privacy.nb.ca/cryptography/archives/cryptography/html/1998-04/0051.html

            http://www.siam.org/siamnews/05-00/crypt.pdf

http://cryptome.org/a51-crack.htm

http://www.ecst.csuchico.edu/~atman/Crypto/misc/applied-crypto-2ed.html

http://infolab.kub.nl/edu/telematica/scripties98/groep17/a5_schn.html

http://ece.gmu.edu/courses/ECE543/viewgraphs_F02/lecture2_concepts_3.pdf