Albo rzecz o myśleniu programisty

Wstęp

Cześć,
Tym artykułem chciałbym otworzyć krótką serię artykułów pod tytułem „Teoretyczne minimum programisty”. Seria ta skierowana jest raczej dla początkujących programistów oraz tych, którzy dopiero zaczynają swoją przygodę z programowaniem. Moim celem będzie przybliżenie Wam szerokiego spektrum zagadnień związanych z podstawami informatyki. W tym artykule (jako otwierającym) skoncentruję się raczej na filozoficznej i logistycznej niż technicznej stronie inżynierii oprogramowania. Postaram się przedstawić Wam proces wytwarzania oprogramowania, dowiecie się czym jest myślenie obliczeniowe oraz poznacie podstawowe paradygmaty programiwania – trudne słowo, które wytłumaczę za dłuższy moment 😊.

Czym jest oprogramowanie

Na początku musimy sobie odpowiedzieć na pewne z pozoru błahe pytania – czym jest oprogramowanie oraz jak ono powstaje. W zasadzie komputer, od momentu naciśnięcia przycisku „Włącz”, nawet gdy nie jesteśmy jeszcze w stanie na nim nic fizycznie zrobić wykonuje całą masę programów. Najpierw jest to firmware (oprogramowanie układowe, wpalone w pamięć na płycie głównej), który ładuje do pamięci BIOS lub UEFI. One konfigurują wstępnie sprzęt aby mógł wystartować na nim system operacyjny, który dalej ładuje kolejne sterowniki, a później koordynuje pracę różnych procesów oraz zarządza sprzętem. Kiedy wystartuje system operacyjny (taki jak Windows, Linux czy Mac OS), dopiero wtedy możemy na nim uruchamiać nasze aplikacje użytkowe (takiej jak pakiet biurowy, program do edycji zdjęć czy przeglądarka internetowa) lub gry. Nie inaczej działają konsole do gier, smartphone’y, czy routery.

Warto zwrócić uwagę na drobne rozróżnienie – program jest to zbiór instrukcji dla komputera do zrealizowania, podczas gdy proces jest to aplikacja już uruchomiona tzn. system przydzielił jej zasoby (pamięć oraz czas procesora), załadował program do pamięci i zaczął go wykonywać.

Programy często wykorzystują również biblioteki funkcjonalne, dzięki którym nie trzeba pewnych podstawowych funkcji implementować od podstaw. W końcu nikt (a w szczególności korporacje liczące przede wszystkim na zysk) nie lubi odkrywać koła na nowo. Prawda jest taka, że jest wiele obszarów, które są na tyle ogólne (biblioteki do tworzenia graficznych interfejsów użytkownika czy serializacja danych, tj. zapisywanie danych w formacie umożliwiającym ich przesłanie np. przez Internet), że mogą być użyte dla praktycznie każdego scenariusza biznesowego. Między Bogiem i prawdą, gotowe, popularne biblioteki o otwartych źródłach są często solidnie przetestowane, a niektóre funkcjonalności jak kryptografia są zbyt wrażliwe na błędy by implementować je na własną rękę bez dobrego powodu.

Oprogramowanie możemy podzielić zasadniczo względem ich relacji ze sprzętem i systemem operacyjnym:

• Niskopoziomowe – kontrolujące sprzęt lub komunikujące się z systemem operacyjnym bezpośrednio poprzez wywołania systemowe (funkcje, które system operacyjny udostępnia programistom),
• Wysokopoziomowe – aplikacja nie wykorzystuje bezpośrednio elektroniki ani funkcji systemu operacyjnego.

Poza tym też możemy je podzielić względem zastosowań:

• Biblioteka użytkowa – udostępnia zbiór funkcji, które zazwyczaj są na tyle ogólne, że programiści mogą je zastosować w wielu różnych obszarach lub na tyle specyficzne, że kłopotliwym byłoby pisanie ich od podstaw,
• Aplikacja użytkowa – program, który jest po prostu użyteczny dla użytkownika,
• Firmware – oprogramowanie dla układów elektronicznych,
• Oprogramowanie dla systemów wbudowanych – oprogramowanie, które jest wykorzystywane w tzw. systemach wbudowanych, są to komputery, wyspecjalizowane do konkretnych zadań.

Elektronika

HAL – warstwa abstrakcji sprzętu

System operacyjny / sterowniki

Biblioteka standardowa języka

Biblioteki użytkowe

Aplikacje

Jak powstaje oprogramowanie

Teraz, kiedy wiemy, że cebula ma warstwy, ogry mają warstwy oraz oprogramowanie ma warstwy możemy przejść do krótkiego opisu w jaki sposób powstaje oprogramowanie. Omówię to w kilku (mam nadzieję, że krótkich) punktach

1.     Zbieranie wymagań

Podobno programista to osoba, która rozwiąże Twój problem, którego nie miałeś, w sposób, który nie rozumiesz przetwarzając w tym celu snikersy, Coca-Colę oraz kawę w kody programów. Niestety, to nie jest do końca prawda – klienci płacą tylko za sprawne programy (przynajmniej w dostatecznym stopniu), które realizują to czego się od nich oczekuje.

Aby mieć pewność, że wszystko jest jasne tworzy się listę wymagań funkcjonalnych – w świecie automotive’u nierzadko uzupełnionych o uzasadnienie oraz listę przeanalizowanych alternatyw razem z przyczyną ich odrzucenia.

Na potrzeby branży motoryzacyjnej powstał cały zbiór procesów, które należy przejść tworząc oprogramowanie aby zapewnić wysoką jakość produktów. Możecie pogooglować frazę ASPICE albo chwilę zaczekać bo planuję napisać o tym parę słów za jakiś czas). Czasem polemizowałbym z ich sensem gdyż bywają one tak sztywne, że nie wprowadza się poprawek, o ile nie są krytyczne,
gdyż wymuszałoby to tonę dodatkowej papierkowej roboty,

2.     Projektowanie architektury

W tej fazie architekci decydują o podziale aplikacji na mniejsze komponenty funkcjonalne oraz decydują o wewnętrznej strukturze aplikacji oraz planują w jakiej kolejności będą one implementowane.

Zazwyczaj projektując system staramy się zrobić to w taki sposób, by był on maksymalnie rozszerzalny i modyfikowalny.

3.     Implementacja

Chyba najprzyjemniejsza faza tworzenia oprogramowania. Programiści tworzą kody źródłowe w języku programowania, następnie kompilator tłumaczy je do formy zrozumiałej dla komputera (tzw. Języka maszynowego, ten etap kompilacji nazywamy fazą translacji) po czym linker łączy tak wygenerowane pliki z bibliotekami (nazywamy to fazą linkowania lub rzadziej, konsolidacji).

Kod źródłowy 1

Kod źródłowy 2

Biblioteka 1

Plik objektowy 1

Plik objektowy 1

Translacja

Translacja

Linker

Pliki obiektowe i biblioteki są przekazywane do  linkera

Program / Biblioteka

Linkowanie

Często sam system budowania aplikacji (tj. przekształcania kodu w działającą aplikację) jest projektowany tak aby proces kompilacji był szybszy gdyż przekłada się to na produktywność programisty – szybszy czas budowania, mniejsze straty czasu przy testach. Odczuwalne jest to w szczególności gdy pracuje się z systemami takimi jak Yocto (na szczęście używa się go tylko i wyłącznie do budowania całych dystrybucji systemu Linux)…

