3. Pofiderné kasíno vzorové riešenie

sudo apt-get install netcat

nc 158.195.16.154 9947

cd cesta_k_netcatu

chcp 65001

nc.exe 158.195.16.154 9947

def random():
    global seed1
    seed1 = (a*seed1)%10000
    return seed1

//Hodnotu a nepoznáte, medzi pokusmi sa však nemení
int a;

bool vyhral(){
    int x,y;
    cout << "Ake x tipujes?";
    cin >> x;               // načíta prvé číslo
    cout << "Ake y tipujes?";
    cin >> y;               // načíta druhé číslo
    int z = x*a + y;
    if(z<0) z = -z;         // pridaný riadok
    if(z<0) return true;    // Výhra - nemožné?
    else return false;      // Prehra
}

def random():
    global seed1
    seed1 = (a*seed1 + b)%9973
    return seed1

seed(int(time.time()))

def random():
    return randint(0,1000000)

Hlavným cieľom tejto úlohy bolo ukázať vám, že mnohé programy obsahujú chyby, ktorými sa dá tento program prinútiť robiť niečo iné, ako jeho tvorca zamýšľal. Vedieť hľadať takéto chyby je veľmi užitočné, hlavne pri opravovaní vlastných riešení. Jednou z veľkých chýb bývajú náhodné čísla – na počítači sa totiž nedajú generovať skutočne náhodné čísla, preto sa používajú takzvané pseudonáhodné čísla.

Ľubovoľný program sa v každom momente nachádza v nejakom stave – tento stav si môžme predstaviť ako celú pamäť programu, teda hodnoty jeho jednotlivých premenných, a číslo riadka, ktorý sa momentálne vykonáva. Je ľahké ukázať, že stavov je konečne veľa – program má predsa obmedzenú pamäť, napríklad veľkosťou pamäte RAM, a program tiež nemôže mať nekonečne veľa riadkov. Zároveň má program pre každý stav jasne definované, do akého ďalšieho stavu má prejsť. Počítač totiž nemá vlastnú vôľu a nemá sa podľa čoho rozhodovať. Musí sa pevne riadiť tým, čo sme mu určili. V tomto momente si možno poviete, že máme predsa príkazy, z ktorých vieme skočiť na rôzne miesta v programe – napríklad taký príkaz if. Ale if sa tiež rozhoduje podľa hodnôt príslušných premenných, teda podľa aktuálneho stavu.

Keby to samozrejme bolo také jednoduché, nevedeli by sme s počitačmi nijako interagovať a boli by nám vcelku nanič – chceme, aby sme vedeli zvonka meniť stav programu, napríklad pomocou klávesnice, myšky, momentálneho času, alebo nejakých iných senzorov. Väčšina týchto operácii je ale dosť drahá na čas – program na to, aby mohol získať nejaké vonkajšie informácie musí komunikovať s operačným systémom, čo trvá o dosť dlhšie ako keď si len počíta nejaké veci sám pre seba.

Z tohoto dôvodu je ťažké na počítači generovať skutočne náhodné čísla – program má konečné množstvo stavov, čiže ak by sme naprogramovali náhodný generátor, po nejakom čase by sa buď zastavil a prestal nám dávať náhodné čísla, alebo by sa dostal do stavu, v akom už bol, a začal by nám dávať znova tie isté čísla, čo teda rozhodne náhodné nie je.

Tento problém sa dá riešiť dvoma spôsobmi – prvým je, že použijeme generátor ktorý má dosť veľké množstvo stavov a teda by sa zacyklil po veľmi dlhom čase. Tieto čísla sú ale stále pseudonáhodné. Ak chceme na počítači získavať skutočne náhodné čísla¹, musíme od niekiaľ získať túto náhodnosť ktorá občas pomení stavy v programe. Tu prichádzajú do hry vonkajšie vstupy – napríklad pohyby myši, senzory, ktoré merajú teplotu procesora, momentálny čas atď.. Ako sme už ale zmienil, zisťovať tieto veci trvá dlhšie a preto si väčšinou vystačíme s nejakými dosť dobrými pseudonáhodnými generátormi.

Podúloha a)

Náhodný generátor v podúlohe a) mal veľmi málo stavov, preto stačilo len pozerať na to, aké čísla generuje. Po chvíli ste si mohli všimnúť, že sa začali opakovať a vtedy je už jasné, čo sa stane najbližšie – pozrieme sa, aké číslo sa po aktuálnom vypísalo naposledy a toto číslo tipneme.

