Kriptografija je veda, ki se ukvarja z zaščito informacij, tako da jih zašifrira v neberljiv format, ki se imenuje šifriran tekst (ciphertext). Temu postopku pravimo šifriranje oziroma enkripcija podatkov. Samo tisti, ki imajo skrivni ključ lahko dešifrirajo sporočilo nazaj v navadni text (plain text). Postopku, ki spremeni šifrirano sporočilo nazaj v originalno pravimo dekripcija. Skrivni ključ je tisti delček informacije, ki nam omogoča dešifrirati neberljiv tekst nazaj v berljivega.

Primer enkripcije in dekripcije

Dekripcijo sporočila se navadno ne da izvesti brez skrivnega ključa. Matematika, ki se ukvarja z dekripcijo podatkov brez poznavanja skrivnega ključa se imenuje kriptoanaliza. Če s kriptoanalizo ugotovimo kakšen je skrivni ključ, pravimo da smo kodo zlomili in tako dešifrirali podatke. Temu postpoku pravimo tudi "codebreaking", vendar so moderne tehnike kriptografije že praktično nezlomljive.

Ker je elektronsko komuniciranje iz dneva v dan bolj razširjeno, postaja elektronska varnost vedno bolj pomembna. Kriptografija se uporablja za zaščito elektronskih sporočil, podatkov kreditnih kartic in ostalih pomembnih poslovnih informacij.

Za šifriranje podatkov obstajajo različni algoritmi. Glede na vrsto uporabljenih algoritmov imamo različnekriptografske sisteme:

• sisteme s simetričnim ključem, ki uporabljajo samo en ključ katerega imata pošiljatelj in prejemnik
• sisteme z asimetričnim ključem, ki uporabljajo dva ključa. Javni ključ (public key), ki je znan vsem in zasebni ključ (private key), ki ga pozna le prejemnik sporočila.

Algoritmom za šifriranje s simetričnim ključem (en skrivni ključ) pravimo private key encryption, saj morata pošiljatelj in prejemnik sporočila imeti enak skrivni ključ s katerim podatke zašifrirata in odšifrirata. Ta ključ mora ostati tajen, saj bi drugače lahko vsak dešifriral naše sporočilo.

Na sliki je prikazan princip simetričnega šifriranja. Uporabljen je enak ključ za enkripcijo in dekripcijo teksta.

V nadaljevanju si bomo ogledali, kako so se simetrični kriptografski algoritmi razvili skoz zgodovino.

Ena prvih in najbolj znanih kriptografskih šifer je bila Cezarjeva šifra. Sporočilo kodiramo tako, da vsako črko sporočila nadomestimo z neko drugo. To dobimo tako, da črke zamaknemo za neko dogovorjeno število. Temu številu (ki igra vlogo skrivnega ključa) rečemo alfabetični zamik.

PRIMER:

Na tej sliki smo vse črke zamaknili za tri v desno glede na angleško abecedo.

M je 13. črka po angleški abecedi. Črko pomaknemo po abecedi za 3 mesta v desno. Nova črka je 16. črka po angleški abecedi. Torej črko M zamenjamo s P.

M - 13 +3 = 16 -> P

A - 1 +3 = 4 -> D

T - 20 +3 = 23 -> W

...

Taka oblika šifriranja se je izkazala za precej šibko, saj jo z dovolj podatki zlahkoto zlomimo. Skrivnost je v frekvenci vsake črke jezika. Ko med seboj komuniciramo, nekatere črke uporabljamo bolj pogosto kot druge. Poglejmo si naslednja grafa.

Iz grafov lahko vidimo, da je uporabljen alfabetični zamik za 3 črke v desno. Res pa je, da bo izrazitost podobnosti grafov frekvenc odvisna od števila podatkov, ki smo jih prestregli. Več podatkov zašifriranih z enakim ključem prestrežemo, bolj izrazita bo postajala podobnost grafov frekvenc in skrivni ključ (alfabetični zamik) bo postal očiten. Tako lahko zlomimo Cezarjevo šifro in dešifriramo sporočilo.

Pogledamo frekvence posameznih črk v besedilu.

