ˇ ˇ 
P51(2023/2024)1
22
Kratice
O   ˇ   
A Jˇ ´   K Kˇ ˇ 
V vsakdanjem življenju pogosto krajšamo dolga
imenainnazivezaradihitrejšegasporazumevanja.
Uˇ citeljica bo pogosto na tablo ali novinarka vˇ clan-
ku prviˇ c zapisala neskrajšano ime, nato bo dodala
tudi kratico in jo kasneje uporabljala. V tem be-
sedilu bomo predstavili matematiˇ cno ozadje kraj-
šanja, kot se uporablja pri raˇ cunalniški varnosti,
s poudarkom na kriptografiji (npr. ˇ ce želi novinar
prikriti ime neke osebe, bo praviloma uporabil za-
ˇ cetnici imena in priimka – ne nujno pravih).
Zanasbokrajšanjepostopek,prikaterempoljub-
nemu nizu znakov dodelimo nekokratico oz. okraj-
šavo,kratkooznako,npr. zaˇ cetniceuporabljenihbe-
sed, glej sliki 1 in 2 ter tudi nalogo 2.
Primerikrajšanja
Primer 1. (Oznake) Ko uˇ cence na zaˇ cetku šol-
skega leta razporedimo v razrede, npr. 100
uˇ cencev v 4 razrede A–D (24+23+27+26), je po-
gostoposamezniuˇ cenecnakratkooznaˇ cennpr.
»A-jevec«.
Zgornji primer omogoˇ ci kuharici, da v jedilnici hi-
tro pokliˇ ce del uˇ cencev ali pa veˇ cje skupine razdeli
namanjšeinjihzatolažjerazporedizadeljenjema-
lice.
Primer 2. (Zaˇ cetnice) Ko se v jedilnici štirje po-
sedejokenimizi,ugotovijo,dadogovoroklica-
njupozaˇ cetnicahimenainpriimkazanježalne
pride v poštev, glej sliko 2.
V zadnjem primeru vidimo, da je treba biti pri
krajšanju precej previden.
SLIKA1.
Stiskanje, zmešnjava, razpršenost, kot pri stiskanju grozdja ali
jabolk, pri tem pa gredo nekatere stvari tudi med odpadke.
krajšanje imena
Peter Horvat
Ivan Kralj
Ajda Krajnc
Ana Kos
kratice
AK
AJ
RF
TA
ZO
IK
PH
BC
KK
SLIKA2.
Trˇ cenja pri zaˇ cetnicah.
Primer 3. (Konice – gr. akronimi), in (radijske)
kode. Krajšanje se pogosto uporablja za hitrej-
še posredovanje informacij.

