ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη
Wersja PL ENG Version

Salsa20

  • Ogólny opis
  • Algorytm
  • Schematy blokowe
  • Funkcje matematyczne
  • Implementacja
Salsa20 jest nowoczesnym i wydajnym strumieniowym szyfrem symetrycznym. Został on zaprojektowany w 2005 roku przez Daniela Bernstein'a, profesora informatyki na Uniwersytecie Illinois w Chicago.
Szyfr strumieniowy z kluczem symetrycznym
Długość klucza = 32 bajty
Szyfr Salsa20 został zgłoszony do projektu eSTREAM, mającego miejsce w latach 2004 to 2008, który miał na celu spopularyzowanie szyfrów strumieniowych i doprowadził do opublikowania kilku nowych szyfrów strumieniowych przyzwoitej jakości. Salsa20 jest uważany za dobrze zaprojektowany i efektywny algorytm. Nie są znane żadne skuteczne ataki na szyfry z rodziny Salsa20.

Salsa20 jest szyfrem strumieniowym, który operuje na blokach danych o wielkości 64 bajtów.

Szyfrowanie

Dla każdego 64-bajtowego bloku danych, algorytm wywołuje funkcję rozszerzającą Salsa20. Danymi wejściowymi do funkcji są: sekretny klucz (który może mieć 32 lub 16 bajtów) oraz 8-bajtowy nonce, połączony dodatkowo z numerem aktualnie szyfrowanego bloku. Wartości numerów bloków zmieniają się od 0 do 264-1 (jest więc zapisany na 8 bajtach). Każde wywołanie funkcji rozszerzającej zwiększa wartość numeru bloku o jeden.

Rdzeniem algorytmu Salsa20 jest funkcja haszująca, która otrzymuje 64 bajty z funkcji rozszerzającej, następnie miesza je, a na koniec zwraca inne 64 bajty danych, z powrotem do funkcji rozszerzającej. Funkcja haszująca jako dane wejściowe przyjmuje ciąg bajtów, na który składają się:

Funkcja haszująca operuje na danych podzielonych na słowa (słowa maszynowe, ang. words). Każde słowo składa się z 4 bajtów i może zawierać liczbę z przedziału od 0 do 232-1. Wynika z tego, że blok danych wejściowych ma 16 słów długości, sekretny klucz zawiera 8 lub 4 słowa, natomiast nonce ma 2 słowa.

Wyjście z funkcji rozszerzającej szyfru Salsa20 jest dodawane XOR do 64-bajtowego bloku danych. Wynikiem tego działania jest 64-bajtowy blok zaszyfrowanego tekstu.

Deszyfrowanie

W celu odszyfrowania otrzymanego szyfrogramu, należy wykorzystać ten sam algorytm. Dane powinny zostać podzielone w ten sam sposób.

Wyjście z funkcji rozszerzającej szyfru Salsa20 jest powinno być dodane XOR do 64-bajtowego bloku zaszyfrowanego tekstu. Wynikiem tego sumowania jest 64-bajtowy blok tekstu jawnego.

Inne szyfry oparte na Salsa20

Istnieje kilka odmian szyfru Salsa20. Bazują one na tym samym algorytmie, ale różnią się pewnymi detalami w implementacji:

Operacje wykonywane w ramach algorytmu szyfrującego Salsa20 zostały przedstawione od funkcji najniższego poziomu, do zbudowanych z nich funkcji wyższego poziomu.

Suma dwóch słów
Dodawanie dwóch 4-bajtowych słów jest przedstawione w opisie algorytmu jako a + b. Wynik dodawania jest dzielony modulo przez 232 (czyli przez maksymalną wartość słowa 4-bajtowego).

Suma dwóch słów ab jest równa a+b mod 232. Wynik ma 4 bajty długości.

XOR dwóch słów
Operacja XOR na dwóch 4-bajtowych słowach jest przedstawiona w opisie algorytmu jako a XOR b.

Aby dodać XOR dwa 4-bajtowe słowa, należy obie liczby porównać bit po bicie i dla każdej takiej pary bitów wykonać działanie XOR. Otrzymany wynik ma również 4 bajty długości.

Rotacja bitów w lewo
Rotacja w lewo o a bitów 4-bajtowego słowa w jest przedstawiona w opisie algorytmu jako w <<< a.
Podczas rotacji, a najbardziej skrajnych lewych bitów przechodzi na prawą stronę słowa.