Program dobite na povezavi:Program za izris grafov frekvenc črk angleške abecede danega niza.

Vidimo, da je prvi graf bolj podobn grafu frekvenc črk angleške abecede.

Ko so ugotovili, da šifriranje s Cezarjevo šifro ni varno, so začeli uporabljati tako imenovano šifriranje s ključno besedo.

To šifriranje je potekalo tako, da so vsaki črki teksta priredili eno črko iz ključne besede. V primeru, da je bila dolžina teksta daljša od ključne besede, so za prirejanje ostalega dela teksta uporabili enako ključno besedo. Tako se je prirejanje ključne besede skozi besedilo ponavljalo. Tako ima vsaka črka teksta prirejeno svojo črko iz ključne besede. Nato vsaki črki teksta povečamo alfabetično vrednost za alfabetično vrednost prirejene črke ključne besede. Torej smo tekst alfabetično zamaknili za alfabetično vrednost posamezne črke v ključni besedi. Ključna beseda igra vlogo skrivnega ključa!

Poglejmo si primer šifriranja s ključno besedo "alice".

primer šifriranja teksta s ključno besedo "alice"

(ponovno je bila uporabljena angleška abeceda)

V primeru, da se prirejanje teksta s ključno besedo ni tako idealno izšlo (dolžina besede "matematika" je ravno 2x dolžina besede "alice"), so za prirejanje na koncu uporabili le del ključne besede.

Enkripcija oziroma šifriranje teksta je sedaj videti močnejša. Če bi sedaj pogledali porazdelitev frekvenc črk, bi videli manjša odstopanja med posameznimi frekvencami črk. Torej frekvenca črk bo bolj enakomerno porazdeljena. Ampak tudi tokrat je naše šifriranje za sabo pustilo sled informacij, ki omogoča dešifratorjem razvozlanje šifre, ne da bi poznali skrivni ključ (tem dešifratorjem pravimo ponavadi tudi codebreakerji). Ker se ključna beseda ponavlja skozi celoten tekst, frekvence črk še vedno niso enakomerno porazdeljene (še vedno pride do odstopanja med posameznimi frekvencami črk- je pa manj očitno kot pri Cezarjevi šifri).

Da razvozlamo to šifriranje, ne potrebujemo ključne besede same, ampak le njeno dolžino.To dobimo tako, da pregledujemo frekvence vsake n-te črke (iščmo ključno besedo dolžine n, ki se skozi šifriran tekst ponavlja). Iščemo tak n, da dobimo graf frekvenc, ki je podoben kakšnemu grafu frekvenc črk posameznega jezika (kot primer pri Cezarjevi šifri). Ko ugotovimo n (dolžina ključne besede), vemo katere črke v sporočilu so zakodirane z enakim alfabetičnim zamikom in tako to šifriranje razpade na več Cezarjevih šifer. Kot smo videli, je zlomiti Cezarjevo šifro precej trivialen problem.

Potrebno pa je povdariti, da je šibkost šifriranja s ključno besedo odvisna od števila podatkov, ki jih prestrežemo. Recimo, da bi prestregli samo del zakodiranega teksta npr.: N M C H R (iz primera na sliki). Ti podatki nam praktično ne povedo nič, saj je vsaka črka zamaknjena z različnim alfabetičnim zamikom in naš graf frekvenc bi bil popolnoma enakomerno porazdeljen. Tako nebi mogli sklepati nič iz danih informacij. Če pa bi prestregli daljše sporočilo, v katerem bi se ključna beseda ponovila večkrat, bi frekvence črk začele odstopati druga od druge (frekvence nebi bile več enakomerno porazdeljene in naše šifriranje bi za seboj pustilo sled, ki nam lahko izda algoritem šifriranja).

Iščemo toraj šifriranje, ki za seboj ne pusti informacij, s katerimi bi si lahko dešifrator pomagal.

IDEJA: Vsaki črki v sporočilu prirediti nek naključni alfabetični zamik. Frekvence zakodiranih črk bi morale biti sedaj enakomerno porazdeljene, saj je vsaka črka v zakodiranem tekstu enako verjetna. Tako ne uporabimo nobene ključne besede, ki bi omogočila dešifratorju razbrati iz šifriranega teksta kakšne vzorce oz. informacije o šifriranju.

