JP2000293507A - 有限体演算における表現データ生成装置および方法 - Google Patents
有限体演算における表現データ生成装置および方法Info
- Publication number
- JP2000293507A JP2000293507A JP11102920A JP10292099A JP2000293507A JP 2000293507 A JP2000293507 A JP 2000293507A JP 11102920 A JP11102920 A JP 11102920A JP 10292099 A JP10292099 A JP 10292099A JP 2000293507 A JP2000293507 A JP 2000293507A
- Authority
- JP
- Japan
- Prior art keywords
- expression data
- data
- finite field
- condition
- expression
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Computational Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Abstract
(57)【要約】
【課題】 ユーザの負荷をなるべく軽減しながら、有限
体の表現データを柔軟に設定することが課題である。 【解決手段】 ユーザが入出力装置１１から自動条件指
定インタフェース１２を介して指定条件を入力すると、
表現データ生成器１５は、固定データテーブル１４を参
照し、固定データテーブル１４に条件を満たす表現デー
タがなければ、自動的に表現データを生成する。生成さ
れた表現データは表現データ格納域１７に設定され、有
限体演算装置１８は、その表現データを参照して、有限
体演算を行う。
体の表現データを柔軟に設定することが課題である。 【解決手段】 ユーザが入出力装置１１から自動条件指
定インタフェース１２を介して指定条件を入力すると、
表現データ生成器１５は、固定データテーブル１４を参
照し、固定データテーブル１４に条件を満たす表現デー
タがなければ、自動的に表現データを生成する。生成さ
れた表現データは表現データ格納域１７に設定され、有
限体演算装置１８は、その表現データを参照して、有限
体演算を行う。
Description
【０００１】
【発明の属する技術分野】本発明は、符号、暗号等に関
する有限体演算を行う際に、有限体の表現データを自動
的に設定するデータ生成装置およびその方法に関する。
する有限体演算を行う際に、有限体の表現データを自動
的に設定するデータ生成装置およびその方法に関する。
【０００２】
【従来の技術】近年のコンピュータ技術およびネットワ
ーク技術の発展に伴い、符号、暗号等を含む様々な分野
において、有限体演算を行う局面が増えてきている。有
限体（finite field）とは、四則演算が定義されている
有限集合を指し、有限体演算とは、有限体上で定義され
たこれらの演算を指す。
ーク技術の発展に伴い、符号、暗号等を含む様々な分野
において、有限体演算を行う局面が増えてきている。有
限体（finite field）とは、四則演算が定義されている
有限集合を指し、有限体演算とは、有限体上で定義され
たこれらの演算を指す。
【０００３】特に、電子商取引等のインターネットを利
用したビジネスにおいては、オープンネットワークのセ
キュリティを確保するための暗号理論が非常に重要な技
術として脚光を浴びている。暗号技術を実現するために
は有限体演算が必須であるが、データのセキュリティを
保つために非常に大きなサイズの有限体を用いるケース
が多く、その演算効率を上げることは、実用上重要なテ
ーマである。
用したビジネスにおいては、オープンネットワークのセ
キュリティを確保するための暗号理論が非常に重要な技
術として脚光を浴びている。暗号技術を実現するために
は有限体演算が必須であるが、データのセキュリティを
保つために非常に大きなサイズの有限体を用いるケース
が多く、その演算効率を上げることは、実用上重要なテ
ーマである。
【０００４】有限体演算を実現するためには、まず、い
くつかの表現データを決定して、有限体を表現しなけれ
ばならない。有限体の要素（元）の個数は、ｐを素数と
し、ｍを正整数として、ｐm となる。この正整数ｍは拡
大次数と呼ばれる。一般に、有限体の要素を記述するた
めには、素数ｐ、拡大次数ｍ、およびｍ次の既約多項式
Ｆ（ｘ）を表現データとして設定しなければならないこ
とが知られている。
くつかの表現データを決定して、有限体を表現しなけれ
ばならない。有限体の要素（元）の個数は、ｐを素数と
し、ｍを正整数として、ｐm となる。この正整数ｍは拡
大次数と呼ばれる。一般に、有限体の要素を記述するた
めには、素数ｐ、拡大次数ｍ、およびｍ次の既約多項式
Ｆ（ｘ）を表現データとして設定しなければならないこ
とが知られている。
【０００５】従来の有限体演算装置においては、装置自
身があらかじめ内蔵している固定の表現データを用いる
か、もしくは、ユーザがすべての表現データを指定する
ことで、有限体を表現していた。
身があらかじめ内蔵している固定の表現データを用いる
か、もしくは、ユーザがすべての表現データを指定する
ことで、有限体を表現していた。
【０００６】
【発明が解決しようとする課題】しかしながら、従来の
有限体の表現方法には、次のような問題がある。固定の
表現データのみを用いる場合、符号、暗号等のシステム
における様々な局面に必要となる多様な表現データを得
ることができず、表現の柔軟性に欠ける。また、非常に
大きな有限体において、ユーザがすべての表現データを
指定する場合、表現データの選択に多大な労力を要す
る。さらに、ユーザが不適切な表現データを選択する
と、演算速度が低下し、システムの性能が低下するとい
った弊害が生じることもある。
有限体の表現方法には、次のような問題がある。固定の
表現データのみを用いる場合、符号、暗号等のシステム
における様々な局面に必要となる多様な表現データを得
ることができず、表現の柔軟性に欠ける。また、非常に
大きな有限体において、ユーザがすべての表現データを
指定する場合、表現データの選択に多大な労力を要す
る。さらに、ユーザが不適切な表現データを選択する
と、演算速度が低下し、システムの性能が低下するとい
った弊害が生じることもある。
【０００７】本発明の課題は、効率の良い有限体演算を
実現するために、ユーザの負荷をなるべく軽減しなが
ら、有限体の表現データを柔軟に設定するデータ生成装
置およびその方法を提供することである。
実現するために、ユーザの負荷をなるべく軽減しなが
ら、有限体の表現データを柔軟に設定するデータ生成装
置およびその方法を提供することである。
【０００８】
【課題を解決するための手段】図１は、本発明のデータ
生成装置の原理図である。図１のデータ生成装置は、入
力手段１、生成手段２、および表現データ格納手段３を
備える。入力手段１は、有限体を指定する条件を入力す
る。生成手段２は、入力された条件に基づいて、有限体
の表現データを自動的に生成し、表現データ格納手段３
は、生成された表現データを格納する。
生成装置の原理図である。図１のデータ生成装置は、入
力手段１、生成手段２、および表現データ格納手段３を
備える。入力手段１は、有限体を指定する条件を入力す
る。生成手段２は、入力された条件に基づいて、有限体
の表現データを自動的に生成し、表現データ格納手段３
は、生成された表現データを格納する。
【０００９】生成手段２は、入力手段１が入力した指定
条件に基づいて、その条件に対応する有限体の表現デー
タを自動的に生成し、生成された表現データを表現デー
タ格納手段３に格納する。格納された表現データは、有
限体演算を行う装置に供給され、その表現データを用い
た有限体演算が行われる。
条件に基づいて、その条件に対応する有限体の表現デー
タを自動的に生成し、生成された表現データを表現デー
タ格納手段３に格納する。格納された表現データは、有
限体演算を行う装置に供給され、その表現データを用い
た有限体演算が行われる。
【００１０】ユーザは、入力手段１を介して、希望する
有限体の条件を入力することができる。このとき、例え
ば、素数ｐのビット長や拡大次数ｍのような、直観的に
思いつくことのできる最小限の条件さえ指定すれば、生
成手段２が、素数ｐやｍ次の既約多項式Ｆ（ｘ）のよう
な、直観的に思いつくことの困難な表現データを自動的
に生成する。
有限体の条件を入力することができる。このとき、例え
ば、素数ｐのビット長や拡大次数ｍのような、直観的に
思いつくことのできる最小限の条件さえ指定すれば、生
成手段２が、素数ｐやｍ次の既約多項式Ｆ（ｘ）のよう
な、直観的に思いつくことの困難な表現データを自動的
に生成する。
【００１１】したがって、有限体の表現データの選択に
おけるユーザの負荷が軽減され、生成手段２が生成可能
な範囲内で、表現データを柔軟に設定することが可能に
なる。さらに、適切な条件が指定されれば、効率の良い
有限体演算を実現する表現データが生成される。このよ
うに、本発明のポイントは、指定された条件に基づい
て、有限体の表現データを自動的に生成することであ
る。
おけるユーザの負荷が軽減され、生成手段２が生成可能
な範囲内で、表現データを柔軟に設定することが可能に
なる。さらに、適切な条件が指定されれば、効率の良い
有限体演算を実現する表現データが生成される。このよ
うに、本発明のポイントは、指定された条件に基づい
て、有限体の表現データを自動的に生成することであ
る。
【００１２】例えば、図１の入力手段１は、後述する図
４の入出力装置１１および自動条件指定インタフェース
１２に対応し、図１の生成手段２は、図４の表現データ
生成器１５に対応し、図１の表現データ格納手段３は、
図４の表現データ格納域１７に対応する。
４の入出力装置１１および自動条件指定インタフェース
１２に対応し、図１の生成手段２は、図４の表現データ
生成器１５に対応し、図１の表現データ格納手段３は、
図４の表現データ格納域１７に対応する。
【００１３】
【発明の実施の形態】以下、図面を参照しながら、本発
明の実施の形態を詳細に説明する。まず、図２および図
３を参照しながら、暗号技術に用いられる有限体演算の
例を説明する。
明の実施の形態を詳細に説明する。まず、図２および図
３を参照しながら、暗号技術に用いられる有限体演算の
例を説明する。
【００１４】図２は、よく知られたDiffie-Hellmanの鍵
交換の例を示している。例えば、ユーザＡとユーザＢの
間で秘密鍵暗号を用いてデータ通信を行う場合、まず、
両者が秘密鍵を共有する必要がある。このとき、第３者
に知られることなく、ネットワーク上で秘密情報を交換
するために、Diffie-Hellmanの鍵交換が用いられる。
交換の例を示している。例えば、ユーザＡとユーザＢの
間で秘密鍵暗号を用いてデータ通信を行う場合、まず、
両者が秘密鍵を共有する必要がある。このとき、第３者
に知られることなく、ネットワーク上で秘密情報を交換
するために、Diffie-Hellmanの鍵交換が用いられる。
【００１５】素数ｐ、拡大次数ｍにより表される要素数
ｐm の有限体をＧＦ（ｐm ）と記すことにすると、図２
で用いられている有限体は、ＧＦ（１１）と記される
（ｍ＝１）。ｍ＝１の有限体は、素体（prime field ）
とも呼ばれる。
ｐm の有限体をＧＦ（ｐm ）と記すことにすると、図２
で用いられている有限体は、ＧＦ（１１）と記される
（ｍ＝１）。ｍ＝１の有限体は、素体（prime field ）
とも呼ばれる。
【００１６】ここでは、ｐ＝１１、ｇ＝２が公開されて
おり、ユーザＡの秘密情報がｘ＝４であり、ユーザＢの
秘密情報がｙ＝６であり、共有すべき秘密情報がｓ＝ｇ
xyｍｏｄ ｐ＝２24 ｍｏｄ １１＝５である場合を考
える。ｍｏｄ ｐは、ｐを法とする剰余演算を表し、ｇ
xy ｍｏｄ ｐは、ＧＦ（１１）における有限体演算の
一例を表している。
おり、ユーザＡの秘密情報がｘ＝４であり、ユーザＢの
秘密情報がｙ＝６であり、共有すべき秘密情報がｓ＝ｇ
xyｍｏｄ ｐ＝２24 ｍｏｄ １１＝５である場合を考
える。ｍｏｄ ｐは、ｐを法とする剰余演算を表し、ｇ
xy ｍｏｄ ｐは、ＧＦ（１１）における有限体演算の
一例を表している。
【００１７】このとき、ユーザＡは、ｇx ｍｏｄ ｐ＝
２4 ｍｏｄ １１＝５をユーザＢに送信し、ユーザＢ
は、ｇy ｍｏｄ ｐ＝２6 ｍｏｄ １１＝９をユーザＡ
に送信する。次に、ユーザＡは、ユーザＢから受信した
ｇy ｍｏｄ ｐ＝９を用いて、次式により共有秘密情報
ｓを求める。 ｓ＝（ｇy ）x ＝９4 ＝５ （ｍｏｄ ｐ） （１） また、ユーザＢは、ユーザＡから受信したｇx ｍｏｄ
ｐ＝５を用いて、次式により共有秘密情報ｓを求める。 ｓ＝（ｇx ）y ＝５6 ＝５ （ｍｏｄ ｐ） （２） ここでは、簡単のためにｐ＝１１としたが、実際には、
ｐとして非常に大きな値が用いられる。ｐが十分に大き
ければ、たとえ第３者がｇx ｍｏｄ ｐとｇyｍｏｄ
ｐを取得したとしても、これらの情報からｘとｙを求め
ることは極めて困難となり、秘密情報ｓを知ることは事
実上不可能である。こうして、ユーザＡとユーザＢは、
秘密情報ｓを安全に共有することができ、この情報を秘
密鍵として用いて暗号通信を行うことができる。
２4 ｍｏｄ １１＝５をユーザＢに送信し、ユーザＢ
は、ｇy ｍｏｄ ｐ＝２6 ｍｏｄ １１＝９をユーザＡ
に送信する。次に、ユーザＡは、ユーザＢから受信した
ｇy ｍｏｄ ｐ＝９を用いて、次式により共有秘密情報
ｓを求める。 ｓ＝（ｇy ）x ＝９4 ＝５ （ｍｏｄ ｐ） （１） また、ユーザＢは、ユーザＡから受信したｇx ｍｏｄ
ｐ＝５を用いて、次式により共有秘密情報ｓを求める。 ｓ＝（ｇx ）y ＝５6 ＝５ （ｍｏｄ ｐ） （２） ここでは、簡単のためにｐ＝１１としたが、実際には、
ｐとして非常に大きな値が用いられる。ｐが十分に大き
ければ、たとえ第３者がｇx ｍｏｄ ｐとｇyｍｏｄ
ｐを取得したとしても、これらの情報からｘとｙを求め
ることは極めて困難となり、秘密情報ｓを知ることは事
実上不可能である。こうして、ユーザＡとユーザＢは、
秘密情報ｓを安全に共有することができ、この情報を秘
密鍵として用いて暗号通信を行うことができる。
【００１８】次に、図３は、Diffie-Hellmanの鍵交換に
おいて、有限体ＧＦ（２）＝｛０，１｝の要素（０また
は１）を係数とする３次既約多項式を用いて表される有
限体ＧＦ（２3 ）を用いた例を示している。この場合、
ＧＦ（２3 ）は、ＧＦ（２）の要素を係数とする項から
なる２3 個の２次以下の多項式を要素として持つ。
おいて、有限体ＧＦ（２）＝｛０，１｝の要素（０また
は１）を係数とする３次既約多項式を用いて表される有
限体ＧＦ（２3 ）を用いた例を示している。この場合、
ＧＦ（２3 ）は、ＧＦ（２）の要素を係数とする項から
なる２3 個の２次以下の多項式を要素として持つ。
【００１９】ここでは、ｐ＝２、３次既約多項式ｆ
（ｘ）＝ｘ3 ＋ｘ＋１、ｇ＝ｘ ｍｏｄｆ（ｘ）が公開
されており、ユーザＡの秘密情報がｉ＝４であり、ユー
ザＢの秘密情報がｊ＝６であり、共有すべき秘密情報が
ｓ＝ｇij ｍｏｄ ｆ（ｘ）である場合を考える。ｍｏ
ｄ ｆ（ｘ）は、ｆ（ｘ）を法とする多項式の剰余演算
を表し、ｇij ｍｏｄ ｆ（ｘ）は、ＧＦ（２3 ）にお
ける有限体演算の一例を表している。
（ｘ）＝ｘ3 ＋ｘ＋１、ｇ＝ｘ ｍｏｄｆ（ｘ）が公開
されており、ユーザＡの秘密情報がｉ＝４であり、ユー
ザＢの秘密情報がｊ＝６であり、共有すべき秘密情報が
ｓ＝ｇij ｍｏｄ ｆ（ｘ）である場合を考える。ｍｏ
ｄ ｆ（ｘ）は、ｆ（ｘ）を法とする多項式の剰余演算
を表し、ｇij ｍｏｄ ｆ（ｘ）は、ＧＦ（２3 ）にお
ける有限体演算の一例を表している。
【００２０】このとき、ユーザＡは、ｇi ｍｏｄ ｆ
（ｘ）＝ｘ4 ｍｏｄ （ｘ3 ＋ｘ＋１）＝ｘ2 ＋ｘをユ
ーザＢに送信し、ユーザＢは、ｇj ｍｏｄ ｆ（ｘ）＝
ｘ6 ｍｏｄ （ｘ3 ＋ｘ＋１）＝ｘ2 ＋１をユーザＡに
送信する。次に、ユーザＡは、ユーザＢから受信したｇ
j ｍｏｄ ｆ（ｘ）＝ｘ2 ＋１を用いて、次式により共
有秘密情報ｓを求める。 ｓ＝（ｇj ）i ＝（ｘ2 ＋１）4 ＝ｘ＋１ （ｍｏｄ ｆ（ｘ）） （３） また、ユーザＢは、ユーザＡから受信したｇi ｍｏｄ
ｆ（ｘ）＝ｘ2 ＋ｘを用いて、次式により共有秘密情報
ｓを求める。 ｓ＝（ｇi ）j ＝（ｘ2 ＋ｘ）6 ＝ｘ＋１ （ｍｏｄ ｆ（ｘ）） （４） ここでは、簡単のためにｍ＝３としたが、実際には、ｍ
として非常に大きな値が用いられる。ｍが十分に大きけ
れば、たとえ第３者がｇi ｍｏｄ ｆ（ｘ）とｇj ｍｏ
ｄ ｆ（ｘ）を取得したとしても、これらの情報からｉ
とｊを求めることは極めて困難となり、第３者が秘密情
報ｓを知ることは事実上不可能である。こうして、ユー
ザＡとユーザＢは、秘密情報ｓを安全に共有することが
でき、この情報を秘密鍵として用いて暗号通信を行うこ
とができる。
（ｘ）＝ｘ4 ｍｏｄ （ｘ3 ＋ｘ＋１）＝ｘ2 ＋ｘをユ
ーザＢに送信し、ユーザＢは、ｇj ｍｏｄ ｆ（ｘ）＝
ｘ6 ｍｏｄ （ｘ3 ＋ｘ＋１）＝ｘ2 ＋１をユーザＡに
送信する。次に、ユーザＡは、ユーザＢから受信したｇ
j ｍｏｄ ｆ（ｘ）＝ｘ2 ＋１を用いて、次式により共
有秘密情報ｓを求める。 ｓ＝（ｇj ）i ＝（ｘ2 ＋１）4 ＝ｘ＋１ （ｍｏｄ ｆ（ｘ）） （３） また、ユーザＢは、ユーザＡから受信したｇi ｍｏｄ
ｆ（ｘ）＝ｘ2 ＋ｘを用いて、次式により共有秘密情報
ｓを求める。 ｓ＝（ｇi ）j ＝（ｘ2 ＋ｘ）6 ＝ｘ＋１ （ｍｏｄ ｆ（ｘ）） （４） ここでは、簡単のためにｍ＝３としたが、実際には、ｍ
として非常に大きな値が用いられる。ｍが十分に大きけ
れば、たとえ第３者がｇi ｍｏｄ ｆ（ｘ）とｇj ｍｏ
ｄ ｆ（ｘ）を取得したとしても、これらの情報からｉ
とｊを求めることは極めて困難となり、第３者が秘密情
報ｓを知ることは事実上不可能である。こうして、ユー
ザＡとユーザＢは、秘密情報ｓを安全に共有することが
でき、この情報を秘密鍵として用いて暗号通信を行うこ
とができる。
【００２１】上述したように、素体ＧＦ（ｐ）を表現す
るためには、素数ｐを指定しなければならず、有限体Ｇ
Ｆ（２m ）を表現するためには、拡大次数ｍとｍ次の既
約多項式を指定しなければならない。しかしながら、ｐ
やｍとして非常に大きな数を用いる場合、ユーザが素数
ｐやｍ次の既約多項式を陽に指定することは難しい。
るためには、素数ｐを指定しなければならず、有限体Ｇ
Ｆ（２m ）を表現するためには、拡大次数ｍとｍ次の既
約多項式を指定しなければならない。しかしながら、ｐ
やｍとして非常に大きな数を用いる場合、ユーザが素数
ｐやｍ次の既約多項式を陽に指定することは難しい。
【００２２】本実施形態のデータ生成装置は、ユーザが
直観的に思いつくことのできる最小限の条件さえ指定す
れば、自動的に素数ｐやｍ次の既約多項式等の表現デー
タを生成する。このため、ユーザが表現データを指定す
る際の負荷が大きく軽減される。
直観的に思いつくことのできる最小限の条件さえ指定す
れば、自動的に素数ｐやｍ次の既約多項式等の表現デー
タを生成する。このため、ユーザが表現データを指定す
る際の負荷が大きく軽減される。
【００２３】このとき、可能であれば、高速演算に適し
た表現データを選択することで、より高速な有限体演算
が実現される。さらに、ユーザがすべての表現データを
指定することのできるインタフェースを設けることによ
り、様々な局面に対応できる柔軟性が実現される。
た表現データを選択することで、より高速な有限体演算
が実現される。さらに、ユーザがすべての表現データを
指定することのできるインタフェースを設けることによ
り、様々な局面に対応できる柔軟性が実現される。
【００２４】図４は、このようなデータ生成装置の基本
構成図である。図４のデータ生成装置は、入出力装置１
１、自動条件指定インタフェース１２、手動データ指定
インタフェース１３、固定データテーブル１４、表現デ
ータ生成器１５、表現データ検証器１６、および表現デ
ータ格納域１７を備え、有限体演算装置１８が用いる有
限体の表現データを生成する。
構成図である。図４のデータ生成装置は、入出力装置１
１、自動条件指定インタフェース１２、手動データ指定
インタフェース１３、固定データテーブル１４、表現デ
ータ生成器１５、表現データ検証器１６、および表現デ
ータ格納域１７を備え、有限体演算装置１８が用いる有
限体の表現データを生成する。
【００２５】ユーザは、入出力装置１１を介して、自動
条件指定インタフェース１２または手動データ指定イン
タフェース１３に対して必要な指示を入力する。自動条
件指定インタフェース１２は、ユーザが表現データ生成
のための最小限の条件を指定する場合に用いられ、手動
データ指定インタフェース１３は、ユーザが表現データ
の任意のパラメータを自ら指定する場合に用いられる。
条件指定インタフェース１２または手動データ指定イン
タフェース１３に対して必要な指示を入力する。自動条
件指定インタフェース１２は、ユーザが表現データ生成
のための最小限の条件を指定する場合に用いられ、手動
データ指定インタフェース１３は、ユーザが表現データ
の任意のパラメータを自ら指定する場合に用いられる。
【００２６】固定データテーブル１４は、あらかじめ決
められた適切な表現データを格納し、表現データ生成器
１５は、自動条件指定インタフェース１２による指定に
従って、最終的に使用される表現データを決定する。表
現データ検証器１６は、手動データ指定インタフェース
１３により指定された表現データが有限体演算に適切な
ものかどうかを検証する。
められた適切な表現データを格納し、表現データ生成器
１５は、自動条件指定インタフェース１２による指定に
従って、最終的に使用される表現データを決定する。表
現データ検証器１６は、手動データ指定インタフェース
１３により指定された表現データが有限体演算に適切な
ものかどうかを検証する。
【００２７】表現データ格納域１７は、実際の演算時に
使用される表現データを格納し、有限体演算装置１８
は、表現データ格納域１７の表現データを参照して、有
限体演算を行う。
使用される表現データを格納し、有限体演算装置１８
は、表現データ格納域１７の表現データを参照して、有
限体演算を行う。
【００２８】図５は、図４のデータ生成装置による処理
のフローチャートである。ユーザは表現データ選択のた
めの条件指定において、自動モードまたは手動モードの
いずれかを選択することができ、データ生成装置は、自
動条件指定インタフェース１２および手動データ指定イ
ンタフェース１３により、どちらのモードが選択された
かをチェックする（ステップＳ１）。自動モードにおい
ては、ユーザは最低限の条件を指定するだけで済み、手
動モードにおいては、ユーザは表現データのすべてのパ
ラメータを指定しなければならない。
のフローチャートである。ユーザは表現データ選択のた
めの条件指定において、自動モードまたは手動モードの
いずれかを選択することができ、データ生成装置は、自
動条件指定インタフェース１２および手動データ指定イ
ンタフェース１３により、どちらのモードが選択された
かをチェックする（ステップＳ１）。自動モードにおい
ては、ユーザは最低限の条件を指定するだけで済み、手
動モードにおいては、ユーザは表現データのすべてのパ
ラメータを指定しなければならない。
【００２９】自動モードが選択された場合、表現データ
生成器１５は、まず、指定された条件が適切か否か（正
当か否か）をチェックする（ステップＳ２）。そして、
それが適切でなければ、自動条件指定インタフェース１
２を介して警告を発し、条件の再入力を要求して（ステ
ップＳ３）、ステップＳ２以降の処理を繰り返す。
生成器１５は、まず、指定された条件が適切か否か（正
当か否か）をチェックする（ステップＳ２）。そして、
それが適切でなければ、自動条件指定インタフェース１
２を介して警告を発し、条件の再入力を要求して（ステ
ップＳ３）、ステップＳ２以降の処理を繰り返す。
【００３０】適切な条件が入力されると、次に、固定デ
ータテーブル１４を検索して、指定された条件を満たす
表現データが存在するか否かをチェックする（ステップ
Ｓ４）。そのような表現データが固定データテーブル１
４に存在すれば、そのパラメータを表現データ格納域１
７に設定し（ステップＳ６）、処理を終了する。また、
そのような表現データが存在しなければ、指定された条
件に基づいて表現データを生成して（ステップＳ５）、
表現データ格納域１７に設定し（ステップＳ６）、処理
を終了する。
ータテーブル１４を検索して、指定された条件を満たす
表現データが存在するか否かをチェックする（ステップ
Ｓ４）。そのような表現データが固定データテーブル１
４に存在すれば、そのパラメータを表現データ格納域１
７に設定し（ステップＳ６）、処理を終了する。また、
そのような表現データが存在しなければ、指定された条
件に基づいて表現データを生成して（ステップＳ５）、
表現データ格納域１７に設定し（ステップＳ６）、処理
を終了する。
【００３１】固定データテーブル１４にあらかじめ保持
された表現データは、例えば、高速な有限体演算を実現
できるように選ばれたものであり、表現データ生成器１
５による表現データ生成のロジックは、例えば、高速な
有限体演算を実現する表現データを生成するものであ
る。
された表現データは、例えば、高速な有限体演算を実現
できるように選ばれたものであり、表現データ生成器１
５による表現データ生成のロジックは、例えば、高速な
有限体演算を実現する表現データを生成するものであ
る。
【００３２】ステップＳ１において手動モードが選択さ
れた場合、表現データ検証器１６は、指定された表現デ
ータの正当性を検証し（ステップＳ７）、それが有限体
演算を行うにあたって適切なものかどうかをチェックす
る（ステップＳ８）。
れた場合、表現データ検証器１６は、指定された表現デ
ータの正当性を検証し（ステップＳ７）、それが有限体
演算を行うにあたって適切なものかどうかをチェックす
る（ステップＳ８）。
【００３３】そして、その表現データが適切であれば、
それを表現データ格納域１７に設定し（ステップＳ
６）、処理を終了する。また、指定された表現データが
適切でなければ、手動データ指定インタフェース１３を
介して警告を発し、再度、適切な表現データを指定する
ようにユーザに促し（ステップＳ９）、ステップＳ７以
降の処理を繰り返す。
それを表現データ格納域１７に設定し（ステップＳ
６）、処理を終了する。また、指定された表現データが
適切でなければ、手動データ指定インタフェース１３を
介して警告を発し、再度、適切な表現データを指定する
ようにユーザに促し（ステップＳ９）、ステップＳ７以
降の処理を繰り返す。
【００３４】表現データが表現データ格納域１７に設定
されると、有限体演算部１８は、その値に基づいて有限
体演算を行う。自動モードが選択された場合、自動的に
高速な有限体演算を実現する表現データが設定されるた
め、演算の効率が向上する。
されると、有限体演算部１８は、その値に基づいて有限
体演算を行う。自動モードが選択された場合、自動的に
高速な有限体演算を実現する表現データが設定されるた
め、演算の効率が向上する。
【００３５】次に、図６から図１２までを参照しなが
ら、図４の構成に基づく様々なデータ生成装置の実施形
態について説明する。図６は、素数ｐに関する条件に基
づいて素体ＧＦ（ｐ）の表現データを生成するデータ生
成装置の構成図である。素体ＧＦ（ｐ）の表現データと
しては、素数ｐを設定すればよい。この数ｐは、標数
（characteristic）とも呼ばれる。
ら、図４の構成に基づく様々なデータ生成装置の実施形
態について説明する。図６は、素数ｐに関する条件に基
づいて素体ＧＦ（ｐ）の表現データを生成するデータ生
成装置の構成図である。素体ＧＦ（ｐ）の表現データと
しては、素数ｐを設定すればよい。この数ｐは、標数
（characteristic）とも呼ばれる。
【００３６】図６のデータ生成装置は、入出力装置１
１、自動条件指定インタフェース１２、手動データ指定
インタフェース１３、素数表２１、テーブル参照部２
２、乱数発生部２３、素数判定部２４、２５、および素
数格納域２６を備え、有限体演算装置１８が用いる素体
の表現データを生成する。
１、自動条件指定インタフェース１２、手動データ指定
インタフェース１３、素数表２１、テーブル参照部２
２、乱数発生部２３、素数判定部２４、２５、および素
数格納域２６を備え、有限体演算装置１８が用いる素体
の表現データを生成する。
【００３７】素数表２１は、図４の固定データテーブル
１４に対応し、あらかじめ決められた素数とそのバイナ
リコードのビット長ｎの対応関係を格納する。例えば、
図７に示す素数表においては、ｎ＝２，３，４，．．．
に対応する素数３，７，１１，．．．が順に格納されて
いる。
１４に対応し、あらかじめ決められた素数とそのバイナ
リコードのビット長ｎの対応関係を格納する。例えば、
図７に示す素数表においては、ｎ＝２，３，４，．．．
に対応する素数３，７，１１，．．．が順に格納されて
いる。
【００３８】テーブル参照部２２、乱数発生部２３、お
よび素数判定部２４は、図４の表現データ生成器１５に
対応する。テーブル参照部２２は、与えられたビット長
ｎをキーとして素数表２１を参照し、対応する素数を取
得する。与えられたビット長ｎに対応する素数が素数表
２１に存在しないとき、乱数発生部２３は、ビット長ｎ
の乱数を発生し、素数判定部２４は、その乱数が素数か
否かを判定する。
よび素数判定部２４は、図４の表現データ生成器１５に
対応する。テーブル参照部２２は、与えられたビット長
ｎをキーとして素数表２１を参照し、対応する素数を取
得する。与えられたビット長ｎに対応する素数が素数表
２１に存在しないとき、乱数発生部２３は、ビット長ｎ
の乱数を発生し、素数判定部２４は、その乱数が素数か
否かを判定する。
【００３９】素数判定部２５は、図４の表現データ検証
器１６に対応し、ユーザが指定した素数ｐが本当に素数
であるか否かを判定する。素数格納域２６は、図４の表
現データ格納域１７に対応し、与えられた素数ｐを表現
データとして格納する。
器１６に対応し、ユーザが指定した素数ｐが本当に素数
であるか否かを判定する。素数格納域２６は、図４の表
現データ格納域１７に対応し、与えられた素数ｐを表現
データとして格納する。
【００４０】図８は、図６のデータ生成装置による処理
のフローチャートである。まず、データ生成装置は、自
動モードと手動モードのいずれが選択されたかをチェッ
クする（ステップＳ１１）。自動モードにおいては、ユ
ーザは自動条件指定インタフェース１２を介して素数の
ビット長ｎ（素体のビットサイズ）のみを入力し、手動
モードにおいては、ユーザは自ら具体的な素数ｐを選択
し、手動データ指定インタフェース１３を介してそれを
入力する。
のフローチャートである。まず、データ生成装置は、自
動モードと手動モードのいずれが選択されたかをチェッ
クする（ステップＳ１１）。自動モードにおいては、ユ
ーザは自動条件指定インタフェース１２を介して素数の
ビット長ｎ（素体のビットサイズ）のみを入力し、手動
モードにおいては、ユーザは自ら具体的な素数ｐを選択
し、手動データ指定インタフェース１３を介してそれを
入力する。
【００４１】自動モードが選択された場合、テーブル参
照部２２は、指定されたビット長ｎがサポート範囲内の
ビット長か否かをチェックする（ステップＳ１２）。そ
して、それがサポート範囲外であれば、自動条件指定イ
ンタフェース１２を介して警告を発し、ビット長の再入
力を要求して（ステップＳ１３）、ステップＳ１２以降
の処理を繰り返す。
照部２２は、指定されたビット長ｎがサポート範囲内の
ビット長か否かをチェックする（ステップＳ１２）。そ
して、それがサポート範囲外であれば、自動条件指定イ
ンタフェース１２を介して警告を発し、ビット長の再入
力を要求して（ステップＳ１３）、ステップＳ１２以降
の処理を繰り返す。
【００４２】サポート範囲内のビット長ｎが入力される
と、次に、素数表２１を検索して、ビット長ｎに対応す
る素数が存在するか否かをチェックする（ステップＳ１
４）。そのような素数が素数表２１に存在すれば、それ
を素数ｐとして素数格納域２６に設定し（ステップＳ１
６）、処理を終了する。
と、次に、素数表２１を検索して、ビット長ｎに対応す
る素数が存在するか否かをチェックする（ステップＳ１
４）。そのような素数が素数表２１に存在すれば、それ
を素数ｐとして素数格納域２６に設定し（ステップＳ１
６）、処理を終了する。
【００４３】また、そのような素数が存在しなければ、
乱数発生部２３は、指定されたビット長ｎの乱数を発生
させ、素数判定部２４は、発生した乱数が素数か否かを
判定する（ステップＳ１５）。そして、素数判定部２４
は、素数と判定された乱数を表現データとして採用し、
それを素数ｐとして素数格納域２６に設定して（ステッ
プＳ１６）、処理を終了する。
乱数発生部２３は、指定されたビット長ｎの乱数を発生
させ、素数判定部２４は、発生した乱数が素数か否かを
判定する（ステップＳ１５）。そして、素数判定部２４
は、素数と判定された乱数を表現データとして採用し、
それを素数ｐとして素数格納域２６に設定して（ステッ
プＳ１６）、処理を終了する。
【００４４】素数判定部２４による素数判定（primalit
y test）のアルゴリズムとしては、例えば、以下の文献
に記載されているようなものが用いられる。 文献［１］：情報処理学会 監修，岡本龍明（おかもと
たつあき）・太田和夫（おおた かずお） 共編，
“暗号・ゼロ知識証明・数論”，共立出版，ｐｐ．１３
０−１４３，１９９５． 文献［２］：IEEE P1363 Annex A/Editorial Contribut
ion,“Standard Specifications For Public Key Crypt
ography ”, pp.78-81, 1998. ステップＳ１１において手動モードが選択された場合、
素数判定部２５は、素数判定部２４と同様にして、指定
された数ｐの素数判定を行い（ステップＳ１７）、それ
が本当に素数であるか否かをチェックする（ステップＳ
１８）。
y test）のアルゴリズムとしては、例えば、以下の文献
に記載されているようなものが用いられる。 文献［１］：情報処理学会 監修，岡本龍明（おかもと
たつあき）・太田和夫（おおた かずお） 共編，
“暗号・ゼロ知識証明・数論”，共立出版，ｐｐ．１３
０−１４３，１９９５． 文献［２］：IEEE P1363 Annex A/Editorial Contribut
ion,“Standard Specifications For Public Key Crypt
ography ”, pp.78-81, 1998. ステップＳ１１において手動モードが選択された場合、
素数判定部２５は、素数判定部２４と同様にして、指定
された数ｐの素数判定を行い（ステップＳ１７）、それ
が本当に素数であるか否かをチェックする（ステップＳ
１８）。
【００４５】そして、指定された数ｐが素数であれば、
それを表現データとして採用して、素数格納域２６に設
定し（ステップＳ１６）、処理を終了する。また、それ
が素数でなければ、手動データ指定インタフェース１３
を介して警告を発し、再度、正しい素数を入力するよう
にユーザに促し（ステップＳ１９）、ステップＳ１７以
降の処理を繰り返す。
それを表現データとして採用して、素数格納域２６に設
定し（ステップＳ１６）、処理を終了する。また、それ
が素数でなければ、手動データ指定インタフェース１３
を介して警告を発し、再度、正しい素数を入力するよう
にユーザに促し（ステップＳ１９）、ステップＳ１７以
降の処理を繰り返す。
【００４６】素数ｐが素数格納域２６に設定されると、
有限体演算部１８は、その値に基づいて素体ＧＦ（ｐ）
上の有限体演算を行う。このような構成によれば、ユー
ザがビット長さえ指定すれば自動的に素数ｐが生成され
るため、ユーザが素数ｐを指定する際の負荷が軽減され
る。また、必要であれば、ユーザが素数ｐを直接指定す
ることもでき、柔軟な操作性が実現される。
有限体演算部１８は、その値に基づいて素体ＧＦ（ｐ）
上の有限体演算を行う。このような構成によれば、ユー
ザがビット長さえ指定すれば自動的に素数ｐが生成され
るため、ユーザが素数ｐを指定する際の負荷が軽減され
る。また、必要であれば、ユーザが素数ｐを直接指定す
ることもでき、柔軟な操作性が実現される。
【００４７】図９は、拡大次数ｍに基づいて有限体ＧＦ
（２m ）の表現データを生成するデータ生成装置の構成
図である。有限体ＧＦ（２m ）の場合、素数ｐは２に決
められているため、それ以外の表現データとしては、拡
大次数ｍとｍ次の既約多項式Ｆ（ｘ）を設定すればよ
い。ｍ次の多項式は、例えば、各項ｘk（ｋ＝０，
１，．．．，ｍ）の係数（０または１）の集合により表
すことができる。
（２m ）の表現データを生成するデータ生成装置の構成
図である。有限体ＧＦ（２m ）の場合、素数ｐは２に決
められているため、それ以外の表現データとしては、拡
大次数ｍとｍ次の既約多項式Ｆ（ｘ）を設定すればよ
い。ｍ次の多項式は、例えば、各項ｘk（ｋ＝０，
１，．．．，ｍ）の係数（０または１）の集合により表
すことができる。
【００４８】図９のデータ生成装置は、入出力装置１
１、自動条件指定インタフェース１２、手動データ指定
インタフェース１３、既約多項式表３１、テーブル参照
部３２、多項式発生部３３、既約性判定部３４、３５、
および既約多項式格納域３６を備え、有限体演算装置１
８が用いる有限体の表現データを生成する。
１、自動条件指定インタフェース１２、手動データ指定
インタフェース１３、既約多項式表３１、テーブル参照
部３２、多項式発生部３３、既約性判定部３４、３５、
および既約多項式格納域３６を備え、有限体演算装置１
８が用いる有限体の表現データを生成する。
【００４９】既約多項式表３１は、図４の固定データテ
ーブル１４に対応し、あらかじめ決められた拡大次数ｍ
とｍ次の既約多項式Ｆ（ｘ）の対応関係を格納する。例
えば、図１０に示す既約多項式表においては、ｍ＝２，
３，４，．．．に対応する既約多項式として、ｘ2 ＋ｘ
＋１，ｘ3 ＋ｘ＋１，ｘ4 ＋ｘ＋１，．．．が格納され
ている。
ーブル１４に対応し、あらかじめ決められた拡大次数ｍ
とｍ次の既約多項式Ｆ（ｘ）の対応関係を格納する。例
えば、図１０に示す既約多項式表においては、ｍ＝２，
３，４，．．．に対応する既約多項式として、ｘ2 ＋ｘ
＋１，ｘ3 ＋ｘ＋１，ｘ4 ＋ｘ＋１，．．．が格納され
ている。
【００５０】テーブル参照部３２、多項式発生部３３、
および既約性判定部３４は、図４の表現データ生成器１
５に対応する。テーブル参照部３２は、与えられた拡大
次数ｍをキーとして既約多項式表３１を参照し、対応す
る既約多項式を取得する。与えられた拡大次数ｍに対応
する既約多項式が既約多項式表３１に存在しないとき、
多項式発生部３３は、ｍ次の多項式を発生し、既約性判
定部３４は、その多項式が既約か否かを判定する。
および既約性判定部３４は、図４の表現データ生成器１
５に対応する。テーブル参照部３２は、与えられた拡大
次数ｍをキーとして既約多項式表３１を参照し、対応す
る既約多項式を取得する。与えられた拡大次数ｍに対応
する既約多項式が既約多項式表３１に存在しないとき、
多項式発生部３３は、ｍ次の多項式を発生し、既約性判
定部３４は、その多項式が既約か否かを判定する。
【００５１】既約性判定部３５は、図４の表現データ検
証器１６に対応し、ユーザが指定したｍ次の既約多項式
が本当に既約であるか否かを判定する。既約多項式格納
域３６は、図４の表現データ格納域１７に対応し、拡大
次数ｍとｍ次の既約多項式Ｆ（ｘ）を表現データとして
格納する。
証器１６に対応し、ユーザが指定したｍ次の既約多項式
が本当に既約であるか否かを判定する。既約多項式格納
域３６は、図４の表現データ格納域１７に対応し、拡大
次数ｍとｍ次の既約多項式Ｆ（ｘ）を表現データとして
格納する。
【００５２】図１１は、図９のデータ生成装置による処
理のフローチャートである。まず、データ生成装置は、
自動モードと手動モードのいずれが選択されたかをチェ
ックする（ステップＳ２１）。自動モードにおいては、
ユーザは自動条件指定インタフェース１２を介して拡大
次数ｍのみを入力し、手動モードにおいては、ユーザは
自ら具体的なｍ次の既約多項式Ｆ（ｘ）を選択し、それ
を拡大次数ｍとともに手動データ指定インタフェース１
３を介して入力する。
理のフローチャートである。まず、データ生成装置は、
自動モードと手動モードのいずれが選択されたかをチェ
ックする（ステップＳ２１）。自動モードにおいては、
ユーザは自動条件指定インタフェース１２を介して拡大
次数ｍのみを入力し、手動モードにおいては、ユーザは
自ら具体的なｍ次の既約多項式Ｆ（ｘ）を選択し、それ
を拡大次数ｍとともに手動データ指定インタフェース１
３を介して入力する。
【００５３】自動モードが選択された場合、テーブル参
照部３２は、指定された拡大次数ｍがサポート範囲内の
拡大次数か否かをチェックする（ステップＳ２２）。そ
して、それがサポート範囲外であれば、自動条件指定イ
ンタフェース１２を介して警告を発し、拡大次数の再入
力を要求して（ステップＳ２３）、ステップＳ２２以降
の処理を繰り返す。
照部３２は、指定された拡大次数ｍがサポート範囲内の
拡大次数か否かをチェックする（ステップＳ２２）。そ
して、それがサポート範囲外であれば、自動条件指定イ
ンタフェース１２を介して警告を発し、拡大次数の再入
力を要求して（ステップＳ２３）、ステップＳ２２以降
の処理を繰り返す。
【００５４】サポート範囲内の拡大次数ｍが入力される
と、次に、既約多項式表３１を検索して、拡大次数ｍに
対応する既約多項式が存在するか否かをチェックする
（ステップＳ２４）。そのような既約多項式が既約多項
式表３１に存在すれば、それを既約多項式Ｆ（ｘ）とし
て、拡大次数ｍとともに既約多項式格納域３６に設定し
（ステップＳ２６）、処理を終了する。
と、次に、既約多項式表３１を検索して、拡大次数ｍに
対応する既約多項式が存在するか否かをチェックする
（ステップＳ２４）。そのような既約多項式が既約多項
式表３１に存在すれば、それを既約多項式Ｆ（ｘ）とし
て、拡大次数ｍとともに既約多項式格納域３６に設定し
（ステップＳ２６）、処理を終了する。
【００５５】また、そのような既約多項式が存在しなけ
れば、多項式発生部３３は、ｍ次のの多項式を発生さ
せ、既約性判定部３４は、発生した多項式が既約か否か
を判定する（ステップＳ２５）。そして、既約性判定部
３４は、既約と判定された多項式を既約多項式Ｆ（ｘ）
として採用し、それを拡大次数ｍとともに既約多項式格
納域３６に設定して（ステップＳ２６）、処理を終了す
る。
れば、多項式発生部３３は、ｍ次のの多項式を発生さ
せ、既約性判定部３４は、発生した多項式が既約か否か
を判定する（ステップＳ２５）。そして、既約性判定部
３４は、既約と判定された多項式を既約多項式Ｆ（ｘ）
として採用し、それを拡大次数ｍとともに既約多項式格
納域３６に設定して（ステップＳ２６）、処理を終了す
る。
【００５６】ステップＳ２１において手動モードが選択
された場合、既約性判定部３５は、既約性判定部３４と
同様にして、指定された多項式Ｆ（ｘ）の既約性判定
（irreducibility test ）を行い（ステップＳ２７）、
それが本当に既約であるか否かをチェックする（ステッ
プＳ２８）。
された場合、既約性判定部３５は、既約性判定部３４と
同様にして、指定された多項式Ｆ（ｘ）の既約性判定
（irreducibility test ）を行い（ステップＳ２７）、
それが本当に既約であるか否かをチェックする（ステッ
プＳ２８）。
【００５７】そして、指定された多項式Ｆ（ｘ）が既約
であれば、それを表現データとして採用して、拡大次数
ｍとともに既約多項式格納域３６に設定し（ステップＳ
２６）、処理を終了する。また、それが既約でなけれ
ば、手動データ指定インタフェース１３を介して警告を
発し、再度、正しい既約多項式を入力するようにユーザ
に促し（ステップＳ２９）、ステップＳ２７以降の処理
を繰り返す。
であれば、それを表現データとして採用して、拡大次数
ｍとともに既約多項式格納域３６に設定し（ステップＳ
２６）、処理を終了する。また、それが既約でなけれ
ば、手動データ指定インタフェース１３を介して警告を
発し、再度、正しい既約多項式を入力するようにユーザ
に促し（ステップＳ２９）、ステップＳ２７以降の処理
を繰り返す。
【００５８】図１２は、図１１のステップＳ２５におけ
る既約多項式生成処理のフローチャートである。まず、
テーブル参照部３２は、多項式発生部３３に拡大次数ｍ
を入力し（ステップＳ３１）、多項式発生部３３は、
（ｍ＋１）ビットの乱数（バイナリコード）を発生させ
る（ステップＳ３２）。
る既約多項式生成処理のフローチャートである。まず、
テーブル参照部３２は、多項式発生部３３に拡大次数ｍ
を入力し（ステップＳ３１）、多項式発生部３３は、
（ｍ＋１）ビットの乱数（バイナリコード）を発生させ
る（ステップＳ３２）。
【００５９】次に、多項式発生部３３は、有限体ＧＦ
（２）＝｛０，１｝の要素を係数とするｍ次の多項式を
生成する（ステップＳ３３）。ここでは、ｋ＝１，
２，．．．，ｍ＋１のそれぞれの値について、発生した
乱数のｋビット目の値（０または１）をｘk-1 の項の係
数とし、それらの項からなるｍ次の多項式を生成する。
（２）＝｛０，１｝の要素を係数とするｍ次の多項式を
生成する（ステップＳ３３）。ここでは、ｋ＝１，
２，．．．，ｍ＋１のそれぞれの値について、発生した
乱数のｋビット目の値（０または１）をｘk-1 の項の係
数とし、それらの項からなるｍ次の多項式を生成する。
【００６０】次に、既約性判定部３４は、生成された多
項式の既約性判定を行い（ステップＳ３４）、それが既
約か否かをチェックする（ステップＳ３５）。既約性判
定のアルゴリズムとしては、例えば、上述した文献
［２］の３０ページに記載されているようなものが用い
られる。生成された多項式が既約でなければ、ステップ
Ｓ３２以降の処理を繰り返し、既約な多項式が得られれ
ば、それを既約多項式格納域３６に出力して（ステップ
Ｓ３６）、処理を終了する。
項式の既約性判定を行い（ステップＳ３４）、それが既
約か否かをチェックする（ステップＳ３５）。既約性判
定のアルゴリズムとしては、例えば、上述した文献
［２］の３０ページに記載されているようなものが用い
られる。生成された多項式が既約でなければ、ステップ
Ｓ３２以降の処理を繰り返し、既約な多項式が得られれ
ば、それを既約多項式格納域３６に出力して（ステップ
Ｓ３６）、処理を終了する。
【００６１】図１１の処理により、拡大次数ｍと既約多
項式Ｆ（ｘ）が既約多項式格納域３６に設定されると、
有限体演算部１８は、そのデータに基づいて有限体ＧＦ
（２ m ）上の有限体演算を行う。このような構成によれ
ば、ユーザが拡大次数ｍさえ指定すれば自動的にｍ次の
既約多項式Ｆ（ｘ）が生成されるため、ユーザが既約多
項式Ｆ（ｘ）を指定する際の負荷が軽減される。また、
必要であれば、ユーザが既約多項式Ｆ（ｘ）を直接指定
することもでき、柔軟な操作性が実現される。
項式Ｆ（ｘ）が既約多項式格納域３６に設定されると、
有限体演算部１８は、そのデータに基づいて有限体ＧＦ
（２ m ）上の有限体演算を行う。このような構成によれ
ば、ユーザが拡大次数ｍさえ指定すれば自動的にｍ次の
既約多項式Ｆ（ｘ）が生成されるため、ユーザが既約多
項式Ｆ（ｘ）を指定する際の負荷が軽減される。また、
必要であれば、ユーザが既約多項式Ｆ（ｘ）を直接指定
することもでき、柔軟な操作性が実現される。
【００６２】ところで、有限体ＧＦ（２m ）上の演算を
高速化する方法の１つとして、最適化正規基底（optima
l normal basis）を用いる方法が知られている（文献
［１］，ｐｐ．１６７−１７０／文献［２］，ｐｐ．１
９−２４）。一般に、有限体ＧＦ（２m ）は、正規基底
（normal basis）を生成元として表現することができ、
特に、最適化正規基底に基づく表現データを用いれば、
べき乗算および乗算を飛躍的に高速化することができ
る。
高速化する方法の１つとして、最適化正規基底（optima
l normal basis）を用いる方法が知られている（文献
［１］，ｐｐ．１６７−１７０／文献［２］，ｐｐ．１
９−２４）。一般に、有限体ＧＦ（２m ）は、正規基底
（normal basis）を生成元として表現することができ、
特に、最適化正規基底に基づく表現データを用いれば、
べき乗算および乗算を飛躍的に高速化することができ
る。
【００６３】そこで、図９のデータ生成装置において、
最適化正規基底を用いた表現データを生成するオプショ
ンを設けることにする。ただし、最適化正規基底は、必
ずしもすべての拡大次数について存在するわけではな
く、これを利用するためには、拡大次数ｍを適切に指定
する必要がある。例えば、暗号に用いられる１６０≦ｍ
≦２０００の拡大次数のうち最適化正規基底が存在する
ものは、以下の文献にリストアップされている。 文献［３］：American National Standard, x9.62-199
x, Public Key Cryptography For The Financial Servi
ces Industry: The Elliptic Curve Digital Signature
Algorithm, p.41, Working Draft. ユーザは、自動条件指定インタフェース１２および手動
データ指定インタフェース１３を介して、最適化正規基
底を使用するか否かをオプションとして指定することが
できる。この場合、既約多項式表３１には、各拡大次数
について、最適化正規基底が存在するか否かを表す情報
が付加され、存在する場合は、必要に応じてその最適化
正規基底用既約多項式の情報が付加される。最適化正規
基底用既約多項式とは、最適化正規基底を用いて有限体
を表現するために必要な特定の既約多項式を指す。
最適化正規基底を用いた表現データを生成するオプショ
ンを設けることにする。ただし、最適化正規基底は、必
ずしもすべての拡大次数について存在するわけではな
く、これを利用するためには、拡大次数ｍを適切に指定
する必要がある。例えば、暗号に用いられる１６０≦ｍ
≦２０００の拡大次数のうち最適化正規基底が存在する
ものは、以下の文献にリストアップされている。 文献［３］：American National Standard, x9.62-199
x, Public Key Cryptography For The Financial Servi
ces Industry: The Elliptic Curve Digital Signature
Algorithm, p.41, Working Draft. ユーザは、自動条件指定インタフェース１２および手動
データ指定インタフェース１３を介して、最適化正規基
底を使用するか否かをオプションとして指定することが
できる。この場合、既約多項式表３１には、各拡大次数
について、最適化正規基底が存在するか否かを表す情報
が付加され、存在する場合は、必要に応じてその最適化
正規基底用既約多項式の情報が付加される。最適化正規
基底用既約多項式とは、最適化正規基底を用いて有限体
を表現するために必要な特定の既約多項式を指す。
【００６４】図１３は、このようなデータ生成装置によ
る処理のフローチャートである。まず、データ生成装置
は、自動モードと手動モードのいずれが選択されたかを
チェックする（ステップＳ４１）。自動モードにおいて
は、ユーザは、自動条件指定インタフェース１２を介し
て、拡大次数ｍと最適化正規基底を使用する指示とを入
力する。また、手動モードにおいては、ユーザは、自ら
具体的なｍ次の最適化正規基底用既約多項式Ｆ（ｘ）を
選択し、それを拡大次数ｍとともに手動データ指定イン
タフェース１３を介して入力する。
る処理のフローチャートである。まず、データ生成装置
は、自動モードと手動モードのいずれが選択されたかを
チェックする（ステップＳ４１）。自動モードにおいて
は、ユーザは、自動条件指定インタフェース１２を介し
て、拡大次数ｍと最適化正規基底を使用する指示とを入
力する。また、手動モードにおいては、ユーザは、自ら
具体的なｍ次の最適化正規基底用既約多項式Ｆ（ｘ）を
選択し、それを拡大次数ｍとともに手動データ指定イン
タフェース１３を介して入力する。
【００６５】自動モードが選択された場合、テーブル参
照部３２は、既約多項式表３１を参照して、指定された
拡大次数ｍの最適化正規基底が存在するか否かをチェッ
クする（ステップＳ４２）。そして、ｍ次の最適化正規
基底が存在しないか、あるいは拡大次数ｍがサポート範
囲外であれば、自動条件指定インタフェース１２を介し
て警告を発し、拡大次数の再入力を要求して（ステップ
Ｓ４３）、ステップＳ４２以降の処理を繰り返す。
照部３２は、既約多項式表３１を参照して、指定された
拡大次数ｍの最適化正規基底が存在するか否かをチェッ
クする（ステップＳ４２）。そして、ｍ次の最適化正規
基底が存在しないか、あるいは拡大次数ｍがサポート範
囲外であれば、自動条件指定インタフェース１２を介し
て警告を発し、拡大次数の再入力を要求して（ステップ
Ｓ４３）、ステップＳ４２以降の処理を繰り返す。
【００６６】最適化正規基底を有する拡大次数ｍが入力
されると、次に、既約多項式表３１に最適化正規基底用
既約多項式が存在するか否かをチェックする（ステップ
Ｓ４４）。そのような既約多項式が既約多項式表３１に
存在すれば、それを最適化正規基底用既約多項式Ｆ
（ｘ）として、拡大次数ｍとともに既約多項式格納域３
６に設定し（ステップＳ４６）、処理を終了する。
されると、次に、既約多項式表３１に最適化正規基底用
既約多項式が存在するか否かをチェックする（ステップ
Ｓ４４）。そのような既約多項式が既約多項式表３１に
存在すれば、それを最適化正規基底用既約多項式Ｆ
（ｘ）として、拡大次数ｍとともに既約多項式格納域３
６に設定し（ステップＳ４６）、処理を終了する。
【００６７】また、そのような既約多項式が存在しなけ
れば、多項式発生部３３は、ｍ次の最適化正規基底用既
約多項式を生成する（ステップＳ４５）。そして、それ
を最適化正規基底用既約多項式Ｆ（ｘ）として、拡大次
数ｍとともに既約多項式格納域３６に設定し（ステップ
Ｓ４６）、処理を終了する。最適化正規基底用既約多項
式の生成アルゴリズムとしては、例えば、上述した文献
［２］の３７ページに記載されているようなものが用い
られる。
れば、多項式発生部３３は、ｍ次の最適化正規基底用既
約多項式を生成する（ステップＳ４５）。そして、それ
を最適化正規基底用既約多項式Ｆ（ｘ）として、拡大次
数ｍとともに既約多項式格納域３６に設定し（ステップ
Ｓ４６）、処理を終了する。最適化正規基底用既約多項
式の生成アルゴリズムとしては、例えば、上述した文献
［２］の３７ページに記載されているようなものが用い
られる。
【００６８】ステップＳ４１において手動モードが選択
された場合、既約性判定部３５は、指定された多項式Ｆ
（ｘ）の最適化正規基底用既約性判定を行い（ステップ
Ｓ４７）、それが本当に最適化正規基底用既約多項式で
あるか否かをチェックする（ステップＳ４８）。
された場合、既約性判定部３５は、指定された多項式Ｆ
（ｘ）の最適化正規基底用既約性判定を行い（ステップ
Ｓ４７）、それが本当に最適化正規基底用既約多項式で
あるか否かをチェックする（ステップＳ４８）。
【００６９】最適化正規基底用既約性判定は、例えば、
上述した文献［２］の２０ページに記載されている最適
化正規基底が存在するか否かの判定アルゴリズムと、最
適化正規基底用既約多項式の生成アルゴリズムとを組み
合わせて行われる。
上述した文献［２］の２０ページに記載されている最適
化正規基底が存在するか否かの判定アルゴリズムと、最
適化正規基底用既約多項式の生成アルゴリズムとを組み
合わせて行われる。
【００７０】この場合、既約性判定部３５は、まず、指
定された多項式Ｆ（ｘ）の拡大次数ｍにおいて、最適化
正規基底が存在するか否かをチェックする。最適化正規
基底が存在すれば、次に、ｍ次の最適化正規基底用既約
多項式を生成して、Ｆ（ｘ）を生成された多項式と比較
する。そして、両者が一致すれば、Ｆ（ｘ）が最適化正
規基底用既約多項式であると判定する。
定された多項式Ｆ（ｘ）の拡大次数ｍにおいて、最適化
正規基底が存在するか否かをチェックする。最適化正規
基底が存在すれば、次に、ｍ次の最適化正規基底用既約
多項式を生成して、Ｆ（ｘ）を生成された多項式と比較
する。そして、両者が一致すれば、Ｆ（ｘ）が最適化正
規基底用既約多項式であると判定する。
【００７１】また、あらかじめこれらのアルゴリズムに
基づいて、サポート範囲内のすべての最適化正規基底用
既約多項式のテーブルを生成しておき、そのテーブルを
参照しながら、最適化正規基底用既約性判定を行うこと
もできる。
基づいて、サポート範囲内のすべての最適化正規基底用
既約多項式のテーブルを生成しておき、そのテーブルを
参照しながら、最適化正規基底用既約性判定を行うこと
もできる。
【００７２】指定された多項式Ｆ（ｘ）が最適化正規基
底用既約多項式であれば、それを表現データとして採用
して、拡大次数ｍとともに既約多項式格納域３６に設定
し（ステップＳ４６）、処理を終了する。また、それが
最適化正規基底用既約多項式でなければ、手動データ指
定インタフェース１３を介して警告を発し、再度、正し
い最適化正規基底用既約多項式を入力するようにユーザ
に促し（ステップＳ４９）、ステップＳ４７以降の処理
を繰り返す。
底用既約多項式であれば、それを表現データとして採用
して、拡大次数ｍとともに既約多項式格納域３６に設定
し（ステップＳ４６）、処理を終了する。また、それが
最適化正規基底用既約多項式でなければ、手動データ指
定インタフェース１３を介して警告を発し、再度、正し
い最適化正規基底用既約多項式を入力するようにユーザ
に促し（ステップＳ４９）、ステップＳ４７以降の処理
を繰り返す。
【００７３】拡大次数ｍと最適化正規基底用既約多項式
Ｆ（ｘ）が既約多項式格納域３６に設定されると、有限
体演算部１８は、そのデータに基づいて有限体ＧＦ（２
m ）上の有限体演算を行う。
Ｆ（ｘ）が既約多項式格納域３６に設定されると、有限
体演算部１８は、そのデータに基づいて有限体ＧＦ（２
m ）上の有限体演算を行う。
【００７４】このような構成によれば、ユーザが最適化
正規基底を有する拡大次数ｍさえ指定すれば、自動的に
ｍ次の最適化正規基底用既約多項式Ｆ（ｘ）が生成され
る。このため、ユーザが最適化正規基底用既約多項式Ｆ
（ｘ）を指定する際の負荷が軽減されるとともに、最適
化正規基底に基づく高速な有限体演算が可能となる。ま
た、必要であれば、ユーザが最適化正規基底用既約多項
式Ｆ（ｘ）を直接指定することもでき、柔軟な操作性が
実現される。
正規基底を有する拡大次数ｍさえ指定すれば、自動的に
ｍ次の最適化正規基底用既約多項式Ｆ（ｘ）が生成され
る。このため、ユーザが最適化正規基底用既約多項式Ｆ
（ｘ）を指定する際の負荷が軽減されるとともに、最適
化正規基底に基づく高速な有限体演算が可能となる。ま
た、必要であれば、ユーザが最適化正規基底用既約多項
式Ｆ（ｘ）を直接指定することもでき、柔軟な操作性が
実現される。
【００７５】以上の実施形態においては、主として、有
限体ＧＦ（ｐ）およびＧＦ（２m ）の表現データを生成
する場合について説明したが、一般の有限体ＧＦ
（ｐm ）の表現データを生成する場合も同様である。こ
の場合、ユーザは、素数ｐまたはそのビット長ｎと拡大
次数ｍさえ指定すれば、データ生成装置は、自動的にＧ
Ｆ（ｐm ）の表現データを生成する。
限体ＧＦ（ｐ）およびＧＦ（２m ）の表現データを生成
する場合について説明したが、一般の有限体ＧＦ
（ｐm ）の表現データを生成する場合も同様である。こ
の場合、ユーザは、素数ｐまたはそのビット長ｎと拡大
次数ｍさえ指定すれば、データ生成装置は、自動的にＧ
Ｆ（ｐm ）の表現データを生成する。
【００７６】ところで、本実施形態のデータ生成装置お
よび有限体演算装置は、図１４に示すような情報処理装
置（コンピュータ）を用いて構成することができる。図
１４の情報処理装置は、ＣＰＵ（中央処理装置）４１、
メモリ４２、入力装置４３、出力装置４４、外部記憶装
置４５、媒体駆動装置４６、およびネットワーク接続装
置４７を備え、それらはバス４８により互いに接続され
ている。
よび有限体演算装置は、図１４に示すような情報処理装
置（コンピュータ）を用いて構成することができる。図
１４の情報処理装置は、ＣＰＵ（中央処理装置）４１、
メモリ４２、入力装置４３、出力装置４４、外部記憶装
置４５、媒体駆動装置４６、およびネットワーク接続装
置４７を備え、それらはバス４８により互いに接続され
ている。
【００７７】メモリ４２は、例えば、ＲＯＭ（read onl
y memory）、ＲＡＭ（random access memory）等を含
み、処理に用いられるプログラムとデータを格納する。
ＣＰＵ４１は、メモリ４２を利用してプログラムを実行
することにより、必要な処理を行う。
y memory）、ＲＡＭ（random access memory）等を含
み、処理に用いられるプログラムとデータを格納する。
ＣＰＵ４１は、メモリ４２を利用してプログラムを実行
することにより、必要な処理を行う。
【００７８】この場合、図４の自動条件指定インタフェ
ース１２、手動データ指定インタフェース１３、表現デ
ータ生成器１５、および表現データ検証器１６は、メモ
リ４２の特定のプログラムコードセグメントに格納され
たインストラクションの集合により実現されるソフトウ
ェアコンポーネントに対応する。また、図４の固定デー
タテーブル１４と表現データ格納域１７は、メモリ４２
内に設けられる。
ース１２、手動データ指定インタフェース１３、表現デ
ータ生成器１５、および表現データ検証器１６は、メモ
リ４２の特定のプログラムコードセグメントに格納され
たインストラクションの集合により実現されるソフトウ
ェアコンポーネントに対応する。また、図４の固定デー
タテーブル１４と表現データ格納域１７は、メモリ４２
内に設けられる。
【００７９】入力装置４３は、例えば、キーボード、ポ
インティングデバイス、タッチパネル等であり、ユーザ
からの指示や情報の入力に用いられる。出力装置４４
は、例えば、ディスプレイ、プリンタ、スピーカ等であ
り、ユーザへのメッセージや処理結果の出力に用いられ
る。
インティングデバイス、タッチパネル等であり、ユーザ
からの指示や情報の入力に用いられる。出力装置４４
は、例えば、ディスプレイ、プリンタ、スピーカ等であ
り、ユーザへのメッセージや処理結果の出力に用いられ
る。
【００８０】外部記憶装置４５は、例えば、磁気ディス
ク装置、光ディスク装置、光磁気ディスク（magneto-op
tical disk）装置等である。情報処理装置は、この外部
記憶装置４５に、上述のプログラムとデータを保存して
おき、必要に応じて、それらをメモリ４２にロードして
使用することができる。
ク装置、光ディスク装置、光磁気ディスク（magneto-op
tical disk）装置等である。情報処理装置は、この外部
記憶装置４５に、上述のプログラムとデータを保存して
おき、必要に応じて、それらをメモリ４２にロードして
使用することができる。
【００８１】媒体駆動装置４６は、可搬記録媒体４９を
駆動し、その記録内容にアクセスする。可搬記録媒体４
９としては、メモリカード、フロッピーディスク、ＣＤ
−ＲＯＭ（compact disk read only memory ）、光ディ
スク、光磁気ディスク等、任意のコンピュータ読み取り
可能な記録媒体が用いられる。ユーザは、この可搬記録
媒体４９に上述のプログラムとデータを格納しておき、
必要に応じて、それらをメモリ４２にロードして使用す
ることができる。
駆動し、その記録内容にアクセスする。可搬記録媒体４
９としては、メモリカード、フロッピーディスク、ＣＤ
−ＲＯＭ（compact disk read only memory ）、光ディ
スク、光磁気ディスク等、任意のコンピュータ読み取り
可能な記録媒体が用いられる。ユーザは、この可搬記録
媒体４９に上述のプログラムとデータを格納しておき、
必要に応じて、それらをメモリ４２にロードして使用す
ることができる。
【００８２】ネットワーク接続装置４７は、任意のネッ
トワーク（回線）を介して外部の装置と通信し、通信に
伴うデータ変換を行う。情報処理装置は、必要に応じ
て、ネットワーク接続装置４７を介して上述のプログラ
ムとデータを外部の装置から受け取り、それらをメモリ
４２にロードして使用することができる。
トワーク（回線）を介して外部の装置と通信し、通信に
伴うデータ変換を行う。情報処理装置は、必要に応じ
て、ネットワーク接続装置４７を介して上述のプログラ
ムとデータを外部の装置から受け取り、それらをメモリ
４２にロードして使用することができる。
【００８３】図１５は、図１４の情報処理装置にプログ
ラムとデータを供給することのできるコンピュータ読み
取り可能な記録媒体を示している。可搬記録媒体４９や
外部のデータベース５０に保存されたプログラムとデー
タは、メモリ４２にロードされる。そして、ＣＰＵ４１
は、そのデータを用いてそのプログラムを実行し、必要
な処理を行う。
ラムとデータを供給することのできるコンピュータ読み
取り可能な記録媒体を示している。可搬記録媒体４９や
外部のデータベース５０に保存されたプログラムとデー
タは、メモリ４２にロードされる。そして、ＣＰＵ４１
は、そのデータを用いてそのプログラムを実行し、必要
な処理を行う。
【００８４】
【発明の効果】本発明によれば、ユーザが最小限の条件
さえ指定すれば自動的に有限体の表現データが生成され
るため、ユーザの負荷が大きく軽減される。また、特定
の表現データを選択的に生成することにより、高速な有
限体演算を実現することができる。さらに、有限体演算
の様々な局面に応じて、ユーザがすべての表現データを
柔軟に指定することもできる。
さえ指定すれば自動的に有限体の表現データが生成され
るため、ユーザの負荷が大きく軽減される。また、特定
の表現データを選択的に生成することにより、高速な有
限体演算を実現することができる。さらに、有限体演算
の様々な局面に応じて、ユーザがすべての表現データを
柔軟に指定することもできる。
【図１】本発明のデータ生成装置の原理図である。
【図２】第１の秘密情報の交換を示す図である。
【図３】第２の秘密情報の交換を示す図である。
【図４】第１のデータ生成装置の構成図である。
【図５】第１のデータ生成処理のフローチャートであ
る。
る。
【図６】第２のデータ生成装置の構成図である。
【図７】素数表を示す図である。
【図８】第２のデータ生成処理のフローチャートであ
る。
る。
【図９】第３のデータ生成装置の構成図である。
【図１０】既約多項式表を示す図である。
【図１１】第３のデータ生成処理のフローチャートであ
る。
る。
【図１２】既約多項式生成処理のフローチャートであ
る。
る。
【図１３】第４のデータ生成処理のフローチャートであ
る。
る。
【図１４】情報処理装置の構成図である。
【図１５】記録媒体を示す図である。
１ 入力手段 ２ 生成手段 ３ 表現データ格納手段 １１ 入出力装置 １２ 自動条件指定インタフェース １３ 手動データ指定インタフェース １４ 固定データテーブル １５ 表現データ生成器 １６ 表現データ検証器 １７ 表現データ格納域 １８ 有限体演算装置 ２１ 素数表 ２２、３２ テーブル参照部 ２３ 乱数発生部 ２４、２５ 素数判定部 ２６ 素数格納域 ３１ 既約多項式表 ３３ 多項式発生部 ３４、３５ 既約性判定部 ３６ 既約多項式格納域 ４１ ＣＰＵ ４２ メモリ ４３ 入力装置 ４４ 出力装置 ４５ 外部記憶装置 ４６ 媒体駆動装置 ４７ ネットワーク接続装置 ４８ バス ４９ 可搬記録媒体 ５０ データベース //
Claims (9)
- 【請求項１】 有限体を指定する条件を入力する入力手
段と、 入力された条件に基づいて、前記有限体の表現データを
自動的に生成する生成手段と、 生成された表現データを格納する表現データ格納手段と
を備えることを特徴とするデータ生成装置。 - 【請求項２】 前記表現データ格納手段に格納された表
現データに基づいて有限体演算を行う演算手段をさらに
備えることを特徴とする請求項１記載のデータ生成装
置。 - 【請求項３】 前記生成手段は、前記条件として前記有
限体を記述する素数のビット長が入力されたとき、該ビ
ット長に対応する素数データを自動的に生成し、前記表
現データ格納手段に格納することを特徴とする請求項１
記載のデータ生成装置。 - 【請求項４】 前記生成手段は、前記条件として前記有
限体を記述する拡大次数が入力されたとき、該拡大次数
に対応する既約多項式データを自動的に生成し、前記表
現データ格納手段に格納することを特徴とする請求項１
記載のデータ生成装置。 - 【請求項５】 前記生成手段は、最適化正規基底を使用
する指示が入力されたとき、前記拡大次数に対応する最
適化正規基底用既約多項式データを自動的に生成し、前
記表現データ格納手段に格納することを特徴とする請求
項４記載のデータ生成装置。 - 【請求項６】 あらかじめ決められた１つ以上の有限体
の表現データを格納する固定データ格納手段をさらに備
え、前記生成手段は、該固定データ格納手段に前記条件
に対応する有限体の表現データが存在するとき、該条件
に対応する有限体の表現データを前記表現データ格納手
段に格納し、該固定データ格納手段に前記条件に対応す
る有限体の表現データが存在しないとき、該条件に対応
する有限体の表現データを自動的に生成することを特徴
とする請求項１記載のデータ生成装置。 - 【請求項７】 有限体の表現データを指定する指定手段
と、指定された表現データが適切か否かを検証する検証
手段とをさらに備え、該検証手段は、該指定された表現
データが適切であれば、該指定された表現データを前記
表現データ格納手段に格納し、該指定された表現データ
が適切でなければ、該指定手段に他の表現データを要求
することを特徴とする請求項１記載のデータ生成装置。 - 【請求項８】 コンピュータのためのプログラムを記録
した記録媒体であって、 有限体を指定する条件が入力されたとき、入力された条
件に基づいて、該有限体の表現データを自動的に生成す
るステップと、 生成された表現データを出力するステップとを含む処理
を前記コンピュータに実行させるためのプログラムを記
録したコンピュータ読み取り可能な記録媒体。 - 【請求項９】 有限体を指定する条件を指定し、 指定された条件に基づいて、前記有限体の表現データを
自動的に生成し、 生成された表現データを有限体演算装置に供給すること
を特徴とするデータ生成方法。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10292099A JP3833412B2 (ja) | 1999-04-09 | 1999-04-09 | 有限体演算における表現データ生成装置および方法 |
| US09/503,205 US7142668B1 (en) | 1999-04-09 | 2000-02-14 | Apparatus and method for generating expression data for finite field operation |
| CA002298995A CA2298995C (en) | 1999-04-09 | 2000-02-21 | Apparatus and method for generating expression data for finite field operation |
| EP00301488A EP1043654A3 (en) | 1999-04-09 | 2000-02-25 | Apparatus and method for generating parameters for finite field operations |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10292099A JP3833412B2 (ja) | 1999-04-09 | 1999-04-09 | 有限体演算における表現データ生成装置および方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2000293507A true JP2000293507A (ja) | 2000-10-20 |
| JP3833412B2 JP3833412B2 (ja) | 2006-10-11 |
Family
ID=14340303
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10292099A Expired - Fee Related JP3833412B2 (ja) | 1999-04-09 | 1999-04-09 | 有限体演算における表現データ生成装置および方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US7142668B1 (ja) |
| EP (1) | EP1043654A3 (ja) |
| JP (1) | JP3833412B2 (ja) |
| CA (1) | CA2298995C (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2004533671A (ja) * | 2001-02-21 | 2004-11-04 | ミップス テクノロジーズ インコーポレイテッド | 多項式演算オペレーション |
| US7599981B2 (en) | 2001-02-21 | 2009-10-06 | Mips Technologies, Inc. | Binary polynomial multiplier |
| US7617388B2 (en) | 2001-02-21 | 2009-11-10 | Mips Technologies, Inc. | Virtual instruction expansion using parameter selector defining logic operation on parameters for template opcode substitution |
| US7860911B2 (en) | 2001-02-21 | 2010-12-28 | Mips Technologies, Inc. | Extended precision accumulator |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2811093A1 (fr) * | 2000-06-30 | 2002-01-04 | St Microelectronics Sa | Dispositif et procede d'evaluation d'algorithmes |
| GB0622553D0 (en) * | 2006-11-11 | 2006-12-20 | Ibm | A method, apparatus or software for managing partitioning in a cluster of nodes |
| US8707042B2 (en) * | 2008-08-28 | 2014-04-22 | Red Hat, Inc. | Sharing keys between cooperating parties |
| KR20120095210A (ko) * | 2011-02-18 | 2012-08-28 | 삼성전자주식회사 | 반도체 칩의 타이밍 해석 시스템 및 그 방법 |
| GB201907392D0 (en) | 2019-05-24 | 2019-07-10 | Nchain Holdings Ltd | Proof-of-work |
| GB2584154A (en) * | 2019-05-24 | 2020-11-25 | Nchain Holdings Ltd | Knowledge proof |
| GB201907396D0 (en) | 2019-05-24 | 2019-07-10 | Nchain Holdings Ltd | Hash function attacks |
| KR102217928B1 (ko) * | 2019-06-14 | 2021-02-19 | 광운대학교 산학협력단 | 랜덤 소수 생성 방법 및 그를 위한 장치 |
Family Cites Families (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4736423A (en) | 1985-04-30 | 1988-04-05 | International Business Machines Corporation | Technique for reducing RSA Crypto variable storage |
| US4687988A (en) * | 1985-06-24 | 1987-08-18 | International Business Machines Corporation | Weighted random pattern testing apparatus and method |
| US5189633A (en) * | 1990-01-12 | 1993-02-23 | Bonadio Allan R | Apparatus and method for interactively manipulating mathematical equations |
| SE466822B (sv) | 1990-06-15 | 1992-04-06 | Mastrovito Edoardo | Anordning foer multiplikation av tvaa element i en galoiskropp |
| ATE128297T1 (de) | 1991-03-14 | 1995-10-15 | Omnisec Ag | Verschlüsselungssystem mit öffentlichem schlüssel unter verwendung elliptischer kurven über ringe. |
| JPH05181418A (ja) | 1991-06-28 | 1993-07-23 | Matsushita Electric Ind Co Ltd | 楕円曲線を用いた公開鍵暗号通信方式 |
| US5272755A (en) | 1991-06-28 | 1993-12-21 | Matsushita Electric Industrial Co., Ltd. | Public key cryptosystem with an elliptic curve |
| JPH06295154A (ja) | 1993-04-09 | 1994-10-21 | Matsushita Electric Ind Co Ltd | 楕円曲線を用いた署名、認証及び秘密通信方式 |
| US5442707A (en) | 1992-09-28 | 1995-08-15 | Matsushita Electric Industrial Co., Ltd. | Method for generating and verifying electronic signatures and privacy communication using elliptic curves |
| JP3292362B2 (ja) | 1995-09-04 | 2002-06-17 | 日本電信電話株式会社 | 素数生成装置、素因数判定装置、および制限付き素数生成装置 |
| US5933501A (en) * | 1996-08-01 | 1999-08-03 | Harris Corporation | `Virtual` encryption scheme combining different encryption operators into compound-encryption mechanism |
| JP4058152B2 (ja) | 1998-01-27 | 2008-03-05 | 松下電器産業株式会社 | 楕円曲線演算装置 |
| CA2257008C (en) | 1998-12-24 | 2007-12-11 | Certicom Corp. | A method for accelerating cryptographic operations on elliptic curves |
-
1999
- 1999-04-09 JP JP10292099A patent/JP3833412B2/ja not_active Expired - Fee Related
-
2000
- 2000-02-14 US US09/503,205 patent/US7142668B1/en not_active Expired - Fee Related
- 2000-02-21 CA CA002298995A patent/CA2298995C/en not_active Expired - Fee Related
- 2000-02-25 EP EP00301488A patent/EP1043654A3/en not_active Ceased
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2004533671A (ja) * | 2001-02-21 | 2004-11-04 | ミップス テクノロジーズ インコーポレイテッド | 多項式演算オペレーション |
| US7599981B2 (en) | 2001-02-21 | 2009-10-06 | Mips Technologies, Inc. | Binary polynomial multiplier |
| US7617388B2 (en) | 2001-02-21 | 2009-11-10 | Mips Technologies, Inc. | Virtual instruction expansion using parameter selector defining logic operation on parameters for template opcode substitution |
| JP2009282992A (ja) * | 2001-02-21 | 2009-12-03 | Mips Technologies Inc | 多項式演算オペレーション |
| US7711763B2 (en) | 2001-02-21 | 2010-05-04 | Mips Technologies, Inc. | Microprocessor instructions for performing polynomial arithmetic operations |
| US7860911B2 (en) | 2001-02-21 | 2010-12-28 | Mips Technologies, Inc. | Extended precision accumulator |
| US8447958B2 (en) | 2001-02-21 | 2013-05-21 | Bridge Crossing, Llc | Substituting portion of template instruction parameter with selected virtual instruction parameter |
Also Published As
| Publication number | Publication date |
|---|---|
| EP1043654A3 (en) | 2005-02-09 |
| CA2298995A1 (en) | 2000-10-09 |
| CA2298995C (en) | 2003-08-05 |
| JP3833412B2 (ja) | 2006-10-11 |
| US7142668B1 (en) | 2006-11-28 |
| EP1043654A2 (en) | 2000-10-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP5068176B2 (ja) | デジタル署名と公開鍵の促進された検証 | |
| EP0823802A2 (en) | Secret communication and authentication scheme based on public key cryptosystem using N-adic expansion | |
| US6266688B1 (en) | Scheme for arithmetic operations in finite field and group operations over elliptic curves realizing improved computational speed | |
| KR101594553B1 (ko) | 암호화 키를 생성하는 방법, 이를 위한 네트워크 및 컴퓨터 프로그램 | |
| JP4282546B2 (ja) | 暗号装置、復号装置、鍵生成装置、プログラム及び方法 | |
| US20060251247A1 (en) | Encryption apparatus, decryption apparatus, key generation apparatus, program and method therefor | |
| JP3833412B2 (ja) | 有限体演算における表現データ生成装置および方法 | |
| JP3292107B2 (ja) | ２重ベクトル加算装置、２重ベクトル２倍装置及び２重ベクトル整数倍装置 | |
| JP5328993B2 (ja) | 署名生成装置及び署名生成方法及び記録媒体 | |
| US20020126838A1 (en) | Modular exponentiation calculation apparatus and modular exponentiation calculation method | |
| US6252960B1 (en) | Compression and decompression of elliptic curve data points | |
| JP2956709B2 (ja) | 公開鍵生成方法及び装置 | |
| JP3551853B2 (ja) | αＹａ＋βＸｂ＋１＝０という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置、生成方法、および記録媒体 | |
| JP2002358012A (ja) | 情報セキュリティ装置、べき乗演算装置、べき乗剰余演算装置及び楕円べき倍演算装置 | |
| JP4802228B2 (ja) | 鍵生成装置及びプログラム | |
| JP4861272B2 (ja) | 楕円曲線暗号演算装置、方法、プログラム | |
| JPWO2006057171A1 (ja) | 署名および検証方法ならびに署名および検証装置 | |
| JP3881273B2 (ja) | 暗号鍵生成装置、暗号鍵生成プログラムおよびそのプログラムを記録した記録媒体 | |
| JP2003228285A (ja) | 楕円曲線スカラ倍演算装置 | |
| JPH1155244A (ja) | 鍵回復方法および装置 | |
| JP2001194996A (ja) | 多項式の除算装置 | |
| JPH06282226A (ja) | 楕円曲線に基づく公開鍵暗号方式 | |
| CN117595984A (zh) | 基于sm2的可验证随机函数构造方法、装置、设备及介质 | |
| JP4237306B2 (ja) | 超楕円曲線ｃ生成装置、暗号管理装置、データ送信装置及びデータ受信装置 | |
| CN120910877A (zh) | 一种用于软件开发的计算机系统加密方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20051118 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20051129 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20060130 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20060718 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20060719 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100728 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100728 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110728 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110728 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120728 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120728 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130728 Year of fee payment: 7 |
|
| LAPS | Cancellation because of no payment of annual fees |