reede, 2. oktoober 2015

Mis on see salapärane moodulus?

Septembris kerkis üles viga ID kaardi sertifikaade genereerimisel, kus väidetavalt olevat mingisugune moodulus negatiivne, aga teadjamad räägivad, et see ei saa seda kuidagi olla ja seega on viga kõigest formaalne. Hea ülevaate probleemist leiab näiteks RIA blogist. Ei hakkakski siin probleemi olemust üle kirjeldama, keskenduks pigem tollele müstilisele moodulusele, et mis asi see üldse on ja miks see negatiivne olla ei saa. Järgnev jutt ei ole krütpograafiline ega matemaatiline teadustekst, vaid for dummies from a dummie, nii et kannatage ära ja jätke parandused kommentaaridesse.

Kõige lihtsamalt võttes on moodulus, nagu nimigi viitab, jäägiga jagamistehte jagaja. Modernse krüptograafia aluseks on hiigelpikad algaarvud, näiteks 2048 bitiga esitatud täisarvul on veidi üle 600 nulli ning selline moodulus ehk jagaja määrab sisuliselt ära numbriskaala, millel toimetame. Võrdluseks autode puhul võiks mooduluseks olla see number, mis on spidomeetril kõige suurem, näiteks 160 km/h. Auto mootor saab tekitada liikumiskiirust vahemikus 0 kuni 160, aga mitte vähem ega rohkem. Jah, osad detailid protsessi käigus võivad liikuda küll kiiremini – näiteks punkt auto ratta välisküljel võib vastavalt asukohale liikuda autost kiiremini, aeglasemalt või olla üldse paigal, aga auto liikumiskiirus jääb siiski sinna määratud vahemikku. Sama on ka krüptoarvutustega.

Et juttu veidi ilmestada, siis koostame siinkohal lihtsa jagatud võtmega ROT põhise krüptolahenduse, kuid fikseeritud saladuse (tavaliselt 13) asemel arvutame jagatud saladuse osapoolte salajasest ja avalikust võtmest Diffie-Hellman võtmevahetuse abil. Sellisel juhul saavad kasutatud võtit teada ainult mõlemad osapooled, aga mitte seda sõnumit pealt kuulavad kolmandad isikud.

Meil on kaks osapoolt, vanad tuttavad Alice ja Bob, kes lepivad kokku, et nende kasutatud võtmevahetuse avalikeks konstantideks on eelpool mainitud moodulus, milleks valitakse 23 (seega prime p=23) ja generaatoriks valitakse 5 (ehk g=5), mis määravadki kasutatava numbriskaala. Järgmiseks valib Alice endale meelepärase salajase võtme, milleks saab algarv 7 (ehk a=7, pange tähele, et see jääb g ja p vahele) ning Bob valib endale salajaseks võtmeks algarvu 11 (ehk b=11).

Salajast võtit loomulikult kellelegi edastada ei tohi ja seetõttu peavad Alice ja Bob tuletama oma salajasest võtmest ka avaliku võtme. Selle leiame tehtega

A←ga mod p

Kus A on Alice avalik võti, g on generaator 5, a on salajane võti 7 ning p on 23.

Alice avalik võti = 57 % 23 = 78125 % 23 = 17

Sama teeme ka Bobi võtmega:

Bobi avalik võti = 511 % 23 =  48828125 % 23 = 22

Seega on Alice salajaseks võtmeks 7 ning avalikuks võtmeks 17, viimase väärtuse edastab ta ka Bobile. Bobi salajaseks võtmeks on omakorda 11 ning avalikuks 22, mille ta edastab Alicele.

Järgmiseks tuleks tuletada nendest väärtusest ühisosa ehk jagatud võti. Selle leiame oma salajasest võtmest ja vastaspoole avalikust võtmest tehtega

S←Ba mod p

Kus B on Bobi avalik võti 22, a on Alice salajane võti 7 ning p on 23.

Jagatud võti Alice jaoks = 227 % 23 = 2494357888 % 23 = 22

Ning sama tehe Bobi jaoks

Jagatud võti Bobi jaoks = 1711 % 23 = 34271896307633 % 23 = 22

Nüüd teavad nii Bob kui Alice, et salajase info omavahel vahetamiseks tuleb kasutada ROT22 algoritmi. Kuna me ei ela enam Rooma impeeriumis, vaid vahepeal on paar tuhat aastat edasi läinud, siis kasutame 26 kohalise tähetabeli asemel tervelt 256 kohalist (ehk siis toimetame 1 baidi raames).

