Dreifilyklar og RSA

Í samhverfri dulritun þurfa Anna og Bjarni að deila sama leynda lyklinum. Það er þægilegt þegar þau þekkjast fyrir, en vandasamt þegar Anna vill fyrst tengjast vefþjóni sem hún hefur aldrei talað við.

Hvernig getur Anna sent Bjarna leyndarmál svo hann einn geti lesið það, án þess að þau hafi áður skipst á lykli?

Lausnin er ósamhverf dulritun (e. asymmetric cryptography), sem notar lykilpar:

dreifilykill (e. public key) má deila með öllum,
einkalykill (e. private key) á að vera leyndarmál eigandans.

Dreifilykillinn og einkalykillinn eru stærðfræðilega tengdir, en þannig að það á að vera óframkvæmanlegt að finna einkalykilinn út frá dreifilyklinum þegar notaðar eru nægilega stórar tölur.

Ósamhverf dulritun er yfirleitt hægari

Í raunverulegum kerfum notum við oft ósamhverfa dulritun til að koma á öruggu sambandi eða deila litlum leyndum lykli. Síðan notum við hraða samhverfa dulritun til að vernda stóru gögnin. Þetta kallast blönduð eða tvinnuð dulritun og við sjáum dæmi um hana þegar við skoðum HTTPS.

Lás sem allir mega læsa

Hugsum okkur hengilás sem Anna setur í opna glugga:

Anna býr til lykilpar.
Hún setur hengilásinn — dreifilykilinn — á vefinn.
Bjarni sækir dreifilykilinn.
Bjarni læsir skilaboði í kassa með dreifilyklinum.
Aðeins Anna getur opnað kassann með einkalyklinum sínum.

Bjarni                           Anna
  │                                │
  │ sækir dreifilykil ────────────►│
  │                                │
  │ dulritar með dreifilykli       │
  └──────── dultexti ─────────────►│
                                   │ dulráðir með einkalykli

Þetta er frábrugðið samhverfri dulritun: Bjarni þarf ekki að fá leynilegan lykil frá Önnu áður en hann getur sent fyrsta skilaboðið.

Æfing: hvor lykillinn?

Æfing 1

Anna vill senda Bjarna leynd skilaboð. Bjarni vill svo svara Önnu með öðru leyndu skilaboði.

Hvaða lykil notar Anna til að dulrita skilaboð til Bjarna?
Hvaða lykil notar Bjarni til að dulráða þau?
Hvaða lykil notar Bjarni til að dulrita svar til Önnu?
Hvaða lykil notar Anna til að dulráða svarið?

Lausn við æfingu 1

Anna notar dreifilykil Bjarna. Hann má vera opinber og allir mega nota hann til að læsa skilaboðum til Bjarna.
Bjarni notar einkalykil sinn til að opna skilaboðin.
Bjarni notar dreifilykil Önnu til að læsa svarinu.
Anna notar einkalykil sinn til að opna svarið.

Það mikilvægasta er að rugla ekki saman eiganda lykilsins og þeim sem sendir skilaboðin. Við notum dreifilykil viðtakandans til að tryggja að aðeins viðtakandinn geti dulráð.

RSA í stuttu máli

RSA er eitt þekktasta dæmið um ósamhverfa dulritun. Heitið er myndað úr upphafsstöfum höfunda þess: Ron Rivest, Adi Shamir og Leonard Adleman.

RSA byggir á einfaldri hugmynd:

velja tvær stórar frumtölur,
margfalda þær saman,
nota niðurstöðuna sem hluta af báðum lyklum,
nota mismunandi veldisvísa til að dulrita og dulráða.

Við notum litlar tölur til að skilja ferlið. Litla dæmið er ekki öruggt; það er bara reikningsæfing.

Smíðum leikfangs-RSA

Við notum eftirfarandi tákn:

p og q eru frumtölur,
n = p · q er módúlus (e. modulus),
e er opinber veldisvísir,
d er leynilegur veldisvísir.

Skref 1: veljum frumtölur

Veljum:

p = 3
q = 11

Þá er:

n = p · q = 3 · 11 = 33

Í alvöru RSA væru p og q gríðarlega stórar frumtölur. Hér eru þær litlar svo við getum reiknað með þeim sjálf.

