A fast modular exponentiation for RSA on systolic arrays

被引：0
作者：
Han, YF
Mitchell, CJ
Gollmann, D
机构：
[1] Dept. of Computer Science, Royal Holloway, University of London, Egham
来源：
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1997年 / 63卷 / 3-4期
基金：
英国工程与自然科学研究理事会;
关键词：
cryptography; RSA; modular exponentiation; systolic arrays;
D O I：
10.1080/00207169708804562
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
This paper presents two systolic algorithms for modular exponentiations based on a k-SR representation. In a systolic k-SR scheme, throughput is one modular exponentiation of a message block having n digits in every clock cycle, with a latency of nearly 5n/4 cycles to output the final result. The speedup for a group of messages having l message blocks is around (5/6l + 2/3n), compared to a single processor or processing element for modular multiplications. The scheme saves nearly n/4 processing elements and around n/4 modular multiplications, compared with the scheme in [23].
引用
收藏
页码：215 / 226
页数：12
相关论文
共 24 条
[11]   MINIMUM WEIGHT MODIFIED SIGNED-DIGIT REPRESENTATIONS AND FAST EXPONENTIATION [J].
JEDWAB, J ;
MITCHELL, CJ .
ELECTRONICS LETTERS, 1989, 25 (17) :1171-1172
[12]  
Knuth Donald, 1981, ART COMPUTER PROGRAM, V2
[13]  
Koc C. K., 1991, Journal of VLSI Signal Processing, V3, P215, DOI 10.1007/BF00925832
[14]  
KUNG HT, 1978, P SIAM SPARSE MATRIX, P256
[15]   EFFICIENCY OF SS(I) SQUARE-AND-MULTIPLY EXPONENTIATION ALGORITHMS [J].
LAM, KY ;
HUI, LCK .
ELECTRONICS LETTERS, 1994, 30 (25) :2115-2116
[16]  
MITCHELL HY, UNPUB MINIMAL K SR R
[17]  
RIVEST RL, 1978, COMMUN ACM, V21, P120, DOI [10.1145/359340.359342, 10.1145/357980.358017]
[18]  
Schneier B, APPL CRYPTOGRAPHY PR, V20th
[19]  
Shand M., 1991, Computer Architecture News, V19, P106, DOI 10.1145/121956.121968
[20]   SYSTOLIC MODULAR MULTIPLICATION [J].
WALTER, CD .
IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (03) :376-378
123