One-time pad

Në kriptografi, one-time pad (OTP) është një teknikë e enkriptimit që nuk mund të thyhët nëse përdoret siç duhet. Në këtë teknikë, një plaintext kombinohet me një çelës të rastit të fshehtë (që referohet edhe si one-time pad). Pastaj, çdo bit apo karakter i plaintext-it (tekstit të thjeshtë) enkriptohet duke e kombinuar atë me bitin apo karakterin korrespondues nga blloku duke përdorur shumën modulare. Nëse çelësi është me të vërtetë i rastit, është së paku i gjatë sa plaintext-ti, nuk ri-përdoret kurr në tërë pjesën, dhe mbahet plotësisht sekret, atëherë ciphertexti rezultues do të jetë i pamundur për t'u dekriptuar apo per t'u thyer. Gjithashtu është vërtetuar se çfarëdo cipher me vetinë e fshehtësisë së plotë duhet të përdorë çelësat me efektivitetin e kërkesave të njëjta si OTP çelësa. Sidoqoftë, problemet praktike kanë parandaluar one-time pads për t'u përdorur gjerësisht.

Fragment nga një one-time pad

Fillimisht përshkruar nga Frank Miller më 1882, one-time pad u ri-zbulua më 1971. Më 22 qershor, 1919, Shtetet e Bashkuara patentuan 1,310,719 u lëshua për Gilbert S. Vernam për XOR (ose eksklusive) operacionin e përdorur për enkriptimin e një blloku one-time pad.Është derivuar nga Vernam cipher, emëruar sipas Gilbert Vernam, një prej zbuluesve të tij. Sistemi i Vernam-it ishte një cipher që kombinonte një mesazh me një çelës lexuar nga shirit çelësi. Ne formën e vetë origjinale, sistemi i Vernam-it ishte i cenueshëm sepse çelësi prej shiriti ishte një cikël (diçka që përsëritej), që ripërdorej çdoherë kur shiriti bënte një cikël të plotë. Përdorimi i One-Time erdhi më vonë, kur Joseph Mauborgne vërejti që nëse shiriti i çelësit ishte plotësisht i rastit, atëherë kriptoanaliza do të ishte e pamundur.

Pjesa "pad" e emrit vjen nga një implementimin i hershëm, ku materiali i çelësit ishte i shperndarë si nje bllok (pad) prej letre, ashtuqë pjesa e sipërme e letrës mund te hiqej lehtë dhe te shkatërrohej pas përdorimit. Për lehtësinë e fshehjes, blloku ndonjëherë ishte i reduktuar në një pjesë aq të vogël saqë një çelq zmadhues i fuqishëm ishte i nevojshëm për t'a përdorur atë.KGB-ja përdorte "pads" të madhësive të tilla që ato të mund të përshtateshin në pëllëmbën e dores, apo në një lëvozhg arre. Për të rritur sigurinë, one-time pads ndonjëherë printoheshin ne fletë me nitrocelulozë të ndezshëm të lartë, në atë menyrë që ato të mund të digjeshin shpejt pas përdorimit të tyre.

Ka disa paqartësi në terme për shkak se disa autorë përdorin termat "shifër Vernam" dhe "One-Time pad", ndërsa të tjerët i referohen ndonjë rrjedhje të shifrës si një "shifër Vernam", duke përfshirë edhe ato të bazuara në një gjenerator pseudorandom të numërave kriptografikisht të sigurt (CSPRNG - Cryptographically Secure Pseudorandom Number Generator).

Historiku

Frank Miller në 1882 ishte i pari për të përshkruar sistemin one-time pad për sigurimin e telegrafisë.

Sistemi i ardhshëm i one-time pad ishte elektrikë. Në vitin 1917, Gilbert Vernam (i AT & T Corporation) shpiku dhe më vonë patentuar në 1919 (U.S Patent 1,310,719) një cipher i bazuar në teknologjinë teleprinter. Secili karakter në një mesazh të ishte e kombinuar në mënyrë elektrike me një karakter në një çelës kasetë letër. Joseph Mauborgne (atëherë një kapiten në ushtrinë amerikane) vërejti se sekuenca e karaktereve kyçe në kasetë mund të jenë krejtësisht të rastit, dhe, nëse po, kriptoanaliza do të jetë më e vështirë. Së bashku ata shpikën sistemin e parë të one-time pad.

