Kaip veikia RSA

Įžanga

RSA kodavimas yra labai įdomus pavyzdys, kaip abstraktų matematinį modelį galima sėkmingai panaudoti realiam gyvenime. Šiame įraše pabandysim išsiaiškinti kaip vyksta RSA duomenų kodavimas iš matematinės pusės.

Paprastos funkcijos

Matematiškai funkcijos yra toks pats reiškinys, kaip ir programavime. Pavyzdžiui:

foo(x) = 10*x-2

Jeigu į funkciją perduosim 2, tuomet ji gražins 18. Viskas logiška. Mes taip pat galima parašyti funkciją, kuri daro lygiai tą patį, tik atvirkščiai:

bar(x) = (x+2)/10

Jeigu į funkciją perduosim 18, tuomet ji gražins 2. Kadangi bar(x) funkcija daro funkcijai foo(x) priešingus veiksmus, tai bar(x) funkcija yra atvirkštinė funkcijai foo(x).

Dabar pesikelkim į programavimo terpę. Pavyzdžiui, jeigu mes turim foo(x) funkcijos pradinį kodą, tačiau neturim bar(x) funkcijos pradinio kodo. Ar yra įmanoma parašyti bar(x) funkcija, kuri yra atvirkštinė funkcijai foo(x) ? Mes žinom kas bus siunčiama į bar(x) funkciją ir ką ji turėtų gražinti. Teoretiškai atsakymas būtų taip. Tačiau, yra keletas specialių funkcijų, kurių veikimo principas yra žinomas, tačiau parašyti jai atvirkštinę funkciją yra labai sunkus uždavinys.

Modulių aritmetika

Daugelis programuotojų yra sutikę % operatorių, kuris gražina dalybos liekaną. Pavyzdžiui:

10 % 3 = 1

Matematikoje, idėja yra panaši, tačiau pati modulių teorija yra skirtinga. Modulių aritmetika sudaro begalinis skaičius, kuris yra sukamas apie realaus skaičiaus lanką. Skaičiai, kurie neužbaigia ciklo yra vadinami kartotiniai. Analogišką operaciją programavime, matematikoje galime užrašyti taip:

10 = 1 (mod 3)

Skamba tai kaip: “10 turi kartotinį 1, moduliu 3”.

Liekaną geriau pamatysime, jeigu išskaidysime skaičių į jo dedamąsias:

6 + 4 = 0(mod 3) + 1(mod 3) = 1(mod 3)

Šioje išraiškoje, skaičius 6 liekana yra 0, o 4 liekana yra 1. Į (mod 3) veiksmą galime žiūrėti kaip į trijų valandų laikrodį, kuriame ciklas kartojasi su kiekvienu apsisukimu.

Įdomiausia modulių aritmetikoje, kad veiksmuose mes galime pakeisti skaičius jų liekanomis ir vistiek gauti teisingą atsakymą:

4 = 1(mod 3 )
6 + 4 = 6 + 1 = 1(mod 3)

Jeigu naudojame kaip pagrindą 10 – mūsų visiškai nejaudina koks yra skaičius, mums svarbu kokiu skaičiumi yra baigiama:

37383 = 3(mod 10)
33313134 = 4(mod 10)

Didžiausias bendras daliklis

Didžiausias bendras daliklis ( GCD funkcija ) yra dviejų skaičių didžiausias skaičius, iš kurio dalinasi abu skaičiai:

gcd(22,11) = 11
gcd(23,55) = 1
gcd(999,99) = 9

Kuomet dviejų skaičių didžiausias bendras daliklis yra lygūs vienam, tai yra sakoma, kad skaičiai vienas kitam yra pirminiai. Kaip pavyzdžiui 23 ir 55 yra vienas kitam pirminiai.

Eulerio Totient Funkcija

Eurelio Totient Funkcija yra žymima graikiška raide phi(N) ir žymi skaičių kiekį (1;N-1) intervale, kurie yra pirminiai skaičiui N.

Pavyzdžiui:

phi(4) = 2 ( 1 ir 3 yra pirminiai skaičiui 4 )
phi(6) = 2 ( 1 ir 5 yra pirminiai skaičiui 6 )
phi(8) = 4 ( 1, 3, 5 ir 7 yra pirminiai skaičiui 8 )

