Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study

R.H. Bisseling; I. Flesch

Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study

R.H. Bisseling, I. Flesch

Dep Wiskunde

extern

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

A case study is presented demonstrating the application of the Mondriaan package for sparse matrix partitioning to the field of cryptology. An important step in an integer factorisation attack on the RSA public-key cryptosystem is the solution of a large sparse linear system with 0/1 coefficients, which can be done by the block Lanczos algorithm proposed by Montgomery. We parallelise this algorithm using Mondriaan partitioning and discuss the high-level components needed. A speedup of 10 is obtained on 16 processors of a Silicon Graphics Origin 3800 for the factorisation of an integer with 82 decimal digits, and a speedup of 7 for 98 decimal digits.

Original language	English
Title of host publication	Parallel computing
Subtitle of host publication	Current and Future Issues of High-end Computing, Proceedings ParCo 2005
Editors	G.R. Joubert, W.E. Nagel, F.J. Peters, O. Plata, P. Tirado, E. Zapata
Place of Publication	Jülich, Germany
Publisher	John von Neumann Institute for Computing
Pages	819-826
Number of pages	8
ISBN (Print)	3-00-017352-8
Publication status	Published - 2006

Publication series

Name	NIC series
Volume	33

Keywords

Mathematics
Wiskunde en computerwetenschappen
Landbouwwetenschappen
Wiskunde: algemeen

Access to Document

SparseFinal published version, 96.6 KBLicence: CC BY-NC

Cite this

Bisseling, R. H., & Flesch, I. (2006). Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study. In G. R. Joubert, W. E. Nagel, F. J. Peters, O. Plata, P. Tirado, & E. Zapata (Eds.), Parallel computing: Current and Future Issues of High-end Computing, Proceedings ParCo 2005 (pp. 819-826). (NIC series; Vol. 33). John von Neumann Institute for Computing.

Bisseling, R.H. ; Flesch, I. / Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study. Parallel computing: Current and Future Issues of High-end Computing, Proceedings ParCo 2005. editor / G.R. Joubert ; W.E. Nagel ; F.J. Peters ; O. Plata ; P. Tirado ; E. Zapata. Jülich, Germany : John von Neumann Institute for Computing, 2006. pp. 819-826 (NIC series).

@inproceedings{75cd9c08b326467e984ced3b3aed4828,

title = "Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study",

abstract = "A case study is presented demonstrating the application of the Mondriaan package for sparse matrix partitioning to the field of cryptology. An important step in an integer factorisation attack on the RSA public-key cryptosystem is the solution of a large sparse linear system with 0/1 coefficients, which can be done by the block Lanczos algorithm proposed by Montgomery. We parallelise this algorithm using Mondriaan partitioning and discuss the high-level components needed. A speedup of 10 is obtained on 16 processors of a Silicon Graphics Origin 3800 for the factorisation of an integer with 82 decimal digits, and a speedup of 7 for 98 decimal digits.",

keywords = "Mathematics, Wiskunde en computerwetenschappen, Landbouwwetenschappen, Wiskunde: algemeen",

author = "R.H. Bisseling and I. Flesch",

year = "2006",

language = "English",

isbn = "3-00-017352-8",

series = "NIC series",

publisher = "John von Neumann Institute for Computing",

pages = "819--826",

editor = "G.R. Joubert and W.E. Nagel and F.J. Peters and O. Plata and P. Tirado and E. Zapata",

booktitle = "Parallel computing",

}

Bisseling, RH & Flesch, I 2006, Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study. in GR Joubert, WE Nagel, FJ Peters, O Plata, P Tirado & E Zapata (eds), Parallel computing: Current and Future Issues of High-end Computing, Proceedings ParCo 2005. NIC series, vol. 33, John von Neumann Institute for Computing, Jülich, Germany, pp. 819-826.

Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study. / Bisseling, R.H.; Flesch, I.
Parallel computing: Current and Future Issues of High-end Computing, Proceedings ParCo 2005. ed. / G.R. Joubert; W.E. Nagel; F.J. Peters; O. Plata; P. Tirado; E. Zapata. Jülich, Germany: John von Neumann Institute for Computing, 2006. p. 819-826 (NIC series; Vol. 33).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study

AU - Bisseling, R.H.

AU - Flesch, I.

PY - 2006

Y1 - 2006

N2 - A case study is presented demonstrating the application of the Mondriaan package for sparse matrix partitioning to the field of cryptology. An important step in an integer factorisation attack on the RSA public-key cryptosystem is the solution of a large sparse linear system with 0/1 coefficients, which can be done by the block Lanczos algorithm proposed by Montgomery. We parallelise this algorithm using Mondriaan partitioning and discuss the high-level components needed. A speedup of 10 is obtained on 16 processors of a Silicon Graphics Origin 3800 for the factorisation of an integer with 82 decimal digits, and a speedup of 7 for 98 decimal digits.

AB - A case study is presented demonstrating the application of the Mondriaan package for sparse matrix partitioning to the field of cryptology. An important step in an integer factorisation attack on the RSA public-key cryptosystem is the solution of a large sparse linear system with 0/1 coefficients, which can be done by the block Lanczos algorithm proposed by Montgomery. We parallelise this algorithm using Mondriaan partitioning and discuss the high-level components needed. A speedup of 10 is obtained on 16 processors of a Silicon Graphics Origin 3800 for the factorisation of an integer with 82 decimal digits, and a speedup of 7 for 98 decimal digits.

KW - Mathematics

KW - Wiskunde en computerwetenschappen

KW - Landbouwwetenschappen

KW - Wiskunde: algemeen

M3 - Conference contribution

SN - 3-00-017352-8

T3 - NIC series

SP - 819

EP - 826

BT - Parallel computing

A2 - Joubert, G.R.

A2 - Nagel, W.E.

A2 - Peters, F.J.

A2 - Plata, O.

A2 - Tirado, P.

A2 - Zapata, E.

PB - John von Neumann Institute for Computing

CY - Jülich, Germany

ER -

Bisseling RH, Flesch I. Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study. In Joubert GR, Nagel WE, Peters FJ, Plata O, Tirado P, Zapata E, editors, Parallel computing: Current and Future Issues of High-end Computing, Proceedings ParCo 2005. Jülich, Germany: John von Neumann Institute for Computing. 2006. p. 819-826. (NIC series).

Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this