---
title: "Szyfr DES jest 40 razy szybszy w OpenCL"
url: https://michalasobczak.pl/pl/posts/des-cipher-is-40-times-faster-in-opencl.html
author: "Michał Sobczak"
description: "Implementacja szyfru DES w OpenCL jest znacznie szybsza niż zwykły jednowątkowy program w C. 1 mln operacji szyfrowania zajmuje mniej niż sekundę na RTX 3050 Ti, ale aż prawie 40 sekund w jednowątkowej aplikacji na Intel i5-10200h."
published: 2022-12-25T16:43:59.000Z
updated: 2024-08-29T08:23:41.000Z
language: pl
categories: ["AI/ML"]
tags: ["Programming", "GPU", "HPC", "OpenCL"]
license: CC BY-NC-ND 4.0 (https://creativecommons.org/licenses/by-nc-nd/4.0/)
---
# Szyfr DES jest 40 razy szybszy w OpenCL

**Implementacja szyfru DES w OpenCL jest znacznie szybsza niż zwykły jednowątkowy program w C. 1 mln operacji szyfrowania zajmuje mniej niż sekundę na RTX 3050 Ti, ale aż prawie 40 sekund w jednowątkowej aplikacji na Intel i5-10200h.**

**Brak kompaktowej i niezwykle przenośnej biblioteki SSL/TLS w projekcie sprzed C++11** skłonił mnie do poszukania czegoś łatwego do samodzielnego zaimplementowania w zakresie **szyfrowania danych**. Wybrałem DES, czyli Data Encryption Standard, ze względu na moje ogólne rozumienie tego algorytmu. Pochodzi on z 1975 roku i ma pewne **ograniczenia**, w tym **krótką długość klucza** czy znane **słabe klucze**. Jeśli jednak odłożymy uprzedzenia na bok, możemy dostrzec kilka interesujących rzeczy, a także możliwości.

Napisanie kernela C99 w OpenCL zajęło mi kilka dni. Wcześniej wypróbowałem kilka zewnętrznych przykładów w c++. Ich główną wadą jest to, że wszystkie używają `strings`, `vectors`, `stringstreams` i kilku innych funkcji typowych wyłącznie dla c++. Nawet użycie `printf` jest problematyczne w implementacjach OpenCL, ponieważ może być niedostępne albo działać różnie w zależności od implementacji. Nie będzie można też użyć niektórych funkcji c99, takich jak `malloc`/`free`. Aby więc uzyskać maksymalną kompatybilność, zszedłem do **najprostszych rozwiązań**.

Szczególnie podoba mi się przykład, w którym używa się **danych binarnych w postaci ciągów znaków (tablic uchar)**. Dzięki temu łatwo zobaczyć, co się dzieje. Oczywiście (naprawdę?) zwiększa to złożoność oraz liczbę instrukcji, a także zużycie pamięci, ale jak na pierwszą implementację DES jest to **akceptowalne**. W różnych miejscach zobaczysz więc tablice **8-bajtowych elementów oznaczających 64 bity danych**. Klucze i inne wartości jako 56 lub 48 bitów danych, a połówki jako wartości 32-bitowe (4-bajtowe liczby). Zarówno dane wejściowe, jak i wyjściowe można wyświetlić jako znaki. Wejście będzie zwykłym ASCII, ale **wyjście przekracza kod ASCII 128 dziesiętnie**, więc w przypadku wypisywania znaków zamiast samych liczb możesz zobaczyć dziwne symbole.

## OpenCL kontra jednowątkowy C

Aby uruchomić **kod kernela poza środowiskiem uruchomieniowym OpenCL**, trzeba zapewnić kilka rzeczy:

```cpp
#include "stdio.h"
#include <math.h>

typedef unsigned char uchar;
```

Trzeba **dodać bibliotekę matematyczną** w wywołaniu GCC, ponieważ domyślnie nie jest dołączana:

```bash
gcc des.c -lm
```

Następnie główną funkcję kernela trzeba **dostosować**, na przykład tak:

```cpp
void kernel() { 
  // here we have the kernel function body...
}
```

I na koniec dostarczyć **funkcję main** języka C z już sparametryzowanymi iteracjami:

```cpp
int main() {
    int i;
	for (i=0; i<1024*1024; i++) {
		if (i % 1024 == 0) {
			printf("i: %i ", i);
		}
		kernel();
	}
}
```

**Dla uproszczenia pomijam definicję `uchar8`** i jej obsługę, ponieważ nie dodaje wiele do ogólnej złożoności kodu i algorytmu. Uruchamiam na różnym sprzęcie z 1024\*1024 iteracjami. Najpierw porównam czas wykonania na CPU:

| Sprzęt | Czas trwania |
| --- | --- |
| Dell G15: Intel Core i5 10200H 2.4 GHz | 38s |
| MacBookPro3,1: Intel Core 2 Duo 2.2 GHz | 1min 37s |
| PowerBook G4: PowerPC G4 800 MHz | 11 min 22s |

Teraz porównajmy to z **czasem wykonania w OpenCL:**

| Sprzęt | Liczba rdzeni | Compute Units (wg OpenCL) | Czas trwania |
| --- | --- | --- | --- |
| NVIDIA GeForce RTX 3050 Ti Mobile | 2560 | 20 | 930ms |
| Intel UHD 10th gen | 192 | 12 | 2065ms |

## Bazowy projekt w Javie

Korzystam z **bazowego projektu OpenCL**, który można znaleźć [tutaj](https://github.com/michalasobczak/publications/tree/master/opencl). Jest w nim jeden **dodatkowy moduł** o nazwie „des”. Pierwotnie używałem Javy 17, ale dziś wybieram Javę 19. Szczerze mówiąc, nie potrafię łatwo wskazać niczego aż tak istotnego między Javą 11 a 19. Każda wersja wprowadza **albo drobne zmiany w języku, albo nie wprowadza żadnych**. Jeśli jednak piszesz złożone aplikacje obiektowe, te zmiany mogą być dla Ciebie interesujące.

Zatem… najpierw wypełniam tablicę danych źródłowych następującą funkcją:

```java
    public void generateSampleRandomData() {
        Random rd = new Random();
        for (int i = 0; i <= (n*8) - 1; i++) {
            byte c = (byte)('a' + rd.nextInt(10));
            srcArrayA[i] = c;
        }
    }
```

Ta funkcja generuje `n*8` elementów typu byte w zakresie od dziesiętnej reprezentacji litery ‘a’ w ASCII i 10 kolejnych wartości. Innymi słowy **losowe znaki będą w zakresie od ‘a’ do ‘j’, czyli dziesiętnie od 97 do 106**. Słowo o **typie byte** w języku Java – jest on zawsze ze znakiem, więc nie ma bezpośredniej możliwości użycia go jako typu bez znaku. Istnieje jednak funkcja `Byte.toUnsignedInt`, która **zamienia ujemne wartości byte na dodatnie**.

Kolejna rzecz to **bufor**. Jak zobaczymy później, funkcja kernela wykorzystuje typ danych `uchar8`, więc trzeba odwzorować taki typ w Javie. Wpadłem na pomysł użycia zwykłej tablicy bajtów (`byte[]`). Każde wywołanie kernela **będzie mapować kolejne grupy po 8 elementów z tej płaskiej tablicy**:

```java
   public void createBuffers() {
        // Allocate the memory objects for the input- and output data
        this.memObjects[0] = clCreateBuffer(this.context, CL_MEM_READ_ONLY | CL_MEM_COPY_HOST_PTR, (long) Sizeof.cl_uchar8 * this.n, KernelConfigurationSet.srcA, null);
        this.memObjects[1] = clCreateBuffer(this.context, CL_MEM_READ_WRITE, (long) Sizeof.cl_uchar8 * this.n, null, null);
    }
```

Zarówno tablica źródłowa, jak i docelowa są typu `cl_uchar8`, który w samym kernelu odpowiada typowi `uchar8`. Do wypisania wyników zwracanych z wywołań kernela użyjemy wspomnianej wcześniej funkcji `Byte.toUnsignedInt`:

```java
public void printResults() {
        System.out.println("Elements: " + dstArray.length);
        int i = 0;
        for (byte tmp : dstArray) {
            System.out.println(String.valueOf(i) + " : " + (Byte.toUnsignedInt(tmp)) );
            i++;
        }
}
```

I to w zasadzie **wszystko, jeśli chodzi o część w Javie** tego wyzwania. Użycie Javy to tutaj kwestia wygody, bo można to zrobić również w c lub c++. Na razie nie wiem o żadnych rozbieżnościach w bibliotece JOCL i innych dostępnych bibliotekach.

## OpenCL 1.1

Aby uruchomić kod kernela na niektórych **starszych urządzeniach**, trzeba dostosować kilka rzeczy. Po pierwsze należy pozbyć się wywołań funkcji `printf` albo zdefiniować ją samodzielnie. Po drugie trzeba włączyć `cl_khr_fp64`, czyli **rozszerzenie** dla liczb zmiennoprzecinkowych, w przypadku używania typu `double`:

```cpp
#pragma OPENCL EXTENSION cl_khr_fp64 : enable
```

Istnieją możliwości, by nie używać funkcji `pow` i przerobić cały algorytm szyfru na operacje wyboru bitów. Dla moich celów edukacyjnych znacznie łatwiej jest jednak widzieć, co się dzieje, właśnie w takiej formie.

## Kernel C99

Podzieliłem algorytm szyfru DES na **27 punktów funkcjonalnych od FP00 do FP26**. Niektóre z nich zawierają wyłącznie dane, a inne składają się z procedur.

### Sekcja ogólna

-   FP00 – funkcje pomocnicze (linie 1-133)
-   FP01 – definicja kernela
-   FP02 – dane i identyfikacja
-   FP03 – klucz
-   FP04 – tekst jawny
-   FP05 – dane tablic PC1/PC2

### Generowanie kluczy

-   FP06 – permutacja klucza PC1
-   FP07 – podział klucza na dwie równe połowy
-   FP08 – 16 kluczy rund, dla 1, 2, 9 i 16 pojedyncze przesunięcia w lewo
-   FP09 – dla pozostałych iteracji podwójne przesunięcia w lewo
-   FP10 – połączenie lewej i prawej części
-   FP11 – permutacja klucza PC2

### Procedura szyfrowania

-   FP12 – tylko dane, dane permutacji początkowej i tablicy rozszerzenia
-   FP13 – tylko dane, S-boksy: 8 boksów, każdy po 4 wiersze i 16 kolumn
-   FP14 – tylko dane, tablica permutacji
-   FP15 – zastosowanie permutacji początkowej
-   FP16 – podział wyniku na dwie równe połowy
-   FP17 – szyfrowanie 16 razy, prawa połowa jest rozszerzana
-   FP18 – XOR wyniku z kluczem
-   FP19 – 8-krotne zastosowanie S-boksów
-   FP20 – zastosowanie permutacji
-   FP21 – XOR wyniku z lewą połową
-   FP22 – zamiana lewej i prawej części tekstu jawnego
-   FP23 – połączenie lewej i prawej części
-   FP24 – zastosowanie permutacji odwrotnej
-   FP25 – przygotowanie wyniku końcowego
-   FP26 – zapis wyniku do wyjściowego bufora OpenCL

## Podsumowanie

W tym wyzwaniu… którego kod źródłowy można znaleźć [tutaj](https://github.com/michalasobczak/publications/tree/master/opencl/des/src/com/michalasobczak/des), sprawdziłem możliwość zaimplementowania algorytmu szyfru DES na urządzeniach obsługujących OpenCL. Te 500 linii kodu można uruchomić albo na urządzeniu OpenCL, albo w nieco zmodyfikowanej formie na dowolnym innym urządzeniu, które potrafi skompilować język C. Implementacja OpenCL działa na GPU 40 razy szybciej niż na jednowątkowym CPU. To było całkiem interesujące…