(57)【要約】 【構成】  n個の乱数の列{ｒi}が平文ｍに対し、ｍ＝（Σｉ＝１nｒi） mod 2を充たすように、乱数発生器により乱数の列{ｒi}を発生させる。乱数の列{ｒi}とn個の正整数からなる公開鍵{ａi}とにより、暗号文ＣをＣ＝Σｉ＝１nａi・ｒiにより求め、平文ｍを陽に用いることなく暗号文Ｃを生成する。【効果】  平文ｍを陽に用いずに暗号文Ｃを生成でき、かつ暗号化を高速で行うことができる。【選択図】    図１
2013152389.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵を記憶するメモリと乱数発生器とを備えて、
n個の乱数の列{ｒi}が平文ｍに対し、ｍ＝（Σｉ＝１nｒi） mod 2  または
ｍ＝（Σｉ＝１nｂi・ｒi） mod Ｚ（ここに{ｂi}はn個の非負整数からなる公開鍵、Ｚは正整数）を充たすように、前記乱数発生器により前記乱数の列{ｒi}を発生させ、
さらに前記乱数の列{ｒi}とn個の正整数からなる公開鍵{ａi}とにより、暗号文Ｃを  Ｃ＝Σｉ＝１nａi・ｒiにより求める演算器とを備え、
平文ｍを陽に用いることなく暗号文Ｃを生成するように構成されている暗号化装置。
【請求項２】
公開鍵を記憶するメモリと乱数発生器とを備えて、
n個の乱数の列{ｒi}が平文ｍに対し、ｍ＝（Σｉ＝１nｒi） mod 2  または
ｍ＝（Σｉ＝１nｂi・ｒi） mod Ｚ（ここに{ｂi}はn個の非負整数からなる公開鍵、Ｚは正整数）を充たすように、前記乱数発生器により前記乱数の列{ｒi}を発生させるステップと、
さらに前記乱数の列{ｒi}とn個の正整数からなる公開鍵{ａi}とにより、演算器により、暗号文Ｃを  Ｃ＝Σｉ＝１nａi・ｒiにより求めるステップ、とを実行することにより、
平文ｍを陽に用いることなく暗号文Ｃを生成する暗号化方法。
【請求項３】
コンピュータからなる暗号化装置に、
n個の乱数の列{ｒi}が平文ｍに対し、ｍ＝（Σｉ＝１nｒi） mod 2  または
ｍ＝（Σｉ＝１nｂi・ｒi） mod Ｚ（ここに{ｂi}はn個の非負整数からなる公開鍵、Ｚは正整数）を充たすように、前記乱数の列{ｒi}を発生させるステップと、
さらに前記乱数の列{ｒi}とn個の正整数からなる公開鍵{ａi}とにより、暗号文Ｃを  Ｃ＝Σｉ＝１nａi・ｒiにより求めるステップ、とを実行させることにより、
平文ｍを陽に用いることなく暗号文Ｃを生成する暗号化プログラム。
【請求項４】
請求項１の暗号化装置により暗号化された暗号文を復号するための装置であって、秘密鍵を記憶するメモリと、暗号文の受信を行う通信インターフェースと、
受信した暗号文Ｃに対し秘密の正整数Ｐと秘密の正整数ｅ−１とにより、Ｍ＝ｅ−１・Ｃ mod Ｐにより中間平文Ｍを求める乗算器と剰余演算器と、前記中間平文Ｍの最下位ビットを平文ｍとして抽出する、もしくはＭ mod Ｚ（ここにＺは２以上の正整数）を平文ｍとして求める剰余演算器とを備えている、復号装置。
【請求項５】
n個の秘密の正整数{ｓi}と、秘密の正整数Ｐと、秘密の正整数e及びｅ−１を発生させる秘密鍵生成手段と、
前記n個の秘密の正整数{ｓi}をａi＝ｅ・ｓi mod Ｐ（i＝1〜n）により公開鍵{ａi}に変換する剰余演算器とを備え、
秘密鍵｛ｓi｝を選択する際の自由度をビット単位でＩs、公開鍵｛ａi｝の総ビット数をＩpとした際に、nを大きくすると  Ｉs／Ｉpが１に漸近するように構成されていることを特徴とする、鍵生成装置。  
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は公開鍵を用いた暗号化装置等に関し、特に平文が陽に用いられない暗号化装置等に関する。  
【背景技術】
【０００２】
発明者らは、超増加数列等のトラップドアを備えないナップザック暗号を提案した（非特許文献１  "A Probablistic Knapsack Public-Key Cryptosystem" The 33rd Symposium on Information Theory and its Applications (SITA2010) 予稿集）。この暗号では、正奇数ｓとn-1個の一様な偶数の乱数｛ｔi｝、正の素数Ｐ及び正整数ｅを秘密鍵とし、正整数ａとn-1個の数の列｛bi｝を公開鍵とする。そして公開鍵は  ａ＝ｅ・ｓ mod Ｐ，
ｂi＝ｅ・ｔi mod Ｐ  により秘密鍵から生成されている。暗号化は平文ｍに対し、
Ｃ＝ａｍ＋Σｉ＝２nｂi・ｒi
により行われ、ここにｒiは各１ビットのn-1個の乱数である。中間平文Ｍを
Ｍ＝ｅ−１・Ｃ mod Ｐにより求め、さらに中間平文の最下位ビットを抽出することにより、平文ｍが復号される。
【０００３】
この暗号は超増加数列等のトラップドアを用いないが、暗号文Ｃを生成する際に平文ｍが陽に用いられ、この点から解読される可能性がないとは言えない。発明者はこの点を検討し、平文ｍを陽に用いずに暗号文Ｃを生成できる暗号を開発し、この発明に到った。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】"A Probablistic Knapsack Public-Key Cryptosystem" The 33rd Symposium on Information Theory and its Applications (SITA2010) 予稿集
【発明の概要】
【発明が解決しようとする課題】
【０００５】
この発明の課題は、平文ｍを陽に用いずに暗号文Ｃを生成でき、かつ暗号化を高速で行うことができる、新規な暗号化装置等を提供することにある。
【課題を解決するための手段】
【０００６】
この発明は、公開鍵を記憶するメモリと乱数発生器とを備えて、
n個の乱数の列{ｒi}が平文ｍに対し、ｍ＝（Σｉ＝１nｒi） mod 2  または
ｍ＝（Σｉ＝１nｂi・ｒi） mod Ｚ（ここに{ｂi}はn個の非負整数からなる公開鍵、Ｚは正整数）を充たすように、前記乱数発生器により前記乱数の列{ｒi}を発生させ、
さらに前記乱数の列{ｒi}とn個の正整数からなる公開鍵{ａi}とにより、暗号文Ｃを  Ｃ＝Σｉ＝１nａi・ｒiにより求める演算器とを備え、
平文ｍを陽に用いることなく暗号文Ｃを生成するように構成されている暗号化装置にある。
【０００７】
またこの発明は、公開鍵を記憶するメモリと乱数発生器とを備えて、
n個の乱数の列{ｒi}が平文ｍに対し、ｍ＝（Σｉ＝１nｒi） mod 2  または
ｍ＝（Σｉ＝１nｂi・ｒi） mod Ｚ（ここに{ｂi}はn個の非負整数からなる公開鍵、Ｚは正整数）を充たすように、前記乱数発生器により前記乱数の列{ｒi}を発生させるステップと、
さらに前記乱数の列{ｒi}とn個の正整数からなる公開鍵{ａi}とにより、演算器により、暗号文Ｃを  Ｃ＝Σｉ＝１nａi・ｒiにより求めるステップ、とを実行することにより、  平文ｍを陽に用いることなく暗号文Ｃを生成する暗号化方法にある。
【０００８】
またこの発明は、コンピュータからなる暗号化装置に、
n個の乱数の列{ｒi}が平文ｍに対し、ｍ＝（Σｉ＝１nｒi） mod 2  または
ｍ＝（Σｉ＝１nｂi・ｒi） mod Ｚ（ここに{ｂi}はn個の非負整数からなる公開鍵、Ｚは正整数）を充たすように、前記乱数の列{ｒi}を発生させるステップと、
さらに前記乱数の列{ｒi}とn個の正整数からなる公開鍵{ａi}とにより、暗号文Ｃを  Ｃ＝Σｉ＝１nａi・ｒiにより求めるステップ、とを実行させることにより、
平文ｍを陽に用いることなく暗号文Ｃを生成する暗号化プログラムにある。
【０００９】
この発明では、ｍ＝（Σｉ＝１nｒi） mod 2  またはｍ＝（Σｉ＝１nｂi・ｒi） mod Ｚを充たすように、乱数の列{ｒi}を発生させることと、演算によりＣ＝Σｉ＝１nａi・ｒiを求めることにより、暗号化ができる。そして暗号化の過程で平文ｍは陽に用いられないので安全性が高く、暗号化の手順が簡単なため高速で暗号化ができる。
【００１０】
この明細書において、暗号化装置に関する記載はそのまま暗号化方法、暗号化プログラム、及び復号装置、鍵生成装置にも当てはまり、暗号化方法等に関する記載は暗号化装置等にもそのまま当てはまる。
【００１１】
またこの発明は、請求項１の暗号化装置により暗号化された暗号文を復号するための装置であって、秘密鍵を記憶するメモリと、暗号文の受信を行う通信インターフェースと、
受信した暗号文Ｃに対し秘密の正整数Ｐと秘密の正整数ｅ−１とにより、Ｍ＝ｅ−１・Ｃ mod Ｐにより中間平文Ｍを求める乗算器と剰余演算器と、前記中間平文Ｍの最下位ビットを平文ｍとして抽出する、もしくはＭ mod Ｚ（ここにＺは２以上の正整数）を平文ｍとして求める剰余演算器とを備えている、復号装置にある。この発明の復号装置では簡単かつ高速で復号ができる。
【００１２】
この発明はまた、n個の秘密の正整数{ｓi}と、秘密の正整数Ｐと、秘密の正整数e及びｅ−１を発生させる秘密鍵生成手段と、
前記n個の秘密の正整数{ｓi}をａi＝ｅ・ｓi mod Ｐ（i＝1〜n）により公開鍵{ａi}に変換する剰余演算器とを備え、
秘密鍵｛ｓi｝を選択する際の自由度をビット単位でＩs、公開鍵｛ａi｝の総ビット数をＩpとした際に、nを大きくすると  Ｉs／Ｉpが１に漸近するように構成されていることを特徴とする、鍵生成装置にある。この発明では、秘密鍵｛ｓi｝に対し、超増加数列であること等の制約が無く、秘密鍵は一様乱数として定めることができる。このため秘密鍵｛ｓi｝を選択する際の自由度が広く、Ｉs／Ｉpを１に漸近させることができ、秘密鍵が露呈するおそれが少ない。
【図面の簡単な説明】
【００１３】
【図１】実施例の暗号通信装置のブロック図
【図２】実施例での暗号化アルゴリズムを示すフローチャート
【図３】実施例での復号アルゴリズムを示すフローチャート
【図４】実施例の暗号通信での鍵の構造と復号の正当性を示す図
【図５】変形例の暗号通信装置のブロック図
【図６】変形例での暗号化アルゴリズムを示すフローチャート
【図７】実施例の鍵生成装置のブロック図
【発明を実施するための形態】
【００１４】
以下に本発明を実施するための最適実施例を示す。この発明の範囲は、特許請求の範囲の記載に基づき、明細書の記載とこの分野での周知技術とを参酌し、当業者の理解に従って定められるべきである。
【実施例】
【００１５】
図１〜図６に実施例とその変形とを示し、変形例において実施例と同じ符号は同じものを表し、実施例に関する記載は特に断らない限り、変形例にもそのまま当てはまる。図１において、２は暗号通信装置で、暗号化装置４と復号装置６及び通信インターフェース８とから成る。公開鍵メモリ１０は、通信インターフェース８を介して、n個の数ａiから成る公開鍵｛ａi｝を受信して記憶し、乱数発生器１２は１ビットのn個の乱数列｛ｒi｝を発生する。
【００１６】
加算器１４は乱数ｒiを加算し、検査器１６は１ビットの平文ｍの入力を受け付け、乱数の和（Σｉ＝１nｒi） mod 2がｍと一致するか否かを検査する。検査器１６は
（Σｉ＝１nｒi） mod 2がｍと一致すると乱数列｛ｒi｝を演算器１８へ出力し、一致しないとその旨の信号を乱数発生器１２と加算器１４へ出力し、（Σｉ＝１nｒi） mod 2がｍと一致するまで乱数の発生と加算を繰り返させる。検査器１６の役割は、（Σｉ＝１nｒi） mod 2がｍと一致するように乱数列｛ｒi｝を発生させる点にあり、具体的な構成は任意である。例えばn-1個の乱数を発生させた際に例えば（Σｉ＝１n-1ｒi） mod 2を求めてｍと比較し、最後のｒnを
（Σｉ＝１nｒi） mod 2がｍと一致するように定めても良い。乱数発生器１２〜検査器１６での処理は、
ｍ＝（Σｉ＝１nｒi） mod 2                                    (1)
を充たすように、各１ビットの乱数列{ｒi｝を発生させることである。なお乱数riは複数ビットの乱数の最下位ビットを用いるとも考えることができ、riを複数ビットの乱数として発生させて、(1)式によりその最下位ビットのみを取り出すようにしても良い。
【００１７】
演算器１８は、n個の公開鍵｛ａi｝とn個の乱数の列｛ｒi｝との積和演算を行い、  
Ｃ＝Σｉ＝１nａi・ｒi                                        (2)
により、暗号文Ｃを発生させる。なお｛ｒi｝が１ビットの乱数の列である場合、積和演算ではなく単なる加算となる。複数ビットの暗号文を送信する場合、暗号文の各ビット毎に前記の平文１ビット相当の暗号文Ｃを発生させ、複数個の暗号文Ｃの列を出力する。生成した暗号文Ｃを通信インターフェース８を介し、通信相手の暗号通信装置２’へ送信する。
【００１８】
復号を説明し、秘密鍵のｅ−１とＰを暗号化に用いた公開鍵｛ａi｝に対応させて示す。鍵メモリ２０は秘密鍵ｅ−１とＰ及び公開鍵｛ａi｝もしくは、公開鍵｛ａi｝，｛ｂi｝及びＺを記憶し、公開鍵は通信インターフェース８を介して通信相手の暗号通信装置２'へ送信される。なお｛ｂi｝及びＺは図５，図６を参照して後で説明する。暗号文Ｃを暗号文メモリ２２に記憶し、乗算器２４で秘密鍵ｅ−１と乗算し、剰余演算器２６で素数Ｐに対する剰余
Ｍ＝ｅ−１・Ｃ mod Ｐ                                            (3)
を求め、その最下位ビット（Ｍ mod 2）を平文ｍとして出力する。剰余Ｍを中間平文と呼ぶ。
【００１９】
図２に暗号化のアルゴリズムを、図３に復号アルゴリズムを示す。図２のステップ１で１ビットの平文ｍを入力し、ステップ２で各１ビットの乱数の列{ｒi}を発生させ、ステップ３で（Σｉ＝１nｒi） mod 2がｍと一致するか否かを検査し、（Σｉ＝１nｒi） mod 2をｍと一致させる。ステップ４でＣ＝Σｉ＝１nａi・ｒiを求めて送信する。
【００２０】
図３の復号では、ステップ１１で暗号文Ｃを受信し、ステップ１２で(3)式に従い中間平文Ｍを求め、ステップ１３でその最下位ビットを平文ｍとして出力する。なお図４の変形例では、中間平文Ｍの２以上の正整数Ｚによる剰余  
ｍ＝Ｍ mod Ｚ                                                  (4)
を求めて出力し、この場合、平文ｍは｛0,1,…，Z-1｝のＺ通りの値を取ることができる。
【００２１】
図４に鍵の構造と復号の正当性とを示す。正整数Ｎを定め、正の奇数ｓi
（sｉ-1≦２Ｎ）を一様乱数として発生させる。
Ｐ＞Σｉ＝１nｓi＞Ｐ／２                                        (5)
を充たすように正の素数Ｐを生成し、
Ｐ＞ｅ＞Ｐ／２                                               (6)
を充たすＰと互いに素な正の整数ｅを発生させる。なおＰは素数であることが好ましいが素数に限るものではなく、Σｉ＝１nｓi＞Ｐ／２であることが好ましいがこれに限るものではない。乱数riを１ビットの数ではなく、０以上ｋ以下の整数とする場合、(5)式の代わりに、(5’)式を充たすようにすることが好ましい。
Ｐ＞ｋΣｉ＝１nｓi                                              (5’)
ｅはＰ未満でかつ１に比べて充分大きな正整数が好ましいので、(6)式を充たすように定めることが好ましいが、Ｐ／２以下でも良い。Ｎは例えばnビットよりもやや小さいｔビットオーダーの数である。秘密鍵｛ｓi｝により公開鍵｛ａi｝を
ａi＝ｅ・ｓi   mod Ｐ                                            (7)
により生成し、秘密鍵｛ｓi｝は暗号化にも復号にも陽に表れることはない。    
【００２２】
暗号化と復号の手順は図２，図３に示した通りで、Ｃ＝Σｉ＝１nａi・ｒiなので、
ｅ−１・Ｃ mod Ｐ＝（Σｉ＝１nｅ-1・ａi・ｒi） mod Ｐ＝（Σｉ＝１nｓi・ｒi） mod Ｐである。ここで  Ｐ＞Σｉ＝１nｓi＞Ｐ／２  なので、
（Σｉ＝１nｓi・ｒi） mod Ｐ＝Σｉ＝１nｓi・ｒi                            (8)
となる。ｓi（ｉ＝1〜n）は奇数なので、Σｉ＝１nｓi・ｒiの最下位ビットはΣｉ＝１nｒi＝ｍに等しい。
【００２３】
上記の公開鍵暗号は、暗号化に平文ｍを陽に用いず、ｍ＝（Σｉ＝１nｒi） mod 2のように、n個の乱数｛ｒi｝中に平文ｍを埋め込んでいる。同じ平文ｍに対応する暗号文Ｃは多数存在し、ｎと共に増加存在する。秘密鍵｛ｓi｝は一様乱数で、超増加数列であること等の制約を課してトラップドアを設ける必要がない。言い換えると秘密鍵｛ｓi｝を選択する自由度が高い。秘密鍵｛ｓi｝を選択する際の自由度をビット単位でＩs、公開鍵｛ａi｝の総ビット数をＩpとすると、
Ｉs＝n（[log２Ｎ]−１）                                    (9)
が成立し、例えばＮは２tオーダーの数で、ｔ≒ｎなので、nを充分大きくするとＮ>>ｎである。なお[log２Ｎ]はlog２Ｎを越えない最大の整数を表す。(5)式からＰはＮ・n程度の数であり、
Ｉp≒n（log２Ｐ）≒n（log２Ｎ＋log２n）                      (10)
が近似的に成立し、nが充分大きいとき、Ｎ>>nなのでＩs／Ｉpは１に収束する。このことは、秘密鍵を選択する自由度が高く、公開鍵から秘密鍵が露呈するおそれが少ないことを意味する。
【００２４】
ナップザック暗号への攻撃として低密度攻撃が知られている。ここに密度ｄは、
ｄ＝n／（log２maxａi）で表され、ｄ＜0.9408で低密度攻撃が成立する。(7)式から
maxａiはＰ未満の数で、
maxａi＜log２Ｐ≒log２Ｎ＋log２n                              (11)
が成立し、例えば
n＞log２Ｎ＋log２n                                           (12)
が成立するようにＮを定めると、密度ｄは１よりも大きくなる。
【００２５】
図５に、１ビットよりも長い平文ｍを送信できる暗号通信装置３を示し、図1と同じ符号は同じものを表し、図１〜図４の実施例に関する記載は、特に断らない限り、図５，図６の変形例にも当てはまる。公開鍵はn個の数｛ａi｝とn個の数｛ｂｉ｝及び正整数Ｚである。Ｚを1としたものが図１〜図４の実施例で、図５の変形例では平文ｍは０〜Z-1の値を取ることができ、Ｚ<<Ｐである。公開鍵ｂiを
ｂi＝ｓi mod Ｚ                                           (13)
により定める。
【００２６】
暗号化では演算器１５により（Σｉ＝１nｂi・ｒi） mod Ｚを求め、この値がｍと一致するか否かを検査器１６で検査し、一致しなければ各１ビットの乱数列｛ｒi｝を再生成し、一致すれば演算器１８で暗号文Ｃ＝Σｉ＝１nａi・ｒiを求めて送信する。
【００２７】
復号装置７では、暗号文Ｃを暗号文メモリ２２に記憶し、乗算器２４によりｅ−１を乗算し、剰余演算器２６により中間平文Ｍ＝ｅ−１・Ｃ mod Ｐを求め、剰余演算器２８によりＺを法とする剰余を求めて平文ｍとして出力する。
【００２８】
図６に暗号化のアルゴリズムを示し、ステップ１で平文ｍを入力し、ステップ２１，２２で  ｍ＝（Σｉ＝１nｂi・ｒi） mod Ｚを充たすように、n個の乱数の列｛ｒi｝を生成し、ステップ４で暗号文ＣをＣ＝Σｉ＝１nａi・ｒiにより求めて送信する。復号のアルゴリズムは図３に示してある。
【００２９】
図７に、鍵生成装置６０を示し、３２は素数発生器で前記の素数Ｐを発生し、３４は乱数発生器で前記の正の数ｅと前記のｎ個の正整数｛si｝とを発生する。３６は逆数演算器で  e-1・e=１ mod P により秘密の正の数e-1を発生する。３８は乗算器でn個の数{e・si}を乗算により求め、４０は剰余演算器で  ai＝e・si mod Pにより公開鍵{ai}を求める。なお｛bi｝を用いる場合、bi=si mod Ｚにより｛bi｝を発生させる。素数Ｐのビット数等に応じて、式(5)，(6)を充たすように、ｅと｛si｝とを発生させる。なお変形例のように、２よりも大きな法Ｚを用いる場合、Ｐと秘密鍵｛si｝との関係は(5)式ではなく、
Ｐ＞（Ｚ−１）Σｉ＝１nｓi  とすることが好ましい。秘密鍵｛ｓi｝は一様乱数とし、秘密鍵｛ｓi｝を選択する際の自由度をビット単位でＩs、公開鍵｛ａi｝の総ビット数をＩpとすると、
Ｉs＝n（[log２Ｎ]−１）                                    (9)
が成立し、例えばＮは２tオーダーの数で、ｔ≒ｎなので、nを充分大きくするとＮ>>ｎである。(5)式からＰはＮ・n程度の数であり、
Ｉp≒n（log２Ｐ）≒n（log２Ｎ＋log２n）                      (10)
が近似的に成立し、nが充分大きいとき、Ｎ>>nなのでＩs／Ｉpは１に収束する。
【符号の説明】
【００３０】
２，３        暗号通信装置
４，５        暗号化装置
６，７        復号装置
８            通信インターフェース
１０          公開鍵メモリ
１２          乱数発生器
１４          加算器
１５          演算器
１６          検査器
１８          演算器
２０          鍵メモリ
２２          暗号文メモリ
２４          乗算器
２６，２８    剰余演算器
３０          鍵生成装置
３２          素数発生器
３４          乱数発生器
３６          逆数演算器
３８          乗算器
４０          剰余演算器
【図１】
2013152389.tif 000003
【図２】
2013152389.tif 000004
【図３】
2013152389.tif 000005
【図４】
2013152389.tif 000006
【図５】
2013152389.tif 000007
【図６】
2013152389.tif 000008
【図７】
2013152389.tif 000009