JPH06282226A - 楕円曲線に基づく公開鍵暗号方式 - Google Patents
楕円曲線に基づく公開鍵暗号方式Info
- Publication number
- JPH06282226A JPH06282226A JP5070436A JP7043693A JPH06282226A JP H06282226 A JPH06282226 A JP H06282226A JP 5070436 A JP5070436 A JP 5070436A JP 7043693 A JP7043693 A JP 7043693A JP H06282226 A JPH06282226 A JP H06282226A
- Authority
- JP
- Japan
- Prior art keywords
- elliptic curve
- decryption key
- decryption
- prime number
- mod
- 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.)
- Pending
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
- G06F7/725—Finite field arithmetic over elliptic curves
Abstract
(57)【要約】
【目的】 本発明の目的は、パラメータの素数の制限を
なくすことにより安全性を一層高めた楕円曲線に基づく
公開暗号方式を提供することである。 【構成】 本発明は、任意の素数を選び、素数に対応し
た暗号化鍵を公開ファイル装置に登録し、素数、暗号鍵
に対応する復号鍵表により生成し、素数と共に復号鍵表
を復号装置に記憶しておく。暗号化装置は公開ファイル
装置より受信者（復号装置）の公開鍵を入手し、平文を
楕円曲線上で乗算し、その値を暗号文として復号装置に
送信する。復号装置は暗号文から楕円曲線のパラメータ
を計算し、復号鍵表を用いてパラメータに対応する復号
鍵を選び、暗号文をを楕円曲線で乗算した値から中国剰
余定理を用いて平文を得る。
なくすことにより安全性を一層高めた楕円曲線に基づく
公開暗号方式を提供することである。 【構成】 本発明は、任意の素数を選び、素数に対応し
た暗号化鍵を公開ファイル装置に登録し、素数、暗号鍵
に対応する復号鍵表により生成し、素数と共に復号鍵表
を復号装置に記憶しておく。暗号化装置は公開ファイル
装置より受信者（復号装置）の公開鍵を入手し、平文を
楕円曲線上で乗算し、その値を暗号文として復号装置に
送信する。復号装置は暗号文から楕円曲線のパラメータ
を計算し、復号鍵表を用いてパラメータに対応する復号
鍵を選び、暗号文をを楕円曲線で乗算した値から中国剰
余定理を用いて平文を得る。
Description
【０００１】
【産業上の利用分野】本発明は、楕円曲線に基づく公開
鍵暗号方式に係り、特に、ディジタル化された文書を伝
送する際の暗号方式における有限のモノイド上の楕円曲
線に基づく暗号方式及び暗号方式に用いられる鍵生成装
置、暗号化装置及び復号装置における楕円曲線に基づく
公開鍵暗号方式に関する。
鍵暗号方式に係り、特に、ディジタル化された文書を伝
送する際の暗号方式における有限のモノイド上の楕円曲
線に基づく暗号方式及び暗号方式に用いられる鍵生成装
置、暗号化装置及び復号装置における楕円曲線に基づく
公開鍵暗号方式に関する。
【０００２】
【従来の技術】１９９０年に楕円曲線に基づく公開鍵暗
号（ＫＭＯＶ方式）が提案されている。このＫＭＯＶ方
式はパラメータｎ（＝ｐｑ）の素因数分解の困難さに安
全性の根拠をおいているものである。ＫＭＯＶ方式は、
パラメータの素数ｐ，ｑがｐ≡ｑ≡２（mod ３）また
は、ｐ≡ｑ≡３（mod ４）でなければならないという制
限がある。
号（ＫＭＯＶ方式）が提案されている。このＫＭＯＶ方
式はパラメータｎ（＝ｐｑ）の素因数分解の困難さに安
全性の根拠をおいているものである。ＫＭＯＶ方式は、
パラメータの素数ｐ，ｑがｐ≡ｑ≡２（mod ３）また
は、ｐ≡ｑ≡３（mod ４）でなければならないという制
限がある。
【０００３】
【発明が解決しようとする課題】しかしながら、従来の
公開鍵暗号方式にはＫＭＯＶ方式を用いた方式により暗
号方式を用いていたが、法のｎの素因数に制限があるた
め、この制限内で暗号方式を適用すると鍵の安全性に問
題がある。
公開鍵暗号方式にはＫＭＯＶ方式を用いた方式により暗
号方式を用いていたが、法のｎの素因数に制限があるた
め、この制限内で暗号方式を適用すると鍵の安全性に問
題がある。
【０００４】本発明は、上記の点に鑑みなされたもの
で、パラメータの素数の制限をなくすことにより安全性
を一層高めた楕円曲線に基づく公開暗号方式を提供する
ことを目的とする。
で、パラメータの素数の制限をなくすことにより安全性
を一層高めた楕円曲線に基づく公開暗号方式を提供する
ことを目的とする。
【０００５】
【課題を解決するための手段】図１は本発明の原理構成
図を示す。本発明は、受信者により５以上の任意の素数
ｐ，ｑを選択し、素数ｐ，ｑに対応する公開鍵ｅ，ｎを
登録する公開ファイル装置１０と、素数ｐ，ｑに対して
楕円曲線Ｅp （０，ｂ）：ｙ2 ≡ｘ3 ＋ｂp （mod
ｐ），Ｅq （０，ｂ）：ｙ2 ≡ｘ3 ＋ｂq （mod ｑ）の
位数ｂp ，ｂq とパラメータｂとの関係を示す識別子と
位数の対応を示す位数表を生成する位数表生成手段２１
と、素数ｐ，ｑと位数表生成手段２１により生成された
位数表から復号鍵を計算し、復号鍵と位数表の識別子と
の対応を示す復号鍵表を生成する復号鍵表生成手段２４
とを含む鍵生成装置２０と、平文Ｍと受信者の公開鍵
ｅ，ｎが入力され、平文Ｍを楕円曲線Ｅn （０，
ｂM ）：ｙ2 ≡ｘ3 ＋ｂM （mod ｎ）上で公開鍵ｅに基
づいて乗算する楕円曲線乗算手段３１を含み、暗号文を
出力する暗号化装置３０と、該鍵生成装置２０から受け
取った素数ｐ，ｑと復号鍵表を記憶する記憶手段４１
と、暗号化装置３０からの暗号文Ｃと素数ｐ，ｑから楕
円曲線Ｅp （０，ｂp）：ｙ2 ≡ｘ3 ＋ｂp （mod
ｐ），Ｅq （０，ｂq ）：ｙ2 ≡ｘ3 ＋ｂq （modｑ）
のパラメータｂp ，ｂq を計算する係数計算手段４２
と、記憶手段４１に記憶されている復号鍵表より楕円曲
線のパラメータに対応する復号鍵ｄp ，ｄq を検索する
復号鍵検索手段と、暗号化装置３０から入力された暗号
文Ｃを楕円曲線Ｅp （０，ｂp ），Ｅq （０，ｂq ）上
で復号鍵ｄp ，ｄq に基づいて乗算する楕円曲線乗算手
段４５と、楕円曲線乗算手段４５により求められた値Ｍ
p ，Ｍqと、素数ｐ，ｑから平文Ｍを中国剰余定理に基
づいて計算し出力する中国剰余定理計算手段４６とを含
む復号装置を有する。
図を示す。本発明は、受信者により５以上の任意の素数
ｐ，ｑを選択し、素数ｐ，ｑに対応する公開鍵ｅ，ｎを
登録する公開ファイル装置１０と、素数ｐ，ｑに対して
楕円曲線Ｅp （０，ｂ）：ｙ2 ≡ｘ3 ＋ｂp （mod
ｐ），Ｅq （０，ｂ）：ｙ2 ≡ｘ3 ＋ｂq （mod ｑ）の
位数ｂp ，ｂq とパラメータｂとの関係を示す識別子と
位数の対応を示す位数表を生成する位数表生成手段２１
と、素数ｐ，ｑと位数表生成手段２１により生成された
位数表から復号鍵を計算し、復号鍵と位数表の識別子と
の対応を示す復号鍵表を生成する復号鍵表生成手段２４
とを含む鍵生成装置２０と、平文Ｍと受信者の公開鍵
ｅ，ｎが入力され、平文Ｍを楕円曲線Ｅn （０，
ｂM ）：ｙ2 ≡ｘ3 ＋ｂM （mod ｎ）上で公開鍵ｅに基
づいて乗算する楕円曲線乗算手段３１を含み、暗号文を
出力する暗号化装置３０と、該鍵生成装置２０から受け
取った素数ｐ，ｑと復号鍵表を記憶する記憶手段４１
と、暗号化装置３０からの暗号文Ｃと素数ｐ，ｑから楕
円曲線Ｅp （０，ｂp）：ｙ2 ≡ｘ3 ＋ｂp （mod
ｐ），Ｅq （０，ｂq ）：ｙ2 ≡ｘ3 ＋ｂq （modｑ）
のパラメータｂp ，ｂq を計算する係数計算手段４２
と、記憶手段４１に記憶されている復号鍵表より楕円曲
線のパラメータに対応する復号鍵ｄp ，ｄq を検索する
復号鍵検索手段と、暗号化装置３０から入力された暗号
文Ｃを楕円曲線Ｅp （０，ｂp ），Ｅq （０，ｂq ）上
で復号鍵ｄp ，ｄq に基づいて乗算する楕円曲線乗算手
段４５と、楕円曲線乗算手段４５により求められた値Ｍ
p ，Ｍqと、素数ｐ，ｑから平文Ｍを中国剰余定理に基
づいて計算し出力する中国剰余定理計算手段４６とを含
む復号装置を有する。
【０００６】
【作用】本発明は、５以上の任意の素数ｐ，ｑを選び、
ｐ，ｑに対応した暗号化鍵ｅ，ｎを公開ファイル装置１
０に登録し、ｐ，ｑ，ｅに対応する復号鍵表を生成し、
素数ｐ，ｑと共に復号鍵表を復号装置に記憶しておく。
送信者（暗号化装置）は公開ファイル装置１０より受信
者（復号装置）の公開鍵ｅ，ｎを入手し、平文Ｍ＝（ｍ
x ，ｍy ）を楕円曲線Ｅn （０，ｂM ）：ｙ2 ≡ｘ3 ＋
ｂM （mod ｎ）上でｅ倍した点Ｃを暗号文Ｃとして受信
者（復号装置）に送信する。受信者（復号装置）は暗号
文Ｃから楕円曲線Ｅp （０，ｂp ）：ｙ2 ≡ｘ3 ＋ｂp
（mod ｐ），Ｅq （０，ｂq ）：ｙ2 ≡ｘ3 ＋ｂq （mo
d ｑ）のパラメータｂp ，ｂq を計算し、復号鍵表を用
いてパラメータｂp ，ｂq を計算し、復号装置側で予め
記憶されている復号鍵表を用いてパラメータｂp ，ｂq
に対応する復号鍵ｄp ，ｄqを選び、暗号文Ｃを楕円曲
線でｄp ，ｄq 倍した点Ｍp ，Ｍq とから中国剰余定理
を用いて平文Ｍを得る。これにより、公開鍵暗号方式と
して、従来のＫＭＯＶ方式に代わり有限モノイド上の楕
円曲線に基づいており、用いる素数に制限がないため、
素因数分解がＫＭＯＶ方式よりも難解になり、安全性が
高くなる。
ｐ，ｑに対応した暗号化鍵ｅ，ｎを公開ファイル装置１
０に登録し、ｐ，ｑ，ｅに対応する復号鍵表を生成し、
素数ｐ，ｑと共に復号鍵表を復号装置に記憶しておく。
送信者（暗号化装置）は公開ファイル装置１０より受信
者（復号装置）の公開鍵ｅ，ｎを入手し、平文Ｍ＝（ｍ
x ，ｍy ）を楕円曲線Ｅn （０，ｂM ）：ｙ2 ≡ｘ3 ＋
ｂM （mod ｎ）上でｅ倍した点Ｃを暗号文Ｃとして受信
者（復号装置）に送信する。受信者（復号装置）は暗号
文Ｃから楕円曲線Ｅp （０，ｂp ）：ｙ2 ≡ｘ3 ＋ｂp
（mod ｐ），Ｅq （０，ｂq ）：ｙ2 ≡ｘ3 ＋ｂq （mo
d ｑ）のパラメータｂp ，ｂq を計算し、復号鍵表を用
いてパラメータｂp ，ｂq を計算し、復号装置側で予め
記憶されている復号鍵表を用いてパラメータｂp ，ｂq
に対応する復号鍵ｄp ，ｄqを選び、暗号文Ｃを楕円曲
線でｄp ，ｄq 倍した点Ｍp ，Ｍq とから中国剰余定理
を用いて平文Ｍを得る。これにより、公開鍵暗号方式と
して、従来のＫＭＯＶ方式に代わり有限モノイド上の楕
円曲線に基づいており、用いる素数に制限がないため、
素因数分解がＫＭＯＶ方式よりも難解になり、安全性が
高くなる。
【０００７】
【実施例】以下、図面と共に本発明の実施例を説明す
る。
る。
【０００８】図２は本発明の一実施例のシステム構成を
示す。同図のシステムは、公開鍵ｅ，ｎを登録しておく
公開ファイル装置１０、公開鍵ｅ，ｎ及び、復号鍵
ｄp ，ｄq を生成する鍵生成装置２０、入力された平文
Ｍを公開ファイル装置１０からの公開鍵ｅ，ｎにより平
文Ｍを暗号化し、暗号文Ｃを作成し、出力する暗号化装
置３０と、暗号化装置３０から入力された暗号文Ｃを楕
円曲線を用いて復号し，平文Ｍを出力する復号装置４０
から構成される。
示す。同図のシステムは、公開鍵ｅ，ｎを登録しておく
公開ファイル装置１０、公開鍵ｅ，ｎ及び、復号鍵
ｄp ，ｄq を生成する鍵生成装置２０、入力された平文
Ｍを公開ファイル装置１０からの公開鍵ｅ，ｎにより平
文Ｍを暗号化し、暗号文Ｃを作成し、出力する暗号化装
置３０と、暗号化装置３０から入力された暗号文Ｃを楕
円曲線を用いて復号し，平文Ｍを出力する復号装置４０
から構成される。
【０００９】以下、実施例を説明するにあたり、本発明
の公開鍵暗号方式における前提条件を説明する。本発明
における公開鍵暗号方式は、有限モノイド上の楕円曲線
に基づいており、用いる素数に制限のないものである。
の公開鍵暗号方式における前提条件を説明する。本発明
における公開鍵暗号方式は、有限モノイド上の楕円曲線
に基づいており、用いる素数に制限のないものである。
【００１０】まず、楕円曲線に関する記号の説明をす
る。素数ｐとパラメータａ，ｂに対しし、 ｙ2 ≡ｘ3 ＋ａｘ＋ｂ(mod ｐ） を満たす点の集合に無限遠点Οを加えた集合を楕円曲線
Ｅn （ａ，ｂ）と呼ぶ。本発明の実施例ではパラメータ
ａが零（ａ＝０）の楕円曲線Ｅn （０，ｂ）を用いる。
る。素数ｐとパラメータａ，ｂに対しし、 ｙ2 ≡ｘ3 ＋ａｘ＋ｂ(mod ｐ） を満たす点の集合に無限遠点Οを加えた集合を楕円曲線
Ｅn （ａ，ｂ）と呼ぶ。本発明の実施例ではパラメータ
ａが零（ａ＝０）の楕円曲線Ｅn （０，ｂ）を用いる。
【００１１】以下に本発明の一実施例の各装置について
説明する。 １．公開ファイル装置 公開ファイル装置１０は、受信者（復号装置）により５
以上の任意の素数ｐ，ｑが選択され、この素数に対応し
た暗号化鍵（公開鍵）ｅ，ｎが登録される。
説明する。 １．公開ファイル装置 公開ファイル装置１０は、受信者（復号装置）により５
以上の任意の素数ｐ，ｑが選択され、この素数に対応し
た暗号化鍵（公開鍵）ｅ，ｎが登録される。
【００１２】２．鍵生成装置 図３は本発明の一実施例の鍵生成装置の構成を示す。同
図に示す復号鍵生成装置２４は、素数生成器２４１、位
数表生成装置２４２、２４３及び復号鍵表生成装置２４
４から構成される。素数生成器２４１は素数ｐ，ｑを生
成し、素数ｐを位数表生成装置２４２に、素数ｑを位数
表生成装置２４３に入力する。
図に示す復号鍵生成装置２４は、素数生成器２４１、位
数表生成装置２４２、２４３及び復号鍵表生成装置２４
４から構成される。素数生成器２４１は素数ｐ，ｑを生
成し、素数ｐを位数表生成装置２４２に、素数ｑを位数
表生成装置２４３に入力する。
【００１３】（１）位数表生成装置 ここで、各位数表生成装置２４２、２４３は、素数生成
器２４１から素数ｐ，ｑにより位数表を作成する。位数
表生成装置２４２は、素数ｐに対して楕円曲線 Ｅp （０，ｂ）：ｙ2 ≡ｘ3 ＋ｂ（mod ｐ） の位数とパラメータｂとの関係を示す識別子と位数の対
応を示す位数表を生成する。もし、素数ｐが ｐ≡２（mod ３） であれば、位数表生成装置２４２が生成する位数表は、
器２４１から素数ｐ，ｑにより位数表を作成する。位数
表生成装置２４２は、素数ｐに対して楕円曲線 Ｅp （０，ｂ）：ｙ2 ≡ｘ3 ＋ｂ（mod ｐ） の位数とパラメータｂとの関係を示す識別子と位数の対
応を示す位数表を生成する。もし、素数ｐが ｐ≡２（mod ３） であれば、位数表生成装置２４２が生成する位数表は、
【００１４】
【表１】
【００１５】となる。位数表生成装置２４２は、この位
数表を復号鍵表生成装置２４５に出力する。
数表を復号鍵表生成装置２４５に出力する。
【００１６】また、位数表生成装置２４３は素数ｑに対
して楕円曲線 Ｅq （０，ｂ）：ｙ2 ≡ｘ3 ＋ｂ（mod q ） の位数とパラメータｂとの関係を示す識別子と位数の対
応を示す位数表を生成する。もし、素数ｑが、 ｑ≡２（mod ３） であれば、位数表生成装置２４３が生成する位数表は、
して楕円曲線 Ｅq （０，ｂ）：ｙ2 ≡ｘ3 ＋ｂ（mod q ） の位数とパラメータｂとの関係を示す識別子と位数の対
応を示す位数表を生成する。もし、素数ｑが、 ｑ≡２（mod ３） であれば、位数表生成装置２４３が生成する位数表は、
【００１７】
【表２】
【００１８】となり、位数表生成装置２４３はこの位数
表を復号鍵生成装置２４５に出力する。
表を復号鍵生成装置２４５に出力する。
【００１９】ここで、位数表生成装置２４２、２４３は ｐ＝ππ’かつ、π≡２（mod ３） を満たす二次体Ｚ［ω］上の整数 π＝αーβω を求める。この時、位数表生成装置２４２、２４３は以
下に示す位数表を生成する。
下に示す位数表を生成する。
【００２０】
【表３】
【００２１】位数表生成装置２４２、２４３は、この位
数表を復号鍵生成装置２４５に出力し、動作を終了す
る。
数表を復号鍵生成装置２４５に出力し、動作を終了す
る。
【００２２】（２）復号鍵表生成装置 次に、復号鍵表生成装置２４５は、２つの素数ｐ，ｑと
各素数の位数表から公開鍵ｅ，ｎを計算し、復号鍵表を
生成し、公開鍵ｅ，ｎ及び復号鍵表を出力する。
各素数の位数表から公開鍵ｅ，ｎを計算し、復号鍵表を
生成し、公開鍵ｅ，ｎ及び復号鍵表を出力する。
【００２３】図４は本発明の一実施例の鍵生成装置の復
号鍵表生成装置を説明するための図である。復号鍵表生
成装置２４５は、素数ｐ，ｑの入力により使用する復号
鍵生成装置１〜３を使い分ける。
号鍵表生成装置を説明するための図である。復号鍵表生
成装置２４５は、素数ｐ，ｑの入力により使用する復号
鍵生成装置１〜３を使い分ける。
【００２４】まず、素数ｐ，ｑが、 ｐ≡ｑ≡２(mod ３） であれば、復号鍵生成装置１に素数ｐ，ｑとそれらの位
数表を入力し、復号鍵生成装置１の出力をそのまま、復
号鍵生成装置２４５の出力とし、処理を終了する。
数表を入力し、復号鍵生成装置１の出力をそのまま、復
号鍵生成装置２４５の出力とし、処理を終了する。
【００２５】詳しくは、復号鍵生成装置１は、入力とし
て素数ｐ，ｑと、当該素数ｐ，ｑの位数表が与えられ
る。ここで、復号鍵生成装置１は、 ｇｃｄ（ｅ，ｐ＋１）＝ｇｃｄ（ｅ，ｑ＋１）＝１ となる公開鍵ｅをランダムに設定する。そして、以下の
式を満たす復号鍵ｄp0，ｄq0を計算する。 ｅ・ｄp0≡１(mod ｐ）， ｅ・ｄq0≡１(mod
ｑ）． これにより、復号鍵生成装置１が出力する復号鍵表は、
て素数ｐ，ｑと、当該素数ｐ，ｑの位数表が与えられ
る。ここで、復号鍵生成装置１は、 ｇｃｄ（ｅ，ｐ＋１）＝ｇｃｄ（ｅ，ｑ＋１）＝１ となる公開鍵ｅをランダムに設定する。そして、以下の
式を満たす復号鍵ｄp0，ｄq0を計算する。 ｅ・ｄp0≡１(mod ｐ）， ｅ・ｄq0≡１(mod
ｑ）． これにより、復号鍵生成装置１が出力する復号鍵表は、
【００２６】
【表４】
【００２７】とする。但し、これらの表において、左の
列の項は識別子を表し、右の列の項はその識別子に対応
する復号鍵を表す。これにより復号鍵生成装置１は暗号
化鍵ｅ，ｎと復号鍵表を出力する。
列の項は識別子を表し、右の列の項はその識別子に対応
する復号鍵を表す。これにより復号鍵生成装置１は暗号
化鍵ｅ，ｎと復号鍵表を出力する。
【００２８】次に、素数ｐ，ｑが、 ｐ≡１(mod ３），ｑ≡２（mod ３） であれば、復号鍵表生成装置２に素数ｐ，ｑとそれらの
位数表を入力し、復号鍵表生成装置２の出力をそのまま
復号鍵表生成装置２４５の出力とし、処理を終了する。
位数表を入力し、復号鍵表生成装置２の出力をそのまま
復号鍵表生成装置２４５の出力とし、処理を終了する。
【００２９】詳しくは、復号鍵生成装置２は、入力とし
て素数ｐ，ｑと、当該素数ｐ，ｑの位数表が与えられ
る。ここで、復号鍵生成装置１は、 ｇｃｄ（ｅ，Ｎp0）＝ｇｃｄ（ｅ，Ｎp0） ＝ｇｃｄ（ｅ，Ｎp1） ＝ｇｃｄ（ｅ，Ｎp2） ＝ｇｃｄ（ｅ，Ｎp3） ＝（ｅ，ｑ＋１） ＝１ となる公開鍵ｅをランダムに設定する。そして、以下の
式を満たす復号鍵ｄpi（ｉ＝０〜３）、ｄq0を計算す
る。
て素数ｐ，ｑと、当該素数ｐ，ｑの位数表が与えられ
る。ここで、復号鍵生成装置１は、 ｇｃｄ（ｅ，Ｎp0）＝ｇｃｄ（ｅ，Ｎp0） ＝ｇｃｄ（ｅ，Ｎp1） ＝ｇｃｄ（ｅ，Ｎp2） ＝ｇｃｄ（ｅ，Ｎp3） ＝（ｅ，ｑ＋１） ＝１ となる公開鍵ｅをランダムに設定する。そして、以下の
式を満たす復号鍵ｄpi（ｉ＝０〜３）、ｄq0を計算す
る。
【００３０】ｅ・ｄpi≡１(mod ｐ）（ｉ＝０〜３）， ｅ・ｄq0≡１(mod ｑ）． これにより、復号鍵生成装置２が出力する復号鍵表は、
【００３１】
【表５】
【００３２】とする。但し、これらの表において、左の
列の項は識別子を表し、右の列の項はその識別子に対応
する復号鍵を表す。これにより復号鍵生成装置２は暗号
化鍵ｅ，ｎと復号鍵表を出力する。
列の項は識別子を表し、右の列の項はその識別子に対応
する復号鍵を表す。これにより復号鍵生成装置２は暗号
化鍵ｅ，ｎと復号鍵表を出力する。
【００３３】さらに、素数ｐ，ｑが ｐ≡ｑ≡１（mod ３） ならば、復号鍵表生成装置３に素数ｐ，ｑとそれらの位
数表を入力し、復号鍵表生成装置２４５の出力とし、処
理を終了する。
数表を入力し、復号鍵表生成装置２４５の出力とし、処
理を終了する。
【００３４】詳しくは、復号鍵生成装置３は、入力とし
て素数ｐ，ｑと、当該素数ｐ，ｑの位数表が与えられ
る。ここで、復号鍵生成装置１は、 ｇｃｄ（ｅ，Ｎpi）＝ｇｃｄ（ｅ，Ｎpi） ＝１（ｉ＝０〜３） となる公開鍵ｅをランダムに設定する。そして、以下の
式を満たす復号鍵ｄpi、ｄqiを計算する。
て素数ｐ，ｑと、当該素数ｐ，ｑの位数表が与えられ
る。ここで、復号鍵生成装置１は、 ｇｃｄ（ｅ，Ｎpi）＝ｇｃｄ（ｅ，Ｎpi） ＝１（ｉ＝０〜３） となる公開鍵ｅをランダムに設定する。そして、以下の
式を満たす復号鍵ｄpi、ｄqiを計算する。
【００３５】ｅ・ｄpi≡１(mod ｐ） ｅ・ｄqi≡１(mod ｑ）（ｉ＝０〜３）． これにより、復号鍵生成装置３が出力する復号鍵表は、
【００３６】
【表６】
【００３７】とする。但し、これらの表において、左の
列の項は識別子を表し、右の列の項はその識別子に対応
する復号鍵を表す。
列の項は識別子を表し、右の列の項はその識別子に対応
する復号鍵を表す。
【００３８】これにより復号鍵生成装置３は暗号化鍵
ｅ，ｎと復号鍵表を公開ファイル装置１０または、復号
装置４０に出力する。
ｅ，ｎと復号鍵表を公開ファイル装置１０または、復号
装置４０に出力する。
【００３９】（３）暗号化装置 図５は本発明の一実施例の暗号化装置の構成を示す。暗
号化装置３０は楕円曲線Ｅn （０，ｂM ）上において入
力された平文Ｍに公開鍵ｅ分を乗算する楕円曲線乗算器
３１を有する。
号化装置３０は楕円曲線Ｅn （０，ｂM ）上において入
力された平文Ｍに公開鍵ｅ分を乗算する楕円曲線乗算器
３１を有する。
【００４０】暗号化装置３０は、入力として、公開鍵
ｅ，ｎと平文Ｍ＝（ｍx ，ｍy ）が与えられる。但し、 ０＜ｍx ，ｍy ＜ｎ ａｎｄ ｇｃｄ（ｍx ，ｎ）＝ｇ
ｃｄ（ｍy ，ｎ）＝１ とする。
ｅ，ｎと平文Ｍ＝（ｍx ，ｍy ）が与えられる。但し、 ０＜ｍx ，ｍy ＜ｎ ａｎｄ ｇｃｄ（ｍx ，ｎ）＝ｇ
ｃｄ（ｍy ，ｎ）＝１ とする。
【００４１】暗号化装置３０は、楕円曲線Ｅn （０，ｂ
M ）：ｙ2 ≡ｘ3 ＋ｂM （mod ｎ）上で、 ｅ・ｍ over Ｅn （０，ｂM ） を計算し、その計算結果を暗号文Ｃとする。そして、暗
号文Ｃを復号装置４０に出力して処理を終了する。
M ）：ｙ2 ≡ｘ3 ＋ｂM （mod ｎ）上で、 ｅ・ｍ over Ｅn （０，ｂM ） を計算し、その計算結果を暗号文Ｃとする。そして、暗
号文Ｃを復号装置４０に出力して処理を終了する。
【００４２】（４）復号装置 図６は本発明の一実施例の復号装置の構成を示す。同図
において、復号装置４０は、素数ｐ記憶部４１０、素数
ｑ記憶部４１１、第１、第２の係数計算器４２０、４２
１、第１、第２の識別子計算器４３０、４３１、復号鍵
検索器４４０、４４１、第１、第２の楕円曲線乗算器４
５０、４５１、ｐの復号鍵表記憶部４７０、ｑの復号鍵
記憶部４７１及び中国剰余定理計算器４６０より構成さ
れる。
において、復号装置４０は、素数ｐ記憶部４１０、素数
ｑ記憶部４１１、第１、第２の係数計算器４２０、４２
１、第１、第２の識別子計算器４３０、４３１、復号鍵
検索器４４０、４４１、第１、第２の楕円曲線乗算器４
５０、４５１、ｐの復号鍵表記憶部４７０、ｑの復号鍵
記憶部４７１及び中国剰余定理計算器４６０より構成さ
れる。
【００４３】復号装置４０の素数ｐ記憶部４１０は素数
ｐを記憶しておき、素数ｑ記憶部４１１は素数ｑを記憶
しておく。
ｐを記憶しておき、素数ｑ記憶部４１１は素数ｑを記憶
しておく。
【００４４】第１の係数計算器４２０は、暗号化装置３
０から入力された暗号文Ｃと素数ｐ記憶部４１０に記憶
されている素数ｐから楕円曲線 Ｅp （０，ｂp ）：ｙ2 ≡ｘ3 ＋ｂp （mod ｐ） のパラメータｂp を計算する。
０から入力された暗号文Ｃと素数ｐ記憶部４１０に記憶
されている素数ｐから楕円曲線 Ｅp （０，ｂp ）：ｙ2 ≡ｘ3 ＋ｂp （mod ｐ） のパラメータｂp を計算する。
【００４５】第２の係数計算器４２１は、暗号化装置３
０から入力された暗号文Ｃと素数ｑ記憶部４１１に記憶
されている素数ｑから楕円曲線 Ｅq （０，ｂq ）：ｙ2 ≡ｘ3 ＋ｂq （mod ｑ） のパラメータｂq を計算する。
０から入力された暗号文Ｃと素数ｑ記憶部４１１に記憶
されている素数ｑから楕円曲線 Ｅq （０，ｂq ）：ｙ2 ≡ｘ3 ＋ｂq （mod ｑ） のパラメータｂq を計算する。
【００４６】第１の識別子計算器４３０は、楕円曲線の
パラメータｂp と素数ｐから識別子τp を計算する。
パラメータｂp と素数ｐから識別子τp を計算する。
【００４７】第２の識別子計算器４３１は、楕円曲線の
パラメータｂq と素数ｑから識別子τq を計算する。
パラメータｂq と素数ｑから識別子τq を計算する。
【００４８】ｐの復号鍵表記憶部４７０は、素数ｐの復
号鍵表を記憶し、ｑの復号鍵表記憶部４７１は素数ｑの
復号鍵表を記憶する。
号鍵表を記憶し、ｑの復号鍵表記憶部４７１は素数ｑの
復号鍵表を記憶する。
【００４９】復号鍵検索器４４０はｐの復号鍵表記憶部
４７０からの復号鍵表と第１の識別子計算器４３０から
識別子τp が入力されると、当該識別子τp により復号
鍵表を検索し、復号鍵ｄp を取得する。
４７０からの復号鍵表と第１の識別子計算器４３０から
識別子τp が入力されると、当該識別子τp により復号
鍵表を検索し、復号鍵ｄp を取得する。
【００５０】復号鍵検索器４４１は識別子ｑが入力され
ると、当該識別子τq により復号鍵表を検索し、復号鍵
ｄq を取得する。
ると、当該識別子τq により復号鍵表を検索し、復号鍵
ｄq を取得する。
【００５１】第１の楕円曲線乗算部４５０は、暗号化装
置３０から入力された暗号文Ｃを楕円曲線Ｅp （０，ｂ
p ）上でｄp 倍して、乗算された結果Ｍp を出力する。
置３０から入力された暗号文Ｃを楕円曲線Ｅp （０，ｂ
p ）上でｄp 倍して、乗算された結果Ｍp を出力する。
【００５２】第２の楕円曲線乗算部４５１は、暗号化装
置３０から入力された暗号文Ｃを楕円曲線Ｅq （０，ｂ
q ）上でｄq 倍して、乗算された結果Ｍq を出力する。
置３０から入力された暗号文Ｃを楕円曲線Ｅq （０，ｂ
q ）上でｄq 倍して、乗算された結果Ｍq を出力する。
【００５３】中国剰余定理計算器４６０は素数ｐ記憶部
４１０からの素数ｐと素数ｑ記憶部４１１からの素数ｑ
と第１の楕円曲線乗算器４５０、第２の楕円曲線乗算器
４５１からＭp ，Ｍq が入力されると、中国剰余定理に
より、平文Ｍを出力する。
４１０からの素数ｐと素数ｑ記憶部４１１からの素数ｑ
と第１の楕円曲線乗算器４５０、第２の楕円曲線乗算器
４５１からＭp ，Ｍq が入力されると、中国剰余定理に
より、平文Ｍを出力する。
【００５４】詳しくは、復号装置４０は、入力として、
暗号化装置３０から暗号文Ｃ＝（ｃ x ，ｃy ）が与えら
れ、第１及び第２の係数計算器４２０、４２１では、パ
ラメータ ｂp ＝ｃy 2 −ｃx 3mod ｐ， ｂq ＝ｃy 2 −ｃx 3 mod ｑ を計算する。
暗号化装置３０から暗号文Ｃ＝（ｃ x ，ｃy ）が与えら
れ、第１及び第２の係数計算器４２０、４２１では、パ
ラメータ ｂp ＝ｃy 2 −ｃx 3mod ｐ， ｂq ＝ｃy 2 −ｃx 3 mod ｑ を計算する。
【００５５】第１及び第２の識別子計算器４３０、４３
１は、各パラメータｂp 、ｂq と、各素数記憶部４１
０、４１１から得られた素数によりもし、ｐ≡ｑ≡２
（mod ３）であれば、素数ｐに対する識別子を「＊」、
素数ｑに対する識別子を「＊」とする。また、ｐ≡１
（mod ３），ｑ≡２（mod ３）ならば、素数ｐに対する
識別子τp を、
１は、各パラメータｂp 、ｂq と、各素数記憶部４１
０、４１１から得られた素数によりもし、ｐ≡ｑ≡２
（mod ３）であれば、素数ｐに対する識別子を「＊」、
素数ｑに対する識別子を「＊」とする。また、ｐ≡１
（mod ３），ｑ≡２（mod ３）ならば、素数ｐに対する
識別子τp を、
【００５６】
【数１】 の計算結果とし、素数ｑに対する識別子τq を、
【００５７】
【数２】
【００５８】とし、各々の計算結果を素数ｐに対する識
別子τp 、素数ｑに対する識別子τqとする。復号鍵検
索器４４０、４４１は、ｐ，ｑの復号鍵表記録部４７
０、４７１から復号鍵表を識別子τp ，τq により検索
し、復号鍵ｄp ，ｄq を得る。次に、第 1の楕円曲線乗
算器４５０、４５１は、楕円曲線 Ｅp （０，ｂp ）：ｙ2 ≡ｘ3 ＋ｂp （mod ｐ） Ｅq （０，ｂq ）：ｙ2 ≡ｘ3 ＋ｂq （mod ｑ） 上において、 ｄp ・Ｃ over Ｅp （０，ｂp ）， ｄq ・Ｃ over Ｅq （０，ｂq ） を計算し、各々の計算結果をＭp ，Ｍq とする。これに
より、中国剰余定理計算器４６０は中国剰余定理を用い
てＭp ，Ｍq より平文Ｍを計算し、平文Ｍとして出力す
る。
別子τp 、素数ｑに対する識別子τqとする。復号鍵検
索器４４０、４４１は、ｐ，ｑの復号鍵表記録部４７
０、４７１から復号鍵表を識別子τp ，τq により検索
し、復号鍵ｄp ，ｄq を得る。次に、第 1の楕円曲線乗
算器４５０、４５１は、楕円曲線 Ｅp （０，ｂp ）：ｙ2 ≡ｘ3 ＋ｂp （mod ｐ） Ｅq （０，ｂq ）：ｙ2 ≡ｘ3 ＋ｂq （mod ｑ） 上において、 ｄp ・Ｃ over Ｅp （０，ｂp ）， ｄq ・Ｃ over Ｅq （０，ｂq ） を計算し、各々の計算結果をＭp ，Ｍq とする。これに
より、中国剰余定理計算器４６０は中国剰余定理を用い
てＭp ，Ｍq より平文Ｍを計算し、平文Ｍとして出力す
る。
【００５９】なお、上記実施例の中の説明で用いられて
いる素数ｐ，ｑの桁数は、その積ｎ（＝ｐｑ）の素因数
分解の困難さを考慮して決められる。
いる素数ｐ，ｑの桁数は、その積ｎ（＝ｐｑ）の素因数
分解の困難さを考慮して決められる。
【００６０】
【発明の効果】上述のように本発明によれば、法ｎの素
因数ｐ，ｑに制限がないため、その素因数分解がより難
しくり、素数ｐ，ｑの大きさを同じにした場合に、ＫＭ
ＯＶ方式に比べてより安全である。これにより、安全な
公開鍵暗号方式を提供することができる。
因数ｐ，ｑに制限がないため、その素因数分解がより難
しくり、素数ｐ，ｑの大きさを同じにした場合に、ＫＭ
ＯＶ方式に比べてより安全である。これにより、安全な
公開鍵暗号方式を提供することができる。
【図１】本発明の原理構成図である。
【図２】本発明の一実施例のシステム構成図である。
【図３】本発明の一実施例の鍵生成装置の構成図であ
る。
る。
【図４】本発明の一実施例の復号鍵表生成装置を説明す
るための図である。
るための図である。
【図５】本発明の一実施例の暗号化装置の構成図であ
る。
る。
【図６】本発明の一実施例の復号装置の構成図である。
１，２，３ 復号鍵生成装置 １０ 公開ファイル装置 ２０ 鍵生成装置 ２１ 位数表生成手段 ２４ 復号鍵生成手段 ３０ 暗号化装置 ３１，４５ 楕円曲線乗算手段 ４０ 復号装置 ４１ 記憶手段 ４２ 係数計算手段 ４３ 識別子計算手段 ４４ 復号鍵検索手段 ４６ 中国剰余定理計算手段 ２４１ 素数生成器 ２４２，２４３ 位数表生成装置 ２４５ 復号鍵表生成装置 ４１０ 素数ｐ記憶部 ４１１ 素数ｑ記憶部 ４２０ 第１の係数計算器 ４２１ 第２の係数計算器 ４３０ 第１の識別子計算器 ４３１ 第２の識別子計算器 ４４０，４４１ 復号鍵検索器 ４５０ 第１の楕円曲線乗算器 ４５１ 第２の楕円曲線乗算器 ４６０ 中国剰余定理計算器
【手続補正書】
【提出日】平成５年５月７日
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正内容】
【特許請求の範囲】
Claims (1)
- 【請求項１】 受信者により５以上の任意の素数を選択
し、該素数に対応する公開鍵を登録する公開ファイル装
置と、 素数に対して楕円曲線ｙ2 ≡ｘ3 ＋ａｘ（mod ｎ）の位
数とパラメータとの関係を示す識別子と該位数の対応を
示す位数表を生成する位数表生成手段と、該素数と該位
数表生成手段により生成された該位数表から復号鍵を計
算し、該復号鍵と該位数表の識別子との対応を示す復号
鍵表を生成する復号鍵表生成手段とを含む復号表生成装
置とを有する鍵生成装置と、 平文と公開鍵が入力され、該平文を楕円曲線ｙ2 ≡ｘ3
＋ａｘ（mod ｎ）上で該公開鍵に基づいて乗算する楕円
曲線乗算手段を含み、暗号文を出力する暗号化装置と、 該素数と復号鍵表を予め記憶しておく記憶手段と、該暗
号化装置から取得した該暗号文と該素数から該楕円曲線
ｙ2 ≡ｘ3 ＋ａｘ（mod ｎ）のパラメータを計算する係
数計算手段と、該記憶手段に記憶されている該復号鍵表
より該楕円曲線ｙ2 ≡ｘ3 ＋ａｘ（mod ｎ）のパラメー
タに対応する復号鍵を検索する復号鍵検索手段と、該暗
号化装置から入力された該暗号文を該楕円曲線ｙ2 ≡ｘ
3 ＋ａｘ（mod ｎ）上で該復号鍵に基づいて乗算する楕
円曲線乗算手段と、該楕円曲線乗算手段により求められ
た値と該素数から平文を中国剰余定理に基づいて計算
し、出力する中国剰余定理計算手段とを含む復号装とを
有することを特徴とする楕円曲線に基づく公開鍵暗号方
式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5070436A JPH06282226A (ja) | 1993-03-29 | 1993-03-29 | 楕円曲線に基づく公開鍵暗号方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5070436A JPH06282226A (ja) | 1993-03-29 | 1993-03-29 | 楕円曲線に基づく公開鍵暗号方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH06282226A true JPH06282226A (ja) | 1994-10-07 |
Family
ID=13431439
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5070436A Pending JPH06282226A (ja) | 1993-03-29 | 1993-03-29 | 楕円曲線に基づく公開鍵暗号方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH06282226A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2004252433A (ja) * | 2003-01-28 | 2004-09-09 | Matsushita Electric Ind Co Ltd | 故障利用攻撃に対抗できる楕円べき倍演算装置及び情報セキュリティ装置 |
| US7023990B1 (en) | 1999-08-27 | 2006-04-04 | Nec Corporation | Secure parameter generating device and parameter generating method in algebraic curve crytography |
| CN110247771A (zh) * | 2019-06-21 | 2019-09-17 | 恒宝股份有限公司 | 一种智能卡及其曲线参数密钥的管理方法 |
-
1993
- 1993-03-29 JP JP5070436A patent/JPH06282226A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7023990B1 (en) | 1999-08-27 | 2006-04-04 | Nec Corporation | Secure parameter generating device and parameter generating method in algebraic curve crytography |
| JP2004252433A (ja) * | 2003-01-28 | 2004-09-09 | Matsushita Electric Ind Co Ltd | 故障利用攻撃に対抗できる楕円べき倍演算装置及び情報セキュリティ装置 |
| CN110247771A (zh) * | 2019-06-21 | 2019-09-17 | 恒宝股份有限公司 | 一种智能卡及其曲线参数密钥的管理方法 |
| CN110247771B (zh) * | 2019-06-21 | 2022-10-25 | 恒宝股份有限公司 | 一种智能卡及其曲线参数密钥的管理方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3862500B2 (ja) | 直接埋め込み方式による高速楕円曲線暗号化の方法と装置 | |
| Merkle | A certified digital signature | |
| US6263081B1 (en) | Elliptic curve calculation apparatus capable of calculating multiples at high speed | |
| KR101861089B1 (ko) | 근사 복소수 연산을 지원하는 복수 개의 메시지의 동형 암호화 방법 | |
| EP0596945A1 (en) | Digital signature algorithm | |
| JP3292107B2 (ja) | ２重ベクトル加算装置、２重ベクトル２倍装置及び２重ベクトル整数倍装置 | |
| CN114172651B (zh) | 一种sm9公钥加密算法、解密算法的gpu加速实现方法 | |
| JP4875686B2 (ja) | 楕円曲線上の有限体演算の加速方法 | |
| US6337909B1 (en) | Generation of session keys for El Gamal-like protocols from low hamming weight integers | |
| JP3616897B2 (ja) | モンゴメリ法による乗算剰余計算装置 | |
| JP3551853B2 (ja) | αＹａ＋βＸｂ＋１＝０という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置、生成方法、および記録媒体 | |
| JPH06282226A (ja) | 楕円曲線に基づく公開鍵暗号方式 | |
| US6901513B1 (en) | Process for generating a digital signature and process for checking the signature | |
| JP3123820B2 (ja) | 有限可換群における演算器 | |
| JP4598269B2 (ja) | 楕円曲線上の高速有限体演算 | |
| JP2000132095A (ja) | 暗号化方法、復号化方法、認証方法、暗号化装置、復号化装置、認証装置、認証文送信者装置、認証文受信者装置、暗号通信システム及び認証システム | |
| JP3278790B2 (ja) | 公開鍵暗号方法及び公開鍵暗号システム | |
| EP0854603B1 (en) | Generation of session parameters for el gamal-like protocols | |
| JP4462511B2 (ja) | エルガマル・ライクなプロトコルのためのセッション・パラメータ生成方法 | |
| Rao et al. | A novel modular multiplication algorithm and its application to RSA decryption | |
| CN119788264B (zh) | 适用于密文加密的全同态加密方法、系统、装置及介质 | |
| JPH0713484A (ja) | 楕円曲線に基づく鍵生成装置、暗号化装置及び復号化装置 | |
| JPH06308882A (ja) | 楕円曲線に基づく公開鍵暗号システム、その鍵生成装置、その暗号化装置及びその復号化装置 | |
| JPH0798563A (ja) | 楕円曲線による署名、認証及び秘密通信方式 | |
| JP2002215024A (ja) | ナップサック型公開鍵暗号システム、その公開鍵生成方法、その装置、そのプログラム、及びその記録媒体 |