A Parallel and Uniform k-Partition Method for Montgomery Multiplication

被引：13

作者：

Neto, Joao Carlos ^{[1
]}

Tenca, Alexandre Ferreira ^{[2
]}

Ruggiero, Wilson Vicente ^{[1
]}

机构：

[1] Univ Sao Paulo, Polytech Sch, Dept Comp & Digital Syst Engn, BR-05508900 Sao Paulo, Brazil

[2] Synopsys Inc, Hillsboro, OR 97124 USA

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2014年 / 63卷 / 09期

关键词：

Cryptography; high-speed arithmetic; modular exponentiation and multiplication; high-radix; low-power; fault-tolerant; MODULAR MULTIPLICATION;

D O I：

10.1109/TC.2013.89

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A way to speed up the Montgomery Multiplication by distributing the multiplier operand bits into k partitions is proposed. All of them process in parallel and use an identical algorithm. Each partition executes its task in n/k steps. Even though the computation step operates in radix 2(k), the complexity is reduced by the use of a limited digit set. Experiments with a 90-nm cell library show that the hardware cost and its complexity have a linear growth according to the number of partitions. Besides the gain in speed, the proposal reduces power consumption for multiplication operands with 256, 512, 1024, and 2048 bits. The uniform treatment of partition hardware design enables the realization of a fault-tolerant hardware.

引用

页码：2122 / 2133

页数：12

共 24 条

[1] Parallel High-Radix Montgomery Multipliers [J].

Amberg, Philip ;

Pinckney, Nathaniel ;

Harris, David Money .

2008 42ND ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS AND COMPUTERS, VOLS 1-4, 2008, :772-776

[2]

[Anonymous], 2009, NIST STAND FIPS PUB, V74

[3]

[Anonymous], THESIS OREGON STATE

[4]

Barrett P., 1984, THESIS OXFORD U OXFO

[5] Automatic Generation of Modular Multipliers for FPGA Applications [J].

Beuchat, Jean-Luc ;

Muller, Jean-Michel .

IEEE TRANSACTIONS ON COMPUTERS, 2008, 57 (12) :1600-1613

[6] Power compiler: A gate-level power optimization and synthesis system [J].

Chen, B ;

Nedelchev, I .

INTERNATIONAL CONFERENCE ON COMPUTER DESIGN - VLSI IN COMPUTERS AND PROCESSORS, PROCEEDINGS, 1997, :74-79

[7]

Cormen TH., 2009, Introduction to Algorithms, V3

[8] NEW DIRECTIONS IN CRYPTOGRAPHY [J].

DIFFIE, W ;

HELLMAN, ME .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1976, 22 (06) :644-654

[9] A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS [J].

ELGAMAL, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) :469-472

[10]

Freedman David A., 2005, Statistical Models: Theory and Practice, DOI [10.1017/CBO9781139165495, DOI 10.1017/CBO9781139165495]

← 1 2 3 →