Edgar Dijikstra napisał kiedyś równanie:

Programy = Algorytmy + Struktury danych

Niektórzy dopisują tam również sterowanie, gdyż rzadko programy nie wymagają żadnej interakcji ze światem zewnętrznym – choćby w postaci danych.

Wracając do meritum czym jest algorytm? Nazwa wzięła się od łacińskiego algorithmus (oznaczającego obliczenia przy użyciu liczb arabskich) będącego zlatynizowaną formą arabskiego nazwiska Al Chwarizmi, matematyka perskiego z IX wieku.

Komputer ze swojej natury jest sekwencyjny – procesor pobiera z pamięci i wykonuje kolejne instrukcje. Algorytm jest to sekwencja kroków niezbędnych do uzyskania konkretnego efektu. Przykładowo algorytm parzenia kawy mógłby wyglądać następująco.

1. Weź kawę z półki
2. Jeśli nie jest zmielona – zmiel ją,
3. Zaparz wodę,
4. Zalej wrzącą wodą,
5. Odczekaj 5 minut żeby się nie poparzyć,
6. Dodaj cukru dopóki nie będzie odpowiednio słodka.

Widać tutaj trzy niezbędne elementy algorytmu:

• Sekwencja – kroki są wykonywane jeden po drugim,
• Bloki warunkowe – niekiedy musimy rozróżnić jakie zachowania podjąć w danych okolicznościach,
• Iteracje – niektóre kroki będziemy podejmować do momentu spełnienia pewnych warunków brzegowych, wynika z tego jedna z podstawowych zalet komputerów, nie powiedzą Ci po wykonaniu jednego kroku 1000 razy, że są zmęczone 😊.

Struktury danych definiują natomiast w jaki sposób dane są przechowywane w pamięci – co również może wpłynąć na prędkość ich przetwarzania.

W kolejnej części tego artykułu pochylimy się nad tematem wyobraźni obliczeniowej, dzięki której jesteśmy w stanie zaprojektować algorytm (tj. wyspecyfikować kroki, potrzebne do uzyskania oczekiwanego rezultatu).

4.     Testowanie

Dość wredny etap tworzenia oprogramowania… W końcu nikt nie lubi jak wskazuje mu się błędy i niedoróbki 😊.

Testy można podzielić ze względu na sposób ich przeprowadzania tj. manualne (żmudne, pracochłonne, każdy krok musi być ręcznie wykonany) czy automatyczne, albo ze względu na ich funkcję:

• Testy jednostkowe – pisane przez programistów sprawdzające podstawowe jednostki z których zbudowany jest program,
• Testy komponentowe – sprawdzają działanie konkretnych komponentów,
• Testy funkcjonalne – sprawdzają działanie konkretnych funkcjonalności,
• Testy integracyjne – testują działanie dwóch lub więcej zależnych od siebie komponentów.

Od testerów często oczekuje się certyfikatu ISTQB. Testerzy automatyczni dość często są już także praktycznie programistami choć często oczekiwania od nich są wciąż nieco mniejsze.

Według mnie,  chyba najbardziej upierdliwym elementem tego procesu jest specyfikowanie oraz dokumentacja testów. W moim obecnym projekcie dodatkowo wspieramy tzw. tracing requirement’ów. Przy każdym teście mamy wskazanie na wpis w dokumentacji use case’a testowego oraz odniesienie do wymagań funkcjonalnych – co sprawia, że czasem perspektywa poprawiania komentarzy w kodzie skutecznie zniechęca do wprowadzania poprawek w kodzie.

5.     Wdrażanie i utrzymanie

Z doświadczenia najnudniejszy etap – oprogramowanie jest wprowadzane na systemy produkcyjne, robota programisty sprowadza się zazwyczaj do łatania błędów (popularnie zwanych bug’ami).

W moim obecnym projekcie, pierwsze prototypy naszego komponentu powstawały na normalnym komputerze, dopiero później przy jednym z pierwszych release’ów (jest to moment wydawania nowej wersji w cyklu życia programu) przetestowaliśmy go na płytce, która docelowo trafiała
do samochodu.

Proces, który Wam opisałem nosi nazwę tzw. Waterfall’a, jest to tak zwany kaskadowy model tworzenia oprogramowania. Stosowany jest w sytuacji gdy wymagania są proste i przejrzyste w szczególności do prostych aplikacji.

Modnym ostatnio modelem jest SCRUM (z ang. młyn).

Oprogramowanie powstaje w sposób przyrostowy. Proces jest podzielony na sprinty, na koniec każdego dostarczony jest produkt z coraz większą liczbą funkcji. W SCRUMie każdy sprint ma swój ceremoniał składającego się z szeregu spotkań:

1. Sprint refinement – w ramach którego wykonuje się wstępną inwestygację zadań do wykonania w najbliższym czasie,
2. Sprint planning – zespół estymuje ile czasu zajmą zadania i wybiera te, które zostaną zrealizowane w ramach sprintu,
3. Daily – codzienne spotkanie w czasie których dyskutowane są postępy w realizacji zadań,
4. Sprint review – ewaluacja sprintu, dyskusje co udało się zrobić a które będą kontynuowane w kolejnym sprint’cie,
5. Sprint retrospective – wymiana wrażeń na temat pracy w danym sprintcie, problemy, wyzwania i co można poprawić w kooperacji zespołu.

Sam osobiście nie jestem wielkim miłośnikiem tego modelu. O ile pomysł iteracyjnego tworzenia oprogramowania i by nie rozwiązywać na samym początku problemów których jeszcze nie mamy projektując od razu całą aplikację od zera uważam za dobry tak sam SCRUM może być kłopotliwy.

Zależnie od typu zadań i tego jak długo trwają scrumowe gusła (tutaj czyt. potkania 😉) może to drastycznie skracać faktyczny czas na zrealizowanie zadań. Zdarzyło mi się pracować w zespole w którym podzielono nas na dwa podzespoły:

1. Realizujący nowe funkcjonalności niezależne od HAL’a maszyny,
2. Dodający funkcjonalności zależne od HAL’a maszyny, które wymagały często dodatkowej analizy starego kodu, dodatkowo napisanego nie do końca zgodnie ze sztuką inżynierii oprogramowania… Strzeżcie się kodu pisanego przez naukowców 😊

Okazało się, że o ile dwutygodniowy okres sprintu dla podzespołu 1 był wystarczający tak w drugim optymalną długością były trzy tygodnie. W szczególności, że refinement’y, planningi, retrospektywy pochłaniały praktycznie około 2-3 dni roboczych (czyli de facto 20-30% czasu sprintu) bo nieraz wypadało się jeszcze do tych spotkań przygotować. W późniejszym okresie udało się to nieco skrócić 😉.

Na szczęście mimo wszystko moje wspomnienia z retrospektyw mimo wszystko są raczej pozytywne – dyskusje i spostrzeżenia dotyczące komunikacji w zespole i analizy co poszło dobrze, jakie problemy się pojawiły dość często faktycznie poprawiały sytuację i umacniały ducha zespołowego a… teraz w końcu przejdę do nieco bardziej filozoficznej części artykułu!

Myślenie obliczeniowe

W akapicie poświęconemu implementacji rozwiązań wspomniałem o pojęciu wyobraźni obliczeniowej. Chcąc zaproponować rozwiązanie algorytmiczne problemu z tzw. realnego świata, analizujemy je zazwyczaj podobnie jak w czasach szkolnych rozwiązywaliśmy zadania z matematyki.

