(57)【特許請求の範囲】
【請求項１】
素数ｐに対するガロア体ＧＦ（ｐ）上の一連の演算を実現するための演算装置であって、
ｇ、ｍを正の整数、Ｒを２以上の正の整数、δを大きさがＲmより小さい０以外の整数とし、ｐにｇを乗じた数を、
0004348463.tif 000037
と表すとき、
２つの整数データを互いに加算あるいは乗算して、演算結果である整数データの絶対値が上記Ｒm以上となった際には、適宜、下記第１の手段によって、上記整数データの絶対値を小さくすることを特徴とする演算部と、
前記整数データを１つ以上記憶するデータ記憶部と、
一連の演算手続きを記憶する手続き記憶部と、
前記手続き記憶部に記憶された演算手続きに基づいて前記演算部を制御する演算制御部とを具備し、
前記第１の手段は、前記演算結果である整数データをＲmで除算した商の整数部に前記δを乗じた値を、前記演算結果である整数データをＲmで除算した剰余から減ずることを特徴とし、
前記一連の演算では、前記演算制御部は、前記手続き記憶部に記憶された演算手続きに基づいて、前記データ記憶部に格納された整数データもしくは、外部から入力された整数データを前記演算部へ読み込んで演算を行い、その結果の整数データを前記データ記憶部へ出力するという手順を、前記手続き記憶部に記憶された前記一連の演算手続きの全ての演算が終了するまで複数回繰り返すことによって、一連の演算を実施することを特徴とする演算装置。
【請求項２】
素数ｐに対するガロア体ＧＦ（ｐ）上の一連の演算を実現するための演算装置であって、
ｇ、ｍを正の整数、Ｒを２以上の正の整数、δを大きさがＲmより小さい０以外の整数とし、ｐにｇを乗じた数を、
0004348463.tif 000038
と表すとき、
ＧＦ（ｐ）の元を整数データへ変換する第１のデータ変換部と、
２つの整数データを互いに加算あるいは乗算して、演算結果である整数データの絶対値が上記Ｒm以上となった際に、適宜、下記第１の手段によって、上記整数データの絶対値を小さくすることを特徴とする演算部と、
前記整数データを１つ以上記憶するデータ記憶部と、
一連の演算手続きを記憶する手続き記憶部と、
前記手続き記憶部に記憶された演算手続きに基づいて前記演算部を制御する演算制御部と、
前記整数データをＧＦ（ｐ）の元へ変換する第２のデータ変換部とを具備し、
前記第１の手段は、前記演算結果である整数データをＲmで除算した商の整数部に前記δを乗じた値を、前記演算結果である整数データをＲmで除算した剰余から減ずることを特徴とし、
ＧＦ（ｐ）の元を前記整数データに変換する前記第１のデータ変換部および前記整数データをＧＦ（ｐ）の元に変換する前記第２のデータ変換部においては、
前記整数データと前記ＧＦ（ｐ）の元との関係は、前記ＧＦ（ｐ）の元は、前記整数データをｐで除算した剰余、即ち、０以上ｐ未満の整数であることを特徴とし、
前記一連の演算では、前記演算制御部は、前記手続き記憶部に記憶された演算手続きに基づいて、前記データ記憶部に格納された整数データもしくは、外部から前記第１のデータ変換部を通してＧＦ（ｐ）の元から整数に変換されたデータを前記演算部へ読み込んで演算を行い、その結果の整数データを前記データ記憶部へ出力するという手順を、前記手続き記憶部に記憶された前記一連の演算手続きの全ての演算が終了するまで複数回繰り返すことによって、一連の演算を実施することを特徴とする演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ガロア体上の演算装置に係り、より詳しくは、暗号化や復号化等を実現するセキュリティー技術、または、誤り訂正符号等の符号化器や復号化器で用いられるガロア体ＧＦ（ｐ）上の一連の演算を実現するための演算装置に関する。
【０００２】
【従来の技術】
近年、情報のディジタル化によって、様々なサービスが提供され、快適な生活環境が整備されつつある。例えば、インターネットの普及により、我々は、ネットワークに接続された世界中のサーバの提供するサービスの恩恵を受けることができる。ディジタル携帯電話の普及により、必要なときにすぐにコミュニケーションをとることが可能になり、通話以外の付加サービスが利用できたりする。クレジットカードやプリペイトカードは，現金のやりとりによる煩わしさを解消してくれる。
情報のディジタル化は，我々に利便性を提供してくれる反面、不正利用による被害を受けやすいという欠点を有する。盗聴によるプライバシーの侵害や個人情報の流出・複写・改ざん・なりすましによるシステムの不正利用などがそれである。それら問題の解決策として暗号技術が注目されており、中でも、ガロア体上の演算を利用した暗号技術の研究開発が盛んに行われている。
ｐを素数とするガロア体ＧＦ（ｐ）は、ｐ個の元からなる集合であり、通常は、０以上ｐ未満の整数を代表とする。
ガロア体の詳細説明については一般の代数の参考書に記述されているのでここでは割愛する。
ガロア体ＧＦ（ｐ）上では２種類の演算即ち、加算と乗算が定義される。
ＧＦ（ｐ）上の２つの元ａ、ｂのＧＦ（ｐ）上の加算は、ａ、ｂを整数上で加算した後に、ｐで除算して剰余を求めることにより実施される。即ち、ｃを加算結果とすると、
0004348463.tif 000002
と記述できる。
ＧＦ（ｐ）上の２つの元ａ、ｂのＧＦ（ｐ）上の乗算は、ａ、ｂを整数上で乗算した後に、ｐで除算して剰余を求めることにより実施される。即ち、ｃを乗算結果とすると、
0004348463.tif 000003
と記述できる。
【０００３】
【発明が解決しようとする課題】
しかしながら、このような従来のガロア体ＧＦ（ｐ）上の演算にあたっては、以下に述べるような問題があった。
つまり、上述したような演算を行う場合は、ＧＦ（ｐ）上の元を整数として演算し、後にｐで除算を行って剰余を求め、ＧＦ（ｐ）上の元に戻していた。
このため、ガロア体ＧＦ（ｐ）上の演算には、除算処理が必要となることから、演算処理のステップ数が多くなって、多大な処理時間を要し、計算速度が遅くなると共に、除算回路の回路規模が大きくなるという問題があった。
本発明は、上述した従来の課題を解決するためになされたものであって、ガロア体ＧＦ（ｐ）上の演算量を少なくして演算処理自体を高速化すると共に、演算回路の回路規模を小さくすることができるガロア体上の演算装置を提供することを目的とする。
【０００４】
【課題を解決するための手段】
上記目的を達成するために、請求項１記載の発明は、素数ｐに対するガロア体ＧＦ（ｐ）上の一連の演算を実現するための演算装置であって、ｇ、ｍを正の整数、Ｒを２以上の正の整数、δを大きさがＲmより小さい０以外の整数とし、ｐにｇを乗じた数を、
0004348463.tif 000004
と表すとき、２つの整数データを互いに加算あるいは乗算して、演算結果である整数データの絶対値が上記Ｒm以上となった際には、適宜、下記第１の手段によって、上記整数データの絶対値を小さくすることを特徴とする演算部と、前記整数データを１つ以上記憶するデータ記憶部と、一連の演算手続きを記憶する手続き記憶部と、前記手続き記憶部に記憶された演算手続きに基づいて前記演算部を制御する演算制御部とを具備し、前記第１の手段は、前記演算結果である前記整数データをＲmで除算した商の整数部に前記δを乗じた値を、前記演算結果である前記整数データをＲmで除算した剰余から減ずることを特徴とし、前記一連の演算では、前記演算制御部は、前記手続き記憶部に記憶された演算手続きに基づいて、前記データ記憶部に格納された整数データもしくは、外部から入力された整数データを前記演算部へ読み込んで演算を行い、その結果の整数データを前記データ記憶部へ出力するという手順を、前記手続き記憶部に記憶された前記一連の演算手続きの全ての演算が終了するまで複数回繰り返すことによって、一連の演算を実施するものである。
【０００５】
請求項２記載の発明は、素数ｐに対するガロア体ＧＦ（ｐ）上の一連の演算を実現するための演算装置であって、ｇ、ｍを正の整数、Ｒを２以上の正の整数、δを大きさがＲmより小さい０以外の整数とし、ｐにｇを乗じた数を、
0004348463.tif 000005
と表すとき、ＧＦ（ｐ）の元を整数データへ変換する第１のデータ変換部と、２つの整数データを互いに加算あるいは乗算して、演算結果である整数データの絶対値が上記Ｒm以上となった際に、適宜、下記第１の手段によって、上記整数データの絶対値を小さくすることを特徴とする演算部と、前記整数データを１つ以上記憶するデータ記憶部と、一連の演算手続きを記憶する手続き記憶部と、前記手続き記憶部に記憶された演算手続きに基づいて前記演算部を制御する演算制御部と、前記整数データをＧＦ（ｐ）の元へ変換する第２のデータ変換部とを具備し、前記第１の手段は、前記演算結果である前記整数データをＲmで除算した商の整数部に前記δを乗じた値を、前記演算結果である前記整数データをＲmで除算した剰余から減ずることを特徴とし、ＧＦ（ｐ）の元を前記整数データに変換する前記第１のデータ変換部および前記整数データをＧＦ（ｐ）の元に変換する前記第２のデータ変換部においては、前記整数データと前記ＧＦ（ｐ）の元との関係は、前記ＧＦ（ｐ）の元は、前記整数データをｐで除算した剰余、即ち、０以上ｐ未満の整数であることを特徴とし、前記一連の演算では、前記演算制御部は、前記手続き記憶部に記憶された演算手続きに基づいて、前記データ記憶部に格納された整数データもしくは、外部から前記第１のデータ変換部を通してＧＦ（ｐ）の元から整数に変換されたデータを前記演算部へ読み込んで演算を行い、その結果の整数データを前記データ記憶部へ出力するという手順を、前記手続き記憶部に記憶された前記一連の演算手続きの全ての演算が終了するまで複数回繰り返すことによって、一連の演算を実施するのものである。
【０００６】
以下、本発明の原理について説明する。本発明装置の演算部は、素数ｐに対するガロア体ＧＦ（ｐ）上の一連の演算を実現するための演算装置であって、ｇ、ｍを正の整数、Ｒを２以上の正の整数、δを大きさがＲmより小さい０以外の整数とし、ｐにｇを乗じた数を、
0004348463.tif 000006
と表すとき、２つの整数データを互いに加算あるいは乗算して、演算結果である整数データの絶対値が上記Ｒm以上となった際には、適宜、下記第１の手段によって、上記整数データの絶対値を小さくすることを特徴としており、前記第１の手段は、前記演算結果である前記整数データをＲmで除算した商の整数部に前記δを乗じた値を、前記演算結果である前記整数データをＲmで除算した剰余から減ずることを特徴としている。素数ｐでの除算と比較し、Ｒmでの除算が容易である。以下で、Ｒmでの除算を説明する。任意の整数Ｚ*は、基数Ｒを用いて表現すれば、下式になる。
0004348463.tif 000007
よって、Ｒmでの除算によって求められた商ｑ*は、
0004348463.tif 000008
上式で示せ、剰余ｒ*は、
0004348463.tif 000009
上式で示せる。また、前記整数Ｚ*，商ｑ*，剰余ｒ*をそれぞれＲ進表現すれば、
0004348463.tif 000010
上式となる。即ち、前記整数Ｚ*をＲmで除算した結果、商はｍ番目のブロックより上位のブロックであり、剰余はｍ番目以下のブロックとなるため、Ｒmでの除算はそれぞれのブロックを取出すだけの処理である。
【０００７】
【発明の実施の形態】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
（実施の形態１）
本実施の形態１では、ガロア体ＧＦ（ｐ）上の一連の演算を実現するため、図１に示すような演算装置100を用いて演算処理が行われる。ここでは、ｇ、ｍを正の整数、Ｒを２以上の正の整数、δを大きさがＲmより小さい０以外の整数とし、ｐにｇを乗じた数を、
0004348463.tif 000011
と表せる場合について述べる。
図１は、本実施の形態１に係る演算装置100の概略構成を示したブロック図であり、手続き記憶部101、演算制御部102、演算部103、データ記憶部104、第１のデータ変換部105、及び、第２のデータ変換部106などを備えていて、外部107との間で演算データの入出力等が行われる。手続き記憶部101は、一連の演算手続きを記憶する記憶領域である。演算制御部102は、上記手続き記憶部101に記憶されている演算手続きに基づいて、演算部103の制御を行うものである。演算部103は、整数である２つのデータを互いに演算して、整数であるデータを算出する１種類以上の演算を実現するものである。データ記憶部104は、整数のデータを１つ以上記憶する記憶領域である。
【０００８】
第１のデータ変換部105は、ガロア体ＧＦ（ｐ）上の元であるデータを整数のデータへ変換するものであり、第２のデータ変換部106は、整数のデータをガロア体ＧＦ（ｐ）上の元であるデータへ変換するものであり、整数のデータをａ*と表記し、ＧＦ（ｐ）上の元であるデータをａと表記した場合、整数のデータａ*を前記のｐで除算した剰余がａとなることを特徴としている。
そこで、上記演算装置100を用いて演算処理を行う場合は、演算制御部102が手続き記憶部101に記憶されている演算手続きに基づいてデータ記憶部104に格納された整数のデータ、あるいは、外部107から第１のデータ変換部105を通してＧＦ（ｐ）上の元であるデータから整数データに変換されたデータを前記演算部103へ読み込んで演算を行い、その結果である整数データを前記データ記憶部104へ出力するか、もしくは前記第２のデータ変換部106を介してＧＦ（ｐ）上の元であるデータに変換し外部107へ出力するという手順を複数回繰り返す。この手順により、一連の演算を実施し、その演算結果であるＧＦ（ｐ）上の元であるデータを外部107へ出力する。
また、図１に示す演算装置100の演算部103においては、２つの整数のデータを用いた演算においては、整数のデータを整数上で演算を行った後に、前記請求項１記載の第１の手段による手続きを行って算出した結果を、演算結果とするものである。
【０００９】
さらに、図１に示す演算装置100の演算部103においては、以下に述べる第１の演算、第２の演算を行う場合について述べる。即ち、２つの整数のデータをａ*、ｂ*とするとき、演算部103における第１の演算は、
0004348463.tif 000012
を実現する演算とし、また、演算部103における第２の演算は、
0004348463.tif 000013
を実現する演算とする。
本実施の形態１における前記第１の演算、前記第２の演算は、前述したようにそれぞれ、ガロア体ＧＦ（ｐ）上の乗算、加算に相当する演算である。しかしながら、ＧＦ（ｐ）上の乗算においては、各乗算ステップ毎にｐでの除算を実施する必要があったのに対し、本実施の形態１においては、ｐでの除算は前記第２のデータ変換処理においてのみ実施すればよく、従って、演算処理のステップ数を大幅に減らすことが可能となり、演算処理を高速化することができると共に、回路規模の小さい演算回路でガロア体ＧＦ（ｐ）上の一連の演算処理を実現することができるようになる。
なお、本実施の形態１では、演算部103においては、上述した第１、第２の演算を行うものだけではなく、第１の演算をおこなうものであってもよく、このような場合であっても、演算処理を高速化することができると共に、回路規模の小さい演算回路でガロア体ＧＦ（ｐ）上の一連の演算処理を実現することができる。
【００１０】
（実施の形態２）
本実施の形態２では、前記実施の形態１で説明した演算装置100で実施される演算の具体例を実際の数値を用いて詳細に説明する。
まず、ガロア体ＧＦ（ｐ）における素数ｐを以下のように選択する。
0004348463.tif 000014
ここで、請求項１記載の
0004348463.tif 000015
を以下のように選択すると、
0004348463.tif 000016
即ち、ｇ＝３，Ｒ＝２，ｍ＝１６７，δ＝１である。
さて、ＧＦ（ｐ）上の元、
0004348463.tif 000017
に対し、
0004348463.tif 000018
を算出する例を考える。
【００１１】
本実施例２においては、本発明における第１のデータ変換部は、ガロア体ＧＦ（ｐ）上の元であるデータを整数のデータへ変換するものであり、整数のデータａ*とガロア体ＧＦ（ｐ）上の元であるデータａとすれば、整数のデータａ*を前記ｐで除算した剰余がガロア体ＧＦ（ｐ）上の元であるデータａとなることを特徴としている。よって、本発明における第１のデータ変換の一例はＧＦ（ｐ）のデータを替えずに整数のデータとする。即ち、第１のデータ変換により、ＧＦ（ｐ）上の元ａ、ｂ、ｃがそれぞれ、ａ*、ｂ*、ｃ*とすると、
0004348463.tif 000019
となる。
本発明における第１の演算、第２の演算をそれぞれ、・、＋で表せば、前記
0004348463.tif 000020
なる演算は、前記ａ*、ｂ*、ｃ*を用いて、
0004348463.tif 000021
によって計算し、結果のｗ*を第２のデータ変換によってＧＦ（ｐ）上の元に写像すればよいことになる。ここにｗ*は、ＧＦ（ｐ）上の元であるデータを格納できる領域である。上記ｗ*を算出する演算は以下の手順で実施できる。
0004348463.tif 000022
Step1では本発明における第１の演算によって、ａ*およびｂ*が演算され、ｗ*に格納される。Step2では、本発明における第２の演算によって、ｃ*およびStep1において算出されたｗ*が演算され、ｗ*に格納される。Step3では、本発明における第１の演算によって、Step2において算出されたｗ*が演算され、ｗ*に格納される。Step1,Step2,Step3では、ｗ*の値が、
0004348463.tif 000023
のように遷移する。前記ｐは、
0004348463.tif 000024
であるので、結果のｗ*を第２のデータ変換によってＧＦ（ｐ）上の元に写像した結果は、
0004348463.tif 000025
のようになる。上記結果は、ＧＦ（ｐ）上で演算した、
0004348463.tif 000026
の値に一致する。
【００１２】
本実施の形態２では、ガロア体ＧＦ（ｐ）において、
0004348463.tif 000027
である場合について、実際の数値例を用いて説明したが、本発明では、上記ｐ、ｇ、Ｒ、ｍ、δは、ｐは素数、ｇ、Ｒは２以上の整数、ｍは正の整数、δは整数であって、
0004348463.tif 000028
となる場合であればどのようなものであってもよい。また、本実施の形態２においては、ガロア体ＧＦ（ｐ）上の一連の演算として、
0004348463.tif 000029
を算出する例を考えたが、本発明では、ガロア体ＧＦ（ｐ）上の一連の演算は、上記例に限らず、どのようなものであってもよい。
【００１３】
（実施の形態３）
本実施の形態３では、前記実施の形態１で説明した演算装置を楕円曲線暗号の暗号化処理に適用する方法を説明する。
ガロア体ＧＦ（ｐ）
但し、ｐは素数でかつ、ｐ＞３を定義体とする楕円曲線は、
0004348463.tif 000030
と定義される。ここに、ａ、ｂはＧＦ（ｐ）上の定数であり、ｘ、ｙはＧＦ（ｐ）上の元であり、楕円曲線上のＧＦ（ｐ）上の有理点は（ｘ、ｙ）のように表される。楕円曲線上に１つの点Ｇ＝（ｘG、ｙG）を定めると、その点を生成元として楕円曲線上に巡回加法群を形成することができる。ここに、ｘGおよびｙGはＧＦ（ｐ）の元である。以下の式は、楕円曲線上の点Ｐ＝（ｘ1，ｙ1）およびＱ＝（ｘ2，ｙ2）について加法を定義するものであり、上記巡回加法群を形成するために利用される。
▲１▼Ｐ−Ｐ＝０
▲２▼−Ｐ＝（ｘ1，−ｙ1）
▲３▼Ｐ≠ＱのときＰ＋Ｑ＝（ｘ3，ｙ3）。但し、
0004348463.tif 000031
【００１４】
ここに、ｘ1，ｘ2，ｘ3，ｙ1，ｙ2，ｙ3はＧＦ（ｐ）の元である。また、ＧＦ（ｐ）上の除算
0004348463.tif 000032
は、次のようにｘに
0004348463.tif 000033
を乗ずることで実現できる。
0004348463.tif 000034
また、
0004348463.tif 000035
はＧＦ（ｐ）上の乗算のみで実現できる。
【００１５】
以下に、楕円曲線暗号における暗号化の一例を示す。
楕円曲線の生成元をＧ＝（ｘG、ｙG），秘密の整数をｋ，公開鍵をＶ＝（ｘV、ｙV），メッセージをｐとする（但し、ｘG、ｙG、ｘV、ｙV、ｐはＧＦ（ｐ）の元）。このとき、暗号化されたメッセージは、（Ｗ、ｃ）となる。ここに、
0004348463.tif 000036
である。上記ｋＧは前述の楕円曲線上の点の加法によって、Ｇをｋ回加算した結果であり、上記ｋＶは、前述の楕円曲線上の点の加法によって、Ｖをｋ回加算した結果である。また、上記ｘW、ｙW、ｘC、ｙC、ｃはＧＦ（ｐ）の元である。
楕円曲線暗号に関しては、その原理は、例えば、IEEE P1363 Working Draft等に詳細に説明されている。
上記楕円曲線暗号によって暗号化されたメッセージは３対のＧＦ（ｐ）の元であり、暗号化されたメッセージを生成するのに用いたデータはｋ以外は全てＧＦ（ｐ）の元である。また、暗号化に利用した演算は全て、ＧＦ（ｐ）上の乗算、加算の組合わせで実現されている。
【００１６】
従って、上記暗号化は前記実施の形態１で説明した演算装置を利用して効率的に実施することができる。以下では、前記実施の形態１で説明した演算装置を楕円曲線暗号の暗号化処理に適用する手順を示す。
▲１▼手続き記憶部に秘密の整数ｋおよび暗号化手続きを記憶させる。
▲２▼外部からＧＦ（ｐ）上の元ｘG、ｙG、ｘV、ｙV、ｐを入力する。
▲３▼外部から入力されたＧＦ（ｐ）上の元を全て第１のデータ変換部によって整数データに変換し、データ記憶部へ格納する。
▲４▼手続き記憶部に記憶された秘密の整数ｋおよび暗号化手続きに基づいて、演算制御部はデータ記憶部に格納された上記整数データを読み込み、演算部において整数データ同士の演算を行い、結果をデータ記憶部へ格納する一連の手順をおこなう。
▲５▼データ記憶部に格納された整数データを第２のデータ変換部はＧＦ（ｐ）上の元に変換し、ｘW、ｙW、ｃとして外部へ出力する。
以上を以って、前記実施の形態１で説明した演算装置を利用して楕円曲線暗号における暗号化を効率よく実現することができる。
なお、本実施の形態３では、楕円曲線暗号における暗号化を例にとって説明したが、本発明は、必ずしも楕円曲線暗号の暗号化のみに適用されるものでなく、ＧＦ（ｐ）上の演算によって実現される一連の演算であればどのような演算にも適用することができる。
なお、本明細書中では、数式及び記号がイタリック（斜体）で書いてある部分と、ブロック体で書いてある部分とがあるが、その意味するところは同じである。
【００１７】
【発明の効果】
本発明は、以上説明してきたように、ＧＦ（ｐ）上の一連の演算をｐでの除算を実施することなしに実現するものであるから、演算処理のステップ数を大幅に削減し、演算処理を高速化すると共に、回路規模の小さい演算回路でガロア体ＧＦ（ｐ）上の一連の演算処理を実現する上で著しい効果を発揮する。
【図面の簡単な説明】
【図１】本実施の形態１に係るガロア体ＧＦ（ｐ）上の一連の演算を実現するための演算装置の概略構成を示したブロック図である。
【符号の説明】
１００  演算装置
１０１  手続き記憶部
１０２  演算制御部
１０３  演算部
１０４  データ記憶部
１０５  第１のデータ変換部
１０６  第２のデータ変換部
【図１】
0004348463.tif 000039