Change search
ReferencesLink to record
Permanent link

Direct link
Attacking RSA moduli with SAT solvers
KTH, School of Computer Science and Communication (CSC).
2014 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

This thesis aimed to explore how sequential boolean satisability solvers can be used on the integer factorisation problem. The integer factorisation problem is believed to be hard and modern public key cryptography relies on that,note worthily SSL/TSL and SSH support the use of RSA. However, it is not proven that integer factorisation is hard and therefore it is of great importanceto explore dierent attack avenues. The modulus in RSA is a semiprime, integer that is the product of two primes. Hence, in this thesis an empiricalstudy of the factorisation of semiprimes with a bit-length of up to 32 bits iscarried out. Randomly selected semiprimes are factorized through six dierent reductions using three dierent solvers (Glucose, Lingeling and PicoSAT) and the result are compared to that of MSieve, an open-source integer factorisationprogram. As seen in the comparison boolean satisability solvers cannot be used as a replacement of an integer factorisation solver. Additionally comparisons between the dierent reductions and boolean satisability solvers show that the combination of solver and reduction greatly aects performance. The implication is that further explorations of the integer factorisation problem with boolean satisability solvers can greatly benet from either avoiding a inadequate solver and reduction pair or from attempting to identify the outliers that signify a inadequate coupling.

Place, publisher, year, edition, pages
National Category
Computer Science
URN: urn:nbn:se:kth:diva-157352OAI: diva2:769846
Available from: 2014-12-09 Created: 2014-12-09 Last updated: 2014-12-09Bibliographically approved

Open Access in DiVA

fulltext(6432 kB)211 downloads
File information
File name FULLTEXT01.pdfFile size 6432 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 211 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 356 hits
ReferencesLink to record
Permanent link

Direct link