Top > Search of Japanese Patents > (In Japanese)暗号化/復号化プログラム、暗号化/復号化装置及び拡大体の乗算装置

(In Japanese)暗号化/復号化プログラム、暗号化/復号化装置及び拡大体の乗算装置 meetings foreign

Patent code P110005386
Posted date Aug 18, 2011
Application number P2008-526767
Patent number P4836208
Date of filing Jul 24, 2007
Date of registration Oct 7, 2011
International application number JP2007064474
International publication number WO2008013154
Date of international filing Jul 24, 2007
Date of international publication Jan 31, 2008
Priority data
  • P2006-200946 (Jul 24, 2006) JP
  • P2007-010072 (Jan 19, 2007) JP
Inventor
  • (In Japanese)野上 保之
  • (In Japanese)森川 良孝
Applicant
  • (In Japanese)国立大学法人岡山大学
Title (In Japanese)暗号化/復号化プログラム、暗号化/復号化装置及び拡大体の乗算装置 meetings foreign
Abstract (In Japanese)任意な鍵長を選択可能としながら高速に拡大体の乗算処理を実行可能とした暗号化/復号化プログラム、暗号化/復号化装置、及び拡大体の乗算装置を提供する。
素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を乗算する際に、km+1が素数であって、Fkm+1でpが原始元となる正整数kを特定し、2つの元A,Bを、正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として演算し、この演算結果を用いて部分体である拡大次数mの拡大体Fpmの元における乗算の結果を求める。
Outline of related art and contending technology (In Japanese)

従来、インターネットなどの電気通信回線を利用した情報通信において、送受信されるデータの秘匿性を保持するために、データの暗号化が行われている。すなわち、平文データを送信する送信者は、平文データに暗号化処理を施して暗号データを生成し、この暗号データを受信者に送信している。一方、暗号データを受信した受信者は、暗号データに復号化処理を施して平文データを生成することにより、平文データを受け取ることができる。

このような暗号化及び復号化の方法として、昨今では公開鍵暗号と呼ばれる方法が用いられている。公開鍵暗号では、公開鍵と秘密鍵があらかじめ設定され、所定の平文データを送信する送信者に公開鍵を開示しており、送信者は公開鍵を用いて平文データを暗号化することにより暗号データを生成し、受信者に送信している。受信者は、暗号データを受信すると、秘密鍵を用いて暗号データを復号化して平文データを生成している。

ここで、平文データを暗号化する場合には、平文データを暗号化に用いる公開鍵の鍵長に合わせた所定のデータ長ごとに分断して複数の単位長平文データを生成し、各単位長平文データと公開鍵を用いて乗算処理を行うことにより単位長暗号データを生成し、所定数の単位長暗号データで構成された暗号データを生成している。

一方、暗号データを復号化する場合には、暗号データを復号化に用いる秘密鍵の鍵長に合わせた所定のデータ長ごとに分断して複数の単位長暗号データを生成し、各単位長暗号データと秘密鍵を用いて乗算処理を行うことにより単位長平文データを生成し、所定数の単位長平文データで構成された平文データを生成している。

このような公開鍵暗号には様々な方式が提案されており、Rivest Shamir Adleman(RSA)暗号、楕円曲線暗号、ElGamal暗号などが知られている。

昨今、パーソナルコンピュータなどの電子計算機の性能向上にともなって、各種の暗号方法で暗号化された暗号データが解読されるおそれが高まっている。すなわち、暗号データは、秘密鍵さえ分かれば解読できることから、電子計算機によって手当たり次第に秘密鍵を生成して復号化を試みることにより、時間はかかるものの解読されるおそれがあった。

そこで、各暗号方法では、安全性を高めるために公開鍵及び秘密鍵の鍵長を長くすることが行われている。すなわち、公開鍵及び秘密鍵の鍵長を長くすると、解読に用いる秘密鍵の数が飛躍的に増大し、現実的な時間内での解読を不可能とすることができるからである。そのため、現在では、RSA暗号では1024ビット以上、楕円曲線暗号では160ビット以上、ElGamal暗号では1024ビット以上の鍵長が求められている。

しかしながら、公開鍵及び秘密鍵の鍵長を長くした場合には、公開鍵を用いた乗算処理による暗号化、及び秘密鍵を用いた乗算処理による復号化に多大な時間を要することとなっていた。この場合、処理時間の短縮のためには、乗算処理の演算速度が高速な演算手段が必要となることにより、安全性を高めるためのコストが増大することとなっていた。

