Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Tłumaczył: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

1986

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Węzły lotnicze

W ostatnich latach główne linie lotnicze zaadoptowały strukturę tras opartą o "dystrybucję centralną", aby zapewnić bardziej ekonomiczne planowanie lotów. Jako węzeł centralny wybierane jest miasto centralne; poranne loty dostarczają pasażerów ze wszystkich innych miast do węzła centralnego, a popołudniowe loty zabierają pasażerów z tego węzła do wszystkich pozostałych miast. Ten problem prosi cię o wspomożenie Bogus Airlanes w wyborze ich węzła centralnego.

Bogus Airlines (BA) ma zamiar obsługiwać do 30 miast. Zna następującą informację na temat planowania lotu: Czas przelotu pomiędzy dwoma miastami jest równy odległości pomiędzy nimi podzielonej przez 500 mph (mil na godzinę) plus 30 minut. W każdym locie należy uwzględnić 30 minut postoju na ziemi przed startem i 30 minut postoju na ziemi po lądowaniu. Dlatego, na przykład, 1000 milowy lot musi zostać zaplanowany jako lot trwający trzy i pół godziny (1000/500 + 0,5 + 0,5 + 0,5). Musi upłynąć co najmniej jedna godzina  w węźle pomiędzy stykającymi się lotami. Jednakże nie ma potrzeby doliczania jednej godziny pomiędzy porannym lotem z określonego miasta a lotem popołudniowym  z powrotem do tego samego miasta; zakładamy, iż żaden pasażer nie wziąłby tych dwóch lotów. Żaden lot nie może się rozpocząć przed 8:00 rano, ani zakończyć po 10:00 wieczorem. Wybór jakiegoś miasta na węzeł zawsze pozwoli dowolnemu pasażerowi na podróż z dowolnego miasta do węzła, a następnie do dowolnego innego miasta w ciągu jednego dnia (tj. pomiędzy 8:00 a 22:00). Możesz również założyć, że lotnisko jest w stanie obsłużyć dowolną liczbę jednoczesnych przylotów i odlotów.

Na potrzeby tego problemu wolno ci swobodnie interpretować słowa "rano" i "popołudniu". Na przykład "popołudniowy" lot może być zaplanowany przed południem lub po 6:00 popołudniu pod warunkiem spełnienia pozostałych warunków lotu przedstawionych wyżej.

Otrzymasz pięć zestawów danych w pojedynczym pliku. Dla prostoty miejsca będą podane jako współrzędna na płaszczyźnie (nie będzie potrzebna geometria sferyczna). Wysokość i szerokość geograficzna będą wyrażone jako liczby całkowite z zakresu od 0 do 9999, a jednostką miary jest mila. Odległości pomiędzy miastami można policzyć za pomocą normalnej funkcji odległości euklidesowej. Pierwszy wiersz każdego zestawu danych składa się z dwucyfrowej liczby na dwóch pierwszych pozycjach znakowych wiersza; jest to liczba miast. Reszta zestawu danych składa się z wierszy, z których każdy opisuje jedno miasto. Pierwsze osiem znaków wiersza zawiera nazwę miasta (tylko duże litery, cyfry i spacje, wyrównanie lewostronne). Bezpośrednio za tą nazwą znajdują się dwa pięcioznakowe pola, które przechowują odpowiednio wysokość i szerokość geograficzną miasta ; wartości te są wyrównanymi prawostronnie liczbami całkowitymi. Każdy kolejny zestaw danych następuje tuż za swoim poprzednikiem.

Dla każdego zestawu danych twój program powinien zidentyfikować każde miasto, które mogłoby być węzłem, co oznacza, że pozwalałoby ono na zaplanowanie lotów wg opisu podanego powyżej. Następnie twój program musi zidentyfikować miasto, które byłoby najlepszym węzłem centralnym. Takie miasto musiałoby pozwalać na najkrótszy czas całkowity od pierwszego lotu rano (o 8:00) do końca ostatniego lotu popołudniowego (oczywiście z uwzględnieniem czasów postoju na ziemi opisanych powyżej). Jeśli więcej niż jedno miasto jest równie dobre, zidentyfikuj je wszystkie. Twój program musi również wydrukować liczbę możliwych węzłów oraz liczbę najlepszych węzłów dla każdego zestawu danych. Przykładowe dane wejściowe i odpowiadające im dane wyjściowe powinny pomóc ci zrozumieć, co masz zrobić.

