素因数分解問題に基づく公開鍵暗号系

概要

論文の詳細を見る
素因数分解問題に基づく落とし戸一方向関数を利用した公開鍵暗号系の具体的な実現方法を提案する.本方法では演算量が極めて少なくなる.また,平文の範囲を拡張することにより,任意の暗号文0≤w≤nに対応する平文が存在し,ディジタル署名が可能となる.系の構成は,次のようになる.十分に大きな素数p,qから成るn=pqを法とする有限環上で,整数a,bを係数,wを暗号文,0≤x,y,z≤Rを平文とする暗号化式w=x+ay+bz(mod n)を構築する.ここで,ο(p)=ο(q^2),a=e^<-1>c (mod n), b=e^<-1>d (mod n), c=c_1k_1q+c_2k_2p (mod n), d=d_1k_1q+d_2k_2p (mod n), e=e_1k_1q+e_2k_2p (mod n), 1=k_1q+k_2p (mod n),R(e_1+c_1+d_1)<p, R<d_1,ο(c_1)=ο(e_1)=ο(q^<0.9>), ο(d_1)=ο(q), d_1c_2-c_1d_2 (mod q) = 0「係数a,bが与えられたとき,nの素因数分解に必要な計算量と,本暗号を解読する困難さとは等価である」ことを示すことができる.
1995-10-15