Archívum - Sorbarendezés

A számítástechnikai feladat matematikai leírása:

Domain-név igénylések ügyintézése

Hitelesítés:

A beérkezett igénylésekről technikai ellenőrzésük után egy lista készült, amely az igénylők által a bejelentkezésekor megadott, nyilvánosságra hozható információt tartalmazó rekordokból áll. A listát 2000. március 02-án 24 órakor lezárták. Neve: input.txt, 17958 sort tartalmaz. Felkértünk egy közjegyzőt, hogy az ezzel kapcsolatos tényeket tanúsítsa.

Mivel Magyarországon még nincs digitális aláírás törvény, ezért a hitelesítés az érvényben levő, a közjegyzőkről szóló 1991 évi XLI. törvény 144. szakasza alapján történt. Eszerint a közjegyző hatáskörébe tartozik, hogy tényeknek a jelenlétében történt információhordozóra való felvételét tanúsítsa. Az információ hordozója bármilyen média lehet. A rögzítésnek kell a közjegyző jelenlétében történnie, neki kell őriznie a médiát, azt a tárgyat, amire az információt, tényeket fölvették. A visszajátszás alkalmával ő ad ki tanúsítványt arról, hogy ezek a tények a jelenlétében kerültek felvételre. A letétbe helyezés ennek a törvénynek megfelelően történt. Egy üres CD-ROM lemezre a Bókai Judit Közjegyzői Iroda közjegyző helyettesének jelenlétében felírtuk a teljes listát. Ennek megtörténtét tanúsítja Dr. Józsa Krisztina közjegyző, aki CD-ROM lemezt közjegyzői letétbe helyezte. Az egyes rekordok nyilvánosak, azokat bárki megismerheti.

A megmásíthatatlanság további garanciájaként a listát az USA digitális aláírás szabványának (DSS) megfelelő "ellenörző blokkal" láttuk el. A Digital Signature Standard szabványt 1998 december 15-én fogadták el FIPS PUB 186-1 szám alatt, amely nyilvános és az interneten elérhető. A digitális aláírás algoritmus alkalmazása során először egy sűrítményt készítenek a dokumentumból. Ehhez egy másik USA szabvány, a FIP PUB 180-1 számú SHS Hashing szabvány használatát írják elő, amely szintén nyilvános és az internetről letölthető.

A szabványok a National Institute of Standard and Technology, USA honlapján mmegtalálhatók:

http://csrc.nist.gov/fips/

A szabványnak megfelelő SHA-1 nyilvános Hashing algoritmust használtuk fel az input.txt öt szavas (húsz byte-os) ellenőrző blokkjának az elkészítéséhez. Hangsúlyozni kell, hogy ez a blokk nem jelent digitális aláírást. A szavaknak megfelelő előjel nélküli 5 "hosszú egész" szám a következő:

Hash in decimal format:

2518584340, 4158335853, 3273613793, 355063469, 1483914814

Hash in hexadecimal format:

148C1E966D2BDBF7E1611FC3ADD629153EBE7258

Az SHA-1 egy olyan hashing algoritmus, amely tetszőleges digitális dokumentumból egy digitális lenyomatot képez. Egy dokumentum az algoritmus alkalmazása számára mindig egy bit-sorozat. Megszorítás, hogy a sorozat hossza < 264. Kimenete mindig 160 bit hosszúságú sorozat, akár 1 byte hosszú bemeneti "dokumentum" esetén is.

Az SHA-1 algoritmus programját bárki elkészítheti a szabvány alapján. Az internetről is több forráskód tölthető le. Az általunk alkalmazott program saját fejlesztés, így nem vonatkoznak rá az export-tilalmi USA rendelkezések. Az SHA-1 algoritmus mellett a program megoldja a lista véletlen átrendezését is. A program .exe file-ját ugyancsak a közjegyző jelenlétében ugyanarra CD-ROM-ra írtuk fel, mint amelyikre magát a listát rögzítettük. Ez biztosítja a sorrend törvény előtti reprodukálhatóságát.

Röviden az SHA-1 algoritmusról:

Az SHA (Secure Hashing Algorithm) elnevezésben a biztonságos (Secure) szó használatát a következő tulajdonságok indokolják.

  1. Ha legalább egy bitet egy dokumentumban megváltoztatunk, akkor a megfelelő új lenyomat sok bitben különbözik az előzőtől.
  2. Gyakorlatilag lehetetlen egy adott lenyomathoz olyan új dokumentumot konstruálni, amelyiknek a lenyomata éppen ez.
  3. Gyakorlatilag lehetetlen két olyan dokumentumot konstruálni, amelyeknek azonos a lenyomata.
  4. Elegendő hosszúságú bementi dokumentum esetén a lenyomat véletlenszerűen viselkedik. 300 bites bemenet már "elegendően" hosszúnak tekinthető.

Az első 3 Tulajdonság a megmásíthatatlanságot garantálja. A 4.Tulajdonság (véletlenszerűség) viszont a következőkben leírt követelményeknek megfelelő véletlen sorbarendezés megvalósításához nyújt segítséget.

Megjegyezzük, hogy az SHA-1 algoritmus számítástechnikailag sokféle módon valósítható meg, amelyeknek azonban ugyanazon bementi sorozat esetén ugyanazt a lenyomatot kell eredményezni. A szabvány három stringet ad meg a szabvánnyal való megfelelés ellenőrzésére.

 

Véletlen újrarendezés

A már lezárt Z=input.txt listát újrarendeztük egy olyan A sorbarendezési algoritmussal, amely rendelkezik a következő tulajdonságokkal:

  1. Permutálás: Az A algoritmus tetszőleges Z listára alkalmazható, és alkalmazásának eredménye a listában szereplő rekordok egy egyértelműen meghatározott P=P(A,Z) permutációja (átrendezése).
  2. Véletlenszerűség: Az algoritmus tetszőleges Z lista esetén is véletlen, vagy "közel" véletlen permutációt eredményez.
  3. Reprodukálhatóság: Az algoritmus eredményeképpen adódó permutáció reprodukálható. Ismételt alkalmazása ugyanazon lista esetén ugyanazt a permutációt adja meg.
  4. Megjósolhatatlanság: A permutáció nem jósolható meg: Az A algoritmus teljes ismeretében, de a Z lista konkrét ismerete nélkül nem lehet megmondani a keletkező permutációt, még akár a listában szereplő több rekord ismeretében sem.
  5. Előkészíthetetlenség: Az algoritmus ismeretében sem lehet olyan rekordot konstruálni, amely az átrendezés után biztosan az új lista elejére kerül.
  6. Rendezéstartás: A lista egy tetszőleges részhalmaza esetén az algoritmus alkalmazása a részhalmazon ugyanazt a sorrendet eredményezi, mint ami a teljes lista átrendezése során ezen a részhalmazon belül adódik.
  7. Nyilvános elérhetőség: A felhasználásra kerülő szoftver nemzetközi szabványoknak megfelelő, nyilvánosan hozzáférhető elemekből építkezik.
  8. Egyértelműség: ha az algoritmus a rendezés során különböző rekordokat ugyanoda tudna besorolni, akkor az összes ilyen között a sorrendet véletlenszerűen, de mindenképpen "objektíven" állapítja meg. (Ez a feltétel csupán kihangsúlyozása az 1. Pontban is kifejezett "egyértelműen meghatározott permutáció" követelménynek.)