Išsiskaičiuoti pirminius skaičius taip pat galima ir pasitelkus kitą išraišką:

phi(P*Q) = (P-1)*(Q-1)

Jeigu P ir Q yra pirminiai.

Eurelio Totient Teorema

Šita teorema yra pats svarbiausias raktas, vedantis prie RSA algoritmo:

Jeigu gcd(T, R) = 1 ir T < R, tuomet T^(phi(R)) = 1 (mod R)

Mes galima patikrinti teoremą, panaudodami kelis mažus skaičius. Jeigu pažymėsime T = 5 ir R = 6, gausime:

phi(6) = (2-1)*(3-1) = 1 * 2 = 2
5^(phi(6)) = 5^2 = 25
25 = 24 + 1 = 6*4 +1 = 1(mod 6)

Teoremos nagrinėjimas

Toliau paimkime Eurelio Totient teoremą ir su ja pažaiskime:

T^(phi(R)) = 1(mod R)

Padauginkime šitą teoremą iš jos paties. Dėka modulių daugybos viskas atrodys taip:

T^(phi(R))*T^(phi(R)) = 1*1(mod R)
T^(2*phi(R)) = 1(mod R)

Pakartoję ciklą gausime:

T^(3*phi(R)) = 1(mod R)

Galime tęsti kiek norime. Atradus tokį dėsningumą mes galime praplėsti Eurelio Totient Teoremą:

Jeigu GCD(T, R) = 1 ir T < R, tuomet T^(K*phi(R)) = 1(mod R), kur K bet koks skaičius

Galima pastebėti, jog K gali būti tik sveikasis skaičius, kas reiškia, kad K*phi(R) dalinsis be liekanos iš phi(R). Taigi dėsnį galime perfrazuoti:

Jeigu GCD(T, R) = 1 ir T < R, tuomet T^S = 1(mod R), kuomet S = 0(mod phi(R))

Tęskime savo žaidimą ir padauginkime gautą lygtį iš T:

T^S*T = 1*T(mod R)
T^(S+1) = T(mod R)

Pakartojam:

T^(S+1)*T = T*T(mod R)
T(S+2) = T^2(mod R)

Ir taip toliau. Matome dėsningumą. Iš jo galime nusręsti, kad S ne R kartotinis, o phi(R). Iš šito seka nauja taisyklė:

T^E = T^F(mod R), kuomet E = F(mod phi(R))

Idėja

Grįžkime prie ankstesnės lygties ir panagrinėkime ją dėtaliau:

T^(S+1) = T(mod R)

Vienoje lygties pusėje mes turim T, pakeliam jį kvadratu. Kitoje lygties pusėje mes su T atliekame modulių aritmetikas. Mes turi dvi lygtis, kurios yra lygios ir kuriose dalyvauja tas pats vienas kintamasis.

Tačiau kas gi čia tokio stebuklingo? O stebuklinga yra tai, kad mes galime lengvai jas atskirti. Būtent šiuo atveju, paimkime kažkokius du nauju skaičius P ir Q, tuomet:

P*Q = S+1, kiekvienai S reikšmei

Arba:

P*Q = 1(mod phi(R))

Tuomet mes galima parašyti:

T^(P*Q) = T(mod R)

Kas yra tas pats, kas ir:

(T^P)^Q = T(mod R)

Ir tai mes jau galime perskelti į du žingsnius:

T^P = X(mod R) ir 
X^Q = T(mod R)

Generuojam raktų porą

Norint sugeneruoti tam tikrus raktus, pirmiausiai reikia parinkti reikšmę R. Taigi, galime pradėti atsitiktinai imdami du skaičius, U ir V, ir juos daugindami:

R = U*V

Abudu skaičiai turi būti pirminiai vienas kito atžvilgiu. Paskui bus galima lengvai rasti skaičiaus R pirminius skaičius:

phi(R) = (U-1)*(V-1)

Pavyzdys

Tam, kad pamatyti, kaip viskas suskaičiuojama, paimkime mažus skaičius, tarkime U = 5, V = 11:

R = U*V = 5*11 = 55
phi(R) = phi(55) = (5-1)*(11-1) = 4*10 = 40

