Druhá série devátého ročníku KSP
- Termín série: 5. ledna 1997
- Odevzdávání: elektronicky přes Odevzdávátko
- Jak sepsat řešení: viz Návod na teoretické úlohy
- Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.
Zadání úloh
- 9-2-1: Psí funkce
- 9-2-2: Tiskařský šotek
- 9-2-3: Překla-datel
- 9-2-4: Nesčetní námětové
- 9-2-5: Top secret
9-2-1 Psí funkce (10 bodů)
Funkce Ψ(n) je pro přirozená čísla n definována následujícím předpisem:
- Ψ(1) = 2
- Ψ(n+1) = 2Ψ(n)
Napište program, který pro dané velké přirozené číslo n > 1000 spočte, kolik je Ψ(n) mod 13.
9-2-2 Tiskařský šotek (10 bodů)
V tiskárně jedněch (pro jistotu nejmenovaných) novin se usídlil tiskařský šotek. Čas od času se rozhodl, že v sázeném textu prostě přidá, ubere nebo změní jedno písmenko, a tak změní jeho smysl (obvykle na něco žertovně laděného – například "Pražský průmysl masný" na "Pražský průmysl mastný").
Ledva redaktoři zjistili přítomnost našeho šotka, pořídili si počítačový systém pro kontrolu pravopisu (tzv. spelling-checker, to jest program, který upozorňuje na jemu neznámá slova). Proto šotek musí své změny provádět tak, aby vždy vzniklo spelling-checkeru známé slovo a jeho čin tak zůstal (alespoň do vytištění příslušné stránky) v tajnosti.
Vás požádal, abyste mu ku pomoci v jeho počínání napsali jednoduchý program, jenž dostane k dispozici kompletní seznam slov známých spelling-checkeru a pak se jej bude šotek moci ptát, na jaká všechna známá slova může zadané slovo změnit popsanými "jednopísmenkovými" úpravami.
9-2-3 Překla-datel (10 bodů)
Jednoho dne se stalo, že na Zemi přistáli Ufouni, malá to zelená stvoření obývající zapomenuté kouty Vesmíru. Nabídli nám, že si z paměti jejich palubního počítače můžeme odčerpat libovolné množství informací o jejich rodné planetě, pokud to ovšem dokážeme.
Jediným problémem při připojování ufounského počítače k našemu se ukázalo být to, že Ufouni zapisují čísla ve dvojkové soustavě v přesně opačném pořadí číslic než jak činíme my – to jest s nejméně významnou číslicí na začátku místo na konci (například číslo 34 zapisujeme jako 10010 a oni jako 01001).
Při konstrukci překládacího zařízení je tedy klíčovým problémem vytvořit program, který k danému 128-bitovému číslu N nalezne číslo N′, jež má přesně opačný binární zápis: má-li N binární zápis a127a126… a1a0, musí mít N′ zápis a0a1… a126a127.
Překládací stroj je ovšem programován ve velice jednoduchém programovacím jazyce,
který disponuje stovkou 128-bitových proměnných a jedním jediným příkazem: přiřazením
typu a = b °c, kde a je proměnná, b a c jsou proměnné nebo konstanty
a ° je jedna z operací + (sčítání), - (odčítání), * (násobení),
/ (dělení), & (bitový logický součin), | (bitový logický součet),
< (bitový posun b doleva o c bitů) a > (bitový posun b doprava
o c bitů). Vstup dostanete v proměnné x, výstup budiž na konci výpočtu uložen
v proměnné y.
Napište co nejkratší program pro překládací stroj, který najde příslušné "reverzní číslo" k číslu danému.
9-2-4 Nesčetní námětové (10 bodů)
Za devatero horami a devatero řekami byla velká země. Tamější obyvatelé se rozhodli, že by mohli tisíc let starou státní vlajku vyměnit za jinou, poněkud méně okoukanou. Sešlo se úžasné množství různých námětů, ty byly očíslovány (37: zelený, fialový a hnědý pruh, 666: čert s rudou hvězdou v rozích, 919: kosa a palička na maso apod.) a bylo vyhlášeno celonárodní referendum, které má z těchto námětů vybrat ten pravý s tím, že za právoplatného vítěze je možno považovat jen takový námět, jenž získal nadpoloviční většinu hlasů.
Vás najali, abyste napsali program pro vyhodnocování výsledků voleb. Dostane pole o N prvcích (pozor, N je velké číslo), jehož každý prvek odpovídá jednomu hlasujícímu občanovi a jeho obsahem je číslo námětu daným občanem voleného. Program má co nejrychleji nalézt číslo, které se v poli vyskytuje více než N/2-krát nebo odpovědět, že tam žádné takové není.
9-2-5 Top secret (10 bodů)
Při klasickém šifrování je bezpečnost založena na utajení jak klíče pro šifrování tak klíče pro dešifrování. Dlouho se zdálo nemožné, aby existovala šifra, u které by bylo možné zveřejnit klíč pro šifrování aniž by byla výrazně narušena bezpečnost (klíč pro dešifrování samozřejmě musí zůstat utajen). Jedním z důvodů, který k tomu vedl, bylo, že pro se pro šifrování i dešifrování používal stejný klíč.
V kryptosystémech s veřejným klíčem jsou klíče dva: jeden šifrovací (ten je zveřejněn) a jeden dešifrovací (ten je utajen). Tyto dva klíče musí být komplementární, tj. dešifrováním zašifrované zprávy bychom měli dostat zprávu původní. Navíc nesmí být možné bez znalosti tajného klíče "rychle" zašifrovanou zprávu rozluštit.
Mezi nejvíce používané kryptosystémy s veřejným klíčem patří systém RSA, jehož objev oznámili 4. dubna 1977 pánové Ronald L. Rivest, Adi Shamir a Leonard Adleman z Massachusetts Institute of Technology.
RSA funguje takto: veřejný klíč je nějaká dvojice čísel <N,s>, tajný klíč je dvojice čísel <N,t>. Šifrovat můžeme celá čísla x, která splňují podmínku 1 < x < N. Šifrujeme pomocí vztahu y = xs mod N, dešifrujeme pomocí vztahu x=yt mod N. (Zamyslete se, jak šifrovat text a proč není vhodné šifrovat čísla x=0 a x=1.)
Klíče samozřejmě nesmí být náhodně zvolená čísla – o generování klíčů bude příští úloha.
Příklad: Veřejný klíč je <143,23>, tajný <143,47>. Šifrováním čísla 123 dostaneme číslo
dešifrováním tohoto čísla dostaneme opět
Úloha: V již neplatném vydání Veřejného šifrovacího seznamu je u jména KSP uvedena dvojice
Vaším úkolem je zašifrovat pomocí tohoto veřejného klíče číslo 123456789012345678901234567890. Nezapomeňte nám napsat, jak jste to rafinovaně provedli. Abyste si mohli ověřit, že vše funguje tak, jak má, prozradíme vám ještě, že tajný klíč je
Pokud znovu použijete nějakou část svého řešení úlohy 9-1-5, stačí, když na ně uvedete pouze odkaz.