RSA

RSA er dulmálskerfi sem byggist á notkun stórra prímtalna ásamt leifareikningi til þess að gera gögn ólæsileg öðrum en þeim sem hafa einkalykilinn.

RSA Reikniritið.

Til þess að notast við RSA reikniritið þarf fyrst að búa til lyklapar, þ.e. dreifilykil (e. "public key") og einkalykil (e. "private key"). Þetta er gert í fimm skrefum:

Þá er einkalykillinn talnaparið formula_15 og almenningslykillinn er parið formula_16. Þá sést að formula_13 er leyndarmálið í þessu, enda er ekki hægt að finna út formula_13 nema með því að reikna formula_1 og formula_2 út frá formula_8, og finna svo rétt formula_22 þannig að formula_23.

Reikniritið er svo skilgreint þannig:

þar sem að formula_25 er inntak, formula_26 er úttak og formula_27, lykillinn, fær gildið formula_28 ef að inntakið er dulkóðað en formula_29 ef dulkóða á inntakið. Dulkóðun fer þá fram með formula_30, þar sem að formula_31 er textinn sem dulkóða á og formula_32 er dulkóðað úttak, og afkóðun fer fram með sömu aðferð, sem leidd er út:

formula_33

sem byggist á Eulersreglu formula_34, sem gengur bara upp ef að formula_31 er ósamþátta formula_8, sem er óhugnanlega líklegt.

Saga RSA.

Whitfield Diffie, Martin Hellman og Ralph Merkle birtu Diffie-Hellman-Merkle dulmálskerfið árið 1976. Dulmálskerfið þeirra var þeim eiginleikum gætt að í stað eins dulmálslykils voru þeir tveir, og að dulmálskerfið var ósamhverft. Diffie og Hellman voru að íhuga einkalykladulmálsfræði (e. "Public Key Cryptography"), en Merkle var aðallega að skoða aðferðir til þess að dreifa dulmálslyklum. Þegar að þeir áttuðu sig á því að það væri margt skylt með vinnu hópanna þá samtvinnuðust hugmyndir þeirra þriggja, og þær birtust í grein að nafni "New Directions in Cryptography" í tímaritinu IEEE Transactions on Information Theory, sem var þó bara eftir Diffie og Hellman, og hefur kerfið verið kennt við þá síðan.

Hugmyndin þeirra var að það væri hægt að búa til stærðfræðilegar "fallgildrur", þ.e. aðferðir sem tættu gögn upp án þess að glata þeim, þannig að með réttu aukaílagi væri auðvelt að andhverfa þær, en annars væri það mjög torleyst.

RSA dulkóðunarreikniritið var afrakstur verka þriggja manna, Ronald Rivest, Adi Shamir and Leonard Adleman. Þeir birtu sameiginlega ritgerðina "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" árið 1977, en í henni lögðu þeir fram RSA dulmálið. Þeir byrjuðu að vinna að RSA eftir að Diffie og Hellman birtu sitt dulmálskerfi.

Rivest, Shamir og Adleman töldu að þó svo að aðferð Diffie-Hellman væri góð, þá væri hún ekki nógu góð, þar sem að það kerfi bauð eingöngu upp á dulkóðun, en ekki stafrænar undirskriftir. Þeir skoðuðu um fjörtíu mismunandi dulmálsaðferðir og römbuðu svo niður á notkun á margfeldi prímtalna sem einátta fall (e. "trapdoor one-way function").

RSA dulmálið var fyrst auglýst í ágúst 1977, í dálki í Scientific American þar sem að kerfinu var lýst í grófum dráttum. Þar buðust þeir félagar einnig til þess að senda hverjum þeim sem hafði áhuga afrit af ritgerð sinni, sem fór nokkuð fyrir brjóstið á þjóðaröryggisstofnun Bandaríkjanna, NSA, sem sá hversu öflugt þetta kerfi var og hversu hættulegt það yrði ef að þetta félli í óvinahendur. Þeir kröfðust þess að hætt yrði dreifingu dulmálskerfisins um leið, en það rann á daginn að ekki voru lagalegar stoðir til staðar fyrir slíkri kröfu. Þegar að greinin var svo birt í IEEE Transactions on Information Theory var leyndarmálið komið í mjög almenna umferð, og allar frekari tilraunir NSA til þess að hindra dreifingu þess voru úr sögunni.

Árið 2000 rann út einkaleyfi þeirra á RSA dulmálskerfinu í Bandaríkjum Ameríku, með þeim afleiðingum að nú geta allir heimsins íbúar notast við dulmálskerfið án endurgjalds. Margt hefur breyst síðan að RSA var birt, enda er búið að uppgötva marga galla og margar holur í reikniritinu sem gera það óöruggt. Enn fremur er búið að renna traustari stoðum undir einkalykladulmálskerfi með fyrirbærum á borð við OAEP, AES og Rijendel, ásamt því að RSA er komið í mun meiri almenna notkun með tilkomu PGP (e. "Pretty Good Privacy") kerfisins eftir Philip Zimmermann.

Ljóst er að RSA er ekki óbrjótanlegt dulmál, heldur er það frekar "torbrjótanlegt" - þ.e., að á meðan að aðferðir manna til þess að þátta tölur í frumþætti hafa ekki einfaldari tímaflækju en þær hafa í dag, þá er alltaf hægt að auka þannig á stærð lyklanna að talan formula_8 sé óþáttanleg innan raunhæfs tímaspans. Fræðimenn hafa nefnt tvo mjög góða möguleika til þess að gera RSA auðleysanlegt:

Vegna ótta manna við að hið síðarnefnda yrði að veruleika var þróuð skammtafræðilega örugg aðferð til þess að skiptast á lyklum, og yrði þá hægt að notast við OTP (e. "One Time Pad") dulkóðun í stórum stíl, sem yrði fullkomnlega öruggt.