BLOWFISH

Autor:       Bruce Schneier
Typ:          blokowy, 64-bitowy blok
Klucz:       symetryczny, 448 bitów


        Algorytm Blowfish operuje na 64-bitowym bloku wejściowym tekstu jawnego, który przetwarzamy w 16-tu rundach. Maksymalna długość klucza to 448 bitów. Szyfrowanie przebiega w następujący sposób:
a) Inicjujemy S-bloki i skrzynkę P kluczy pomocniczych ze względu na główny klucz użytkownika.
S-bloków jako skrzynek podstawień mamy w Blowfish cztery, gdzie każda z nich posiada 256 elementów, z kolei każdy element jest wartością 32-bitową. W przypadku kluczy pomocniczy P mamy jedną skrzynkę z 18-ma elementami, również wartość każdego elementu to 32 bity.
S-bloki:     S0[0..255], S1[0..255], S2[0..255], S3[0..255]
P:           P[0..17]
b) dzielimy 64 bity tekstu jawnego "m" na xL (starsze 32 bity) i xR (młodsze 32 bity),
c) wykonujemy operację sumy modulo 2 (xor) pierwszego klucza pomocniczego P1 z xL,
d) wynik z punktu "c" poddajemy operacjom wynikającym w funkcji "F",
e) wykonujemy operacje sumy modulo 2 wyniku z punktu "d" z xR,
f) zamieniamy miejscami xL i xR,
g) wracamy do punktu "c" wykonując xor z kolejnym kluczem pomocniczym Pi. Wykonujemy łącznie 16 iteracji licznika "i", tyle ile rund jest wymaganych w algorytmie Bruce Schneiera. Po 16-tym cyklu przechodzimy do następnego punktu kończąc działanie algorytmu,
( UWAGA!    Po 16-tym cyklu nie zamieniamy miejscami xL i xR !!! Nie wykonujemy punktu "f" ),
h) wykonujemy xor xR z P17 jako 17-tym kluczem pomocniczym i xor-ujemy xL z P18,
i) łączymy xL i xR ze sobą w 64-ro bitowy blok otrzymując tym samym szyfrogram "c".





Rys. 1.  Schemat ogólny algorytmu Blowfish z 16-ma rundami.


        Funkcja "F" wykonuje proste operacje arytmetyczne: suma modulo 2 oraz operacja dodawania modulo 232. Wejściem dla naszej funkcji jest 32-bitowa wartość. Zostaje ona rozłożona na cztery 8-bitowe wartości będące indeksami dla poszczególnych S-bloków. W algorytmie wykorzystujemy 4 S-bloki, każdy blok posiada 256 elementów. Poniższy schemat funkcji "F" rozwieje wszelkie wątpliwości.



Rys. 2.  Schemat funkcji F.

PRZED  SZYFROWANIEM  INICJUJEMY  BLOWFISH


        Wróćmy jeszcze do samego początku, a mianowicie do punktu, w którym inicjujemy bloki S i P. Wydawać by się mogło, że wszystko jest już jasne, a jednak poświęcimy inicjowaniu dłuższą chwilę.
Bruce Schneier przyjął pewne wartości pierwotne zarówno dla S-bloków jak i kluczy pomocniczych P. Wartości te modyfikujemy w zależności od przyjętego klucza użytkownika. Tak więc wykonujemy następujące kroki:
a) Dla wszystkich 18-tu 32-bitowych indeksów skrzynki P, podstawiamy:

                    P[i] := P[i] xor KEY32,     dla    0 <= i <= 17

gdzie KEY32 to kolejne 32 bity klucza licząc od początku. Jeśli użytkownik nie podał pełnego 448-bitowego klucza, natomiast klucz jest ciągiem np. "abcd", budujemy klucz równoważny składający się z ciągu "abcdabcdabcd....abcd" dopełniając do 448 bitów. Jednak jeśli klucz użytkownika jest równy dokładnie 448 bitów, dopełniamy ostatnie 4 podklucze (P14, P15, P16, P17), wracając do pierwszych 32-bitów klucza użytkownika. Poniżej przedstawiam algorytm generowania podkluczy Blowfish.

Algorytm generowania kluczy pomocniczych P.
1.    Len = Length(KEY)
2.    k = 0
3.    for i = 0 to 17 do
4.        A32 = KEY[(k + 3) modulo Len)
5.        A32 = A32 + (KEY[(k + 2) modulo Len] shl 8)
6.        A32 = A32 + (KEY[(k + 1) modulo Len] shl 16)
7.        A32 = A32 + (KEY[k] shl 24)
8.        P[i] = P[i] xor A32
9.        k = (k + 4) modulo Len

