Príklady 2. kola letnej časti 22. ročníka KSP

Môžete predpokladať, že naraz bude naplánovaných najviac N prestávok a budú naplánované najviac M sekúnd dopredu (kde N a M sú dané na vstupe). Váš program by po spustení mal bežať večne, teda napríklad ani po veľmi dlhom čase by v ňom nemalo nič pretiecť.

Príklad

Takto by mohla vyzerať interakcia s vašim programom. (Čítaj najskôr ľavý, potom pravý stĺpec, nie striedavo!) (N=17, M=47)

> TICK                          > SET 3
> TICK                          17idemejest
> SET 2                         > TICK
47ksp                           > SET 2
> TICK                          147teraz
> SET 4                         > TICK
74obed                          > TICK
> TICK                          BZZZ 17idemejest
BZZZ 47ksp                      BZZZ 147teraz
> DEL 74obed

(15 bodov)

"To je škandál!"
"Už som zažila všeličo, ale toto tu ešte nebolo!"
"Ako keby nestačilo, že minulý rok zaviedli daň zo svine!"
"Hovoríš mi z duše drahá."
"A čo sa vlastne stalo?"
"Ále, vy ste to ešte nepočuli? Veď sú toho plné správy."
"Nepočula, práve som sa vrátila z dovolenky."
"Nebudem chodiť okolo horúcej kaše a poviem vám to rovno. Minister chodenia do práce vydal nehorázne nariadenie."
"...no a ja neviem či sú blbí alebo čo, ale ja proste nemám ako to spraviť, no neviem..."
"...neskáčte mi do reči drahá! Takže, ževraj od prvého mája nesmie človek cestou z práce použiť žiadnu ulicu, ktorou šiel cestou do práce, vraj aby sa nenudil."
"No a viete, zlatko, vďaka tým žgrlošom na ministerstve ciest do prace (Nepliesť si s ministerstvom chodenia do práce! Ministerstvo chodenia z práce zatiaľ ešte neexistuje, ale určite chápete, k čomu táto reforma smeruje, všakže?) nepoznám jedinú dušu, ktorá by toto mohla spraviť, tak málo ulíc máme!"
"A vrchol všetkého je, že minister financii teraz vyhlásil, že sa dostavajú nové ulice, ale musí ich byť čo najmenej!"
"Presne tak. No povedzte, je normálny?"

Úloha

Máte zadané n - počet významných lokalít v meste. Momentálne sú tieto lokality poprepájané ulicami veľmi skromne, pre každé dve lokality existuje práve jeden spôsob, ako sa z jednej dostať po uliciach do druhej. Na vstupe je zadaných n-1 dvojíc (Ak vám nie je jasné, prečo n-1, radšej si to rozmyslite!) čísel lokalít, ktoré sú spojené ulicou.

Úlohou ministerstva ciest do práce (a aj vašou) je pospájať niekoľko dvojíc lokalít novými cestami tak, aby už nik nemohol mať problémy s plnením nového nariadenia. Pre každú dvojicu lokalít teda budú musieť existovať dve cesty, ktoré nemajú spoločnú ani jednu ulicu.

Môžete predpokladať, že pracovníci ministerstva sú šikovní a zvládnu postaviť novú ulicu medzi ľubovoľnou dvojicou lokalít. (Použijú nadjazdy, mimoúrovňové križovatky a podobné fičúrie.)

Výstupom programu by mal byť najmenší počet ulíc, ktoré stačí postaviť. Nezabudnite na dôkaz, že váš program naozaj nájde najmenšie možné riešenie!

Príklad

Vstup

6
1 3
3 4
4 5
2 3
4 6

Výstup

2
(Napríklad postavíme ulice 1-6 a 2-5.)

(15 bodov)

Aj v štvrtej časti nášho malého kryptologického seriálu si vyberieme jednu zo zaujímavých oblastí. Minule sme si niečo povedali o šifrovaní. Okrem iného sme si ukázali šifru, ktorá síce sama o sebe bola absolútne bezpečná... ale spôsoby, ktorými sme ju použili, už také skvelé neboli. (Tí z vás, ktorí vyriešili podúlohy c,d a e z minulej série, prípadne čítali jej vzorové riešenie, už vedia svoje.)

A práve o tom si budeme rozprávať dnes. Kryptológia nie je totiž len o tom vymyslieť čo najsilnejšiu a najťažšie prelomiteľnú šifru. Treba tieto šifry aj vedieť správnym spôsobom použiť. Tieto spôsoby použitia budeme volať kryptografické protokoly. Taký protokol nie je vlastne nič iné, ako dohodnutý postup, kto má kedy komu poslať akú správu.