Rotacja bitów w lewo w <<< a 4-bajtowego słowa w może być przedstawiona jako operacja mnożenia:
2a·w mod(232-1)
Otrzymany wynik jest poprawnym słowem, o długości 4 bajtów.

Funkcja Ćwiartki Rundy (ang. Quarterround Function)
Funkcja Ćwiartki Rundy pobiera 4 słowa danych wejściowych. Zwracany ciąg ma również długość 4 słów.

Jeżeli x jest wejściem do funkcji o długości 4 słów:
    x = (x0, x1, x2, x3)
to Funkcja Ćwiartki Rundy może być zdefiniowana następująco:
    quarterround(x) = (y0, y1, y2, y3)
gdzie:
    y1 = x1 XOR ((x0 + x3) <<< 7)
    y2 = x2 XOR ((y1 + x0) <<< 9)
    y3 = x3 XOR ((y2 + y1) <<< 13)
    y0 = x0 XOR ((y3 + y2) <<< 18)

Funkcja Ćwiartki Rundy może wykonywać się w miejscu, to znaczy bez potrzeby przydzielania dodatkowej pamięci. Najpierw x1 zamienia się na y1, potem x2 przekształca się w y2, następnie x3 przekształca się w y3, a na końcu x0 zamienia się na y0. Funkcja Ćwiartki Rundy jest odwracalna, ponieważ wszystkie powyższe operacje są odwracalne.

Funkcja Rundy Wierszy (ang. Rowround Function)
Funkcja Rundy Wierszy pobiera 16 słów wejściowych, przekształca je i zwraca ciąg o długości również 16 słów.

Funkcja ta jest bardzo podobna do Funkcji Rundy Kolumn, ale operuje na słowach w innej kolejności.

Jeżeli x jest 16-bajtowym ciągiem przekazanym do funkcji:
    x = (x0, x1, x2, ..., x15)
to Funkcja Rundy Wierszy może być zdefiniowana następująco:
    rowround(x) = (y0, y1, y2, ..., y15)
gdzie:
    (y0, y1, y2, y3) = quarterround(x0, x1, x2, x3)
    (y5, y6, y7, y4) = quarterround(x5, x6, x7, x4)
    (y10, y11, y8, y9) = quarterround(x10, x11, x8, x9)
    (y15, y12, y13, y14) = quarterround(x15, x12, x13, x14)


Dane wejściowe do funkcji składające się z 16 słów mogą być przedstawione za pomocą macierzy:

x0x1x2x3
x4x5x6x7
x8x9x10x11
x12x13x14x15

Wiersze w macierzy są modyfikowane równocześnie. Każdy z nich jest przetwarzany za pomocą Funkcji Ćwiartki Rundy.

Słowa w pierwszym wierszu są zmieniane w następującej kolejności:

  1. x1
  2. x2
  3. x3
  4. x0

Słowa w drugim wierszu są zmieniane w następującej kolejności:

  1. x6
  2. x7
  3. x4
  4. x5

W trzecim wierszu, słowa zmieniane w kolejności:

  1. x11
  2. x8
  3. x9
  4. x10

W ostatnim, czwartym wierszu, słowa są zmieniane w kolejności:

  1. x12
  2. x13
  3. x14
  4. x15
Funkcja Rundy Kolumn (ang. Columnround Function)
Funkcja Rundy Kolumn pobiera 16 słów wejściowych i zwraca ciąg o długości również 16 słów.

Jeżeli x jest wejściem do funkcji o długości 16 słów:
    x = (x0, x1, x2, ..., x15)
to funkcja rundy kolumn może być zdefiniowana następująco:
    columnround(x) = (y0, y1, y2, ..., y15)
gdzie:
    (y0, y4, y8, y12) = quarterround(x0, x4, x8, x12)
    (y5, y9, y13, y1) = quarterround(x5, x9, x13, x1)
    (y10, y14, y2, y6) = quarterround(x10, x14, x2, x6)
    (y15, y3, y7, y11) = quarterround(x15, x3, x7, x11)


Dane wejściowe składające się z 16 słów mogą być przedstawione za pomocą macierzy:

x0x1x2x3
x4x5x6x7
x8x9x10x11
x12x13x14x15

Kolumny w macierzy mogą być przekształcane równocześnie. Każda z nich jest modyfikowana za pomocą Funkcji Ćwiartki Rundy.

W pierwszej kolumnie, słowa są zmieniane w następującej kolejności:

  1. x4
  2. x8
  3. x12
  4. x0