Skref 2: finnum φ(n)

Fyrir tvær ólíkar frumtölur er:

φ(n) = (p - 1)(q - 1)

Í dæminu okkar:

φ(33) = (3 - 1)(11 - 1)
      = 2 · 10
      = 20

Við þurfum ekki að kafa djúpt í alla eiginleika φ-fallsins í þessum kafla. Hér nægir að vita að þessi tala hjálpar okkur að velja e og reikna d.

Skref 3: veljum opinbera veldisvísinn

Við veljum e þannig að e eigi engan sameiginlegan deili með 20:

gcd(3, 20) = 1

Við veljum því:

e = 3

Skref 4: finnum leynda veldisvísinn

Við þurfum að finna d þannig að:

e · d ≡ 1 (mod φ(n))

Það þýðir í dæminu:

3 · d ≡ 1 (mod 20)

Úr fyrri kafla vitum við að margföldunarandhverfa 3 modulo 20 er 7:

3 · 7 = 21 ≡ 1 (mod 20)

Því er:

d = 7

Lykilparið

RSA-lyklarnir okkar eru þá:

Dreifilykill: (n, e) = (33, 3)
Einkalykill:  (n, d) = (33, 7)

Í alvöru kerfi þyrfti að vernda p, q og d. Dreifilykillinn (33, 3) má vera opinber.

Æfing: smíða lítið lykilpar

Æfing 2

Notaðu:

p = 5
q = 7
e = 5

Reiknaðu n.
Reiknaðu φ(n).
Finndu d þannig að 5 · d ≡ 1 (mod φ(n)).
Skrifaðu dreifilykilinn og einkalykilinn.

Lausn við æfingu 2

n = 5 · 7 = 35.
φ(n) = (5 - 1)(7 - 1) = 4 · 6 = 24.
Við leitum að margföldunarandhverfu 5 modulo 24. Talan 5 virkar:

5 · 5 = 25 ≡ 1 (mod 24)

Því er d = 5. 4. Lykilparið verður:

Dreifilykill: (n, e) = (35, 5)
Einkalykill:  (n, d) = (35, 5)

Í þessu litla dæmi verða gildin e og d eins. Það er ekki vandamál fyrir reikningsæfinguna, en slíkar litlar tölur eru alls ekki öruggar.

RSA-dulritun og dulráðning

Í RSA er skilaboðunum fyrst breytt í tölu m sem er minni en n. Síðan eru notuð þessi föll:

Dulritun:  c = mᵉ mod n
Dulráðning: m = cᵈ mod n

c er dultextatalan.

Sýnidæmi: dulrita töluna 4

Við notum lykilparið:

n = 33
e = 3
d = 7

Látum skilaboðið vera m = 4.

Dulritun:

c = 4³ mod 33
  = 64 mod 33
  = 31

Dultextinn er 31.

Dulráðning:

m = 31⁷ mod 33

Við getum reiknað þetta í Python:

>>> pow(31, 7, 33)
4

Við fáum upphaflegu skilaboðatöluna 4 aftur.

Sýnidæmi: sama dæmi í Python

p = 3
q = 11
n = p * q
e = 3
d = 7

skilabod = 4
dultexti = pow(skilabod, e, n)
upprunalegt = pow(dultexti, d, n)

print(dultexti)   # 31
print(upprunalegt)  # 4

pow(a, b, n) er mikilvægt hér vegna þess að það reiknar aᵇ mod n skilvirkt. Við viljum ekki fyrst búa til allar tölurnar sem felast í stóru veldi.

Æfing: dulrita með leikfangs-RSA

Æfing 3

Notaðu:

n = 33
e = 3
d = 7
m = 2

Reiknaðu dultextann c.
Dulráðaðu c aftur.

Lausn við æfingu 3

Dulritun:

c = 2³ mod 33
  = 8 mod 33
  = 8

Dulráðning:

pow(8, 7, 33)
# 2

Við fáum m = 2 aftur.

Dæmið virkar vegna þess að d var valið sem rétt margföldunarandhverfa e miðað við φ-gildið. Í alvöru RSA eru tölurnar svo stórar að enginn reiknar þær handvirkt.

Af hverju er þetta erfitt að brjóta?

