新しい乗算剰余算の高速化法とべき乗剰余形暗号への応用

林 彬  

誌名
電子情報通信学会論文誌 A   Vol.J81-A   No.10   pp.1372-1376
発行日: 1998/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: 情報セキュリティ基礎
キーワード: 
乗算剰余算,  べき乗剰余算,  公開鍵暗号,  RSA暗号,  エルガマル暗号,  

本文: PDF(323.4KB)>>
論文を購入




あらまし: 
RSA暗号,エルガマル暗号などべき乗剰余形暗号の本格的実用化のためには,暗号化と復号の一層の高速化が望まれる.本論文は,べき乗剰余算を高速化するための新しい算法を提案するものである.提案法はべき乗剰余の計算過程において,平方・乗算の法nにおける剰余を,nとは異なる法に関する剰余から構成しようとする考えに基づいている.詳しくは次の2点に基づく.(1)法n+1に関する剰余とn+2に関する剰余とから,nに関する剰余を構成できる.(2)nが素数であるか素因数分解が困難な合成数の場合でも,n+1,n+2は分解が容易である場合が多く,従ってこれらを法とする剰余算には中国剰余定理が利用できる.提案法にビット計算量を見積もり,並列計算を仮定して,従来の方法に比べ計算量が少ないことを明らかにする.特にn+1,n+2がほぼ均等にK個に分解する場合には,計算量は漸近的に1/Kのように減少する.提案法は,べき乗剰余算を必要とする暗号のみならず,類似の計算を伴う信号処理の高速化に役立つであろう.