ˇ ˇ 
P51(2023/2024)1
23
Omenili smo že novinarje, a tudi policija, vojska
in interventne službe uporabljajo kratice, s katerimi
lahko zelo hitro opišejo stanje na terenu.
ˇ
Ce pa že-
limo ohraniti posredovane informacije še tajne, v
kriptografiji pravimo, da gre za uporabo kodnih
knjig.
ˇ
Ceprav tak pristop štejemo v kriptografiji za
zastarelega,sejesplošnouporabljalvdrugisvetovni
vojni(glejnpr.nalogo3)injevnekaterihprimerihše
vedno aktualen (npr. ko celotne fraze nadomestimo
s kraticami iz kodnih knjig).
Namesto gesel v raˇ cunalniških sistemih hranimo
le njihove »okrajšave«. Zakaj?. Pri shranjevanju po-
datkov pogosto poleg samega podatka hranimo še
njegovo »okrajšavo«. Zakaj?.
Primer4. (Serijskeštevilke)Zaevidentiranjena-
prav (knjig, ljudi ...) namesto dolgih opisov,
hranimo le pripisano številko vsake naprave
(npr. evidenˇ cna, registrska, telefonska, matiˇ cna,
davˇ cna, datum).
Poznamo pa tudi druge tehniˇ cno bolj zapletene
primere uporabe krajšanja, kot so digitalni podpisi,
denaralizaprisege,tvorjenjenakljuˇ cnihštevilinpo-
dobno. Ti primeri pridejo na vrsto v kakšnem nada-
ljevanju.
Vsaka tehnika krajšanja ima svoje prednosti in
slabosti, zato po navadi ni namenjena splošni upo-
rabi. Besedi krajšanje in kratica nista niti nujno naj-
bolj primerni za vsako tehniko, zato omenimo še
nekaj možnosti. Najbolj pogosta je zgošˇ cevanje in
zgostitev(angl.hash). Zarezultatzgošˇ cevanjapaso
tu še prstni odtis, izvleˇ cek in povzetek.
Zaželenelastnostikrajšanj
Predstavljamo nekaj zaželenih lastnosti tehnike
krajšanja, ki so uporabne na splošno:
1. Doloˇ cenost—krajšanjeistihizrazovvednopri-
pelje do iste okrajšave. Enostavna posledica te
lastnosti je, da razliˇ cni okrajšavi dveh (nezna-
nih)izrazovpomenita,damoratabitiizrazaza-
gotovo razliˇ cna.
2. Uˇ cinkovitost — postopek krajšanja je hiter in
enostaven (vsaj za raˇ cunalnike). Daljše izraze
bomo sicer obiˇ cajno krajšali dlje, npr. raˇ cuna-
nje vsote števk števila za potrebe ugotavljanja
njegove deljivosti s 3.
3. Enosmernost — iz same okrajšave (brez doda-
tnih informacij) je težko najti izraz, ki smo ga
krajšali. Izokrajšavenemoremosklepati,kako
seglasineokrajšaniizraz. Poslediˇ cnomorabiti
vsak delˇ cek okrajšave odvisen od vseh delov
vhoda ali pa od nobenega (v kriptografiji tej la-
stnosti pravimo zmešnjava – angl. confusion),
npr. zadnja števka vsote števk neznanega šte-
vila.
4. Skoraj brez trˇ cenj — možnost, da imata dva
razliˇ cna izraza enako okrajšavo, je majhna.
Takojenpr.pripravih/fiziˇ cnihprstnihodtisih.
Dodatna zahteva: najti dva razliˇ cna izraza z
istookrajšavojetežko. Poslediˇ cnomoraceloten
izrazvplivatinaizbranookrajšavo(vkriptogra-
fiji tej lastnosti pravimo razpršenost – angl. di-
ffusion).
Lastnosti 1 in 2 držita za veˇ cino krajšanj, ˇ ce pa k
temu dodamo še lastnosti 3 in 4, potem smo z eno
nogo že vstopili v deželo (tete) kriptografije. A pre-
den gremo po tej poti, omenimo še nekaj zanimivih
primerov.
Hranjenjevelikihdatotek
Najprejsmonatelefonushranjevalisamoštevilkein
še to kar v SIM-kartici. Ko pa je telefon postal še fo-
toaparat, predvajalnik glasbe ter celo filmov, lahko
hitro zapolnimo še tako velik pomnilnik. Ker so za
nas podatki pomembni (po navadi šele, kadar jih iz-
gubimo), smo se nauˇ cili delati varnostne kopije.
ˇ
Ce
pri tem nismo pazljivi, zelo hitro porabimo ves pro-
stortakonatelefonukotnaraˇ cunalnikualivoblaˇ cni
storitvi in se pri tem ne zavedamo, da hranimo vse
veˇ c kopij z isto vsebino. Pojavi se še problem razliˇ c-
nih verzij in kaj hitro se nam lahko zgodi, da s staro
verzijo »povozimo« novejšo datoteko. Pri reševanju
teh problemov si pomagamo tako, da poleg datotek
hranimo še njihove zgostitve, preko katerih znamo
uˇ cinkovito (lastnost 2) ugotoviti:
1. zeloverjetnoimamonadiskuveˇ ckopijisteda-
toteke (lastnost 4),
2. pri prenosu datotek je/ni prišlo do napak (la-
stnosti 1 in 4).
Ker je hitrost prenosa pogosto omejena, je hitrost
primerjanja še bolj pomembna. V nekem smislu je