Predstavljajmo si, da imamo 26 strano kocko, ki predstavlja alfabetične zamike angleške abecede. Za vsako črko sporočila vržemo kocko, ki nam da nek naključni alfabetični zamik.

Tako smo dobili seznam zamikov, ki so popolnoma naključni. Sedaj dešifrator v šifri ne bo mogel dobiti nobenega repetitivnega vzorca, kot je ponavljanje ključne besede, saj je naša šifra osnovana na dveh pomembnih lastnostih:

• naključni zamiki (v ozadju se ne skriva noben algoritem)
• frekvenca črk bo za dovolj veliko sporočilo zdaj za vse črke enaka, saj so vse enako verjetne, da se pojavijo (ker je alfabetični zamik določen naključno). Enkripcija ne bo za sabo pustila nobene sledi, ki bi dešifratorju omogočala razvozlanje kode.

To vrsto šifriranja imenujemo The one time pad. Paziti pa moramo, da je seznam naključnih zamikov enako dolg črkam sporočila ali daljši, saj tako nikoli ne pride do ponavljanja. Niti ne smemo enakega seznama večrkat uporabiti za šifriranje drugih sporočil, saj bi tako ustvarili repetitivni vzorec (kot da bi večkrat uporabili enako ključno besedo - to pa smo videli, da ni varno šifriranje).

V praksi se je izkazalo, da je generiranje popolno naključnih števil s stroji nemogoče, saj so deterministični in ne morejo zgenerirati popolnoma naključna števila brez zunanjega upliva (recimo vnosa uporabnika).

Izumili so tako imenovana psevdonaključna števila, ki so generirana s pomočjo posebnih algoritmov, ki simulirajo naključnost. Seznam teh števil je odvisen od začetnega stanja algoritma oz. izbire semena.

Poglejmo si en primer takega algoritma, kjer generiramo psevdonaključna števila s pomočjo kvadriranja:

V tem algoritmu smo za seme uporabili število 121 (začetno stanje oz. vrednost algoritma).

Več o tem algoritmu si lahko preberete na naslednji povezavi: Middle square method

Ker so to psevdonaključna števila, se bodo enkrat začela ponavljati, saj se bo enkrat neko število zaporedja ponovilo in zaporedje bo dobilo periodo. Dolžina periode je odvisna od izbire začetnega semena. Nekatera števila približno enake velikosti so sposobna zgenerirati dalješe zaporedje od ostalih. Največja možna dolžina periode je seveda enaka velikosti semena, saj bo vsako zaporedje dobilo svojo periodo. To pa ne pomeni nujno, da bo večje seme zagotovo zgeneriralo daljše zaporedje, kot manjše seme.

Glede na dolžino teksta, ki ga želimo šifrirati izberemo primerno veliko seme, ki bo tvorilo vsaj tako dolgo zaporedje naključnih alfabetičnih zamikov, kot je dolžina teksta. Tako bomo zagotovili, da pri šifriranju ne bo prišlo do ponavljanja zamikov in vzorcev (lahko si predstavljamo, da je to šifriranje s ključno besedo, ki je enaka ali večja od dolžine šifriranega teksta). Če bi uporabili zaporedje zamikov s neko periodo, bi namreč ustvarili šifriranje s ključno besedo. Za to šifriranje smo pa že pokazali da v splošnem ni varno.

Torej za varno šifriranje mora pošiljatelj zagotoviti, da izbrano seme tvori zaporedje z dovolj veliko periodo. Perioda zaporedja mora biti enaka ali večja od dolžine teksta, ki ga pošiljatelj želi zašifrirati. Prejemnik morata poznati seme in algoritem za tvorbo psevdonaključnih števil, da lahko razšifrirat sporočilo pošiljatelja.

Seme in algoritem psevdonaključnih števil pri One time padu predstavljata skrivni ključ.

• Cezarjeva šifra:

  • skrivni ključ - alfabetični zamik
  • šibka vrsta šifriranja, še posebej če je dolžina teksta velika