Podúloha b)

Táto úloha vám mala ukázať, že pre počítače neplatia rovnaké pravidlá teoreticky aj prakticky – máme kód, ktorý vyzerá byť teoreticky správny, no má závažnú chybu. Problém je, že premenná typu int nemôže obsahovať ľubovoľne veľké číslo. Takáto premenná má len 32 bitov a teda obmedzený rozsah. Na väčšine požítačov má int so znamienkom rozsah od \(-2\,147\,483\,648\) do \(2\,147\,483\,647\). V pamäti počítača je int reprezentovaný 32 bitmi, ktoré môžu mať hodnoty 0 alebo 1. Na to aby sa odlišili záporné čísla od kladných, sa používa prvý bit – všetky kladné čísla ho majú nastavený na 0, záporné zasa na 1.

Na zapisovanie kladných čísel sa používa binárna sústava, otázka však je, ako zapísať čísla záporné. Najjednoduchšia možnosť je, aby číslo \(-x\) bolo zapísané rovnako ako \(x\), akurát by sa líšilo v prvom bite, ktorý reprezentuje znamienko. Takýto prístup má však dva problémy. Číslo 0 je zapísané dvoma spôsobmi (hoci \(-0\) neexistuje) a hlavne vypočítať \(-x+x\) (a súčty celkovo) je za pomoci binárnych operácii veľmi zložité – môžete si to vyskúšať na papiery.

Preto sa používa iný spôsob – dvojkový doplnokový kód. Hodnota \(-x\) sa z \(x\) určí nasledovne. Všetky jednotky v pôvodnom čísle zmeníme na 0, všetky 0 na jednotky, a následne k tomuto novému číslu pripočítame 1. Sčítavať čísla, teraz môžeme pomocou klasického binárneho súčtu. Súčet čísel \(x\) a \(-x\) teraz určite vyjde 0 – ak by sme nepripočítali 1, dostali by sme súčtom ich zápisov číslo kde by všetkých 32 bitov bolo nastavených na 1. Keďže ale my pripočítavame ešte 1, pretečie nám súčet do ďalšieho bitu, ktorý neexistuje, a v 32 bitoch, ktoré nás zaujímajú, nám zostanú teda samé 0. A naviac, aj 0 má v tomto prípade jediný zápis – 32 bitov nastavených na 0.

Našou úlohou je teraz nájsť jedno špeciálne číslo. Vieme totiž, že \(-z\) sa v programe vyhodnotí ako dvojkový doplnok \(z\). A existujú len dve čísla, ktorých dvojkový doplnok v 32 bitoch sa rovná pôvodnému číslu – je to číslo \(-2\,147\,483\,648\) a číslo 0.

Takže chceme dosiahnúť, aby premenná \(z\) mala nakoniec hodnotu práve \(-2\,147\,483\,648\), keďže hodnotu 0 dosiahnuť nevieme. Prvým krokom je zistiť hodnotu \(a\), čo vieme spraviť zadaním \(x=1, y=0\). V tomto prípade nám kasíno povie hodnotu \(a\). S jej pomocou už nie je vypočítať také \(x\) a \(y\), aby sa \(x\cdot a +y = -2\,147\,483\,647\) a keďže toto číslo vynásobené \(-1\) bude opäť to isté a teda záporné, podarí sa nám vyhrať.

Podúloha c)

Tento náhodný generátor mal už viac stavov, stále sa ale dali všetky vyčísliť – po maximálne 9973 volaniach by sa už určite dostal do stavu, v ktorom už bol a od toho momentu by bol zacyklený.

Vieme to však robiť aj rýchlejšie ako skúšať 9973 čísel. Stačí si uvedomiť, že pri hodnoťách \(a\) a \(b\) sa stačí pozerať na ich zvyšok po delení 9973. Ak by napríklad v jednom prípade bolo \(a=1\) a v druhom by bolo \(a=9974\), tak výsledok by bol rovnaký.

A keďže možností pre \(a\) a \(b\) nie je veľa, len 9974 pre každé z nich, dokopy nám stačí vyskúšať iba \(9974\cdot 9974 = 99\,480\,676\) možností. A na to, aby sme určili, ktorá z týchto možností je správna nám stačia tri prvé čísla, ktoré vytvorí generátor v kasíne. S pomocou krátkeho programu, ktorý vyskúša všetky tieto možnosti a zistí, či sedia na vypísané čísla dostaneme hodnotu ďalšieho tipu za pár sekúnd.