Aby zdefiniować zbiór kroków, które komputer musi wykonać aby rozwiązać problem. Pierwsze co próbujemy zrobić to dokonać dekompozycji problemu tj. rozłożyć problem na mniejsze, które z dużym prawdopodobieństwem będzie łatwiej rozwiązać. Kolejnym krokiem jest dokonanie generalizacji, rozważenia czy istnieją pewne ogólne własności, pomocne w rozwiązaniu zadania. Następnie możemy zastosować logiczne wnioskowanie,aby wybrać użyteczne dla nas własności by koniec końców przejść przez wszystkie proste problemy, wyodrębnione w fazie dekompozycji. Ważnym elementem jest spojrzenie na problem z pewnego poziomu abstrakcji – należy uzmysłowić sobie w jaki sposób elementy prawdziwego świata można przedstawić tak. by rozwiązać zadany problem.

Zatem podstawowymi narzędziami przy projektowaniu algorytmów są:

• Dekompozycja,
• Generalizacja
• Logiczne wnioskowanie
• Abstrakcja.

Używamy ich, aby rozwiązać problem wciąż na pewnym poziomie abstrakcji a następnie używając już myślenia algorytmicznego definiujemy sekwencję kroków do wykonania dla komputera aby wykonał część obliczeniową.

Często też okazuje się, że wiele problemów sprowadza się do tego samego. Spójrzcie na tak zdefiniowany problem: jaka jest najkrótsza droga pomiędzy Wrocławiem a Warszawą?

Problem ten możemy podzielić na podproblemy:

1. Jakich danych potrzebujemy?

Najlepiej mapę drogową z podanymi długościami odcinków drogowych.

• Jak reprezentować mapę?

Możemy wyobrazić sobie każdą wioskę, miasto i miasteczko jako wierzchołek w grafie. Każda droga pomiędzy nimi jest krawędzią o wadze, która odpowiada długości odcinka.

• Jak znaleźć najkrótszą drogę?

Problem znalezienia najkrótszej ścieżki pomiędzy dwoma wierzchołkami w grafie z wagami dodatnimi (ciężko przejechać -100 km 😊) jest już klasycznym problemem rozwiązujemy go dość często algorytmem Dijikstry (w tym miejscu nie jest istotne jak on działa).

Zatem program odpowiadający na nasz problem mógłby wyglądać tak:

1. Wczytaj drogi pomiędzy miastami,
2. Utwórz graf sieci dróg,
3. Ustaw wierzchołek początkowy na Wrocław,
4. Ustaw wierzchołek końcowy na Warszawę,
5. Uruchom algorytm Dijikstry by znalazł najkrótszą drogę z Wrocławia do Warszawy.

Problemy grafowe są dość wdzięczne pod względem liczby zastosowań. Wyobraźcie sobie, że dowódcy wojskowi zajmują się logistyką i planują w jaki sposób zabezpieczyć dostawy na front tak aby zminimalizować ryzyko przerwania trasy kolejowej przez uszkodzone mosty. W tym przypadku, też będziemy wykorzystywać grafy, ale nie interesuje nas odległość a liczba krawędzi więc każda będzie miała wagę 1. Moglibyśmy również użyć algorytmu Dijikstry ale o wiele łatwiej jest to rozwiązać poprzez tzw. przejście grafu wszerz. Dzięki dokładnej analizie problemu jesteśmy w stanie wybrać odpowiednie algorytmy dla naszego problemu.

Grafy mogą być używane także zarówno w kontekście sprawdzania poprawności certyfikatów kryptograficznych, logistyce, jak i analizie sprawności sieci komputerowych i uwierzcie mi na słowo, że jest tego o wiele więcej.

Języki programowania

Kiedy już mamy algorytmy możemy się zastanowić w jaki sposób zrealizować je z wykorzystaniem komputera i tutaj pojawia się nasz ostatni element układanki czyli język programowania. Podstawowym językiem dla komputera jest kod maszynowy czyli zestaw rozkazów procesora reprezentowanych jako ciąg liczb. Prawda jest jednak taka, że w miarę rozwoju technologii używanie go dość szybko okazało się niewygodne i powstały asemblery – rodzina języków programowania,
w której kody poszczególnych operacji zostały zamienione na łatwe do zapamiętania skróty (tzw. mnemoniki). Później powstawały kolejne języki, które miały zwiększyć produktywność programistów oraz naukowców (gdyż oni pierwsi wykorzystywali komputery, najczęściej do celów wojskowych, takich np. jak projekt Manhattan czy przewidywania pogody).

Wiele eksperymentowano… pierwsze języki przypominały trochę eksperymenty małego dziecka, które nie do końca zdaje sobie z tego co potrafi. W ubiegłym wieku powstało ich pewnie co najmniej kilkaset, część z nich wprowadzały nowe pomysły dotyczące paradygmatu programowania (sposobu w jaki możemy myśleć tworząc programy, rozwinę to za chwilę), inne składniowe (niektóre się przyjęły, inne nie) albo zwiększały poziom abstrakcji i uniezależnienia od maszyny. W pewnym momencie zauważycie, że znaczna część z nich jest do siebie w pewnym stopniu podobna, przynajmniej dopóki implementują ten sam paradygmat.

Paradygmaty programowania

Pierwszy paradygmat był prostą konsekwencją tego jak działa procesor. Procesor pobiera z pamięci jedną instrukcję, dekoduje ją i wykonuje. Proces trwa dopóki komputer jest włączony. Instrukcje natomiast są różne… Mogą dodawać, odejmować, zapisywać do pamięci i odczytywać z pamięci i wiele innych ale co ważne w tym momencie dla nas umożliwiają skok do innego obszaru kodu, który może być wykonany pod pewnymi warunkami.

Dość szybko zauważono, że przy użyciu skoków i instrukcji warunkowych procesora można implementujemy pewne podstawowe struktury, którymi są pętle (blok kodu, który jest wykonywany dopóki warunek jest spełniony) oraz bloki warunkowe (fragmenty kodu wykonywane w określonych warunkach). Tak powstało programowanie strukturalne.

Kod maszynowy       Assembler	Kod w języku C

Później spostrzeżono, że część kroków w kodzie jest używana na zasadzie kopiuj-wklej – kolejnym, naturalnym etapem było więc wydzielenie osobnych funkcji i łączenie ich w większe moduły, które byłyby ponownie używalne na przestrzeni całego kodu. I tak oto doszliśmy do etapu w którym wynaleziono programowanie proceduralne.

Kolejną ewolucją, która na dobre zagościła w świecie języków programowania jest programowanie obiektowe. Jest to obecnie chyba najpopularniejszy paradygmat a co zabawne zręby idei pojawiły się już… w starożytnej Grecji. Platon z Arystotelesem stworzyli teorię nazywaną dzisiaj teorią idei. Mówi ona, że:

Zgodnie z dominującą wykładnią filozofii (i powyższej alegorii) Platona ogół tego, co istnieje, dzieli się na dwie sfery – sferę przedmiotów fizycznych, wśród których aktualnie żyjemy, i sferę przedmiotów idealnych, które są poza naszym bezpośrednim zasięgiem. Pierwsze mają się do drugich tak, jak cienie do autentycznych rzeczy lub jak niedoskonałe ucieleśnienia do ich doskonałych wzorców. Owe rzeczy lub wzorce – stanowiące „prawdziwszą” lub „lepszą” rzeczywistość – Platon nazwał ideami lub formami.