• šifriranje s ključno besedo:

  • skrivni ključ - alfabetični zamik posamezne črke ključne besede
  • s poznavanjem dolžine ključne besede, lahko ugotovimo v katerem jeziku je zapisan originalen tekst in tako razvozlamo šifro
  • šibkost te vrste šifriranja je odvisna od števila podatkov, ki smo jih uspeli prestreči in od števila ponovitev ključne besede v danem tekstu.
  • več podatkov prestrežemo, lažje zlomimo šifro
  • večkrat kot se ponovi ključna beseda v danem tekstu, lažje zlomimo šifro.

• ONE TIME PAD:

  • skrivni ključ - seme in algoritem za generiranje psevdonaključnih števil
  • šifriranje je varno, če je perioda zaporedja psevdonaključnih števil večja od dolžine teksta, ki ga šifriramo.
  • frekvenca črk je enaka, saj so alfabetični zamiki "naključni" in tako verjetnost črk enaka (črke so enakomirno porazdeljene).

Princip delovanja teh algoritmov je podoben. Pošiljatelj in prejemnik se skupaj dogovorita za skrivni ključ, s katerim bosta zašifrirala in razšifrirala tekst. Izbira skrivnega ključa mora ostati tajna, sicer bi vsak lahko razšifriral sporočilo. Ko je skrivni ključ izbran z njim pošiljatelj zašifriral sporočilo in ga pošlje. Ko ga prejemnik prejme ga z lahkoto razšifrira, saj pozna skrivni ključ. Če bi sporočilo prejela oseba, ki nebi poznala skrivnega ključa, bi dešifriranje sporočila bilo zelo težko (če je sporočilo smiselno zašifrirano).

V programskem jeziku Python sem napisal preprosti program, ki nam omogoča enkripcijo in dekripcijo sporočil.

Program si lahko prenesete tukaj: OTP enkripcija - program

KODA PROGRAMA:

Primer šifriranja sporočila s prikazanim programom:

Na naslednjih povezavah si lahko pogledate nekaj simetričnih algoritmov, ki delujejo na podobnih principih kot One time pad.

DEA, 3DES, AES, BLOWFISH...

Kot smo že omenili, morata imeti pošiljatelj in prejemnik enak skrivni ključ. Ker tehnologija računalnikov napreduje, se uporablja vedno večje skrivne ključe, ki nam omogočajo kompleksnejše enkripcije, da se zagotovi varnost šifriranja. Večji kot je ključ, več možnih enkripcij nam omogoča in tako zašifrirano sporočilo težje razšifrirati.

Razen DES algoritma so danes uporabljeni vsi našteti algoritmi. DES pa je nekoliko zastarel, saj ne omogoča ustvariti skrivnega ključa, ki bi bil dovolj velik, da bi bilo šifriranje varno.

Pravimo, da če je skrivni ključ večji od 80 bitov, potem je šifriranje varno.

Pri simetričnih algoritmih smo zahtevali, da imata pošiljatelj in prejemnik enak skrivni ključ, ki je namenjen šifriranju in dešifriranju.

Kaj pa se zgodi, če se pošiljatelj in prejemnik nikoli nista spoznala in si nista izmenjala skrivnega ključa, prek katerega bi lahko komunicirala v šifrah?

V tem primeru moramo uporabiti asimetrične algoritme.

Poglejmo si primer AES enkripcije, ki je trenutno ena najbolj popularnih simetričnih enkripcij.

Tukaj si lahko prenesete omenjen program za AES enkripcijo:AES enkripcija - program

// napisana koda je prireditev kode s spletne strani http://www.dreamincode.net/forums/topic/156922-aes-encryption-and-c%23/

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
// dodamo imenski prostor, ki nam bo omogočal delo z šifriranjem
using System.Security.Cryptography;