#Nacitame 3 cisla - pouzijeme pythonovsky trik
x,y,z = [int(x) for x in input().split()]
m = 9973

#Skusime pre kazde a,b ci by davali take nahodne cisla ako sme dostali
for a in range(m):
    for b in range(m):
        if (a*x+b)%m == y and (a*y+b)%m == z:
            print(a,b,(a*z+b)%m)

Podúloha d)

Tu to začalo byť ťažké – zatiaľčo predtým sme sa snažili oklamať slabo navrhnuté generátory, pythonovský randint má dosť veľké množstvo stavov, ktoré sa len tak rýchlo nezopakujú.

Prvý riadok kódu je seed generátora. Seed náhodného generátora je nastavenie jeho stavu na nejakú hodnotu. Ako sme si vysvetlili, náhodný generátor sa vždy nachádza v nejakom stave. Pomocou funkcie seed tento stav explicitne nastavíme. Z toho vyplýva, že ak dva rovnaké pseudonáhodné generátory nastavíme na rovnaký seed, budú nám generovať rovnaké čísla.

V kóde vidíme, že na začiatku sa generátor naseeduje na aktuálny čas. Toto je dosť bežná prax hlavne v C a C++ – na začiatku programu v nich má generátor vždy rovnaký stav, preto by pri spustení dával vždy tie isté čísla. Musíme teda zobrať niečo mimo programu, a aktuálny čas je na to dostatočne vhodný – môžme totiž očakávať, že program sa spustí väčšinou v iných časoch, pretože len málokto pustí ten istý program dva krát presne naraz. Toto ale nie je dokonalá technika – hacker by mohol napríklad zmeniť časti svojho systému tak, aby funkcia time vracala vždy rovnaký čas, alebo by mohol skúsiť program spustiť viac krát naraz.

V pythone sa seed časom deje automaticky. Keď importneme knižnicu random, automaticky zoberie momentálny čas a použije ho ako seed. Do nášho ukážkového kódu sme to napísali explicitne len preto, aby vám to trochu uľahčilo riešenie úlohy.

Je jasné, že ak by sa nám podarilo zistiť čas, ktorým sa generátor naseedoval, vieme potom nastaviť vlastný náhodný generátor na rovnaký seed a generovať rovnaké čísla ako server.

Opäť si vieme všimnúť, že možných seedov nie je veľa. Ich rozsah vieme zistiť vložením vypísaných časov do online konvertera časov na Unix timestamp, ktoré vracia funkcia time. Keď vkládame časy do konvertera, musíme si však dať pozor. Konverter očakával od nás čísla v časovom pásme GMT, zatiaľčo slovenský čas je buď GMT+1 alebo GMT+2, podľa toho, či je letný alebo zimný. Preto skôr ako sme daný čas konvertovali, museli sme od neho odpočítať 2 hodiny.

Potom si už len stačí vypísať prvých pár čísel, ktoré vygeneruje kasíno, nech vieme, aké čísla hľadať. Následne vieme postupne vyskúšať všetky možné seedy, pre každý vygenerovať viac ako 1000 čísel, a vyskúšať, či sa tých pár, ktoré nám povedalo kasíno zhoduje s nejakými za sebou idúcimi z tých, čo sa si vygenerujeme pre daný seed. Ak áno, objavili sme správny seed a zistiť hodnotu nasledujúceho čísla je už ľahké.

from random import randint,seed
#Najprv zoberieme prvy mozny seed a posledny mozny seed
zaciatok_cas, koniec_cas = [int(x) for x in input().split()]
#Zoberieme nejaku postupnost nahodnych vygenerovanych cisel
randomNums = [int(x) for x in input().split()]

# Vyskusame postupne vsetky mozne hodnoty seedu
for skusany_seed in range(zaciatok_cas,koniec_cas+1):
    seed(skusany_seed)
    arr = []
    for x in range(1500):
        # Tu zaciname - chceme naplnit nas zoznam momentalnych nahodnych cisel
        if len(arr) < len(randomNums):
            arr.append(randint(0,1000000))
        # Pokial ho uz mame naplneny, ked pridavame nove cislo tak uberieme
        # prve a pridame nove na koniec
        else:
            arr = arr[1:]
            arr.append(randint(0,1000000))
        # Otestujeme ci nas momentalny zoznam k nahodnych cisel sa rovna k ktore
        # hladame
        if arr == randomNums:
            print(skusany_seed, randint(0,1000000))