Haszowanie w kryptografii

Chcesz dowiedzieć się więcej o haszowaniu w kryptografii? Jeśli tak, to trafiłeś we właściwe miejsce.

W tym artykule dowiemy się więcej o haszowaniu.

Haszowanie to technika informatyczna służąca do identyfikowania obiektów lub wartości z grupy obiektów lub wartości.

Brzmi myląco?

Spróbujmy zrozumieć na przykładzie.

Cóż, uczelnie i szkoły zapewniają unikalny numer każdemu ze swoich uczniów. Ten unikalny numer identyfikuje ucznia i związane z nim informacje. Metodą używaną do generowania unikatowego numeru jest haszowanie.

Innym popularnym przykładem są biblioteki, w których na półkach znajdziesz mnóstwo książek. Każda książka ma swój unikalny numer identyfikacyjny, dzięki czemu może znajdować się w ogromnej bibliotece!

Współczesnym przykładem haszowania mogą być gracze, którzy rejestrują się w grze. Valorant to darmowa gra uruchomiona przez Riot. Bycie free-to-play oznacza, że ​​w tę grę będą grać miliony ludzi.

Każdy gracz jest identyfikowany za pomocą unikalnej wartości identyfikacyjnej wygenerowanej za pomocą algorytmu haszującego.

Spróbujmy to zrozumieć bardziej szczegółowo poniżej.

 

Co to jest haszowanie?

Jak wspomniano powyżej, haszowanie jest metodą identyfikacji obiektu z grupy.


Każdy obiekt po zaszyfrowaniu otrzymuje unikalny numer identyfikacyjny.

Ale co to oznacza technicznie?

Z technicznego punktu widzenia funkcja matematyczna generuje wynik o stałej długości z dowolnego ciągu wejściowego o dowolnej długości.

Transakcje Bitcoin są hashowane, gdzie transakcje uzyskują unikalne identyfikatory.

Jeśli wpiszesz „Hello, World!” w Algorytm mieszający SHA-256, otrzymasz następujące dane wyjściowe:

Wejście: Witaj świecie!

Wynik: dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362182986f

Tutaj SHA256 generuje dane wyjściowe z podanego wejścia. Jak widać, użyliśmy algorytmu mieszającego Secure Hash Function (SHA-256). Jest to jedna z popularnych metod haszowania, w tym Message Direct (MD5) i Secure Hash Function (SHA1).

Kluczowe właściwości funkcji skrótu sprawiają, że jest ona niezawodna. Wymieńmy je poniżej.

  • Deterministyczne → Oznacza to, że wynik będzie taki sam dla danego wejścia w danych okolicznościach.
  • Odporny na przedobraz → Funkcja odporności na przedobraz zapewnia, że ​​wartość skrótu nie jest przydatna do generowania wartości wejściowej.
  • Wydajne obliczeniowo → Funkcje skrótu są wydajne i nie wymagają do wykonania ogromnych zasobów obliczeniowych.
  • Nie można odwrócić inżynierii → Funkcji skrótu nie można odwrócić.
  • Odporny na kolizje → Odporność na kolizję zapewnia, że ​​żadne dwa wejścia nie dają tego samego wyjścia.

Omówiliśmy już tutaj haszowanie kryptograficzne dla początkujących. Sprawdź to: Cryptographic Hashing: A Beginner’s Guide. 

Ale jeśli jesteś tutaj po zaawansowane rzeczy, nie będziesz rozczarowany.

 

Co to jest funkcja skrótu i ​​tabele skrótów? I jak one działają?

W tej sekcji omówimy bardziej szczegółowo funkcję skrótu i ​​tabele skrótów. Jeśli chodzi o haszowanie, istnieją funkcje skrótu. Te funkcje są odpowiedzialne za przekształcanie dużych wejść w małe stałe wejścia. Tabele skrótów przechowują dane wyjściowe.

W procesie haszowania obiekty są dystrybuowane na podstawie ich par klucz / wartość do tablicy. Tak więc, jeśli przekażesz tablicę elementów do funkcji skrótu, otrzymasz tablicę wyjściową, w której każdy z elementów ma teraz dołączony klucz. Para klucz / wartość jest bardzo przydatna, jeśli chodzi o dostęp do elementów w czasie rzeczywistym, ponieważ oferuje imponujący czas O (1).