namespace AES
{
    class AES_cryptography
    {
        static void Main()
        {
            // definiramo spremenljivke, ki jih bomo potrebovali
            string Plain_Text;
            string Decrypted;
            string Encrypted_Text;
            byte[] Encrypted_Bytes;

            //razred Rijndael vsebuje skoraj vse metode, ki jih bomo potrebovali za šifriranje
            //ko pokličemo konstruktor se ustvari tako ključ in inicializacijski vektor (IV), ki nam omogoča uporabo istega ključa za večkratno šifriranje
            RijndaelManaged Crypto = new RijndaelManaged();

            //This is just here to convert the Encrypted byte array to a string for viewing purposes.
            System.Text.UTF8Encoding UTF = new System.Text.UTF8Encoding();

            Console.WriteLine("Vnesite tekst, ki ga želite zašifrirati:");
            Plain_Text = Console.ReadLine();

            try
            {
                // funkcija, ki vrne tabelo bytov, ki hrani šifrirane podatke
                // uporabljen mora biti enak ključ in inicializacijski vektor kot je biu uporabljen pri konstruktorju
                Encrypted_Bytes = encrypt_function(Plain_Text, Crypto.Key, Crypto.IV);
                // pretvorimo zašifrirane byte v niz, da ga lahko izpišemo kot zašifriran tekst
                Encrypted_Text = UTF.GetString(Encrypted_Bytes);
                // funkcija, ki vrne tabelo odšifriranih bytov
                // uporabljen mora biti enak ključ in inicializacijski vektor kot je biu uporabljen pri konstruktorju
                Decrypted = decrypt_function(Encrypted_Bytes, Crypto.Key, Crypto.IV);

                Console.WriteLine("Vnešen tekst: {0}", Plain_Text);
                Console.WriteLine("Encrypted: {0}", Encrypted_Text);
                Console.WriteLine("Decrypted: {0}", Decrypted);

            }
            catch (Exception e)
            {
                Console.WriteLine("Exception: {0}", e.Message);
            }

            Console.WriteLine("Pritisni enter za izhod");
            Console.ReadKey();

        }

        // funkcija, ki zašifrira podatke
        #region enkripcijska funkcija
        private static byte[] encrypt_function(string Plain_Text, byte[] Key, byte[] IV)
        {

            RijndaelManaged Crypto = null;
            MemoryStream MemStream = null;
            //I crypto transform uporabimo, da izvedemo enkripcijo oz. dekripcijo
            ICryptoTransform Encryptor = null;
            //Crypto streams omogoča enkripcijo v spominu - podeduje se iz MemoryStream namespaca.
            //Crypto steam potrebuje tri parametre: memory steam,  tip enkrpicije (ICryptoTransform) in Cryptographiv mode ("Write" - enkripcija oz. "Read" - dekripcija)
            CryptoStream Crypto_Stream = null;

            System.Text.UTF8Encoding Byte_Transform = new System.Text.UTF8Encoding();

            //tekst spremenimo v byte, saj večino kriptografskih funkcij potrebuje byte kot parameter
            byte[] PlainBytes = Byte_Transform.GetBytes(Plain_Text);

            try
            {
                Crypto = new RijndaelManaged();
                Crypto.Key = Key;
                Crypto.IV = IV;

                MemStream = new MemoryStream();

                //pokličemo metodo create encryptor ( potrebuje tako ključ kot IV, ki morajo biti iz originalnega klica Rijndael konstruktorja               //If these are changed nothing will work right.
                Encryptor = Crypto.CreateEncryptor(Crypto.Key, Crypto.IV);

                //v tej funkciji zapišemo podatke v spomin kjer bomo izvedli transformacijo (šifriranje)
                Crypto_Stream = new CryptoStream(MemStream, Encryptor, CryptoStreamMode.Write);

                //metoda write potrebuje tri parametre: podatke, ki jih zapisujemo (v bytih) , offset value (int) in dolžino streama (int)
                Crypto_Stream.Write(PlainBytes, 0, PlainBytes.Length);

            }
            finally
            {
                //če crypto blocks niso prazni, jih izpraznimo
                if (Crypto != null)
                    Crypto.Clear();
                // kot datoteko po pisanju zapremo
                Crypto_Stream.Close();
            }
            //iz spomina vrnemo tabelo zašifriranih bytov
            return MemStream.ToArray();
        }
        #endregion