W drugiej kolumnie, słowa są zmieniane w kolejności:

  1. x9
  2. x13
  3. x1
  4. x5

W trzeciej kolumnie, słowa są zmieniane w następującej kolejności:

  1. x14
  2. x2
  3. x6
  4. x10

W ostatniej, czwartej kolumnie, słowa są zmieniane w kolejności:

  1. x3
  2. x7
  3. x11
  4. x15
Funkcja Podwójnej Rundy (ang. Doubleround Function)
Funkcja Podwójnej Rundy pobiera 16 słów wejściowych, przekształca je, a na koniec zwraca ciąg o długości również 16 słów.

Jeżeli x jest wejściem do funkcji o długości 16 słów, to Funkcja Podwójnej Rundy może być zdefiniowana następująco:
    doubleround(x) = rowround(columnround(x))

Funkcja Zmiany Porządku Bajtów (ang. Littleendian Function)
Otrzymane 4 bajty są zwracane w odwrotnej kolejności.

Jeśli b jest ciągiem 4 bajtów:
    b = (b0, b1, b2, b3)
to przekształcenie może być zdefiniowane następująco:
    littleendian(b) = b0 + 28b1 + 216b2 + 224b3

Zamiana ta jest odwracalna. Powtórne użycie tej funkcji na otrzymanych danych powoduje powrót do stanu pierwotnego.

Funkcja Haszująca Salsa20
Funkcja Haszująca Salsa20 pobiera 64 bajty wejściowe i zwraca również ciąg o długości 64 bajtów.

Najpierw, Funkcja Haszująca tworzy 16 słów bazując na otrzymanych 64 bajtach wejściowych. Jażeli input jest ciągiem 64 bajtów:
    input =(b0, b1, b2, ..., b63)
to 16 słów jest tworzonych następująco:
    w0 = littleendian(b0, b1, b2, b3)
    w1 = littleendian(b4, b5, b6, b7)
    [...]
    w15 = littleendian(b60, b61, b62, b63)

Następnie, wszystkie 16 słów jest modyfikowanych w trakcie 10 iteracji Funkcji Podwójnej Rundy:
    (x0, x1, ..., x15) = doubleround10(w0, w1, ..., w15)

Na końcu, otrzymane na wejściu 16 słów jest dodawanych (tak jak to opisano powyżej) do 16 zmodyfikowanych słów i zamienianych na 64 bajty przy użyciu Funkcji Zmiany Porządku Bajtów. Otrzymane w wyniku 64 bajty są wyjściem (output) z Funkcji Haszującej Salsa20:
    output = littleendian-1(x0+w0) + littleendian-1(x1+w1) + ... + littleendian-1(x15+w15)

Funkcja Rozszerzająca Salsa20
Funkcja Rozszerzająca Salsa20 pobiera dwa ciągi bajtów. Pierwszy ciąg może mieć 16 lub 32 bajty. Drugi ciąg ma 16 bajtów długości. Funkcja zwraca ciąg o długości 64 bajtów.

Jeżeli pierwszy ciąg ma długość 32 bajtów, to jest on dzielony na dwa ciągi o długości 16 bajtów każdy (k0k1). Funkcja Rozszerzająca Salsa20 jest wtedy definiowana za pomocą Funkcji Haszującej Salsa20 w następujący sposób:
    Salsa20Expansionk0, k1(n) = Salsa20Hash(a0, k0, a1, n, a2, k1, a3)
gdzie:
    a0 = (101, 120, 112, 97)
    a1 = (110, 100, 32, 51)
    a2 = (50, 45, 98, 121)
    a3 = (116, 101, 32, 107)

Jeżeli pierwszy ciąg ma długość 16 bajtów (k), to wtedy Funkcja Rozszerzająca Salsa20 jest definiowana za pomocą Funkcji Haszującej Salsa20 w sposób przedstawiony poniżej:
    Salsa20Expansionk(n) = Salsa20Hash(b0, k, b1, n, b2, k, b3)
gdzie:
    b0 = (101, 120, 112, 97)
    b1 = (110, 100, 32, 49)
    b2 = (54, 45, 98, 121)
    b3 = (116, 101, 32, 107)

Wartości wektora (a0, a1, a2, a3) oznaczają "expand 32-byte k", zapisane w kodzie ASCII. Wartości wektora (b0, b1, b2, b3) oznacza "expand 16-byte k" w kodzie ASCII.

Strona w trakcie budowy.