Category Archives: IT

IT Kriptografija

Simetrinės kriptosistemos, atsakymai į keletą klausimų

Atsakymai į klausimus nebūtinai yra visiškai teisingi. 😉

1. Simetrinės kriptosistemos

1.1. Kokie elementai sudaro kriptosistemą?

Kriptografine sistema vadinsime trejetą M, K, C, čia M ­- nešifruotu tekstu, K - naudojamu raktu ir C šifrų aibes, kartu su dešifravimo operacijomis.

1.2. Kas suformulavo moderniosios kriptografijos principus? Jei prisimenate bent vieną iš jų, tai suformuluokite?

Augustas Kerckhoffas

Pirma, jeigu šifravimo sistema gali būti įveikta, tai tik matematiškai.

Antra, sistema turi būti tokia, kad net ją turėdamas priešininkas negalėtų jos įveikti.

Trečia, sistemos raktas turi būti įsimenamas ir perduodamas jo neužrašius, jis turi būti keičiamas.

Ketvirta, sistema turi būti pritaikyta telegrafo ryšiu.

Penkta, šifravimo sistema turi būti nešiojama ir naudojimuisi ja nereiktų daugelio žmoniu.

Šešta, sistema turi būti paprasta naudotis: neturi būti reikalinga nei proto įtampa, nei ilga taisykliu seka.

1.3. Kokius informacijos apsaugos uždavinius sprendžia kriptografija?

Kriptografija sprendžia matematinius priemonių, skirtų užtikrinti saugų ryšį, kūrimo uždavinius.

1.4. Kokios kriptosistemos vadinamos simetrinėmis?

Simetrinėse kriptosistemose šifravimo rakto žinojimas leidžia lengvai rasti dešifravimo raktą (neretai šie raktai yra vienodi). Todėl tokiose sistemose abu raktai turi būti laikomi paslaptyje. Taigi simetrinės kriptosistemos nėra itin saugios; jos gali būti naudingos tik tada, kai siuntėjas ir gavėjas yra tas pats asmuo. Tad šios sistemos dažniausiai yra naudingos tam tikros privačios informacijos išsaugojimui. Vienintelis tokio šifravimo privalumas ─ greitumas (informaciją galima greitai užšifruoti ir dešifruoti); naudojantis simetrine kriptografija, yra sutaupoma daug laiko.

1.5. Paaiškinkite simetrinės kriptosistemos naudojimą blokine schema.

Simetrinė kriptosistema

1.6. Kas yra pavienių šifrų ataka?

Jei kriptoanalitikas sugebėjo gauti tik užšifruotą pranešimą, tai jo rengiama ataka priklauso pavienių šifrų atakų grupei (ang. ciphertext­only).

1.7. Kas yra teksto­šifro porų ataka?

Jei atakuotojas sugebėjo gauti tiek užšifruotus duomenis, tiek ir dešifruotus, tuomet jo rengiama ataka priklauso teksto­šifro porų grupei (ang. known­plaintext).

1.8. Kas yra pasirinktų teksto­šifro porų ataka?

Jei kriptoanalitikas turi galimybę realiu laiku pateikti norimus tekstinius pranešimus šifravimo sistemai ir gauti užšifruotus pranešimus, tuomet ataka priklausytų pasirinktų teksto – šifro porų atakų grupei (ang. chosen­plaintext).

1.9. Kas yra adaptyvi pasirinktų teksto­šifro porų ataka?

Jei atakuotojui pasiseka dar labiau, t.y. gauti priėjimą prie sistemos tokį, kad galėtų siųsti prašymus užšifruoti pakartotinai, tai tokia ataka priklausytų adaptyvių pasirinktų teksto – šifro porų atakoms (ang. adaptive­chosen­plaintext).

1.10. Kokia kriptosistema vadinama besąlygiškai saugia (unconditional security)?

Kriptosistema vadinama besalygiškai saugia (unconditional security) , jei net ir turėdamas beribius skaičiavimo resursus negali nežinodamas rakto iš šifro nustatyti, koks pranešimas buvo siųstas. Tai griežčiausias saugios kriptosistemos apibrėžimas.