一方で、現実的には、電気通信回線中を流れているデータにおいては重要度が様々に異なっており、利用価値が高いために高度の秘匿性が必要なデータから、利用価値が低いために秘匿性を必要としないデータまでが存在している。

したがって、何れのデータに対しても同等の安全性で暗号化する必要はなく、高い安全性が要求されるデータには長い鍵長の公開鍵及び秘密鍵を用い、高い安全性が要求されないデータには短い鍵長の公開鍵及び秘密鍵が用いられている。

また、パーソナルコンピュータなどのような高速な演算処理の実行が可能な装置では、できるだけ長い鍵長の公開鍵及び秘密鍵による暗号化が利用されており、携帯電話機やICカードなどのような演算処理能力の乏しい装置では、比較的短い鍵長の公開鍵及び秘密鍵による暗号化が利用され、保証され得る安全性の範囲内でデータの送受信が行われている。

特に、パーソナルコンピュータなどの電子計算機では、複数種類の鍵長の公開鍵及び秘密鍵が利用可能となっており、送信するデータに応じた安全性、あるいは送信先の装置における乗算処理の処理能力などに応じて鍵長を変えて暗号化することも行われており、鍵長に汎用性を持たせることが提案されている(例えば、特許文献1参照。)。
【特許文献1】
特開2001-051832号公報

Field of industrial application (In Japanese)

本発明は、暗号化/復号化プログラム、暗号化/復号化装置、及び暗号化または復号化における乗算処理を実行する拡大体の乗算装置に関する。

Scope of claims (In Japanese)
【請求項1】
 
素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、
電子計算機で、前記平文データと前記暗号化鍵とを乗算して暗号データの元C={c0,c1,c2,・・・,cm-1}を生成させる、または前記暗号データと前記復号化鍵とを乗算して平文データの元C={c0,c1,c2,・・・,cm-1}を生成させる暗号化/復号化プログラムにおいて、
km+1が素数であって、Fkm+1でpが原始元となる正整数kを特定する第1のステップと、
前記の2つの元A,Bを、前記正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として乗算を行う第2のステップと、
この乗算の結果を用いて部分体である前記拡大次数mの拡大体Fpmの元における乗算の結果を求める第3のステップと
を有することを特徴とする暗号化/復号化プログラム。

【請求項2】
 
0≦i≦m-1、0≦j≦k-1とし、
<x>がxのmod(km+1)をとるものとして、
前記第2のステップは、
0≦t≦k-1で、<pmt>=K[t]となる各K[t]をそれぞれ求めるステップと、
0≦i≦kmで、それぞれ0=q[<i>]とするステップと、
0≦i≦m-1で、aibimodp=q[<pi>]をそれぞれ求めるステップと、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k-1でq[<pi+(pjK[t])>]にMをそれぞれ足し込むステップと
を有することを特徴とする請求項1記載の暗号化/復号化プログラム。

【請求項3】
 
前記第3のステップは、
0≦i≦m-1で、かつ1≦t≦k-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むステップと、
0≦i≦m-1で、kq[<0>]-q[<pi>]=ciをそれぞれ求めるステップと
を有することを特徴とする請求項2記載の暗号化/復号化プログラム。

【請求項4】
 
