(57)【特許請求の範囲】
【請求項１】
暗号文の作成に乱数を使用し、その使用した乱数を受信側で復元できる暗号化方式に対して、乱数を使用しない暗号化方式に対応するパディング方式を適用する方法において、
送信側の通信端末に備えられているプロセッサは、
入力情報を前記パディング方式により所定長以下のビット列に変換し、
前記ビット列を所定の変換規則によって第１ビット列と第２ビット列とに変換し、
前記第１ビット列をデータ入力とし、前記第２ビット列を乱数入力として暗号化関数にそれぞれ供給し、
前記暗号化関数の出力を暗号文として出力し、
前記変換規則は、前記所定長以下のビット列を前記第１ビット列の集合と第２ビット列の集合との直積の元に対応させる写像であり、かつ、前記写像は単射であること、前記写像およびその逆写像が多項式時間で計算可能であること、および、前記直積を定義域とする前記暗号化関数が一方向性関数であること、を満たす、
ことを特徴とするパディング適用方法。
【請求項２】
前記変換規則は、前記ビット列の前半を前記第１ビット列とし、後半を前記第２ビット列とするように前記ビット列を２分割する規則であることを特徴とする請求項１に記載のパディング適用方法。
【請求項３】
前記パディング方式はＯＡＥＰ＋パディングであり、前記乱数を使用する暗号化方式はＮＴＲＵ暗号方式であることを特徴とする請求項１または２に記載のパディング適用方法。
【請求項４】
暗号文の作成に乱数を使用し、その使用した乱数を受信側で復元できる暗号化方式に対して、乱数を使用しない暗号化方式に対応するパディング方式を適用する装置において、
入力情報を前記パディング方式により所定長以下のビット列に変換するパディング変換手段と、
前記ビット列を所定の変換規則によって第１ビット列と第２ビット列とに変換するビット列変換手段と、
前記第１ビット列をデータ入力とし、前記第２ビット列を乱数入力として暗号化関数にそれぞれ供給して暗号文を生成する暗号化手段と、
を有し、
前記変換規則は、前記所定長以下のビット列を前記第１ビット列の集合と第２ビット列の集合との直積の元に対応させる写像であり、かつ、前記写像は単射であること、前記写像およびその逆写像が多項式時間で計算可能であること、および、前記直積を定義域とする前記暗号化関数が一方向性関数であること、を満たす、
ことを特徴とするパディング装置。
【請求項５】
前記変換規則は、前記ビット列の前半を前記第１ビット列とし、後半を前記第２ビット列とするように前記ビット列を２分割する規則であることを特徴とする請求項４に記載のパディング装置。
【請求項６】
前記パディング方式はＯＡＥＰ＋パディングであり、前記乱数を使用する暗号化方式はＮＴＲＵ暗号方式であることを特徴とする請求項４または５に記載のパディング装置。
【請求項７】
暗号文の作成に乱数を使用し、その使用した乱数を受信側で復元できる暗号化方式に対して、乱数を使用しない暗号化方式に対応するパディング方式を適用することで暗号文を生成する暗号化装置において、
入力した平文を前記パディング方式により所定長以下のビット列に変換するパディング変換手段と、
前記ビット列を所定の変換規則によって第１ビット列と第２ビット列とに変換するビット列変換手段と、
前記第１ビット列をデータ入力とし、前記第２ビット列を乱数入力として暗号化関数にそれぞれ供給して暗号文を生成する暗号化手段と、
を有し、
前記変換規則は、前記所定長以下のビット列を前記第１ビット列の集合と第２ビット列の集合との直積の元に対応させる写像であり、かつ、前記写像は単射であること、前記写像およびその逆写像が多項式時間で計算可能であること、および、前記直積を定義域とする前記暗号化関数が一方向性関数であること、を満たす、
ことを特徴とする暗号化装置。
【請求項８】
暗号文の作成に乱数を使用し、その使用した乱数を受信側で復元できる暗号化方式に対して、乱数を使用しない暗号化方式に対応するパディング方式を適用することで暗号文を生成する暗号化装置において、
秘密鍵暗号の鍵をランダムに選択し、前記秘密鍵暗号の鍵を用いて、入力した平文を秘密鍵暗号化することで第１暗号文を生成する第１暗号化手段と、
前記秘密鍵暗号の鍵を前記パディング方式により所定長以下のビット列に変換するパディング変換手段と、
前記ビット列を所定の変換規則によって第１ビット列と第２ビット列とに変換するビット列変換手段と、
前記第１ビット列をデータ入力とし、前記第２ビット列を乱数入力として暗号化関数にそれぞれ供給して第２暗号文を生成する第２暗号化手段と、
前記第１暗号文および前記第２暗号文を暗号文として出力する暗号文出力手段と、
を有し、
前記変換規則は、前記所定長以下のビット列を前記第１ビット列の集合と第２ビット列の集合との直積の元に対応させる写像であり、かつ、前記写像は単射であること、前記写像およびその逆写像が多項式時間で計算可能であること、および、前記直積を定義域とする前記暗号化関数が一方向性関数であること、を満たす、
ことを特徴とする暗号化装置。
【請求項９】
前記変換規則は、前記ビット列の前半を前記第１ビット列とし、後半を前記第２ビット列とするように前記ビット列を２分割する規則であることを特徴とする請求項７または８に記載の暗号化装置。
【請求項１０】
前記パディング方式はＯＡＥＰ＋パディングであり、前記乱数を使用する暗号化方式はＮＴＲＵ暗号方式であることを特徴とする請求項７または８または９に記載の暗号化装置。
【請求項１１】
暗号文の作成に乱数を使用し、その使用した乱数を受信側で復元できる暗号化方式に対して、乱数を使用しない暗号化方式に対応するパディング方式を適用することで暗号文を生成する方法において、
送信側の通信端末に備えられているプロセッサは、
入力した平文を前記パディング方式により所定長以下のビット列に変換し、
前記ビット列を所定の変換規則によって第１ビット列と第２ビット列とに変換し、
前記第１ビット列をデータ入力とし、前記第２ビット列を乱数入力として暗号化関数にそれぞれ供給して暗号文を生成し、
前記変換規則は、前記所定長以下のビット列を前記第１ビット列の集合と第２ビット列の集合との直積の元に対応させる写像であり、かつ、前記写像は単射であること、前記写像およびその逆写像が多項式時間で計算可能であること、および、前記直積を定義域とする前記暗号化関数が一方向性関数であること、を満たす、
ことを特徴とする暗号化方法。
【請求項１２】
暗号文の作成に乱数を使用し、その使用した乱数を受信側で復元できる暗号化方式に対して、乱数を使用しない暗号化方式に対応するパディング方式を適用することで暗号文を生成する方法において、
送信側の通信端末に備えられているプロセッサは、
秘密鍵暗号の鍵をランダムに選択し、
前記秘密鍵暗号の鍵を用いて、入力した平文を秘密鍵暗号化することで第１暗号文を生成し、
前記秘密鍵暗号の鍵を前記パディング方式により所定長以下のビット列に変換し、
前記ビット列を所定の変換規則によって第１ビット列と第２ビット列とに変換し、
前記第１ビット列をデータ入力とし、前記第２ビット列を乱数入力として暗号化関数にそれぞれ供給して第２暗号文を生成し、
前記第１暗号文および前記第２暗号文を暗号文として出力し、
前記変換規則は、前記所定長以下のビット列を前記第１ビット列の集合と第２ビット列の集合との直積の元に対応させる写像であり、かつ、前記写像は単射であること、前記写像およびその逆写像が多項式時間で計算可能であること、および、前記直積を定義域とする前記暗号化関数が一方向性関数であること、を満たす、
ことを特徴とする暗号化方法。
【請求項１３】
前記変換規則は、前記ビット列の前半を前記第１ビット列とし、後半を前記第２ビット列とするように前記ビット列を２分割する規則であることを特徴とする請求項１１または１２に記載の暗号化方法。
【請求項１４】
前記パディング方式はＯＡＥＰ＋パディングであり、前記乱数を使用する暗号化方式はＮＴＲＵ暗号方式であることを特徴とする請求項１１または１２または１３に記載の暗号化方法。
【請求項１５】
請求項７に記載の暗号化装置により生成された暗号文を復号化する装置において、
前記乱数を使用する暗号化方式に対応する復号化方式に従って、入力した暗号文を復号化して第１ビット列を生成する第１復号化手段と、
予め定められた関数に基づいて前記暗号文から、前記暗号化に使用した乱数を第２ビット列として復元する乱数復号手段と、
前記暗号化装置のビット列変換手段における変換処理での変換規則の逆変換規則に従って、前記第１ビット列および前記第２ビット列を所定長以下のビット列に逆変換するビット列逆変換手段と、
前記所定長以下のビット列から前記パディング方式によるパディングを除去することで元の平文を生成するパディング逆変換手段と、
前記パディングの正当性を判断し、正当であれば前記平文を出力する判定手段と、
を有することを特徴とする復号化装置。
【請求項１６】
請求項８に記載の暗号化装置により生成された暗号文を復号化する装置において、
前記乱数を使用する暗号化方式に対応する復号化方式に従って、前記第２暗号文を復号化して第１ビット列を生成する第１復号化手段と、
予め定められた関数に基づいて前記暗号文から、前記暗号化に使用した乱数を第２ビット列として復元する乱数復号手段と、
前記暗号化装置のビット列変換手段における変換処理での変換規則の逆変換規則に従って、前記第１ビット列および前記第２ビット列を所定長以下のビット列に逆変換するビット列逆変換手段と、
前記所定長以下のビット列から前記パディング方式によるパディングを除去することで元の秘密鍵暗号の鍵を生成するパディング逆変換手段と、
前記パディングの正当性を判断し、正当であれば前記秘密鍵暗号の鍵を用いて前記第１暗号文を復号する第２復号手段と、
を有することを特徴とする復号化装置。
【請求項１７】
請求項１１に記載の暗号化方法により生成された暗号文を復号化する方法において、
受信端末に備えられているプロセッサは、
前記乱数を使用する暗号化方式に対応する復号化方式に従って、入力した暗号文を復号化して第１ビット列を生成し、
予め定められた関数に基づいて前記暗号文から、前記暗号化に使用した乱数を第２ビット列として復元し、
前記暗号化方法による変換規則の逆変換規則に従って、前記第１ビット列および前記第２ビット列を所定長以下のビット列に逆変換し、
前記所定長以下のビット列から前記パディング方式によるパディングを除去することで元の平文を生成し、
前記パディングの正当性を判断し、正当であれば前記平文を出力する、
ことを特徴とする復号化方法。
【請求項１８】
請求項１２に記載の暗号化方法により生成された暗号文を復号化する方法において、
受信端末に備えられているプロセッサは、
前記乱数を使用する暗号化方式に対応する復号化方式に従って、前記第２暗号文を復号化して第１ビット列を生成し、
予め定められた関数に基づいて前記暗号文から、前記暗号化に使用した乱数を第２ビット列として復元し、
前記暗号化方法による変換規則の逆変換規則に従って、前記第１ビット列および前記第２ビット列を所定長以下のビット列に逆変換し、
前記所定長以下のビット列から前記パディング方式によるパディングを除去することで元の秘密鍵暗号の鍵を生成し、
前記パディングの正当性を判断し、正当であれば前記秘密鍵暗号の鍵を用いて前記第１暗号文を復号する、
ことを特徴とする復号化方法。
【請求項１９】
暗号文の作成に乱数を使用し、その使用した乱数を受信側で復元できる暗号化方式と、乱数を使用しない暗号化方式に対応するパディング方式とを用い、通信ネットワークを通して通信端末間で暗号通信を行うシステムにおいて、
送信側通信端末は、
入力した平文を前記パディング方式により所定長以下のビット列に変換するパディング変換手段と、
前記所定長以下のビット列を前記第１ビット列の集合と第２ビット列の集合との直積の元に対応させる写像であり、かつ、前記写像は単射であること、前記写像およびその逆写像が多項式時間で計算可能であること、および、前記直積を定義域とする前記暗号化関数が一方向性関数であること、を満たす変換規則に従って、前記ビット列を第１ビット列と第２ビット列とに変換するビット列変換手段と、
前記第１ビット列をデータ入力とし、前記第２ビット列を乱数入力として暗号化関数にそれぞれ供給して暗号文を生成する暗号化手段と、
前記暗号文を受信側通信端末へ送信する送信手段と、
を有し、
前記受信側通信端末は、
前記暗号文を前記送信側通信端末から受信する受信手段と、
前記乱数を使用する暗号化方式に対応する復号化方式に従って、入力した暗号文を復号化して第１ビット列を生成する第１復号化手段と、
予め定められた関数に基づいて前記暗号文から、前記暗号化に使用した乱数を第２ビット列として復元する乱数復号手段と、
前記変換規則の逆変換規則に従って、前記第１ビット列および前記第２ビット列を所定長以下のビット列に逆変換するビット列逆変換手段と、
前記所定長以下のビット列から前記パディング方式によるパディングを除去することで元の平文を生成するパディング逆変換手段と、
前記パディングの正当性を判断し、正当であれば前記平文を出力する判定手段と、
を有する、
ことを特徴とする暗号通信システム。
【請求項２０】
暗号文の作成に乱数を使用し、その使用した乱数を受信側で復元できる暗号化方式と、乱数を使用しない暗号化方式に対応するパディング方式とを用い、通信ネットワークを通して通信端末間で暗号通信を行うシステムにおいて、
送信側通信端末は、
秘密鍵暗号の鍵をランダムに選択し、前記秘密鍵暗号の鍵を用いて、入力した平文を秘密鍵暗号化することで第１暗号文を生成する第１暗号化手段と、
前記秘密鍵暗号の鍵を前記パディング方式により所定長以下のビット列に変換するパディング変換手段と、
前記所定長以下のビット列を前記第１ビット列の集合と第２ビット列の集合との直積の元に対応させる写像であり、かつ、前記写像は単射であること、前記写像およびその逆写像が多項式時間で計算可能であること、および、前記直積を定義域とする前記暗号化関数が一方向性関数であること、を満たす変換規則に従って、前記ビット列を第１ビット列と第２ビット列とに変換するビット列変換手段と、
前記第１ビット列をデータ入力とし、前記第２ビット列を乱数入力として暗号化関数にそれぞれ供給して第２暗号文を生成する第２暗号化手段と、
前記第１暗号文および前記第２暗号文を暗号文として出力する暗号文出力手段と、
を有し、
受信側通信端末は、
前記暗号文を前記送信側通信端末から受信する受信手段と、
前記乱数を使用する暗号化方式に対応する復号化方式に従って、前記第２暗号文を復号化して第１ビット列を生成する第１復号化手段と、
予め定められた関数に基づいて前記暗号文から、前記暗号化に使用した乱数を第２ビット列として復元する乱数復号手段と、
前記変換規則の逆変換規則に従って、前記第１ビット列および前記第２ビット列を所定長以下のビット列に逆変換するビット列逆変換手段と、
前記所定長以下のビット列から前記パディング方式によるパディングを除去することで元の秘密鍵暗号の鍵を生成するパディング逆変換手段と、
前記パディングの正当性を判断し、正当であれば前記秘密鍵暗号の鍵を用いて前記第１暗号文を復号する第２復号手段と、
を有する、
ことを特徴とする暗号通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は情報の暗号化／復号化システムに係り、特に選択暗号文攻撃に対し安全性を保証するパディング適用方法および暗号化／復号化装置に関する。
【背景技術】
【０００２】  通信のセキュリティを確保するために暗号技術の社会的応用が盛んに進められ、効率的な暗号計算が従来以上に望まれている。このような傾向のなかで、Jeffrey Hoffstein、Jill PipherおよびJoseph H. Silvermanによる文献“NTRU:A Ring-Based Public Key Cryptosystem”（非特許文献１）により提案されたNTRU暗号方式は、従来のRSA暗号方式やElGamal暗号方式と比べ、メモリ消費が少なく高速な暗号／復号計算方法として注目されている。【０００３】  （ＮＴＲＵ暗号化方式）  NTRU暗号方式は以下のような公開鍵暗号方式である。【０００４】  まず以下のようにして鍵生成を行う。正整数p, q, Nをとり領域変数として公開し、R = Z[X]/(XN-1)とする。以下、L(a,b)は、Rの元uであって、uの各次数の係数のうちa個が1でb個が-1、他のものが0であるもの全体の集合（Rの部分集合）を表すものとする。パラメータdf, dg, dを決め、Lf = L(df, df+1), Lg = L(dg, dg+1), Lφ = L(d, d)とする。Lfからfを、Lgからgをランダムに取り、h = f-1g mod q とする。f, gを秘密鍵とし、hを公開鍵とする。【０００５】  鍵が生成されると、Rの部分集合Lmの元mを暗号化する。まず、Rの部分集合元Lrからr をランダムに選び、e = phr + m mod q を計算し、eを暗号文として出力する。【０００６】  暗号文eから元の平文mを復号するには、まずfe = pgr + fm mod qを計算する。f, g, r, mがそれぞれLf、Lg、Lr、Lmの元であることから fe = pgr + fmであるので、fe (mod p) = m (mod p)を計算することができ、mがLmの元であることからm = m (mod p)なので mを復元できる。【０００７】  しかしながら、Don Coppersmith、Adi Shamirによる文献“Lattice Attacks on NTRU”, Eurocrypt'97 Springer Lecture Notes in Computer Sciences,1997（非特許文献２）などに指摘されているように、NTRU暗号方式には数々の解読方法が知られている。これに対して、平文に何らかのパディングを施した後、NTRU暗号化することにより解読を防御する方法が幾つか知られている。【０００８】  （ＯＡＥＰ＋パディング方式）  暗号方式を安全にするためのパディング方法としては、例えばVictor Shoupによる文献“OAEP Reconsidered”Journal of Cryptology 15(4)（非特許文献３）で提案されたOAEP+と呼ばれるパディング方法が知られている。OAEP+パディングは以下のようなパディング方式である。【０００９】  まず、パラメータk, k0, k1を次のように選ぶ：k, k0, k1は正整数、かつ、k0 + k1 ≦ k ≦ L を満たす。ここで、L は平文空間の元の数である。【００１０】  さらに、n = k - k0 - k1とし、  Gは、kビットのビット列にnビットのビット列を対応させるハッシュ関数、  H'は、n+k0ビットのビット列にk1ビットのビット列を対応させるハッシュ関数、および、  Hは、n+k1ビットのビット列にk0ビットのビット列を対応させるハッシュ関数とする。【００１１】  パディング装置はnビットの平文Mを受け取り、k0ビットのビット列Rをランダムに選ぶ。続いて、G(R)とMのビット毎の排他的論理和s0を計算し、s1=H'(R||M)を計算し、s = s0||s1とする。ここで「||」はビット列の連接を表す。ｔをH(s)とRのビット毎の排他的論理和とし、w = s||tとする。このwを「平文Mの乱数Rを用いたOAEP+パディング」と呼ぶ。こうして得られたOAEP+パディングwを（乱数を使わない暗号方式で）暗号化し、暗号文eを受信者に送信する。【００１２】  受信者は、受信した暗号文eを復号し、wを得る。wを復号後、パディング復元装置は以下のようにして平文Mを復元する。まずwはw = s||t = s0||s1||tの形をしているので、これを使ってs0、s1、tを復元する。次にH(s)とtのビット毎の排他的論理和を取ることによりRを復元する。G(R)とs0のビット毎の排他的論理和を計算することによりMを復元する。s1 = H'(R||M)を満たせばMを出力し、満たさなければeは不正な暗号文として「⊥」を出力する。【００１３】  しかしながら、このOAEP+パディングは、暗号化関数を計算する際に乱数を使用しない暗号方式に対して適応するために提案されたパディング方式である。このために、上述したNTRUのような乱数を使用した暗号方式に適応した場合は必ずしも安全性が保証されないという問題がある。また、NTRUのような乱数を使用した暗号方式にOAEP+パディングを適応する場合には、適応方法は一意ではなく様々な方法を考えることができるために、どのようなパディングの適用方法が安全で、どのようなパディングの適用方法が安全でないかがすぐには分からないという問題もある。【００１４】  このようにOAEP+パディング方式は乱数を使用しない暗号方式に対してのみ安全性が保証できるのであるが、乱数を使用するNTRU暗号方式に対してOAEP+パディング方式ないしそれに類似したパディング方式を適応することで安全性を保証しようという試みもいくつか提案されている。たとえば、次の文献を参照されたい。【００１５】  ・Joseph H. Silvermanによる文献“Plaintext Awareness and the NTRU PKCS” Technical Report#7 version 2, NTRU Cryptosystems, 1998（非特許文献４）  ・Jeffrey Hoffstein、Joseph H. Silvermanによる文献“Optimizations for NTRU” Public-key Cryptography and Computational Number Theory（非特許文献５）  ・Jeffrey Hoffstein、Joseph H. Silvermanによる文献“Protecting NTRU Against Chosen Ciphertext and Reaction Attacks”Technical Report, NTRU Cryptosystems, 2000, Report#16 version 1（非特許文献６）  ・Phong Q. Nguyen、David Pointchevalによる文献“Analysis and Improvements of NTRU Encryption Paddings”Crypto 2002 Springer Lecture Notes in Computer Sciences, 2002（非特許文献７）。【００１６】  しかしながら、これらのパディングつきNTRU暗号方式はすべて解読された。非特許文献４に記載されたパディングを施したNTRU暗号方式は、Eliane Jaulmes、Antoine Jouxによる文献“A Chosen-Ciphertext Attack against NTRU”Crypto 2000 Springer Lecture Notes in Computer Sciences, 2000（非特許文献８）で提案されたアルゴリズムで解読された。【００１７】  また、非特許文献５および６に記載されたパディングを施したNTRU暗号方式は非特許文献７で提案されたアルゴリズムで解読され、この非特許文献７によるパディング方法はJohn A. Proosによる“Imperfect Decryption and an Attack on the NTRU Encryption Scheme”（非特許文献９)により解読された。【００１８】  OAEP+パディング方式以外のパディング方式を用いてNTRU暗号方式のような乱数を使った暗号方式の安全性確保を図った方式も提案されているが、パディング方式は方式毎に異なる弱点を持っているために、OAEP+パディングを用いて暗号方式の安全性を確保することは依然として有意義である。【非特許文献１】Jeffrey Hoffstein、Jill PipherおよびJoseph H. Silvermanによる文献“NTRU:A Ring-Based Public Key Cryptosystem”
【非特許文献２】“Lattice Attacks on NTRU”, Eurocrypt'97 Springer Lecture Notes in Computer Sciences,1997
【非特許文献３】“OAEP Reconsidered”Journal of Cryptology 15(4)
【非特許文献４】“Plaintext Awareness and the NTRU PKCS” Technical Report#7 version 2, NTRU Cryptosystems, 1998
【非特許文献５】Jeffrey Hoffstein、Joseph H. Silvermanによる文献“Optimizations for NTRU” Public-key Cryptography and Computational Number Theory
【非特許文献６】“Protecting NTRU Against Chosen Ciphertext and Reaction Attacks”Technical Report, NTRU Cryptosystems, 2000, Report#16 version 1
【非特許文献７】“Analysis and Improvements of NTRU Encryption Paddings”Crypto 2002 Springer Lecture Notes in Computer Sciences, 2002
【非特許文献８】“A Chosen-Ciphertext Attack against NTRU”Crypto 2000 Springer Lecture Notes in Computer Sciences, 2000
【非特許文献９】John A. Proosによる“Imperfect Decryption and an Attack on the NTRU Encryption Scheme”
【発明の開示】
【発明が解決しようとする課題】
【００１９】  上述したように、従来のパディングつきNTRU暗号方式は安全な暗号通信を行うことができない。【００２０】  本発明の目的はNTRU暗号方式のような方式に対して適切なパディングを施すことで安全な暗号通信を達成するパディング適用方法および暗号化／復号化装置を提供することにある。
【課題を解決するための手段】
【００２１】  本発明者は、NTRU暗号方式では暗号に使用した乱数を復元可能であることに着目し、暗号通信の安全性を保証できる新規なパディング適用方式を発明した。【００２２】  （成立根拠）  まず、本発明の成立根拠について簡単に説明する。乱数を使用した暗号方式で代表的なものに、エルガマル暗号方式やペイリエー暗号方式などがある。これらの暗号方式では、暗号文受信者が平文を復元することはできるが乱数を復元することはできないために、平文と乱数とは全く異なる種類のデータとして扱う必要がある。【００２３】  また、エルガマル暗号方式やペイリエー暗号方式等の多くの暗号方式では、暗号化関数は確率的な関数であり、暗号化関数の定義域は平文Ｍ全体の空間であり、値域は暗号文全体の空間である。それに対し、復号化関数は確率を使わない関数であり、定義域は暗号文全体の空間で値域は平文全体の空間である。繰り返すが、これらの暗号方式では暗号に使用した乱数を復元できない。【００２４】  これに対して、NTRU暗号方式は、平文mを復元した後に、r = (fe - fm)/pg により乱数rを求めることができる、という特徴がある。このため、NTRU暗号方式は、エルガマル暗号方式やペイリエー暗号方式等の暗号方式とは異なり、平文と乱数とを区別する必然性がない。【００２５】  したがって、NTRU暗号方式では、次のようにみなすことができる。【００２６】  ・暗号化関数は乱数を使わない関数であり、その定義域は平文Mと乱数Rとの連接全体の空間、値域は暗号文全体の空間である。【００２７】  ・復号化関数も乱数を使わない関数であり、その定義域は暗号文全体の空間、値域は平文Mと乱数Rとの連接全体の空間である。【００２８】  既に述べたようにOAEP+パディングは暗号化関数が乱数を使わない場合には安全性が保証される。したがって、NTRU暗号方式の平文と乱数とを区別しないデータ構造に対して、安全性保証つきOAEP+パディングを適用可能であることがわかる。【００２９】  （本発明の概要）  この知見に基づいて、本発明がなされた。すなわち、本発明によるパディング適用方式は、暗号文作成者が暗号文の作成に使用した乱数の値を暗号文受信者が復元できる暗号方式Er(m)に対して適用可能であり、このような暗号方式に対して本発明を適用した場合に安全性が保証される。【００３０】
本発明によれば、暗号文の作成に乱数を使用し、その使用した乱数を受信側で復元できる暗号化方式に対して、乱数を使用しない暗号化方式に対応するパディング方式を適用する方法は、送信側の通信端末に備えられているプロセッサが、入力情報を前記パディング方式により所定長以下のビット列に変換し、前記ビット列を所定の変換規則によって第１ビット列と第２ビット列とに変換し、前記第１ビット列をデータ入力とし、前記第２ビット列を乱数入力として暗号化関数にそれぞれ供給し、前記暗号化関数の出力を暗号文として出力し、前記変換規則は、前記所定長以下のビット列を前記第１ビット列の集合と第２ビット列の集合との直積の元に対応させる写像であり、かつ、前記写像は単射であること、前記写像およびその逆写像が多項式時間で計算可能であること、および、前記直積を定義域とする前記暗号化関数が一方向性関数であること、を満たす、ことを特徴とする。
【００３１】  本発明の一実施形態によれば、変換規則は、前記ビット列の前半を前記第１ビット列とし、後半を前記第２ビット列とするように前記ビット列を２分割する規則である。【００３２】  本発明の一実施例によれば前記パディング方式はＯＡＥＰ＋パディングであり、前記乱数を使用する暗号化方式はＮＴＲＵ暗号方式である。【００３３】  図１（Ａ）は、本発明によるパディング適用方式による暗号化装置の概念的ブロック図であり、（Ｂ）は従来例によるＯＡＥＰベースのパディング方式を適用した暗号化装置の概念的ブロック図である。ただし、パラメータは最も標準的な場合が示されており、n = k0 = k1であり、mのビット数はrである。【００３４】  図１（Ａ）を用いて本発明によるパディング適用方式を説明すると、おおよそ次のようになる。まず、OAEP+パディング方式と同様のパラメータを選ぶ。すなわち、上述したように、正整数k, k0, k1を k0 + k1 < k < L を満たすように取る。ここでLは平文空間の元の数である。n = k - k0 - k1とし、Gをkビットのビット列にnビットのビット列を対応させるハッシュ関数、H'をn+k0ビットのビット列にk1ビットのビット列を対応させるハッシュ関数、Hをn+k1ビットのビット列にk0ビットのビット列を対応させるハッシュ関数とする。【００３５】  次に、nビットの平文Mを受け取り、OAEP+パディングを行う。すなわちk0ビットのビット列Rをランダムに選び、G(R)とMのビット毎の排他的論理和s0を計算し、s1=H'(R||M)を計算して、s = s0||s1とする。記号「||」はビット列の連接を表す。tをH(s)とRのビット毎の排他的論理和とし、w = s||tとする。【００３６】  次に、wを次の条件を満たす規則A（以下、変換関数Aという。）を用いて２つのビット列mおよびrを生成する。Aは、kビット以下のビット列にLm × Lrの元を対応させる写像であり、ここでLmはmの取りうる範囲、Lrはrの取りうる範囲である。変換関数Aが満たすべき条件は次の通りである。【００３７】  （１）Aは単射であること  （２）Aおよびその逆写像は多項式時間で計算できること  （３）暗号化関数をE(m,r)とした時、写像E：A(X)→Leは、一方向性関数であること（ただしXは(m,r)の取りうる範囲を表し、Leは暗号文全体の空間を表す）。【００３８】  NTRU暗号方式の場合、例えばビット列wを前半のビット列と後半のビット列に等分割して、それぞれをmおよびrとすればよい。こうして２つのビット列に変換されると、e = Er(m)を計算して暗号化し、eを暗号文受信者に送信する。【００３９】  受信者はeを受信したら、eを復号してmを得る。上述したようにEr(m)の特徴によりrは復元可能であるから、rを復元する。そして、w = m||rによりwを復元する。wを復号後、OAEP+パディングの復元と同様にMを復元する。具体的には、まず、wはw = s||t =s0||s1||tの形をしているので、これを使ってs0、s1、tを復元する。次に、H(s)とtのビット毎の排他的論理和を取ることによりRを復元し、G(R)とs0のビット毎の排他的論理和を計算することによりMを復元する。s1 = H'(R||M)を満たせば、Mを出力し、そうでなければeは不正な暗号文として⊥を出力する。
【発明の効果】
【００４０】  次に、本発明による方式と従来の方式とを比較して、本発明の効果を説明する。図１（Ｂ）に一例を示すように、上述した非特許文献４〜７で提案された方式では、平文MからOAEP+(あるいはその他の)パディング方式を使ってmのみを作り上げ、rは何らかの別の手段を用いて作っている。これらの方式は、エルガマル暗号方式やペイリエー暗号方式のような受信側で平文だけが復元でき乱数は復元できない暗号方式に対しても利用できるが、ad-hocな方法であるため安全性が保証できず、特にNTRUの場合には完全解読が可能である。【００４１】  これに対して、本発明による方式は、NTRUのような暗号文受信者が平文および乱数を共に復元できる暗号方式に適用されるパディング方式である。上記の従来の方式とは異なり、平文MからOAEP+パディング方式および所定の変換規則（関数A）を使ってmおよびrの両方を作り上げる。また、従来の方式とは異なり、NTRUのような暗号文受信者が平文および乱数をともに復元できる暗号方式に対して適用した場合に安全性が保証できる。【００４２】  すなわち、本発明により、NTRU暗号方式という必要メモリ量の少なくかつ暗号化復号化計算が高速な暗号方式を利用して安全な暗号通信を行うことが可能になる。
【発明を実施するための最良の形態】
【００４３】  図２は、本発明による暗号化／復号化装置を実装した暗号通信システムの一例を示すブロック図である。ここではネットワークを通して通信端末間で暗号通信が行われる。【００４４】  送信側の通信端末は、プログラム制御プロセッサ１０、乱数生成器１１、プログラムメモリ１２、メモリ１３および送受信部１４を有し、後述するように、プログラムメモリ１２に格納されたOAEP＋変換、変換関数Aによる変換、NTRU暗号化などの必要なプログラムを実行することで平文を暗号化し、暗号文を送受信部１４からネットワークを通して宛先の受信端末へ送信する。なお、メモリ１３には、公開情報や秘密鍵などの暗号化に必要な情報が格納されている。【００４５】  受信端末も同様に、プログラム制御プロセッサ２０、乱数生成器２１、プログラムメモリ２２、メモリ２３および送受信部２４を有し、後述するように、プログラムメモリ２２、メモリ１３および送受信部１４を有し、後述するように、プログラムメモリ２２に格納されたNTRU復号化、乱数復元、逆変換、OAEP＋逆変換などの必要なプログラムを実行することで、送受信部２４で受信した暗号文を平文に復号する。なお、メモリ２３には、公開情報や秘密鍵などの復号化に必要な情報が格納されている。【００４６】  １．第１実施形態  図３は、本発明の第１実施形態による暗号化／復号化装置の機能的構成を示すブロック図である。本実施形態による暗号化／復号化装置は、平文を暗号化するための暗号化装置１００と、暗号文を平文に復号するための復号化装置２００とを有し、さらに鍵生成装置３００により生成された暗号化／復号化に必要な公開情報を記憶する公開情報記憶装置３０１、復号化に必要な秘密鍵情報を記憶する秘密鍵記憶装置３０２を有する。【００４７】  平文は、平文入力装置１０１により暗号化装置１００へ与えられ、暗号化装置１００にはOAEP+変換部１０２、変換関数Aによる変換部１０３およびNTRU暗号化部１０４などのプロセスが実現されている。暗号化装置１００により生成された暗号文は暗号文出力装置１０５を通して、例えば受信端末へ出力される。【００４８】  暗号文は、暗号文入力装置２０１により復号化装置２００へ与えられ、復号化装置２００にはNTRU復号化部２０２、乱数復元部２０３、変換関数Aの逆変換部２０４、OAEP+逆変換部２０５などのプロセスが実現されている。復号化装置２００により生成された平文は平文出力装置２０６を通して出力される。【００４９】  １．１）鍵生成  まず鍵生成手順を説明する。【００５０】  図４は、第１実施形態における鍵生成手順を示すフローチャートである。鍵生成装置３００は、正整数p, q, Nをとり、領域変数として公開する。上述したNTRU暗号方式と同様に、R = Z[X]/(XN-1)とし、Rの元uであってuの各次数の係数のうちa個が1でb個が-1、他のものが0であるもの全体の集合（Rの部分集合）をL(a,b)で表すものとし、Rの部分集合Lf, Lg, Lr, Lmを取る（ステップＳ１１）。【００５１】
さらに鍵生成装置３００は、OAEP+パディング方式で説明したように、パラメータk, k0, k1を次のように選ぶ：k, k0, k1は正整数、かつ、k0 + k1 ≦ k ≦ Lを満たす。ここで、LはLm × Lrの元の数である。さらに、n = k - k0 - k1とし、
Gは、kビットのビット列にnビットのビット列を対応させるハッシュ関数、
H'は、n+k0ビットのビット列にk1ビットのビット列を対応させるハッシュ関数、および、
Hは、n+k1ビットのビット列にk0ビットのビット列を対応させるハッシュ関数とする（ステップＳ１２)。
【００５２】
さらに、鍵生成装置３００は変換関数Aを決定する（ステップＳ１３）。変換関数Aはkビット以下のビット列にLm × Lrの元を対応させる写像とし、以下の性質を満たさねばならない。
【００５３】  （１）Aは単射であること  （２）Aおよびその逆写像が多項式時間で計算できること  （３）暗号化関数をE(m, r)とした時、写像E：A(X)→Leは、一方向性関数であること（ただし、Xは(m, r)の取りうる範囲を表し、Leは暗号文全体の空間を表す）。【００５４】
鍵生成装置３００は、NTRUと同様の方法で鍵生成を実行する。すなわちLfからfを、Lgからgをランダムに取り、h = f-1g mod q とする。f, gを秘密鍵とし、hを公開鍵とする（ステップＳ１４）。鍵生成装置３００は、f, gを秘密鍵記憶装置３０２に秘密裡に保持し（ステップＳ１５）、NTRUの公開鍵、上記ハッシュ関数および変換関数（p, q, N, Lf, Lg, Lr, Lm, k, k0, k1, G, H', H, A, h）を公開情報記憶装置３０１に格納して公開する（ステップＳ１６）。
【００５５】  １．２）暗号化手順  次に暗号化手順を説明する。【００５６】  図５は、第１実施形態における暗号化手順を示すフローチャートである。暗号化装置１００は、まず平文入力装置１０１からnビットの平文Mを受け取り（ステップＳ２１）、公開情報記憶装置３０１から公開情報p, q, N, Lf, Lg, Lr, Lm, k, k0, k1, G, H', H, A, およびhを受け取る（ステップＳ２２）。【００５７】  続いて、k0ビットのビット列Rをランダムに選び（ステップＳ２３）、OAEP+変換部１０２は、G(R)とMのビット毎の排他的論理和s0を計算し、s1=H'(R||M)を計算し、s = s0||s1とし、さらに、tをH(s)とRのビット毎の排他的論理和として、w = s||tを生成することで、平文をOAEP+パディングする（ステップＳ２４）。【００５８】  さらに、変換部１０３は変換関数Aを用いて、(m, r)=A(w)によって、wを２つのビット列mおよびrに変換する（ステップＳ２５）。ここでは、wを等分割して前半のビット列をm、後半のビット列をｒとする。そして、NTRU暗号化部１０４は、e = phr + m mod qを計算することでNTRU暗号化を行い（ステップＳ２６）、生成された暗号文を暗号文出力装置１０５から出力する（ステップＳ２７）。【００５９】  １．３）復号化手順  最後に復号化手順を説明する。【００６０】  図６は、第１実施形態における復号化手順を示すフローチャートである。まず復号化装置２００は暗号文入力装置２０１から暗号文eを受け取り（ステップＳ３１）、続いて、秘密鍵記憶装置３０２から暗号文に対応する秘密鍵を、公開情報記憶装置３０１からその秘密鍵に対応する公開情報を受け取る（ステップＳ３２）。【００６１】  NTRU復号部２０２は、公開情報および秘密鍵を用いて、NTRU暗号方式と同様に暗号文ｅの復号化処理を行う。すなわち、fe = pgr + fm mod qを計算し、f, g, r, mがそれぞれLf、Lg、Lr、Lmの元であることからfe = pgr + fmであるので、fe (mod p) = m (mod p)を計算することができ、mがLmの元であることからm = m (mod p)なので、mを復元できる（ステップＳ３３）。【００６２】  また、乱数復元部２０３は、fe = pgr + fmであるので、r = (fe - fm)/pgによりrを復元する（ステップＳ３４）。【００６３】  次に、逆変換部２０４は変換関数Aの逆変換を用いて、A-1(m,r)により、w = s||t = s0||s1||tを復元する（ステップＳ３５）。続いて、OAEP+逆変換部２０５は、H(s)とtのビット毎の排他的論理和を取ることによりRを復元し、G(R)とs0のビット毎の排他的論理和を計算することによりMを復元する（ステップＳ３６）。【００６４】  最後に、パディングが正当であるか否かをs1 = H'(R||M)が満たされるか否かによって判断し（ステップＳ３７）、正当であれば平文Mを出力し（ステップＳ３８）、正当でなければ暗号文eは不正な暗号文として⊥を出力する（ステップＳ３９）。【００６５】  ２．第２実施形態  図７は、本発明の第２実施形態による暗号化／復号化装置の機能的構成を示すブロック図である。本実施形態による暗号化／復号化装置は、平文を暗号化するための暗号化装置４００と、暗号文を平文に復号するための復号化装置５００とを有し、さらに鍵生成装置３００により生成された暗号化／復号化に必要な公開情報を記憶する公開情報記憶装置３０１、復号化に必要な秘密鍵情報を記憶する秘密鍵記憶装置３０２を有する。【００６６】  平文は、平文入力装置１０１により暗号化装置４００へ与えられ、暗号化装置４００には乱数発生部４０１、秘密鍵暗号化部４０２、OAEP+変換部４０３、変換関数Aによる変換部４０４およびNTRU暗号化部４０５などのプロセスが実現されている。暗号化装置４００により生成された暗号文は暗号文出力装置１０５を通して、例えば受信端末へ出力される。【００６７】  暗号文は、暗号文入力装置２０１により復号化装置５００へ与えられ、復号化装置５００にはNTRU復号化部５０１、乱数復元部５０２、変換関数Aの逆変換部５０３、OAEP+逆変換部５０４、秘密鍵暗号復号部５０５などのプロセスが実現されている。復号化装置５００により生成された平文は平文出力装置２０６を通して出力される。【００６８】  ２．１）鍵生成  まず鍵生成手順を説明する。【００６９】  図８は、第２実施形態における鍵生成手順を示すフローチャートである。鍵生成装置３００は、正整数p, q, Nをとり、領域変数として公開する。上述したNTRU暗号方式と同様に、R = Z[X]/(XN-1)とし、Rの元uであってuの各次数の係数のうちa個が1でb個が-1、他のものが0であるもの全体の集合（Rの部分集合）をL(a,b)で表すものとし、Rの部分集合Lf, Lg, Lr, Lmを取る（ステップＳ４１）。【００７０】
さらに鍵生成装置３００は、OAEP+パディング方式で説明したように、パラメータk, k0, k1を次のように選ぶ：k, k0, k1は正整数、かつ、k0 + k1 ≦ k ≦ Lを満たす。ここで、LはLm × Lrの元の数である。さらに、n = k - k0 - k1とし、
Gは、kビットのビット列にnビットのビット列を対応させるハッシュ関数、
H'は、n+k0ビットのビット列にk1ビットのビット列を対応させるハッシュ関数、および、
Hは、n+k1ビットのビット列にk0ビットのビット列を対応させるハッシュ関数とする（ステップＳ４２)。
【００７１】
さらに、鍵生成装置３００は変換関数Aを決定する（ステップＳ４３）。変換関数Aは、上述したように、kビット以下のビット列にLm × Lrの元を対応させる写像とし、以下の性質を満たさねばならない。
【００７２】  （１）Aは単射であること  （２）Aおよびその逆写像が多項式時間で計算できること  （３）暗号化関数をE(m, r)とした時、写像E：A(X)→Leは、一方向性関数であること（ただし、Xは(m, r)の取りうる範囲を表し、Leは暗号文全体の空間を表す）。【００７３】
鍵生成装置３００は、NTRUと同様の方法で鍵生成を実行する。すなわちLfからfを、Lgからgをランダムに取り、h = f-1g mod q とする。f, gを秘密鍵とし、hを公開鍵とする。鍵生成装置３００は、f, gを秘密鍵記憶装置３０２に秘密裡に保持し（ステップＳ４４）する。
【００７４】
さらに、鍵生成装置３００は、使用する共通鍵鍵暗号方式Eを決定し（ステップＳ４５）、NTRUの公開鍵、上記ハッシュ関数および変換関数（p, q, N, Lf, Lg, Lr, Lm, k, k0, k1, G, H', H, A, h）を公開情報記憶装置３０１に格納して公開する（ステップＳ４６）。
【００７５】  ２．２）暗号化手順  次に暗号化手順を説明する。【００７６】  図９は、第２実施形態における暗号化手順を示すフローチャートである。暗号化装置４００は、まず平文入力装置１０１からnビットの平文Xを受け取り（ステップＳ５１）、公開情報記憶装置３０１から公開情報p, q, N, Lf, Lg, Lr, Lm, k, k0, k1, G, H', H, A,およびhを受け取る（ステップＳ５２）。【００７７】  続いて、乱数発生部４０１を用いて秘密鍵暗号化部４０２はnビットのビット列Mをランダムに選び（ステップＳ５３）、Y = EM(X)を計算して共通化鍵暗号化を行う（ステップＳ５４）。ここで、EM(X)は、Mを鍵として平文Xを共通鍵暗号方式Eに従って暗号化したものである。【００７８】  続いて、k0ビットのビット列Rをランダムに選び（ステップＳ５５）、OAEP+変換部４０３は、G(R)とMのビット毎の排他的論理和s0を計算し、s1=H'(R||M)を計算し、s = s0||s1とし、さらに、tをH(s)とRのビット毎の排他的論理和として、w = s||tを生成することで、平文をOAEP+パディングする（ステップＳ５６）。【００７９】  さらに、変換関数Aによる変換部４０４は、(m, r) = A(w)によってwを２つのビット列mおよびrに変換する（ステップＳ５７）。ここでは、wを２分割して前半のビット列をm、後半のビット列をｒとする。そして、NTRU暗号化部４０５は、e = phr + m mod qを計算することでNTRU暗号化を行い（ステップＳ５８）、生成された暗号文ｅと共通鍵暗号の暗号文Ｙとを暗号文（ｅ，Ｙ）として暗号文出力装置１０５から出力する（ステップＳ５９）。【００８０】  ２．３）復号化手順  最後に復号化手順を説明する。【００８１】  図１０は、第２実施形態における復号化手順を示すフローチャートである。まず復号化装置５００は暗号文入力装置２０１から暗号文eを受け取り（ステップＳ６１）、続いて、秘密鍵記憶装置３０２から暗号文に対応する秘密鍵を、公開情報記憶装置３０１からその秘密鍵に対応する公開情報を受け取る（ステップＳ６２）。【００８２】  NTRU復号化部５０１は、公開情報および秘密鍵を用いて、NTRU暗号方式と同様に暗号文ｅの復号化処理を行う。すなわち、fe = pgr + fm mod qを計算し、f, g, r, mがそれぞれLf、Lg、Lr、Lmの元であることからfe = pgr + fmであるので、fe(mod p) = m (mod p)を計算することができ、mがLmの元であることからm = m (mod p)なので、mを復元できる（ステップＳ６３）。【００８３】  また、乱数復元部５０２は、fe = pgr + fmであるので、r = (fe - fm)/pgによりrを復元する（ステップＳ６４）。【００８４】  次に、逆変換部５０３は、A-1(m,r)により、w = s||t = s0||s1||tを復元する（ステップＳ６５）。続いて、OAEP+逆変換部５０４は、H(s)とtのビット毎の排他的論理和を取ることによりRを復元し、G(R)とs0のビット毎の排他的論理和を計算することによりMを復元する（ステップＳ６６）。【００８５】  最後に、パディングが正当であるか否かをs1 = H'(R||M)が満たされるか否かによって判断し（ステップＳ６７）、正当であれば、共通鍵暗号の鍵Mを用いて共通鍵暗号を解き、平文Xを出力し（ステップＳ６８）、正当でなければ暗号文eは不正な暗号文として⊥を出力する（ステップＳ６９）。
【図面の簡単な説明】
【００８６】
【図１】（Ａ）は、本発明によるパディング適用方式による暗号化装置の概念的ブロック図であり、（Ｂ）は従来例によるＯＡＥＰベースのパディング方式を適用した暗号化装置の概念的ブロック図である。
【図２】本発明による暗号化／復号化装置を実装した暗号通信システムの一例を示すブロック図である。
【図３】本発明の第１実施形態による暗号化／復号化装置の機能的構成を示すブロック図である。
【図４】第１実施形態における鍵生成手順を示すフローチャートである。
【図５】第１実施形態における暗号化手順を示すフローチャートである。
【図６】第１実施形態における復号化手順を示すフローチャートである。
【図７】本発明の第２実施形態による暗号化／復号化装置の機能的構成を示すブロック図である。
【図８】第２実施形態における鍵生成手順を示すフローチャートである。
【図９】第２実施形態における暗号化手順を示すフローチャートである。
【図１０】第２実施形態における復号化手順を示すフローチャートである。
【符号の説明】
【００８７】  １００    暗号化装置  １０１    平文入力装置  １０２    ＯＡＥＰ＋変換部  １０３    変換関数Aによる変換部  １０４    ＮＴＲＵ暗号化部  １０５    暗号文出力装置  ２００    復号化装置  ２０１    暗号文入力装置  ２０２    ＮＴＲＵ復号化部  ２０３    乱数復元部  ２０４    変換関数Aの逆変換部  ２０５    ＯＡＥＰ＋逆変換部  ２０６    平文出力装置  ３００    鍵生成装置  ３０１    公開情報記憶装置  ３０２    秘密鍵記憶装置
【図１】
0004715748.tif 000002
【図２】
0004715748.tif 000003
【図３】
0004715748.tif 000004
【図４】
0004715748.tif 000005
【図５】
0004715748.tif 000006
【図６】
0004715748.tif 000007
【図７】
0004715748.tif 000008
【図８】
0004715748.tif 000009
【図９】
0004715748.tif 000010
【図１０】
0004715748.tif 000011