Polega na znalezieniu wyst\u0105pie\u0144 okre\u015blonego wzorca w danym tek\u015bcie. Przyk\u0142adowe algorytmy:<\/p>\n\n\n\n
- \n
- Metoda naiwna<\/strong>: Przesuwa wzorzec wzd\u0142u\u017c tekstu i por\u00f3wnuje go z ka\u017cdym fragmentem.<\/li>\n\n\n\n
- Algorytm Knutha-Morrisa-Pratta (KMP)<\/strong>: U\u017cywa prefiks\u00f3w wzorca do optymalizacji wyszukiwania.<\/li>\n\n\n\n
- Algorytm Boyera-Moore\u2019a<\/strong>: Por\u00f3wnuje wzorzec od ko\u0144ca i efektywnie pomija niepasuj\u0105ce fragmenty.<\/li>\n<\/ul>\n\n\n\n
2. Szyfrowanie tekst\u00f3w<\/strong><\/h5>\n\n\n\n
Stosowane w celu ochrony informacji poprzez przekszta\u0142canie tekstu w form\u0119 niezrozumia\u0142\u0105 dla os\u00f3b niepowo\u0142anych. Rodzaje:<\/p>\n\n\n\n
- \n
- Szyfrowanie podstawieniowe<\/strong>: Ka\u017cda litera jest zamieniana na inn\u0105, np. szyfr Cezara.<\/li>\n\n\n\n
- Szyfrowanie przestawieniowe<\/strong>: Zmienia kolejno\u015b\u0107 liter w tek\u015bcie, tworz\u0105c anagramy.<\/li>\n\n\n\n
- Szyfrowanie symetryczne<\/strong>: Jeden klucz s\u0142u\u017cy do szyfrowania i deszyfrowania (np. AES).<\/li>\n\n\n\n
- Szyfrowanie asymetryczne<\/strong>: U\u017cywa pary kluczy (publicznego i prywatnego), np. algorytm RSA.<\/li>\n<\/ul>\n\n\n\n
3. Analiza tekst\u00f3w<\/strong><\/h5>\n\n\n\n
Obejmuje algorytmy przetwarzania j\u0119zyka naturalnego, wyszukiwania informacji i kompresji danych tekstowych.<\/p>\n\n\n\n
Algorytmy na tekstach maj\u0105 kluczowe znaczenie w aplikacjach takich jak wyszukiwarki, systemy szyfrowania danych, edytory tekstowe oraz systemy wykrywania plagiat\u00f3w.<\/p>\n\n\n\n
<\/p>\n\n\n\n
1. Wyszukiwanie wzorca w tek\u015bcie metod\u0105 naiwn\u0105<\/strong><\/h3>\n\n\n\n
Metoda naiwna jest jednym z najprostszych sposob\u00f3w wyszukiwania wzorca w tek\u015bcie. Polega na przesuwaniu wzorca wzd\u0142u\u017c tekstu i por\u00f3wnywaniu go z kolejnymi fragmentami.<\/p>\n\n\n\n
Opis algorytmu:<\/strong><\/h4>\n\n\n\n
- \n
- Przesu\u0144 wzorzec o jedn\u0105 pozycj\u0119 wzd\u0142u\u017c tekstu, zaczynaj\u0105c od pocz\u0105tku.<\/li>\n\n\n\n
- Na ka\u017cdym etapie por\u00f3wnaj wzorzec z odpowiadaj\u0105cym mu fragmentem tekstu.<\/li>\n\n\n\n
- Je\u015bli wzorzec pasuje do fragmentu, zapisz pozycj\u0119 dopasowania.<\/li>\n\n\n\n
- Powtarzaj a\u017c do ko\u0144ca tekstu.<\/li>\n<\/ol>\n\n\n\n
Przyk\u0142ad:<\/strong><\/h4>\n\n\n\n
- \n
- Tekst: “abcabcabc”<\/li>\n\n\n\n
- Wzorzec: “abc”<\/li>\n\n\n\n
- Wynik: Dopasowania na pozycjach 0, 3, 6.<\/li>\n<\/ul>\n\n\n\n
![\"\"](\"http:\/\/maciux.pl\/wp-content\/uploads\/2024\/11\/image.png\")
<\/figure>\n\n\n\nZalety i wady:<\/strong><\/h4>\n\n\n\n
- \n
- Zalety:<\/strong> Prosty do implementacji.<\/li>\n\n\n\n
- Wady:<\/strong> Wolny przy d\u0142ugich tekstach i wzorcach.<\/li>\n<\/ul>\n\n\n\n
\n\n\n\n2. Szyfrowanie tekstu metod\u0105 podstawieniow\u0105<\/strong><\/h3>\n\n\n\n
W jakim celu stosujemy szyfry?<\/strong><\/h4>\n\n\n\n
Szyfrowanie jest kluczowym elementem ochrony danych w cyfrowym \u015bwiecie. Jego g\u0142\u00f3wnym celem jest zapewnienie:<\/p>\n\n\n\n
- \n
- Poufno\u015bci:<\/strong> Dane s\u0105 dost\u0119pne tylko dla uprawnionych u\u017cytkownik\u00f3w.<\/li>\n\n\n\n
- Integralno\u015bci:<\/strong> Dane nie zosta\u0142y zmienione w trakcie przesy\u0142ania.<\/li>\n\n\n\n
- Autentyczno\u015bci:<\/strong> Odbiorca mo\u017ce potwierdzi\u0107 to\u017csamo\u015b\u0107 nadawcy.<\/li>\n<\/ul>\n\n\n\n
Podstawowe poj\u0119cia dotycz\u0105ce szyfrowania:<\/strong><\/h4>\n\n\n\n
- \n
- Tekst jawny (ang. plaintext):<\/strong> Dane przed szyfrowaniem.<\/li>\n\n\n\n
- Tekst zaszyfrowany (ang. ciphertext):<\/strong> Dane po zaszyfrowaniu.<\/li>\n\n\n\n
- Klucz:<\/strong> Sekretna informacja u\u017cywana do szyfrowania i deszyfrowania.<\/li>\n\n\n\n
- Algorytm szyfrowania:<\/strong> Zestaw regu\u0142 matematycznych u\u017cywanych do przekszta\u0142cania danych.<\/li>\n<\/ul>\n\n\n\n
![\"\"](\"http:\/\/maciux.pl\/wp-content\/uploads\/2024\/11\/image-1.png\")
<\/figure>\n\n\n\n
\n\n\n\nSzyfr Cezara<\/strong><\/h4>\n\n\n\n
Jest to jeden z najprostszych szyfr\u00f3w podstawieniowych. Jego dzia\u0142anie polega na przesuni\u0119ciu ka\u017cdej litery w alfabecie o okre\u015blon\u0105 liczb\u0119 miejsc.<\/p>\n\n\n\n
Schemat dzia\u0142ania:<\/strong><\/p>\n\n\n\n
- \n
- Przypisz ka\u017cdej literze jej numer w alfabecie (A=0, B=1, …, Z=25).<\/li>\n\n\n\n
- Zaszyfruj ka\u017cd\u0105 liter\u0119, przesuwaj\u0105c j\u0105 o okre\u015blony klucz kkk:
Zaszyfrowana litera = (Pozycja+k) mod\u2009\u200926 \\ text {Zaszyfrowana litera} = (\\text{Pozycja} + k) \\mod 26 Zaszyfrowana litera = (Pozycja+k) mod26.<\/li>\n\n\n\n - Odzyskaj tekst jawny, stosuj\u0105c przesuni\u0119cie wstecz.<\/li>\n<\/ol>\n\n\n\n
Przyk\u0142ad:<\/strong><\/p>\n\n\n\n
- \n
- Tekst jawny:
HELLO<\/code><\/li>\n\n\n\n- Klucz: 3<\/li>\n\n\n\n
- Tekst zaszyfrowany:
KHOOR<\/code><\/li>\n<\/ul>\n\n\n\n![\"\"](\"http:\/\/maciux.pl\/wp-content\/uploads\/2024\/11\/image-2.png\")
<\/figure>\n\n\n\nAnaliza bezpiecze\u0144stwa:<\/strong><\/h4>\n\n\n\n
- \n
- \u0141atwo go z\u0142ama\u0107, stosuj\u0105c brutaln\u0105 si\u0142\u0119 (sprawdzenie 25 przesuni\u0119\u0107).<\/li>\n\n\n\n
- Wsp\u00f3\u0142cze\u015bnie u\u017cywany jedynie w celach dydaktycznych.<\/li>\n<\/ul>\n\n\n\n
\n\n\n\n3. Szyfrowanie tekstu metod\u0105 przestawieniow\u0105<\/strong><\/h3>\n\n\n\n
W szyfrowaniu przestawieniowym kolejno\u015b\u0107 znak\u00f3w w tek\u015bcie jest zmieniana zgodnie z okre\u015blonym kluczem.<\/p>\n\n\n\n
Miniszyfrowanie \u2013 tworzenie anagram\u00f3w<\/strong><\/h4>\n\n\n\n
Jednym z przyk\u0142ad\u00f3w szyfrowania przestawieniowego jest zamiana kolejno\u015bci liter w s\u0142owach w spos\u00f3b losowy, np. z
KOT<\/code> naTOK<\/code>. Takie podej\u015bcie jest stosunkowo \u0142atwe do z\u0142amania, ale mo\u017ce by\u0107 u\u017cywane w prostych grach i zabawach j\u0119zykowych.<\/p>\n\n\n\n
\n\n\n\nSzyfrowanie symetryczne i asymetryczne<\/strong><\/h4>\n\n\n\n
- \n
- Symetryczne:<\/strong>
W tym typie szyfrowania ten sam klucz jest u\u017cywany do szyfrowania i deszyfrowania danych. Przyk\u0142ady: DES, AES.
Zalety:<\/strong> Szybko\u015b\u0107 dzia\u0142ania.
Wady:<\/strong> Problem z bezpiecznym przekazywaniem klucza.<\/li>\n\n\n\n- Asymetryczne:<\/strong>
Opiera si\u0119 na dw\u00f3ch kluczach \u2013 publicznym i prywatnym. Publiczny s\u0142u\u017cy do szyfrowania, a prywatny do deszyfrowania. Przyk\u0142ady: RSA, ElGamal.
Zalety:<\/strong> Brak konieczno\u015bci wymiany klucza prywatnego.
Wady:<\/strong> Wi\u0119ksze zapotrzebowanie na zasoby obliczeniowe.<\/li>\n<\/ol>\n\n\n\n
\n\n\n\nAlgorytm RSA<\/strong><\/h4>\n\n\n\n
RSA to jeden z najbardziej znanych algorytm\u00f3w szyfrowania asymetrycznego. Jego bezpiecze\u0144stwo opiera si\u0119 na trudno\u015bci faktoryzacji du\u017cych liczb.<\/p>\n\n\n\n
Proces szyfrowania:<\/strong><\/p>\n\n\n\n
- \n
- Wygeneruj dwie liczby pierwsze ppp i qqq.<\/li>\n\n\n\n
- Oblicz n=p\u22c5qn = p \\cdot qn=p\u22c5q oraz \u03d5(n)=(p\u22121)(q\u22121)\\phi(n) = (p-1)(q-1)\u03d5(n)=(p\u22121)(q\u22121).<\/li>\n\n\n\n
- Wybierz liczb\u0119 eee, tak\u0105 \u017ce gcd\u2061(e,\u03d5(n))=1\\gcd(e, \\phi(n)) = 1gcd(e,\u03d5(n))=1.<\/li>\n\n\n\n
- Oblicz klucz prywatny ddd, taki \u017ce e\u22c5d\u22611(mod\u03d5(n))e \\cdot d \\equiv 1 \\pmod{\\phi(n)}e\u22c5d\u22611(mod\u03d5(n)).<\/li>\n\n\n\n
- Szyfruj wiadomo\u015b\u0107 MMM: C=Memod\u2009\u2009nC = M^e \\mod nC=Memodn.<\/li>\n\n\n\n
- Deszyfruj wiadomo\u015b\u0107 CCC: M=Cdmod\u2009\u2009nM = C^d \\mod nM=Cdmodn.<\/li>\n<\/ol>\n\n\n\n
RSA jest szeroko stosowany w protoko\u0142ach bezpiecze\u0144stwa takich jak HTTPS.<\/p>\n","protected":false},"excerpt":{"rendered":"
Algorytmy na tekstach to zestaw technik i metod przetwarzania danych tekstowych, kt\u00f3re maj\u0105 szerokie zastosowanie w informatyce, lingwistyce komputerowej i kryptografii. Oto kluczowe obszary zastosowania i algorytm\u00f3w: 1. Wyszukiwanie wzorc\u00f3w w tek\u015bcie Polega na znalezieniu wyst\u0105pie\u0144 okre\u015blonego wzorca w danym tek\u015bcie. Przyk\u0142adowe algorytmy: 2. Szyfrowanie tekst\u00f3w Stosowane w celu ochrony informacji poprzez przekszta\u0142canie tekstu w … <\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-772","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/pages\/772","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/comments?post=772"}],"version-history":[{"count":10,"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/pages\/772\/revisions"}],"predecessor-version":[{"id":821,"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/pages\/772\/revisions\/821"}],"wp:attachment":[{"href":"https:\/\/maciux.pl\/index.php\/wp-json\/wp\/v2\/media?parent=772"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- Asymetryczne:<\/strong>
- Symetryczne:<\/strong>
- Tekst jawny:
- Tekst zaszyfrowany (ang. ciphertext):<\/strong> Dane po zaszyfrowaniu.<\/li>\n\n\n\n
- Integralno\u015bci:<\/strong> Dane nie zosta\u0142y zmienione w trakcie przesy\u0142ania.<\/li>\n\n\n\n
- Wady:<\/strong> Wolny przy d\u0142ugich tekstach i wzorcach.<\/li>\n<\/ul>\n\n\n\n
- Zalety:<\/strong> Prosty do implementacji.<\/li>\n\n\n\n
- Szyfrowanie przestawieniowe<\/strong>: Zmienia kolejno\u015b\u0107 liter w tek\u015bcie, tworz\u0105c anagramy.<\/li>\n\n\n\n
- Algorytm Knutha-Morrisa-Pratta (KMP)<\/strong>: U\u017cywa prefiks\u00f3w wzorca do optymalizacji wyszukiwania.<\/li>\n\n\n\n