Przykładowe dane wejściowe

06
CITY 1    200  400
CITY 2    100  300
CITY 3    100  200
CITY 4    200  100
CITY 5    300  200
CITY 6    300  300

Odpowiadające im dane wyjściowe

6 POSSIBLE HUB(S) MAY BE AT
CITY 1
CITY 2
CITY 3
CITY 4
CITY 5
CITY 6

4 BEST HUB(S) AT
CITY 2
CITY 3
CITY 5
CITY 6
Na początek:  podrozdziału   strony 

Problem B - Zapytania bazodanowe

W wielu środowiskach pożądany jest dla niezaawansowanych użytkowników dostęp do informacji w bazie danych poprzez zapytania w języku naturalnym. Dla tego problemu zaimplementujesz zarówno małą bazę danych jak i interpreter języka zapytań.

Baza danych będzie opisywała, kto oraz jakie przedmioty znajdują się w każdym z pokojów pewnego domu. Każda osoba, obiekt i pokój posiadają nazwy zbudowane z pojedynczych słów zapisanych dużymi literami, o długości maksymalnie dziesięciu znaków. W domu znajduje się dokładnie osiem pokoi, a każdy pokój zawiera dokładnie jedną osobę i jeden obiekt. Baza danych będzie opisana w pierwszych ośmiu wierszach danych. Każdy z tych wierszy zawiera nazwę pokoju wyrównaną lewostronnie w pierwszych dziesięciu znakach wiersza, nazwisko osoby wyrównane lewostronnie w następnych dziesięciu znakach oraz nazwę obiektu również wyrównana lewostronnie w następnych dziesięciu znakach. Na przykład:

LIVINGROOMSMITH     PIANO     
BATHROOM  JONES     TOOTHBRUSH

Język zapytań zezwala tylko na cztery rodzaje pytań:

WHO IS IN THE <pokój>?
WHAT IS IN THE <pokój>?
WHERE IS <osoba>?
WHERE IS THE <obiekt>?

Pytania będą wyrażane dużymi literami, po jednym w wierszu. Twój program musi odczytać pytanie, wydrukować jeden pusty wiersz, wydrukować to pytanie w następnym wierszu, a następnie w kolejnym wierszu wydrukować jedno słowo odpowiedzi lub wiadomość o błędzie. Jeśli pytanie zostało ułożone nieprawidłowo, to wydrukuj wiadomość ERRONEOUS QUESTION. Jeśli poprawnie ułożone pytanie odwołuje się do pokoju, osoby lub obiektu nieobecnych w bazie danych, wydrukuj wiadomość UNKNOWN.

Odpowiedzi pojawiają się w osobnym wierszu zaraz pod pytaniem. Pytania rozpoczną się od dziewiątego wiersza wejściowego, po ośmiu wierszach bazy danych. W pytaniach słowa będą rozdzielone przynajmniej jedną spacją, a spacje mogą wystąpić przed pierwszym słowem lub przed pytajnikiem. Słowa pytań nie będą posiadały więcej niż dziesięć liter. Pytajnik musi być obecny; inaczej pytanie jest błędne. Znaki występujące po pytajniku powinny zostać zignorowane i nie mają być drukowane razem z pytaniem. Liczba wierszy pytań będzie dowolna. Wiersze będą zakończone znacznikiem końca pliku.

Na przykład, dla bazy danych zawierającej wartości z dwóch wierszy podanych powyżej:

WHERE IS JONES?
BATHROOM

   WHAT   IS   IN   THE   LIVINGROOM   ?
PIANO

WHAT IS IN THE VARDAGSRUM?
UNKNOWN

WHO ATE MY WOMBAT?
ERRONEOUS QUESTION
Na początek:  podrozdziału   strony 

