(57)【要約】【課題】  極めて簡単な暗号系を提案し、ＲＳＡ暗号化方式と等価な安全性を保持しつつ、暗号化および復号化する際の計算量を減らして単純化し、簡単な計算で暗号化および復号化が可能な暗号化装置および復号化装置、並びにこれらを備えた暗号システム、暗号化方法および復号化方法を提供する。【解決手段】  暗号システム１０は、暗号化装置１１、通信路１４、および復号化演算装置１５を備えている。暗号化装置１１の鍵生成手段１２は、公開鍵｛ｇ１，ｇ２｝を、（ｐ−１）、（ｑ−１）のべき乗を含む乱数として生成し、復号化の際には、フェルマーの小定理および中国人剰余定理を用いてメッセージｍを復号化する。【選択図】  図１
2004246350.tif 000002
【特許請求の範囲】
【請求項１】
２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１），（２）で表されるｇ１，ｇ２を公開鍵として生成する鍵生成手段と、
入力された平文ｍに対して、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３），（４）で表される暗号文Ｃ＝（Ｃ１，Ｃ２）を生成する暗号化演算手段とを備えたことを特徴とする暗号化装置。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１とする）
【請求項２】
素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）で表されるｇ１を公開鍵として生成する鍵生成手段と、
入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを生成する暗号化演算手段とを備えたことを特徴とする暗号化装置。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
（ただし、情報ｂ＝size of ｐ（bits）であって、０＜ｍ＜２ｂ−１、ｇｃｄ｛ｓ，ｑ−１｝＝１とする）
【請求項３】
上記暗号文Ｃに下記の関係式で示されるｅを加えて、Ｃ＝（Ｃ１，Ｃ２，ｅ）とすることを特徴とする請求項１に記載の暗号化装置。
（ただし、ｅ＝ｈ（ｄ）（ｈは一方向性ハッシュ関数）、ｄ＝（Ｃ１＋Ｃ２）／ｍ（ｍｏｄｎ）、Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）、Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）とする。）
【請求項４】
上記暗号文Ｃの乱数部分の計算を行ったデータを蓄積したデータベースを備えていることを特徴とする請求項１または３に記載の暗号化装置。
【請求項５】
上記暗号化演算手段は、最初の平文ｍ１だけを暗号文Ｃ１＝（Ｃ１１，Ｃ１２）に暗号化し、それ以降の暗号文については、受信した平文ｍｉと、平文ｍ１のビット情報と、暗号文Ｃ１に含まれる２つの乱数Ｒ１またはＲ２とを使用して暗号文を作成することを特徴とする請求項１または３に記載の暗号化装置。
【請求項６】
２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１），（２）で表されるｇ１，ｇ２を公開鍵として用いるとともに、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３），（４）で表される平文ｍを暗号化した暗号文Ｃ＝（Ｃ１，Ｃ２）を受信し、
フェルマーの小定理を用いて下記の関係式（５），（６）で表される受信暗号文ａ，ｂを生成し、該受信暗号文ａ，ｂから、中国人剰余定理を用いて、下記の関係式（７）を満たす平文ｍを導出し、復号化処理を行う復号化演算手段を備えていることを特徴とする復号化装置。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
ａ＝Ｃ１（ｍｏｄｐ）＝ｍ（ｍｏｄｐ）  ・・・・・（５）
ｂ＝Ｃ２（ｍｏｄｑ）＝ｍ（ｍｏｄｑ）  ・・・・・（６）
ｍ＝ａＡｑ＋ｂＢｐ（ｍｏｄｎ）  ・・・・・（７）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１、Ａｑ（ｍｏｄｐ）＝１、Ｂｐ（ｍｏｄｑ）＝１とする）
【請求項７】
素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）で表されるｇ１を公開鍵として生成し、入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを受信し、
フェルマーの小定理を用いて下記の関係式（８）を満たす平文ｍを導出し、復号化処理を行う復号化演算手段を備えていることを特徴とする復号化装置。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
ｍ＝Ｃ（ｍｏｄｐ）  ・・・・・（８）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１とする）
【請求項８】
２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１），（２）で表されるｇ１，ｇ２を公開鍵として生成する鍵生成手段と、入力された平文ｍに対して、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３），（４）で表される暗号文Ｃ１，Ｃ２を生成する暗号化演算手段とを備えた暗号化装置と、
上記暗号化装置で算出された暗号文Ｃ１，Ｃ２を受信し、フェルマーの小定理を用いて下記の関係式（５），（６）で表される受信暗号文ａ，ｂを生成し、該受信暗号文ａ，ｂから、中国人剰余定理を用いて、下記の関係式（７）を満たす平文ｍを導出し、復号化処理を行う復号化演算手段を備えている復号化装置とを備えていることを特徴とする暗号システム。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
ａ＝Ｃ１（ｍｏｄｐ）＝ｍ（ｍｏｄｐ）  ・・・・・（５）
ｂ＝Ｃ２（ｍｏｄｑ）＝ｍ（ｍｏｄｑ）  ・・・・・（６）
ｍ＝ａＡｑ＋ｂＢｐ（ｍｏｄｎ）  ・・・・・（７）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１、Ａｑ（ｍｏｄｐ）＝１、Ｂｐ（ｍｏｄｑ）＝１とする）
【請求項９】
素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）で表されるｇ１を公開鍵として生成する鍵生成手段と、入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを生成する暗号化演算手段とを有する暗号化装置と、
上記暗号化装置から暗号文Ｃを受信し、フェルマーの小定理を用いて下記の関係式（８）を満たす平文ｍを導出し、復号化処理を行う復号化演算手段を有する復号化装置とを備えていることを特徴とする暗号システム。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
ｍ＝Ｃ（ｍｏｄｐ）  ・・・・・（８）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１とする）
【請求項１０】
２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１），（２）で表されるｇ１，ｇ２を公開鍵として生成するとともに、
入力された平文ｍに対して、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３），（４）で表される暗号文Ｃ１，Ｃ２を生成することを特徴とする暗号化方法。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１とする）
【請求項１１】
素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）で表されるｇ１を公開鍵として生成するとともに、
入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを生成することを特徴とする暗号化方法。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
（ただし、情報ｂ＝size of ｐ（bits）であって、０＜ｍ＜２ｂ−１，ｇｃｄ｛ｓ，ｑ−１｝＝１とする）
【請求項１２】
２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１），（２）で表されるｇ１，ｇ２を公開鍵として用いるとともに、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３），（４）で表される平文ｍを暗号化した暗号文Ｃ＝（Ｃ１，Ｃ２）を受信し、
フェルマーの小定理を用いて下記の関係式（５），（６）で表される受信暗号文ａ，ｂを生成し、該受信暗号文ａ，ｂから、中国人剰余定理を用いて、下記の関係式（７）を満たす平文ｍを導出し、復号化処理を行うことを特徴とする復号化方法。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
ａ＝Ｃ１（ｍｏｄｐ）＝ｍ（ｍｏｄｐ）  ・・・・・（５）
ｂ＝Ｃ２（ｍｏｄｑ）＝ｍ（ｍｏｄｑ）  ・・・・・（６）
ｍ＝ａＡｑ＋ｂＢｐ（ｍｏｄｎ）  ・・・・・（７）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１、Ａｑ（ｍｏｄｐ）＝１、Ｂｐ（ｍｏｄｑ）＝１とする）
【請求項１３】
素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇを用いて下記の関係式（１）で表されるｇ１とを公開鍵として生成し、入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを受信し、
フェルマーの小定理を用いて下記の関係式（８）を満たす平文ｍを導出し、復号化処理を行うことを特徴とする復号化方法。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
ｍ＝Ｃ（ｍｏｄｐ）  ・・・・・（８）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１とする）
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等を通じて送受信される通信文を暗号化するための暗号化装置、および暗号化された通信文を復号化するための復号化装置、並びにこれらを備えた暗号システムに関するものである。
【背景技術】
【０００２】
従来より、インターネット等を通じてやり取りが行われるデータ等の漏洩、改竄が問題となっており、この対策として、データ等を暗号化して相手先へ送信する暗号システムが利用されている。
【０００３】
暗号システムは、共通鍵暗号方式と公開鍵暗号方式とに大別され、鍵管理の容易性、データ漏洩の危険性が低い等の理由から、主として、公開鍵暗号方式が採用されている。
【０００４】
公開鍵暗号方式の代表的な例としては、ＲＳＡ暗号化方式がある。
【０００５】
このＲＳＡ暗号化方式は、２つの素数ｐ，ｑを実質的な秘密鍵として生成し、その積ｎ＝ｐｑを公開鍵の一つとして用いることで、ｐｑからｎは容易に求められるが、ｎから２つの素数ｐ，ｑを求めることが非常に困難であるという性質を利用した公開鍵暗号方式である。
【０００６】
このように、ｎを公開鍵の一つとして公開することで、誰もが暗号文を作成できる一方、これを復号するために２つの大きな素数ｐ，ｑを求めることは非常に困難であることから、ＲＳＡ暗号化方式によって送信されるデータの安全性は非常に高いといえる。
【特許文献１】特開平８−２５１１５５号公報（１９９６年９月２７日公開）
【特許文献２】特開２０００−２１４７７７号公報（２０００年８月４日公開）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述のような従来のＲＳＡ暗号化方式では、データの秘匿性の面では高い性能を有し、アルゴリズムも単純であるものの、その安全性は大きな二つの素数ｐ，ｑの積ｎを素因数分解する困難さに起因している。このため、ｎ＝ｐｑの値を10進法で200桁程度の大きさにする必要があり、暗号化および復号を実行するために必要なｎを法とするべき乗計算の実行が極めて困難であるという問題を有している。
【０００８】
さらに、ＲＳＡ暗号化方式は、乗法特性を有しており、２つの署名から第３の署名が生成できるため、安全性の面で問題がある。
【０００９】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、極めて簡単な秘密暗号系を提案し、ＲＳＡ暗号化方式と等価な安全性を保持しつつ、アルゴリズムをより単純化し、簡単な計算で暗号化および復号化が可能な暗号化装置および復号化装置、並びにこれらを備えた暗号システム、暗号化方法および復号化方法を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の暗号化装置は、上記の課題を解決するために、２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）、（２）で表されるｇ１，ｇ２を公開鍵として生成する鍵生成手段と、入力された平文ｍに対して、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３）、（４）で表される暗号文Ｃ＝（Ｃ１、Ｃ２）を生成する暗号化演算手段とを備えたことを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１とする）。
【００１１】
上記の構成によれば、公開鍵として生成した鍵ｇ１，ｇ２は、それぞれ（ｐ−１），（ｑ−１）のべき乗を含んでおり、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて生成した暗号文Ｃ１，Ｃ２も、（ｐ−１），（ｑ−１）のべき乗をそれぞれ含んでいるため、この暗号文Ｃ１，Ｃ２を復号化する際において、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、簡単に復号化することができる。
【００１２】
すなわち、本発明の暗号化装置は、鍵生成手段により、２つの大きな素数ｐ，ｑを発生させ、これを秘密鍵として用いるとともに、この秘密鍵｛ｐ，ｑ｝と乱数ｓ，ｔとを用いて、それぞれ（ｐ−１），（ｑ−１）のべき乗を含むように公開鍵｛ｇ１，ｇ２｝を生成している。
【００１３】
これにより、２つの大きな素数ｐ，ｑをそのまま秘密鍵として用いることができ、さらに、公開鍵｛ｇ１，ｇ２｝についても、乱数を用いて、（ｐ−１）のべき乗を含む非常に簡単な計算で算出できる。
【００１４】
また、本発明の暗号化装置の暗号化演算手段によって生成された暗号文は、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて、（ｐ−１），（ｑ−１）のべき乗を含んだ式で表されるため、その復号化にはフェルマーの小定理を用いることが可能になる。
【００１５】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。よって、暗号文Ｃ１，Ｃ２から、フェルマーの小定理を用いて、暗号文Ｃ１，Ｃ２に対応する２つの受信暗号文を算出し、ここでさらに中国人剰余定理を用いることで、２つの受信暗号文から平文ｍを復号化できる。
【００１６】
本発明の暗号化装置では、以上のように、単純な秘密鍵｛ｐ，ｑ｝を用いて、簡単な計算で公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎを生成し、暗号文も簡単な計算で算出でき、さらにこの暗号文の復号化についても、フェルマーの小定理を用いて簡単に計算できるため、従来の暗号化方式と比較して、高速処理が可能になる。
【００１７】
一方、本発明の暗号化装置における安全性については、公開鍵｛ｇ１，ｇ２｝には、それぞれ乱数ｓ，ｔが含まれているため、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎは互いに関係が断ち切られている。
【００１８】
よって、本発明の暗号化装置によれば、高い安全性を維持しつつ、計算量を減らして暗号化および復号化の高速処理を行うことが可能になる。
【００１９】
本発明の暗号化装置は、上記の課題を解決するために、素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）で表されるｇ１を公開鍵として生成する鍵生成手段と、入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを生成する暗号化演算手段とを備えたことを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
（ただし、情報ｂ＝size of ｐ（bits）であって、０＜ｍ＜２ｂ−１，ｇｃｄ｛ｓ，ｑ−１｝＝１とする）
上記の構成によれば、公開鍵として生成した鍵ｇ１は、（ｐ−１）のべき乗を含んでおり、公開鍵ｇ１及び秘密鍵ｎを用いて生成した暗号文Ｃも、（ｐ−１）のべき乗を含んでいるため、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、この暗号文Ｃを簡単に復号化することができる。
【００２０】
すなわち、本発明の暗号化装置は、鍵生成手段により、２つの大きな素数ｐ，ｑを発生させ、これを秘密鍵として用いるとともに、この秘密鍵｛ｐ，ｑ｝と乱数ｓ，ｔとを用いて、それぞれ（ｐ−１）のべき乗を含むように公開鍵ｇ１を生成している。
【００２１】
さらに、秘密鍵ｐのサイズｂとの関係において、メッセージｍに長さの制限を課し、このサイズｂを用いることで、暗号文の生成および復号化の計算をそれぞれ１つの式で行うことができるため、中国人剰余定理を用いることなく、より簡単な計算により暗号化復号化処理を行うことができる。
【００２２】
また、本発明の暗号化装置の暗号化演算手段によって生成された暗号文は、上記と同様に、公開鍵ｇ１及び秘密鍵ｎを用いて、（ｐ−１）のべき乗を含んだ式で表されるため、その復号化にはフェルマーの小定理を用いることが可能である。
【００２３】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。
【００２４】
よって、単純な秘密鍵｛ｐ，ｑ｝を用いて、簡単な計算で公開鍵ｇ１を生成し、暗号文も簡単な計算で算出でき、さらにこの暗号文の復号化についても、フェルマーの小定理だけを用いることで簡単に計算できるため、従来の暗号化方式と比較して、さらに高速処理が可能になる。
【００２５】
一方、本発明の暗号化装置における安全性については、公開鍵ｇ１には、乱数ｓが含まれているため、公開鍵ｇ１及び秘密鍵ｎは互いに関係が断ち切られている。
【００２６】
よって、本発明の暗号化装置によれば、高い安全性を維持しつつ、平文ｍの長さに制限を加えることで、さらに計算量を減らして暗号化、復号化処理の高速化を実現できる。
【００２７】
上記暗号文Ｃに下記の関係式で示されるｅを加えて、Ｃ＝（Ｃ１，Ｃ２，ｅ）とすることがより好ましい。（ただし、ｅ＝ｈ（ｄ）（ｈは一方向性ハッシュ関数）、ｄ＝（Ｃ１＋Ｃ２）／ｍ（ｍｏｄｎ）、Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ），Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）とする）。
【００２８】
これにより、暗号文Ｃが長くなるが、メッセージｍが少しでも変わるとｅが一致しなくなるため、適応型選択暗号文攻撃（ＣＣＡ２）に対しても耐性を持たせて、より信頼度の高い暗号システムを得ることができる。
【００２９】
また、ｅはハッシュ関数を用いて計算されているため、３２bitsまたは６４bits程度の情報量にまとめることができる。
【００３０】
上記暗号文Ｃの乱数部分の計算を行ったデータを蓄積したデータベースを備えていることがより好ましい。
【００３１】
これにより、例えば、暗号文Ｃに含まれる乱数部分のデータを蓄積した２行ｆ列のデータベースを予め用意しておくことで、暗号化処理を行う際には、このデータベースから対応する乱数を取り出して暗号文を作成することができるため、暗号化処理をより高速化できる。
【００３２】
よって、例えば、従来のＲＳＡ暗号方式と比較して、計算量を減らして暗号化処理を高速化できるとともに、復号化処理についてもｍｏｄｐの演算を施すだけで復号化できるため、計算量が多い従来のＲＳＡ暗号化方式の暗号システムと比較してはるかに高速化できる。
【００３３】
上記暗号化演算手段は、最初の暗号文Ｃだけを暗号文Ｃ１，Ｃ２に暗号化し、それ以降の暗号文については前の暗号文Ｃ１と、Ｃ１に含まれる２つの乱数とを使用して暗号文を作成することがより好ましい
これにより、最初の暗号文Ｃについてのみ通常の手順で暗号文を作成し、それ以降の暗号文については、最初のビットｂｉ＝０の場合には、乱数部分Ｒ１を加算し、最初のビットｂｉ＝１の場合には、乱数部分Ｒ２を加算していくことで、暗号文Ｃを作成できる。
【００３４】
本発明の復号化装置は、上記の課題を解決するために、２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１），（２）で表されるｇ１，ｇ２を公開鍵として用いるとともに、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３），（４）で表される平文ｍを暗号化した暗号文Ｃ＝（Ｃ１，Ｃ２）を受信し、フェルマーの小定理を用いて下記の関係式（５），（６）で表される受信暗号文ａ，ｂを生成し、該受信暗号文ａ，ｂから、中国人剰余定理を用いて、下記の関係式（７）を満たす平文ｍを導出し、復号化処理を行う復号化演算手段を備えていることを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
ａ＝Ｃ１（ｍｏｄｐ）＝ｍ（ｍｏｄｐ）  ・・・・・（５）
ｂ＝Ｃ２（ｍｏｄｑ）＝ｍ（ｍｏｄｑ）  ・・・・・（６）
ｍ＝ａＡｑ＋ｂＢｐ（ｍｏｄｎ）  ・・・・・（７）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１、Ａｑ（ｍｏｄｐ）＝１、Ｂｐ（ｍｏｄｑ）＝１とする）。
【００３５】
上記の構成によれば、公開鍵として生成した鍵ｇ１，ｇ２は、それぞれ（ｐ−１），（ｑ−１）のべき乗を含んでおり、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて生成した暗号文Ｃ１，Ｃ２も、（ｐ−１），（ｑ−１）のべき乗をそれぞれ含んでいるため、この暗号文Ｃ１，Ｃ２を復号化する際において、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、簡単に復号化することができる。
【００３６】
すなわち、本発明の復号化装置が受信する暗号文は、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて、（ｐ−１），（ｑ−１）のべき乗を含んだ式で表されるため、その復号化にはフェルマーの小定理を用いることが可能になる。
【００３７】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。よって、暗号文Ｃ１，Ｃ２から、フェルマーの小定理を用いて、暗号文Ｃ１，Ｃ２に対応する２つの受信暗号文を算出し、ここでさらに中国人剰余定理を用いることで、２つの受信暗号文から平文ｍを復号化できる。
【００３８】
以上のように、本発明の復号化装置では、フェルマーの小定理を用いて簡単に暗号文を復号化できるため、従来の復号化方式と比較して、高速処理が可能になる。
【００３９】
本発明の復号化装置は、上記の課題を解決するために、素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）で表されるｇ１を公開鍵として生成し、入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを受信し、
フェルマーの小定理を用いて下記の関係式（８）を満たす平文ｍを導出し、復号化処理を行う復号化演算手段を備えていることを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
ｍ＝Ｃ（ｍｏｄｐ）  ・・・・・（８）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１とする）。
【００４０】
上記の構成によれば、公開鍵ｇ１を用いて生成した暗号文Ｃは、（ｐ−１）のべき乗を含んでいるため、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、この暗号文Ｃを簡単に復号化することができる。
【００４１】
すなわち、本発明の復号化装置は、秘密鍵ｐのサイズｂとの関係において、メッセージｍに長さの制限を課し、このサイズｂを用いることで、暗号文Ｃの生成および復号化の計算をそれぞれ１つの式で行うことができるため、中国人剰余定理を用いることなく、より簡単な計算により復号化処理を行うことができる。
【００４２】
また、本発明の復号化装置で復号化される暗号文は、公開鍵ｇ１を用いて、（ｐ−１）のべき乗を含んだ式で表されるため、その復号化にはフェルマーの小定理を用いることが可能である。
【００４３】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。
【００４４】
よって、単純な秘密鍵｛ｐ，ｑ｝を用いて、簡単な計算で公開鍵ｇ１及び秘密鍵ｎを生成し、暗号文も簡単な計算で算出でき、さらに暗号文の復号化についても、フェルマーの小定理だけを用いることで簡単に計算できるため、従来の復号化方式と比較して、さらに高速処理が可能になる。
【００４５】
なお、本発明は、暗号鍵の配布に適用することが可能である。
【００４６】
本発明の暗号システムは、上記の課題を解決するために、２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１），（２）で表されるｇ１，ｇ２を公開鍵として生成する鍵生成手段と、入力された平文ｍに対して、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３），（４）で表される暗号文Ｃ１，Ｃ２を生成する暗号化演算手段とを備えた暗号化装置と、上記暗号化装置で算出された暗号文Ｃ１，Ｃ２を受信し、フェルマーの小定理を用いて下記の関係式（５），（６）で表される受信暗号文ａ，ｂを生成し、該受信暗号文ａ，ｂから、中国人剰余定理を用いて、下記の関係式（７）を満たす平文ｍを導出し、復号化処理を行う復号化演算手段を備えている復号化装置とを備えていることを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
ａ＝Ｃ１（ｍｏｄｐ）＝ｍ（ｍｏｄｐ）  ・・・・・（５）
ｂ＝Ｃ２（ｍｏｄｑ）＝ｍ（ｍｏｄｑ）  ・・・・・（６）
ｍ＝ａＡｑ＋ｂＢｐ（ｍｏｄｎ）  ・・・・・（７）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１、Ａｑ（ｍｏｄｐ）＝１、Ｂｐ（ｍｏｄｑ）＝１とする）。
【００４７】
上記の構成によれば、暗号化装置において、公開鍵として生成した鍵ｇ１，ｇ２は、それぞれ（ｐ−１），（ｑ−１）のべき乗を含んでおり、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて生成した暗号文Ｃ１，Ｃ２も、（ｐ−１），（ｑ−１）のべき乗をそれぞれ含んでいるため、復号化装置において、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、暗号文Ｃ１，Ｃ２を簡単に復号化することができる。
【００４８】
すなわち、本発明の暗号システムは、暗号化装置と復号化装置とを備えている。暗号化装置は、鍵生成手段を備え、２つの大きな素数ｐ，ｑを発生させ、これを秘密鍵として用いるとともに、この秘密鍵｛ｐ，ｑ｝と乱数ｓ，ｔとを用いて、それぞれ（ｐ−１），（ｑ−１）のべき乗を含むように公開鍵｛ｇ１，ｇ２｝を生成している。
【００４９】
これにより、２つの大きな素数ｐ，ｑをそのまま秘密鍵として用いることができ、さらに、公開鍵｛ｇ１，ｇ２｝についても、乱数を用いて、（ｐ−１）のべき乗を含む非常に簡単な計算で算出できる。
【００５０】
また、本発明の暗号システムの暗号化装置は、暗号化演算手段において、公開鍵｛ｇ１，ｇ２｝を用いて、（ｐ−１），（ｑ−１）のべき乗を含んだ式で表される暗号文Ｃを作成するため、その暗号文Ｃの復号化にフェルマーの小定理を用いることが可能になる。
【００５１】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。よって、暗号文Ｃ１，Ｃ２から、フェルマーの小定理を用いて、暗号文Ｃ１，Ｃ２に対応する２つの受信暗号文を算出し、ここでさらに中国人剰余定理を用いることで、２つの受信暗号文から平文ｍを復号化できる。
【００５２】
以上のように、本発明の暗号システムでは、暗号化装置において、単純な秘密鍵｛ｐ，ｑ｝を用いて、簡単な計算で公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを生成し、暗号文も簡単な計算で算出でき、さらに、復号化装置において、フェルマーの小定理を用いて簡易に暗号文を復号化できるため、従来の暗号システムと比較して、高速処理が可能になる。
【００５３】
一方、本発明の暗号システムにおける安全性については、暗号化装置において作成される公開鍵｛ｇ１，ｇ２｝には、それぞれ乱数ｓ，ｔが含まれているため、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎは互いに関係が断ち切られている。
【００５４】
よって、本発明の暗号システムによれば、高い安全性を維持しつつ、計算量を減らして暗号化および復号化の高速処理を行うことが可能になる。
【００５５】
本発明の暗号システムは、上記の課題を解決するために、素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）で表されるｇ１を公開鍵として生成する鍵生成手段と、入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを生成する暗号化演算手段とを有する暗号化装置と、上記暗号化装置から暗号文Ｃを受信し、フェルマーの小定理を用いて下記の関係式（８）を満たす平文ｍを導出し、復号化処理を行う復号化演算手段を有する復号化装置とを備えていることを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
ｍ＝Ｃ（ｍｏｄｐ）  ・・・・・（８）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１とする）。
【００５６】
上記の構成によれば、暗号化装置において、公開鍵ｇ１及び秘密鍵ｎを用いて作成された暗号文Ｃは、（ｐ−１）のべき乗を含んでいるため、復号化装置において、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、この暗号文Ｃを簡単に復号化することができる。
【００５７】
すなわち、本発明の暗号システムは、暗号化装置が備えている鍵生成手段により、２つの大きな素数ｐ，ｑを発生させ、これを秘密鍵として用いるとともに、この秘密鍵｛ｐ，ｑ｝と乱数ｓ，ｔとを用いて、それぞれ（ｐ−１）のべき乗を含むように公開鍵ｇ１を生成している。
【００５８】
さらに、秘密鍵ｐのサイズｂとの関係において、メッセージｍに長さの制限を課し、このサイズｂを用いることで、暗号文Ｃの生成および復号化の計算をそれぞれ１つの式で行うことができるため、復号化装置において、中国人剰余定理を用いることなく、より簡単な計算により復号化処理を行うことができる。
【００５９】
また、本発明の暗号システムにおいては、復号化装置において復号化される暗号文が、（ｐ−１）のべき乗を含んだ式で表されるため、その復号化にはフェルマーの小定理を用いることが可能である。
【００６０】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。
【００６１】
よって、単純な秘密鍵｛ｐ，ｑ｝を用いて、簡単な計算で公開鍵ｇ１及び秘密鍵ｎを生成し、暗号文も簡単な計算で算出でき、さらに暗号文の復号化についても、フェルマーの小定理だけを用いることで簡単に計算できるため、従来の復号化方式と比較して、さらに高速処理が可能になる。
【００６２】
一方、本発明の暗号システムにおける安全性については、公開鍵ｇ１には、乱数ｓが含まれているため、公開鍵ｇ１及び秘密鍵ｎは互いに関係が断ち切られている。
【００６３】
よって、本発明の暗号化装置によれば、高い安全性を維持しつつ、平文ｍの長さに制限を加えることで、さらに簡単な計算により暗号化、復号化処理を行って、高速処理を実現できる。
【００６４】
本発明の暗号化方法は、上記の課題を解決するために、２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１），（２）で表されるｇ１，ｇ２を公開鍵として生成するとともに、入力された平文ｍに対して、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３），（４）で表される暗号文Ｃ１，Ｃ２を生成することを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１とする）。
【００６５】
上記の暗号化方法によれば、公開鍵として生成した鍵ｇ１，ｇ２は、それぞれ（ｐ−１），（ｑ−１）のべき乗を含んでおり、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて生成した暗号文Ｃ１，Ｃ２も、（ｐ−１），（ｑ−１）のべき乗をそれぞれ含んでいるため、この暗号文Ｃ１，Ｃ２を復号化する際において、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、簡単に復号化することができる。
【００６６】
すなわち、本発明の暗号化方法は、２つの大きな素数ｐ，ｑを発生させ、これを秘密鍵として用いるとともに、この秘密鍵｛ｐ，ｑ｝と乱数ｓ，ｔとを用いて、それぞれ（ｐ−１），（ｑ−１）のべき乗を含むように公開鍵｛ｇ１，ｇ２｝を生成している。
【００６７】
これにより、２つの大きな素数ｐ，ｑをそのまま秘密鍵として用いることができ、さらに、公開鍵｛ｇ１，ｇ２｝についても、乱数を用いて非常に簡単な計算により算出できる。
【００６８】
また、本発明の暗号化方法によって生成された暗号文は、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて、（ｐ−１），（ｑ−１）のべき乗を含んだ式で表されるため、その復号化にはフェルマーの小定理を用いることが可能になる。
【００６９】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。よって、暗号文Ｃ１，Ｃ２から、フェルマーの小定理を用いて、暗号文Ｃ１，Ｃ２に対応する２つの受信暗号文を算出し、ここでさらに中国人剰余定理を用いることで、２つの受信暗号文から平文ｍを復号化できる。
【００７０】
以上のように、本発明の暗号化方法では、単純な秘密鍵｛ｐ，ｑ｝を用いて、簡単な計算で公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを生成し、暗号文も簡単な計算で算出でき、さらにこの暗号文の復号化についても、フェルマーの小定理を用いて簡単に計算できるため、従来の暗号化方法と比較して、高速処理が可能になる。
【００７１】
一方、本発明の暗号化方法における安全性については、公開鍵｛ｇ１，ｇ２｝には、それぞれ乱数ｓ，ｔが含まれているため、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎは互いに関係が断ち切られている。
【００７２】
よって、本発明の暗号化方法によれば、高い安全性を維持しつつ、計算量を減らして暗号化および復号化の高速処理を行うことが可能になる。
【００７３】
本発明の暗号化方法は、上記の課題を解決するために、素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）で表されるｇ１を公開鍵として生成するとともに、入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを生成することを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
（ただし、情報ｂ＝size of ｐ（bits）であって、０＜ｍ＜２ｂ−１，ｇｃｄ｛ｓ，ｑ−１｝＝１とする）。
【００７４】
上記の暗号化方法によれば、公開鍵として生成した鍵ｇ１は、（ｐ−１）のべき乗を含んでおり、公開鍵ｇ１及び秘密鍵ｎを用いて生成した暗号文Ｃも、（ｐ−１）のべき乗を含んでいるため、この暗号文Ｃを復号化する際において、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、簡単に復号化することができる。
【００７５】
すなわち、本発明の暗号化方法は、２つの大きな素数ｐ，ｑを発生させ、これを秘密鍵として用いるとともに、この秘密鍵｛ｐ，ｑ｝と乱数ｓ，ｔとを用いて、それぞれ（ｐ−１）のべき乗を含むように公開鍵ｇ１を生成している。
【００７６】
さらに、秘密鍵ｐのサイズｂとの関係において、メッセージｍに長さの制限を課し、このサイズｂを用いることで、暗号文の生成および復号化の計算をそれぞれ１つの式で行うことができるため、中国人剰余定理を用いることなく、より簡単な計算により暗号化復号化処理を行うことができる。
【００７７】
また、本発明の暗号化方法によって生成された暗号文は、上記の暗号化方法と同様に、公開鍵ｇ１を用いて、（ｐ−１）のべき乗を含んだ式で表されるため、その復号化にはフェルマーの小定理を用いることが可能である。
【００７８】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。
【００７９】
よって、単純な秘密鍵｛ｐ，ｑ｝を用いて、簡単な計算で公開鍵ｇ１を生成し、暗号文も簡単な計算で算出でき、さらにこの暗号文の復号化についても、フェルマーの小定理を用いるだけで簡単に計算できるため、従来の暗号化方法と比較して、高速処理が可能になる。
【００８０】
一方、本発明の暗号化方法における安全性については、公開鍵ｇ１には、乱数ｓが含まれているため、公開鍵ｇ１及び秘密鍵ｎは互いに関係が断ち切られている。
【００８１】
よって、本発明の暗号化方法によれば、高い安全性を維持しつつ、計算量を減らして暗号化および復号化の高速処理を行うことが可能になる。
【００８２】
本発明の復号化方法は、上記の課題を解決するために、２つの素数ｐ，ｑを秘密鍵として生成し、その積ｎ＝ｐｑと、２つの乱数ｓ，ｔと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１），（２）で表されるｇ１，ｇ２を公開鍵として用いるとともに、上記公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎおよび乱数ｒ１，ｒ２を用いて、下記の関係式（３），（４）で表される平文ｍを暗号化した暗号文Ｃ＝（Ｃ１，Ｃ２）を受信し、フェルマーの小定理を用いて下記の関係式（５），（６）で表される受信暗号文ａ，ｂを生成し、該受信暗号文ａ，ｂから、中国人剰余定理を用いて、下記の関係式（７）を満たす平文ｍを導出し、復号化処理を行うことを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）
ａ＝Ｃ１（ｍｏｄｐ）＝ｍ（ｍｏｄｐ）  ・・・・・（５）
ｂ＝Ｃ２（ｍｏｄｑ）＝ｍ（ｍｏｄｑ）  ・・・・・（６）
ｍ＝ａＡｑ＋ｂＢｐ（ｍｏｄｎ）  ・・・・・（７）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１、ｇｃｄ｛ｔ，ｐ−１｝＝１、Ａｑ（ｍｏｄｐ）＝１、Ｂｐ（ｍｏｄｑ）＝１とする）
上記の復号化方法によれば、公開鍵として生成した鍵ｇ１，ｇ２は、それぞれ（ｐ−１），（ｑ−１）のべき乗を含んでおり、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて生成した暗号文Ｃ１，Ｃ２も、（ｐ−１），（ｑ−１）のべき乗をそれぞれ含んでいるため、この暗号文Ｃ１，Ｃ２を復号化する際において、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、簡単に復号化することができる。
【００８３】
すなわち、本発明の復号化方法においては、暗号文は、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて、（ｐ−１），（ｑ−１）のべき乗を含んだ式で表されているため、その復号化にはフェルマーの小定理を用いることが可能になる。
【００８４】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。
【００８５】
よって、暗号文Ｃ１，Ｃ２から、フェルマーの小定理を用いて、暗号文Ｃ１，Ｃ２に対応する２つの受信暗号文を算出し、ここでさらに中国人剰余定理を用いることで、２つの受信暗号文から平文ｍを復号化できる。
【００８６】
本発明の復号化装置は、以上のように、フェルマーの小定理を用いて簡単に暗号文を復号化できるため、従来の復号化方式と比較して、高速処理が可能になる。
【００８７】
本発明の復号化方法は、上記の課題を解決するために、素数ｐ，ｑのうちｐを秘密鍵として生成し、その積ｎ＝ｐｑと、乱数ｓと、整数にｍｏｄｎの演算を施して得られる乗法群の最大生成源ｇとを用いて下記の関係式（１）で表されるｇ１を公開鍵として生成し、入力された平文ｍに対して、上記公開鍵ｇ１、秘密鍵ｎおよび乱数ｒを用いて、下記の関係式（３）’で表される暗号文Ｃを受信し、
フェルマーの小定理を用いて下記の関係式（８）を満たす平文ｍを導出し、復号化処理を行うことを特徴としている。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
ｍ＝Ｃ（ｍｏｄｐ）  ・・・・・（８）
（ただし、ｇｃｄ｛ｓ，ｑ−１｝＝１とする）
上記の復号化方法によれば、公開鍵ｇ１及び秘密鍵ｎを用いて生成した暗号文Ｃは、（ｐ−１）のべき乗を含んでいるため、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、この暗号文Ｃを簡単に復号化することができる。
【００８８】
すなわち、本発明の復号化方法は、秘密鍵ｐのサイズｂとの関係において、メッセージｍに長さの制限を課し、このサイズｂを用いることで、暗号文Ｃの生成および復号化の計算をそれぞれ１つの式で行うことができる。このため、中国人剰余定理を用いることなく、より簡単な計算により復号化処理を行うことができる。
【００８９】
また、本発明の復号化方法により復号化される暗号文は、公開鍵ｇ１及び秘密鍵ｎを用いて、（ｐ−１）のべき乗を含んだ式で表されるため、その復号化にはフェルマーの小定理を用いることが可能である。
【００９０】
フェルマーの小定理は、ａｐ−１≡１（ｍｏｄｐ）で表され、（ｐ−１）のべき乗を含む数に対して、ｍｏｄｐの演算を施すことでその剰余を「１」に帰着させることができる。
【００９１】
よって、単純な秘密鍵｛ｐ，ｑ｝を用いて、簡単な計算で公開鍵ｇ１を生成し、暗号文も簡単な計算で算出でき、さらに暗号文の復号化についても、フェルマーの小定理だけを用いることで簡単に計算できるため、従来の復号化方式と比較して、さらに高速処理が可能になる。
【発明の効果】
【００９２】
本発明の暗号化方法、復号化方法を用いた暗号化装置、復号化装置、暗号システムによれば、高い安全性を維持しつつ、計算量を減らして暗号化および復号化の高速処理を行うことが可能になる。
【発明を実施するための最良の形態】
【００９３】
〔実施形態１〕
本発明の暗号化装置および復号化装置、並びにこれらを備えた暗号システム、暗号化方法および復号化方法に関する一実施形態について、図１および図２に基づいて説明すれば以下のとおりである。
【００９４】
本実施形態の暗号システムは、図２に示すような、基本的な概念に基づいて、メッセージ（平文）ｍの暗号化および復号化を行う。
【００９５】
すなわち、図２に示すように、メッセージ（平文）ｍに公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて、乱数Ｒを掛けて暗号文ｍＲを生成し、これを相手先へ送信する。そして、暗号文ｍＲを受信した者は、秘密鍵｛ｐ，ｑ｝を用いて乱数Ｒを「１」に帰着させ、メッセージｍを復号する。
【００９６】
本実施形態の暗号システムは、図１に示すように、暗号化装置（暗号化演算手段）１１、通信路１４、および復号化演算装置（復号化演算手段）１５を備えている。
【００９７】
さらに、暗号化装置１１は、鍵生成部１２および暗号化演算装置１３を備えている。
【００９８】
鍵生成部１２は、メッセージｍの暗号化および復号化に使用する公開鍵｛ｇ１，ｇ２｝と秘密鍵｛ｐ，ｑ｝とをそれぞれ生成する。なお、公開鍵｛ｇ１，ｇ２｝および秘密鍵｛ｐ，ｑ｝の生成については、後段にて詳述する。
【００９９】
暗号化演算装置１３は、入力されたメッセージｍを公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて暗号文Ｃ１，Ｃ２を作成し、通信路１４へ出力する。
【０１００】
ここで、平文ｍは、ｍ１，ｍ２，ｍ３，…からなり、暗号文Ｃは、平文ｍ１を暗号化した暗号文Ｃ１、平文ｍ２を暗号化した暗号文Ｃ２、（以降同様）からなる。
【０１０１】
暗号文Ｃ１は２つの乱数Ｒ１、Ｒ２を使った暗号文Ｃ１１およびＣ１２からなる。
【０１０２】
Ｃ１＝（Ｃ１１，Ｃ１２）
Ｃ１１＝ｍ１Ｒ１（ｍｏｄｎ）
Ｃ１２＝ｍ１Ｒ２（ｍｏｄｎ）
実際の暗号化の手順としては、まず、最初の平文ｍ１だけを暗号化した暗号文Ｃ１＝（Ｃ１１，Ｃ１２）を作成し、それ以降の暗号文の作成については、平文ｍ２と２つの乱数Ｒ１，Ｒ２とを使用して暗号文を作成する。
【０１０３】
【数２】
2004246350.tif 000003
【０１０４】
但し、ｊの値は、ｍ１＝（ｂ１ｂ２…ｂｋ）のビット情報ｂ１に依存して決める。以降、Ｃ３、Ｃ４…についても同様に暗号化する。
【０１０５】
復号化演算装置１５は、通信路１４を介して暗号文Ｃ１，Ｃ２を受信するとともに、鍵生成部１２から秘密鍵｛ｐ，ｑ｝を受け取って、暗号文Ｃ１、Ｃ２からメッセージｍを復号して出力する。
【０１０６】
このように、公開鍵｛ｇ１，ｇ２｝を用いて、メッセージｍを暗号化して暗号文Ｃ１，Ｃ２として送信し、受信した側において、秘密鍵｛ｐ，ｑ｝を用いて暗号文Ｃ１，Ｃ２をメッセージｍに復号化することで、通信路１４におけるメッセージｍの漏洩、改竄等の問題の発生を防止して、安全性の高い通信を行うことができる。
【０１０７】
ここで、本実施形態の暗号システム１０によるメッセージｍの暗号化処理および復号化処理について説明すれば以下のとおりである。
【０１０８】
まず、鍵生成部１２による公開鍵｛ｇ１，ｇ２｝の生成について説明する。
【０１０９】
鍵生成部１２は、秘密鍵｛ｐ，ｑ｝（ｐ，ｑは大きな素数とする）、その積ｎ＝ｐｑ、ｇを整数×ｍｏｄｎの乗法群の最大生成源、ｓ，ｔをｇｃｄ｛ｓ，ｑ−１｝＝１，ｇｃｄ｛ｔ，ｐ−１｝＝１を満たす乱数とすると、公開鍵｛ｇ１，ｇ２｝を、以下の関係式（１）および関係式（２）で表される乱数として生成する。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
ｇ２＝ｇｔ（ｑ−１）（ｍｏｄｎ）  ・・・・・（２）。
【０１１０】
ここで、上記関係式（１），（２）には、乱数ｓ，ｔが含まれているため、ｎ＝ｐｑの式と上記関係式（１），（２）とは、完全に関係が断ち切られた状態となっている。よって、公開鍵｛ｇ１，ｇ２｝から秘密鍵｛ｐ，ｑ｝を導き出すためには、２つの大きな素数ｐ，ｑの積である「ｎ」から素因数分解によってｐ，ｑを導き出す必要がある。
【０１１１】
続いて、暗号化演算装置１３による上記関係式（１）および関係式（２）で表される公開鍵｛ｇ１，ｇ２｝を用いたメッセージｍの暗号文の作成について説明する。
【０１１２】
ｍをメッセージ（平文）（但し、ｍ＜ｎとする）、ｒ１，ｒ２を乱数、暗号文をＣ＝（Ｃ１，Ｃ２）とすると、暗号文Ｃ＝｛Ｃ１，Ｃ２｝は、公開鍵｛ｇ１，ｇ２｝及び秘密鍵ｎを用いて、以下に示す式によって表される。
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ・・・・・（３）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ・・・・・（４）。
【０１１３】
暗号文Ｃには、上記関係式（３）、関係式（４）に示すように、乱数ｇ１，ｇ２の乱数ｒ１，ｒ２が含まれているため、メッセージｍを乱数として相手先に送信できる。
【０１１４】
なお、上記関係式（３）および関係式（４）のｇ１ｒ１，ｇ２ｒ２が、図２に示す概念図における乱数Ｒに相当する。
【０１１５】
そして、復号化演算装置１５による暗号文Ｃ１，Ｃ２からメッセージｍへの復号化について説明する。
【０１１６】
復号化演算手段１５は、秘密鍵｛ｐ，ｑ｝を用いて、暗号文Ｃ１，Ｃ２をメッセージｍに復号化する。
【０１１７】
ここで、本発明の暗号システムでは、メッセージｍを復号化する際に、先ず、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、（ｐ−１）のべき乗が含まれている乱数部分を「１」に帰着させることができるため、以下に示す受信暗号文ａ，ｂが生成される。
ａ＝Ｃ１（ｍｏｄｐ）＝ｍ（ｍｏｄｐ）  ・・・・・（５）
ｂ＝Ｃ２（ｍｏｄｑ）＝ｍ（ｍｏｄｑ）  ・・・・・（６）。
【０１１８】
ここで、上記関係式（５）および関係式（６）の右辺について、ｍ＞ｐ、ｍ＞ｑであるため、ｍ（ｍｏｄｐ）およびｍ（ｍｏｄｑ）は乱数であり、メッセージｍは完全に復号されていない。
【０１１９】
そこで、本発明の暗号システムでは、上記２つの関係式（５）および関係式（６）に基づいて、中国人剰余定理を用いてメッセージｍを復号する。
【０１２０】
すなわち、中国人剰余定理を用いれば、メッセージｍは、上記関係式（５）および関係式（６）に基づいて以下の関係式（７）によって表されるため、復号化されたことがわかる。
ｍ＝ａＡｑ＋ｂＢｐ（ｍｏｄｎ）・・・・・（７）
（ただし、Ａｑ（ｍｏｄｐ）＝１，Ｂｐ（ｍｏｄｑ）＝１とする）。
【０１２１】
本発明の暗号システムは、以上のように、フェルマーの小定理を用いて復号化することができるように、（ｐ−１）乗、（ｑ−１）乗を含むように公開鍵｛ｇ１，ｇ２｝を生成し、復号化の際には、フェルマーの小定理および中国人剰余定理を用いてメッセージｍを復号化する。
【０１２２】
これにより、非常に簡単な計算で公開鍵｛ｇ１，ｇ２｝を生成できるため、極めて簡単な暗号系を提案できる。また、２つの大きな素数ｐ，ｑをそのまま秘密鍵｛ｐ，ｑ｝として用いることができる。さらに、フェルマーの小定理と中国人剰余定理とを用いて簡単な計算によりメッセージｍを復号できるため、従来のＲＳＡ暗号システムと比較して、暗号化する際の計算量を減らして、高速処理が可能な暗号システムを得ることができる。
【０１２３】
〔実施形態２〕
本発明の暗号化装置および復号化装置、並びにこれらを備えた暗号システム、暗号化方法および復号化方法に関する他の実施形態について説明すれば、以下のとおりである。
【０１２４】
本実施形態の暗号システムは、上記実施形態１の暗号システムと基本的な原理については同様であるが、秘密鍵ｐのサイズｂをメッセージｍとの関係で制限することを条件として、アルゴリズムをより単純化することができる。
【０１２５】
すなわち、上記実施形態１の暗号システムでは、１つのメッセージｍに対して、２つの暗号文Ｃ１，Ｃ２を生成しているが、本実施形態の暗号システムでは、秘密鍵ｐのサイズｂを０＜ｍ＜２ｂ−１という条件式を満たすように制限し、このサイズｂを用いることで、１つの暗号文Ｃを生成し、これを復号するだけで済むため、より暗号化、復号化処理を高速化が図れる。
【０１２６】
具体的には、暗号化演算装置は、乱数ｒを発生させるとともに、秘密鍵ｐのサイズｂと、秘密鍵ｐとを用いて下記の関係式（１）で表される公開鍵ｇと、（３）’で表される暗号文Ｃを生成する。
ｇ１＝ｇｓ（ｐ−１）（ｍｏｄｎ）  ・・・・・（１）
Ｃ＝ｍ・ｇ１ｒ（ｍｏｄｎ）  ・・・・・（３）’
（ただし、メッセージｍとサイズｂとは、０＜ｍ＜２ｂ−１の条件式を満たす）。
【０１２７】
続いて、上記暗号文Ｃの復号化については、上記実施形態１の暗号システムと同様に、復号化演算装置が、フェルマーの小定理（ａｐ−１≡１（ｍｏｄｐ））を用いて、下記の関係式（８）を導出する。
ｍ＝Ｃ（ｍｏｄｐ）  ・・・・・（８）。
【０１２８】
ここで、暗号文Ｃには、ｇ１が含まれており、実施形態１のｇ１の関係式（１）より、ｇ１は（ｐ−１）乗を含んでいるため、（ｍｏｄｐ）をとることにより、ｍ以外の数を１に帰着させることができるため、メッセージｍを容易に復号化できる。
【０１２９】
本実施形態の暗号システムでは、以上のように、秘密鍵ｐのサイズｂについてメッセージｍとの関係で制限する。そして、公開鍵ｇ１を生成して、１つの暗号文Ｃを生成し、この暗号文Ｃを秘密鍵ｐを用いて復号するため、実施形態１で用いた中国人剰余定理を用いなくても容易に復号化処理を行うことができる。
【０１３０】
よって、上記実施形態１の暗号システムと等価の安全性を維持しつつ、実施形態１の暗号化装置よりもさらに高速処理が可能な暗号システムを得ることができる。
【０１３１】
また、上述した本実施形態の暗号システムは、以下のような特徴を有している。
【０１３２】
１つ目の特徴としては、暗号文Ｃ１，Ｃ２を示す上記関係式（３），（４）には、ｇ１ｒ１が含まれているため、メッセージｍを送るたびに暗号文が異なる、いわゆる確率暗号となっている。これは、べき乗の「ｒ」が乱数であることによる特徴である。よって、ＲＳＡ暗号化方式では、メッセージｍと暗号文Ｃとが一対一に対応するのに対し、本発明の暗号システムでは、メッセージｍと暗号文Ｃとが一対一に対応しないため、暗号文Ｃから解読することが困難であり、より暗号強度を高めることができる。
【０１３３】
２つ目の特徴としては、メッセージｍから暗号文Ｃへの変換は容易であるが、その逆の変換は非常に困難である、いわゆる一方向性関数であることが挙げられる。
【０１３４】
３つ目の特徴としては、１つ目の特徴としてあげたように、メッセージｍと暗号文Ｃとが一対一に対応しないため、生成された暗号文が同じ暗号文Ｃであっても、元のメッセージが異なるメッセージｍ０，ｍ１である可能性がある。よって、暗号文Ｃからは、どのメッセージｍを暗号化したものかわかりにくいため、暗号強度を高めることができる。
【０１３５】
ここでさらに、暗号解析者による以下に示す３種類の攻撃に対する本発明の暗号システムの安全性について説明すれば以下のとおりである。
【０１３６】
まず、１つ目の攻撃として、選択平文攻撃（Chosen Plaintext Attack：ＣＰＡ）に対する安全性について説明する。
【０１３７】
この選択平文攻撃は、通常、暗号文を作成する際のプロセスであり、与えられた平文（メッセージ）ｍに対する暗号文のペアを多数作成し、新しい暗号文が与えられた際に平文を求めることができるか否かについて調べることで、暗号文を復号する鍵を求める攻撃である。
【０１３８】
これに対し、本発明の暗号システムは、上述のように、一方向性関数であって、かつ確率暗号であるため、メッセージｍと暗号文Ｃとが一対一に対応していない。このため、この選択平文攻撃に対する本発明の暗号システムの安全性は高いことがわかる。
【０１３９】
２つ目の攻撃として、非適応型選択暗号文攻撃（Non-Adaptive Chosen Ciphertext Attack：ＣＣＡ１）に対する安全性について検討する。
【０１４０】
この非適応型選択暗号文攻撃は、暗号文を与えてこれに対応する平文のペアを作成し、ターゲットとなる暗号文を与えて平文が求められるかを調べる攻撃であって、かつ復号化したいターゲットとなる暗号文に質問した後は一切質問不可となる条件の攻撃である。
【０１４１】
これに対して、本発明の暗号システムは、上記と同様に、一方向性関数であって、かつ確率暗号であるため、メッセージｍと暗号文Ｃとが一対一に対応していない。このため、この非適応型選択暗号文攻撃に対する本発明の暗号システムの安全性は高いことがわかる。
【０１４２】
３つ目の攻撃として、適応型選択暗号文攻撃（Adaptive Chosen Ciphertext Attack：ＣＣＡ２）に対する安全性について説明する。
【０１４３】
この適応型選択暗号文攻撃は、暗号文を与えてこれに対応する平文のペアを作成し、ターゲットとなる暗号文を与えて平文が求められるかを調べる攻撃であって、かつ復号化したいターゲットとなる暗号文以外は何をいつ聞いてもよいという条件で、前回の結果を活用して繰り返し処理を行う攻撃である。
【０１４４】
これに対して、本発明の暗号システムは、ターゲットとなる暗号文が識別不能であるため、完全に安全であるとは言い難い。
【０１４５】
つまり、ターゲットとなる暗号文Ｃ＝（Ｃ１，Ｃ２）とすると、Ｃ１，Ｃ２は以下に示すようになる。
Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ）  ⇒  Ｃ１＊＝ｍ・ｇ１ｒ１＋ｔ１（ｍｏｄｎ）
Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）  ⇒  Ｃ２＊＝ｍ・ｇ２ｒ２＋ｔ２（ｍｏｄｎ）
ここで求めたＣ＊＝（Ｃ１＊，Ｃ２＊）はＣ＊≠Ｃであるが、Ｃ＊を提示して平文ｍを得ることができるため、本発明の暗号システムは、この適応型選択暗号文攻撃に対しては安全ではないといえる。
【０１４６】
そこで、本実施形態の暗号システムでは、適応型選択暗号文攻撃に対して耐性を持たせるために、Ｃ＝（Ｃ１，Ｃ２，ｅ）とする。
【０１４７】
ただし、「ｅ」は、Ｃ１＝ｍ・ｇ１ｒ１（ｍｏｄｎ），Ｃ２＝ｍ・ｇ２ｒ２（ｍｏｄｎ）より、ｄ＝（Ｃ１＋Ｃ２）／ｍ（ｍｏｄｎ）であるから，ｅ＝ｈ（ｄ）（ｈは一方向性ハッシュ関数）とする。
【０１４８】
これにより、暗号文Ｃは長くなるという問題はあるが、ｅを３２bitsまたは６４bitsにまとめることができるとともに、メッセージｍが少しでも変わるとｅが一致しなくなるため、上記適応型選択暗号文攻撃に対して耐性を持たせて、信頼度の高い暗号システムを得ることができる。
【０１４９】
なお、本発明の暗号システムは、以下に示すデータベースを用いることにより、演算をより高速化できる。
ＤＢ（２，ｅ）＝［Ｒｉｊ＝ｇｉｒｉｊ（ｍｏｄｎ）］
（ただし、１≦ｉ≦２，１≦ｊ≦ｅ）
Ｃ＝（Ｃ１，Ｃ２）
【０１５０】
【数１】
2004246350.tif 000004
【０１５１】
すなわち、２行×ｅ列のデータベースにＲｉｊを前もって計算して蓄積しておくことで、暗号化処理を行う際には、このデータベースからＲｉｊを取り出して乱数部分を作ることができるため、暗号化処理をより高速化できる。
【０１５２】
これにより、例えば、計算量が多い従来のＲＳＡ暗号方式と比較して、暗号化処理を高速化できるとともに、復号化処理についてはｍｏｄｐの演算を施すことだけで復号化できるため、計算量が多いＲＳＡ暗号化方式と比較してはるかに高速化できる。
【０１５３】
さらに、本発明の暗号システムは、べき乗の特性を利用して、図３に示すような拡張ブロックサイファに応用することができる。
【０１５４】
この拡張ブロックサイファは、暗号文Ｃ１だけを通常のスキルで暗号文Ｃ１１，Ｃ１２に暗号化し、後のＣ２以降の暗号文については前の暗号文Ｃ１１，Ｃ１２に含まれる２つの乱数Ｒ１，Ｒ２を使用して暗号文を作成するため、従来の共通鍵暗号系と公開鍵暗号系とで処理をより高速化できる。
【０１５５】
具体的には、最初の暗号文Ｃ１についてのみ通常の手順で暗号文Ｃ１１，Ｃ１２を作成し、Ｃ２以降の暗号文については、最初のビットｂｉ＝０の場合には、Ｒ１を加算し、最初のビットｂｉ＝１の場合には、Ｒ２を加算していくことで、暗号文Ｃを作成できる。
【０１５６】
【表１】
2004246350.tif 000005
【０１５７】
表１は、図３に示す拡張ブロックサイファによって計算回数をどれだけ減らせるかを示している。
【０１５８】
暗号化処理については、表１上段に示すように、ブロック長ｋとすると、べき乗計算、掛け算ともに、計算回数を２／ｋ回に減らせることが分かる。
【０１５９】
復号化処理については、表１下段に示すように、ブロック長ｋとすると、割り算については４／ｋ回に、掛け算については２／ｋ回に減らせることが分かる。
【０１６０】
以上のように、本発明の暗号システムの応用例として、拡張ブロックサイファを適用することで、より計算回数の少ない高速処理が可能なハイブリッド型の暗号システムを得ることができる。
【０１６１】
なお、上記実施形態２の単純化した暗号システムにこの拡張ブロックサイファを適用した場合には、表１に示す計算回数は全て１回になり、非常に使い易い暗号システムが得られる。
【０１６２】
さらに、本発明の暗号システムをディジタル署名に適応させた場合について説明すれば以下のとおりである。
【０１６３】
まず、公開鍵｛ｇ１，ｇ２｝の指数部分ｓ（ｐ−１）とｔ（ｑ−１）とをα、βとすると、署名（ｕ，ｖ）は以下の式で表される。
ｕ＝αｒ＋βｍ（ｍｏｄΦ（ｎ））  ・・・・・（１２）
ｖ＝ｇ（α２ｒ＋β２）（ｍｏｄｎ）  ・・・・・（１３）
（ただし、メッセージｍ，ｍ≦Ｍｅ≦Φ（ｎ），乱数ｒとする）。
【０１６４】
上記関係式（１２）より、ｕには不明な変数が３つ以上あるため、この式を解くことはできない。また、上記関係式（１３）より、ｖでは、ｇ，α，β，ｒは全て秘密の変数であるため、この式を解くこともできない。
【０１６５】
また、この署名付きメッセージ｛ｍ，（ｕ，ｖ）｝の認証式は、以下の関係式で表される。
（ｇ１ｍｇ２）ｕ＝ｖｍ（ｍｏｄｎ）  ・・・・・（１４）。
【０１６６】
続いて、この関係式（１４）を認証する。
【０１６７】
（ｇ１ｍ・ｇ２）ｕ＝ｇ（αｍ＋β）（αｒ＋βｍ）（ｍｏｄｎ）
＝ｇ（α２ｒ＋β２）ｍ（ｍｏｄｎ）
＝ｖｍ（ｍｏｄｎ）
（ただし、ｇαβ＝ｇｓｔ（ｐ−１）（ｑ−１）＝ｇｓｔΦ（ｎ）＝１（ｍｏｄｎ）とする）。
【０１６８】
これにより、署名した人から送信されたメッセージｍであることが認証された。
【０１６９】
本発明の暗号システムは、以上のように、従来とは異なる新たな方式であって、安全性が高く、高速処理が可能なディジタル署名を提案できる。
【０１７０】
なお、本発明の暗号化装置および復号化装置、並びにこれらを備えた暗号システム、暗号化方法および復号化方法は、例えば、相手認証、相互認証、電子選挙および電子入札等にも適用することができる。
【０１７１】
また、本発明の暗号システムは、２つの大きな素数ｐ，ｑを秘密鍵として用いるとともに、素数ｐ，ｑについてその積ｎ＝ｐｑと、（ｐ−１）および（ｑ−１）のべき乗および乱数ｓ、ｔを含むｇ１，ｇ２とを公開鍵｛ｇ１，ｇ２｝、秘密鍵ｎとして、暗号文Ｃ＝（Ｃ１，Ｃ２）を作成する暗号化装置と、該暗号文Ｃに対してフェルマーの小定理を用いて暗号文Ｃを復号化する復号化装置とを備えていることを特徴とする暗号システムと、関係式を用いることなく表現することもできる。
【０１７２】
なお、本発明の暗号化技術は、例えば、家庭内の小さな領域でのストリーミングデータのスクランブラあるいはデスクランブラに適用することが可能である。
【０１７３】
また、本発明は、暗号鍵の配布に適用することも可能である。
【０１７４】
本発明は上述した各実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、異なる実施形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【図面の簡単な説明】
【０１７５】
【図１】本発明の暗号化装置および復号化装置、並びにこれらを備えた暗号システム、暗号化方法および復号化方法の一実施形態を示す暗号システムの構成を示すブロック図である。
【図２】本発明の暗号化および復号化処理の概念を簡潔に示すブロック図である。
【図３】本発明の暗号システムの応用例としての拡張ブロックサイファの態様を示す図である。
【符号の説明】
【０１７６】
１０      暗号システム
１１      暗号化装置
１２      鍵生成部
１３      暗号化演算装置
１４      通信路
１５      復号化演算装置
ｍ      メッセージ（平文）
ｎ      秘密鍵（２つの大きな素数の積）
ｇ１，ｇ２   公開鍵
ｐ，ｑ      秘密鍵（２つの大きな素数）
Ｃ      暗号文
Ｃ１，Ｃ２   暗号文
【図１】
2004246350.tif 000006
【図２】
2004246350.tif 000007
【図３】
2004246350.tif 000008