Dabar reikia rasti skaičius, kurie tinka lygčiai:

P*Q = 1(mod 40)

Žinoma, jų yra begalinis skaičius, tačiau pradėkime nuo P = 7.

7*Q = 1(mod 40)

Perrašom dešinę pusę:

7*Q = K*40 + 1

Pirmas skaičius, kuris tenkina lygtį yra Q = 23:

7*23 = 161 = 4 * 40 + 1

Taigi, mūsų viešas raktas yra P = 7, o privatus Q = 23.

Tarkime, norime išsiųsti žodį “VGTU”. Painaudoję ASCII kodų lentelę, skaičiais tai atrodytų taip:

86 71 84 85

Dabar užkoduojam kiekvieną simbolį su viešu raktu:

86^7 (mod 55)  = 26
71^7(mod 55) = 36
84^7(mod 55) = 39
85^7(mod 55) = 35

Gauvome tokį kodą:

26 36 39 35

Jeigu išversime visą tai pasitelkdami ASCII lentelę, gausime “SUB$’#”, kas visiškai neturi nieko bendro su mūsų siunčiama žinute. Kuomet duomenys baigia savo kelią per nesaugią liniją, gavėjo pusėje vyksta duomenų dekodavimas pagal privatų raktą Q = 23.

26^23(mod 55) = 86
36^23(mod 55) = 71
39^23(mod 55) = 84
35^23(mod 55) = 85

Gavome kodą:

86 71 84 85

Kas iš ASCII kodų lentelės surenka “VGTU”.

Galite pabandyti atkoduoti:

68 10 20 20 34 43 23 29 07 17 12 36

Su privačiu raktu Q = 23 ir R = 55.

Išvados

RSA yra gan paprastas kodavimo algoritmas, tačiau nežinant raktų, jį iškoduoti su dabartiniais kompiuteriais gali užtrukti ant tiek ilgai, kad saulė jau išnaudos visus savo resursus ir sprogs, o kompiuteris vis dar bandys iškoduoti RSA kodą.

Jis neparodo simbolių priklausomybės, kaip tarkim T (84) ir U (85) skiriasi tik viena eile, tačiau užkoduojant juos RSA, jų skirtumo eilė pasikeitė T (39) ir U (35) ir netgi tapo neigiama.

Šaltinis

Paslėptas Markovo modelis: Įžanga

Po truputi ruošiames baigiamąjam darbui, todėl pradėjau versti vieną gerą paslėpto Markovo modelio vadovą “A tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”. Pateikiu Jums išverstą įvadą.

Nors ir buvo pristatyti dar vėlesniais 1960-tais ir ankstyvais 1970-tais metais, statistinis Markovo metodas arba paslėptas Markovo metodas tapo labai populiarūs tik paskutiniais metais. Yra dvi pagrindinės priežastys kodėl taip nutiko. Pirma, modeliai yra stipriai pagrįsti matematiškai ir iš to galima suformuoti teoretinę bazę modelių taikymui. Antra, modeliai, reikiamai pritaikyti, labai gerai dirba praktikoje, svarbiuose įtaisuose. Šiame vadove pabandysime atsargiai ir metodiškai apžvelgti teoretinius šio tipo statistinio modelio aspektus ir parodyti kaip jie yra pritaikomi balso atpažinimo problemoms spręsti.

Realaus pasaulio procesus paprasčiausiai galime apibūdinti signalais. Signalai gamtoje gali būti diskretiniai (raidės iš žodyno) arba nuolatiniai (garsiniai signalai, temperatūros matavimai). Signalo šaltinis gali būti stacionarus (jo statistiniai apibrėžimai nepriklauso nuo laiko), ar nestacionarus (signalo apibrėžimai laikui bėgant kinta). Signalai gali būti gryni (siunčiami tiesiai iš šaltinio), ar pažeisti iš kitų signalų šaltinių (kaip pavyzdžiui triukšmo) arba dėl perdavimo trukdžių, aido, kt.

