Crypto-IT

• Długość bloku = 128 bitów
• Długość klucza = 128, 192 lub 256 bitów

Szyfr został opracowany w Japonii przez firmy Mitsubishi i NTT w roku 2000. Jest zatwierdzony jako skuteczny i bezpieczny algorytm szyfrujący przez wiele organizacji na całym świecie, między innymi Międzynarodową Organizację Normalizacyjną (ang. International Organization for Standardization - ISO), projekt badawczy UE NESSIE oraz japoński CRYPTREC.

Camellia został zaprojektowany dla efektywnego działania w rozwiązaniach programistycznych i sprzętowych. Jest używana w wielu różnych sytuacjach od tanich kart elektronicznych do wydajnych protokołów sieciowych.

Camellia jest szyfrem blokowym z kluczem symetrycznym o długości 128, 192 lub 256 bitów. Wielkości bloków tekstu jawnego i szyfrogramu są takie same i wynoszą zawsze 128 bitów.

W opisie szyfru zachowano oryginalne nazewnictwo wszystkich wykorzystywanych zmiennych, bazując na oficjalnej dokumentacji Camellia.

Najważniejszymi elementami algorytmu są funkcje F, które wykorzystywane są podczas szyfrowania, deszyfrowania i manipulacji zmiennymi pomocniczymi klucza. Funkcja F pobiera 128 bitów wejściowych, miesza je z bitami podkluczy k_i i zwraca 128 nowych bitów. Przekształcenie bitów w funkcji F nazywane jest rundą algorytmu. Wywołania funkcji F zebrane są w bloki zawierające sześć kolejnych powtórzeń takich rund.

Bloki sześciu rund (czyli sześciu wywołań funkcji F) oddzielone są wywołaniami funkcji FL oraz FL^-1. Manipulują one 64-bitowymi partiami danych, mieszając je z podkluczami kl_i.

Algorytmy szyfrowania i deszyfrowania polegają na wykonaniu pewnej liczby powtórzeń opisanych wyżej bloków sześciu rund (wywołań funkcji F). Ilość powtórzeń tych bloków zależy od długości używanego sekretnego klucza szyfrującego:

• 3 powtórzenia bloków sześciu rund - dla klucza o długości 128 bitów,
• 4 powtórzenia bloków sześciu rund - dla kluczy o długości 192 lub 256 bitów.

Dodatkowo, na początku i na końcu działania algorytmów szyfrującego i deszyfrującego wykonywane są dodatkowe operacje sumowania z bitami podkluczy kw_i.

Podklucze wykorzystywane do zaszyfrowania każdego bloku danych (lub odczytania każdego bloku szyfrogramu) tworzone są w oddzielnym procesie. Dla każdego bloku danych, z sekretnego klucza tworzonych jest wiele podkluczy, wykorzystywanych potem w różnych miejscach głównego algorytmu.

Sekretny klucz używany w szyfrze Camellia może składać się ze 128, 192 lub 256 bitów. W celu zaszyfrowania każdego bloku danych, z bitów klucza tworzonych jest szereg zmiennych pomocniczych, a następnie podkluczy, z których każdy ma długość 64 bitów.

W pierwszej kolejności tworzone są dwie zmienne o długości 128 bitów (K_L oraz K_R) oraz cztery zmienne o długości 64 bitów (K_LL, K_LR, K_RL oraz K_RR). Zmienne te związane są pomiędzy sobą następującymi zależnościami:

• K_LL = lewe 64 bity K_L
• K_LR = prawe 64 bity K_L
• K_RL = lewe 64 bity K_R
• K_RR = prawe 64 bity K_R

Pozostałe zależności należy wybrać bazując na używanej długości sekretnego klucza K.

• dla sekretnego klucza K o długości 128 bitów:
  • K_L = K
  • K_R = 0
• dla sekretnego klucza K o długości 192 bitów:
  • K_L = lewe 128 bitów K
  • K_RL = prawe 64 bity K
  • K_RR = ~K_RL (negacja bitów)
• dla sekretnego klucza K o długości 256 bitów:
  • K_L = lewe 128 bitów K
  • K_R = prawe 128 bitów K