Problem C - Pobieranie wiadomości

Każdej nocy Midnight Message Service nagrywa wiadomości dla swoich klientów w pojedynczym pliku tekstowym. Pierwszy wiersz tego pliku zawiera (w pierwszych 25 znakach) datę otrzymania pliku wiadomości. Reszta pliku zawiera wiadomości w kolejności ich otrzymywania. Każda wiadomość zawarta jest w dwóch wierszach. Pierwszy wiersz zawiera numer konta klienta, do którego wiadomość była wysłana. Drugi wiersz zawiera wiadomość do tego klienta. Żadna wiadomość nie jest dłuższa niż 72 znaki, a numer konta jest całkowitą liczbą dodatnią mniejszą od 32767. W pliku znajduje się co najwyżej 200 wiadomości.

Napisz program, który tworzy raport zawierający wszystkie wiadomości w tym pliku. Raport będzie się składał z nagłówka, za którym wystąpi ciąg raportów klientów pojawiających się w kolejności rosnącej wg numeru konta. Nagłówek i pierwszy raport klienta będą rozdzielone dwoma pustymi wierszami; raporty klientów będą rozdzielone jednym pustym wierszem. Nagłówek będzie się składał z wiersza pokazanego poniżej, w którym <date> zostanie zastąpione datą otrzymania wiadomości.

Midnight Message Service -- messages received on <date>

Raporty klienta będą składały się z wierszy jeden pod drugim. Pierwszy wiersz każdego raportu klienta będzie zawierał numer konta klienta. Pozostałe wiersze będą wymieniać wiadomości klienta, po jednej na wiersz, w kolejności otrzymywania.

Na początek:  podrozdziału   strony 

Problem D - Szyfr Lobid

Twój  pracodawca, Lobid Inc., pragnie zaproponować system szyfrowania i rozszyfrowywania. przy pomocy którego można kodować tekst wiadomości w postaci ciągu liczb całkowitych. Tekst jest najpierw dzielony na 15-literowe bloki, z których każdy zostaje następnie zaszyfrowany jako ciąg pięciu liczb całkowitych. (Jeśli długość wiadomości nie jest wielokrotnością piętnastu, to na końcu zostają dodane spacje.) Tylko 32 znaki pojawiające się w poniższym przykładzie można używać w wiadomości.

Wiadomość 'ABCDEFGHIJKLMNOPQRSTUVWXYZ .,()-' jest zaszyfrowana jako 0,  255,  3855,  13107,  -10923,  -1,  127,  1927,   6553,  10922,  -8193,  -8193,  -16384,  -8193,  -8193.

Procedura szyfrowania jest zilustrowana poniżej:

blok 1 -->  A B C D E F G H I J K L M N O
    bit 1   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  daje 0
    bit 2   0 0 0 0 0 0 0 1 1 1 1 1 1 1 1  daje 255
    bit 3   0 0 0 1 1 1 1 0 0 0 0 1 1 1 1  daje 3855
    bit 4   0 1 1 0 0 1 1 0 0 1 1 0 0 1 1  daje 13107
    bit 5   1 0 1 0 1 0 1 0 1 0 1 0 1 0 1  daje -10923

blok 1  --> P Q R S T U V W X Y Z   . , (
    bit 1   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -1
    bit 2   0 0 0 0 0 0 0 0 1 1 1 1 1 1 1  daje 127
    bit 3   0 0 0 0 1 1 1 1 0 0 0 0 1 1 1  daje 1927
    bit 4   0 0 1 1 0 0 1 1 0 0 1 1 0 0 1  daje 6553
    bit 5   0 1 0 1 0 1 0 1 0 1 0 1 0 1 0  daje 10922

blok 3 -->  ) -
    bit 1   1 0 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -8193
    bit 2   1 0 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -8193
    bit 3   1 0 0 0 0 0 0 0 0 0 0 0 0 0 0  daje -16384
    bit 4   1 0 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -8193
    bit 5   1 0 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -8193

