【手続補正書】
【提出日】平成19年1月29日(2007.1.29)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
非対称ないくつかの暗号鍵を生成するためのシステムであって、該いくつかの暗号鍵は、ｍ個の秘密値Ｑ1，Ｑ2，…Ｑmとｍ個の公開値Ｇ1，Ｇ2，…Ｇm（ｍは１以上）とを含んでおり、
プロセッサと、
前記プロセッサに接続されたメモリユニットであって、実行されると、前記プロセッサに以下の動作をさせる命令の集合を記憶しているものであるメモリユニットと、ここで、該動作は、
１より大きい整数である機密保護パラメータｋを選択することと、
ｎが、少なくとも２つの素因数、例えばｐ1およびｐ2がｐ1≡３ｍｏｄ４（４を法にして３）およびｐ2≡３ｍｏｄ４であるような少なくとも２つの素因数ｐ1，ｐ2，…ｐfの積に等しい公開値となるように、モジュロｎを決定することと、
ｍ個の基数ｇ1，ｇ2，…ｇmを選択することと、ここで、各基数ｇi（ｉ＝１，…，ｍ）は、１より大きい整数であり、モジュロｎの整数環の非平方剰余であり、前記基数の１つに関してｐ2とｐ1とは相補的であり、
Ｇi≡ｇi2ｍｏｄ  ｎである前記公開値Ｇiを、ｉ＝１からｉ＝ｍまで計算することと、
方程式Ｇi・Ｑiv≡１ｍｏｄ  ｎまたは方程式Ｇi≡Ｑivｍｏｄ  ｎ（ここで、公開指数ｖはｖ＝２kである）のいずれかを解くことによって、ｉ＝１からｉ＝ｍまでについての秘密値Ｑiを計算することと
を含んでなるものである、システム。
【請求項２】
３ｍｏｄ４に合同のｅ≧０である前記モジュロｎの素因数の数（ｆ−ｅ）が２より大きいものであり、３ｍｏｄ４に合同の２≦ｊ≦ｍについてのこれらの素因数ｐj+1が、
前記素因数ｐ1，ｐ2，…ｐjに関するｇjのＰｒｏｆｉｌｅj（ｇj）を計算することと、
プロファイル（Ｐｒｏｆｉｌｅj（ｇj））が平坦である場合には、ｐj+1がｇjに関してｐ1に相補的となるように因数ｐj+1を選択し、さもなければ、ｊ−１個の基数ｇ1，ｇ2，…ｇj-1およびそのすべての乗法の組み合わせの中で、Ｐｒｏｆｉｌｅj（ｇ）＝Ｐｒｏｆｉｌｅj（ｇj）となるようにｇという数を選択し、Ｐｒｏｆｉｌｅj+1（ｇj）≠Ｐｒｏｆｉｌｅj+1（ｇ）となるようにｐj+1を選択することと
によって反復的に決定されるものであり、ここで、ｆ−ｅ≦ｍのときに、ｆ−ｅ≦ｉ≦ｍであってそれのプロファイルであるＰｒｏｆｉｌｅj（ｇj）が平坦であるように、前記基数ｇiのすべてに関してｐf-eがｐ1と相補的になるように、３ｍｏｄ４に合同の最後の素因数ｐf-eは選択されるものである、請求項１に記載のシステム。
【請求項３】
１ｍｏｄ４（４を法にして１）に合同の、前記モジュロｎの素因数の数ｅが少なくとも１に等しいものであり、
ｐについてｇ1からｇmまでの基数ｇiのルジャンドル記号が＋１に等しくなるように、候補素因数ｐを選択することと、
ｐ−１が２t+1によって除算可能ではなく２tによって除算可能となるように、整数ｔを計算することと、
ｓ＝（ｐ−１＋２t）／２t+1となるように整数ｓを計算することと、
ｈがモジュロｐの整数環についての非平方剰余であり、
ｂ≡ｈp-1/2tｍｏｄ  ｐ
となる整数ｂを計算することと、
ｉ＝１からｍまでについてｍ個の整数ｒi≡ｇi2sｍｏｄ  ｐを計算することと、
整数ｕをｕ＝０に初期化することと、
ｉが１に初期化されているときには、以下の手順、すなわち、
整数ｗをｗ＝０に初期化することと、
ｒi＝±ｇiであって、ｉ＜ｍであれば、ｉの値を増加し、ｉの新たな値について手順をｉ＜ｍとなるまで続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れ、
ｒi≠±ｇiであれば、
整数ｊｊを１に初期化することと、
ｉｉが１に初期化されているときには、以下の手順、すなわち、
ｘ≡ｗ2／ｇi２ｍｏｄ  ｐとなるｘを計算することと、
ｙ≡［ｘ2］(t-ii-1)を計算することと、
ｙ＝＋１であれば、そのときの値ｉｉで前記手順を終了し、
ｙ＝−１であれば、ｊｊ＝２iiとなる値ｊｊを割当て、古い値にｂjjモジュロｐを乗算したものに等しい新たな値をｗに割当て、
ｉｉ＜ｔ−２については、前記ｉｉの値を増加し、新たな反復を続行し、
ｉｉ＝ｔ−２については、ｊｊ＝２t-uまで前記ｕの値を更新し、
ｔ−ｕ＜ｋであれば、モジュロｎの因数としての候補素因数ｐを拒絶し、
ｔ−ｕ＞ｋであって、ｉ＜ｍであれば、前記ｉの値を増加し、値ｉの新たな値について一連の手順を続行し、ｉ＝ｍであれば、候補素因数ｐを前記モジュロｎの因数として受け入れることと
を反復的に実行することによって各素因数が決定されるものである、請求項１に記載のシステム。
【請求項４】
ｍ個の秘密値Ｑ1，Ｑ2，…Ｑmのｆ．ｍ個の秘密構成要素Ｑi,jを計算するために、各組（ｉ，ｊ）について以下の手順、すなわち、
ｐjが３ｍｏｄ４に合同の場合には、１に等しい整数ｔを決定し、ｐjが１ｍｏｄ４に合同の場合には、請求項３に従うｔについて得られた値に整数ｔを決定することと、
ｐjが３ｍｏｄ４に合同の場合には、０に等しい整数ｕを決定し、ｐjが１ｍｏｄ４に合同の場合には、請求項３に従うｔについて得られた値に整数ｕを決定することと、
ｓ＝（ｐ−１＋２t）／２t+1である、整数ｚ≡Ｇisｍｏｄ  ｐjを計算することと、
ｕ＝０であれば、ｚｚがｚに等しいか、または、ｚｚが単位の２ii-t２ii番目の原始根のそれぞれによってｚの積（ｍｏｄ ｐj）に等しくなり、ｉｉが１からｍｉｎ（ｋ，ｔ）の範囲となるようにすべての数ｚｚを考慮し、ｕ＞０であれば、ｚｚが、単位の２k２k番目の根のそれぞれによってｚａの（ｍｏｄ ｐj）に等しくなるように、すべての数ｚｚを考慮することと、ここで、ｚａは、請求項３に従うｗについて得られた値であり、
そのようなそれぞれの数ｚｚについて、ｉの値について前記方程式Ｇi＝Ｑivｍｏｄ  ｎを用いた場合には、Ｑi,jがｚｚに等しいことを考慮して前記構成要素Ｑi,jについての値を得て、ｉの値についてＧi．Ｑiv≡１ｍｏｄ ｎを使用する場合には、ｚｚのモジュロｐjのｚｚの逆数に等しいことを考慮して前記構成要素Ｑi,jについての値を得ることと
を実行するものである、請求項３に記載のシステム。
【請求項５】
非対称ないくつかの暗号鍵を生成するための命令を記憶しているコンピュータ読み取り可能な記録媒体であって、該いくつかの暗号鍵は、ｍ個の秘密値Ｑ1，Ｑ2，…Ｑmとｍ個の公開値Ｇ1，Ｇ2，…Ｇm（ｍは１以上）とを含んでおり、前記媒体は、プロセッサに対して、
１より大きい整数である機密保護パラメータｋを選択することと、
ｎが、少なくとも２つの素因数ｐ1およびｐ2がｐ1≡３ｍｏｄ４およびｐ2≡３ｍｏｄ４であるような少なくとも２つの素因数ｐ1，ｐ2，…ｐfの積に等しい公開値となるように、モジュロｎを決定することと、
いくつかの基数ｇ1，ｇ2，…ｇmとなるｍを選択することと、ここで、各基数ｇi（ｉ＝１，…，ｍ）は、１より大きい整数であり、モジュロｎの整数環の非平方剰余であり、前記基数の１つに関してｐ2とｐ1とは相補的であり、
Ｇi≡ｇi2ｍｏｄ  ｎである前記公開値Ｇiを、ｉ＝１からｉ＝ｍまで計算することと、
方程式Ｇi・Ｑiv≡１ｍｏｄ  ｎまたは方程式Ｇi≡Ｑivｍｏｄ  ｎ（ここで、公開指数ｖはｖ＝２kである）のいずれかを解くことによって、ｉ＝１からｉ＝ｍまでについての秘密値Ｑiを計算することと
を実行させるものである、コンピュータ読み取り可能な記録媒体。
【請求項６】
３ｍｏｄ４に合同のｅ≧０である前記モジュロｎの素因数の数（ｆ−ｅ）が２より大きいものであり、３ｍｏｄ４に合同の２≦ｊ≦ｍについてのこれらの素因数ｐj+1が、
前記素因数ｐ1，ｐ2，…ｐjに関するｇjのＰｒｏｆｉｌｅj（ｇj）を計算することと、
プロファイル（Ｐｒｏｆｉｌｅj（ｇj））が平坦である場合には、ｐj+1がｇjに関してｐ1に相補的となるように因数ｐj+1を選択し、さもなければ、ｊ−１個の基数ｇ1，ｇ2，…ｇj-1およびそのすべての乗法の組み合わせの中で、Ｐｒｏｆｉｌｅj（ｇ）＝Ｐｒｏｆｉｌｅj（ｇj）となるようにｇという数を選択し、Ｐｒｏｆｉｌｅj+1（ｇj）≠Ｐｒｏｆｉｌｅj+1（ｇ）となるようにｐj+1を選択することと
によって反復的に決定されるものであり、ここで、ｆ−ｅ≦ｍのときに、ｆ−ｅ≦ｉ≦ｍであってそれのプロファイルであるＰｒｏｆｉｌｅj（ｇj）が平坦であるように、前記基数ｇiのすべてに関してｐf-eがｐ1と相補的になるように、３ｍｏｄ４に合同の最後の素因数ｐf-eは選択されるものである、請求項５に記載のコンピュータ読み取り可能な記録媒体。
【請求項７】
１ｍｏｄ４に合同であり、前記モジュロｎの素因数の数ｅが少なくとも１に等しいものであり、
ｐについてｇ1からｇmまでの基数ｇiのルジャンドル記号が＋１に等しくなるように、候補素因数ｐを選択することと、
ｐ−１が２t+1によって除算可能ではなく２tによって除算可能であるように、整数ｔを計算することと、
ｓ＝（ｐ−１＋２t）／２t+1となるように整数ｓを計算することと、
ｈがモジュロｐの整数環についての非平方剰余であり、
ｂ≡ｈp-1/2tｍｏｄ  ｐ
となる整数ｂを計算することと、
ｉ＝１からｍまでについてｍ個の整数ｒi≡ｇi2sｍｏｄ  ｐを計算することと、
整数ｕをｕ＝０に初期化することと、
ｉが１に初期化されているときには、以下の手順、すなわち、
整数ｗをｗ＝０に初期化することと、
ｒi＝±ｇiであって、ｉ＜ｍであれば、ｉの値を増加し、ｉの新たな値について手順をｉ＜ｍとなるまで続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れ、
ｒi≠±ｇiであれば、
整数ｊｊを１に初期化することと、
ｉｉが１に初期化されているときには、以下の手順、すなわち、
ｘ≡ｗ2／ｇi２ｍｏｄ  ｐとなるｘを計算することと、
ｙ≡［ｘ2］(t-ii-1)を計算することと、
ｙ＝＋１であれば、そのときの値ｉｉで前記手順を終了し、
ｙ＝−１であれば、ｊｊ＝２iiとなる値ｊｊを割当て、古い値にｂjjモジュロｐを乗算したものに等しい新たな値をｗに割当て、
ｉｉ＜ｔ−２については、前記ｉｉの値を増加し、新たな反復を続行し、
ｉｉ＝ｔ−２については、ｊｊ＝２t-uまで前記ｕの値を更新し、
ｔ−ｕ＜ｋであれば、前記モジュロｎの因数としての前記候補素因数ｐを拒絶し、
ｔ−ｕ＞ｋであって、ｉ＜ｍであれば、前記ｉの値を増加し、値ｉの新たな値について一連の手順をｉ＜ｍとなるまで続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れること
を反復的に実行することによって各素因数が決定されるものである、請求項５に記載のコンピュータ読み取り可能な記録媒体。
【請求項８】
秘密値Ｑ1，Ｑ2，…Ｑmのｆ．ｍ個の秘密構成要素Ｑi,jを計算するために、各組（ｉ，ｊ）について以下の手順、すなわち、
ｐjが３ｍｏｄ４に合同の場合には、１に等しい整数ｔを決定し、ｐjが１ｍｏｄ４に合同の場合には、請求項７に従うｔについて得られた値に整数ｔを決定することと、
ｐjが３ｍｏｄ４に合同の場合には、０に等しい整数ｕを決定し、ｐjが１ｍｏｄ４に合同の場合には、請求項７に従うｔについて得られた値に整数ｕを決定することと、
ｓ＝（ｐ−１＋２t）／２t+1である、整数ｚ≡Ｇisｍｏｄ  ｐjを計算することと、
ｕ＝０であれば、ｚｚがｚに等しいか、または、ｚｚが単位の２ii-t２ii番目の原始根のそれぞれによってｚの積（ｍｏｄ ｐj）に等しくなり、ｉｉが１からｍｉｎ（ｋ，ｔ）の範囲となるようにすべての数ｚｚを考慮し、ｕ＞０であれば、ｚｚが、単位の２k２k番目の根のそれぞれによってｚａの（ｍｏｄ ｐj）に等しくなるように、すべての数ｚｚを考慮することと、ここで、ｚａは、請求項７に従うｗについて得られた値であり、
そのようなそれぞれの数ｚｚについて、ｉの値について前記方程式Ｇi＝Ｑivｍｏｄ  ｎを用いた場合には、Ｑi,jがｚｚに等しいことを考慮して前記構成要素Ｑi,jについての値を得て、ｉの値についてＧi．Ｑiv≡１ｍｏｄ ｎを使用する場合には、ｚｚのモジュロｐｊのｚｚの逆数に等しいことを考慮して前記構成要素Ｑi,jについての値を得ることと
を実行するものである、請求項７に記載のコンピュータ読み取り可能な記録媒体。
【請求項９】
非対称ないくつかの暗号鍵を生成するための方法であって、該いくつかの暗号鍵は、ｍ個の秘密値Ｑ1，Ｑ2，…Ｑmとｍ個の公開値Ｇ1，Ｇ2，…Ｇm（ｍは１以上）とを含んでおり、プロセッサに対して、
１より大きい整数である機密保護パラメータｋを選択することと、
ｎが、少なくとも２つの素因数ｐ1およびｐ2がｐ1≡３ｍｏｄ４（４を法にして３）およびｐ2≡３ｍｏｄ４であるような少なくとも２つの素因数ｐ1，ｐ2，…ｐfの積に等しい公開値となるように、モジュロｎを決定することと、
いくつかの基数ｇ1，ｇ2，…ｇmとなるｍを選択することと、ここで、各基数ｇi（ｉ＝１，…，ｍ）は、１より大きい整数であり、モジュロｎの整数環の非平方剰余であり、前記基数の１つに関してｐ2とｐ1とは相補的であり、
Ｇi≡ｇi2ｍｏｄ  ｎである前記公開値Ｇiを、ｉ＝１からｉ＝ｍまで計算することと、
方程式Ｇi・Ｑiv≡１ｍｏｄ  ｎまたは方程式Ｇi≡Ｑivｍｏｄ  ｎ（ここで、公開指数ｖはｖ＝２kである）のいずれかを解くことによって、ｉ＝１からｉ＝ｍまでについての秘密値Ｑiを計算することと
を実行させるものである方法。
【請求項１０】
３ｍｏｄ４に合同であり、ｅ≧０である前記モジュロｎの素因数の数（ｆ−ｅ）が２より大きいものであり、３ｍｏｄ４に合同であり、２≦ｊ≦ｍについてのこれらの素因数ｐj+1が、
前記素因数ｐ1，ｐ2，…ｐjに関するｇjのＰｒｏｆｉｌｅj（ｇj）を計算することと、
プロファイル（Ｐｒｏｆｉｌｅj（ｇj））が平坦である場合には、ｐj+1がｇjに関してｐ1に相補的となるように因数ｐj+1を選択し、さもなければ、ｊ−１個の基数ｇ1，ｇ2，…ｇj-1およびそのすべての乗法の組み合わせの中で、Ｐｒｏｆｉｌｅj（ｇ）＝Ｐｒｏｆｉｌｅj（ｇj）となるようにｇという数を選択し、Ｐｒｏｆｉｌｅj+1（ｇj）≠Ｐｒｏｆｉｌｅj+1（ｇ）となるようにｐj+1を選択することと
によって反復的に決定されるものであり、ここで、ｆ−ｅ≦ｍのときに、ｆ−ｅ≦ｉ≦ｍであってそれのプロファイルであるＰｒｏｆｉｌｅj（ｇj）が平坦であるように、前記基数ｇiのすべてに関してｐf-eがｐ1と相補的になるように、３ｍｏｄ４に合同の最後の素因数ｐf-eは選択されるものである、請求項９に記載の方法。
【請求項１１】
１ｍｏｄ４（４を法にして１）に合同であり、前記モジュロｎの素因数である数ｅが少なくとも１に等しいものであり、
ｐについてｇ1からｇmまでの基数ｇiのルジャンドル記号が＋１に等しくなるように、候補素因数ｐを選択することと、
ｐ−１が２t+1によって除算可能ではなく２tによって除算可能であるように、整数ｔを計算することと、
ｓ＝（ｐ−１＋２t）／２t+1となるように整数ｓを計算することと、
ｈがモジュロｐの整数環についての非平方剰余であり、
ｂ≡ｈp-1/2tｍｏｄ  ｐ
となる整数ｂを計算することと、
ｉ＝１からｍまでについて整数ｒi≡ｇi2sｍｏｄ  ｐとなるｍを計算することと、
整数ｕをｕ＝０に初期化することと、
ｉが１に初期化されているときには、以下の手順、すなわち、
整数ｗをｗ＝０に初期化することと、
ｒi＝±ｇiであって、ｉ＜ｍであれば、ｉの値を増加し、ｉの新たな値について手順をｉ＜ｍとなるまで続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れ、
ｒi≠±ｇiである場合には、
整数ｊｊを１に初期化することと、
ｉｉが１に初期化されているときには、以下の手順、すなわち、
ｘ≡ｗ2／ｇi２ｍｏｄ  ｐとなるｘを計算することと、
ｙ≡［ｘ2］(t-ii-1)を計算することと、
ｙ＝＋１であれば、そのときの値ｉｉで前記手順を終了し、
ｙ＝−１であれば、ｊｊ＝２iiとなる値ｊｊを割当て、古い値にｂjjモジュロｐを乗算したものに等しい新たな値をｗに割当て、
ｉｉ＜ｔ−２については、前記ｉｉの値を増加し、新たな反復を続行し、
ｉｉ＝ｔ−２については、ｊｊ＝２t-uまで前記ｕの値を更新し、
ｔ−ｕ＜ｋであれば、前記モジュロｎの因数としての前記候補素因数ｐを拒絶し、
ｔ−ｕ＞ｋであって、ｉ＜ｍであれば、前記ｉの値を増加し、値ｉの新たな値について一連の手順をｉ＜ｍとなるまで続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れること
を反復的に実行することによって各素因数が決定されるものである、請求項９に記載の方法。
【請求項１２】
秘密値Ｑ1，Ｑ2，…Ｑmのｆ．ｍ個の秘密構成要素Ｑi,jを計算するために、各組（ｉ，ｊ）について以下の手順、すなわち、
ｐjが３ｍｏｄ４に合同であれば、１に等しい整数ｔを決定し、ｐjが１ｍｏｄ４に合同であれば、請求項１１に従うｔについて得られた値に整数ｔを決定することと、
ｐjが３ｍｏｄ４に合同であれば、０に等しい整数ｕを決定し、ｐjが１ｍｏｄ４に合同であれば、請求項１１に従うｔについて得られた値に整数ｕを決定することと、
ｓ＝（ｐ−１＋２t）／２t+1である、整数ｚ≡Ｇisｍｏｄ  ｐjを計算することと、
ｕ＝０であれば、ｚｚがｚに等しいか、または、ｚｚが単位の２ii-t２ii番目の原始根のそれぞれによってｚの積（ｍｏｄ ｐj）に等しくなり、ｉｉが１からｍｉｎ（ｋ，ｔ）の範囲となるようにすべての数ｚｚを考慮し、ｕ＞０であれば、ｚｚが、単位の２k２k番目の根のそれぞれによってｚａの（ｍｏｄ ｐj）に等しくなるように、すべての数ｚｚを考慮することと、ここで、ｚａは、請求項１１に従うｗについて得られた値であり、
そのようなそれぞれの数ｚｚについて、ｉの値について前記方程式Ｇi＝Ｑivｍｏｄ  ｎを用いた場合には、Ｑi,jがｚｚに等しいことを考慮して前記構成要素Ｑi,jについての値を得て、ｉの値についてＧi．Ｑiv≡１ｍｏｄ ｎを使用する場合には、ｚｚのモジュロｐｊのｚｚの逆数に等しいことを考慮して前記構成要素Ｑi,jについての値を得ることと
を実行するものである、請求項１１に記載の方法。