Alice tahab saata Bobile sõnumit "saladus" (baitidena 73:61:6c:61:64:75:73). Sõnumi krüpteerimiseks kodeerib ta selle jagatud saladusega, liigutades kõiki baite 22 võrra suuremaks ja saab väärtuse 89:77:82:77:7a:8b:89. Bob omakorda saanud sellise sõnumi, kerib jagatud võtme võrra baidid madalamaks ja saabki sõnumi sisu lugeda. Profit!

Kokkuvõtteks

Kui vastata esialgsele küsimusele, siis moodulus ei saa tõesti olla negatiivne ja seda seetõttu, et skaala millel toimetame (ning moodulus määrabki skaala ülemise otsa) on alati positiivne. Täiendavalt võis tähele panna, et juba niivõrd lihtsa lahenduskäigu korral läksid tehetes kasutatud väärtused juba päris suureks (näiteks jagatud saladuse leidmisel korraks läbi käinud väärtus 34 271 896 307 633), mis siis veel "päris" krüptost rääkida.



Täiendus

Kuna Facebookis küsiti, et mis bitt see ikkagi täpselt siis mooduluse negatiivseks muudab, siis kopipeistin siia arhiveerimise mõttes ka oma vastuse:
Küsimus on ASN.1 INTEGER väärtuse korrektses koostamises, see on siis see numbritüüp mida kasutatakse avaliku võtme mooduluse salvestamiseks sertifikaadis. Konkreetselt on sellel numbrivormingul selline tingimus, et esimene bitt näitab märki: kui see on 0, siis on tegu positiivse arvuga, kui aga 1, siis negatiivne. Kui number on piisavalt väike, siis jääb selle biti jaoks kenasti ruumi, aga suurte numbrite korral lähevad kõik bitid kasutusse ja seega tuleks tekitada juurde veel üks täidisbait, mis koosneb ainult nullidest (ei muuda numbri väärtust, küll aga tekitab vajaliku esimese nullbiti). Mis on nende sertifikaatide juures valesti, ongi see, et too täidisena mõeldud nullbait on numbriväärtuse eest puudu, aga numbriväärtus ise on niivõrd suur, et kasutab esimese biti ise ära. OpenSSL aga seda märki üldse ei vaata, sest kuna see ei saa olla muud kui positiivne, siis nullbaiti (kui see on olemas) lihtsalt ignoreeritakse.

Näide minu enda sertidega. Vana serdi puhul on mooduluse esimene väärtusbait 0xB9, mis bittidena väljendub 10111001. Nagu näha, on vasakpoolne bitt täidetud ja selleks, et seda numbrit mitte negatiivseks pöörata, on moodulus esitatud mitte B9:…, vaid 00:B9:… seega kõik klapib. Uue serdi puhul on esimene numbribait 0x97 ehk 10010111 (samuti on esimene bitt täidetud), kuid moodulus ei ole mitte 00:97:…, vaid 97:…. OpenSSL teisendab selle oma kõhuks ikkagi õigeks numbriks, õigemini ta lihtsalt ei arvesta esimese biti kui eriterminiga, aga vähem andestavad implementatsioonid, mis käsitlevad numbri kodeeringut korrektselt, loevad selle asemel välja ühe vigase negatiivse numbri (kuna esimene bitt läheb märgina kasutusse, siis muutub lisaks märgile ka terve number valeks)

Ja jätkuvalt – minu arvamus ei ole mitte kuidagi teaduslik ning selles võib esineda vigu kuna kõik vastavad teadmised olen saanud guugeldades ja oma loogikaga tuletades. Võrdluseks, täpselt samade uurimismeetoditega on teised inimesed jõudnud torusiili lastele sisse jootmiseni, nii et beware. Kui tead paremini või leiad jutus vea, siis anna sellest teada.

2 kommentaari:

Toomas ütles ...

Inglisekeelne "number" on eesti keeles krüptost kirjutades enamasti "arv". Eesti "number" on antud kontekstis "digit". Kõik need võtmed ja moodulused on seega arvud, mitte numbrid. Number, muide, ei saa olla negatiivne.

Telefoni- ja kinganumbrid on teine teema...

Andris ütles ...

Ei vaidle vastu. Eesti keeles on üldse IT teemadel üsna keeruline kirjutada, kuna vastav sõnavara ning konventsioonid ei ole väga levinud ja tihti ei jää muud üle kui kasutada toortõlget, mis ei pruugi olla väga adekvaatne. Võibolla need, kes on õppinud eesti keeles IT'd, saavad paremini hakkama, aga muudel (mina lõpetasin TTÜs elektri, mitte IT eriala) on üsna keeruline end eesti keeles täpselt väljendada.