1.11. Kokia kriptosistema vadinama saugia skaičiavimų požiūriu (computational security)?

Kriptosistema vadinama skaičiavimu požiūriu saugia (computational security), jeigu pasiektas skaičiavimų resursų lygis yra pernelyg žemas, kad naudojant geriausias žinomas atakas, sistema būtu įveikta.

1.12. Kas yra simbolių dažniai natūralioje kalboje ir kaip jie keičiasi, kai naudojame kriptosistemą su perstatomis?

Šifravimas naudojant keitini iš pradžiu apibrėžiamas pavieniams abėcėlės simboliams, o šifruojant žodžius, jis taikomas kiekvienai raidei atskirai, tai pradinio teksto simboliu dažniai lygūs atitinkamiems šifro simboliu dažniams, taip pat pradinio teksto simboliu poru dažniai lygūs atitinkamiems šifro simbolių porų dažniams ir t. t. Taigi naudojantis įvairių kalbų simbolių, jų porų, trejetų ir t. t. dažnių lentelėmis, iš šifro galima nustatyti ir kalbą, kuria buvo parašytas tekstas, ir patį keitinį.

1.13. Paaiškinkite, kaip veikia skytalės šifras.

Tekstas surašomas į m eilučių ir n stulpelių, pvz.:
L A B A S

R Y T A S (2 x 5)
tuomet skaitoma iš eilės kiekvienas stulpelis, gauname: L R A Y B T A A S S

Norint išsifruoti, darome atvirkščiai, t.y. surašome pirma į n stulpelių ir m eilučių ir skaitome iš eilės kiekvieną eilutę.

1.14. Kas yra simbolių dažniai natūralioje kalboje ir kaip jie keičiasi, kai naudojame kriptosistemą su keitiniais?

Jeigu šifruojame ne pavienius simbolius, bet m ilgio žodžius, tai ryšio tarp pavienių simbolų dažniu tekste ir šifre jau nebus, tačiau m; 2m, … ilgio simbolių blokų dažniai bus tie patys. Ž​ inoma, kai m yra didelis skaičius, tuos dažnius skaičiuoti ir lyginti yra sudėtinga. Taigi kai šifruojami ne pavieniai žodžiai, bet m (m > 1) ilgio žodžiai, ryšys tarp simboliu dažniu nešifruotame tekste ir šifre išnyksta.

1.15. Paaiškinkite, kaip konstruojamos kriptosistemos naudojantis Polibijaus kodo idėja.

Polibijaus kodo idėja ­ keisti raides tam tikrais susitartais kodais. Šia idėja paremtose kriptosistemose simboliai keičiami susitartais kodais. Pvz. Morzės abecėlė, Baudot kodas arba šiais laikais naudojamas ASCII kodavimas.

1.17. Cezario kriptosistemos abėcėlė A = {0, 1, 2, 3, 4, 5, 6}. Šifras c ={3, 2, 4, 5} gautas naudojant raktą k = 3. Dešifruokite šį šifrą.

3-­3=0

2-­3=6

4-­3=1

5-­3=2

M={0, 6, 1, 2}

1.22. Kaip keičiasi simbolių dažniai, kai naudojame homofoninius keitinius?

Naudodami homofoniniais keitiniais grindžiamus šifrus, galime panaikinti ryšį tarp atviro teksto simbolių dažnių lentelės bei šifro simbolių dažniu lentelės. Parinkdami funkcija k taip, kad homofono k(a) elementų skaičius būtų proporcingas simbolio a dažniui atvirame tekste, galime pasiekti, kad šifruotame tekste visu simboliu pasirodymo dažniai mažai skirtusi.

1.18. Paaiškinkite, kaip veikia Hilo kriptosistema.

Žinutei m užkoduoti, n ilgio raidžių blokas dauginamas iš n x n dydžio matricos. Dekoduojama blokus dauginant iš atvirščios matricos.
Pvz.:

m=ABCD

Raktas=

3 3

