PL EN
REVIEW PAPER
ACCELERATION OF CRYPTOGRAPHIC CALCULATIONS USING GPUS
 
More details
Hide details
1
Politechnika Warszawska
Publication date: 2014-12-05
 
SBN 2014;6(2): 341–357
 
KEYWORDS
ABSTRACT
The boolean satisfiability problem SAT is one of the fundamental and open tasks in present-day information science. This problem is NP-complete. It means that all N P 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, finding 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. N P. 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 efficiency gained, as well as solution prototyping rate.
 
REFERENCES (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