(57)【要約】【課題】  公開鍵が短くかつ安全な公開鍵暗号システムを提供する。【解決手段】  整数環上の暗号文に第１の秘密の数の逆数を乗算し、かつ第２の秘密の数を法とする剰余を求めることにより、長さの異なる複数の数の和に変換し、この和を第３の秘密の数を法として剰余演算することにより、第１のデータブロックを抽出して復号し、上記の和から第１のデータブロックを除いて、第４の秘密の数を法とする剰余を求めることにより、第２のデータブロックを復号し、復号した第１のデータブロックと第２のデータブロックとから平文を求める。【選択図】    図５
2005141136.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵を用いて平文を暗号文に復号する暗号システムにおいて、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする、公開鍵暗号システム。
【請求項２】
公開鍵を用いて平文を暗号文に復号する暗号通信方法において、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする、暗号通信方法。
【請求項３】
公開鍵を用いた暗号文を平文に復号するための復号装置において、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする、復号装置。
【請求項４】
前記第４の秘密の因子として、複数の因子を用い、最初の因子から最後の因子まで、順次各因子を法とする剰余演算を１回目〜最後の剰余演算として行い、ここで２回目以降の剰余演算では、前回の剰余演算の剰余を演算対象とし、
最後の剰余演算により、前記第２のデータブロックの最初の部分を復号し、
最後の剰余演算で得られた剰余を、その前の剰余演算での剰余から除いて、前記第２のデータブロックの第２の部分を復号し、
前記２回目の剰余演算で得られた剰余を、１回目の剰余演算での剰余から除いて、前記第２のデータブロックの最後の部分を復号するようにしたことを特徴とする、請求項３の復号装置。
【請求項５】
暗号文を整数環上に構築し、
前記第１の秘密の因子は該整数環上の第１の秘密の数の逆数で、
第２の秘密の因子として整数環上の第２の秘密の数を用い、
前記第３の秘密の因子は整数環上の第３の秘密の数で、この数を法とする剰余演算により、第１のデータブロックを抽出し、
前記第４の秘密の因子は整数環上の第４の秘密の数で、この数を法とする剰余を求めることにより、第２のデータブロックを復号することを特徴とする、請求項３または４の復号装置。
【請求項６】
公開鍵を用いた暗号文を平文に復号するための復号プログラムにおいて、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換するための命令と、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号するための命令と、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号するための命令と、
復号した第１のデータブロックと第２のデータブロックとから平文を求めるための命令とを備えたことを特徴とする、復号プログラム。
【請求項７】
公開鍵を用いた暗号文を平文に復号する復号方法において、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする、復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、公開鍵暗号に関し、特に公開鍵を用いた暗号システムと暗号通信方法、並びに復号装置や復号プログラムと復号方法に関する。
【背景技術】
【０００２】
発明者らは、非特許文献１で、多次多変数の連立方程式の求解困難性を用いた公開鍵暗号システムを提案した。また非特許文献２では、ホームページ上の鍵リストから送信者がランダムに鍵を選択できる、積和型の暗号方式を提案した。特に、有限体の特長を生かすことにより、暗号化や復号に必要な演算時間を短縮し、かつリストのサイズを小さくできることを提案した。現在の代表的な公開鍵暗号は、巨大な整数の素因数分解困難性に根拠を置いたＲＳＡ暗号であるが、充分に安全な暗号とするため、公開鍵のサイズが２Ｋビット程度に達している。
【非特許文献１】有限体上の短い公開鍵を用いた暗号システムの構成(A Construction of Short Public Cryptosystem over Extension Field)  笠原,境,  Technical Report of IEICE,ISEC2002-16(2003-03)
【非特許文献２】公開鍵暗号の一手法とその応用  笠原  正雄,電子情報通信学会技術研究報告書,ISEC99-140(2000-03)
【発明の開示】
【発明が解決しようとする課題】
【０００３】
この発明の基本的課題は、新たな公開鍵暗号を提供することにある。
【課題を解決するための手段】
【０００４】
この発明は、公開鍵を用いて平文を暗号文に復号する暗号システムにおいて、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする。
【０００５】
この発明の暗号通信方法は、公開鍵を用いて平文を暗号文に復号する暗号通信方法において、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする。
【０００６】
この発明の復号装置は、公開鍵を用いた暗号文を平文に復号するための復号装置において、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする。
【０００７】
好ましくは、前記第４の秘密の因子として、複数の因子を用い、最初の因子から最後の因子まで、順次各因子を法とする剰余演算を１回目〜最後の剰余演算として行い、ここで２回目以降の剰余演算では、前回の剰余演算の剰余を演算対象とし、
最後の剰余演算により、前記第２のデータブロックの最初の部分を復号し、
最後の剰余演算で得られた剰余を、その前の剰余演算での剰余から除いて、前記第２のデータブロックの第２の部分を復号し、
前記２回目の剰余演算で得られた剰余を、１回目の剰余演算での剰余から除いて、前記第２のデータブロックの最後の部分を復号するようにしたことを特徴とする。
【０００８】
このようにすると第２のデータブロックの復号には、複数回の剰余演算が必要で、これらの法を推定するのは、１個の法を推定するより困難なため、安全性が向上する。
【０００９】
また好ましくは、暗号文を整数環上に構築し、
前記第１の秘密の因子は該整数環上の第１の秘密の数の逆数で、
第２の秘密の因子として整数環上の第２の秘密の数を用い、
前記第３の秘密の因子は整数環上の第３の秘密の数で、この数を法とする剰余演算により、第１のデータブロックを抽出し、
前記第４の秘密の因子は整数環上の第４の秘密の数で、この数を法とする剰余を求めることにより、第２のデータブロックを復号する。
整数環は例えば有限環とする。整数環上の公開鍵暗号システムでは、公開鍵のデータ長を著しく短くできる。
【００１０】
この発明の復号プログラムは、公開鍵を用いた暗号文を平文に復号するための復号プログラムにおいて、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換するための命令と、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号するための命令と、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号するための命令と、
復号した第１のデータブロックと第２のデータブロックとから平文を求めるための命令とを備えたことを特徴とする。
【００１１】
この発明の復号方法は、公開鍵を用いた暗号文を平文に復号する復号方法において、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする。
【発明の効果】
【００１２】
この発明では、暗号文の作成は、例えば多次連立多項式の変数に平文を代入する、あるいは平文のべき乗演算や秘密鍵との積和演算などをすると実行でき、一般に暗号化に必要な演算量が少ない。
また復号では、秘密の多項式などの適宜の体上の秘密の元、あるいは整数環上の秘密の数などを秘密の因子として用いる。そして秘密の多項式や秘密の数を法とする剰余演算や、割り算などが演算の中心となり、復号に必要な演算量が少ない。
さらに第２のデータブロックの復号に、複数回の剰余演算が必要なようにすると、暗号の安全性を高めることができる。
また整数環上に暗号を構築すると、極めて短い公開鍵のサイズで、安全性の高い暗号システムを提供できる。
【発明を実施するための最良の形態】
【００１３】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００１４】
図１〜図７に、有限体を用いたものと整数環を用いたものの、２種類の実施例を示す。図１に公開鍵を用いた暗号システム２を模式的に示し、この暗号システム２は有限体上の公開鍵暗号の場合も整数環上の公開鍵暗号の場合も共通である。４,６はホストで、例えばパーソナルコンピュータや携帯電話などであり、インターネット８などの通信路を介して暗号通信を行う。ここでは、ホスト４が公開鍵をホスト６へ提供し、ホスト６は入手した公開鍵により平文を暗号化して、ホスト４へ送信するものとする。
【００１５】
ホスト４,６には公開鍵記憶部１０を設けて自己の公開鍵を記憶すると共にインターネット８などを介して公開鍵を公開し、秘密鍵記憶部１１には自己の秘密鍵を記憶する。またこれ以外に、暗号化プログラム１２と復号プログラム１３とを記憶し、これらのプログラムとホスト４,６の資源を利用して、暗号化処理部と復号処理部(不図示)とを構成する。プログラム１２,１３並びに公開鍵と秘密鍵の記憶命令とが、暗号システムに用いるプログラムの要部であり、インターネット８などの通信路を介して、あるいはＣＤ−ＲＯＭなどの記憶媒体を介して、ホスト４,６に暗号通信用のプログラムを実装する。
【００１６】
有限体上の公開鍵暗号
図２〜図５に、有限体上の公開鍵暗号システムを示し、図２に暗号化の手順を、図３,図４に復号手順を、図５に復号過程でのデータ構造の変化を示す。表１に、用いる多項式などを示し、表２に記号などの意味を示す。また暗号化過程での処理を式(1)〜(12)に示し、復号過程での処理を式(13)〜(20)に示す。
【００１７】
有限体Ｆ2ｍ 上の、ｗ次の既約多項式Ｗ(Ｘ)を考える。多項式Ｗ(Ｘ)の次数ｗは、平文ｘの長さを定める。多項式Ｇ(Ｘ)はｇ次でｇ個の根を持ち、後述のように復号時にＹ1とＹ2とを分離するために用いる。ｂi(Ｘ)はｉ−１次の多項式で、ｂ1(Ｘ)は定数、ｂ2(Ｘ)は一次式、ｂJ(Ｘ)はＪ−１次式であり、ｉの値と共に次数が増加する。ｂ2(Ｘ)〜ｂJ(Ｘ)を法とする剰余演算により、後述のように、データｙ1〜ｙJを分離して取り出す。
【００１８】
秘密の多項式Ｓ(Ｘ)と、秘密の多項式Ｔ(Ｘ)とは、式(1)のように、秘密の多項式ｗ-1 (Ｘ) により関係づけられ、多項式Ｃi(Ｘ)は前記の多項式Ｇ(Ｘ)やｂi(Ｘ)と秘密の多項式ｗ(Ｘ)により関係づけられている。そしてｗ-1(Ｘ)は、多項式Ｗ(Ｘ)に関する、多項式ｗ(Ｘ)の逆元である。多項式Ｃi(Ｘ)と多項式ｂi(Ｘ)は式(2)により結びつけられ、２つの多項式の積Ｇ(Ｘ)ｂi(Ｘ)のデータ量はｉと共に増加する。しかしこれに多項式ｗ(Ｘ)を乗算し、Ｗ(Ｘ)を法とする剰余演算を行ったＣi(Ｘ)は、データ長とｉとの関係が消滅し、多項式ｂi(Ｘ)を秘匿する役割を持つ。
【００１９】
メッセージｘは、有限体Ｆ2ｍ  上のｗ次元ベクトルもしくはｗ−１次の多項式と見なすことができ、Ａはこれを中間的なデータｙに返還するための正則行列である。ｙは前半のＹ1と後半のＹ2に２分され、前半のＹ1は例えばＪ次元のベクトルとし、後半のＹ2はｗ−Ｊ次元のベクトルと見なすことができる。なおｗ−ＪをＨとする。前半のベクトルＹ1は多項式Ｃi(Ｘ)と組み合わされ、後半のベクトルＹ2は多項式ｙ2(Ｘ)と見なして、これをｅ乗し、多項式Ｔ(Ｘ)と乗算し、多項式ｗ(Ｘ)を法とする剰余をとって、式(10)の多項式Ｄ(Ｘ)とする。
【００２０】
表１    有限体Ｆ上の公開鍵暗号で用いる多項式など  
記号        意  味        そ      の      他                        
Ｆ２ｍ        有限体    有限体Ｆ２ｍ上に公開鍵暗号システムを構成する
Ｆ２ｍに代えて基礎体Ｆ２を用いても良い
Ｗ(Ｘ)                Ｆ２ｍ上のｗ次既約多項式：    秘密鍵
Ｃi(Ｘ)やＳ(Ｘ)の生成等に用いる   
ｗ                    既約多項式Ｗ(Ｘ)の次数  
Ｇ(Ｘ)                (Ｘ−α1)(Ｘ−α2)(Ｘ−α3)…(Ｘ−αg)
次数ｇのモニック多項式で、
根の集合を｛αi｝(i＝１〜ｇ)とする：秘密鍵
｛ｂi(Ｘ)｝           Ｆ２ｍ上のｉ−１次多項式：i＝１〜Ｊ；秘密鍵
ｂi(Ｘ)の項数はｉと共に増加する
Ｓ(Ｘ)                Ｆ２ｍ上のｇ次のランダム多項式：秘密鍵
Ｔ(Ｘ)                Ｆ２ｍ上のｇ次のランダム多項式：秘密鍵
ｗ(Ｘ)                Ｆ２ｍ上の多項式で、
Ｔ(Ｘ)ｗ−１(Ｘ)≡Ｓ(Ｘ)        modＷ(Ｘ)
により求めたｗ−１(Ｘ)の逆元
Ｃi(Ｘ)               Ｇ(Ｘ)ｂi(Ｘ)ｗ(Ｘ)≡Ｃi(Ｘ)  modＷ(Ｘ)
により求めた秘密の多項式：秘密鍵；ｉ＝１〜Ｊ  
Ｙ２ｅ(Ｘ)              メッセージｘを行列Ａを用いて、  ｘＡ＝ｙ  により、
ｙに変換し、ｙを前半Ｙ1と後半Ｙ2に２分する
これを多項式と見なしたＹ2(Ｘ)のｅ乗がＹ２ｅ(Ｘ)
ｅは２ｍ−１と互いに素な数
Ｄ(Ｘ)                Ｔ(Ｘ)Ｙ２ｅ(Ｘ)≡Ｄ(Ｘ)          modＷ(Ｘ)
Ｄ(Ｘ)＝ｄ1＋ｄ2Ｘ＋…＋ｄwＸｗ−１
【００２１】
表  ２    有限体上の暗号システム  記号などの意味      
ｘ                  メッセージ  ｘ＝(ｘ1,ｘ2,…,ｘw)：
公開鍵｛Ｋi｝中での変数で、これにメッセージの実現値
を代入すると暗号文となる
Ａ                  Ｆ２ｍ上のｗ×ｗの正則行列
ｘＡ＝ｙとメッセージｘをｙに線形変換した際に、
ｙの前半  Ｙ1＝(ｙ1,ｙ2,…,ｙJ)と
ｙの後半  Ｙ2＝(ｙJ+1,ｙJ+2,…,ｙw)に２分する
Ａ＝｜ＡL；ＡR｜と表記し、ＡLはＡの左側ｗ行Ｊ列の行列
ＡRはＡの右側ｗ行ｗ−Ｊ＝Ｈ列の行列
ＡR’               ＡRを線形変換した行列で秘密鍵サイズを縮小する際には、
Ｔ(Ｘ)と共に公開する
Ｂ                  Ｆ２ｍ上のｗ×ｗの正則行列、Ｄ(Ｘ)の露呈を防ぐ
｛ｋj｝            ｋj＝Σi=1〜Jｃijｙi＋ｄj  により得られる中間的な鍵
｛Ｋi｝            (ｋ1,ｋ2,…,ｋw)Ｂ＝(Ｋ1,Ｋ2,…,Ｋw)により
得られる公開鍵：Ｋiはｅ次(Ｙ２ｅ(Ｘ)に由来)の
ｗ変数(ｘ1,ｘ2．…,ｘw)の多項式；ｉ＝１〜ｗ
＊  ベクトル表現と多項式表現：  有限体Ｆ２ｍ上のｎ次拡大体上のデータは、
(ｖ1,ｖ2,…,ｖn)とベクトル表現しても、Ｖ(Ｘ)＝ｖ1＋ｖ2Ｘ＋…＋ｖnＸｎ−１
と多項式表現しても同じデータである
【００２２】
式(1)〜(12)に、公開鍵Ｋ1〜Ｋwの算出過程を示す。秘密の多項式Ｔ(Ｘ),Ｓ(Ｘ),Ｇ(Ｘ),ｂi(Ｘ)を定め、式(1)の条件を満たすように、秘密の多項式ｗ−１(Ｘ)を求める。そしてその逆元を多項式ｗ(Ｘ)とする。メッセージｘはｗ次元のベクトルであるが、ベクトルの各要素を変数として考え、式(3)に従って中間的なベクトルｙに変換する。そして式(4)〜(6)に従って、ベクトルｙを前半Ｙ1と後半Ｙ2に２分する。ここで式(7)に示すように、ベクトルｙの各成分ｙiは、メッセージｘを構成するｗ個の変数ｘ1〜ｘwの関数と考えられる。
【００２３】
公開鍵の構造
Ｔ(Ｘ)ｗ−１(Ｘ)≡Ｓ(Ｘ)        modＷ(Ｘ)                      (1)
Ｇ(Ｘ)ｂi(Ｘ)ｗ(Ｘ)≡Ｃi(Ｘ)  modＷ(Ｘ)                      (2)
ｘＡ＝ｙ；ｙ＝(ｙ1,ｙ2,…,ｙw)                               (3)
ｙ＝(Ｙ1,Ｙ2)                                                (4)
Ｙ1＝(ｙ1,ｙ2,…,ｙJ)                                        (5)
Ｙ2＝(ｙJ+1,ｙJ+2,…,ｙw)                                    (6)
yi=ｆ(ｘ1,ｘ2,…,ｘw)                                        (7)
Ｃi(Ｘ)＝ｃi1＋ｃi2Ｘ＋…＋ｃijＸｊ−１＋ｃiwＸｗ−１              (8)
Ｔ(Ｘ)Ｙ２ｅ(Ｘ)≡Ｄ(Ｘ)    modＷ(Ｘ)                          (9)
Ｄ(Ｘ)＝ｄ1＋ｄ2Ｘ＋…＋ｄwＸｗ−１                                                         (10)
ｋj＝Σi=1〜Jｃijｙi＋ｄj                                      (11)
(ｋ1,ｋ2,…,ｋw)Ｂ＝(Ｋ1,Ｋ2,…,Ｋw)                        (12)
【００２４】
ｂi(Ｘ)はｉ−１次の多項式であるが、Ｃi(Ｘ)は一般にｗ−１次の多項式であり、その係数をｃi1〜ｃiwとする。ベクトルＹ2を多項式Ｙ2(Ｘ)と見なして、これをｅ乗したものに、秘密の多項式Ｔ(Ｘ)を乗算して、多項式Ｗ(Ｘ)を法とする剰余演算を行ったものが、多項式Ｄ(Ｘ)である。多項式Ｄ(Ｘ)はｗ−１次の多項式で、その係数をｄ1〜ｄwとする。多項式Ｃi(Ｘ)の係数ｃijとベクトルｙのｉ番目の成分との積を加算したものに、多項式Ｄ(Ｘ)の係数ｄjを加算したものを、ベクトル（ｋ1,…,ｋw）のj番目の成分ｋjとする(式(11))。このようにして得られたベクトル(ｋ1〜ｋw)を、秘密の正則行列Ｂで線形変換したものを公開鍵のベクトル(Ｋ1〜Ｋw)とする。公開鍵(Ｋ1〜Ｋw)は、ｗ−１次の多項式の各係数と見なすこともでき、またメッセージｘの元ｘ1〜ｘwに関して見ると、ｅ次の多次多変数多項式と言うこともできる。
【００２５】
暗号化には図２のステップ１に示したように、公開鍵Ｋiにメッセージの実現値ｘ1’〜ｘw’を代入する。続いて図２のステップ２で、暗号文Ｃを送出する。なおＫi(ｉ＝１〜ｗ)を公開鍵とし、式(1)〜式(12)で用いた、Ｗ(Ｘ),ｗ(Ｘ),Ｇ(Ｘ),ｂi(Ｘ),Ｓ(Ｘ),Ｔ(Ｘ),Ａ,Ｂ,Ｃi(Ｘ),Ｄ(Ｘ)などを秘密鍵のセットとする。
【００２６】
秘密鍵：  Ｗ(Ｘ),ｗ(Ｘ),Ｇ(Ｘ),｛ｂi(Ｘ)｝,Ｓ(Ｘ),Ｔ(Ｘ),Ａ,Ｂ,
Ｃi(Ｘ),Ｄ(Ｘ)
公開鍵： ｛Ｋi｝
【００２７】
復号時には、図３のステップ１１のように、暗号文Ｃを行列Ｂの逆行列Ｂ-1で処理して  Ｃ’を求める。これによって式(12)の左辺のベクトル(ｋ1〜ｋw)が得られる。このベクトルを多項式Ｋ(Ｘ)として表現すると、式(14)のようになり、これに多項式ｗ−１(Ｘ)を乗算すると、多項式Ｗ(Ｘ)を法として、式(15)の右辺と合同となる(ステップ１２)。ここでα1〜αgが多項式Ｇ(Ｘ)の根であるので、これらを代入すると、式(16)を介してｉ＝１〜ｇに対して、Ｓ(αi)Ｙ2ｅ(αi)が得られる(ステップ１３)。そしてＳ(αi)は既知なので、Ｙ2ｅ(αi)が得られ(ステップ１４)、これから式(17)のようにｙJ+1〜ｙwを復号することができる(ステップ１５)。
【００２８】
式(15)の右辺から、Ｓ(Ｘ)とＹ2ｅ(Ｘ)の積を除き、Ｇ(Ｘ)で割り算すると、ｂ1(Ｘ)ｙ1＋…＋ｂJ(Ｘ)ｙJが得られる。ここで、ｂJ(Ｘ)はＪ−１次の多項式で、ｂJ-1はＪ−２次の多項式であることなどを利用し、ｂJ(Ｘ)での法をとると、ｂJ(Ｘ)ｙJの項は消失するが、ｂJ-1(Ｘ)ｙJ-1などの項は消失しない。このようにしてｂJ(Ｘ)の次にｂJ-1(Ｘ)を法とし、ｂ2(Ｘ)までを法として剰余演算すると、ｂ1(Ｘ)ｙ1が得られる(ステップ１６)。そしてｂ1(Ｘ)は既知なので、ｙ1を復号できる。
【００２９】
結合子Ａから図４に移り、ｂ3(Ｘ)の法を求めた段階で、ｂ1(Ｘ)ｙ1＋ｂ2(Ｘ)ｙ2が得られているので、これからｂ1(Ｘ)ｙ1を引くと、ｂ2(Ｘ)ｙ2が得られ、ｙ2が求まる(ステップ１８)。以下同様にして、添字ｉの小さい側から大きい側へと(多項式ｂi(Ｘ)の次数の低い側から高い側へと)順次復号し、ｙ1〜ｙJまでを復号できる(ステップ１９)。ｙJ+1〜ｙwは、Ｓ(Ｘ)Ｙ2ｅ(Ｘ)から既に求まっており、ｙ1〜ｙJが求まったので、行列Ａの逆行列  Ａ-1で処理し、式(20)のようにメッセージｘを復号できる。
【００３０】
復号時の処理
ＣＢ−１＝Ｃ’＝(ｋ1,ｋ2,…,ｋw)                                (13)
Ｋ(Ｘ)＝Ｄ(Ｘ)＋Σi=1〜JＣi(Ｘ)ｙi＝Ｔ(Ｘ)Ｙ２ｅ(Ｘ)＋Σi=1〜JＣi(Ｘ)ｙi
(14)
Ｋ(Ｘ)ｗ−１(Ｘ)≡Ｓ(Ｘ)Ｙ２ｅ(Ｘ)＋Ｇ(Ｘ)｛ｂ1(Ｘ)ｙ1＋…＋ｂJ(Ｘ)ｙJ｝
modＷ(Ｘ)                                 (15)
Ｋ(αi)ｗ−１(αi)＝Ｓ(αi)Ｙ２ｅ(αi)＋Ｇ(αi)・
｛ｂ1(αi)ｙ1＋…＋ｂJ(αiＸ)ｙJ｝
：ｉ＝１〜ｇ；Ｇ(αi)＝０                               (16)
Ｙ２ｅ(αi)  (ｉ＝１〜ｇ)  →  (ｙJ+1〜ｙw)                     (17)
Ｓ(Ｘ)Ｙ２ｅ(Ｘ)＋Ｇ(Ｘ)｛ｂ1(Ｘ)ｙ1＋…＋ｂJ(Ｘ)ｙJ｝を
Ｇ(Ｘ)｛ｂ1(Ｘ)ｙ1＋…＋ｂJ(Ｘ)ｙJ｝  に変換                  (18)
ｂ1(Ｘ)ｙ1＋…＋ｂJ(Ｘ)ｙJ  →  ｙ1,ｙ2,ｙ3,…,ｙJ            (19) 
ｙＡ−１＝ｘ                                                    (20)
【００３１】
復号過程でのデータ構造の変化を図５に示すと、ｋxの段階では、Ｄ(Ｘ)と多項式Ｃ1(Ｘ)ｙ1〜ＣJ(Ｘ)ｙJはほぼ同じデータ長で、これらは入り交じっており分離できない。これにｗ−１(Ｘ)を乗算し、Ｗ(Ｘ)を法として剰余演算することにより、多項式Ｇ(Ｘ)の積の項と、Ｓ(Ｘ)Ｙ2ｅ(Ｘ)の項に分けることができる。ここでα1〜αgが多項式Ｇ(Ｘ)の根であることを利用して、Ｓ(Ｘ)Ｙ2ｅ(Ｘ)の値を、α1〜αgについて求め、これからＹ2を復号することができる。そしてＹ2が求まれば、Ｓ(Ｘ)Ｙ2ｅ(Ｘ)を引き算し、Ｇ(Ｘ)で割ることにより、ｂ1(Ｘ)ｙ1〜ｂJ(Ｘ)ｙJの和を求めることができる。これらの各項は長さが異なり、１番長いｂJ(Ｘ)ｙJに対して、ｂJ(Ｘ)を法とする剰余演算を行っても、ｂ1(Ｘ)ｙ1〜ｂJ-1(Ｘ)ｙJ-1の項は影響を受けない。この手続を順次繰り返してｙ1を求め、次にｙ1から逆にｙ2を求め、次いでｙ3を求めるようにして、ｙJまで復号する。
【００３２】
公開鍵暗号の構成例を示すと、例えばｍ＝１５(Ｆ215)を用いるものとし、暗号サイズを９０ビットとする。ｇ＝２,J＝４,Ｈ＝２,ｗ＝６,ｅ＝３とし、各ｋiは例えば９０ビット程度のデータ長とし、メッセージの要素ｘiも１５ビットとする。Ｈ＝２なので、Ｙ2ｅでの項数は、例えば３６となる。これ以外にｙ1〜ｙ4の項があり、これらはｘ1〜ｘ6の線形和で、公開鍵のサイズは１５×６×(３６＋６)＝３７８０ビット程度となる。ここで１５はＦ215上のデータであることにより、次の６は公開鍵がｋ1〜ｋ6の６成分から成ることによる。
【００３３】
実施例ではＹ2を多項式と見なしてｅ乗したが、Ｙ2からランダムな多項式を生成してＴ(Ｘ)との積を求めても良い。例えばこのようなｅ次の多項式Ｆe(ｙJ+1〜ｙw)を考え、Ｄ(Ｘ)の代わりにＴ(Ｘ)Ｆe(ｙJ+1〜ｙw)を用いる。公開鍵暗号のサイズが大きくなるのは、Ｙ2ｅ(Ｘ)に関係するｘi3やｘi2ｘJなどの項数が多いことによるため、ランダム多項式Ｆe(ｙJ+1〜ｙw)を用いると、公開鍵サイズを大幅に小さくすることができる。そしてランダムな多項式Ｆe(ｙJ+1〜ｙw)を用いると、安全性を改善することも可能である。
【００３４】
これ以外に公開鍵のサイズを縮小するため、多項式Ｔ(Ｘ)を公開すると共に、表２に示した行列ＡR’を公開し、Ｔ(Ｘ)Ｙ2ｅ(Ｘ)を送信者に作成させることも可能である。但しこの場合、残る主要な秘密鍵は多項式Ｗ(Ｘ),ｗ(Ｘ)であり、安全性が低下する恐れがある。
【００３５】
実施例では有限体Ｆ2ｍ上で構成したが基礎体Ｆ2上でも同様に構成できる。例えば多項式Ｇ(Ｘ)をＦ2上の原始多項式とし、Ｆ2上のメッセージをｍ個ずつ１ブロックとして、多項式ｂi(Ｘ)を(ｉ−１)×ｍ次のＦ2上の多項式とすればよい。
【００３６】
整数環上の暗号システム
表３と式(21)〜(27)並びに図６,図７に、有限整数環Ｚrを用いた公開鍵暗号システムを示す。ｒを充分大きい秘密の数とし、メッセージｘはｗ個の要素ｘ1〜ｘwで構成されるものとし、各要素ｘiはＦ2ｍの元とする。有限体上の多項式Ｗ(Ｘ)に代えて、秘密の素数Ｗを用意する。また秘密の多項式ｗ(Ｘ)に代えて、素数ｐを用意し、Ｗとｐは互いに素とする。Ｇ(Ｘ)に対応する秘密の数ｇを用意し、ｂi(Ｘ)に対応する秘密の数ｂiをｉ＝１〜Ｊに対して用意する。式(23)のように、ｇｂiｐを秘密鍵ｗを法として剰余演算すると、多項式Ｃi(Ｘ)に対応する秘密の数Ｃiがｉ＝１〜Ｊに対して得られる。また多項式Ｔ(Ｘ)やＳ(Ｘ)に対応する秘密の数ｓや数ｔを用意する。
【００３７】
秘密の数ｂiは、式(21)に示すように、ｂi+1のビット数がｘi・ｂiの積のビット数以上となるようにする。Ｃi(ｉ＝１〜Ｊ)とｔ並びにｅを公開鍵とし、秘密の数ｗ,Ｗ,ｇ,ｂi(ｉ＝１〜Ｊ),ｓなどを秘密鍵とする。
【００３８】
暗号化では、図６のステップ２０に示すように、メッセージｘの実現値を用いて暗号文Ｃを求める。この時実現値の各要素ｘ1’〜ｘJ’とｘJ+1’〜ｘw’とでは扱いが異なり、ｘ1’〜ｘJ’までは暗号文中に線形変換して取り込まれ、ｘJ+1’〜ｘw’は非線形変換して取り込まれている。なおステップ２０での＊は連接を意味する。図６のステップ２１で暗号文を送出し、ステップ２２〜ステップ２６で復号する。
【００３９】
暗号文Ｃに秘密の数ｐ−１を乗算し、Ｗを法とする剰余演算を行うと、ステップ２２のように式(25)が得られる。これをｇを法として剰余演算すると、式(26)の中間的変数Ｌが得られ、これをｓで除してｅ乗根を求めると、ｘJ〜ｘwの連接を求めることができる。残る項は、Σi=1〜Jｂiｘiなので、式(25)の中辺からｓ(ｘJ＊…＊ｘw)ｅを除き、ｇで割り算すると、ｂiｘiの積和が求まる。ｂiのデータ長は、ｉと共に増加するので、最初にｂJを法とする剰余を求め、次にｂJ-1を法とする剰余を求めるようにして、ｂ2を法とする剰余までを求める。この時の剰余はｂ1ｘ1である。これをｂ3を法とした剰余から除いて、ｂ2で割るとｘ2が求まる。以下このステップを繰り返して、ｘJまでを求めることができる。
【００４０】
表  ３    記号などの意味  整数環Ｚｒ上の暗号システム
記号                意      味            そ      の      他          
Ｚｒ                整数環
ｘ                  メッセージ  ｘ＝(ｘ1,ｘ2,…,ｘw)：ｘi(i＝１〜ｗ)はＺｒの元
ｗ                  メッセージ長を示す定数
メッセージｘは  前半のＸ1＝(ｘ1,ｘ2,…,ｘJ)と
後半のＸ2＝(ｘJ+1,ｘJ+2,…,ｘw)に２分する
Ｗ                  ２００〜１０００ビット程度の素数で秘密鍵：Ｗ(Ｘ)に対応
ｐ                  ｗ(Ｘ)に対応する素数  (ｐ−１,Ｗ)＝(ｐ,Ｗ)＝１    
ｇ                  Ｇ(Ｘ)に対応する秘密の数            
｛ｂi｝              ｂi(Ｘ)に対応する秘密の数：ｉ＝１〜Ｊ
｛ｃi｝              Ｃi(Ｘ)に対応する秘密の数：ｉ＝１〜Ｊ
ｔ                  Ｔ(Ｘ)に対応する数
ｓ                  Ｓ(Ｘ)に対応する秘密の数
ｅ,Ｊ,Ｈ            有限体上の暗号システムの場合と同様で、ｅはｒ−１と互いに素、
Ｊはメッセージｘを前半と後半に２分する際の前半部の長さを示す
パラメータ,Ｈ＝ｗ−Ｊでメッセージの後半部の長さを示すパラメ
ータ
Ｃ                  暗号文
｜｜                データ長を示す記号：例えば|Ｗ|＝２４０は秘密の素数Ｗは
２４０ビット程度のデータであることを示す
【００４１】
図６の復号過程でのデータ構造の変化を図７に示すと、暗号文Ｃ中では、各構成要素の長さは区別がつかず、これらの和として暗号文Ｃが存在する。ｐの逆数を乗算し、Ｗを法とする剰余を求めることにより、ｇの倍数の項とｓの倍数の項に分かれ、ｇを法とする剰余演算を行ってｓで割り、ｅ乗根を求めると、メッセージの実現値の一部ｘJ+1’〜ｘw’を復号できる。この部分を除いてｇで割り、ｂJで剰余演算した後にｂJ-1で剰余演算するようにして、ｂ2まで剰余演算すると、ｂ1ｘ1’が求まる。続いてｂ1ｘ1’を、ｂ3で剰余演算した際の剰余から除き、ｂ2で割ると、ｘ2’が求まる。このようにしてｘ1’〜ｘJ’までを求めることができる。
【００４２】
｜ｘi・ｂi｜≦｜ｂi+1｜                                    (21)
ｔｐ−１≡ｓ            modＷ                                (22)
ｇｂiｐ≡ｃi          modＷ                                (23)
Ｃ＝Σi=１〜J｛ｃiｘi＋ｔ(ｘ1＊…＊ｘw)ｅ｝                    (24)
Ｃｐ-1≡Σi=１〜J｛ｇｂiｘi｝＋ｓ(ｘJ＊…＊ｘw)ｅ＝Ｌ  modＷ    (25)
Ｌ≡ｓ(ｘJ＊…＊ｘw)ｅ  modｇ                               (26)
Σi=１〜Jｂiｘi  →  (ｘ1,ｘ2,…,ｘJ)                         (27)
【００４３】
整数環を用いた構成例を示す。例えば暗号文サイズを２８０ビットとし、またＨ＝２,Ｊ＝４,ｗ＝６,ｅ＝３などとし,Ｗを約２４０ビットとし、ｇやｔを約８０ビットとし、ｂiを約４０ビットとする。公開鍵のサイズは、４×２４０＋８０＝１０４０ビットで与えられ、先頭の４はＪが４であることにより、次の２４０はＣiとしてＷと同等の２４０ビット程度が必要なことによる。なおこれらのデータ長は単なる例である。
【００４４】
この構成例で暗号を破るには、例えば２８０回の総当たり攻撃を行うと、秘密鍵が露呈する可能性がある。しかしｇやｔの値を１００ビット以上と大きくすると、現状では総当たり攻撃は非現実的となる。
【００４５】
他の構成例として、暗号文サイズを４００ビットとし、Ｈ＝１,J＝２,ｗ＝３,ｅ＝３として、Ｗを３００ビット程度とし、ｇやｂ2、ｔやｓなどをそれぞれ１００ビット程度のデータとする。また入力メッセージのサイズをｘ1〜ｘ3を各１００ビットの合計３００ビットとする。公開鍵のサイズは２×３００＋１００＝７００ビットとなり、極めて短い公開鍵が得られる。
【００４６】
この構成例では、見かけの入力文長は２００＋３００ビットの５００ビットであり、これに対する暗号文長は４００ビットなので、ＬＬＬ攻撃に対しては安全と考えられる。またｇやｂ2やｓのサイズをｘ1やｘ2のサイズより大きくし、ｓのサイズをｔのサイズより大きくし、ｘ3のサイズをｘ1のサイズより大きくすることを考える。ここでこれらの値を適切に選ぶと、公開鍵ｃ1,ｃ2,ｔよりも、秘密鍵Ｗ,Ｇ,ｂ,Ｓのサイズが大きくなり、公開鍵から秘密鍵が露呈することは情報量的に矛盾となる。この構成例では、２１００＝１０３０の総当たり攻撃により、暗号が破れる可能性がある。しかしながら現時点では１０３０回の計算は非現実的で、暗号は充分安全と考えられる。
【図面の簡単な説明】
【００４７】
【図１】実施例の暗号システムを模式的に示す図
【図２】有限体を用いた暗号システムでの暗号化を示すフローチャート
【図３】有限体を用いた暗号システムでの復号アルゴリズムを示すフローチャート
【図４】図３の結合子Ａ以降のフローチャート
【図５】図３,図４の復号過程でのデータ構造の変化を模式的に示す図
【図６】整数環を用いた暗号システムでの暗号化と復号のアルゴリズムを示すフローチャート
【図７】図６の復号過程での、データ構造の変化を模式的に示す図
【符号の説明】
【００４８】
２      暗号システム
４,６   ホスト
８      インターネット
１０    公開鍵記憶部
１１    秘密鍵記憶部
１２    暗号化プログラム
１３    復号プログラム
【図１】
2005141136.tif 000003
【図２】
2005141136.tif 000004
【図３】
2005141136.tif 000005
【図４】
2005141136.tif 000006
【図５】
2005141136.tif 000007
【図６】
2005141136.tif 000008
【図７】
2005141136.tif 000009
【手続補正書】
【提出日】平成15年12月1日(2003.12.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１
【補正方法】変更
【補正の内容】
【請求項１】
公開鍵を用いた暗号文を平文に復号する暗号システムにおいて、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする、公開鍵暗号システム。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２
【補正方法】変更
【補正の内容】
【請求項２】
公開鍵を用いた暗号文を平文に復号する暗号通信方法において、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする、暗号通信方法。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
この発明は、公開鍵を用いた暗号文を平文に復号する暗号システムにおいて、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
この発明の暗号通信方法は、公開鍵を用いた暗号文を平文に復号する暗号通信方法において、
暗号文に第１の秘密の因子を乗算し、かつ第２の秘密の因子を法とする剰余を求めることにより、該暗号文を長さの異なる複数の因子の和に変換し、
前記因子の和を第３の秘密の因子で処理することにより、第１のデータブロックを抽出して、該第１のデータブロックを復号し、
前記因子の和から前記第１のデータブロックを除いて、第４の秘密の因子を法とする剰余を求めることにより、第２のデータブロックを復号し、
復号した第１のデータブロックと第２のデータブロックとから平文を求めることを特徴とする。