Fundamentinio tipo svarbi problema yra charakterizuoti tokius, realaus pasaulio, signalus į signalų modelį. Yra keletas priežasčių dėl ko šitą problemą yra būtina spręsti. Pirmiausiai, signalo modelis suteikia mums pradinę informaciją apie signalą, kuria remiantis yra galima apibrėžti reikalingą signalą sistemos išėjime. Pavyzdžiui, mus domina pokalbio, vykstančiu telefonu, signalo sustiprinimas. Signalas yra pažeistas triukšmo ir perdavimo kliūčių. Tokiam uždaviniui atlikti mes galime panaudoti signalų modelį ir suprojektuoti sistemą, kuri pašalins nereikalingą triukšmą ir anuliuos perdavimo iškraipymą. Antra priežastis kodėl signalų modelis yra toks svarbus yra tai, kad jis potencialiai mums gali pasakyti labai daug apie signalo šaltinį, net jeigu mes jo nematome. Ši savybė yra labai svarbi, kai yra būtina gauti tikslų signalą iš šaltinio. Šiuo atveju, su geru signalo modeliu, mes galime simuliuoti signalo šaltinį ir išmokti kuo daugiau iš tokių simuliacijų. Galiausiai, pagrindinė priežastis kodėl signalo modelis yra toks svarbus – jis velniškai gerai veikia praktikoje ir leidžia mums suvokti svarbias praktines sistemas, pavyzdžiui spėjimo sistemos, atpažinimo sistemos, identifikavimo sistemos, kt.

Galima pasirinkti keletą signalo modelio tipų, kuriais galima apibūdinti nagrinėjamo signalo ypatybes. Vienas signalas gali būti išskaidytas į keletas jo sudedamąsias klases: deterministinį modelį ir statistinį modelį. Deterministinis modelis parodo pagrindinę informaciją apie signalą: ar signalas yra sinusinės formos, ar yra eksponentinė suma, kt. Tokiais atvejais, signalo apibūdinimas yra gan paprastas uždavinys. Viskas, kas reikalaujama yra nustatyti signalo modelio parametrų reikšmes (amplitudę, dažnį, fazę, kt.). Antra signalo modelio plati klasė yra statistinis modelis, kuris bando charakterizuoti statistinius signalo parametrus. Tokių statistinių modelių pavyzdžiai yra Gauso procesas, Poisono procesas, Markovo procesas, paslėptas Markovo procesas. Paslėpta prielaida yra ta, kad signalas gali būti gerai charakterizuotas kaip parametrinis atsitiktinis procesas, ir jo stochastinio proceso parametrai gali būni nustatyti tiksliai, gerai apibūdintai.

Įdomumo dėlei, nusakytas kalbos atpažinimas, abudu deterministiniai ir stochastiniai signalo modeliai turi didelį pasisekimą. Šitame straipsnyje mes orientuosimės į vieną stochastinį signalo modelį, kuris pavadintas paslėptas Markovo modelis (angliškai: hidden Markov model (HMM)). Pirmiausiai mes apžvelgsime Markovo grandinės teoriją ir ją plėsdami prieisime prie paslėpto Markovo modelio, panaudodami kelis pavyzdžius. Tuomet sutelksime savo dėmesį į tris fundamentines problemas, su kuriomis susiduriama projektuojant HMM: stebėjimo eilės tikimybės vertinimas specifiniam HMM; geriausios modelio būsenos eilės nustatymas; modelio parametrų apibrėžimas, siekiant gauti norimą signalo atsakymą. Mes parodysime, kad kai šios tris fundamentinės problemos yra išspręstos, mes galime taikyti HMM nurodytoms problemos spręsti balso atpažinimo sistemose.