2 5
M­ -> A , C -­> 1 , 3

B , D 2 , 4
3 3 * 1 = 9 3 3 * 3 = 21

2 5 2 12 2 5 4 26
9 , 21 => I, U

12 , 26 L, Z = užkoduota žinutė

Dekoduodami, elgiames analogiskai, tik užkoduotą pranešimą dauginame iš atvirščios pradinei matricos.

1.19. Hilo šifro abėcėlė A = {0, 1, 2, 3, 4, 5, 6}. Užšifruokite simbolių porą 3, 5 naudodami raktą K = (1 3 2 4)

1 3 * 3 = 18 = 4

2 4 5 26 5 (mod 7)

1.21. Kas yra homofoniniai keitiniai ir kaip jie gali būti naudojami kriptosistemose?

Tekstas ir raktas vienareikšmiškai neapibrėžia šifro. Taigi du skirtingai užrašytus šifrus reikia ,,skaityti”, t.y. dešifruoti vienoda

IT

Goldbach kodai (G0, G1, G2)

Goldbach kodas

Matematikai jau senai žinojo, kad dviejų pirminių skaičių suma yra lyginis skaičius. Tačiau tik 1742 metais, vokiečių matetikui Christian Goldbach kilo klausimas - Jeigu dviejų pirminių skaičių suma yra lyginis skaičius, ar tiesa, kad kiekvienas lyginis skaičius yra dviejų pirminių skaičių suma? Kitaip tariant, Goldbach spėjimas (problema) sako:

Kiekvienas lyginis skaičius, didesnis už 2, yra dviejų pirminių skaičių suma.

Šiuo metu spėjimas yra patvirtintas skaičiams iki maždaug \(\), tačiau kolkas nėra įrodymų, kad tai galioja visiems skaičiams.

Idėja panaudoti Goldbach spėjimą koduoti informacijai kilo Peter Fenwick. Jis panaudojo pirminius skaičius kaip skaičiavimo sistema. O kiekvienas lyginis skaičius užkoduotas dviejų pirminių skaičių suma, dvejetainėje formoje turės tik du vienetus. Kad būtų galima atskirti kiekvieną užkoduotą skaičių iš eilutės, dvejetainė jo forma užrašoma iš kito galo. Tai galima vadinti vienetaine sistema.

G0

Pirmasis Goldbach kodas vadinamas G0. Tai aukščiau aprašytos vienetainės sistemos plėtinys. G0 užkoduoją teigiamą sveikąjį skaičių n, paskaičiavus lyginį skaičių \(\) ir užrašant jį kaip dviejų pirminių skaičių sumą iš kairės į dešinę.

n 2(n+3) Pirminiai sk. G0 kodas
1 8 3+5 11
2 10 3+7 101
3 12 5+7 011
4 14 3+11 1001
5 16 5+11 0101
6 18 7+11 0011
7 18 7+13 00101
8 22 5+17 010001
9 24 11+13 00011
10 26 7+19 0010001
11 28 11+17 000101
12 30 13+17 000011
13 32 13+19 000101
14 34 11+23 00010001

Kodo ilgis auga, tačiau ne monotoniškai. Funkcijos surasti kodo ilgiui duotam n skaičiui nėra. G0 yra efektyvus tik nedidelėms n reikšmėms, dėl trijų priežasčių: 1. Naudojantis priminių skaičių lentele, lengva surasti reikiamus pirminius skaičius. 2. G0 kodą lengva dekoduoti. 3. G0 kodo ilgis yra panašaus ilgio kaip Fibinacci kodo arba standartinės dvejetainės išraiškos.

Didėjant n reikšmei, G0 kodai tampa per ilgi. Taip pat, galimų pirminių skaičių pasirinkimas smarkiai išauga, o kiekvienas toks rinkinys nulemia skirtingo ilgio G0 kodą. Tad geriausių pirminių skaičių radimas užima per daug laiko.

G1