        // funkcija, ki dešifrira zašifrirane podatke
        #region dekripcijska funkcija
        private static string decrypt_function(byte[] Cipher_Text, byte[] Key, byte[] IV)
        {
            RijndaelManaged Crypto = null;
            MemoryStream MemStream = null;
            //tokrat bomo potrebovali I crypto transform, da izvedemo dekripcijo
            ICryptoTransform Decryptor = null;
            CryptoStream Crypto_Stream = null;
            StreamReader Stream_Read = null;
            string Plain_Text;

            try
            {
                // nastavimo ključ in IV na originalne vrednosti (drugače dekripcija ne bo prava saj bo uporabljen drugačen skrivni ključ)
                Crypto = new RijndaelManaged();
                Crypto.Key = Key;
                Crypto.IV = IV;

                MemStream = new MemoryStream(Cipher_Text);

                // pokličemo metodo Create Decryptor, ki mora za parametre imeti originalni ključ in IV
                Decryptor = Crypto.CreateDecryptor(Crypto.Key, Crypto.IV);

                // ta funkcija iz spomina razbere zašifrirane podatke, jih odšifrira (uporabimo metodo Read - odšifriranje)
                Crypto_Stream = new CryptoStream(MemStream, Decryptor, CryptoStreamMode.Read);

                //uporabimo stream reader nad katerim kličemo metodo ReadToEnd (vrne niz)
                Stream_Read = new StreamReader(Crypto_Stream);
                Plain_Text = Stream_Read.ReadToEnd();
            }
            finally
            {
                // izpraznimo podatke iz spomina
                if (Crypto != null)
                    Crypto.Clear();

                MemStream.Flush();
                MemStream.Close();

            }

            return Plain_Text;
        }
        #endregion



    }
}

Za razliko od simetričnih algoritmon, asimetrični uporabljajo dva različna ključa. En je uporabljen za šifriranje podatkov, drugi pa za dešifriranje.

Ključ za dešifriranje je ponavadi skrivni in ga zato imenujemo zasebni oz. skrivni ključ.

Ključ za šifriranje pa je javni in zato do njega lahko dostopajo vsi, ki si želijo osebi pošiljati podatke. Imenujemo ga javni ključ.

Kot bomo videli, sta zasebni in javni ključ ponavadi v tesni povezavi.

Na sliki je prikazana enkripcija sporočila z javnim ključem, dekripcija pa z zasebnim.

Idejo asimetričnih algoritmov sta prvič objavila Diffi in Hellmann leta 1976.

Asimetrični algoritmi so idealni za uporabo v realnem svetu (skrivnega oziroma zasebnega ključa ni treba deliti s pošiljatelji in je tako manjša verjetnost, da se izve). Pri simetričnih algoritmin pa bi si morala pošiljatelj in prejemnik najprej varno izmenjati skrivni ključ.

Znani asimetrični algoritmi so RSA, DSA, ELGAMAL, DH,...

Mi si bomo v nadaljevanju podrobneje ogledali RSA algoritem.

Predstavljajmo si, da imamo dve osebi, ki si morata poslati sporočilo, a se ne moreta fizično srečati, da bi se dogovorila za skriti ključ s katerim bi sporočila zašifrirala.

Leta 1970 je britanski matematik James Alice prišel do preproste ideje, kako bi bilo to lahko mogoče. Predstavljajmo si navadno ključavnico. Odklepanje in zaklepanje ključavnice sta inverzni operaciji. Recimo da imamo dve osebi Alice in Bob, ki si želita izmenjati skrivno sporočilo.

Alice bi lahko kupila ključavnico s ključem in jo odklenjeno poslala Bobu, ključ pa bi obdržala. On bi svoje sporočilo zaklenil s ključavnico in poslal ključavnico in sporočilo nazaj do Alice. Če bi slučajno sporočilo kdo prestregel, ga nebi mogel odkleniti, saj ključa ni bilo zraven. Niti Bob, ko enkrat zaklene ključavnico je ne more več odpreti, saj ima samo Alice ključ za to specifično ključavnico.

Poglejmo si spodnjo skico:

Tako je Bob lahko poslal sporočilo brez Alicinega ključa.

Tako dobimo idejo:

• ključavnica, ki jo kupi Alice je namreč javni ključ, s katerim potem Bob zašifrira svoje sporočilo
• Alicin ključ, ki odklepa ključavnico, pa je zasebni ključ (le Alice ima dostop do tega ključa)

