Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Lanczos algorithm - a case study

被引：5

作者：

Bisseling, Rob H. ^{[1
]}

Flesch, Ildiko ^{[2
]}

机构：

[1] Univ Utrecht, Dept Math, NL-3508 TA Utrecht, Netherlands

[2] Radboud Univ Nijmegen, Dept Informat & Knowledge Syst, Inst Comp & Informat Sci, NL-6525 ED Nijmegen, Netherlands

来源：

PARALLEL COMPUTING | 2006年 / 32卷 / 7-8期

关键词：

Bulk synchronous parallel; Cryptology; Integer factorisation; Matrix partitioning; Sparse matrix;

D O I：

10.1016/j.parco.2006.08.005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 8 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. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：551 / 567

页数：17