Dėl prastų rezultatų koduojant didelius skaičius su G0 kodu, buvo sugalvotas būdas, pavadintas G1, kaip sutrumpinti užkoduotus skaičius. Koduojant skaičių n, G1 kodu, surandami du pirminiai skaičiai \(\) ir \(\) \(\), kurių suma lygi skaičiui n. Rastųjų pirminių skaičių indeksų pora \(\) yra užkoduojama gamma kodais. Indeksas i gali būti lygus j, todėl kodavimui negalima poros apskaičiuoti pagal formulę \(\).

n Suma Indeksai Pora G1 kodas Ilgis
2 1+1 1,1 1,1 1:1 2
4 1+3 1,2 1,2 1:010 4
6 3+3 2,2 2,1 010:010 6
10 3+7 2,4 2,3 010:011 6
20 7+13 4,6 4,3 00100:011 8
40 17+23 7,9 7,3 00111:011 8
40 3+37 2,12 2,11 010:0001011 10
50 13+37 6,12 6,7 00110:00111 10
50 19+31 8,11 8,4 0001000:00100 12
70 29+41 10,13 10,4 0001010:00100 12
80 37+43 12,14 12,3 0001100:011 10
100 47+53 15,16 15,2 0001111:010 10

Kodo ilgio priklausomybę nuo pasirinktų pirminių skaičių pademonstruoja lentelės pavyzdys su skaičiais 40 ir 50. Dažniausiai, trumpiausias kodas gaunamas pasirenkant du panašius pirminius skaičius, tačiau pasitaiko atvejų, kada tokia taisykle vadovautis negalima.

Norint pritaikyti G1 praktikoje, reikalinga galimybė užkoduoti bet kokį teigiamą skaičių. Tą pasiekti galima dviem būdais:

1. Prieš pradedant G1 kodavimą, duotąjį skaičių n paversti į \(\) ir pradėti kodavimą su skaičiumi N. Tačiau naudojant šį būdą, indeksai padidėja apie 60 procentų, o tai sąlygoja ilgesnius G1 kodus.

2. Kiekvieną koduojamą skaičių įvertinti individualiai ir pagal tai pritaikyti apdorojimą. Šį būdą naudoja G2 kodavimas.

Nors nėra tikslios formulės, norint sužinoti G1 kodo ilgį duotajam skaičiui n, tačiau apytikslį kodo ilgį galime apskačiuoti. Vieno iš G1 sudarančių gamma kodų ilgis yra apytiksliai apskaičiuojami pagal formulę

\(\)

Kitas indeksas poroje \(\) yra apytiksliai \(\) ilgio. Iš to seka, kad G1 kodo ilgis duotajam n apytiksliai yra \(\), kur L yra gaunamas pagal aukščiau pateiktą formulę.

G1 kodas yra trumpesnis už gamma kodus, kai n neviršyja 100. Tačiau esant didesniam n, G1 kodas yra ilgesnis už gamma kodą.

G2

G2 kodavimas pratęsia G1 ir leidžia užkoduoti bet kokius teigiamus skaičius. G2 kodavime išskiriami keturi atvejai:

1. Skaičiai 1 ir 2 yra užkoduojami atitinkamai 110 ir 111. Jokie kiti kodai neprasidės dviem vienetais priekyje.

2. Lyginiai sveikieji skaičiai koduojami panašiai kaip ir G1. Apskaičiavus pirminių skaičių porą, jų indeksų pora gaunama pagal formulę \(\). Jeigu \(\), jis užkoduojamas kaip 010 - gamma kodas skaičiaus 2. Tai garantuoja, kad G2 kodai su lyginių skaičiumi neprasidės 1 ir visada bus formos \(\).

3. Jei n yra pirminis \(\), jis yra užkoduojamas \(\) gamma kodu ir iš dešinės pusės pridedamas 1, tokie skaičiai visada bus formos \(\).

4. Jei n yra nelyginis, tačiau ne pirminis, jo G2 kodas prasideda 1, o toliau seka G2 kodas skaičiaus \(\). Užkoduoti skaičiai turi forma \(\).