Torej recimo, da bi Alice kupila na tisoče enakih ključavnic (ki bi jih vse odpiral isti ključ). Vsak, ki bi se želel z Alice varno pogovarjati, bi moral vzeti eno izmed tistih odklenjenih Alicinih ključavnic.

Sedaj pa se vprašamo, kaj naj bi bil v dobi elektronskih komunikacij ustrezna zadeva, ki bi igrala vlogo ključa in kaj tisto, kar naj bi bila odklenjena klučavnica in kaj zaklepanje.

Potrebovali bomo "matematično ključavnico" oziroma funkcijo, ki jo je lahko izvršiti v eno smer v drugo pa težko (poiskati njen inverz).Takim funkcijam pravimo "one-way funkcije".

Zaklepanje ključavnice je lahka operacija, medtem ko odklepanje težka (brez ključa)

Rešitev je dobil matematik Clifford Cocks in sicer v iskanju ostankov.

Na sliki je prikazano, da je iskanje ostanka števila m na e-to potenco pri deljenju z številom N enostavno. Iskanje števila m pa težek.

Iskanje c-ja je časovno precej poceni postopek medtem ko je iskanje m-ja časovno zahteven postopek (ni znanega nobenega učinkovitega algoritma, ki bi to znal direktno izračunati).

To pomeni, da bo ta enosmerna funkcija (one-way funkcija) naša matematična ključavnica (v eno smer je lahka, v drugo pa težka). Zaklepanje pa bo izračun ostanka c.

Sedaj bomo podrobneje opisali asimetrični algoritem RSA, ki za matematično ključavnico uporablja omenjeno operacijo, ki nam vrne ostanke pri deljenju dveh števil (operacija modulo).

OPERACIJA MODULO - ta operacija poišče ostanek deljenja ene številke z drugo. Če imamo podani dve pozitivni števili, deljenec a in deljitelj n, potem je a mod n ostanek pri deljenju števila a z n.

PRIEMR: Izraz 7 mod 2 bi nam vrnil vrednost 1, saj nam deljenje števila 7 z 2 da koeficient 3 in ostanek 1 (7=2*3+1)

Še enkrat si oglejmo, kako bi potekal postopek, a tokrat z matematično ključavnico.

m - bobovo sporočilo pretvorjeno v število

c - zašifrirano sporočilo

e - javni ključ

d - zasebni ključ (se ga ne pošilja)

Prikazano je 'zaklepanje ključavnice' z operacijo modulo. Kaj pa je d?

Sedaj ko je naša matematična ključavnica zaklenjena, jo je težko nazaj odkleniti (ker je matematična ključavnica enosmerna funkcija). Da bo Alice lahko razšifrirala Bobovo sporočilo, bo potrebovala dodatne informacije, ki ji bodo omogočile, da bo inverz enkripcije preprosto izračunati. Tem informacijam ponavadi pravimo tudi TRAP DOOR. V splošnem pa je obratni postopek težek problem.

Alice lahko razšifrira Bobovo sporočilo (odklene ključavnico), ker pozna trap door.

d bo Alicin zasebni ključ, ki bo razšifriral Bobovo sporočilo. Njegov izračun bo moral biti odvisen od poznavanja trap doora. Torej če trap doora ne poznamo, ne moremo poiskati zasebnega ključa d in tako ne moremo odkleniti ključavnice (razšifrirati Bobovega sporočila).

Kot smo že ugotovili bo d Alicin zasebni ključ, saj bo z njim lahko dešifrirala sporočila, ki jih bo poslal Bob.

Poglejmo si nekaj izpeljav:

Tukaj se bomo obrnili na praštevila!

Kot vemo je praštevilo število, ki je deljivo samo z ena in samim sabo. Iskanje praštevil je še vedno časovno zahteven problem in zato posledično tudi faktorizacija sestavljenih števil.

Naša 2. One-way funkcija bo osnovana na časovni zahtevnosti faktorizacije števila (odvisna bo od poznavanja faktorjev).