Na podstawie tych zmiennych generuje się dwie kolejne zmienne pomocnicze: K_A oraz K_B. Każda z nich składa się ze 128 bitów. Zmienna K_B jest różna od zera wtedy i tylko wtedy, gdy wykorzystywany sekretny klucz ma 192 lub 256 bitów. W procesie tworzenia zmiennych K_A i K_B wykorzystuje się sześć pomocniczych stałych oznaczanych jako ∑_i.

Na podstawie czterech 128-bitowych zmiennych K_L, K_R, K_A i K_B wyliczane są wszystkie sekretne 64-bitowe podklucze: k_i, kw_i oraz kl_i. Podklucze wykorzystywane są we wszystkich etapach szyfrowania i deszyfrowania w algorytmie Camellia.

Camellia wykorzystuje zestaw podstawowych operacji na bitach używanych w komputerach: iloczyn bitowy AND, sumę bitową OR, operację sumowania XOR, negację bitów w zmiennej oraz przesunięcie bitów w lewo o podaną liczbę pozycji <<< n (bity ze skrajnie lewych pozycji przechodzą na wolne skrajnie prawe pozycje w zmiennej).

Poza tymi podstawowymi działaniami, zdefiniowane są bardziej złożone funkcje, z których składają się algorytmy szyfrujący i deszyfrujący oraz algorytm tworzenia podkluczy.

Funkcja S jest wykorzystywana przez funkcję F. Dane wejściowe o długości 64 bitów są podmieniane na inne 8 bajtów, zwracane następnie do dalszego przetwarzania.

Funkcja wykorzystuje w swoim działaniu 4 tablice podstawieniowe, nazywane blokami S (ang. s-box).

Dane wejściowe dzielone są na osiem oddzielnych bajtów x₁,...,x₈, z których x₁ zawiera najbardziej skrajne osiem bitów, x₂ kolejne osiem bitów, a x₈ ostatnie skrajne osiem prawych bitów.

Każdy z bloków S podmienia osiem otrzymanych bitów na osiem innych bitów wskazanych w tabeli. Bloki S oznaczone są jako s₁,...,s₄. Oznaczając przez y₁,...,y₈ osiem klejnych bajtów wyjściowych z funkcji (bajt y₁ zawiera najbardziej lewe bity wyjściowe, natomiast bajt y₈ zawiera najbardziej prawe bity wyjściowe), można przedstawić przekształcenia dokonywane w funkcji S jako:

    y₁ = s₁(x₁)
    y₂ = s₂(x₂)
    y₃ = s₃(x₃)
    y₄ = s₄(x₄)
    y₅ = s₂(x₅)
    y₆ = s₃(x₆)
    y₇ = s₄(x₇)
    y₈ = s₁(x₈)

Blok s₁ zawiera 256 następjących wartości:

Bloki S zwracają wartości wskazane przez jednobajtową liczbę wejściową. Komórki w tabeli numerowane są liczbami od 0 do 255, od lewej do prawej strony oraz od góry do dołu. Przykładowo s₁[0] wynosi 112, s₁[1] równa się 130, natomiast s₁[255] wynosi 158.

Pozostałe trzy bloki S mogą zostać zdefiniowane jako tablice zawierające 256 liczb, podobnie jak blok s₁. Alternatywnie, można operacje na nich przedstawić jako działania na s₁, ze zmienionymi danymi wejściowymi:

    s₂(x) := (s₁(x) <<< 1)
    s₃(x) := (s₁(x) >>> 1)
    s₄(x) :=   s₁(x<<<1)

Funkcja P jest wykorzystywana przez funkcję F. Funkcja P pobiera dane wejściowe o długości 8 bajtów (które są wyjściem z funkcji S), przekształca je i zwraca również wektor o długości 8 bajtów. Wyjście z funkcji P jest też wyjściem z funkcji F.

Dane wejściowe dzielone są na osiem oddzielnych bajtów x₁,...,x₈, z których x₁ zawiera najbardziej skrajne osiem bitów, x₂ kolejne osiem bitów, natomiast x₈ ostatnie skrajne osiem prawych bitów.

