Gjenerimi i Numrave Random në Kriptografi

Nga Wikipedia, enciklopedia e lirë
Jump to navigation Jump to search

Abstrakt

Ky material fokusohet në përdorimin e numrave të rastësishëm në kriptografi, rëndësinë e këtyre numrave në këtë fushë dhe metodat e gjenerimit të tyre. Dy kategoritë kryesore të metodave të gjenerimit të numrave random janë metodat fizike dhe ato llogaritëse (aritmetike). Më vonë kuptojmë se me metoda aritmetike nuk është e mundur të gjenerojmë numra vërtetë të rastësishëm, por vetëm numra (të pseudo-rastësishëm) të cilët i përafrohen atyre. Kualiteti i një algoritmi përcaktohet saktësisht nga kjo veti. Metodat fizike, duke përdorur vetë fenomenet fizike, sjellin rezultate më të kënaqshme dhe sekuenca më reale të numrave random.

Si rrjedhojë e rëndësisë së tyre, studiuesëve të kësaj lëmie i është paraqitur një sfidë e gjetjes së një zgjidhjeje e cila i afrohet sa më shumë një algoritmi “perfekt” për gjenerimin e numrave vërtetë të rastësishëm. Përpjekjet për të arritur këtë qëllim kanë qenë të shumta dhe kanë rezultuar në krijimin e një numri të madh të algoritmeve, me kualitete të ndryshme.

1 Hyrje

Numrat e rastësishëm kanë përdorim të gjerë në shumë fusha shkencore apo qoftë edhe për argëtim. Do të ishte shumë mirë për algoritmet kriptografike nëse numrat e rastësishëm të përdorur aty janë numra vërtetë të rastësishëm. Rezultatet nuk do të mund të riprodhoheshin dhe siguria do të ishte maksimale. Mirëpo realiteti funksionon ndryshe dhe metodat për gjenerimin e këtyre numrave janë të rralla. Dikush mund të mendojë që mënyra më e mirë për të krijuar numra të rastësishëm është që të pëdorim një algoritëm “të rastit” i cili kryen një varg të operacioneve të llojllojshme (matematikore, logjike) me qëllim të nxjerrjes së një numri të rastësishëm.

Formulimi i këtyre algoritmeve është më vështirë se që duket dhe sekuencat e numrave të rastësishëm të gjeneruar nga këto algoritme eventualisht fillojnë të përsëriten apo të shfaqin algoritmet prapa tyre.

Numrat që duken si numra vërtetë të rastësishëm e që në esencë nuk janë, njihen me termin pseudo-random.

Pasi që numrat vërtetë të rastësishëm nuk mund të gjenerohen nga proceset e paracaktuara, idea kryesore është që gjenerimi i numrave të pseudo-rastësishëm t’i përafrohet sa më shumë procesit të gjenerimit të numrave vërtetë të rastësishëm.

2 Përmbajtja


2.1 Numrat e rastësishëm

Numrat e rastësishëm janë numra të cilët gjenerohen nga procese të rastësishme në natyrë që ndikohen nga faktorë të pamundshëm për t’u përcaktuar.

Numrat e rastësishëm (random) kanë përdorim të gjerë ne eksperimente statistikore, në algoritme të tjera të gjenerimit të numrave të rastësishëm dhe posaçërisht në kriptografi.

2.1.1 Numrat e pseudo-rastësishëm

Që nga fillimi i kompjuterizimit, është paraqitur sfida e gjenerimit të numrave të rastësishëm me anë të algoritmeve. Problemi qëndronte te fakti se asnjë numër “i rastësishëm” i gjeneruar nga proceset kompjuterike nuk është numër vërtetë i rastësishëm. Këta numra i quajmë numra të pseudo-rastësishëm.

Numrat e pseudo-rastësishëm duken si numra të gjeneruar në mënyrë të rastësishme, mirëpo në realitet prapa procesit të gjenerimit të tyre qëndron një algoritëm që bën caktimin e tyre. Kjo është arsyeja pse këta numra quhen të pseudo-rastësishëm (‘ pseudo’ – ‘ jo real’). Përdorimi i proceseve të pseudo-rastësishme rezulton në pseudo-siguri. Edhe pse këta numra nuk janë numra vërtetë të rastësishëm, në shumicën e aplikacioneve mund të përdoren si të tillë.