k=2k'の場合に、
F2k'm+1でpが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'とし、
0≦i≦m-1、0≦j≦2k'-1とし、
<x>がxのmod(2k'm+1)をとるものとして、
前記第2のステップは、
0≦t≦k'-1で、<pmt>=K[t]となる各K[t]をそれぞれ求めるステップと、
0≦i≦2k'mで、それぞれ0=q[<i>]とするステップと、
0≦i≦m-1で、aibimodp=q[<pi>]をそれぞれ求めるステップと、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k'-1でq[<pi+(pjK[t])>]にMをそれぞれ足し込むとともに、q[<pi-(pjK[t])>]にMをそれぞれ足し込むステップと
を有することを特徴とする請求項1記載の暗号化/復号化プログラム。

【請求項5】
 
前記第3のステップは、
0≦i≦m-1で、かつ1≦t≦k'-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むとともに、q[<pi>]にq[<-(piK[t])>]をそれぞれ足し込むステップと、
0≦i≦m-1で、-q[<pi>]=ciをそれぞれ求めるステップと
を有することを特徴とする請求項4記載の暗号化/復号化プログラム。

【請求項6】
 
素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、
前記平文データと前記暗号化鍵とを乗算させて元C={c0,c1,c2,・・・,cm-1}を生成することにより暗号化する、または前記暗号データと前記復号化鍵とを乗算させて元C={c0,c1,c2,・・・,cm-1}を生成することにより復号化する演算器を備えた暗号化/復号化装置において、
前記元をそれぞれ記憶する第1の記憶部と、
前記拡大次数mを記憶する第2の記憶部と、
km+1が素数であって、Fkm+1でpが原始元となる正整数kを前記演算器による演算に基づいて特定して記憶する第3の記憶部と、
前記の2つの元A,Bを、前記正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として前記演算器で乗算した結果を記憶する第4の記憶部と、
前記拡大次数kmの拡大体Fpkmの元の乗算結果を用いて前記演算器で所定の演算を行って、部分体である前記拡大次数mの拡大体Fpmの元における乗算の結果を求めて記憶する第5の記憶部と
を有することを特徴とする暗号化/復号化装置。

【請求項7】
 
0≦i≦m-1、0≦j≦k-1とし、
<x>がxのmod(km+1)をとるものとして、
前記第4の記憶部は、
0≦t≦k-1で、<pmt>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
0≦i≦kmで、それぞれ0=q[<i>]として記憶する記憶部と、
0≦i≦m-1で、aibimodp=q[<pi>]をそれぞれ求めて記憶する記憶部と、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶する記憶部と、
0≦t≦k-1でq[<pi+(pjK[t])>]にMをそれぞれ足し込んで記憶する記憶部と
を有することを特徴とする請求項6記載の暗号化/復号化装置。

【請求項8】
 
前記第5の記憶部は、
0≦i≦m-1で、かつ1≦t≦k-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込んで記憶する記憶部と、
0≦i≦m-1で、kq[<0>]-q[<pi>]=ciをそれぞれ求めて記憶する記憶部と
を有することを特徴とする請求項7記載の暗号化/復号化装置。

【請求項9】
 
k=2k'の場合に、
F2k'm+1でpが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'として、この正整数k'を記憶する記憶部を有し、
0≦i≦m-1、0≦j≦2k'-1とし、
<x>がxのmod(2k'm+1)をとるものとして、
前記第4の記憶部は、
0≦t≦k'-1で、<pmt>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
0≦i≦2k'mで、それぞれ0=q[<i>]として記憶する記憶部と、
0≦i≦m-1で、aibimodp=q[<pi>]をそれぞれ求めて記憶する記憶部と、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶する記憶部と、
0≦t≦k'-1でq[<pi+(pjK[t])>]にMをそれぞれ足し込し込んで記憶するとともに、q[<pi-(pjK[t])>]にMをそれぞれ足し込んで記憶する記憶部と
を有することを特徴とする請求項6記載の暗号化/復号化装置。

【請求項10】
 
前記第5の記憶部は、
0≦i≦m-1で、かつ1≦t≦k'-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むとともに、q[<pi>]にq[<-(piK[t])>]をそれぞれ足し込んで記憶する記憶部と、
0≦i≦m-1で、-q[<pi>]=ciをそれぞれ求めて記憶する記憶部と
を有することを特徴とする請求項9記載の暗号化/復号化装置。

【請求項11】
 
素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を乗算して元C={c0,c1,c2,・・・,cm-1}を生成する演算器を備えた拡大体の乗算装置において、
前記元をそれぞれ記憶する第1の記憶部と、
前記拡大次数mを記憶する第2の記憶部と、
km+1が素数であって、Fkm+1でpが原始元となる正整数kを前記演算器による演算に基づいて特定して記憶する第3の記憶部と、
前記の2つの元A,Bを、前記正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として前記演算器で乗算した結果を記憶する第4の記憶部と、
前記拡大次数kmの拡大体Fpkmの元の乗算結果を用いて前記演算器で所定の演算を行って、部分体である前記拡大次数mの拡大体Fpmの元における乗算の結果を求めて記憶する第5の記憶部と
を有することを特徴とする拡大体の乗算装置。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2008526767thum.jpg
State of application right Registered
(In Japanese)特許内容に関しての問い合せ窓口は岡山大学連携機構知的財産部門です。
技術移転に関しては岡山TLOが窓口になります。


PAGE TOP

close
close
close
close
close
close
close