Vemo, da je faktorizacija števila težja, če ima število malo faktorjev, zato bomo naše število N definirali kot zmnožek dveh približno enako velikih naključno generiranih praštevil (naše število bo imelo le dva faktorja - težko ga bo faktorizirati).

Da bo faktorizacija časovno prezahtevna tudi za superračunalnik morata biti izbrani praštevili vsaj 150-mestni števili.

Prikaz one-way funkcije -> faktorizacija števila N, kjer je N zmnožek dveh velikih praštevil.

To pomeni, da bo Alice tista, ki bo izbrala dve praštevili. Ko Alice naračuna N skrije njuna faktorja in javno razglasi številko N. Če bi kdorkoli želel ugotoviti faktorja števila N, bi potreboval več let, da bi prišel do odgovora.

Sedaj moramo še skonstruirati enosmerno funkcijo, ki bo odvisna od poznavanja faktorizacije N-ja.

Sedaj potrebujemo funkcijo, ki bo odvisna od poznavanja faktorjev števila N.

Uporabili bomo Eulerjevo funkcijo Phi.

Funkcija φ(n) je v teoriji števil multiplikativna aritmetična funkcija poljubnega pozitivnega celega števila n. Kot funkcijsko vrednost vrne skupno število pozitivnih celih števil z intervala [1,n], ki so tuja številu n.

Poglejmo si primer:

Torej če vemo, da je N produkt dveh praštevil p1 in p2, potem lahko φ(N) z lahkoto izračunamo:

φ(N)=φ(p1*p2)=φ(p1)*φ(p2)=(p1-1)*(p2-1) - sledi iz multiplikativnosti φ funkcije

Tako smo dobili trap door (poznamo p1 in p2 - to je tisti del informacije, ki ga ima samo Alice) za reševanje φ funkcije.

Vse kar moramo sedaj narediti, je povezati Eulerjevo φ funkcijo z operacijo modulo. Tu bomo uporabili Eulerjev teorem, ki prikazuje zvezo med φ funkcijo in operacijo modulo.

To pomeni, da mora biti d vedno Alicin zasebni ključ, saj je Alice edina, ki ga lahko naračuna (pozna trap door -faktorja števila N). Zasebni ključ d ji omogoča dešifrirati enkripcijo e-ja!

Poglejmo si sedaj RSA algoritem na primeru:

Kot smo videli, le Alice lahko dešifrira sporočilo, ker le ona pozna praštevili, ki sta produkt števila N.

• IDEJA: Pretvorimo vsako črko teksta v njeno ustrezno ASCII vrednost. Poglejmo si primer pretvorbe teksta v število s Pythonom.

pretvorba niza v seznam ustreznih ASCII vrednosti črk niza

Sedaj imamo sporočilo predstavljeno v številih. Vsako število seznama lahko sedaj z omenjenim RSA algoritmom zašifriramo v neko novo število. Če bomo to naredili za vsak element seznama s bomo naše originalno sporočilo zašifrirali. Naj bo seznam s' zašifriran seznam. Če bi vrednosti zašifriranega seznama s' pretvorili nazaj v niz, bi dobili neberljiv tekst. ASCII vrednosti so se z RSA algoritmom spremenile in tako ne predstavljajo več ustreznih črk, ki so bile del originalnega sporočila.

• V PRAKSI: najbolj popularni in zanesljiv algoritem za pretvorbo teksta v število, ki se uporabla skupaj z RSA, je Optimal asymmetric encryption padding. Več o tem si lahko preberete na sledeči povezavi: OAEP

• WIKIPEDIA

  • Kaj je kriptografija
  • Algoritem za simetrično šifriranje
  • http://en.wikipedia.org/wiki/Algoritmi za asimetrično šifriranje
  • Cezarjeva šifra
  • Šifriranje s ključno besedo
  • One time pad (OTP)
  • One-way funkcije
  • trapdoor funkcije
  • RSA algoritem
  • Eulerjeva phi funkcija

• FMF literatura: skripta za predmet algrabra in diskretna matematika (Primož Potočnik)

  • RSA algoritem in podoben primer
  • Eulerjeva funkcija
  • kongruenga in MOD funkcija

• AES koda v C#

• večina slik je bilo pobranih z interneta in prirejenih