n G2 kodas Ilgis
1 110 3
2 111 3
3 0101 4
4 010010 6
5 0111 4
10 01100100 8
11 001011 6
16 0010100100 10
20 00111011 8
30 0001010010 10
40 0001100011 10
60 000010001010 12
80 000010110010 12
100 000011001011 12

Apytikslis G2 kodo ilgis apskaičiuojamas pagal formulę \(\)

Pvz.: \(\), pagal formulę, užkoduoto skaičiaus ilgis gaunasi 16.625, tai yra 1.66 karto daugiau, nei standartinė dvejetainė išraiška. Tačiau, šiuo atveju, gamma kodas yra ilgesnis 2 kartus.

Literatūra:

Fenwick P. Variable-Length Integer Codes Based on the Goldbach Conjecture, and Other Additive Codes. IEEE Trans. Inform. Theory, 48(8), 2002.
David Salomon, Giovanni Motta. Handbook of Data Compression. Springer, 2010.
Khalid Sayood. Lossless Compression Handbook. Academic Press, 2002.

IT

Even-Rodeh kodas

Data EncodingS. Even ir M. Rodeh sugalvotas kodas remiasi panašiu principu kaip ir Elijaus omega kodas. Pagrindinis skirtumas yra tas, kad Even-Rodeh kodavime simbolio ilgis yra pridedami iš kairės iki tol, kol simbolio ilgio užrašymui pakanka trijų bitų. Pavyzdžiui skaičiaus 2761 Even-Rodeh kodas būtų 100|1100|101011001001|0.

Šio kodo ilgis \(\) tenkina sąlygą \(\). Kur \(\) yra n dvejetainio atitikmens (beta kodo) ilgis. Sužinoti tikslų kodo ilgi duotajam \(\) galima pasinaudojus formule \(\), kol \(\) reikšmę galima užrašyti trimis bitais dvejetainėje sistemoje.

Turint simbolių eilutę \(\), prieš kiekvieną \(\) simbolį reikia pridėti Even-Rodeh kodą R su ilgiu \(\). Tuomet visus simbolius galima sujungti į eilutę \(\). Tokioje sukonstruotoje eilutėje kiekvienas simbolis gali būti nesunkiai atskiriamas, nes kodai veikia kaip tarpai, t.y. pakeičia kablelius, o 000 žymi eilutės pabaigą.

Even-Rodeh kodų ilgis asimptotiškai mažėja į nulį. Pavyzdžiui, eilutėms, kurių ilgis \(\) bitų, kodo priešdėlis tesudaro 2 proc. ilgio.

Reikšmė Even-Rodeh ilgis
1 3
2-3 3
4-7 4
8-15 8
16-31 9
32-63 10
64-127 11
128-255 17
256-512 18

Pavyzdys:

Turime užkoduotą eilutę \(\)

Nuskaitome pirmus tris bitus eilutėje - 100, jų reikšmė dešimtainėje sistemoje yra 4. Nuskaitę sekančius 4 bitus gauname 1100, o tai yra 12. Skaitome toliau, dabar jau 12 bitų. 101011001001 dešimtainėje sistemoje yra 2761. Toliau dekodavimui turėsime nuskaityti 2761 bitus, tačiau nuskaitę pirmąjį gauname 0. Jeigu pirmas nuskaitytas bitas yra 0, jį suprantame kaip kablelį, o prieš tai buvusi reikšmė - užkoduotas skaičiukas. Šiuo atveju tai yra 2761. Toliau tęsiame vėl skaitydami tris bitus. 111 reiškia, kad turėsime skaityti 7 sekančius bitus, bet pirmasis iš jų yra 0, tad užkoduotas skaičius - 7. Sekantys trys bitai yra 000, o tai reiškią eilutės pabaigą.

Literatūra:

Fenwick P. Variable-Length Integer Codes Based on the Goldbach Conjecture, and Other Additive Codes. IEEE Trans. Inform. Theory, 48(8), 2002.
David Salomon, Giovanni Motta. Handbook of Data Compression. Springer, 2010.
Khalid Sayood. Lossless Compression Handbook. Academic Press, 2002.