Aby zaimplementować funkcje skrótu, możesz zdjąć dwa preferowane podejścia.

  • Pierwszym podejściem jest użycie funkcji skrótu do konwersji elementu na liczbę całkowitą. Następnie dane wyjściowe w postaci liczb całkowitych mogą być użyte do uzyskania dostępu do elementu podczas wstawiania do tablicy skrótów.
  • Kolejnym krokiem jest umieszczenie elementu w tablicy haszującej, a następnie pobranie go za pomocą skrótu klucza.

W drugiej metodzie funkcje będą wyglądać następująco:

hash = hash_function (klucz) index = hash% array_size

Tutaj hasz i rozmiary tablicy są od siebie niezależne. Wartość indeksu jest obliczana na podstawie rozmiaru tablicy. Operator modulo (%) umożliwia nam obliczenie wartości.

Mówiąc prościej, funkcję skrótu można zdefiniować jako funkcję, która może mapować zestaw danych o dowolnym rozmiarze do zestawu danych o stałym rozmiarze. Wynikowy zestaw danych o stałym rozmiarze można przechowywać w tabeli skrótów. Wartości zwracane przez funkcję skrótu mają wiele nazw. Można je nazwać wartościami skrótu, skrótami, sumami skrótów i kodami skrótów.

 

Pisanie dobrej funkcji skrótu

Jeśli chcesz stworzyć dobrą funkcję lub mechanizm skrótu, musisz zrozumieć podstawowe wymagania dotyczące jej tworzenia. Wymieńmy je poniżej:

  • Funkcja skrótu musi być łatwa do obliczenia. Oznacza to, że jego wykonanie nie powinno wymagać wielu zasobów.
  • Funkcja skrótu musi być równomiernie rozmieszczona. W ten sposób tabele skrótów są używane do przechowywania wartości skrótów, aby nie doszło do klastrowania.
  • Ostatnim wymaganiem jest mniejsza lub żadna kolizja. Brak kolizji oznacza, że ​​żadne pojedyncze wyjście nie jest mapowane na dwa wejścia.

Technicznie rzecz biorąc, kolizje są częścią funkcji skrótu i ​​po prostu nie można ich usunąć z funkcji skrótu. Celem jest stworzenie funkcji skrótu, która może zapewnić dobrą wydajność tablicy mieszania i rozwiązywać kolizje za pomocą technik rozwiązywania kolizji.

 

Dlaczego potrzebujemy dobrej funkcji skrótu?

Aby zrozumieć potrzebę użytecznej funkcji skrótu, przejdźmy do poniższego przykładu.

Załóżmy, że chcemy utworzyć tablicę haszującą przy użyciu techniki mieszania, w której ciągi wejściowe będą następujące: {„agk”, „kag”, „gak”, „akg”, „kga”, „gka”}

Teraz tworzymy funkcję mieszającą, która po prostu dodaje wartość ASCII a (97), g (103) i k (107), a następnie wykonuje modulo sumy przez 307.

Oczywiście suma tych trzech liczb również wynosi 307. Oznacza to, że jeśli dokonamy permutacji wszystkich liczb, a następnie wykonamy operację modulo, otrzymamy ten sam wynik. Końcowym wynikiem byłoby przechowywanie wszystkich ciągów pod tym samym numerem indeksu. Algorytmiczny czas dla funkcji skrótu byłby również złożonością O (n), co nie jest pożądane. Możemy łatwo stwierdzić, że opisana przez nas funkcja skrótu nie jest optymalna dla rzeczywistych scenariuszy.

Aby naprawić funkcję skrótu, możemy zastosować podzielenie sumy wartości ASCII każdego elementu przez inną liczbę pierwszą, 727. W ten sposób otrzymamy inne dane wyjściowe dla naszej podanej tablicy ciągów wejściowych.

 

Nauka o tabelach skrótów

Tabele skrótów są bardzo przydatne do przechowywania wyniku funkcji skrótu, która oblicza indeks, a następnie przechowuje dla niego wartość. Efektem końcowym byłby szybszy proces obliczeniowy o złożoności O (1).

Tabele haszujące są tradycyjnie dobrym wyborem przy rozwiązywaniu problemów wymagających O (n) czasu.

Tak więc, jeśli weźmiesz ciąg o stałej długości, a następnie spróbujesz nauczyć się częstotliwości znaków w ciągu.

Tak więc, jeśli string = „aacddce”, to ogólne podejście polega na wielokrotnym przejrzeniu ciągu i zapisaniu każdej częstotliwości.

# Podaj ciąg wejściowy i policz częstotliwość znaków w tym ciągu

#Algorytm ma czas złożoności 0 (n)