Oznaczając osiem klejnych bajtów wyjściowych z funkcji jako y₁,...,y₈ (gdzie y₁ zawiera najbardziej lewe osiem bitów wyjściowych, y₂ kolejne osiem bitów, natomiast y₈ zawiera skrajne prawe osiem bitów wyjściowych), można przedstawić przekształcenia dokonywane w funkcji P jako:

    y₁ = x₁ XOR x₃ XOR x₄ XOR x₆ XOR x₇ XOR x₈
    y₂ = x₁ XOR x₂ XOR x₄ XOR x₅ XOR x₇ XOR x₈
    y₃ = x₁ XOR x₂ XOR x₃ XOR x₅ XOR x₆ XOR x₈
    y₄ = x₂ XOR x₃ XOR x₄ XOR x₅ XOR x₆ XOR x₇
    y₅ = x₁ XOR x₂ XOR x₆ XOR x₇ XOR x₈
    y₆ = x₂ XOR x₃ XOR x₅ XOR x₇ XOR x₈
    y₇ = x₃ XOR x₄ XOR x₅ XOR x₆ XOR x₈
    y₈ = x₁ XOR x₄ XOR x₅ XOR x₆ XOR x₇

Funkcja F jest jedną z głównych funkcji wykorzystywaną podczas szyfrowania i deszyfrowania danych oraz generowania podkluczy. Dane wejściowe (X) mają długość 64 bitów i są mieszane z jednym z podkluczy (k), również o długości 64 bitów. Funkcja zwraca 64 bity oznaczone jako Y.

Bity danych są dodawane XOR do bitów klucza, a następnie przekształcane przez dwie funkcje S oraz P.

    (X, k) -> Y  =>  P (S (X XOR k)) -> Y

Funkcja FL wykorzystywana jest podczas szyfrowania i deszyfrowania. Operuje na bloku danych o długości 64 bitów. Bity są mieszane z jednym z podkluczy i zwracany blok wyjściowy ma również długość 64 bitów.

Blok danych wejściowych jest oznaczony jako X, natomiast Y to 64 bity wyjściowe, a kl to bity utworzonego wcześniej podklucza:

    (X, kl) -> Y  =>  (X_L || X_R, kl_L || kl_R) -> Y_L || Y_R

W pierwszej kolejności X jest dzielone na dwie 32-bitowe połówki: X_L zawiera 32 lewych bitów X, natomiast X_R składa się z 32 prawych bitów X. Następnie wylicza dwa bloki, również o długości 32 bitów:

    Y_R = ((X_L AND kl_L) <<< 1) XOR X_R
    Y_L = (Y_R OR kl_R) XOR X_L

Y_L stanowi 32 lewe bity wyjściowe z funkcji FL, natomiast Y_R to 32 prawe bity wyjściowe.

Funkcja FL^-1 wykorzystywana jest podczas algorytmów szyfrowania i deszyfrowania. Operuje na bloku danych o długości 64 bitów, który mieszany jest z jednym z podkluczy. Zwracany blok wyjściowy ma również długość 64 bitów.

Blok danych wejściowych jest oznaczony jako Y, natomiast X to 64 bity wyjściowe, a kl to bity utworzonego wcześniej podklucza:

    (Y, kl) -> X  =>  (Y_L || Y_R, kl_L || kl_R) -> X_L || X_R

W pierwszej kolejności Y jest dzielone na dwie 32-bitowe połówki: Y_L zawiera 32 lewych bitów Y, natomiast Y_R składa się z 32 prawych bitów Y. Następnie wylicza dwa bloki, również o długości 32 bitów:

    X_L = (Y_R OR kl_R) XOR Y_L
    X_R = ((X_L AND kl_L) <<< 1) XOR Y_R

X_L stanowi 32 lewe bity wyjściowe z funkcji FL^-1, natomiast X_R to 32 prawe bity wyjściowe.

W trakcie generowania podkluczy w procesie szyfrowania i deszyfrowania kolejnych bloków używanych jest sześć stałych wartości, oznaczanych jako ∑_i.

Poniższe wartości mają długości 64 bitów i są przedstawione w zapisie szesnastkowym.

Na podstawie czterech 128-bitowych zmiennych K_L, K_R, K_A i K_B należy wyliczyć podklucze k_i, kw_i oraz kl_i, wszystkie o długości 64 bitów.

Tabela generowania podkluczy dla sekretnego klucza o długości 128 bitów:

Tabela generowania podkluczy dla sekretnych kluczy o długości 192 bitów lub 256 bitów:

Na stronie korporacji NTT można znaleźć kody źródłowe i szczegółowe opisy szyfru Camellia:
    info.isl.ntt.co.jp/crypt/eng/camellia