Z podanego przykładu można wywnioskować, że każdy znak jest reprezentowany przez unikalny kod 5-bitowy. Co więcej, pierwsza z pięciu liczb całkowitych reprezentujących blok pochodzi z interpretacji pierwszych bitów każdego znaku w bloku jako 15-bitowej liczby całkowitej U2. 15 drugich bitów łączone jest w podobny sposób, aby utworzyć drugą liczbę całkowitą, itd.

Plik danych dla twojego programu jest w dwóch częściach. Pierwsza część jest ciągiem jednego lub więcej wierszy, każdy po 16 znaków w pierwszych 16 kolumnach. Dla każdego wiersza zapisz ciąg pięciu liczb całkowitych generowanych przez szyfrowanie pierwszych 15 znaków. Zapisuj te liczby kodu we właściwej kolejności w pojedynczym wierszu wyjściowym.  Jeśli szesnasty znak jest znakiem plus ("+"), to ma być zaszyfrowany następny wiersz, inaczej faza szyfrowania kończy się.

Reszta pliku składa się z zera lub więcej wierszy, każdy zawierający pięć liczb całkowitych pochodzących z kodowania bloku tekstu wiadomości. Liczby te są wyrównane prawostronnie w pięciu kolejnych polach siedmioznakowych. Możesz założyć, że pomiędzy sąsiadującymi liczbami jest co najmniej jedna spacja. Dla każdego z tych wierszy zapisz rozszyfrowany blok tekstu w pojedynczym wierszu.

Na początek:  podrozdziału   strony 

Problem E - Generator obrazków

Nowopowstała firma, Pseudo-Art, Inc., zatrudniła cię jako zdolnego programistę do utworzenia programu, który będzie generował obrazki na drukarce ASCII zawierające osadzoną wiadomość. Na wejściu program będzie pobierał jakąś wiadomość i opis obrazka i będzie tworzył złożony obrazek dla klienta.

Wygenerowane obrazki mają być zbudowane ze znaków zawartych w wiadomości klienta i wyświetlone w matrycy o formacie 24 wiersze na 64 kolumny. Wiadomość może posiadać maksymalnie 32 znaki długości bez spacji i ma być wstawiona cyklicznie do matrycy wiersz po wierszu aż do wypełnienia całego obszaru. Opis obrazka składa się z listy liczb oznaczających liczbę pozycji wyliczanych wiersz po wierszu, które mają zostać na przemian maskowane spacjami lub drukowane jako znaki wiadomości wewnątrz matrycy. Pierwsza liczba w pliku oznacza, że pole to ma zostać wydrukowane jako znaki wiadomości.

Specyfikacja wejścia:

Pojedynczy zestaw danych zawarty w pliku jest zorganizowany następująco:

Rekord nr Zawartość
1 Wiadomość do osadzenia w obrazku (długość do 32 znaków)
2 - n Liczby całkowite, po 10 na wiersz, wyrównane prawostronnie w polach 5-cio znakowych, które oznaczają rozmiar pola do wypełnienia na przemian znakami wiadomości lub spacjami. Ostatnią wartością jest 0  oznaczające koniec danych.

Specyfikacja wyjścia:

Twój program powinien utworzyć obrazek w matrycy złożonej ze znaków wiadomości i spacji określonych przez plik wejściowy i zapisać wynikową matrycę w pliku. Znaki w tej matrycy mają być zapisane do tego pliku w 24 wierszach po 64 kolumn każdy.

Przykład:

Przykładowy zestaw danych:

BILBO.BAGGINS.FOR.PRESIDENT
    4   56    8   56    4   76   35   29   35   29
   35   45    6   58    6   58    6   58    6   58
    6   58    6   58    6   52   18   46   18   46
   18  244    6   58    6   30    4   24    6   26
    8   56    8   56    4    0

Wyjście wygenerowane przez powyższe dane:

BILB                                                        BAGG
INS.                                                        R.PR
                                                                
            OR.PRESIDENTBILBO.BAGGINS.FOR.PRESI                 
            NTBILBO.BAGGINS.FOR.PRESIDENTBILBO.                 
            GGINS.FOR.PRESIDENTBILBO.BAGGINS.FO                 
                            AGGINS                              
                            BILBO.                              
                            INS.FO                              
                            ESIDEN                              
                            BO.BAG                              
                      BILBO.BAGGINS.FOR.                        
                      INS.FOR.PRESIDENTB                        
                                                                
                                                                
                                                                
                            LBO.BA                              
                            S.FOR.                              
