Python koncept - prosta funkcja haszująca

Zrobimy sobie prostą funkcję haszującą. Haszowanie to zamiana tekstu na jakąś wartość liczbową. Wiemy już, że komputer nie przechowuje tak naprawdę liter, tylko odpowiadające im cyfry. Możemy podejrzeć jaka litera jakiej cyfrze odpowiada, używając na literze/znaku funkcji ord:

print(ord("a"))
print(ord("A"))
print(ord("b"))
print(ord("B"))
print(ord("c"))
print(ord("C"))
# 97
# 65
# 98
# 66
# 99
# 67

Jak widać „a” to 97, „A” to 65 i tak dalej. Możemy ten proces odwrócić i za pomocą funkcji chr wygenerować litery z liczb. Jeżeli wiemy, że „a” to liczba 65 zaś alfabet ma 24 litery, możemy to zrobić w pętli:

print(chr(65)) #A
for num in range(65,65+25):
    print(chr(num))
#A
#(...)
#Z

Naszych znaków tu nie ma, ponieważ one są nieco dalej, nie znajdują się w ASCII, z którego te liczby pochodzą.

Tym niemniej, w przypadku ord i chr widzimy, że łatwo możemy znak na liczbę zamienić i odwrotnie, liczbę na znak.

Haszowanie to nieco inny proces. Tutaj chodzi o zamianę po pierwsze całego tekstu do jakiejś wartości liczbowej, a zatem redukcji tekstu do wartości liczbowej. Po drugie, haszowanie ma działać w jedną stronę. Mamy nie być w stanie na podstawie hasza odgadnąć oryginalnego tekstu.

Po co się haszuje? Rzecz pierwsza to słowniki. Zauważyliśmy, że listy są indeksowane cyframi

lst = ["red", "green", "blue"]
print(lst[0])
print(lst[1])

Słowniki też są indeksowane cyframi. To jest, my widzimy napisy:

color = {
    "red" : 255,
    "green" : 255,
    "blue" : 255
}
print(color["red"])
#255

Natomiast gdzieś tam „pod spodem” nasz napis, w tym wypadku red, jest zamieniany na hasz, liczbę i pod tą liczbą jako kluczem znajduje się wartość 255.

Dlatego słowniki czasami nazywa się haszmapami. Oczywiście dobra funkcja haszująca sprawi, że nie będzie kolizji, to jest więcej niż 2 napisy produkujące taki sam hasz. A gdy to się zdarzy – rozwiąże problem w inny sposób.

Inne zastosowanie haszy to hasła w bazie danych. Tworzysz konto, tworzysz hasło, w bazie danych zostaje zapisany hasz tego hasła. Przechodzisz do logowania, wpisujesz hasło, funkcja haszuje wpisane hasło i porównuje z haszem z bazy danych. Gdyby dane z serwisu internetowego wyciekły, ludzie nie poznają haseł tylko jakieś cyferki.

Czy dwa różne hasła mogą dać ten sam hasz? Teoretycznie tak. W praktyce – nie bardzo. Napiszemy sobie dzisiaj bardzo prostą funkcję haszującą, pokazując cały ten mechanizm, natomiast prawdziwe funkcje haszujące są dużo bardziej skomplikowane.

Nasza funkcja – algorytm

W haszowaniu chodzi o to zatem, aby tekst dało się zredukować do wartości liczbowej. I to w taki sposób, aby zawsze ten sam tekst dawał te samą liczbę. A zarazem taki, aby nie było łatwo napisać coś, co nam odcyfruje ten hasz, weźmie liczbę i zamieni na tekst.

Nasz algorytm będzie wyglądał tak:

Zamieniamy napis na listę znaków
Zamieniamy każdy znak na jego wartość liczbową według ASCII, czyli funkcja ord
Dodajemy do siebie te wartości
Dodane wartości dzielimy modulo przez długość listy

Oto przykład:

msg = "hello world"
print(list(msg))
#['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']

Mamy listę znaków. Teraz zamieńmy te znaki na ich wartość liczbową:

msg = "hello world"
print([ord(char) for char in msg])
#[104, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100]

Już lepiej. Teraz dodajmy je do siebie:

msg = "hello world"
print(sum([ord(char) for char in msg]))
#1116

Teraz podzielmy modulo przez długość napisu:

msg = "hello world"
print(sum([ord(char) for char in msg]) % len(msg))
#5

Dziwny ten hasz. Właśnie do mnie dotarło, że chyba dzielić przez długość napisów to powinniśmy każdy jeden element przez długość całego napisu. Oczywiście ta funkcja jest jak najbardziej okej, ale zróbmy to:

msg = "hello world"
print(sum([ord(char) % len(msg) for char in msg]))
#60

I tak – ten napis zawsze nam da liczbę 60. Natomiast zrobienie algorytmu, który nam liczbę 60 zamieni na ten napis powinno być niemożliwe, albo bardzo bardzo trudne.

Zresztą pomyślmy czy nawet znając wszystkie kroki (zamieniamy każdy znak na jego wartość liczbową i dzielimy modulo przez długość tekstu, dodajemy te liczby do siebie) nie rozboli nas głowa, gdy myślimy co zrobić, aby biorąc tę liczbę jakoś ten proces odwrócić? I niby jak, widzimy tylko 60, nie wiemy, jaka jest długość tekstu, tak haszowanego.

Nasza funkcja, haszowanie Pythona

def hash_text(text):
    txtlst = [ord(char) % len(text) for char in text]
    return sum(txtlst)

print(hash_text("hello world"))
print(hash_text("Hello world"))
print(hash_text("abcd"))
print(hash_text("blablabla"))
# 60
# 61
# 6
# 45

Tak wygląda nasza funkcja zapisana. Warunek jest spełniony – dochodzi do redukcji tekstu do liczby, zawsze ten sam tekst daje te samą liczbę, konwersja odwrotna (z liczby do tekstu) powinna być niemożliwa albo bardzo trudna.

Oczywiście istnieje też inny warunek: funkcja powinna być na tyle skomplikowana, aby nie było „kolizji” czyli 2 różne teksty produkujące te same liczby. W tak prostej funkcji do kolizji dochodzić może.

Zobaczmy sobie jak Python haszuje teksty. Użyjmy wbudowanej funkcji hash():

def hash_text(text):
    txtlst = [ord(char) % len(text) for char in text]
    return sum(txtlst)

print(hash_text("hello world"), hash("hello world"))
print(hash_text("Hello world"), hash("Hello world"))
print(hash_text("abcd"), hash("abcd"))
print(hash_text("blablabla"), hash("blablabla"))
# 60 1958460757847330116
# 61 -7258926597081246054
# 6 -1316839970342492034
# 45 8528100172571209949

Jak widać nasza funkcja jest nieco mniej skomplikowana niż funkcja haszowania Pythona, natomiast spełnia te samą funkcję.

Python koncept – prosta funkcja haszująca

Nasza funkcja – algorytm

Nasza funkcja, haszowanie Pythona