Skąd wiadomo, że idee istnieją? Jeden z argumentów za ich istnieniem wygląda następująco. Przedmioty fizyczne układają się w grupy (zbiory), których elementy są do siebie podobne. Każdą z tych grup opatrujemy osobnym pojęciem i nazwą.

Źródło: https://antycznahellada.com/2020/03/15/swiat-idei-platona/

W programowaniu proceduralnym dane i procedury nie są ze sobą w żaden sposób związane podczas gdy programowanie obiektowe zmienia to drastycznie. Programiści tworzą klasy, które są swego rodzaju matrycami opisujące świat przedstawiony w programie. Klasy zawierają dane potrzebne do opisu przedmiotu oraz metody czyli zachowania specyficzne, które też mogą być dziedziczone. Ważną cechą języków obiektowych jest hermetyzacja danych – nie wszystkie są dostępne na zewnątrz.

Przykładowo, gdybyśmy pisali program do przechowywania informacji o zwierzętach w ZOO moglibyśmy stworzyć klasę Animal, która przechowywałaby informację o imieniu zwierzęcia i klasy tj. Reptiles czy Mammals, które będą miały bardziej charakterystyczne cechy tych grup gatunków jak np. pełzaj dla płazów i skacz dla ssaków 😉.

Rysunek 1 ClientFactory przy tworzeniu otrzymuje obiekt typu ConfigurationBundle, używa go aby utworzyć konkretny typ klienta

Cechą wspólną dla tych trzech paradygmatów jest to, że reprezentują one grupę paradygmatów imperatywnych – programista opisuje w nich proces wykonania jako sekwencję instrukcji zmieniających stan programu. Przeciwieństwem ich są paradygmaty deklaratywne (ostatnio modne programowanie funkcyjne czy programowanie w logice) w których programista raczej definiuje co ma zostać obliczone. Na przestrzeni ostatnich lat można zauważyć coraz silniejszy wpływ języków funkcyjnych na nowe funkcjonalności w językach imperatywnych. W językach czysto funkcyjnych nie są przechowywane żadne stany oraz funkcje nie są rozumiane jako sekwencje instrukcji do wykonania a raczej w sensie matematycznym, które przekształcają dziedzinę (argumenty) w zbiór wartości.

Programując w logice programista definiuje raczej zbiór relacji, które muszą zajść aby rozwiązać problem.

Język a ekosystem

Pamiętacie jak na początku artykułu wskazałem, że programowanie niskopoziomowe jest to tworzenie oprogramowania na styku systemu operacyjnego lub elektroniki? W przypadku języków programowania podział na języki niskiego poziomu i wysokiego poziomu jest dość subiektywny.

Co do jednego nikt się nie kłóci – na pewno językiem niskopoziomowym jest asembler. Język C? Za pewne niektórzy hardcore’owi niskopoziomowcy by się kłócili, mnie natomiast przekonuje argument, że jest to język w którym ręcznie zarządzamy pamięcią oraz są w nim pisane systemy operacyjne, sterowniki oraz oprogramowanie na mikrokontrolery.

Języki wysokopoziomowe są to języki dzięki którym tworzony kod będzie wyrażał bardziej abstrakcyjne idee. Bardzo często języki te łączą cechy wielu paradygmatów, najpopularniejsze języki łączą w sobie programowanie strukturalne, obiektowe oraz pewne cechy funkcyjne. Przykładem języków wysokopoziomowych są C++, Java, C#, Python, Ruby itd… I z tej listy tak na prawdę jedynie C++ jest kompilowany bezpośrednio do kodu maszynowego.

Języki takie jak Java oraz C# są kompilowane do swego rodzaju kodu bajtowego, który jest wykonywany przez środowisko uruchomieniowe – abstrakcyjną maszynę dzięki której program może być wykonany na dowolnym systemie na którym jest ona dostępna. Python oraz Ruby nie są kompilowane a interpretowane na bieżąco przez interpreter. Najczęściej językami interpretowymi są języki skryptowe (tj. Python, Ruby, Perl czy bash; skrypty były to proste programy wykonywane przez wiersz poleceń aby zautomatyzować pewne czynności administracyjne), chociaż istnieją wyjątki takie jak język D.

Ciekawym przykładem jest C++ – z jednej strony udostępnia wysokopoziomowe funkcje a z drugiej wciąż mamy możliwość programowania niskopoziomowego. Będąc profesjonalnie programistą C++, kiedy spotykam się z kolegami tęskniącymi z asemblerem jestem programistą pracującym na wysokim poziomie abstrakcji, podczas gdy dla kolegów Javowców jestem niskopoziomowcem… Jest to jedyny akceptowalny dla mnie konflikt w poczuciu własnej tożsamości 😊.

Wiecie, tak na dobrą sprawę, na stronie OSDev (wiki.osdev.org) można znaleźć artykuły jak napisać system operacyjny zarówno w języku C, jak i w językach wysokopoziomowych takich jak C++, D, Rust, czy Ada.

Kilka przykładów języków, które warto kojarzyć

Możecie znaleźć na internecie kursy wielu różnych języków programowania. Ja skoncentruję się na tym blogu pewnie na Rust’cie, którego się aktualnie uczę (i co by nie mówić zyskuje ostatnio coraz większą popularność), coś być może pojawi się z C/C++’a z którymi pracuję od lat i nęcącej mnie od jakiegoś czasu Adzie jednak chciałbym podać Wam krótką listę języków programowania, które warto kojarzyć. Zastawienie jest mocno subiektywne i czasem nie do końca poważne 😉. W większości języki te są imperatywne chyba, że wprost napisałem, że jest inaczej (np. jest funkcyjny albo służy do programowania w logice, jest tutaj tylko jeden przedstawiciel tej grupy).