SIDE                        IDENTB                          BILB
O.BA                                                        INS.
FOR.                                                        ESID
                                                                
                                                               
                                                                
Na początek:  podrozdziału   strony 

Problem F - Metryka stylu programowania

W próbie wspomożenia zautomatyzowania procesu zapewniania jakości dla tworzonego oprogramowania naukowcy starają się znaleźć metrykę lub odpowiednie pomiary określające to, co jest dobre lub złe w programach. Zaproponowano kilka metryk stylu programowania. Ten problem dotyczy najprostszych z tych metryk.

Twój program powinien odczytać jako dane kod źródłowy programu w języku Pascal, a następnie zliczyć następujące rzeczy:

  1. Całkowitą liczbę wierszy w programie.
  2. Liczbę pustych wierszy w programie.
  3. Całkowitą liczbę znaków w programie.
  4. Liczbę znaków w komentarzach łącznie ze znakami ograniczającymi komentarze.
  5. Liczbę znaków białych (spacje) w programie, pomijając znaki białe w komentarzach lub w literałach łańcuchowych.
  6. Liczbę pozostałych znaków w programie (bez znaków białych i z pominięciem komentarzy).

Twój program powinien wyświetlić każde z tych zliczeń z odpowiednim opisem.

Poniższa informacja może okazać się pomocna przy odświeżaniu twojej pamięci na temat struktury programów pascalowych. Program posiada swobodny format i wiersze mogą być dowolnie długie lub krótkie. Komentarz rozpoczyna się znakiem {, a kończy znakiem }. Wszystkie znaki pomiędzy tymi dwoma ogranicznikami są częścią komentarza, jak również same ograniczniki. Dla celów tego programu nie pojawią się komentarze zagnieżdżone. Literał łańcuchowy rozpoczyna się i kończy znakiem apostrofu ( ' ). Dwa sąsiednie apostrofy wewnątrz literału są interpretowane jako pojedynczy apostrof,  a nie ogranicznik kończący. Jednakże dla celów zliczania, licz dwa sąsiednie apostrofy jako dwa znaki. Klamry ( { lub } ) wewnątrz literału łańcuchowego nie są ogranicznikami komentarza, jak również apostrof wewnątrz komentarza nie jest ogranicznikiem literału łańcuchowego.

Zestawem danych dla tego problemu jest poprawny program pascalowy. Może być on dowolnie długi, a kończy się znacznikiem końca pliku. Żaden wiersz w zestawie danych nie posiada spacji końcowych. Jeśli wybierzesz rozwiązanie tego problemu, które wstawia spacje końcowe, to musisz je również usunąć. Żaden wiersz w zestawie danych nie przekracza 80 znaków. Nie powinny być w żaden sposób  zliczane znaki kontrolne, jak CR (ang. carriage return), LF (ang. line feed) lub NL (ang. new line). W zestawie danych nie będzie znaków tabulacji. Żadne poprawne zliczenie nie przekroczy maksymalnej wartości liczb całkowitych.

Przykładowe wejście:

program test ( input, output );

  { this is a data set
  }
var
    num  : integer;
    word : packed array [ 1..15 ] of char;
begin
  word := '.:.            ';  { this is a comment }
  for num := 1 to 5 do
      writeln ( 'Number is:', num * 4 : 3 );
  word := '{not a comment}';
end.  { end test }

Odpowiadające mu wyjście:

Total lines               13
Blank lines                1
Total characters         288
Blank characters          60
Comment characters        56
Other characters         172
Na początek:  podrozdziału   strony 

Problem G - Planowanie tras kolejowych

Koleje Binary and Octal (B&O) zdecydowały, że będą dążyć do osiągnięcia większej efektywności na swoich trasach przewozu towarów, aby móc konkurować na wymagającym rynku transportu kolejowego. B&O jest małym towarzystwem kolejowym z centralną stacją i z 10 stacjami rozstawionymi wzdłuż swoich linii. Każda z tych stacji jest bezpośrednio połączona z każdą z pozostałych, a B&O wie o planowym transporcie towarów do każdej stacji co najmniej na jeden dzień naprzód.

Każdego dnia ze stacji centralnej B&O wyrusza specjalny transport z zaplanowanym ładunkiem samochodów, które mają być dostarczone do swoich zaplanowanych miejsc przeznaczenia. Każdego dnia może być do 100 samochodów dostarczanych do każdego z miejsc przeznaczenia od stacji centralnej i dostawa może iść do każdej ze stacji. Stacja centralna nie jest miejscem przeznaczenia żadnego samochodu.

Problem, o którego rozwiązanie poprosił cię zarząd B&O, dotyczy zaplanowania dziennych dostaw o minimalnym koszcie trasy dla codziennego pociągu. Minimalny koszt trasy jest zdefiniowany jako suma przebytych mil pomnożona przez liczbę przewożonych samochodów.  Ponieważ liczba samochodów dla każdego z miejsc przeznaczenia oraz liczba miejsc przeznaczenia różni się każdego dnia, konieczne będzie przeliczanie minimalnego kosztu trasy codziennie.

Specyfikacja wejścia:

W pliku znajduje się pojedynczy zestaw danych zorganizowany następująco:

Rekord nr Zawartość
1 Liczba miejsc przeznaczenia (N) dla dzisiejszych dostaw.
2 1 do N liczb całkowitych wyrównanych prawostronnie w 5-znakowych polach, reprezentujących liczbę samochodów do dostarczenia do każdego miejsca przeznaczenia.
3
:
:
3 + N
Liczby całkowite wyrównane prawostronnie w 5-znakowych polach, reprezentujące  odległości pomiędzy stacjami dla dzisiejszego kursu. Odległości są przedstawione jako górna macierz trójkątna zawierająca tylko niezbędne odległości. Na przykład jako pierwszy rekord z N = 3 pojawiają się wartości 1 2 3. Wartości te reprezentują odległości od stacji 0 do 1, od 0 do 2 i od 0 do 3 (stacja 0 jest stacją centralną, a stacjami odbiorczymi są stacje 1 - N)

Specyfikacja wyjścia:

Twój program ma określić trasę o minimalnym koszcie dla codziennego pociągu B&O oraz zapisać do pliku ten koszt minimalny oraz trasę do przebycia. Dokładny format dla twojego wyjścia jest pokazany na przykładowym wyjściu.

Przykład:

Przykładowy zestaw danych:

4
   70   50   16   21
    4    5    6    1
    4    4    5
    1    2
    3

Wyjście generowane przez powyższe dane:

Minimal cost is 795 car/miles.

Stop 1 is Station 4
Stop 2 is Station 2
Stop 3 is Station 3
Stop 4 is Station 1
Na początek:  podrozdziału   strony 

Problem H - Rozszyfrowywanie szyfru RSA

Ostatnio odnowiła się obawa o bezpieczeństwo informacji przetwarzanej przez komputery i transmisji tej informacji pomiędzy ośrodkami komputerowymi. Gdy wymagana jest poufność, informację koduje się zwykle przy pomocy jakiegoś szyfru, co czyni ją nieczytelną dla wszystkich z wyjątkiem zamierzonego odbiorcy. Problemem większości schematów szyfrowania jest to, iż "klucz" do rozszyfrowania informacji jest znany zarówno nadawcy jak i odbiorcy. To rodzi problem bezpiecznego sposobu przesyłania "klucza". Jednym systemem unikającym tej trudności  jest system szyfrowania kluczem publicznym RSA, który opiera się na używaniu pewnej funkcji matematycznej z "pułapką" oraz trudności związanej z rozkładem dużych liczb na ich czynniki pierwsze.

System RSA jest systemem z dwoma kluczami. Klucz publiczny jest znany wszystkim użytkownikom. Następnie każdy indywidualny użytkownik otrzymuje klucz prywatny. Aby wysłać wiadomość, jest ona kodowana przy użyciu klucza publicznego należącego do zamierzonego odbiorcy i przesyłana do niego. Ten z kolei stosuje proces rozszyfrowywania wiadomości używając obu swoich kluczy, publicznego i prywatnego. Główną cechą systemu RSA jest to, iż rozszyfrowanie wiadomości przy użyciu tego samego klucza, którym została ona zaszyfrowana, nie daje oryginalnej wiadomości. W procesie rozszyfrowywania musi być użyty również klucz prywatny.

Masz opracować program implementujący ograniczoną wersję procesu rozszyfrowywania RSA. Stosowane klucze będą zbyt małe, aby zapewnić rozsądną integralność danych, lecz ta metoda jest poprawna.

Plik danych wejściowych jest plikiem tekstowym składającym się z listy zestawów danych, po jednym zestawie na każdy wiersz oryginalnej wiadomości. Każdy zestaw danych jest ciągiem wartości bezznakowych liczb całkowitych, po jednej na wiersz i wyrównanej prawostronnie w pierwszych pięciu kolumnach kolejnych wierszy wejściowych. Pierwsza wartość dla wszystkich zestawów danych z wyjątkiem ostatniego zawiera liczbę wartości w zestawie danych, łącznie z sobą samą. Ostatni zestaw danych składa się tylko z jednego wiersza, zawierającego wartość 0. Dla każdego zestawu danych liczby występujące po pierwszej są zaszyfrowanymi blokami do rozszyfrowania wg opisu podanego poniżej.

Rozszyfrowywanie zaszyfrowanego bloku jest procesem dwustopniowym. Najpierw zaszyfrowany blok, EB, jest dekodowany w blok zakodowany dziesiętnie, DEB, za pomocą przekształcenia,

DEB = ( EB ** DK ) mod EK  ,

gdzie DK jest prywatnym kluczem rozszyfrowania, EK jest kluczem publicznym szyfrowania, a "**" oznacza potęgowanie. Następnie nieujemna liczba dziesiętna DEB jest dekodowana w dwa znaki oryginalnej wiadomości. Kodem ASCII pierwszego znaku jest 31 plus liczba całkowita z zakresu od 0 do 99, której cyfry na pozycji dziesiątek i jedności są odpowiednio cyframi DEB na pozycji tysięcy i setek. Kod ASCII drugiego znaku jest równy 31 plus liczba całkowita z zakresu od 0 do 99, której cyfry na pozycji dziesiątek i jedności są cyframi DEB odpowiednio na pozycjach dziesiątek i jedności. Na przykład, używając prywatnego klucza rozszyfrującego 26787 i publicznego klucza szyfrującego 40753, zaszyfrowany blok 30239 daje dziesiętnie kodowany blok 4734, który następnie jest dekodowany w "NA", ponieważ kod ASCII litery N jest równy 31+47=78, a kod ASCII litery A jest równy 31+34=65.

W celu policzenia DEB=(EB**DK) mod EK bez przekraczania zakresu obliczeniowego komputera można użyć zmodyfikowanej wersji algorytmu "ruskich chłopów":

  1. Niech DEB będzie równe 1.
  2. Jeśli DK jest nieparzyste, to zmień DEB na (DEB * EB) mod EK.
  3. Zmień EB na (EB * EB) mod EK.
  4. Zmień DK na część całkowitą z (DK podzielone przez dwa).
  5. Jeśli DK jest równe zero, zakończ. Inaczej powtarzaj od kroku 2.

Masz rozszyfrować, złożyć ponownie w całość i wydrukować każdą wiadomość zakodowaną przy pomocy kluczy wspomnianych w tym przykładzie. Zachowaj strukturę wiersza oryginalnej wiadomości. Załóż, iż żaden rozszyfrowany wiersz nie jest dłuższy od 80 znaków.

WSKAZÓWKA: Zauważ, iż DEB jest zawsze mniejsze niż EK. Przy wyborze swojej reprezentacji danych weź pod uwagę to oraz operacje arytmetyczne wymagane w algorytmie podanym powyżej.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.