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:

1. Velja tvær stórar prímtölur $p$ og $q$ af handahófi, þannig að $p\neq q$.
2. Reikna $n=pq$.
3. Reikna $\phi (n)=(p-1)(q-1)$, þar sem $\phi$ er Eulers $\phi (n)$ fallið, sem skilar fjölda talna minni en $n$ sem eru ósamþátta við $n$.
4. Velja heiltölu $e$, þannig að $1<e<\phi (n)$, sem er ósamþátta $\phi (n)$.
5. Reikna $d$ þannig að $de\equiv 1{\pmod {\phi (n)}}$.

Þá er einkalykillinn talnaparið $(n,d)$ og almenningslykillinn er parið $(n,e)$. Þá sést að $d$ er leyndarmálið í þessu, enda er ekki hægt að finna út $d$ nema með því að reikna $p$ og $q$ út frá $n$, og finna svo rétt $k$ þannig að $d={\frac {k\phi (n)+1}{e}}$.

Reikniritið er svo skilgreint þannig:

$I^{l}=O{\pmod {n}}$

þar sem að $I$ er inntak, $O$ er úttak og $l$, lykillinn, fær gildið $l:=d$ ef að inntakið er dulkóðað en $l:=e$ ef dulkóða á inntakið. Dulkóðun fer þá fram með $T^{e}=C{\pmod {n}}$, þar sem að $T$ er textinn sem dulkóða á og $C$ er dulkóðað úttak, og afkóðun fer fram með sömu aðferð, sem leidd er út:

${\begin{matrix}C^{d}&=&(T^{e})^{d}\\&=&T^{ed}\\&=&T^{k\phi (n)+1}\\&=&(T^{\phi (n)})^{k}T\\&=&1^{k}\cdot T{\pmod {n}}\\&=&T{\pmod {n}}.\end{matrix}}$

sem byggist á Eulersreglu $T^{\phi (n)}=1{\pmod {n}}$, sem gengur bara upp ef að $T$ er ósamþátta $n$, 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 $n$ 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:

1. Finna nýja aðferð til þess að leysa þáttunarvandamál með $O(n)$ eða, ákjósanlega, $O(\log n)$ tímaflækju.
2. Með skammtatölvu ætti, samkvæmt kenningunni, að vera hægt að framkvæma allar hugsanlegar reikniaðgerðir á augnabliki. Það hefði í för með sér að þáttunarvandamál, hversu mikil sem stærðargráðan á $n$ er, yrðu nær óendanlega fljótleyst.

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.

Heimildir og ýtarefni

• Frumtexti úr RSA Afkóðun eftir Smára P. McCarthy. Notað með leyfi höfundar.
• A Method for Obtaining Digital Signatures and Public-Key Cryptosystems Geymt 27 janúar 2007 í Wayback Machine, upprunalega ritgerðin um RSA.
• The Code Book; Simon Singh; Anchor 2000; ISBN 0-385-49532-3
• Codes, Ciphers, and other Cryptic and Clandestine Communications; Fred B. Wrixon; Black Dog & Leventhal Publishers 1998; ISBN 1-57912-040-7
• Mathworld, Wolfram research, http://mathworld.wolfram.com