Az újrarendezési algoritmus lépései:

  1. Lépés: Véletlenszerűen választunk egy 160 bites vektort, és ezt prefixként valamennyi rekord elé írjuk. Ezt a vektort a március 3-án este a TV2 nyilvánossága előtt közjegyző jelenlétében kisorsolt 20 KENO számalapján képezzük. A 20 byte ezeknek a számoknak felel meg: rendre a növekvő nagyságrendbe írt kisorsolt KENO számok lesznek. A véletlen választásnak ezt a módja március 3-án délután 4 órakor kerül nyilvánosságra hozatalra, jóval a sorsolás előtt, tehát a véletlen vektor megjósolhatatlan.
  2. Lépés: Valamennyi rekordot külön-külön hasheljük az SHA-1 algoritmussal. A kimenetként adódó H[0], H[1], H[2], H[3], H[4] szavakkal a közös véletlen vektor prefixet felülírjuk. Ezt az öt szavat előjel nélküli egészként értelmezzük. A rekordonkénti Hash értékek nyilvánosak, és az SHA-1 algoritmus nyilnánossága miatt bárki által ellenőrizhetőek.
  3. Lépés: Az öt egyedi szót előjel nélküli egészként értelmezve rendezzük a listát a következőképpen. Két rekord közül az a kisebb, ahol a megfelelő H[0] Hash érték kisebb. Ha a két H[0] érték azonos, akkor a két rekord közül az a kisebb, ahol a megfelelő H[1] Hash érték kisebb. Hasonlóan folytatjuk a H[2], digest[3] és H[4] értékékre. A listát úgy rendezzük, hogy a legkisebb rekordok kerülnek a lista elejére.
  4. Lépés: A rendezés után előfordulhatnak olyan sorozatok, amelyek azonos Hash-értékkel rendelkeznek. Ezeket ellenőrizzük. Az azonos hash-értékkel rendelkezőket újra rendezzük de csak egymás között. Az újra-rendezés úgy történik, hogy ezeket az azonosítokat addig növeljük egyesével, amíg különböző új Hash értékeik nem lesznek. Ezek szerint az újra hashelt értékek között végezzük el a rendezést.

Az SHS szabványban leírt tulajdonságok alapján belátható, hogy ez a rendezés kielégíti az előírt követelményeket. Valamennyi listán szereplő rekord hosszabb 100 karakternél, így a véletlenszerűség feltételezése megalapozott.

Példa a sorbarendezésre

A képzeletbeli file 4 rekordot tartalmaz a bejelentkezés sorrendjében:

1. ANETT Kereskedelmi és Szolgáltató Kft.%1960917001%anett1.hu%0970325011%19970325121056%Profill Kft.%HU H-3523 Miskolc Jenei utca 22%1000106005%Jenei Istvan%HU H-3516 Miskolc Jenei u. 57.%2970325011

2. ANETT Kereskedelmi és Szolgáltató Kft.%1960917001%anett2.hu%0970819004%19970819172951%Kliens Komputers Kft.%HU H-1139 Budapest Egres 78.%1000213002%Kiss Imre%HU H-1149 Budapest Egres 48.%2000213001

3. INET Hungary%1960228001%inet.hu%0970310013%19970310161530%Intro Számítástechnikai Szöv.%HU 1445 Budapest Pf. 538%1000215120%Varso Krisza%HU H-1096 Budapest Haller 8.%2970310021

4. FIXMIX Hungary%1960228001%fixmix.hu%0970530021%19970530155455%KergeSoft Kft.%HU H-1119 Budapest Szombathelyi ter. 14.%1991015018%Vaszlavik Gergely%HU H-%2990203005

A következő képzeletbeli a húsz véletlen szám esetén a fenti rekordokhoz tartözó hash értékek:

3, 6, 2, 6, 8, 5, 3, 2, 4, 2, 5, 7, 8, 5, 34, 2, 4, 6, 7, 34

Anett1: 2497609080,3312316788,2524221418,2678879479,3210278257

Anett2: 3154227966,3613987295,2262584642,3772254090,3375930351

INET: 2240469554,3916807065,3409546625,2363598202,2146433775

Fixmix: 1908341437,3110578218,3148163853,1286820710,3119470740

Rendezve:

1. Fixmix: 1908341437,3110578218,3148163853,1286820710,3119470740

2. INET: 2240469554,3916807065,3409546625,2363598202,2146433775

3. Anett1: 2497609080,3312316788,2524221418,2678879479,3210278257

4. Anett2: 3154227966,3613987295,2262584642,3772254090,3375930351

Főlap | Regisztrátorok listája | Delegálási szabályok | Meghirdetés | Keresés | Technikai ellenőrzés
Tanácsadó testület | Alternatív vitarendezés | Eseti Választottbíróság | Archívum | Egyebek | Statisztika