2.1.2 Gjeneratorët e numrave të rastësishëm

Një gjenerator i numrave të rastësishëm (apo shkurt RNG) është një pajisje llogaritëse apo fizike e dizajnuar për të gjeneruar një sekuencë të numrave apo simboleve me strukturë kaotike. PRNG (Pseudo-random number generator) - Këto lloje të gjeneratorëve përfshijnë algoritme të cilat bazohen në formula matematikore. Numrat e gjeneruar nga këto algoritme duken si numra vërtetë të rastësishëm, por në esencë janë të predeterminuara.

TRNG (True random number generator) - Në krahasim me PRNG, gjeneratorët e numrave vërtetë të rastësishëm ekstraktojnë rastësinë nga fenomenet fizike dhe ia pasojnë kompjuterit.


2.4 Numrat e rastësishëm në kriptografi

Sistemet e sotme të sigurisë themelohen mbi baza të forta të algoritmeve kriptografike të cilat zhvillohen vazhdimisht dhe bëjnë të pamundur gjetjen e një modeli apo përsëritje (ang. pattern) prapa kodeve të tyre. Në zemër të të gjitha sistemeve kriptografike është gjenerimi i numrave sekret dhe të rastësishëm.

Mirëpo, siguria e këtyre sistemeve varet nga vetë gjenerimi i çelësave apo fjalëkalimeve të tyre. Një sulmues i sistemit mund ta ketë shumë të lehtë të riprodhojë mjedisin që ka bërë gjenerimin nëse gjenerimi ka qenë i dobët.

Shumë aspekte të kriptografisë kërkojnë numra të rastësishëm, si: • Gjenerimi i çelësave • One-time pad • Gjenerimi i salt-it • Nonce (number used only once) • Vektori i inicializimit • Bajtat e padding-ut Kushtet e kualitetit të numrave të rastësishëm për këto aplikacione ndryshojnë. Për shembull, në disa protokole është më shumë e rëndësishme që këta numra të jenë unik se sa që të jenë të rastësishëm. Mirëpo në anën tjetër, p.sh. te enkriptimi me one-time pad, do të kemi fshehtësi të të dhënave vetëm nëse numrat janë vërtetë të rastësishëm. Një vërtetim i rëndësisë së madhe të përdorimit të këtyre numrave në kriptografi është rasti i gjenerimit të çelësave (publik dhe privat) në RSA (Rivest-Shamir-Adleman). Nëse për gjenerimin e parametrave fillestare për krijimin e një çelësi (publik apo privat) përdorim një algoritëm i cili nuk përmbush kushtet për numra kriptografikisht të sigurt , atëhere rrezikojmë sistemin e sigurisë së komunikimit. Rreziku qëndron te fakti se një sulmues, duke përdorur këtë pikë të dobët, mund të riprodhojë parametrat fillestar duke dhënë hyrjen e njëjtë. Enkriptimi me one-time pad (OTP) është enkriptim i cili bazohet plotësisht në rastësinë e çelësit. Është vërtetuar se thyerja e këtij enkriptimi është e pamundshme nëse çelësi i përdorur është vërtetë i rastësishëm. Sa më shumë që i largohemi këtij kushti, aq më i pasigurt do të jetë enkriptimi. Fjalëkalimi është një shembull tipik i një sekuence të numrave të rastësishëm, zakonisht në formë stringu. Por natyrisht, nuk ofron siguri të mirë nëse është i lehtë për t’u qëlluar.

2.5 Format e gjenerimit


2.5.1 Metodat fizike