Zoznámme sa najskôr s tradičným kryptografickým osadenstvom. Na úvod sú tu vaši starí známi, Alica a Bob, ktorí si chcú poslať správu. Okrem nich sú tu ale aj Eva (eavesdropper, čiže odpočúva komunikáciu) a Oskar (opponent, nepriateľ, ktorý môže do komunikácie aj aktívne zasahovať). Občas sa ukáže aj Trudy (trusted authority, niekto, komu Alica aj Bob dôverujú). V kryptografii sa používajú aj ďalšie postavy, v našom príbehu si ale vystačíme s týmito. Občas budeme namiesto mena človeka písať len jeho prvé písmenko.

Príklad protokolu z minulej série:

1. A->B: M ⊻ K_A
2. B->A: M ⊻ K_A ⊻ K_B
3. A->B: M ⊻ K_B

Povedzme si teraz niečo o nástrojoch, ktoré nám kryptológia ponúka pri navrhovaní protokolov. V prvom rade je to šifrovanie. Správu s zašifrovanú kľúčom K budeme značiť {s}_K. Predpokladáme, že účastníci komunikácie, ktorí K nepoznajú, nevedia efektívne z {s}_K určiť s ani K.

V druhom rade to sú časové pečiatky. Pre naše potreby časová pečiatka bude reťazec, v ktorom je napísaný aktuálny čas a dátum. Časové pečiatky budeme značiť T_*.

Občas sa hodí, aby niektorý účastník komunikácie poslal náhodný reťazec N_* (odborne zvaný nonce). Druhý účastník mu ho bude väčšinou musieť poslať späť, aby potvrdil, že jeho správa je aktuálna. Načo to bude dobré, to ešte uvidíte.

Ale dosť teórie, poďme sa pozrieť na príklad.

Protokol "žaba so širokou hubou":
Pripomeňme si, že T (Trudy) je účastník komunikácie, ktorému Alica aj Bob dôverujú. Nech A a T majú dohodnutý kľúč K_A, nech B a T majú kľúč K_B.

1. A->T: A, {B, K}_KA
2. T->B: {A, K}_KB

Čo tento protokol hovorí? Keď chce Alica niekedy hovoriť súkromne s Bobom, vygeneruje si kľúč K, ktorý potom ona a Bob použijú. Tento kľúč K chce teraz pomocou Trudy oznámiť Bobovi. Tak pošle Trudy správu: Ja, A, chcem hovoriť s B, pošli mu kľúč K. Keďže časť správy je zašifrovaná kľúčom K_A, Trudy má istotu, že správa naozaj prišla od A. Tak pošle B správu, kde oznámi: A chce s tebou komunikovať pomocou kľúča K. Keď B dostane túto správu, vie, že je od Trudy, lebo je zašifrovaná kľúčom K_B, ktorý nik iný nepozná.

Všetko vyzerá byť v poriadku. Čo sa ale stalo, keď Alica s Bobom skúsili použiť tento protokol? Oskar si uložil na disk všetky posielané správy. Niekedy dlho po tom, ako komunikácia skončila, získal kľúč K. (Buď priamo z počítača Alice/Boba, alebo trebárs hrubou silou z nimi posielaných správ.) Teraz ale Oskar prikročí k svojmu diabolskému plánu: Tváriac sa ako Alica pošle Trudy nasledovnú správu:
1'.:O(A) -> T: A, {B, K}_KA
V zápise protokolu značenie O(A) znamená, že je to Oskar, tváriaci sa, že je Alica. (Napr. sa pripojil na jej telefónnu linku, prípadne poslal mail, ktorý sa tvári, že je z Alicinej adresy.)

Oskar síce nevie kľúč K_A, ale správu {B, K}_KA má dávno uloženú na disku. Nič netušiaca Trudy si overí, že to šifrovala Alica a oznámi Bobovi, že Alica s ním chce hovoriť. No a nič netušiaci Bob sa začne s Alicou rozprávať, pričom použije kľúč K, ktorý mu Trudy poslala - ale ktorý už Oskar pozná! A ten jednoducho všetky Alici určené správy odchytí a tvári sa, že je ona.

Keď im toto Oskar vyviedol, videli Alica a Bob, že je zle. I upravili protokol tak, aby používal časové pečiatky. Alica si vygeneruje a v správe pošle časovú pečiatku T_A, aby ukázala, že správa je "čerstvá". Trudy si pri prijatí správy overí, či je či je správa "dostatočne čerstvá", ak nie, ignoruje ju. Podobne sa overí aj čerstvosť správ medzi Trudy a Bobom. Upravený protokol vyzeral takto:

Upravený protokol "žaba so širokou hubou":

1. A->T: A, {T_A, B, K}_KA
2. T->B: {T_T, A, K}_KB

