ディオファンタスの一次不定方程式に基づく公開鍵暗号系

概要

論文の詳細を見る
公開鍵暗号系の実現化手法は,RSA法を初めとして,これまでに多数提案されているが,実用化されているものは極めて少ない.ビット長の大きい演算回数が多いため,計算量が膨大になり,暗号化・復号化に時間がかかり過ぎることが主要因である.本論文でデイオファンタスの一次不定方腿式に基づく公開鍵暗号系を提案する.本暗号系の暗号化・復号化では扱うビット長,演算量が小さくなる.その結果RSA法と比べて演算量がかなり小さくなる利点がある.また,ディジタル署名の実現も可能である.系の構成は,次のようになる.素数P_i(i=0,…,n),正整数係数k_iを用いてb_i=k_iP_0P_1…P_<I-1>(i=1,…,n)を生成し,b_1P_1+…+b_nP_n<Rなる素数RおよびRと互いに素な整数βを選び,a_i≡b_iβmodR(i=1,…,n)を生成する.この際,a_1P_1+…+a_nP_n<Rとなるように,k_i,β,Rを選定する.正整数a_iを係数,Cを与えられた整数,x_iを未知数とするデイオファンタスの一次不定方程式C=a_1x_1+…+a_nx_nを利用して,0&≦x_i<P_I(I=1,…,n)なるx_iを平文,Cを暗号文とする暗号系を構築する.復号化では,O&≦C<Rの範囲の任意のCに対しては,0&≦x_i<P_i(i=1,…,n-1),-(n-1)*o(P_n)<o(x_n)<n*o(P_n)の範囲に平文を拡張することにより,ディジタル署名が可能になる.
1990-12-15