ˇ ˇ 
P51(2023/2024)1
24
prvazgostitevimedatoteke, naslednjistanjenaveli-
kost in datum zadnje spremembe (celo kreiranja ali
dostopa),natopasipomagamošeskakšnimboljza-
pletenim zgošˇ cevanjem.
Preverjanjecelovitostipodatkov
Kako bi preverili, ali manjka kakšna stran iz dnev-
nika ali kakšno sporoˇ cilo (recimo pri nekem dopi-
sovanju)? Obiˇ cajna rešitev je, da uvedemo števce,
a se nato zaplete, ˇ ce želimo dodati novo stran ali
kaj izbrisati. Na nivoju besedila je lahko pomem-
benžeensamdodani,izbrisanialispremenjeniznak
(npr. ocena v spriˇ cevalu) oz. beseda/stavek (npr. v
pogodbi). Vse te probleme celovitosti podatkov re-
šujemo z zgostitvami. V tem primeru je zelo po-
membno, da tudi najmanjša sprememba v vhodnem
nizu vrne drugaˇ cno zgostitev (npr. t. i. vsota za pre-
verjanje–angl.checksum). Uporabljasepriprenosu
datotek (npr. z Bittorrent protokoli), upravljanju z
varnostnimikopijami,hitremiskanjupozbirkahpo-
datkov/dokumentih itd. Verjetno pa je najbolj po-
membna uporaba pri digitalnih podpisih, saj daljša
sporoˇ cila podpisujemo tako, da v resnici podpišemo
njihove zgostitve.
Hranjenje(uporabniških)gesel
O geslih smo že pisali v ˇ clanku Kljuˇ ci (v Preseku),
vendar takrat še nismo omenili postopkov zgošˇ ce-
vanja. Tokrat pojdimo korak dlje. Namesto da bi
raˇ cunalniški sistemi (ki nam omogoˇ cajo dostop do
osebnega raˇ cunalnika, spletne uˇ cilnice, forumov ...)
shranili uporabniška gesla, hranijo le njihove zgosti-
tve. Natanaˇ cingeslaostanejoskrita,tudiˇ cesinapa-
dalec pridobi dostop do sistema. Ker bodo ista gesla
imela iste zgostitve (lastnost 1), je tak naˇ cni shra-
njevanja gesel nepopoln. Napadalec lahko vnaprej
izraˇ cuna/sestavi tabelo vseh možnih parov
zgostitev geslag
n
geslog
n
.
.
.
.
.
.
zgostitev geslag
1
geslog
1
za zbirko pogostih gesel g, urejeno po zgostitvah.
Takozlahkarazbijemanjvarnagesla–zavsakozgo-
stitev v shrambi preveri, ali se nahaja v tabeli.
ˇ
Ce
njegovazbirkavsebujevsebesedeizslovarja,vkrip-
tografiji reˇ cemo, da gre zanapad s slovarjem. Ome-
nimo še napad z mavriˇ cnimi tabelami (velikosti ne-
kaj 100 GiB), s katerim lahko razbijemo skoraj vsa
krajšagesla(recimozmanjkot9znaki–tudiposeb-
nimi).
Kako prepreˇ cimo možnost hitre primerjave takšnih
gesel prek pripadajoˇ cih zgostitev?
Ena možna rešitev je, da za vsakega uporabnika
izberemodrugaˇ cenpostopekzgošˇ cevanja, kigatudi
hranimo. Vtemprimerubibilopotrebnozaugibanje
geselsestavitizgornjotabelozavsakegauporabnika
posebej.
Igrakamen-škarje-list
Okoli 2000 let staro kitajsko igro po navadi igrata
dva igralca takole:
(1) vsak od igralcev si na skrivaj izbere eno izmed
treh možnosti kamen/škarje/list,
(2) igralca drug drugemu istoˇ casno razkrijeta izbiro,
(3) zmagovalca se doloˇ ci po pravilu:
kamen uniˇ ci škarje,
škarje prerežejo list,
list pokrije kamen,
v vseh drugih situacijah imamo izenaˇ cenje.
Za poštenost igre je kljuˇ cnega pomena istoˇ casnost.
Lahko jo zagotovimo s sodnikom.
Kaj pa ˇ ce nimamo sodnika ali pa želimo igro igrati
preko telefona/interneta?
Podobna vprašanja si je postavljal že leta 1982
Manuel Blum — glej nalogo 5.
Problemistoˇ casnostilahkorešimozuporabokrip-
tografsko varne zgošˇ cevalne funkcije. Takšna
funkcijazapoljubnozaporedjeznakovx uˇ cinkovito
(z raˇ cunalnikom) izraˇ cuna zgostitev z := F(x). Za-
radipredstavitvemedijevvdigitalnioblikijelahkox
tudislika,video... Veljatimoratudi,dajepraktiˇ cno
nemogoˇ ce uganiti/izraˇ cunati dva razliˇ cna izraza z
enakima okrajšavama ali pa vrednost x iz zgostitve
z (tudi za najzmogljivejše raˇ cunalnike)
5
.
Primer poteka igre med Ano in Bojanom (brez so-
dnika):
5
Ti dve možnosti sta manjši, kot da 3-krat zapored zade-
nemosedmiconaLotu,intosprvimitremikupljenimisreˇ ckami!