Allir mega sjá n og e. Til að finna d þurfum við í grundvallaratriðum að vita φ(n). Til að finna hana úr n þurfum við að finna frumþættina p og q:

n = p · q

Ef p og q eru litlar er auðvelt að prófa möguleika:

33 = 3 · 11

Ef p og q eru hundruð stafa að lengd verður frumþáttun n mjög erfið með þekktum aðferðum og venjulegum tölvum.

Stórar tölur einar og sér tryggja ekki öryggi

RSA þarf rétta lyklastærð, örugga fyllingu, góða slembni og rétta útfærslu. Lítið RSA-dæmi getur verið stærðfræðilega rétt en samt algjörlega óöruggt.

RSA er ekki bara til að fela skilaboð

Lykilpar má nota í gagnstæðri átt til að búa til stafræna undirskrift (e. digital signature).

Hugmyndin er:

Sendandinn reiknar tætigildi af skeytinu.
Sendandinn notar einkalykil sinn til að búa til undirskrift úr tætigildinu.
Sendandinn sendir skeytið og undirskriftina.
Viðtakandinn notar dreifilykil sendandans til að sannreyna undirskriftina.

Skeyti ──► Tætifall ──► einkalykill ──► undirskrift
   │                                      │
   └────────────── skeyti + undirskrift ──┘

Dulritun með dreifilykli svarar spurningunni:

Getur aðeins réttur viðtakandi lesið þetta?

Undirskrift með einkalykli svarar spurningunni:

Get ég sannreynt að þetta hafi verið búið til af eiganda einkalykilsins og ekki breytt?

Sýnidæmi: undirskrift í leikfangs-RSA

Notum sama litla lykilpar:

Dreifilykill: (n, e) = (33, 3)
Einkalykill:  (n, d) = (33, 7)

Til einföldunar segjum við að tætigildi skeytisins sé m = 4.

Sendandinn býr til undirskrift:

s = mᵈ mod n
  = 4⁷ mod 33
  = 16

Viðtakandinn sannreynir:

sᵉ mod n = 16³ mod 33 = 4

Niðurstaðan 4 passar við upphaflega tætigildið. Í raunverulegu RSA eru notaðar sérstakar fyllingar og staðlaðar aðferðir, en hugmyndin um „einkalykill til að skrifa undir, dreifilykill til að sannreyna“ er sú sama.

Æfing: undirskrift eða leynd?

Æfing 4

Veldu hvaða lykil á að nota í hverju tilviki:

Bjarni vill senda Önnu leynd skeyti.
Anna vill búa til undirskrift sem allir geta sannreynt.
Bjarni vill sannreyna undirskrift Önnu.
Anna vill dulráða leynd svar Bjarna.

Veldu úr: dreifilykill Önnu, einkalykill Önnu, dreifilykill Bjarna, einkalykill Bjarna.

Lausn við æfingu 4

Bjarni notar dreifilykil Önnu. Þá getur aðeins Anna, með einkalykli sínum, dulráð.
Anna notar einkalykil Önnu. Undirskriftin sýnir að hún hafi haft aðgang að einkalyklinum.
Bjarni notar dreifilykil Önnu til að sannreyna undirskriftina.
Anna notar einkalykil Önnu til að dulráða skeytið sem var dulritað með dreifilykli hennar.

Sama lykilpar getur því tengst bæði leynd og undirskriftum, en notkunin og stefnan eru ólík. Í raunverulegum kerfum notum við staðlaðar aðferðir fyrir hvort verkefni.

Ekki „undirskrifa“ hrá gögn með RSA

Raunveruleg RSA-undirskrift undirritar yfirleitt tætigildi með tiltekinni fyllingu, ekki einfaldlega frumtextann með mᵈ mod n. Leikfangsformúlan er góð til að skilja hugmyndina en ekki til að skrifa öruggan kóða.

Vottorð: hver á dreifilykilinn?

Dreifilykillinn þarf ekki að vera leyndur, en við verðum að vita hverjum hann tilheyrir. Annars gæti Marta sett sinn eigin dreifilykil á milli Önnu og Bjarna.

Bjarni heldur að hann sé að nota dreifilykil Önnu
Marta sendir í raun sinn eigin dreifilykil
Marta getur þá lesið skilaboðin