Čo ale Oskar nevymyslel? Podobne ako v prvom prípade, aj tu odchytil obe správy. Teraz mu ale nestačilo uložiť si ich, lebo by mu časom prestali platiť. Namiesto toho poslal Trudy správu:

1'. O(B)->T: B, {T_T, A, K}_KB

Pre Trudy toto vyzerá ako správa od Boba, ktorý chce komunikovať s Alicou. Časová pečiatka je čerstvá. Nuž, Trudy pošle Alici správu:

2'. T->O(A): B, {T_T', B, K}_KA

Samozrejme, Oskar si ju opäť odchytí. Čo získal? Novšiu časovú pečiatku! No a nič mu nebráni opakovať tento postup až do okamihu, kým sa nedozvie kľúč K... A potom aktuálnu správu, stále s platnou časovou pečiatkou, rovnako ako predtým použije na oklamanie Alice alebo Boba.

Úloha

1. Predpokladajme, že na komunikáciu je použité asymetrické šifrovanie.(Príkladom je šifra RSA, viď http://mathworld.wolfram.com/RSAEncryption.html) To pre nás znamená, že hocikto vie vyrobiť šifrovanú správu určenú človeku C, ale len C si vie takúto správu prečítať.
   Použitý protokol funguje tak, že A aj B si vygenerujú náhodné reťazce N_A, resp. N_B, navzájom si ich oznámia, vypočítajú si z nich kľúč K=f(N_A,N_B) (f je nejaká známa funkcia) a pomocou toho budú ďalej komunikovať.
   1. A->B: {N_A, A}_KB
   2. B->A: {N_A, N_B}_KA
   3. A->B: {N_B}_KB
   Vysvetlenie: Alica pošle svoj reťazec a svoje meno, zašifrované tak, aby si to vedel prečítať len Bob. Bob si správu dešifruje, vyrobí správu určenú pre Alicu, v tej jej oznámi N_A a svoje N_B. Alica si overí, že N_A je to, čo poslala (a teda vie, že správa od Boba je čerstvá). Ak áno, oznámi mu N_B. V tomto okamihu aj Alica, aj Bob poznajú N_A aj N_B a spočítajú si kľúč K. Bob po prijatí N_B môže začať komunikáciu použitím kľúča K.
   Tento protokol samozrejme môže použiť na komunikáciu ľubovoľná dvojica ľudí, nie len Alica s Bobom :-).
   Alica práve chce komunikovať s Oskarom a poslala mu prvú správu:
   1. A->O: {N_A, A}_KO
   Ukážte, ako Oskar oklame Boba - Bob si bude myslieť, že si dohodol kľúč s Alicou, v skutočnosti ho ale bude vedieť Oskar.
   Hint: Paralelne s tým, ako komunikuje s Alicou, začne Oskar aj nový rozhovor s Bobom, použitím tohto istého protokolu... a podobných správ :-).
   
   
2. Vráťme sa späť do situácie, kedy máme aj Trudy, ktorej Alica aj Bob veria a majú s ňou dohodnuté šifrovacie kľúče ako v príkladoch. Tentokrát si Alica s Bobom vymysleli nasledujúci protokol:
   
   1. A->B: A, N_A
   2. B->T: B, N_B, {A, N_A}_KB
   3. T->A: N_B, {B, K, N_A}_KA, {A, K, N_B}_KB
   4. A->B: {A, K, N_B}_KB, {N_B}_K
   Vysvetlenie: Alica pošle Bobovi správu, že s ním chce komunikovať a náhodný reťazec N_A. Bob ak súhlasí, pošle Trudy potrebné informácie, časť z nich zašifruje, aby Trudy vedela, že sú od neho. Trudy si overí, že informácia pochádza od Boba - a keďže A bolo zašifrované, vie, že Bob chce naozaj hovoriť s Alicou. Trudy im vygeneruje kľúč K. Alici pošle Bobovo náhodné slovo N_B, správu pre ňu a správu pre Boba. Alica si odšifruje správu určenú pre ňu, overí si N_A (teda vie, že jej prvá správa prešla cez Boba) a dozvie sa kľúč K. Pošle Bobovi jeho správu. Navyše mu oznámi, že ona úspešne získala kľúč K - tak, že mu pošle {N_B}_K. Ak aj Bobovi všetko sedí, vie, že si práve s Alicou dohodol kľúč K.
   Aspoň tak si to Alica s Bobom predstavovali. Oskar však opäť niečo vyhútal. Dokáže Alicu presvedčiť, že si dohodla kľúč s Bobom, hoci to nebude pravda.
   Hint 1: Oskar sa nedozvie K.
   Hint 2: Začiatok útoku bude vyzerať takto:
   
   1. A->E(B): A, N_A
   1'. E(B)->A: B, N_A
   2'. A->E(T): A, N_A' {B, N_A}_KA
   ...