ˇ ˇ 
P51(2023/2024)1
25
(1) Ana na skrivaj izbere (dovolj dolg) nakljuˇ cni niz
H6FUcfqtAGf3inlist,BojanpaizbereuAD22TWTNTz2
in škarje.
(2) Ana izraˇ cuna (z raˇ cunalnikom) zgostitev z
A
=
F(H6FUcfqtAGf3 list), Bojan pa izraˇ cuna
z
B
=F(uAD22TWTNTz2 škarje).
(3) Izmenjata si zgostitviz
A
inz
B
.
(4) Izmenjata si nakljuˇ cna niza (lahko pa tudi še iz-
biri).
(5) Doloˇ cita izid igre. (Kako?)
Hranjenje množic (na papirju oz. raˇ cunalniku —
beri: digitalnemmediju)
Pred veˇ c kot pol stoletja smo v šole hkrati s števili
(aritmetiko)zaˇ celiuvajatišemnožice(glejhttps://
en.wikipedia.org/wiki/New\_Math). Zatojeˇ cisto
prav, da nanje pomislimo danes, ko smo že povsem
obkroženi z raˇ cunalniki, še iz tega zornega kota. Tu
senamreˇ cpojavijozanimiviproblemi,kisopovezani
z našim krajšanjem.
Kajodgovorimonavprašanje,alijenekielementv
množici?
ˇ
Ce je množica majhna in »vidimo« vse njene ele-
mente,potemtonajbržsplohnitežko.
ˇ
Cejeelemen-
tovveˇ c,moramoizbratinekodrugoprimernostrate-
gijo. Kako bi na primer ugotovili, ali je neka beseda
slovenska oziroma, da pripada množici vseh sloven-
skihbesed. Kakobinatovprašanjeodgovorilstriˇ cek
Google,ˇ ce nanj ne bi bil pripravljen? Kako naj zbere
vse slovenske besede, ˇ ce vseh sploh ne pozna. Za
obˇ cutek omenimo še, da imajo najbolj bogati jeziki
tudi do ˇ cetrt milijona besed (pa pri tem ne štejemo
sklonov).
ˇ
Ce se da elemente urediti po vrsti, potem jih radi
hranimo urejene, kot je to narejeno z besedami ne-
kega jezika v slovarjih (leksikografska ureditev). V
temprimerujezapreverjanjeprisotnostielementav
množici potrebno le nekaj primerjav, da preverimo,
ali je neka beseda v slovarju (npr. metoda bisekcije).
Na sreˇ co ni potrebno prelistati vseh strani. Zakaj?
6
6
Po omenjeni metodi bisekcije bi slovar odprli na sredini in
ˇ ce tam ne bi našli besede, bi nadaljevali v prvi ali drugi polovici
– po istem postopku vse do konca, ko bi ugotovili, ali je sploh
iskana beseda v slovarju.
Kaj pa ˇ ce elementov sploh ne znamo enostavno
primerjati?
Recimo, da išˇ cemo nekega vojaka, ki je storil ne-
kajslabega,pasenamzdijovsivojakinaprvipogled
zelo podobni. Upajmo, da imamo na voljo vsaj ka-
kšen prstni odtis nepridiprava, pravzaprav kar vseh
vojakov. Lahko so na voljo le njihove slike, ki jih
je posnela skrita kamera. Kako urediti po vrstnem
redu slike?
ˇ
Ce bi vojake slikali ob vstopu v vojsko,
potem bi najbrž vsak dobil številko in k tej številki
pripeto sliko.
ˇ
Ce pa ne gre za naše vojake, potem
je stvar še nekoliko bolj zapletena (sicer bi lahko šlo
tudi za bakterije, viruse itd., a ne želimo zaiti na po-
droˇ cjebiologijealimedicine),sajsmorekli,dajenaš
zorni kot raˇ cunalništvo. Predpostavimo, da primer-
jamoslikevojakov(atunebomoreševaliproblemov
raˇ cunalniškega vida).
Ena možna rešitev je, da namesto elementov pri-
merjamo njihove zgostitve. Za hitro iskanje in doda-
janje elementov najprej izraˇ cunamo zgostitve vseh
elementov ter sestavimo tabelo na naslednji naˇ cin.
Element spravimo v tisto vrstico tabele, ki jo doloˇ ca
njegova zgostitev. Vsaki zgostitvi namenimo svoj
prostor (to je lahko list papirja, del pomnilnika ali
vrstica v tabeli). Zgostitve igrajo vlogo kazala (npr.
rokovnik z naslovi, zgostitev predstavljata prvi dve
ˇ crki priimka – trki so tukaj dopustni, ampak nezaže-
leni).
Podobno tehniko uporablja sistem za spletno iz-
menjevanje datotek prek t. i. magnetnih povezav
(angl. Magnet Link), ki so pretežno zgostitveh
magnet
.
ˇ
Ce poznamo neko zgostitev, lahko prek Bittorrent
protokolov, prenesemo želeno datoteko (ali pa mapo
z datotekami). Najprej poizvemo, kdo si trenutno
deli pripadajoˇ co datoteko. Podatek o tem, kateri ra-
ˇ cunalnikisitrenutnodelijodatotekovezanonadano
magnetno povezavo, se hrani v velikem skupnem
»imeniku« na spletu, kjer za »zaˇ cetnico« imenika
vzamemo zgostitevh
magnet
, za »naslov« pa IP naslov
invrata(angl.port)raˇ cunalnikov. Kerjeimenikvelik
in se neprestano spreminja, noben raˇ cunalnik nima
celotnega imenika, le nekaj »strani«.
Konajdemoraˇ cunalnike,kitrenutnodelijoželeno
datoteko, najprej prejmemo od njih t. i. torrent da-
toteko. Ker so datoteke, ki jih na ta naˇ cin izmenju-
jemo,ponavadivelike,jihprenašamopomanjšihde-
lih/košˇ ckih. Zaradi tega prejeto torrent datoteko se-
stavljajo zgostitve vseh košˇ ckov datoteke in njihove