Til að leysa þetta vandamál eru notuð stafræn vottorð (e. certificates). Vottorð tengir dreifilykil við lén eða auðkenni og er undirritað af aðila sem aðrir treysta.

Vottunarstöð (e. Certificate Authority, CA) er aðili sem gefur út slík vottorð samkvæmt ákveðnum reglum. Vafri getur til dæmis athugað hvort vottorð vefsvæðis:

eigi við um rétta lénið,
sé enn í gildi,
sé undirritað af traustri vottunarstöð,
hafi ekki verið afturkallað eða orðið ógilt.

Þetta er hluti af því sem gerist þegar við tengjumst HTTPS-vef. Við þurfum ekki að treysta handahófskenndum lykli sem kemur bara frá netinu; við þurfum keðju trausts.

Vissir þú?

Hugmyndin að baki RSA var einnig uppgötvuð hjá bresku leyniþjónustunni GCHQ árið 1973 af Clifford Cocks. Uppgötvunin var leynd þar til löngu síðar, svo Rivest, Shamir og Adleman fengu almennt heiðurinn af aðferðinni þegar hún var birt opinberlega.

RSA í gagnaglímum

Í einföldum CTF-verkefnum getur RSA verið viljandi veikt. Algeng merki eru:

n er mjög lítið og auðvelt að frumþátta,
sama p eða q hefur verið endurnotað í mörgum lykilpörum,
of lítill eða óvenjulegur e er notaður,
hrá RSA-dulritun er notuð án fyllingar,
sama dultexti eða sömu lykilupplýsingar birtast oft,
útfærslan gefur frá sér villur sem leka upplýsingum.

Þetta eru kennsludæmi um hvað getur farið úrskeiðis. Í raunverulegu kerfi eigum við ekki að reyna að finna veikleika með því að nota hráa RSA-útfærslu sjálf; við eigum að nota staðlað bókasafn og rétta samskiptareglu.

Æfing: greindu RSA-kerfið

Æfing 5

Hvað er athugavert við hvert dæmi?

p = 3, q = 11 í netþjónustu sem á að vera örugg.
Kerfi dulkóðar sama skilaboðið tvisvar með hráu RSA og sama dreifilykli.
Forrit setur einkalykilinn í JavaScript sem er sent í vafra notandans.
Vefur notar RSA til að dulrita hvert megabæti af stórri mynd.

Lausn við æfingu 5

Tölurnar eru allt of litlar. Hver sem er getur auðveldlega frumþáttað n = 33 og fundið einkalykilinn.
Hrá RSA er ákveðin: sama inntak með sama dreifilykli gefur sama dultexta. Það getur lekið því að skilaboðin séu eins og gerir orðabókarárásir auðveldari. Nota þarf rétta fyllingu.
Einkalykillinn er þá ekki lengur leyndur. Allir sem sækja JavaScript-kóðann geta lesið hann.
RSA er hæg og hentar ekki fyrir stór gögn. Venjulegt kerfi notar RSA eða aðra ósamhverfa aðferð til að koma á samhverfum lykli og notar svo hraða samhverfa dulritun fyrir myndina.

Samantekt

Í þessum kafla lærðum við að:

ósamhverf dulritun notar dreifilykil og einkalykil,
dreifilykill má vera opinber en einkalykill á að vera leyndur,
skilaboð eru dulrituð með dreifilykli viðtakandans og dulráð með einkalykli hans,
RSA byggir á frumtölum, módúlus, veldisvísum og margföldunarandhverfum,
leikfangs-RSA er gagnlegt til að læra en óöruggt í raunheimum,
stafrænar undirskriftir nota gagnstæða hugmynd: einkalykill til að undirrita og dreifilykill til að sannreyna,
vottorð tengja dreifilykil við rétt lén eða auðkenni,
raunveruleg kerfi nota fyllingu, staðlaðar útfærslur og oft blöndu af ósamhverfri og samhverfri dulritun.

Næst skoðum við hvernig tveir aðilar geta komið sér saman um sameiginlegan samhverfan lykil yfir opið net með Diffie–Hellman og hvernig undirskriftir og vottorð verja okkur gegn miðmannsárásum.