temp_list = [] start = "za" str = "ababcddefff" def alpha_zeta (): alpha = ‘a’ for i in range (0,26): temp_list.append (alpha) alpha = chr (ord (alpha) + 1) return temp_list temp_list = alpha_zeta () #print (temp_list) def character_frequency (str, temp_list): for each in temp_list: freq = 0 for i in str: if (i == each): freq = freq + 1 print (each, freq) character_frequency (str, temp_list)

Wynik powyższego programu będzie następujący:

a 2 b 2 c 1 d 2 e 1 f 3 g 0 h 0 i 0 .. ..

Teraz zaimplementujmy tablicę skrótów w C ++ i policzmy częstotliwość znaków.

#include using namespace std; int Frequency [26]; int hashFunc (char c) {return (c – ‘a’); } void countFre (string S) {for (int i = 0; i< S.length (); ++ i) {int index = hashFunc (S [i]); Częstotliwość [indeks] ++; } Dla (int i = 0; i<26; ++ i) {cout << (znak) (i + ‘a’) << ” << Częstotliwość [i]<< endl; }} Int main () {cout<<"Witaj świecie"; countFre ("abbaccbdd"); }

Wynik programu wyglądałby następująco:

a 2 b 3 c 2 d 2

Złożoność O (N) algorytmu sprawia, że ​​jest on szybszy w porównaniu z innymi podejściami liniowymi.

Jak rozwiązywać kolizje

Istnieją unikalne sposoby rozwiązywania kolizji w funkcjach skrótu. Jednym z popularnych sposobów jest oddzielne łączenie łańcuchowe, które jest również znane jako otwarte haszowanie. Jest zaimplementowany z połączoną listą, w której każdy element w łańcuchu sam jest połączoną listą. Takie podejście umożliwia przechowywanie elementów i zapewnia, że ​​niektóre elementy są tylko częścią określonej połączonej listy, rozwiązując kolizję. Oznacza to, że żadne dwie wartości wejściowe nie mogą mieć tej samej wyjściowej wartości skrótu.

 

Odkrywanie skrótu w Pythonie

W tej sekcji szybko przyjrzymy się hashowi w Pythonie. Powodem, dla którego wybraliśmy Python, jest to, że jest łatwy do odczytania i może być używany przez każdego bez większych problemów.

Ponieważ haszowanie jest popularną funkcją, jest już zaimplementowane w bibliotece Pythona. Korzystając z modułu, możesz podać obiekt jako jego dane wejściowe, a następnie zwrócić zaszyfrowaną wartość.

Składnia metody skrótu jest następująca:

hash (obiekt)

Jak widać, przyjmuje pojedynczy parametr, którym jest obiekt. Obiekt może być liczbą całkowitą, zmiennoprzecinkową lub łańcuchem.

Zwracana wartość metody hash () zależy od danych wejściowych. W przypadku liczby całkowitej może zwracać tę samą liczbę, podczas gdy dla liczb dziesiętnych i łańcuchowych byłyby różne.

Zobaczmy poniżej kilka przykładów.

num = 10 decy = 1,23556 str1 = "Nitish" print (hash (num)) print (hash (deci)) print (hash (str1))

Wynik powyższego kodu jest następujący:

Jednak haszowania nie można zastosować do wszystkich typów obiektów. Na przykład, jeśli pamiętasz, że stworzyliśmy listę od a do z w naszym pierwszym programie. Jeśli spróbujemy to zaszyfrować, okno wyjściowe przejdzie przez błąd TypeError: unhashable type: „list”

Aby zastosować haszowanie do listy obiektów, musisz użyć krotki.

samogłoski = (‘a’, ‘e’, ​​’i’, ‘o’, ‘u’) print (hash (samogłosek)) Wynik ⇒ -5678652950122127926

Haszowanie w kryptografii

Haszowanie jest przydatne w kryptografii. Bitcoin wykorzystuje haszowanie do tworzenia drzew Merkle i zarządzania nimi

Ponadto haszowanie jest częścią kryptografii od dłuższego czasu. Jednak najlepszym przykładem użycia haszowania jest haszowanie haseł i przechowywanie ich. 

Drzewa Merkle

Drzewo Merkle to struktura danych przydatna przy przeprowadzaniu bezpiecznej weryfikacji danych w dużej puli danych. Zarówno Bitcoin, jak i Ethereum wykorzystują drzewa Merkle do rozwiązywania wielu barier technologicznych podczas przechowywania i uzyskiwania dostępu do danych w otwartej sieci.

