PL EN
ARTYKUŁ PRZEGLĄDOWY
AKCELERACJA OBLICZEŃ KRYPTOGRAFICZNYCH Z WYKORZYSTANIEM PROCESORÓW GPU
 
Więcej
Ukryj
1
Politechnika Warszawska
 
 
Data publikacji: 05-12-2014
 
 
SBN 2014;6(2): 341-357
 
SŁOWA KLUCZOWE
STRESZCZENIE
Problem spełnialności formuł rachunku zdań SAT jest jednym z fundamentalnych oraz otwartych zadań we współczesnej informatyce. Jest on problemem N P-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 graficzne 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 OpenCL, kierunek takich prac staje się interesujący ze względu na uzyskiwaną efektywność obliczeniową, jak również szybkość prototypowania rozwiązań.
 
REFERENCJE (30)
1.
T. Eibach, E. Pilz, and G. Volkel ¨ , Attacking Bivium Using SAT Solvers, University of Ulm, Institute of Theoretical Computer Science http://www.uni-ulm.de/fileadmi... uni ulm/iui.inst.190 /Mitarbeiter/eibach/Attacking-Bivium-Using-SAT-Solvers.pdf, 01.02.2014.
 
2.
M. Luisier, A. Schenk, IEEE TRANSACTIONS ON ELECTRON DEVICES, http://www.iis.ee.ethz.ch/ schenk/04495122.pdf, 24.04.2014.
 
3.
S. Anthony, 7nm, 5nm, 3nm: The new materials and transistors that will take us to the limits of Moores law, http://www.extremetech.com/com...- -new-materials-and-transistors-that-will-take-us-to-the-limits-of-moores-law, 24.04.2014.
 
4.
NVIDIA Website, http://www.nvidia.pl/object/cu..., 24.04.2014.
 
5.
SAT Competition, Strona internetowa konkursu SAT Competition, http://www.satcompetition.org/, 01.05.2014.
 
6.
N. Een, N. Sorensson ¨ , An Extensible SAT-solver, [W:] SAT, pod red. Enrico Giunchiglia, Armando Tacchella, Springer, 2003, s. 502–518.
 
7.
C. F. Madigan, S. Malik, M. W. Moskewicz, L. Zhang, Y. Zhao, Chaff: Engineering an Efficient SAT Solver, 39th Design Automation Conference (DAC 2001), ACM, 2001.
 
8.
Glucose, The Glucose SAT Solver. http://www.labri.fr/perso/lsim..., 17.04.2014.
 
9.
WalkSAT, WalkSAT Home Page, http://www.cs.rochester.edu/u/..., 17.04.2014.
 
10.
H. H. Hoos, D. A. D. Tompkins, Novelty+ and Adaptive Novelty+, https://cs.uwaterloo.ca/ dtompkin/papers/satcomp04-novp.pdf, University of British Columbia, 2004.
 
11.
H. Deleau, Ch. Jaillet, M. Krajecki, GPU4SAT: solving the SAT problem on GPU, CReSTIC SysCom, Universitae de Reims Champagne-Ardenne, 2008.
 
12.
V. W. Marek, Introduction to Mathematics of Satisfiability, CRC Press, 2008.
 
13.
G. V. Bard, Algorithms for Solving Linear and Polynomial Systems of Equations over Finite Fields with Applications to Cryptanalysis, Rozprawa doktorska, 2007.
 
14.
S. Cook, The complexity of theorem proving procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, s. 151–158.
 
15.
W. Chrabakh, R. Wolski, GrADSAT: A Parallel SAT Solver for the Grid, University of California Santa Barbara, 2003.
 
16.
D.N. Pham, C. Gretton, gNovelty+ (v.2) [W:] Solver description, SAT competition, 2009.
 
17.
Y. Hamadi, S. Jabbour, L. Sais, ManySAT: A Parallel SAT Solver, Journal on Satisfiability, Boolean Modeling and Computation, JSAT 6, 2009, s. 245–262.
 
18.
A. Roli, Criticality and Parallelism in Structured SAT Instances, [W:] CP’02. Volume 2470 of LNCS., pod red. P. V. Hentenryck, 2002, s.714–719.
 
19.
Instytut Matematyczny Claya http://www.claymath.org/millen..., 07.05.2014.
 
20.
top500.org, Titan – Cray XK7 , Opteron 6274 16C 2.200GHz, Cray Gemini interconnect, NVIDIA K20x, http://www.top500.org/system/1..., 05.02.2014.
 
21.
top500.org, Oak Ridge Claims No. 1 Position on Latest TOP500 List with Titan, http://www.top500.org/blog/lis..., 05.02.2014.
 
22.
amazon.com, http://www.amazon.com/nVidia-K... dp/B00CX35KU2, 28.04.2014.
 
23.
Oak Ridge Computing Facility, https://www.olcf.ornl.gov/supp..., 24.04.2014.
 
24.
computer store – newegg.com, http://www.newegg.com/Product/...= N82E16814132015, 24.04.2014.
 
25.
Texas Advanced Computing Center, https://www.tacc.utexas.edu/ news/press-releases/2013/tacc-to-deploy-maverick, 28.04.2014.
 
26.
M. Vor¨ os¨ , Algebraic attack on stream ciphers, praca magisterska, Bratislava, 2007.
 
27.
Khronos Group – OpenCL, http://www.khronos.org/opencl/, 28.04.2014.
 
28.
CUDA Examples, http://www.nvidia.pl/object/gp..., 28.04.2014.
 
29.
VirtualCL, http://www.mosix.org/txt vcl.html/, 28.04.2014.
 
30.
Timo Stich, OpenCL on NVIDIA GPUs, http://sa09.idav.ucdavis.edu/d... NVIDIA IHV talk.pdf, 09.02.2014.
 
ISSN:2082-2677
Journals System - logo
Scroll to top