Nazwa języka	Komentarz
COBOL	Wspomniany wcześniej Edgar Dijikstra powiedział kiedyś „Używanie COBOL’a uwstecznia; jego nauczanie powinno być tym samym uznane za przestępstwo kryminalne”. Bardzo stary i nie powstają w nim żadne nowe projekty… O ile wiem programista COBOL’a jest poszukiwany gdy jego poprzednik zmarł.
Fortran	Język ogólnego przeznaczenia (tzn. można w nim zrobić praktycznie wszystko) choć pierwotnie zaprojektowany do programów obliczniowych… I prawdę mówiąc kojarzy mi się jedynie jako język dla naukowców do obliczeń numerycznych i symulacji.
Scheme	Pierwszy język z tej listy z którym miałem przyjemność obcować chwilę dłużej. Język będący dialektem Lisp’u – prawie legendarnego języka, który szybko stał się najchętniej wybieranym pod kątem badań nad sztuczną inteligencją. Jest to język funkcyjny, którego cała składnia opiera się na listach… czego konsekwencją jest masakrycznie duża liczba nawiasów. Przykład kodu – implementacja algorytmu szybkiego sortowania
Haskell	Podobnie jak poprzednik, jest to język funkcyjny… CZYSTO funkcyjny! (krzyk jest nie przypadkowy) Nie ma stanów, nie ma pętli a jest tylko wszechogarniająca rekurencja 😊 Programiści Haskell’a przez jego leniwość (obliczenia są wykonywane dopiero wtedy kiedy ich wynik jest potrzebny) potrafią stworzyć nieskończoną listę elementów w skończonym czasie. Nie znam go dobrze, ale zawsze sprawiał na mnie wrażenie dość eleganckiego języka.   Przykład kodu – implementacja algorytmu szybkiego sortowania
Basic	Stary język… Nie jeden programista zaczynał od niego swoją przygodę z programowania np. na komputerach Comodore. Pochodzę z tego pokolenia, których jedynym kontaktem z tym językiem były opowieści starszych kolegów po fachu. Swego czasu Microsoft stworzył na jego podstawie całkiem fajny język do nauki programowania dla młodzieży o nazwie SmallBASIC. Poza tym, chyba stosunkowo nie dawno Microsoft wyrugował aplikację Visual Basic z ich środowiska programowania Visual Studio. Obecnie pozostał on w użyciu chyba jedynie w pakiecie Microsoft Office do obsługi makr.
Pascal	Uczono go w klasie równoległej do mojej kiedy byłem w liceum… Obecnie nie jest zbyt popularny choć miał swój okres chwały. Przez wiele lat, firma Borland (obecnie Embarcadero) tworzyła swój własny dialekt o nazwie Delphi i środowisko programistyczne, które umożliwiało w łatwy sposób tworzyć aplikacje okienkowe.
C	Pierwszy język, którego byłem uczony na studiach, choć nasz wykładowca nie był jego wielkim fanem. Język, który stanowi lingua franca informatyki i wywarł znaczący wpływ na składnię chyba większości współczesnych języków.   Zaimplementowano w nim jądro Linux’a, do dziś pisze się w nim sterowniki, aplikacje na mikrokontrolery i na wszystko co ma mocno ograniczone zasoby albo platforma na którą piszemy jest tak rzadka, że nic innego nie jest dostępne 😉 Jeśli jest coś co przetrwa apokalipsę zombie to pewnie będzie oprogramowane w C! Wciąż króluje także w świecie mechatroniki motoryzacyjnej za sprawą Classic Autosara.   Jest najbliższy do Torvaldsowego (twórca Linuksa) zdania: „Gdzie się podziały te czasy, gdy mężczyźni byli mężczyznami i sami pisali swoje sterowniki” – programiści C muszą sami zarządzać pamięcią, przez co większość programistów uznaje go za język trudny w obyciu.
C++	Język od którego sam zaczynałem moją przygodę z programowaniem… Zanim napiszę o nim parę słów od siebie parę cytatów: „C pozwoli Ci łatwo odstrzelić sobie stopę; C++ czyni to trudniejszym, ale jak już wybuchnie to rozwali całą nogę” – Bjarne Stroustrup, twórca języka „Ja wcale nie nienawidzę C… Po prostu moje odczucia wobec niego są ambiwalentne” – Scott Meyers, ekspert języka C++, twórca książki „Skuteczny, nowoczesny C++”   Język wysokopoziomowy i obiektowy ale wciąż może być wykorzystywany do tworzenia systemów operacyjnych i oprogramowania na mikrokontrolery… Chociaż tam wciąż spisuje się lepiej C ze względu na mniejsze rozmiary skompilowanego kodu. C++’a używamy obecnie najczęściej w systemach wbudowanych na mocniejszych platformach (np. w automotive, C++ jest językiem wiodącym w platformie Adaptive Autosar) oraz grach komputerowych ze względu na większą produktywność niż w C.   Programista wciąż musi myśleć o zarządzaniu pamięcią, chociaż dzięki tzw. inteligentnym wskaźnikom jest to o wiele przyjemniejsze.
Java	Język obiektowy, który w założeniu miał działać na wszystkim o ile jest dostępna maszyna wirtualna. Obecnie najczęściej wykorzystywany do tworzenia oprogramowania na telefony komórkowe oraz do oprogramowywania backendu tzn. logiki biznesowej aplikacji webowych (np. systemów sprzedaży internetowej e-commerce).   Chyba najbardziej charakterystyczną cechą jest garbage collector – mechanizm, który odpowiada za sprzątanie nieużywanej pamięci… Problem z nim jest taki, że włącza się kiedy chce, istnieje polecenie do wywołania tego mechanizmu, ale maszyna wirtualna traktuje to wyłącznie jako sugestię. Nie jestem specjalnie fanem tego języka, też często przez mentalność programistów, która mówi – „Mam gdzieś zasoby, w razie czego zmienię maszynę na mocniejszą”.
C#	Microsoftowa odpowiedź na Javę… i powiedziałbym, że ciut ładniejsza (jeśli kierować się względami estetycznymi). Najczęściej używana do tworzenia aplikacji na Windowsa i backendu aplikacji webowych. Jakiś czas temu powstał projekt o nazwie dotnet Core dzięki któremu możemy korzystać z C# także na Linuksach i Mac’ach
D	Moja pierwsza miłość jeśli chodzi o mniej standardowe języki programowania. Język za którym stoi wiele mądrych głów ale niestety zbytnio się nie przyjął – mimo to używano go między innymi w Facebooku. Wspiera programowanie obiektowe, zaprojektowany przez Waltera Bright’a, twórcę pierwszego kompilatora C++ tłumaczącego bezpośrednio do kodu assemblera (wcześniej był tłumaczony najpierw do C a potem C było kompilowane do assemblera).   Cechą, która mi się podobała jest to, że posiada garbage collector, który można wyłączyć gdy potrzebujemy sami zarządzać pamięcią dla zwiększenia wydajności. Natomiast zniechęcił mnie system budowania z którym za bardzo nie potrafiłem się dogadać.   Wydaje mi się, że mógł się nie przyjąć przez fakt, że istniały dwie iteracje tego języka – D1 i D2 (współcześnie znany jako D). W języku D1 istniały dwie biblioteki standardowe Phobos (opracowywany m.in. przez Alexandrescu, eksperta od C++’a, rozwijała się powoli) oraz Tango (szybciej rozwijana bo przez środowisko, ale gorzej przetestowana), które były niekompatybilne względem siebie. W D2 (znanym dalej jako D) rozwiązano problem wprowadzając standardowy mechanizm obsługi wątków i garbage collectora.
Ada	Na razie za wiele o nim nie wiem. Zaprojektowany dla wojska a używany głównie w lotnictwie. Z tego co czytałem wydaje się wręcz stworzony do systemów wymagających bezpieczeństwa.
Rust	Nowoczesny język, który nadaje się do programowania systemów wbudowanych. Ostatnio powoli wchodzi jako jeden z języków używanych w ramach jądra Linux’a oraz Androida. Przy okazji wydaje się, że będzie coraz częściej używany także w branży automotive patrząc, że są prowadzone prace by można go było wykorzystywać w sytuacjach safety tj. kiedy muszą zostać spełnione normy ISO-26262. Zaprojektowany przez Mozillę.
Golang	Inny stosunkowo młody język, zaprojektowany przez Google’a, który całkiem fajnie się sprawdza w zadaniach rozproszonych. Moje główne skojarzenia z nim odnoszą się głównie z aplikacjami od Docker’ów.
Python	W mojej opinii fajny język dopóki używa się go do prototypowania. Często używany do skryptowania, małych aplikacji webowych oraz przez naukowców do symulacji i obliczeń.
Ruby	Kolejny język skryptowy, który kojarzę głównie za sprawą swego czasu modnego frameworku Ruby on Rails, i chyba to jest jego najczęstsze zastosowanie.
PHP	Martin Lechowicz śpiewał kiedyś „Programuję w dotnecie już trzecie stulecie bo kto się w PHPie połapie”… Kolejny język używany w aplikacjach internetowych o którym zbyt wiele nie wiem.
JavaScript	Język skryptowy wykonywany przez przeglądarki internetowe, najczęściej służy do oprogramowania działania front-endu, czyli tzw. widocznej części aplikacji internetowych.
Prolog	Język deklaratywny, służący do programowania w logice. Program stanowi sekwencję przesłanek, które muszą zostać spełnione, aby rozwiązać problem. :- – oznacza implikacje, tj. quicksort([X|Xs], Ys) :- … oznacza, że element X skonkatenowany z Xs jest w relacji quicksort z Ys jeśli spełnione są warunki …