Nei paslėpto Markovo modelio, nei balso atpažinimas nėra naujas dalykas. Pagrindinė teorija buvo paskelbta Baumo ir jo kolegų dar vėlyvais 1960, ankstyvais 1970 metais ir pritaikyta balso atpažinimo sprendimams Bakerio CMU ir Jelinek su kolegomis IBM 1970 metais. Tačiau, paplitęs supratimas ir HMM teorijos kalbos atpažinimo sprendimai pasirodė tik prieš kelerius metus. Tai nutiko dėl kelių priežasčių. Pirma, paslėptas Markovo modelis buvo publikuotas matematiniuose žurnaluose, kurie pagrinde nebuvo skaitomi inžinierių, kurie dirbo prie balso atpažinimo. Antra priežastis yra ta, kad pagrindiniai balso atpažinimo sprendimai nebuvo gerai dokumentuoti daugeliams vartotojų, todėl buvo sunku suprasti kokiu principu veikia sprendimas ir inžinieriai negalėjo perkelti modelio į savo tyrimus. Kuomet detalūs vadovai buvo išleisti, inžinieriai perkėlė teoretinį modelį savo laboratorijas. Šitas vadovas yra skirtas suteikti pagrindinės HMM teorijos apžvalgą (kaip ją pateikė Baumas ir jo kolegos), sutekti praktines teorinio metodo diegimo detales ir aptarti keletą nurodytų teoretinių aiškių problemų sprendimų pavyzdžių kalbos atpažinime. Vadovas sudeda iš kelių sudėtų straipsnių ir suteikia vientisą vadovą, kuris suteikia reikiamą užnugarį norint dirbti šios sferos tyrimų srityje.

Šis vadovas susideda iš sekančių sekcijų. Antroje sekcijoje mes apžvelgsime diskrečią Markovo grandinę ir parodysime paslėptos būsenos koncepciją, kur stebėjimas yra problematiška būsenos funkcija, gali būti efektyviai panaudota. Teoriją iliustruosime dvejais pavyzdžiais: monetos supimas, klasikinė kamuoliuko ir urnos sistema. Trečioje sekcijoje mes aptarsime tris fundamentines HMM problemas, ir suteiksime tris praktines technikas jas sprendžiant. Ketvirtoje sekcijoje mes aptarsime skirtinus HMM tipus, kurie buvo išstudijuoti: ergodinis ir kairys-dešinys modelius. Šioje sekcijoje mes taip pat aptarsime skirtingas modelio ypatybes, kaip stebėjimo skaičiaus funkcija, būsenos trukmės skaičius ir optimizavimo kriterijus, pasirenkant teisingas HMM parametrų reikšmes. Penktoje sekcijoje mes aptarsime problemas, kuris kyla diegiant HMM, kaip mastelio keitimas, pradinių parametrų sąmatos, modelio dydis, modelio forma, duomenų praradimas ir daugialypės stebėjimo seką. Šeštoje sekcijoje mes aptarsime izoliuotą žodžių iš balso atpažinimą, kuris yra suprojektuotas, naudojantis HMM idėjomis ir parodysime kaip jis elgiasi, lyginant su kitomis, alternatyviomis sistemomis. Septintoje sekcijoje mes išplėsime idėjas, aptartas šeštoje sekcijoje, ir pritaikysime jas sakinio atpažinimui. Tam mes jungsime atskirus, kiekvieno žodžio HMM modelius. Aštuntoje sekcijoje mes trumpai apžvelgsime didelį balso atpažinimo žodyną ir galiausiai, devintoje sekcijoje mes apibendrinsime visas idėjas, kurias aptarinėjome per visą vadovą.

Publikuojam pirmą savo knygą

Prieš rašydamas ( o tiksliau taisydamas ) esamą knygos variantą, noriu papublikuoti savo pirmą atvirai rašytą knygą. Išeities kodas visuomet buvo pasiekiamas Arch Linux Lietuva GitHub saugykloje. Realiai, knyga yra lietuviškas Beginners’ Guide variantas su keliais pridėjimais ( tiesa, šiuo metu perrašau esamą lietuvišką variantą wiki puslapyje į naujesnį ). Ateityje, kai turėsiu daugiau laiko, planuoju ją praplėsti ir pateikti ne vien tik vieno wiki puslapio lietuvišką variantą, o surinkti kiek galima daugiau informacijos apie Arch Linux naudojimą ir administravimą.

Kadangi tokios knygos neturi apčiuopiamos publikos, kuri galėtų ją pirkti, tai ją atiduodu nemokamai. Juk knygos atlieka informacijos saugojimo funkcija, o pinigai jau yra antraeilis dalykas. Be to, knyga yra parašta gan blogai, grubiai. Tai tik pirmas mano darbas, todėl noriu atsiprašyti tų, kurie tikisi rasti labai kokybiškai atliktą darbą.

Pirma gyvenimo svajonė beveik įvykdyta.