Zhvillimi i ardhshëm ishte sistemi paper pad.Diplomatët kishin përdorur gjatë kodet dhe shifrat për konfidencialitet dhe për të minimizuar kostot telegrafike. Kodet, fjalët dhe shprehjet janë konvertuar në grupe të numrave (zakonisht 4 ose 5 shifra) duke përdorur një fjalor-si codebook. Për sigurinë e shtuar, numrat e fshehta mund të kombinohet me (përveç shumës modulare) çdo grup para transmetimit, me numrat e fshehtë duke u ndryshuar në mënyrë periodike (kjo u quajt superenkriptim). Në fillim të viteve 1920, tre kriptografë gjermanë (Werner Kunze, Rudolf Schauffler dhe Erich Langlotz), të cilët ishin të përfshirë në thyerjen e sistemeve të tilla, kuptuan se ata kurrë nuk do të mund të thyejnë atë në qoftë se një numër i veçantë i zgjedhur rastësisht shtesë është përdorur për çdo grup në kod. Ata kishin blloqe të kopjuar në letër të shtypura me linjat e grupeve të numrave të rastit. Çdo faqe ka pasur një numër serial dhe tetë linja. Çdo linjë kishte gjashtë numra 5-shifror. Një faqe do të përdoret si një fletë pune për të shifruar një mesazh dhe pastaj për të shkatërruar atë. Numri serial i faqes do të dërgohen me mesazhin e koduar. Marrësi do të ndryshojë procedurën dhe pastaj të shkatërrojë kopjen e tij të faqes. Zyra e jashtme gjermane vënë këtë sistem në veprim nga 1923.

Zbulimi i fundit ishte nga Claude Shannon në vitet 1940 që vërejtën dhe vërtetuan rëndësinë teorike të sistemit one-time pad. Shannon dorëzoi rezultatet e tij në një raport të klasifikuar në vitin 1945, dhe i botuar ato në mënyrë të hapur në vitin 1949. Në të njëjtën kohë, Vladimir Kotelnikov kishte vërtetuar në mënyrë të pavarur sigurinë absolute të one-time pad; rezultatet e tij u shpërndanë në vitin 1941 në një raport që me sa duket mbetet i klasifikuar.

Fshehtësia Perfekte

One-time pads janë "informacion-teorikisht i sigurtë" në atë menyrë që mesazhi i enkriptuar (psh. ciphertext-i) nuk ofron asnjë informacion në lidhje me mesazhin origjinal tek nje kriptoanalizues (me përjashtim të gjatësisë maksimale të mundshme të mesazhit).Ky është një nocion shumë i fortë i sigurisë i zhvilluar gjatë Luftës së Dytë Botërore nga Claude Shannon dhe provuar, matematikisht, të jetë e vërtetë nga Shannon për të njëjtën kohë. Rezultati i tij u botua në Gazetën Bell Labs Teknik në 1949. Përdorur siç duhet, one-time pads janë të sigurta në kuptimin edhe përkundër kundërshtarëve me fuqi të pafund kompjuterike.

Claude Shannon vërtetoi, duke konsideruar teorinë e informacionit, që one-time pad ka një veti te cilën ai e quajti Fshehtësi Perfekte; që është, ciphertext-i C nuk jep absolutisht asnjë informacion shtesë në lidhje me plaintext-in. Kjo ndodhë për shkak që, duke përdor një çelës vërtetë të gjeneruar në mënyrë të rastit që përdoret vetëm një herë, një ciphertext mund të përkthehet në çfarëdo plaintexti me gjatësi të njejtë, dhe të gjithë kanë të ngjarë të njejtë. Kështu, probabiliteti paraprak i një mesazhi plaintext M është i njëjtë me një probabilitet të një mesazhi plaintext M dhënë ciphertext-in përkatës. Matematikisht, kjo është e shprehur si H (M) = H (M | C), ku H (M) është entropia e plaintext-it dhe H (M | C) është entropia e kushtëzuar e plaintext-it që jep ciphertext-in C. Fshehtësia Perfekte është një nocion i fortë i vështirësisë kriptoanalizuese.

Algoritme konvencionale të enkriptimeve simetrike përdorin modele komplekse të zëvendësimit dhe transpozicionit. Për të mirën e tyre aktualisht në përdorim, nuk dihet nëse ka mundsi të jetë një procedurë kriptoanalitike e cila mund të zhbëjë (ose, në mënyrë të dobishme, pjesërisht të zhbëjë) këto transformime pa e ditur çelësin e përdorur gjatë enkriptimit. Algoritmet e enkriptimit asimetrik varen nga problemet matematikore që mendohet të jenë të vështira për t'u zgjidhur, siç është faktorizimi i një numëri të plotë dhe logaritme diskrete. Megjithatë nuk ka prova se këto probleme janë të vështira, dhe një përparim matematikorë mund të bëjë sistemet ekzistuese të prekshme për t'u sulmuar.

Duke pasur parasysh fshehtësinë e përsosur, në kontrast me enkriptimet simetrike, OTP është imun edhe për brute-force sulmet. Duke i provuar të gjitha çelësat thjeshtë jep të gjitha plaintext-et, e që të gjithë në mënyrë të barabartë kanë të ngjarë të jenë plaintext-i aktual. Edhe me plaintext të njohur, pra me pjesë të njohur të mesazhit, sulme si brute-force nuk mund të përdoren, pasi një sulmues nuk është në gjendje për të fituar ndonjë informacion në lidhje me pjesët kyçe të nevojshme për të dekriptuar pjesën tjetër të mesazhit.