Metodat më të hershme për gjenerimin e numrave random – hudhja e zarit, monedhës, ruleti – janë ende në përdorim sot e kësaj dite, kryesisht nëpër lojëra dhe bixhoz pasi që janë shumë të ngadalshme për shumicën e aplikacioneve në statistikë dhe kriptografi. Mekanika kuantike është metoda më moderne, poashtu dhe metoda më funksionale për gjenerimin e numrave random dhe kjo mbështetet nga fakti se në bazë të ligjeve të kësaj fushe është prodhuar gjeneratori i parë i numrave vërtetë të rastësishëm (në vitin 2010). Burimet e entropisë (gjendjeve jostabile) përfshijnë zbërthimet radioaktive, zhurmat e ndryshme të shkaktuara nga proceset fizike, apo edhe matja e kohës së kokës për lexim dhe shkrim në hard disk. Të gjitha këto janë burime të mundshme për gjenerimin e numrave të rastësishëm. Mirëpo, aparetet për matjen e këtyre burimeve paraqesin konflikte të ndryshme që pengojnë rezultatet e sakta. Një burim tjetër i numrave random do të ishte një “nxjerrës” i rastit, si p.sh. hash funksionet, që mund të përdoren për fitimin e një sekuence unike të bitave nga një burim jo-unik. Ka edhe shumë mënyra të ndryshme për nxjerrjen e numrave random. Një teknikë e tillë do të ishte ekzekutimi i hash funksionit ndaj një video stream që vjen nga një burim i paparashikuar, apo edhe gjenerimi i numrave nga zhurma atmosferike e inçizuar nga një radio. Edhe vetë njeriu paraqet një burim të këtyre numrave per shkak se vetë sjellja e njeriut është e paparashikuar. Një shembull tipik që vlen të theksohet është lëvizja e mausit.

2.5.2 Metodat llogaritëse

“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.” – John von Neumann John von Neumann ka theksuar se nuk duhet bazuar në metoda aritmetike për gjenerimin e numrave random, por e vetma zgjidhje është përdorimi i proceseve fizike për gjenerimin e këtyre numrave. Për të argumentuar të kundërtën, Donald Knuth ka provuar një algoritëm të tillë dhe rezultatet nuk kanë qenë të kënaqshme. Gjatë procesit të gjenerimit, sekuenca e numrave të rastësishëm ka hasur në një pikë të konvergjimit, ku filloi të dukej algoritmi prapa saj. Pas kësaj prove erdhi në përfundim se mënyra më e mirë e gjenerimit të numrave të rastësishëm është që të përdoret shkenca dhe t’i kushtohet një kujdes i vecantë krijimit të një algoritmi për qëllim të tillë.

Në kategorinë e metodave llogaritëse bëjnë pjesë gjeneratorët e numrave pseudo-random (PRNG) të cilët automatikisht krijojnë sekuenca të gjata të numrave me veti të mira të rastësisë por eventualisht do të përsëriten. Kjo është dobësia e këtyre sistemeve. Një seri e vlerave të gjeneruara nga një algoritëm i tillë në pergjithësi është e përcaktuar nga një numër fillestar fiks i quajtar seed (shq. farë). Një metodë e thjeshtë për gjenerimin e numrave random është ajo e John von Neumann e quajtur middle square method (metoda e katrorit të brendshëm) e cila funksionon kështu: Numri i zgjedhur ngritet në katror, pastaj marrim shifrat të cilat gjenden në mes të rezultatit të fituar pas ngritjes në katror të numrit te zgjedhur. Numrat e zgjedhur nga mesi duhet të jenë po aq shifror sa numri fillestar. Shumica e gjuhëve të programimit, në kornizat e tyre, përmbajnë librari ku janë të definuara gjeneratorët e numrave të rastësishëm. Funksionet e këtilla kanë veti të dobëta dhe fillojnë të përsëriten përafërsisht pas dhjetra mijëra numrash të gjeneruar. Si vlerë inicializuese (seed), zakonisht përdoret koha reale e kompjuterit.

2.5.3 Numrat random në kornizën .NET

.NET Framework përmban këto klasa për gjenerimin e numrave random: • Klasa Random • Klasa RandomNumberGenerator (System.Security.Cryptography) • Klasa RNGCryptoServiceProvider (System.Security.Cryptography) Klasa Random nuk përdorët në kriptografi (ose së paku nuk sugjerohet) për arsye se nuk gjeneron numra kriptografikisht të sigurt. Gjenerimi i numrave random nga kjo klasë fillon me një vlerë fillestare. Në qoftë se kjo vlerë fillestare përdoret vazhdimisht atëherë do të gjenerohen sekuenca të njejta.