( shl -
przesunięcie bitowe w lewo )

b) Następnym krokiem jest szyfrowanie zerowego 64-bitowego bloku algorytmem Blowfish przy pomocy wygenerowanych podkluczy z punktu (a). Proces szyfrowania wykonujemy 9 razy, tak aby zmodyfikować każdy klucz pomocniczy P. Algorytm wykonujący tą czynność poniżej.

Algorytm generowania kluczy pomocniczych P. Cz. 2.
1.    Dane = 0              // 64-ro bitowy blok w celu zaszyfrowania
2.    for i = 0 to 8 do
3.        Szyfrogram = BlowfishEncrypt(Dane)
4.        P[i * 2] = Szyfrogram(xL)
5.        P[i * 2 + 1] = Szyfrogram(xR)
6.        Dane = Szyfrogram

c) Modyfikujemy teraz zawartość czterech S-bloków, każdy złożony z 256 elementów.

Modyfikacja S-bloków
1.    for k = 0 to 3 do
2.        for i = 0 to 127 do
3.            Szyfrogram = BlowfishEncrypt(Dane)
4.            S[k, i * 2] = Szyfrogram(xL)
5.            S[k, i * 2 + 1] = Szyfrogram(xR)
6.            Dane = Szyfrogram

Zwróćmy uwagę, że szyfrowaliśmy ten sam blok o nazwie "dane" nie zerując go po zakończeniu poprzedniego algorytmu, tak więc wynik szyfrowania z ostatniego kroku algorytmu "Algorytm generowania kluczy pomocniczych P. Cz. 2." był wartością początkową dla pierwszej iteracji.

SZYFROWANIE  I  DESZYFROWANIE  ALG.  BLOWFISH


        Jeżeli potrafimy zapisać inicjowanie algorytmu oraz funkcje "F" w sposób podany poniżej

BlowfishInit (KEY)
1.    Len = Length(KEY)
2.    k = 0
3.    for i = 0 to 17 do
4.        A32 = KEY[(k + 3) modulo Len)
5.        A32 = A32 + (KEY[(k + 2) modulo Len] shl 8)
6.        A32 = A32 + (KEY[(k + 1) modulo Len] shl 16)
7.        A32 = A32 + (KEY[k] shl 24)
8.        P[i] = P[i] xor A32
9.        k = (k + 4) modulo Len
10.   Dane = 0
11.   for i = 0 to 8 do
12.       Szyfrogram = BlowfishEncrypt(Dane)
13.       P[i * 2] = Szyfrogram(xL)
14.       P[i * 2 + 1] = Szyfrogram(xR)
15.       Dane = Szyfrogram
16.   for k = 0 to 3 do
17.       for i = 0 to 127 do
18.           Szyfrogram = BlowfishEncrypt(Dane)
19.           S[k, i * 2] = Szyfrogram(xL)
20.           S[k, i * 2 + 1] = Szyfrogram(xR)
21.           Dane = Szyfrogram


F (xL)
1.    a = (xL shr 24) and 255
2.    b = (xL shr 16) and 255
3.    c = (xL shr 8)  and 255
4.    d = xL and 255
5.    Return ((((S[0, a] + S[1, b]) mod 232) xor S[2, c]) + S[3, d]) mod 232


procedury szyfrowania i deszyfrowania możemy zapisać w taki sposób:

BlowfishEncrypt (m)
1.    xL = wybierz starsze 32 bity z wiadomości "m"
2.    xR = wybierz młodsze 32 bity z wiadomości "m"
3.    for i = 0 to 15 do
4.        xL = xL xor P[i]
5.        xR = xR xor F(xL)
6.        if i < 15 then
7.           Tmp = xL
8.           xL  = xR
9.           xR  = Tmp
10.   xL = xL xor P[17]
11.   xR = xR xor P[16]
12.   Return xL złącz z xR do 64 bitów


BlowfishDecrypt (c)
1.    xL = wybierz starsze 32 bity z szyfrogramu "c"
2.    xR = wybierz młodsze 32 bity z szyfrogramu "c"
3.    xL = xL xor P[17]
4.    xR = xR xor P[16]
5.    for i = 15 downto 0 do
6.        xR = xR xor F(xL)
7.        xL = xL xor P[i]
8.        if i > 0 then
9.           Tmp = xL
10.          xL  = xR
11.          xR  = Tmp
12.   Return xL złącz z xR do 64 bitów

Mój adres e-mail: szyfrantd@poczta.onet.pl