ˇ ˇ 
P51(2023/2024)1
26
velikosti, ter ime datoteke. Skupna zgostitev vseh
teh treh informacij je h
magnet
in osnovni del magne-
tne povezave, glej sliko 3. Ker se zgošˇ cevanje iz-
vaja s kriptografsko varno zgošˇ cevalno funkcijo H,
so zgostitve datotek praktiˇ cno unikatne. Prednost
takega naˇ cina prenosa datotek je, da lahko datoteke
prejemamo od veˇ c raˇ cunalnikov hkrati (od vsakega
le nekaj košˇ ckov) in smo zato neodvisni od mrežnih
problemov (npr. prekinitve, napake). Namenoma ni-
smo podali celotne zgodbe, saj je še veliko bolj za-
pletena. Primer magnetne povezave: magnet:?xt=
urn:btih:e0d9af6671db5bc4fc77ab5462c50e2f3
545dad9. Število s 40-timi znaki v šestnajstiškem
zapisu e0d9a... (20 »bajtov«) tukaj predstavlja zgo-
stitev (SHA-1) za prenos DVD-ja (velikosti 3,59 GiB
= 14741 košˇ ckov velikosti 256 KiB, torrent datoteka
je velikosti 288 KiB ≈ 14741 × 20 B) za namesti-
tevoperacijskegasistemaUbuntu20.04.5(zaceloten
vpogled v vsebino te torrent datoteke glej povezavo
https://gist.github.com/kllemen/47c7d8782-
c81afbb76bc7ff19d172588).
Zakljuˇ cek
ˇ
Ce boste rešili vsaj nekaj spodnjih nalog, boste opa-
zili,dasezdinaprvipogledkonstrukcijakriptograf-
skih zgošˇ cevalnih funkcij (pre)zahtevna naloga. V
resnici sploh ni lahko najti (sestaviti) takšno funk-
cijo. Tudiˇ ce nam jo nekdo predlaga, ne moremo biti
prepriˇ cani, da se ne bo v prihodnosti izkazalo, da
ena od zahtevanih lastnosti ne drži. Prve zasnove
kriptografskihzgošˇ cevalnihfunkcijsegajo45letna-
zaj (glej Merkle 1979 in npr. Damgärd). V devetde-
setih letih prejšnjega stoletja je zelo hitro naraslo
število modelov zgošˇ cevalnih funkcij, vendar so bile
prištevilnihodtehpredlogovugotovljenevarnostne
pomanjkljivosti,npr.najboljpopularnimRivestovim
zgošˇ cevanim funkcijam MD4 in MD5 (angl. Message
Digest) se je po veˇ c 10-letni uporabi zgodilo prav to.
Odprt problem: ali kriptografske zgošˇ cevalne
funkcije sploh obstajajo?
Ta ˇ cas sicer imamo kar nekaj kriptografskih zgo-
šˇ cevalnih funkcij, za katere se smatra (ali vsaj upa),
danavedenelastnostidržijoinjihzatouporabljamo
v praksi: BLAKE, RIPEMD (Bitcoin), SHA (za digitalno
potrdila v osebni izkaznici oz. v splošni uporabi),
Whirlpool itd. Teh funkcij nikoli ne raˇ cunamo na
roke (https://md5calc.com/hash/sha1 bralec
lahkoposkusipreveritinjihovodelovanjeoziromase
poigrati s simulacijo raˇ cunanja funkcije
https://sha256algorithm.com/). Kakšno med
njimi bi si enkrat celo lahko pobližje ogledali. Že
sedaj pa lahko omenimo:
Odprt problem: najdi zalogo vrednosti zgošˇ ceval-
ne funkcije MD4 ali SHA-1.
Lahko pa se vprašamo tudi, ali obstajajo kripto-
grafsko varne zgošˇ cevalne funkcije primerne za
»ljudi«? Za zdaj kaže, da brez pomoˇ ci raˇ cunalnika,
vsaj za veˇ cino nas, žal ne gre.
Naloge
1. Možni ostanki pri deljenju celega števila s 3 so
0, 1 in 2. Krajšanje, ki nam za naravno šte-
vilo vrne njegov ostanek pri deljenju s 3, ima
oˇ citno prvi dve lastnosti (doloˇ cenost in uˇ cinko-
vitost). Prepriˇ cajse,danitakoprizadnjihdveh
lastnostih (enosmernost oz. iskanje praslike in
problem trˇ cenja).
ubuntu.iso
vsebina torrent datoteke
klju ni del
magnetne
povezave
delitev na koš ke
b
f
H
H
H
H
232d0b… 6f9fd7… a25d9b… f = 3864182784
b = 262144
'ubuntu.iso'
e0d9af… ...
...
...
14740.
0.
1.
SLIKA3.
Ustvarjanje magnetne povezave.

ˇ ˇ 
P51(2023/2024)1
27
2. Teta kriptografija se je pogovarjala z mlajšo
kolegico in izvedela, da bodo mladi bralci ob
besedi krajšanje najprej pomislili na krajšanje
ulomkov. Pritempostopkuobiˇ cajnoizvelikega
imenovalca in števca izpostavimo njun najve-
ˇ cji skupni delitelj D in konˇ camo po krajšanju
z manjšim imenovalcem in števcem (ˇ ce le ni
D = 1), medtem ko vrednost ulomka ostane
ista. Tudi pri našem krajšanju si želimo po-
dobno–krajšizapis. Katerimodomenjenihšti-
rih lastnosti ustreza omenjeno krajšanje ulom-
kov?
3. Ameriška mornarica je zbrala 29 mož indijan-
skega plemena Navajo (https://www.intel-
ligence.gov/people/barrier-breakers-
in-history/453-navajo-code-talkers) in
ustvarili kode, zasnovane na njihovem zaple-
tenem, nenapisanem jeziku. Koda je v prvi vr-
sti uporabljala povezovanje besed tako, da je
kljuˇ cnim frazam in vojaškim taktikam dodelila
besedo Navajo.
ˇ
Ce se želite preizkusiti v odši-
friranju kode v jeziku Navajo, uporabite
https://www.cia.gov/stories/story/na-
vajo-code-talkers-and-the-unbreaka-
ble-code/ za odšifriranje naslednje kode:
TKIN-KE-YAH YIL-DOI AH-JAH YEH-HES
KLESH DIBEH-YAZZIE
WOL-LA-CHEE TSAH BE TKIN YIL-DOI
WOL-LA-CHEE
oziroma odšifrirajte spodnjo kodo, da ugoto-
vite, v kateri bitki je koda pomagala doseˇ ci
zmago ZDA:
Tkin-Gloe-Ih-A-Kha Ah-Ya-Tsinne-Tkin-
Tsin-Tliti-Tse-Nill
4. (a) Kaj bi bil primeren naˇ cin zgošˇ cevanja glas-
be, ki bi ljudem še vedno omogoˇ cal prepozna-
vanje/loˇ cevanje? (b) Katere izmed tistih štirih
lastnosti si tukaj želimo? (c) Kako bi tako pre-
poznavanje naredil z raˇ cunalnikom (torej brez
uporabe naših možganov)? Na telefonu bi lah-
ko uporabili aplikacijo Shazam. (d) Ali mogoˇ ce
veš, kako YouTube portal ve, da si uporabil av-
torsko zašˇ citeno glasbo v svojem videu (ker jih
oˇ citnonepregledujejo»naroke«–razenmorda
ˇ cisto na koncu, ko pride do kakšne tožbe)?
5. Kako varno vreˇ ci kovanec prek telefona (iz
ˇ clanka M. Bluma, Coin Flipping by Telephone,
1982)? Ana in Bojan želita vreˇ ci kovanec prek
telefona. (Nasledni mesec bosta delala v razliˇ c-
nih mestih in želita sprejeti odloˇ citev, kdo bo
dobilskupniavto.) Bojannoˇ cepovedatiAni»ci-
fra« in slišati (na drugi strani linije), kako ona
odvrne »Vržem kovanec ...Izgubil si!«. Ali bi
znal predelati igro kamen-škarje-list z uporabo
zgošˇ cevalnih funkcij tako, da rešiš Anin in Bo-
janov problem?
6. Kakozašˇ cititiidejo,danamjekdoneukradein
predstavi kot svojo? Recimo, da je sošolec pri-
šel do naše seminarske naloge, še preden smo
jo oddali in se je odloˇ cil, da jo bo oddal s svo-
jim imenom. Ali obstaja naˇ cin, da prepriˇ camo
uˇ citeljico o našem avtorstvu?
7. Katere lastnosti želimo pri zgošˇ cevalnih funk-
cijah za hranjenje gesel v raˇ cunalniških siste-
mih?
Kako bi problem primerjav gesel rešil le z eno
zgošˇ cevalno funkcijo (torej v nasprotju s pre-
dlogom v samemˇ clanku)?
8. Zakajprishranjevanjupodatkovpogostopoleg
podatka hranimo še njegovo okrajšavo? (Na-
mig: kako preverimo, ali podatek ni pokvar-
jen, zakaj je iskanje po velikem disku lahko
dolg proces, kako lahko na hitro primerjamo,
kaj imamo shranjeno v oblaku in kaj lokalno
na svojem domaˇ cem raˇ cunalniku — ali lahko
ugotoviš, kaj ti sistemi v ozadju poˇ cnejo.)
9. Poišˇ ci naˇ cin krajšanja, ki ima lastnost 3, ne pa
tudi lastnosti 4.
10. Poišˇ ci naˇ cin krajšanja, ki ima lastnost 4, ne pa
tudi lastnosti 3.
11. Zakaj lahko pri prenosu datotek prek BitTor-
rent protokola, sproti preverjaš ali si doslej
prejel pravilne/nepokvarjene kose datotek.
12. Kakosepriigrikamen-škarje-listodkrijegolju-
fanje?
ˇ
Cemu služi nakljuˇ cen niz, ki si ga Ana

ˇ ˇ 
P51(2023/2024)1
28
in Bojan izbereta na zaˇ cetku? Kaj gre lahko na-
robe, ˇ ce ta niz ni nakljuˇ cno izbran? Zakaj Ana
ne more iz vrednosti zgostitvez
B
ugotoviti Bo-
janoveizbire? Zakajlahkoizmenjavozgostitev
z
A
inz
B
izvedemo z zamikom? Kako bi se dalo
goljufati, ˇ ce za funkcijo F lastnost 4 ne bi dr-
žala?
13. Kako so shranjena gesla za dostop do spletne
uˇ cilnice na vaši šoli oz. tvojega raˇ cunalnika?
14. Za kriptografske zgošˇ cevalne funkcije skoraj
vedno velja, daˇ ce se spremeni en sam bit vho-
da,semoraspremenitipribližnopolovicabitov
na izhodu. Zakaj je to pomembno?
Ali bi bil problem,ˇ ce bi se v izhodu spremenili
skoraj vsi biti?
15. Uporabi seštevanje ali množenje števil (v Z ali
R) za sestavo nove zgošˇ cevalne funkcije in jo
analiziraj. Enosmernost nam zagotavlja pro-
blem iskanja seštevancev ali faktorjev. Ali je
uporaben poseben primer, kadar vemo, da gre
za enaka števila?
16. Ali je krajšanje, ki vraˇ ca zaˇ cetnici imena,
kriptografsko varna zgošˇ cevalna funkcija?
Možnost, da imata dva izmed petih uˇ cencev
enake zaˇ cetnice, je sicer majhna, 2,7 %, a v sve-
tu zgošˇ cevalnih funkcij je to ogromno. Za pri-
mer lahko naredimo tudi scenarij, da je v ra-
zredu 20 uˇ cencev. Takrat je možnost, da imata
dva uˇ cenca enak izhod, že 57,1 % (z upošteva-
njem, da niso vsa imena in priimki enako ver-
jetni; ˇ ce tega ne upoštevamo, zmanjšamo mo-
žnosti na 1,0 % pri 4 uˇ cencih in 26,5 % pri 20
uˇ cencih). Kako smo prišli do teh ocen?
17. Bloˇ cnešifre(najboljslavnajedanesAES)razde-
lijo tekst, ki ga želimo šifrirati, na bloke enake
dolžine (npr. 128 bitov), nato pa šifrirajo vsak
blok posebej
ˇ
Ce to naredimo z enim samim
kljuˇ cem K, se identiˇ cni bloki sporoˇ cila
m= m
1
m
2
...m
t
zašifrirajo v identiˇ cne bloke
tajnopisa:
c=c
1
c
2
...c
t
, kjer je c
i
=AES
K
(m
i
),
kar je lahko problem, glej (zašifrirano) sliko 4.
SLIKA4.
Zašifrirana slika znanega Linuxovega pingvina.
Zatovˇ casihšifriranjenekolikoprepletemo,npr.
po postopku
c
0
=IV, c
i
=AES
K
(c
i−1
)XORm
i
, za i≥1,
kjer je IV neka (javno) znana konstanta, bitni
XOR pa v raˇ cunalništvu zelo znana operacija,
ki ji v slovenšˇ cini reˇ cemo ekskluzivni ali. Po-
stopeksejedolgouporabljalzapreverjanjece-
lovitosti sporoˇ cila. Kako? Bi ga znal zapisati?
Obiˇ cajno zakljuˇ cimo pismo s kakšno obiˇ cajno
frazo (Lep pozdrav) in ˇ ce to napadalec ve, po-
temsedatoizkoristiti(brezpoznavanjakljuˇ ca
K). V bistvu lahko zadnji blok zamenja s po-
ljubnimsvojim. Biznalpokazati,kakotostori?
18. Nad enosmernostjo se zamislimo še zunaj sve-
ta raˇ cunalnikov. Kateri pojavi iz našega obiˇ caj-
nega življenja imajo lastnost enosmernosti?
×××
www.presek.si
www.fmf.uni-lj.si/sl/zalozba/