Ostatnio też zauważalna jest tendencja do tworzenia języków kompatybilnych z ekosystemami związanymi z istniejącymi językami programowania:

• Java => Scala, Clojure, Kotlin
• JavaScript => TypeScript,
• C++ => Carbon.

Po co tworzyć takie języki? Historia każdego jest nieco inna… Język programowania jest formą dzięki której programiści mogą wyrażać swoje myśli. Dobrym przykładem tego jest Clojure, który posiada składnię LISPu, ale wciąż działa na maszynie wirtualnej Javy dzięki czemu oba mogą koegzystować w ramach jednej aplikacji. Z drugiej strony istniejące języki nie rzadko cierpią na chorobę wieku dojrzałego. Dodajemy w nich nowe funkcje, ale nie zmieniamy części jego wcześniejszych cech dla zachowania kompatybilności przez co stają się coraz bardziej skomplikowanymi (przypadek C++’a, w którym niedługo sam diabeł nie dojdzie co się dzieje 😉). Nowy język może zachować zgodność z bibliotekami napisanymi w starym języku jednakże oferując czystszą składnię – tego przykładem jest Carbon, którego celem w teorii jest stopniowe zastępowanie części starego kodu w C++’ie. Jednak wciąć twórcy tego języka zalecają, że jeśli projekt pisany jest od podstaw, zalecane jest użycie Rust’a (pomijając nawet fakt, że nie jest on jeszcze dość dojrzały, żeby używać go na produkcji).

Zakończenie

To już koniec, mam wrażenie, że macie już pewne wyobrażenie jak wygląda praca programisty. W kolejnych artykułach przejdę na reszcie do technikaliów 😊

Miłego wieczoru!

Paweł

Sezamie otwórz się, krótko o dowodach z wiedzą zerową

Cześć!

Pamiętacie może dziecięce przepychanki w stylu „Wiem, ale nie powiem”? Dzisiaj zastanowimy się w jaki sposób projektanci kryptosystemów radzą sobie z podobnym problemem – jak  udowodnić znajomość sekretu (np. tajnego klucza) bez ujawniania go nikomu

.

Analogia jaskini jako przykład dowodu o wiedzy zerowej

Możemy to zrobić korzystając ze swego rodzaju dowodu nie wprost, zanim jednak pokażę Wam to na przykładzie protokołu identyfikacji Schnorr’a, chciałbym żebyście przyjrzeli się pewnej dość obrazowej analogii. Spójrzcie na rysunek poniżej.

Wyobraźcie sobie, że ta grafika przedstawia plan kampusu NSA (amerykańskiej Agencji Bezpieczeństwa Narodowego). Drzwi 2 stanowią wejście do cywilnej części budynku podczas gdy drzwi 3 są dla personelu wojskowego. W bazie pod numerem 1 znajduje się pomieszczenie z klatką schodową prowadzącą do podziemnej serwerowni i jest to jedyne bezpośrednie przejście pomiędzy częścią cywilną a wojskową. Wejścia na klatkę od obu stron zabezpieczone są kartą magnetyczną z PIN’em. Część personelu wojskowego zajmująca się sprzętem komputerowym ma dostęp do serwerowni oraz obu części budynku… Chociaż tak między Bogiem i prawdą, Kevin Mitnick we wspomnianej kiedyś książce „Sztuka Infiltracji” opisywał, że największe uprawnienia dostępu fizycznego mają zazwyczaj sprzątaczki 😉.

Główną bohaterką opowiadania będzie żona jednego z pracowników. Teraz wszędzie jest moda na szukanie ruskich agentów więc założymy, że została ona podkupiona przez rosyjskie służby aby ustalić czy jej mąż posiada dostęp do serwerowni. Ponieważ nie jest ona drugim Jamesem Bondem wynajęła do pomocy prywatnego detektywa. Na szczęście mąż też nie jest na tyle rozgarnięty aby pamiętać, którymi drzwiami danego dnia wchodził 😉.

Przejścia są pilnowane przez portiera, aby nikt nie uprawiał tzw. tailgating’u, tj. wchodzenia na ogonie jednak doświadczony detektyw wie, że skoro jest on średnio rozgarnięty (agent w stylu Johnny’ego English’a) nie da rady pilnować się zawsze – przyjęto za okres obserwacji 3 miesiące. W końcu udało się i na sam koniec pracy z teleobiektywem w ręce dojrzał mężczyznę wchodzącego drzwiami 2 i wychodzącymi 3.

Zmienimy teraz nieco tę historię – przez 3 miesiące mężczyzna się pilnował a żony nie jest stać na dalszą obserwację bo męża zdziwi saldo na koncie. Żona wykazała się wręcz szatańską pomysłowością. Otóż pani, nazwijmy ją Twardowska (w końcu amerykanie nie rozróżniają polskich od rosyjskich nazwisk), wymyśliła sobie grę. Umówiła się z mężem, że nie będzie pilnować jak pan Twardowski wchodzi ale będzie mówić mężowi którymi drzwiami ma wyjść 😊. I tego dopilnuje… Jak powiedziała tak zrobiła. W końcu musi obserwować go tylko przez godzinę czy dwie a nie musi płacić pełnej dniówki detektywowi. A biorąc pod uwagę, że mąż wie, że nie ujawni informacji, którymi drzwiami wszedł mówi: „Dobra, zacznijmy zabawę!”. Czy mąż wyciągnął prawidłowe wnioski?

Odpowiedzmy sobie na pytanie – jakie jest prawdopodobieństwo, że mężczyzna zna PIN przy jednej próbie? Prawdopodobieństwo, to wynosi . Spójrzcie na tabelkę poniżej – jedynka oznacza, że wybrał on dokładnie to samo wyjście co żona.

		Wybrane przez żonę wyjście
		Lewe drzwi	Prawe drzwi
Losowo wybrane przez męża wejście	Lewe drzwi	1	0
	Prawe drzwi	0	1

Sprawdźmy jakie będzie prawdopodobieństwo, że w tydzień, stosując tą, grę poznamy prawdę? Prawdopodobieństwo, że przez tydzień zarówno wchodził jak i wychodził jest… pewne czyli wynosi 1. Przeprowadźmy krótkie rachunki:

Zdarzenie to jest więc niemal pewne. Zwróćcie uwagę, że poznaliśmy informację czy mąż zna PIN a nie zdradził nam samej informacji. Czy da się zrealizować coś podobnego wykorzystując matematykę? Bajeczka może i jest dość mocno naciągana ale pokażę Wam teraz protokół Schnorr’a dzięki któremu jedna osoba może udowodnić drugiej znajomość tajnego klucza nie zdradzając go.

Protokół identyfikacji Schnorr’a

