Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 2014

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: WalkSAT

Sortuj według:

Ogranicz wyniki do:

Akceleracja obliczeń kryptograficznych z wykorzystaniem procesorów GPU

Bęza P., Gocławski J., Mral P., Sapiecha P.

Studia Bezpieczeństwa Narodowego

2014

R. 4, Nr 6

341--357

Problem spełnialności formuł rachunku zdań SAT jest jednym z fundamentalnych oraz otwartych zadań we współczesnej informatyce. Jest on problemem NP-zupełnym. To znaczy, że wszystkie problemy z klasy NP możemy sprowadzić do problemu SAT w czasie wielomianowym. Co ciekawe, wśród problemów z klasy NP istnieje wiele takich, które są ściśle związanych z kryptologią, na przykład: faktoryzacja liczb – ważna dla RSA, łamanie kluczy szyfrów symetrycznych, znajdowanie kolizji funkcji skrótu i wiele innych. Odkrycie wielomianowego algorytmu dla SAT skutkowałoby rozwiązaniem problemu milenijnego: P vs. NP. Cel ten wydaje się bardzo trudny do osiągnięcia – nie wiadomo nawet czy jest możliwy. Mając nieco mniejsze aspiracje możemy projektować algorytmy heurystyczne lub losowe dla SAT. W związku z tym, głównym celem autorów pracy jest przedstawienie projektu równoległego SAT Solvera bazującego na algorytmie WalkSAT, w tym procesu jego implementacji z wykorzystaniem środowiska programistycznego OpenCL oraz komputera wyposażonego w karty graﬁczne NVIDIA Tesla. Wraz z dynamicznym rozwojem technologii procesorów typu GPU oraz układów FPGA, jak również przenośnością rozwiązań stworzonych w Open CL, kierunek takich prac staje się interesujący ze względu na uzyskiwaną efektywność obliczeniową, jak również szybkość prototypowania rozwiązań.

The Boolean satisﬁability problem SAT is one of the fundamental and open tasks in present-day information science. This problem is NP-complete. It means that all NP problems can be reduced to SAT in polynomial time. Interestingly, among NP problems, there are many closely related to cryptology, for example: factorization of numbers – important for RSA, breaking keys of symmetric ciphers, ﬁnding collisions of hash functions and many others. The discovery of the polynomial algorithm for SAT would result in resolving one of Millennium Prize Problems: P vs. NP. This objective seems to be hard to achieve – it’s unknown if it is even possible. With slightly lower aspirations, we can design heuristic or random algorithms for SAT. Therefore, the main goal of our study is to present a project of parallel SAT Solver based on WalkSAT algorithm, including its implementation using the OpenCL programming environment and a computer equipped with NVIDIA Tesla graphics cards. With the rapid development of GPU technology and FPGAs, as well as portability of solutions created in OpenCL, the direction of such works becomes interesting because of computational eﬃciency gained, as well as solution prototyping rate.