(57)【特許請求の範囲】
【請求項１】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをZ*pにおける位数ｑの元とし、これらのｐ、ｑ、ｇを上記両公開鍵の一部のパラメータの共通とされたものとし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｅs を秘密鍵暗号関数とし、EsK(m)は鍵Ｋで平文ｍを暗号化してできる暗号文を表し、Ｄs をＥs に対応する秘密鍵復号関数とし、ＤsK(C) は鍵Ｋで暗号文Ｃを復号して得られる平文を表すものとし、
送信者端末はＺq に属する署名鍵ｘをランダムに生成し、y=gx mod pを計算し、署名検証鍵ｙとして公開し、
受信者端末はZqに属する復号鍵ｄをランダムに生成し、e=gd mod pを計算し、暗号鍵ｅとして公開し、
送信時に、送信者端末はＺq に属する乱数ｗを生成し、K=H1(ew mod p)を計算してセッション鍵Ｋを生成し、メッセージｍに対しＫを用いてC=EsK(m)を演算して暗号文Ｃを生成し、W=gw mod p、b=H2(W‖C)，a=w-bx mod qを計算して署名ａ，ｂを生成し、送信文Σ＝（Ｃ，ａ，ｂ）を受信者端末へ送信し、
Σ＝（Ｃ，ａ，ｂ）を受信した受信者端末は、まず、W'=gayb mod pを計算し、b=H2(W' ‖C)が成り立つことを検証し、成り立たない場合は、受信文Σを破棄し、成り立つ場合は、K=H1((W')d mod p)を計算し、m=DsK(C)を計算して平文ｍを得る
ことを特徴とする署名付き暗号通信方法。
【請求項２】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、これらのｐ、ｑ、ｇを上記両公開鍵の一部のパラメータの共通とされたものとし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｅs を秘密鍵暗号関数とし、ＥsK(m)は鍵Ｋで平文ｍを暗号化してできる暗号文を表し、Ｄs をＥs に対応する秘密鍵復号関数とし、ＤsK(C) は鍵Ｋで暗号文Ｃを復号して得られる平文を表すものとし、
送信者端末はＺq に属する署名鍵ｘをランダムに生成し、y=gx mod pを計算し、署名検証鍵ｙとして公開し、
受信者端末はＺq に属する復号鍵ｄをランダムに生成し、e=gd mod pを計算し、暗号鍵ｅとして公開し、
送信時に、送信者端末はＺｑに属する乱数ｗを生成し、K=H1(ew mod p)を計算してセッション鍵Ｋを生成し、メッセージｍに対しＫを用いてC=EsK(m)を演算して暗号文Ｃを生成し、b=H2(K‖C)，b=H2(W‖C‖K)（Ｗはｇw mod p）の何れかとa=w-bx mod qを計算して署名ａ，ｂを生成し、送信文Σ＝（Ｃ，ａ，ｂ）を受信者端末へ送信し、
Σ＝（Ｃ，ａ，ｂ）を受信した受信者端末は、Ｗ＝gayb mod p，K=H1(Ｗd mod p)を計算し、b=H2(K‖C)，b=H2(W‖C‖K)の送信者端末でのｂの計算と対応したものが成り立つことを検証し、成り立たない場合は、受信文Σを破棄し、成り立つ場合は、m=DsK(C)を演算して平文ｍを求める
ことを特徴とする署名付き暗号通信方法。
【請求項３】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、これらのｐ、ｑ、ｇを上記両公開鍵の一部のパラメータの共通とされたものとし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｅs を秘密鍵暗号関数とし、ＥsK(m)は鍵Ｋで平文ｍを暗号化してできる暗号文を表し、Ｄs をＥs に対応する秘密鍵復号関数とし、ＤsK(C) は鍵Ｋで暗号文Ｃを復号して得られる平文を表すものとし、
送信者端末はＺq に属する署名鍵ｘをランダムに生成し、y=gx mod pを計算し、署名検証鍵ｙとして公開し、
受信者端末はＺq に属する復号鍵ｄをランダムに生成し、e=gd mod pを計算し、暗号鍵ｅとして公開し、
送信時に、送信者端末はＺｑに属する乱数ｗを生成し、K=H1(ew mod p)を計算してセッション鍵Ｋを生成し、メッセージｍに対しＫを用いてC=EsK(m)を演算して暗号文Ｃを生成し、b=H2(W‖C‖ｍ)，（Ｗはｇw mod p），b=H2(C‖ｍ)の何れかとa=w-bx mod qを計算して署名ａ，ｂを生成し、送信文Σ=（Ｃ，ａ，ｂ）を受信者端末へ送信し、
Σ=（Ｃ，ａ，ｂ）を受信した受信者端末は、Ｗ=gayb mod p，K=H1(Ｗd mod p)を計算し、ｍ=ＤKs（Ｃ）を演算し、b=H2(W‖C‖ｍ)，ｂ=H2(C‖ｍ)の送信者端末でのｂの計算と対応したものが成り立つことを検証し、成り立たない場合は、受信文Σを破棄し、成り立つ場合は、ｍを正しい平文とする
ことを特徴とする署名付き暗号通信方法。
【請求項４】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、これらのｐ、ｑ、ｇを上記公開鍵の一部のパラメータの共通とされたものとし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｅs を秘密鍵暗号関数とし、ＥsK(m)は鍵Ｋで平文ｍを暗号化してできる暗号文を表し、Ｄs をＥs に対応する秘密鍵復号関数とし、ＤsK(C) は鍵Ｋで暗号文Ｃを復号して得られる平文を表すものとし、
送信者端末はＺq に属する署名鍵ｘをランダムに生成し、y=gx mod pを計算し、署名検証鍵ｙとして公開し、
受信者端末はＺq に属する復号鍵ｄをランダムに生成し、e=gd mod pを計算し、暗号鍵ｅとして公開し、
送信時に送信者端末はメッセージｍを、ハッシュ関数Ｈ4，Ｈ5及びビット毎排他的論理和（＋）を用いてm'=m(+)H5(H4(m))‖H4(m)と変換し、Ｚｑに属する乱数ｗを生成し、K=H1(ew mod p)を計算してセッション鍵Ｋを生成し、上記変換されたメッセージｍ’に対しＫを用いてC=EsK(m')を演算して暗号文Ｃを生成し、b=H2(C)，a=w-bx mod qを計算して署名ａを生成し、送信文Σ＝（Ｃ，ａ）を受信者端末へ送信し、
Σ＝（Ｃ，ａ）を受信した受信者端末は、b=H2(C)，K=H1((gayb)d mod p)を計算し、このＫを用いてm'=DsK(C)を計算して平文m'をm'＝Ａ‖ＢとしてＢがＨ4（・）の出力ビット数と同じになるようにm'をＡとＢに分割し、H4(H5(B)(+)A)=Bが成り立つか否かを検証し、成り立たない場合は、受信文Σを不正とみなし、成り立つ場合は受信文を正しいものとみなす
ことを特徴とする署名付き暗号通信方法。
【請求項５】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｅs を秘密鍵暗号関数とし、ＥsK(m)は鍵Ｋで平文ｍを暗号化してできる暗号文とし、ｄをＺqからランダムに選ばれた復号鍵とするとき、公開暗号鍵をe=gd mod pとし、ｘをＺqからランダムに選ばれた署名鍵とし、
ｐ，ｑ，ｇ，ｘ，ｅが記憶されたメモリと、
Ｚqに属する乱数ｗを生成して出力する乱数生成器と、
ｗ，ｅ，ｐが入力され、ew mod pを計算してその結果を出力する第１べき乗剰余演算器と、
ew mod pの計算結果が入力され、K=H1(ew mod p)を計算してセッション鍵Ｋを生成して出力する第１ハッシュ器と、
メッセージｍとセッション鍵Ｋが入力され、C=EsK(m)を計算して暗号文Ｃを生成して出力する暗号器と、
ｗ，ｇ，ｐが入力されW=gw mod pを計算してその結果を出力する第２べき乗剰余演算器と、
ＣとＷが入力され、b=H2(W‖C)を計算してｂを出力する第２ハッシュ器と、
ｂとｘ，ｑ，ｗが入力され、a=w-bx mod qを計算してａを出力する剰余乗算・減算器と、
暗号文Ｃと署名ａ及びｂを送信文（Ｃ，ａ，ｂ）として受信者端末へ送信する送信器と、
を具備する送信者端末。
【請求項６】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｅs を秘密鍵暗号関数とし、ＥsK(m)は鍵Ｋで平文ｍを暗号化してできる暗号文とし、ｄをＺqからランダムに選ばれた復号鍵とするとき、公開暗号鍵をe=gd mod pとし、ｘをＺqからランダムに選ばれた署名鍵とし、
ｐ，ｑ，ｇ，ｘ，ｅが記憶されたメモリと、
Ｚqに属する乱数ｗを生成して出力する乱数生成器と、
ｗ，ｅ，ｐが入力され、ew mod pを計算してその結果を出力する第１べき乗剰余演算器と、
ew mod pの計算結果が入力され、K=H1(ew mod p)を計算してセッション鍵Ｋを生成して出力する第１ハッシュ器と、
メッセージｍとセッション鍵Ｋが入力され、C=EsK(m)を計算して暗号文Ｃを生成して出力する暗号器と、
ｗ，ｇ，ｐが入力されW'=gw mod pを計算してその結果を出力する第２べき乗剰余演算器と、
ＣとＫが入力され、b=H2(K‖C)を計算してｂを出力する第２ハッシュ器と、
ｂとｘ，ｑ，ｗが入力され、a=w-bx mod qを計算してａを出力する剰余乗算・減算器と、
暗号文Ｃと署名ａ及びｂを送信文（Ｃ，ａ，ｂ）として受信者端末へ送信する送信器と、
を具備する送信者端末。
【請求項７】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、Ｈ1(・)、Ｈ2(・)、Ｈ4(・)、Ｈ5(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｅs を秘密鍵暗号関数とし、ＥsK(m)は鍵Ｋで平文ｍを暗号化してできる暗号文とし、ｄをＺqからランダムに選ばれた復号鍵とするとき、公開暗号鍵をe=gd mod pとし、ｘをＺqからランダムに選ばれた署名鍵とし、
ｐ，ｑ，ｇ，ｘ，ｅが記憶されたメモリと、
メッセージｍが入力され、m'=m(+)H5(H4(m))‖H4(m)を演算してｍ’を出力するメッセージ変換器と、
Ｚqに属する乱数ｗを生成して出力する乱数生成器と、
ｗ，ｅ，ｐが入力され、ew mod pを計算してその結果を出力する第１べき乗剰余演算器と、
ew mod pの計算結果が入力され、K=H1(ew mod p)を計算してセッション鍵Ｋを生成して出力する第１ハッシュ器と、
メッセージｍとセッション鍵Ｋが入力され、C=EsK(m)を計算して暗号文Ｃを生成して出力する暗号器と、
Ｃが入力され、b=H2(C)を計算してｂを出力する第２ハッシュ器と、
ｂとｘ，ｑ，ｗが入力され、a=w-bx mod qを計算してａを出力する剰余乗算・減算器と、
暗号文Ｃと署名ａを送信文（Ｃ，ａ）として受信者端末へ送信する送信器と、
を具備する送信者端末。
【請求項８】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｄs を秘密鍵復号関数とし、ＤsK(Ｃ)を鍵Ｋで暗号文Ｃを復号して得られる平文を表し、復号鍵ｄはＺqからランダムに選ばれたものとし、Ｚqに属する署名鍵ｘに対する署名検証鍵ｙをgx mod pとし、
ｐ，ｑ，ｇ，ｄ，ｙが記憶されたメモリと、
送信者端末からの受信信号より受信文（Ｃ，ａ，ｂ）を出力する受信器と、
受信したａ，ｂとメモリからのｇ，ｐ，ｙが入力され、W'=gayb mod pを計算してＷ’を出力する第１べき乗剰余演算器と、
Ｗ’と受信したＣが入力され、Ｈ2（Ｗ’‖Ｃ）を計算してその結果を出力するハッシュ器と、
Ｈ2（Ｗ’‖Ｃ）の計算結果と受信したｂが入力され、両者が一致するか否かに応じた署名検証結果を出力する比較器と、
上記Ｗ’が入力され、(W')d mod pを計算し、その結果を出力する第２べき乗剰余演算器と、
第２べき乗剰余演算器の計算結果が入力され、K=H1((W')d mod p)を計算し、鍵Ｋを出力する第２ハッシュ器と、
Ｋと受信したＣが入力され、m=DsK(C)を計算して計算結果を復号平文ｍとして出力する復号器と、
を具備する受信者端末。
【請求項９】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｄs を秘密鍵復号関数とし、ＤsK(Ｃ)を鍵Ｋで暗号文Ｃを復号して得られる平文を表し、復号鍵ｄはＺqからランダムに選ばれたものとし、Ｚqに属する署名鍵ｘに対する署名検証鍵ｙをgx mod pとし、
ｐ，ｑ，ｇ，ｄ，ｙが記憶されたメモリと、
送信者端末からの受信信号より受信文（Ｃ，ａ，ｂ）を出力する受信器と、
受信したａ，ｂとメモリからのｇ，ｐ，ｙ，ｄが入力され、W'=(gayb)d mod pを計算してその結果Ｗ'を出力する第１べき乗剰余演算器と、
Ｗ’が入力され、Ｋ＝Ｈ1(W')を計算して鍵Ｋを出力する第１ハッシュ器と、
Ｋと受信したＣが入力され、Ｈ2（Ｋ‖Ｃ）を計算してその結果を出力する第２ハッシュ器と、
Ｈ2（Ｋ‖Ｃ）の計算結果と受信したｂが入力され、両者が一致するか否かに応じた署名検証結果を出力する比較器と、
Ｋと受信したＣが入力され、m=DsK(C)を計算して計算結果を復号平文ｍとして出力する復号器と、
を具備する受信者端末。
【請求項１０】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、Ｈ1(・)、Ｈ2(・)、Ｈ4(・)、Ｈ5(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｄs を秘密鍵復号関数とし、ＤsK(Ｃ)を鍵Ｋで暗号文Ｃを復号して得られる平文を表し、復号鍵ｄはＺqからランダムに選ばれたものとし、Ｚqに属する署名鍵ｘに対する署名検証鍵ｙをgx mod pとし、
ｐ，ｑ，ｇ，ｄ，ｙが記憶されたメモリと、
送信者端末からの受信信号より受信文（Ｃ，ａ）を出力する受信器と、
受信したＣが入力され、ｂ＝Ｈ2(C)を計算してｂを出力する第１ハッシュ器と、
上記ｂと受信したａとメモリからのｇ，ｐ，ｙ，ｄが入力され、W'=(gayb)d mod pを計算してＷ’を出力する第１べき乗剰余演算器と、
Ｗ’が入力され、Ｋ＝Ｈ1(W')を演算してＫを出力する第２ハッシュ器と、
Ｋと受信したＣが入力され、m=DsK(C)を計算して平文ｍ’を出力する復号器と、
ｍ’が入力され、ｍ’＝Ａ‖Ｂとして、ＢがＨ4(・)の出力ビット数と同一ビット数になるようにｍ’をＡ，Ｂに分割する分割器と、
ＡとＢが入力され、H4(H5(B)(+)A)（N(+)MはＮとＭのビット毎の排他的論理和演算を表す）を計算し、その結果を出力すると共にその途中演算結果m=H5(B)(+)Aを復号されたメッセージとして出力する演算器と、
その演算器の演算結果H4(H5(B)(+)A)とＢが入力され、両者が一致するか否かに応じた署名検証結果を出力する比較器と、
を具備する受信者端末。
【請求項１１】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｅs を秘密鍵暗号関数とし、ＥsK(m)は鍵Ｋで平文ｍを暗号化してできる暗号文とし、ｄをＺqからランダムに選ばれた復号鍵とするとき、公開暗号鍵をe=gd mod pとし、ｘをＺqからランダムに選ばれた署名鍵とし、
ｐ，ｑ，ｇ，ｘ，ｅが記憶されたメモリと、
Ｚqに属する乱数ｗを生成して出力する乱数生成器と、
ｗ，ｅ，ｐが入力され、ew mod pを計算してその結果を出力する第１べき乗剰余演算器と、
ew mod pの計算結果が入力され、K=H1(ew mod p)を計算してセッション鍵Ｋを生成して出力する第１ハッシュ器と、
メッセージｍとセッション鍵Ｋが入力され、C=EsK(m)を計算して暗号文Ｃを生成して出力する暗号器と、
ｗ，ｇ，ｐが入力されW'=gw mod pを計算してその結果を出力する第２べき乗剰余演算器と、
ＣとＸ（ＸはＷ‖Ｋ，Ｗ‖ｍ，ｍの何れか）が入力され、b=H2(Ｘ‖C)を計算してｂを出力する第２ハッシュ器と、
ｂとｘ，ｑ，ｗが入力され、a=w-bx mod qを計算してａを出力する剰余乗算・減算器と、
暗号文Ｃと署名ａ及びｂを送信文（Ｃ，ａ，ｂ）として受信者端末へ送信する送信器と、
を具備する送信者端末。
【請求項１２】
ｐ、ｑを、ｑが（ｐ−１）を割り切る大きな素数とし、ｇをＺ*pにおける位数ｑの元とし、Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すものとし、Ｄs を秘密鍵復号関数とし、ＤsK(Ｃ)を鍵Ｋで暗号文Ｃを復号して得られる平文を表し、復号鍵ｄはＺqからランダムに選ばれたものとし、Ｚqに属する署名鍵ｘに対する署名検証鍵ｙをgx mod pとし、
ｐ，ｑ，ｇ，ｄ，ｙが記憶されたメモリと、
送信者端末からの受信信号より受信文（Ｃ，ａ，ｂ）を出力する受信器と、
受信したａ，ｂとメモリからのｇ，ｐ，ｙが入力され、W'=gayb mod pを計算してＷ’を出力する第１べき乗剰余演算器と、
上記Ｗ’が入力され、(W')d mod pを計算し、その結果を出力する第２べき乗剰余演算器と、
第２べき乗剰余演算器の計算結果が入力され、K=H1((W')d mod p)を計算し、鍵Ｋを出力する第２ハッシュ器と、
Ｋと受信したＣが入力され、m=DsK(C)を計算して計算結果を復号平文ｍとして出力する復号器と、
Ｘ（ＸはＷ’‖Ｋ，Ｗ’‖ｍ‖，ｍの何れか）と受信したＣが入力され、Ｈ2（Ｘ‖Ｃ）を計算してその結果を出力するハッシュ器と、
Ｈ2（Ｘ‖Ｃ）の計算結果と受信したｂが入力され、両者が一致するか否かに応じた署名検証結果を出力する比較器と、
を具備する受信者端末。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、電気通信システムで送信者の身元を確認すると同時に送信内容の秘匿化を行う暗号通信方法及びその装置に関する。
【０００２】
【従来の技術】
送信者と受信者が、盗聴、改ざん、成りすましの恐れのある通信網を介して、安全に通信を行う方法として、任意のディジタル署名方法と公開鍵暗号化方法とを組み合わせる方法がある。
送信者ＵSの署名鍵、署名検証鍵をそれぞれｘ，ｙとし、受信者ＵRの暗号化鍵、復号鍵をそれぞれｅ，ｄとする。ｙおよびｄは公開されており、送信者ＵS，受信者ＵRはこれらを保持しているものとする。
【０００３】
送信する平文をｍとし、Ｅを暗号化関数とし、Ｅe(m)はメッセージｍを暗号化鍵ｅで暗号化した暗号文を表し、Ｄを暗号化関数Ｅに対応する復号関数とし、Ｄd(c)は暗号文ｃを復号鍵ｄで復号して得られる平文を表す。すなわち、m=Dd(Ee(m))が成り立つ。Ｓを署名関数とし、Sx(m)はメッセージｍに対する署名鍵ｘによる署名を表し、Ｖを検証機関とし、Ｖy(a, m)を署名メッセージ対（ａ，ｍ）を署名検証鍵ｙで検証した結果を表す。検証結果は１または０のいずれかであり、ａ＝Sx(m)のとき、またそのときに限りＶy（ａ，ｍ）＝１となるものとする。
【０００４】
平文ｍを送信する場合、送信者ＵSはまず平文ｍを暗号鍵ｅで暗号化して暗号文Ｃ＝Ee(m)を得る。次に暗号文Ｃに対する署名ａ＝Sx(C)を署名鍵ｘを用いて作成する。送信文ΣはΣ＝（Ｃ，ａ）であり、送信者ＵSは送信文Σを受信者ＵRへ送信する。
受信者ＵRは暗号文Ｃと署名ａを受信し、まず、署名検証鍵ｙを用いてＶy（ａ，Ｃ）が１となることを検証する。１とならない場合は、受信したＣ，ａを不正データとみなして破棄する。検証結果が１であれば復号鍵ｄを用いて、ｍ＝Ｄd（Ｃ）を計算し、平文ｍを得る。
【０００５】
署名、暗号方式にそれぞれSchnorr署名とElGamal暗号を用いた場合について具体的な方法を説明する。ps、qsを大きな素数とし、qsが(ps-1)を割り切るものとする。gsをＺ*ps（Ｚpsは整数１，２，…，psの群である）における位数qsの元とする。pr, qr, grも同様に定義する（添字psはpsを表す、以下同様）。Ｈ1(・)、Ｈ2(・)をそれぞれ一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表すps, qs, gs, pr, qr, gr は公開される。
送信者ＵSはSchnorr署名の署名鍵ｘをＺqs（Ｚqsは整数０，１，２，…，qs−１の群である）からランダムに選び、署名検証鍵ｙをｙ＝ｇsx mod psの計算により求めて、このｙを公開する。受信者ＵRはElGamal暗号の復号鍵ｄをＺqrからランダムに選び、暗号鍵e=grd mod pr を計算してｅを公開する。
【０００６】
ElGamal暗号による暗号文ＣはＣ＝（Ｇ，Ｍ）＝（gru mod pr, EsK(m)）であり、このＣに対するSchnorr署名ａはａ＝（ｃ，ｚ）＝（H1(gsv‖C), v-cx mod qs）である。ここで、ｕ，ｖはそれぞれＺqrおよびＺqsからランダムに選ばれた乱数、Ｅsは例えばＤＥＳのような、対称鍵暗号の暗号化関数、ＫはK=H2(ew mod
pr)である。
受信者は、c=H1(gsxyc mod ps‖C)が成り立つことを確認し、次に、K=H2(Gd mod pr), m=DsK(M)を計算して平文ｍを得る。ここで、ＤsはＥsに対応する対称鍵暗号の復号関数とする。
【０００７】
上記従来技術によれば、ディジタル署名の性質により、Ｖy（ａ，Ｃ）＝１となる署名ａを作成できるのは検証鍵ｙに対応した署名鍵ｘを保持している送信者ＵSのみであり、従って暗号文Ｃの作成者を認証することができ、かつ、暗号文Ｃの作成者は署名の事実を否認することができない。更に、暗号文Ｃを復号することができるのは受信者ＵRだけであり、第三者（盗聴者）にメッセージｍの内容が漏洩することが無い。
【０００８】
【発明が解決しようとする課題】
以下では、関数Ｅ，Ｄ，Ｓ，Ｖの計算時間をそれぞれτ(E)，τ(D)，τ(S)，τ(V)と表し、暗号文長および署名長をそれぞれL(C)，L(a)と表す。
上記従来法によれば、送信者が送信文（Ｃ，ａ）を作成するために必要な計算時間はτ(E)＋τ(S)であり、受信者に必要な計算時間も同様に、τ(V)＋τ(D)である。また、送信文（Ｃ，ａ）のビット長は少なくともL(C)＋L(a)となる。
計算時間を見積もるため、指数部がＺqsであるmod psでのべき乗剰余演算の計算時間を１とする。psとpr、およびqsとqrがそれぞれ同じビット数であるものとし、指数部がＺqrであるmod prでのべき乗剰余演算の計算時間も同様に１とみなす。２基底のべき乗剰余演算は１基底のべき乗剰余演算の約１．４倍の計算量で計算できる。ps, qs のビット長をそれぞれ｜ｐ｜，｜ｑ｜で表し、ハッシュ関数Ｈ1(・)値のビット長を｜ｑ｜で表す。暗号文ｍを対称鍵暗号で暗号化した暗号文の長さを｜ｍ｜で表す。mod qrでの剰余乗算、ハッシュ関数、およびmod qs, mod qr での計算時間は、通常、mod psでのべき乗剰余演算の計算時間に比較して非常に小さいため、以下の見積もりでは無視することとする。また、メッセージ長も十分短いものとし、対称鍵暗号の暗号化および復号の時間も無視できる程度のものと仮定する。
【０００９】
以上の条件によれば、送信文Σ＝（Ｃ，ａ）を作成するために送信者が必要とする計算時間は、ew mod prの計算に１，gru mod prの計算に１，gsvの計算に１かかり、よってτ(E)＋τ(S)＝２＋１＝３である。送信文の長さは、暗号文Ｃ中のＥsK(m)の長さが｜ｍ｜、gru mod prの長さが｜ｐ｜、署名 ａ中のＨ1（ｇsv‖Ｃ）の長さが｜ｑ｜、ｖ＝cx mod qsの長さが｜ｑ｜であり、よってL(C)＋L(a)＝｜ｍ｜＋｜ｐ｜＋２｜ｑ｜である。受信者が署名検証および復号に必要とする計算時間は、gsxyc mod psの計算に1．4，Ｇdmod prの計算に１かかり、よってτ(V)＋τ(D)＝1．4＋１＝2．4である。
【００１０】
この発明は、上記従来方法と同様に、改ざん、成りすまし、盗聴に対する安全性を提供しつつ、送信者、受信者の計算時間がそれぞれτ(E)＋τ(S)、τ(V)＋τ(D)よりも少なく、かつ、送信すべきデータ長がＬ(C)＋Ｌ(a)よりも少なくて済む認証付き暗号化方法を提供することを目的とする。
【００１１】
【課題を解決するための手段】
この発明では公開鍵の一部として共通のパラメータを用い、つまり例えば受信者側で作られたpr, qr, grおよび送信者側で作られたps, qs, gs を、システムに共通のｐ，ｑ，ｇとし、また暗号化関数で使用する乱数と署名関数に用いる乱数を共通の乱数とする。
このように共通のパラメータおよび共通の乱数を用いることで、暗号化時に必要な乱数によるべき乗剰余演算と、署名時に必要なべき乗剰余演算を共通化することができる。つまり送信文の中の暗号文中に含まれる、乱数から計算される部分と、署名に含まれる乱数から計算される部分とを共通化することが可能となる。更には、復号手順の一部と署名検証手順の一部を共通化することも可能となる。
【００１２】
【発明の実施の形態】
いま図１に示すように送信者端末１１で平文ｍを暗号化し、その暗号文Ｃに対するディジタル署名ａを作成し、（Ｃ，ａ）を公衆回線１２を介して受信者端末１３へ送信し、受信者端末１３で受信信号の署名検証を行い、合格すると暗号文Ｃを復号する場合にこの発明を適用した実施の形態を以下に説明する。
実施形態１
Ｅsを秘密鍵暗号関数とし、EsK(m)は鍵Ｋで平文ｍを暗号化してできる暗号文を表す。同様に、ＤsをＥsに対応する秘密鍵復号関数とし、DsK(C)は鍵Ｋで暗号文Ｃを復号して得られる平文を表す。例えば、関数Ｅ，Ｄには、Triple-DESやIDEA、等のブロック暗号のＣＢＣモードやＯＦＢモードにおける暗号化関数、復号関数を用いてよい。
【００１３】
ｐ、ｑを大きな素数とし、ｑが（ｐ−１）を割り切るものとする。ｇをＺ*pにおける位数ｑの元とする。Ｈ1(・)、Ｈ2(・)を一方向性ハッシュ関数とし、二項演算子Ａ‖ＢはＡとＢを結合した値を表す。公開鍵の一部を構成するｐ，ｑ，ｇおよびハッシュ関数はシステム共通パラメータとして公開する。ハッシュ関数には、例えば、SHA-1を用いてもよい。
記憶されている送信者は署名鍵ｘをＺqからランダムに選び、送信者端末１１の機能構成例を図２に示す。メモリ２０にはパラメータｐ，ｑ，ｇと、暗号鍵ｅが、つまり送信者端末１１の乱数生成器２１により署名鍵ｘを生成し、署名鍵ｘをメモリ２０に記憶すると共に署名検証鍵生成器２２により、ｘ，ｑ，ｐを用いてy=gx mod qを計算して署名検証鍵ｙを生成し、メモリ２０に記憶すると共に公開する。
【００１４】
受信者端末１３の機能構成を図３に示す。メモリ４０にはパラメータｐ，ｑ，ｇ，署名検証鍵ｙが格納されている。受信者は復号鍵ｄをＺqからランダムに選び、つまり乱数生成器４１から復号鍵ｄを生成し、メモリに復号鍵ｄを格納し、またｇ，ｄ，ｐを用いて暗号鍵生成部４２でe=gd mod pを計算して暗号鍵ｅを生成し、暗号鍵ｅをメモリ４０に記憶すると共に公開する。
平文ｍを送信する際に、送信者端末１１は送信文Σを以下の手順で作成する。まず、乱数ｗをＺqからランダムに選び、つまり乱数生成器２３から乱数ｗを生成し、べき乗剰余演算器２４に、乱数ｗ、暗号鍵ｅ、パラメータｐを入力してew mod pを計算し、その計算結果をハッシュ器２５に入力してK=H1(ew mod p)を計算してセッション鍵Ｋを求め、このセッション鍵Ｋとメッセージｍを暗号器２６に入力してｍを暗号関数Ｅｓにより鍵Ｋにより暗号化し、つまりC=EsK(m)を演算して暗号文Ｃを得る。
【００１５】
次に、べき乗剰余演算器２７に乱数ｗ、パラメータｇ，ｐを入力してW=gw mod pを計算し、その計算結果Ｗと暗号化器２６からの暗号文Ｃをハッシュ器２８に入力して、ＷとＣの連結のハッシュ値ｂ＝Ｈ2（Ｗ‖Ｃ）を計算し、更にｂ，ｑ，乱数ｗ、署名鍵ｘを剰余乗算・減算器２９に入力してa=w-bx mod qを計算して署名ａ，ｂを得る。送信器３０は暗号文Ｃと署名ａ，ｂを送信文Σ＝（Ｃ，ａ，ｂ）として受信者端末１３へ送信する。
なお送信端末１１の各部の制御は制御部３１により行われ、各部が順次、あるいは並列的に処理される。乱数生成器２１と２３は１つで兼用でき、同様にべき乗剰余演算器２４と２７も１つで兼用することができる。べき乗剰余演算器２４，ハッシュ器２５、暗号化器２６は暗号文Ｃを生成する暗号文生成部７０を構成し、べき乗剰余演算器２７，ハッシュ器１８，剰余乗算・減算器２９は署名を生成する署名部９０を構成している。
【００１６】
受信者端末１３は、以下に示す手段で受信器４３に受信した暗号文の検証および復号を行う。まず、受信した署名ａ，ｂとメモリ４０からのｐ、g及び署名検証鍵ｙがべき乗剰余演算器４４に入力されてW'=gayb mod pが計算され、その計算結果Ｗ’と受信した暗号文Ｃがハッシュ器４５に入力されて、ＣとＷ’の結合のハッシュ値Ｈ2（Ｗ’‖Ｃ）が計算され、この計算結果と受信したｂとが比較器４６で比較され、署名検証がされる。つまりa=w-bx mod p，y=gx mod pであるから、これらをＷ’の式に代入すると、W'=gw mod pとなりＨ2(Ｗ'‖Ｃ）がｂと等しいことは暗号文Ｃに対する署名が正しいことになる。この検証が成り立たない場合は、受信文Σを破棄する。この署名検証が成り立つ場合は、べき乗剰余演算器４７にａ，ｂとｇ，ｐ，ｙ，ｄを入力して(gayb modp)dを計算し、又はべき乗剰余演算器４４の出力Ｗ’とｄを入力して(W')d mod pを計算し、その計算結果をハッシュ器４８に入力してK=H1((gayb mod p)dを計算し、セッション鍵Ｋを復号し、その鍵Ｋにより受信暗号文を復号器４９で復号関数演算ｍ＝DsK(C)を行って、平文ｍを得る。
【００１７】
受信者端末１３の各部は制御部５０により、順次又は並列的に処理するように制御される。べき乗剰余演算器４７はべき乗剰余演算器４４の演算結果Ｗ’を入力して(W')dを計算してもよい。
この実施形態において、前述した計算時間の見積もりと同様の条件で計算時間を評価すると、送信者端末１１ではew mod pの計算に１、gw mod pの計算に１、つまりτ(E)＋τ(S)＝１＋１＝２となり、べき乗剰余演算１回分の時間計算が従来より少なくて済み、また送信文長はEsK(m)の長さが｜ｍ｜、ｂ＝Ｈ2（Ｗ‖Ｃ）の長さが｜ｑ｜、a=w-bx mod qの長さが｜ｑ｜、つまりL(C)＋L(a)＝｜ｍ｜＋２｜ｑ｜となり、従来より｜ｐ｜ビットだけ短くなり、受信者端末１３では計算時間はgayb mod pの計算に1．4，(W')dmod pの計算に１、つまりτ(V)＋τ(D)＝1．4＋１＝2．4となり、従来と同一である。
【００１８】
つまり、パラメータｐ，ｑ，ｇを送信者端末１１と受信者端末１３とに共通にし、乱数ｗを暗号関数と署名関数とに共通に使用しているため、従来における暗号文Ｃ=（Ｇ，Ｍ）中のG=gru mod prと署名a=（Ｃ，Ｚ）中のＣ=H1(gsv mod ps‖Ｃ）の計算におけるgsv mod psとが同一の計算gw mod pとなり、暗号化時に必要な乱数によるべき乗剰余演算と、署名時に必要なべき乗剰余演算を共通化することができ、それだけ計算時間が少なくなり、かつ送信文の中の暗号文中に含まれる、乱数から計算される部分Ｇと、署名に含まれる乱数から計算される部分、ｂ＝Ｈ2（Ｗ‖Ｃ）中のＷ＝gw mod pとが共通化され、Ｇを送信する必要がない。即ち受信者端末１３では検証時のW'=gayb mod pの計算により、W'=gv mod pが得られ、ｂ＝Ｈ2（Ｗ’‖Ｃ）を計算することにより、従来技術における復号時に必要とするＧと対応するものが得られ、Ｇの受信を必要としない。
実施形態２
平文ｍを送信する際に、送信者端末１１は送信文Σを以下に示す手段で作成してもよい。暗号文Ｃを上記手段と同様に作成し、次に、図２中で波線で示すようにＷではなく、ハッシュ器２５の出力Ｋを入力してｂ＝Ｈ2（Ｋ‖Ｃ）を計算し、このｂを用いて剰余乗算・減算器２９でa=w-bx mod qを計算して署名ａ，ｂを得る。送信文ΣはΣ＝（Ｃ，ａ，ｂ）とする。
【００１９】
受信者端末１３は、以下に示す手段で受信した暗号文の検証及び復号を行う。まず、べき乗剰余演算器４７及びハッシュ器４８によりK=H1((gayb)d mod p)を計算し、図３中に波線で示すようにハッシュ器４５にＷの代わりにＫを入力してＨ2（Ｋ‖Ｃ）を計算し、比較器４６でｂ＝Ｈ2（Ｋ‖Ｃ）が成り立つことを検証し、成り立たない場合は、受信文Σを破棄する。成り立つ場合は、次に、ｍ＝ＤsK(C)を計算して平文ｍを得る。
この実施の形態２においても、実施形態１と同様な理由で送信者端末１１での計算時間を２とし、送信文長を｜ｍ｜＋２｜ｑ｜とすることができ、しかも受信者端末１３での計算時間はＫの計算の1．4で済む。
【００２０】
実施形態１に対する実施形態の変更から、容易に理解されるようにハッシュ器２８への入力としてはＷとＣとＫとし、Ｈ2（Ｗ‖Ｃ‖Ｋ）＝ｂとしてもよく、又はＷ，Ｃ，ｍを入力して、Ｈ2（Ｗ‖Ｃ‖ｍ）＝ｂとしてもよく、あるいはＣ、ｍを入力してＨ2（Ｃ‖ｍ）＝ｂとしてもよい。なお、ハッシュ器２８への入力としてｍを用いる場合は、受信者端末１３において、検証の際にＫを求め、更にＫによりｍを復号して、そのｍを用いることになる。要は送信者端末１１のハッシュ器２８ではＷ、Ｋ、ｍの少なくとも１つと、Ｃとを入力して、その入力の結合をＨ2(・)演算してｂを出力し、受信者端末１３のハッシュ器４５では、送信者端末のハッシュ器２８の入力と対応するものを入力してその結合をＨ2(・)演算すればよい。
実施形態３
平文ｍを送信する際に、送信者端末１１で以下に示す手段で冗長化してもよい。図４に示すように送信者端末１１において、まずメッセージ変換器６０で入力平文ｍに冗長性を与えたメッセージｍ’に変換する。この変換は例えば図５に示すように平文ｍはハッシュ器６１でハッシュ関数演算Ｈ4(m)が行われ、その演算結果は、更にハッシュ器６２でハッシュ関数演算Ｈ5（Ｈ4（ｍ））が行われる。この演算結果と入力平文ｍとのビット毎の排他的論理和演算H5(H4(m))(+)mが排他的論理和演算器６３で行われ、この演算結果とハッシュ器６１の演算結果Ｈ4(m)との結合が結合器６４で結合されm'=m(+)H5(H4(m))‖H4(m)として出力される。
【００２１】
このように変換されたメッセージｍ'は図４中の暗号文生成部７０で、例えば実施形態１における暗号文Ｃと同様な手法により暗号化されて暗号文Ｃが生成される。この暗号文Ｃはハッシュ器７１でハッシュ関数演算Ｈ2(C)＝ｂが行われ、この演算結果ｂとメモリ２０よりのｘ，ｑ，ａ，乱数生成器２３からのｗとにより剰余乗算・減算器２９においてa=w-bx mod qが演算され、署名のａが生成され、送信器３０より送信文Σ＝（Ｃ，ａ）が送信される。
受信者端末１３では図６に示すように受信器４３で受信されたＣ，ａの中のＣがハッシュ器８１でハッシュ関数演算ｂ＝Ｈ2(C)が行われ、その演算結果ｂと受信したａと、メモリ４０よりのｄ，ｙ，ｐ，ｇによりべき乗剰余演算器４７により、(gayb)d mod pが演算され、その結果に対し、ハッシュ器４８でハッシュ関数Ｈ1(・）が行われ、鍵Ｋが求められる。この鍵Ｋにより受信した暗号文Ｃに対し復号関数演算m'=DsK(C)が復号器４９で行われる。
【００２２】
その復号されたメッセージｍ'はビット分割器８２により、Ｂがハッシュ関数H4(・)の演算結果のビット数と同じになるようにｍ'=Ａ‖Ｂに分割される。そのＢはハッシュ器８３でハッシュ関数演算Ｈ5(Ｂ)が行われ、その演算結果とＡとのビット毎の排他的論理和演算ｍ=H5(B)(+)Aが演算器８４で行われる。この演算結果ｍとＢとを比較器８６で比較され、等しければ演算結果ｍが正しい復号平文として出力され、等しくなければ受信文（Ｃ，ａ）は不正となす。
この実施形態３においても実施形態２と同様に、送信者端末１１及び受信者端末１３の各計算時間を低減でき、かつ送信文の長を低減できる。
【００２３】
上述において送信者端末１１、受信者端末１３はそれぞれ、コンピュータによりプログラムを実行させて、機能させることもできる。
またこの発明は実施形態１乃至３に限らず、公開鍵を用いた暗号化とその暗号文の署名に適応でき、公開鍵の一部を構成するパラメータを共通化し、かつ暗号化に用いる乱数と署名に用いる乱数を共通化すればよい。
【００２４】
【発明の効果】
以上述べたようにこの発明によれば、送信者端末での計算時間と送信文のビット数を低減することができ、実施形態によると、受信者端末での計算時間も低減することができる。
【図面の簡単な説明】
【図１】この発明が適用されるシステム構成例を示す図。
【図２】この発明の送信者端末の機能構成例を示す図。
【図３】この発明の受信者端末の機能構成例を示す図。
【図４】この発明の送信者端末の他の機能構成例を示す図。
【図５】図４中のメッセージ変換器６０の機能構成例を示す図。
【図６】この発明の受信者端末の他の機能構成例を示す図。
【図１】
0003694242.tif 000002
【図２】
0003694242.tif 000003
【図３】
0003694242.tif 000004
【図４】
0003694242.tif 000005
【図５】
0003694242.tif 000006
【図６】
0003694242.tif 000007