Zacznijmy z kolejną historią – łatwiej będzie przedstawić mi protokół, jeśli naszym bohaterom nadamy imiona 😉 Nazwijmy ich Alicja (będzie ona posiadaczką tajnego klucza) i Bob (będzie miał informację potrzebną do weryfikacji). Alicja chce udowodnić Bobowi znajomość sekretu – aby to zrobić musi przeprowadzić z nim wymianę kilku wiadomości. Spójrzcie na diagram poniżej, jednak najpierw parę założeń:

1. g jest parametrem znanym zarówno przez Alicję i Bob’a,
2. Alicja jest posiadaczką klucza prywatnego  i przekazała Bob’owi wartość ,
3. Liczby a oraz c są losowymi liczbami naturalnymi.

W jaki sposób to równanie zdradza nam, że Alicja zna hasło? Odpowiedź tkwi w matematyce jeszcze z lat szkolnych. Dowód jest następujący:

Równość jest tylko wtedy prawdziwa, gdy Alicja zna klucz prywatny. Pozostało jeszcze pytanie czy jest on bezpieczny. Dowodzimy tego z wykorzystaniem tzw. modelu z wyrocznią losową.

Dowody z wyrocznią losową

Cały pomysł dowodu inspirowany jest wyrocznią delficką. W starożytnej Grecji, w miejscowości Delfy znajdowała się znana niegdyś w całym antycznym świecie wyrocznia. Za przepowiednie odpowiadała Pytia – siedząca na trójnogu, odurzone oparami ze szczeliny w ziemi dziewczyna, wychowywana od urodzenia w świątyni. W narkotycznym widzie odpowiadała ona luźnymi słowami, które później kapłani interpretowali jako przepowiednie. Wpływały one na wszystko, od polityki do zwykłych i codziennych spraw a jako, że specjalnie wiary w takie przepowiednie nie pokładam sądzę, że były one raczej losowe. W tym też charakterze będziemy wykorzystywać wyrocznię w naszym dowodzie.

Dowód ten może Wam przypominać dowody nie wprost z lekcji matematyki jednak na razie musimy postawić parę założeń:

1.  (od Oracle) jest to wyrocznia, która wciela się w rolę strony weryfikującej tożsamość, zakładamy, że potrafi odróżnić wymagane przez protokół wartości od liczb zupełnie losowych,
2.  (od Adversary) – nasz oponent, który poddaje się identyfikacji, zakładamy, że nie zna klucza prywatnego jednak ma strategię na prawidłową identyfikację.
3. Potrafimy dokonać transkrypcji wszystkich zapisów protokołu.

Od czego zaczynamy dowód? Spójrzcie na rysunek poniżej:

Przedstawia on zapis dwóch przejść protokołu. Liczby ,  służą inicjacji protokołu (nazywamy te wiadomości commitment’ami, zobowiązaniem względem weryfikatora), ,  są wyzwaniami (challenge) rzuconymi przez wyrocznię, ,  są to dowody posiadania znajomości klucza prywatnego a ,  odpowiedzi wyroczni. Warto przypomnieć, że Adwersarz nie zna klucza prywatnego jednak potrafi wyciągnąć z kapelusza (albo mówiąc bardziej technicznie wylosować lub wygenerować) liczby, które umożliwią mu identyfikację przed wyrocznią. Przypuśćmy, że nasz oponent potrafi dokonać transkrypcji wszystkich przebiegów protokołu (oznaczymy tą liczbę literą ). Spójrzmy na ten zapis transkrypcji:

                                                                                         …

Jeśli  jest dostatecznie duże (lub skrajnie – jako  zostaną wykorzystane wszystkie opcje) z pewnym prawdopodobieństwem powtórzy się któryś z wcześniej wykorzystanych commitment’ów (liczb ). Dla ułatwienia załóżmy, że  powtórzy się jako  i wyrocznia przekaże nowe wyzwanie  a adwersarz wykorzysta swoje moce by wygenerować nową wartość . Jakie są tego konsekwencje?

Jeśli liczby  i  były wcześniej wygenerowane z wykorzystaniem strategii Adwersarza i

wiemy, że

Wtedy adwersarz może obliczyć klucz prywatny z wykorzystaniem następującej formuły , gdyż zarówno wartości , , ,  są mu doskonale znane.

Czego to dowodzi? Protokół byłby możliwy do złamania, gdyby istniał adwersarz z nieskończoną pamięcią i czasem żeby przeszukać dostatecznie dużą część przestrzeni oraz potrafiący wylosować liczby zgodne z protokołem… Czego prawdopodobieństwo jest pomijalnie małe.

Czy Was ten dowód przekonuje? Mnie osobiście nie do końca… Przyjmujemy mało realne założenia, żeby dojść do oczywistych wniosków – w czasie studiów nazywałem tego typu dowody dowodami przez machanie rękami albo dowodami przez niemalże założenie tezy 😉. Przytaczam go przede wszystkim z poczucia kronikarskiego obowiązku .

Powrót do świata matematyki

O ile sam protokół działa to jest też niestety jest jeden drobny szkopuł. Matematycy lubią nieskończoność ale informatycy nie radzą sobie z nią najlepiej. O ile wyobraźnia potrafi wytrzymać nieskończenie wielką liczbę tak komputery nie mają pamięci by je przechowywać. Spójrzcie na zakresy poszczególnych typów całkowitoliczbowych w języku Rust na 64-bitowym procesorze Intel’a:

Nazwa typu	Dolny zakres	Górny zakres
u8	0	255
u16	0	65535
u32	0	4294967295
u64	0	18446744073709551615
i8	-128	127
i16	-32768	65535
i32	-2147483648	2147483647
i64	-9223372036854775808	9223372036854775807

Liczby typu u64 wydają się duże ale biorąc pod uwagę poziom bezpieczeństwa i fakt, że intensywnie wykorzystujemy potęgowanie potrafię sobie wyobrazić, że będzie to wartość zbyt mała i przekroczymy zakres wartości… Czy potrafimy sobie z tym poradzić?

Odpowiedź jest na szczęście pozytywna 😊 Naszym głównym problemem jest fakt, że mnożenie w pewnym momencie może nas wyprowadzić poza zbiór osiągalnych wartości. Powinniśmy skonstruować sobie operację matematyczną, która będzie zamknięta w sensownym zbiorze wartości. Na pomoc tutaj przychodzi nam algebra abstrakcyjna i teoria struktur algebraicznych. Zanim jednak o tym, przez chwilę poopowiadam Wam o liczbach pierwszych, które będą dla nas w pewnym momencie istotne.

Liczby pierwsze

Mam nadzieję, że się nie obrazicie za drobne przypomnienie, że liczby pierwsze  są to liczby naturalne, które dzielą się tylko i wyłącznie przez 1 oraz samą siebie. Tak na marginesie jest nawet jeden dowcip z brodą jak u Albusa Dumbledora jak różni naukowcy sprawdzają czy liczby nieparzyste są pierwsze.

Studenci z różnych wydziałów dostali zadanie: udowodnij, że wszystkie liczby nieparzyste większe od 1 są pierwsze.
– Matematyk: Dla 3 – zgadza się. A dalej jakoś to pójdzie przez indukcję…
– Inżynier: Dla 3 – zgadza się, dla 5 – zgadza się, dla 7 – zgadza się…
– Chemik: Dla 3 – zgadza się, dla 5 – zgadza się, dla 7 – zgadza się, dla 9 – zgadza się…
– Fizyk: Dla 3 – zgadza się, dla 5 – zgadza się, dla 7 – zgadza się, 9 to błąd pomiarowy, dla 11 – zgadza się, dla 13 – zgadza się…
– Astronom: Dla 639547 – zgadza się, dla 979949 – zgadza się…
– Informatyk: Dla 3 – zgadza się, dla 3 – zgadza się, dla 3…

