講演抄録/キーワード |
講演名 |
2007-09-07 14:20
格子篩に基づく数体篩法のFPGA実装 下山武司・伊豆哲也・○小暮 淳(富士通) ISEC2007-84 |
抄録 |
(和) |
素因数分解の困難性については、従来ソフトウェアによる評価が中心となって行なわれてきたが、最近では専用ハードウェアによる評価が注目されている。伊豆らは 2006 年に Xilinx 社の FPGA を用い、768 bit 合成数までをターゲットとした素因数分解ハードウェア専用装置 CAIRN 2 を開発している。ただし CAIRN 2 は、線形篩法と呼ばれる手法をベースに実装されているため、処理性能の面で、必ずしも最適とは言えなかった。本論文では、より性能を向上させた素因数分解ハードウェア装置 CAIRN 3 について報告する。CAIRN 3 は、線形篩法に代わり格子篩法を用いたことにより、CAIRN 2 に比べて性能の面で 38 倍の効率化を達成しており、また本装置を1台用いた場合、RSA768の分解に約 270 年必要であることが見積もられたことを述べる。 |
(英) |
The hardness of the integer factorization problem assures the security of some public-key cryptosystems including RSA, and the number field sieve method (NFS), the most efficient algorithm for factoring large integers currently,is a threat for such cryptosystems. Recently, Izu et al.\ developed a dedicated sieving device CAIRN 2 with Xilinx's FPGA which is designed to handle up to 768-bit integers. However, since CAIRN 2 uses the line sieving, it is not optimized from the viewpoint of the efficiency. In this paper, we report some results of an FPGA-based sieving hardware CAIRN 3 with the lattice sieving. In the experimental sieving for a 768-bit integer (RSA768),CAIRN 3 is about 38 times faster than CAIRN 2. It is estimated that the full sieving for RSA768 requires about 270 years with single CAIRN 3. |
キーワード |
(和) |
素因数分解 / 数体篩法 / 篩処理 / ハードウェア / FPGA / / / |
(英) |
Integer factorization / the number field sieve method (NFS) / the sieving step / implementation / FPGA / / / |
文献情報 |
信学技報, vol. 107, no. 209, ISEC2007-84, pp. 77-83, 2007年9月. |
資料番号 |
ISEC2007-84 |
発行日 |
2007-08-31 (ISEC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2007-84 |