Żadna scentralizowana sieć nie musi martwić się o przechowywanie i uzyskiwanie dostępu do danych, ponieważ istnieje tylko jedno źródło dostępu do danych i ich przechowywania. Jednak równanie zmienia się, gdy istnieje zdecentralizowana sieć, ponieważ teraz dane muszą być kopiowane między setkami uczestniczących rówieśników.

Drzewa Merkle rozwiązują ten problem, zapewniając zaufany i skuteczny sposób udostępniania i weryfikowania danych między rówieśnikami.

Przykład drzewa Merkle

Ale dlaczego omawiamy tutaj drzewa Merkle? Drzewa Merkle używają skrótu jako podstawowej funkcji do łączenia różnych węzłów i bloków danych.

Drzewa Merkle to odwrócone drzewo, które może podsumować cały zestaw transakcji.

Jeśli chcesz dowiedzieć się więcej o drzewach Merkle i ich używaniu haszowania w kryptografii, zapoznaj się z naszym szczegółowym przewodnikiem:

Przewodnik po drzewach Merkle. Tam omówiliśmy, w jaki sposób implementacje drzew Merkle są wykonywane w bitcoinach i innych przypadkach użycia.

Proces wydobycia

Proces wydobywania również wykorzystuje haszowanie. Jeśli chodzi o wydobywanie bitcoinów, nowy blok jest dodawany do łańcucha bloków, gdy jest na niego zapotrzebowanie.

Aby dodać blok do łańcucha bloków, należy postępować zgodnie z metodą. Wartość skrótu jest generowana w zależności od zawartości bloku, gdy nadejdzie nowy blok. Ponadto, jeśli wygenerowany hash jest czymś więcej niż trudnością sieci, rozpoczyna się proces dodawania bloku do łańcucha bloków.

Po zakończeniu wszystkie peery w sieci potwierdzają dodanie nowego bloku.

Rzadko się to zdarza, ponieważ w większości przypadków trudność sieci jest zawsze wyższa w porównaniu z wygenerowanym hashem. Jest jeszcze jeden aspekt, który odgrywa kluczową rolę w procesie wydobywczym. To jest nonce.

Nonce jest dodawany do skrótu bloku i jest dowolnym ciągiem. Po zakończeniu połączony ciąg jest porównywany z poziomem trudności. Jeśli poziom trudności jest niższy niż połączony ciąg, wówczas wartość jednorazowa jest zmieniana, aż poziom trudności będzie wyższy.

Proces można podsumować w następujących krokach:

  • Zawartość jest haszowana, aby utworzyć nową wartość skrótu za każdym razem, gdy zostanie wygenerowany lub pobrany nowy blok,
  • Zostanie wygenerowana nowa wartość jednorazowa i dołączona do skrótu
  • Proces haszowania odbywa się na nowo nawiązanym ciągu 
  • Ostateczna wartość skrótu jest następnie porównywana z poziomem trudności sieci
  •  jeśli końcowa wartość skrótu jest mniejsza niż wartość jednorazowa, proces jest powtarzany ponownie. Proces zatrzymuje się tylko wtedy, gdy wartość skrótu jest większa niż liczba jednorazowa.
  • Blok dołącza do łańcucha, gdy poziom trudności jest wyższy
  • Następnie górnicy biorą na siebie odpowiedzialność za wydobycie nowego bloku i podzielenie się nagrodami między sobą.

Stąd też pochodzi termin „szybkość mieszania”. Szybkość mieszania to szybkość, z jaką odbywają się operacje mieszania. Wyższy wskaźnik mieszania oznacza, że ​​górnicy potrzebowaliby większej mocy obliczeniowej, aby uczestniczyć w procesie wydobywania.

 

Wniosek

To prowadzi nas do końca naszego szczegółowego przewodnika po kryptografii. Omówiliśmy szczegółowo haszowanie, a także zbadaliśmy kod, który za nim stoi.

Więc co o tym myślisz? Skomentuj poniżej i daj nam znać.

 

#FAQ

Co kryptografii kryptografii?

W kryptografii haszowanie to metoda konwersji danych na unikalny ciąg tekstu przy użyciu wydajnej metody. Nie ma też ograniczeń co do typu danych ani ich rozmiaru – haszowanie działa na wszystkich z nich.

W jaki sposób haszowanie jest używane w kryptografii?

Kryptografia wykorzystuje haszowanie do haszowania haseł lub generowania unikalnych numerów identyfikacyjnych.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me
Like this post? Please share to your friends:
Adblock
detector
map