Na potrzeby protokołu będziemy potrzebowali wygenerować odpowiednio długie (tj. w zapisie wykorzystującym system dwójkowy) liczby pierwsze. Aby to zrobić możemy spróbować wykonać następujące działania:

• Wygenerować wszystkie liczby pierwsze z wykorzystaniem sita Eratostenesa, dopóki nie osiągniemy większego zbioru liczb  z których możemy losować – rozwiązanie kiepskie bo wymaga za równo masę pamięci jak i czasu…
• Wylosować ciąg bajtów i sprawdzić czy liczba jest podzielna przez wszystkie liczby mniejsze od niej – rozwiązanie niewiele lepsze, ale wciąż czasochłonne.

Możemy pójść o krok dalej, że nie ma sensu sprawdzać wszystkich dzielników liczby a zatrzymać się na jej pierwiastku jednak przy dużych liczbach wciąż nie jest to oczekiwane, efektywne rozwiązanie problemu.

Rozwiązanie, które jest faktycznie wykorzystywane bazuje na losowości i statystyce nazywane testem Millera-Rabina. Poniżej znajduje się opis algorytmu:

Algorytm ten będzie częścią implementacji protokołu Schnorr’a, do której link znajdziecie na końcu artykułu a teraz możemy wrócić do tematu struktur algebraicznych.

Podstawowa struktura algebraiczna – grupa

Strukturą algebraiczną nazywamy zbiór oraz działania na nim określone, które spełniają pewne konkretne własności. Warto wspomnieć, że pomysł C++’owych szablonów, gdzie funkcja do działania potrzebuje aby argumenty spełniały jedynie wąsko określone wymagania formalne. Dobrze, ale przejdźmy do rzeczy i zajmijmy się najbardziej podstawową strukturą, która wkrótce będzie dla nas istotna.

Pierwszą i najważniejszą strukturę odkrył Evariste Galois w 1832 roku jest to grupa. Definiujemy ją jako parę , gdzie  jest to zbiór na którym określone jest dowolne działanie binarne (tzn. dwuargumentowe, podobnie jak dodawanie czy mnożenie). Poniżej przedstawiona jest lista własności, które musi spełniać działanie na grupie:

• Łączność: ,
• Identyczność (albo istnienie elementu neutralnego :  lub  ,
• Istnienie elementu przeciwnego :  .

W zależności czy używamy notacji addytywnej (bazującej na dodawaniu) używamy zapisu
(i nazywamy elementem przeciwnym) a w przypadku multiplikatywnej (bazującej na dodawaniu) używamy zapisu  (i nazywamy elementem odwrotnym). Co oznacza, zamkniętość działania
w grupie? Dla dowolnych dwóch elementów zbioru  wynik działania  również należy do zbioru .

Jeśli dodatkowo działanie to jest przemienne to taką grupę nazywamy abelową.

Jakie znamy przykłady grup?

•  – addytywna grupa liczb całkowitych, elementy są liczbami całkowitymi a operacją dodawanie,
•  – multiplikatywna grupa niezerowych reszt modulo 7, elementami są liczby od 1 do 6 a działaniem mnożenie modulo 7. Poniżej znajduje się tabela pokazująca „tabliczkę mnożenia”

	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

•  – addytywna grupa liczb całkowitych modulo 6, elementami są liczby od 0 do 5 a działaniem dodawanie modulo 6. Można skonstruować podobną tabelkę do tej z poprzedniego przykładu, najprościej porównać dodawanie w tej grupie do liczenia godzin na zegarku 😊

Dlaczego  – zbiór liczb całkowitych z mnożeniem nie jest grupą? Nie ma ani jednej liczby całkowitej, której odwrotność względem mnożenia należy również do liczb całkowitych.

Użyteczne dla nas będą jeszcze następujące pojęcia:

1. Rzędem grupy nazywamy moc (inaczej liczbę elementów) zbioru elementów,
2. Rzędem elementu nazywamy najmniejszą potęgę, która da element neutralny.
3. Generatorem grupy nazywamy element, na którym powtarzając cały czas działanie wygenerujemy wszystkie elementy zbioru grupy – żeby wygenerować całą grupę  potrzebujemy dwie wartości .
4. Podgrupą nazywamy podzbiór zbioru  z działaniem, który też jest grupą.

Teraz wrócimy do obliczeń związanych z protokołem Schnorr’a.

Grupa Schnorr’a

Claus Schnorr zaproponował żeby wszystkie obliczenia dotyczące jego protokołu były przeprowadzane w pewnym wyspecyfikowanym matematycznym świecie, który nazywamy grupą Schnorr’a. Grupa ta jest podgrupą (rzędu dużej liczby pierwszej) multiplikatywnej grupy modulo , gdzie  jest liczbą pierwszą.

Żeby wygenerować taką grupę potrzebujemy liczby  takie, że  i  są pierwsze i . Następnie musimy wylosować

,

takie że . Liczba  z definicji musi być różna od 1 gdyż w przeciwnym wypadku  oraz  byłyby dwiema sąsiadującymi liczbami pierwszymi. Liczba  będzie generatorem naszej grupy a zarazem podstawą wszystkich potęg z protokołu. Teraz odpowiemy sobie dlaczego 😊. Warto wspomnieć, że jeśli  jest liczbą pierwszą to grupa multiplikatywna  jest cykliczna.

Po pierwsze, przy wykonywaniu protokołu wykonujemy bardzo wiele mnożeń i potęgowań (które de facto też jest złożeniem mnożeń) w związku z tym musimy mieć gwarancję, że wykonując te działania   pozostaniemy w grupie. Liczba  mówi nam w uproszczeniu o tym jak duże wartości mogą potencjalnie znaleźć się w grupie, podczas gdy liczba  będąc rzędem grupy określa maksymalną liczbę mnożeń, którą potrzebujemy wykonać aby dojść do elementu neutralnego. Dlaczego chcemy wydłużać tą ścieżkę? Żeby obliczenia pozostały w podgrupie dla każdego wykonanego mnożenia nasza podgrupa musi być cykliczna – dłuższy cykl oznacza, większy czas potrzebny na przeszukanie podgrupy wygenerowanej przez generator.

Gdyby  byłoby równe 1 oznaczałoby to, że nie nadaje się na generator gdyż podgrupa byłaby zdegenerowana – zawierałaby tylko jeden element, tj. liczbę 1.

Zakończenie

Kończąc podam Wam ostatnie założenia. Liczba  powinna być od 1024-3072 bitowa podczas gdy  160-256 bitowe. Założenie to jest konieczne aby zabezpieczyć się przed atakiem na problem dyskretnego logarytmu (czyli próbę odzyskania wykładnika potęgi, co jest dla komputera kłopotliwym zadaniem) oraz atakom bazującym na małej podgrupie.

Planuję przygotować dla Was krótki artykuł na temat ataków na matematyczną stronę protokołów w którym omówię wskazane ataki.Na stronie repozytorium (DODAJ LINK) znajdziecie uproszczoną implementację protokołu Schnorr’a – uproszczenie polega na tym, że używam mniejszych liczb niż zalecane 😉 Możecie jednak zobaczyć, że matematyka, którą Wam przed momentem opisałem faktycznie działa!

Pozdrawiam,
Paweł Jarosz