JPH11258986A - 暗号化装置、復号化装置、暗号システムおよびそのプログラム記録媒体 - Google Patents
暗号化装置、復号化装置、暗号システムおよびそのプログラム記録媒体Info
- Publication number
- JPH11258986A JPH11258986A JP10065192A JP6519298A JPH11258986A JP H11258986 A JPH11258986 A JP H11258986A JP 10065192 A JP10065192 A JP 10065192A JP 6519298 A JP6519298 A JP 6519298A JP H11258986 A JPH11258986 A JP H11258986A
- Authority
- JP
- Japan
- Prior art keywords
- factor
- curve
- algebraic
- algebraic curve
- secret key
- 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)【要約】
【課題】 素因数分解の困難さと、代数曲線上の離散対
数問題の困難さの両方に根拠を置き、従来より安全性が
高い。 【解決手段】 素数ｐとｑの積ｎと、パラメータａ，ｂ
の楕円曲線Ｅ上の点Ｇと、正整数ｓの秘密鍵を生成し、
Ｅ上でｓ・Ｇmod ｎを演算して点Ｐを求め、ｎ，ａ，
Ｇ，Ｐを公開し、整数の乱数ｒを生成し（２１）、Ｅ上
でｒＧmod ｎ＝Ｃ1，ｒＰmod ｎ＝Ｃ2を演算し（２
３）、Ｃ2のｘ座標ｃ2Xと平文ｍの乗算をmod ｎで行
い、その結果ｃとＣ1を暗号出力とする。復号はｓＣ1mo
d ｎをＥ上で行ってＣ2を得、そのｘ座標ｃ2Xでｃを除
算することをmod ｎで行って平文ｍを得る。
数問題の困難さの両方に根拠を置き、従来より安全性が
高い。 【解決手段】 素数ｐとｑの積ｎと、パラメータａ，ｂ
の楕円曲線Ｅ上の点Ｇと、正整数ｓの秘密鍵を生成し、
Ｅ上でｓ・Ｇmod ｎを演算して点Ｐを求め、ｎ，ａ，
Ｇ，Ｐを公開し、整数の乱数ｒを生成し（２１）、Ｅ上
でｒＧmod ｎ＝Ｃ1，ｒＰmod ｎ＝Ｃ2を演算し（２
３）、Ｃ2のｘ座標ｃ2Xと平文ｍの乗算をmod ｎで行
い、その結果ｃとＣ1を暗号出力とする。復号はｓＣ1mo
d ｎをＥ上で行ってＣ2を得、そのｘ座標ｃ2Xでｃを除
算することをmod ｎで行って平文ｍを得る。
Description
【０００１】
【発明の属する技術分野】この発明は通信の機密を保護
する守秘機能と通信文の改ざん有無を確認する認証機能
を有した暗号化装置、復号化装置、暗号システム、その
プログラム記録媒体に関する。
する守秘機能と通信文の改ざん有無を確認する認証機能
を有した暗号化装置、復号化装置、暗号システム、その
プログラム記録媒体に関する。
【０００２】
【従来の技術】公開鍵暗号方式は鍵管理が容易である。
従来の公開鍵暗号として代表的なＲＳＡ暗号、ＫＭＯＶ
暗号、代数曲線型エルガマル（ＥｌＧａｍａｌ）暗号
（楕円曲線型ＥｌＧａｍａｌ暗号を含む）がある。ここ
で、ＲＳＡ暗号、ＫＭＯＶ暗号は大きな数の素因数分解
の困難さに根拠を置く暗号であり、代数曲線型ＥｌＧａ
ｍａｌ暗号は、大きな素数を法とした対応する代数曲線
上の離散対数問題の困難さに根拠を置く暗号である。し
かし、双方の困難さは厳密には未だ証明されておらず、
十分な安全性は保証されていない、という問題があっ
た。
従来の公開鍵暗号として代表的なＲＳＡ暗号、ＫＭＯＶ
暗号、代数曲線型エルガマル（ＥｌＧａｍａｌ）暗号
（楕円曲線型ＥｌＧａｍａｌ暗号を含む）がある。ここ
で、ＲＳＡ暗号、ＫＭＯＶ暗号は大きな数の素因数分解
の困難さに根拠を置く暗号であり、代数曲線型ＥｌＧａ
ｍａｌ暗号は、大きな素数を法とした対応する代数曲線
上の離散対数問題の困難さに根拠を置く暗号である。し
かし、双方の困難さは厳密には未だ証明されておらず、
十分な安全性は保証されていない、という問題があっ
た。
【０００３】
【発明が解決しようとする課題】この発明は従来の公開
鍵暗号方式のこの問題点を解決させ、機密保護と認証の
機能を有しながら、大きな数の素因数分解の困難さ及び
大きな素数を法とした代数曲線上の離散対数問題の困難
さの両方に根拠を置く、より安全な公開鍵暗号の装置及
びシステムを提供することを目的とする。
鍵暗号方式のこの問題点を解決させ、機密保護と認証の
機能を有しながら、大きな数の素因数分解の困難さ及び
大きな素数を法とした代数曲線上の離散対数問題の困難
さの両方に根拠を置く、より安全な公開鍵暗号の装置及
びシステムを提供することを目的とする。
【０００４】
【課題を解決するための手段】この発明によれば、代数
曲線上の因子Ｇをランダムに生成し、また正整数ｓを秘
密鍵として生成し、更に複数の素数を生成し、かつこれ
ら素数の積ｎを求め、代数曲線上でＧをｓ倍すること
を、ｎを法として行って因子Ｐとし、正整数ｒをランダ
ムに生成し、上記代数曲線上で因子ＧおよびＰをそれぞ
れｒ倍することを、ｎを法として行って因子Ｃ1 および
Ｃ2 を求め、そのＣ2 に整数の平文ｍを乗算してｃを求
め、このｃとＣ1 を暗号出力とする。
曲線上の因子Ｇをランダムに生成し、また正整数ｓを秘
密鍵として生成し、更に複数の素数を生成し、かつこれ
ら素数の積ｎを求め、代数曲線上でＧをｓ倍すること
を、ｎを法として行って因子Ｐとし、正整数ｒをランダ
ムに生成し、上記代数曲線上で因子ＧおよびＰをそれぞ
れｒ倍することを、ｎを法として行って因子Ｃ1 および
Ｃ2 を求め、そのＣ2 に整数の平文ｍを乗算してｃを求
め、このｃとＣ1 を暗号出力とする。
【０００５】復号化はＣ1 を秘密鍵ｓ倍することを上記
代数曲線上で、かつｎを法として行って、因子Ｃ2 を
得、この因子Ｃ2 でｃを、ｎを法とする除算を行って平
文ｍを得る。このように発明は、合成数ｎを法とする演
算を行うことに基づく、素因数分解の困難さと、代数曲
線上の離散対数問題の困難さの両方に根拠を置く暗号を
提供することを最も主要な特徴とする。
代数曲線上で、かつｎを法として行って、因子Ｃ2 を
得、この因子Ｃ2 でｃを、ｎを法とする除算を行って平
文ｍを得る。このように発明は、合成数ｎを法とする演
算を行うことに基づく、素因数分解の困難さと、代数曲
線上の離散対数問題の困難さの両方に根拠を置く暗号を
提供することを最も主要な特徴とする。
【０００６】従来の技術の代数曲線型ＥｌＧａｍａｌ暗
号では、許された法は素数のみであるが、この発明で
は、法として合成数のみを許すことにより、対応する代
数曲線上の離散対数問題の困難さだけでなく、素因数分
解の困難さも安全性の根拠に置くことを可能にしてい
る。
号では、許された法は素数のみであるが、この発明で
は、法として合成数のみを許すことにより、対応する代
数曲線上の離散対数問題の困難さだけでなく、素因数分
解の困難さも安全性の根拠に置くことを可能にしてい
る。
【０００７】
【発明の実施の形態】以下では、代数曲線（３次曲線や
楕円曲線を含む）の中でも、特に楕円曲線における実施
例を示す。以下に示す実施例は、楕円曲線に限らず、任
意の超楕円曲線に対してそのまま適用できるため、超楕
円曲線の場合も適宜参照する。積数ｇが１の代数曲線
は、楕円曲線と呼ばれ、一般にｙ2 ＝ｘ3 ＋ａｘ＋ｂで
表現される曲線である。種類が２以上の代数曲線は、超
楕円曲線と呼ばれ、一般にｙ2 ＋ｈ（ｘ）ｙ＝ｆ（ｘ）
（ここで、ｈ（ｘ）の次数はｇ以下で、ｆ（ｘ）の次数
は２ｇ＋１である）で表現される曲線である。超楕円曲
線上の点の形式和は因子と呼ばれ、この因子の集合は有
限可換群を形成する。他の代数曲線とは異なり、楕円曲
線上の因子は、その楕円曲線上の点と同一視できるた
め、以下では因子と呼ばず、点と呼ぶこととする。
楕円曲線を含む）の中でも、特に楕円曲線における実施
例を示す。以下に示す実施例は、楕円曲線に限らず、任
意の超楕円曲線に対してそのまま適用できるため、超楕
円曲線の場合も適宜参照する。積数ｇが１の代数曲線
は、楕円曲線と呼ばれ、一般にｙ2 ＝ｘ3 ＋ａｘ＋ｂで
表現される曲線である。種類が２以上の代数曲線は、超
楕円曲線と呼ばれ、一般にｙ2 ＋ｈ（ｘ）ｙ＝ｆ（ｘ）
（ここで、ｈ（ｘ）の次数はｇ以下で、ｆ（ｘ）の次数
は２ｇ＋１である）で表現される曲線である。超楕円曲
線上の点の形式和は因子と呼ばれ、この因子の集合は有
限可換群を形成する。他の代数曲線とは異なり、楕円曲
線上の因子は、その楕円曲線上の点と同一視できるた
め、以下では因子と呼ばず、点と呼ぶこととする。
【０００８】図１にこの発明による暗号装置中の鍵生成
手段の実施例を示す。データ読み込み回路１１に乱数生
成の種が入力される。この種から、素数発生回路１２
で、２や３でなく、また安全性を保証できる大きな、例
えば５１２又は１０２４ビットなどの素数ｐとｑとが求
められ、楕円曲線生成回路１３で、楕円曲線のパラメー
タａとｂとが求められ、点生成回路１４で、上記楕円曲
線上の点Ｇ＝（ｘ，ｙ）が求められ、秘密鍵発生回路１
５で、秘密鍵ｓが求められる。つまり、ｐ，ｑはランダ
ムに生成され、かつ、（ｐ−１）、（ｑ−１）が大きな
素因数をもつ、その素数ｐ及びｑとが演算器１６へ供給
され、合成数ｎ＝ｐ×ｑの演算が行なわれる。またａ，
ｂは４ａ3 ＋２７ｂ2 がｎと互いに素であるという条件
を満し、つまり楕円曲線である条件を満すランダムに選
んだ値であり、点Ｇは上記楕円曲線上のランダムに選ん
だ任意の点であり、秘密鍵ｓはランダムに選んだ正整数
である。楕円曲線のパラメータａ及び秘密鍵ｓ及び演算
器１６よりのｎとがメモリ１７へ記憶される。
手段の実施例を示す。データ読み込み回路１１に乱数生
成の種が入力される。この種から、素数発生回路１２
で、２や３でなく、また安全性を保証できる大きな、例
えば５１２又は１０２４ビットなどの素数ｐとｑとが求
められ、楕円曲線生成回路１３で、楕円曲線のパラメー
タａとｂとが求められ、点生成回路１４で、上記楕円曲
線上の点Ｇ＝（ｘ，ｙ）が求められ、秘密鍵発生回路１
５で、秘密鍵ｓが求められる。つまり、ｐ，ｑはランダ
ムに生成され、かつ、（ｐ−１）、（ｑ−１）が大きな
素因数をもつ、その素数ｐ及びｑとが演算器１６へ供給
され、合成数ｎ＝ｐ×ｑの演算が行なわれる。またａ，
ｂは４ａ3 ＋２７ｂ2 がｎと互いに素であるという条件
を満し、つまり楕円曲線である条件を満すランダムに選
んだ値であり、点Ｇは上記楕円曲線上のランダムに選ん
だ任意の点であり、秘密鍵ｓはランダムに選んだ正整数
である。楕円曲線のパラメータａ及び秘密鍵ｓ及び演算
器１６よりのｎとがメモリ１７へ記憶される。
【０００９】上記の点Ｇを因子Ｇに、上記楕円曲線のパ
ラメータａとｂを超楕円曲線のパラメータに書き換える
ことにより、超楕円曲線の場合にも容易に適用できる。
秘密鍵発生回路１５よりのｓと、楕円曲線生成回路１３
よりのａと、点生成回路１４よりのＧと、演算器１６よ
りのｎとが楕円加算回路１８へ供給される。この楕円加
算回路１８により、Ｐ＝ｓ・Ｇが計算される。
ラメータａとｂを超楕円曲線のパラメータに書き換える
ことにより、超楕円曲線の場合にも容易に適用できる。
秘密鍵発生回路１５よりのｓと、楕円曲線生成回路１３
よりのａと、点生成回路１４よりのＧと、演算器１６よ
りのｎとが楕円加算回路１８へ供給される。この楕円加
算回路１８により、Ｐ＝ｓ・Ｇが計算される。
【００１０】アフィン（ａｆｆｉｎｅ）座標では、楕円
曲線上の２点Ｑ1 ＝（ｘ1 ，ｙ1 ），Ｑ2 ＝（ｘ2 ，ｙ
2 ）が与えられた時、これらの２点の和Ｑ3 ＝Ｑ1 ＋Ｑ
2 は次式で与えられる。 Ｑ1 ≠Ｑ2 のとき ｘ3 ＝λ2 −ｘ1 −ｘ2 ｙ3 ＝λ（ｘ1 −ｘ3 ）−ｙ1 λ＝（ｙ2 −ｙ1 ）／（ｘ2 −ｘ1 ） Ｑ1 ＝Ｑ2 のとき ｘ3 ＝λ2 −２ｘ1 ｙ3 ＝λ（ｘ1 −ｘ3 ）−ｙ1 λ＝（３ｘ1 2＋ａ）／２ｙ1 楕円曲線が、体上ではなく、環上で定義されている時、
上記の演算では、加算が実行できない時がある。しか
し、その確率は極めて小さいため、実用上は、加算が実
行できない状況は起らない。
曲線上の２点Ｑ1 ＝（ｘ1 ，ｙ1 ），Ｑ2 ＝（ｘ2 ，ｙ
2 ）が与えられた時、これらの２点の和Ｑ3 ＝Ｑ1 ＋Ｑ
2 は次式で与えられる。 Ｑ1 ≠Ｑ2 のとき ｘ3 ＝λ2 −ｘ1 −ｘ2 ｙ3 ＝λ（ｘ1 −ｘ3 ）−ｙ1 λ＝（ｙ2 −ｙ1 ）／（ｘ2 −ｘ1 ） Ｑ1 ＝Ｑ2 のとき ｘ3 ＝λ2 −２ｘ1 ｙ3 ＝λ（ｘ1 −ｘ3 ）−ｙ1 λ＝（３ｘ1 2＋ａ）／２ｙ1 楕円曲線が、体上ではなく、環上で定義されている時、
上記の演算では、加算が実行できない時がある。しか
し、その確率は極めて小さいため、実用上は、加算が実
行できない状況は起らない。
【００１１】この加算公式は斉次座標系でも同様に定義
できる。これらの加算公式を繰り返し適用して、ある点
Ｑの整数倍の点ｅ・Ｑを求めることができる。つまり、
５・Ｑは（Ｑ＋Ｑ＝２・Ｑ）と（２Ｑ＋２Ｑ＝４・Ｑ）
と（４Ｑ＋Ｑ＝５・Ｑ）とにより求める。有限体上の超
楕円曲線上で作られる群の群演算は、上記のアルゴリズ
ムではなく、Ｃａｎｔｏｒのアルゴリズム［Ｃａｎｔｏ
ｒ，Ｄ：Ｃｏｍｐｕｔｉｎｇ ｉｎ ｔｈｅ Ｊａｃｏ
ｂｉａｎ ｏｆ ａ Ｈｙｐｅｒｅｌｌｉｐｔｉｃ Ｃ
ｕｒｖｅ，Ｍａｔｈ．Ｃｏｍｐ．，４８，ｐｐ．９５−
１０１（１９８７）］により効率的に実行される。
できる。これらの加算公式を繰り返し適用して、ある点
Ｑの整数倍の点ｅ・Ｑを求めることができる。つまり、
５・Ｑは（Ｑ＋Ｑ＝２・Ｑ）と（２Ｑ＋２Ｑ＝４・Ｑ）
と（４Ｑ＋Ｑ＝５・Ｑ）とにより求める。有限体上の超
楕円曲線上で作られる群の群演算は、上記のアルゴリズ
ムではなく、Ｃａｎｔｏｒのアルゴリズム［Ｃａｎｔｏ
ｒ，Ｄ：Ｃｏｍｐｕｔｉｎｇ ｉｎ ｔｈｅ Ｊａｃｏ
ｂｉａｎ ｏｆ ａ Ｈｙｐｅｒｅｌｌｉｐｔｉｃ Ｃ
ｕｒｖｅ，Ｍａｔｈ．Ｃｏｍｐ．，４８，ｐｐ．９５−
１０１（１９８７）］により効率的に実行される。
【００１２】従って、ｓ・Ｇは、例えば前記の加算公式
を繰り返すことにより求められる。また、この演算は
（mod ｎ）で行ない、つまり加算値がｎを越えると、加
算値をｎで割った余りを加算結果として残す。ｎとａと
Ｇ＝（ｘ，ｙ）とＰとが公開鍵とされ、ｓは秘密鍵とさ
れる。つまり、素数発生回路１２及び楕円曲線生成回路
１３及び点生成回路１４及び秘密鍵発生回路１５及び演
算器１６及び楕円加算回路１８は鍵生成手段１９を構成
している。
を繰り返すことにより求められる。また、この演算は
（mod ｎ）で行ない、つまり加算値がｎを越えると、加
算値をｎで割った余りを加算結果として残す。ｎとａと
Ｇ＝（ｘ，ｙ）とＰとが公開鍵とされ、ｓは秘密鍵とさ
れる。つまり、素数発生回路１２及び楕円曲線生成回路
１３及び点生成回路１４及び秘密鍵発生回路１５及び演
算器１６及び楕円加算回路１８は鍵生成手段１９を構成
している。
【００１３】図２にこの発明中の暗号化手段の実施例を
示す。データ読み込み回路２０よりの乱数生成の種か
ら、乱数発生回路２１で乱数ｒが発生される。この乱数
ｒとメモリ２２中の相手方の公開鍵ｎとａとＧとＰとが
楕円加算回路２３へ供給される。この楕円加算回路２３
により、Ｃ1 ＝ｒ・Ｇ及びＣ2 ＝ｒ・Ｐ＝（ｃ2X，
ｃ2Y）とが計算される。
示す。データ読み込み回路２０よりの乱数生成の種か
ら、乱数発生回路２１で乱数ｒが発生される。この乱数
ｒとメモリ２２中の相手方の公開鍵ｎとａとＧとＰとが
楕円加算回路２３へ供給される。この楕円加算回路２３
により、Ｃ1 ＝ｒ・Ｇ及びＣ2 ＝ｒ・Ｐ＝（ｃ2X，
ｃ2Y）とが計算される。
【００１４】この楕円曲線上の点Ｃ2 のｘ座標ｃ2Xとデ
ータ読み込み回路２０よりの平文ｍとが演算器２４に供
給され、積ｃ＝ｍ×ｃ2Xが演算される。点Ｃ1 と積数ｃ
との対が暗号文となる。つまり、乱数発生回路２１及び
メモリ２２及び楕円加算回路２３及び演算器２４は暗号
化手段２５を構成している。このようにして暗号化手段
２５で暗号化された点と整数の対（Ｃ1 ，ｃ）（暗号
文）はデータ送信回路２６により相手方へ送信される。
ータ読み込み回路２０よりの平文ｍとが演算器２４に供
給され、積ｃ＝ｍ×ｃ2Xが演算される。点Ｃ1 と積数ｃ
との対が暗号文となる。つまり、乱数発生回路２１及び
メモリ２２及び楕円加算回路２３及び演算器２４は暗号
化手段２５を構成している。このようにして暗号化手段
２５で暗号化された点と整数の対（Ｃ1 ，ｃ）（暗号
文）はデータ送信回路２６により相手方へ送信される。
【００１５】図３にこの発明中の復号化手段の実施例を
示す。データ受信回路３１で、相手方より送られた楕円
曲線上の点と整数値の対である暗号文（Ｃ1 ，ｃ）を受
信する。楕円加算回路３２により、データ受信回路３１
よりの楕円曲線上の点Ｃ1 とメモリ３３よりの秘密鍵ｓ
との乗算がメモリ３３に記憶されている自己の楕円曲線
上で演算され、ｓ・Ｃ1 ＝（ｃ2X，ｃ2Y）、（つまりｓ
・Ｃ1 ＝ｓ・ｒ・Ｇ＝ｒ・Ｐ＝Ｃ2 ＝（ｃ2X，ｃ2Y））
が求められる。データ受信回路３１よりの整数値ｃ及び
上記楕円曲線上の点ｓ・Ｃ1 のｘ座標ｃ2Xが演算器３４
へ供給される。この演算器３４により、整数値ｃをｃ2X
で割ることにより復号化され、平文ｍが得られる。つま
り、演算器３４及びメモリ３３及び楕円加算回路３２は
復号化手段３５を構成している。
示す。データ受信回路３１で、相手方より送られた楕円
曲線上の点と整数値の対である暗号文（Ｃ1 ，ｃ）を受
信する。楕円加算回路３２により、データ受信回路３１
よりの楕円曲線上の点Ｃ1 とメモリ３３よりの秘密鍵ｓ
との乗算がメモリ３３に記憶されている自己の楕円曲線
上で演算され、ｓ・Ｃ1 ＝（ｃ2X，ｃ2Y）、（つまりｓ
・Ｃ1 ＝ｓ・ｒ・Ｇ＝ｒ・Ｐ＝Ｃ2 ＝（ｃ2X，ｃ2Y））
が求められる。データ受信回路３１よりの整数値ｃ及び
上記楕円曲線上の点ｓ・Ｃ1 のｘ座標ｃ2Xが演算器３４
へ供給される。この演算器３４により、整数値ｃをｃ2X
で割ることにより復号化され、平文ｍが得られる。つま
り、演算器３４及びメモリ３３及び楕円加算回路３２は
復号化手段３５を構成している。
【００１６】図１〜図３は何れも、コンピュータによる
プログラムの読出し、解読実行により動作させることが
でき、その場合ＣＰＵを主体とする制御部３６，３７，
３８がそれぞれ設けられる。図４にこの発明による暗号
装置の実施例を示す。鍵生成手段１９及び暗号化手段２
５及び復号化手段３５は暗号装置４１を構成している。
ただし、鍵生成手段１９及び暗号化手段２５及び復号化
手段３５でデータ読み込み回路１１，２０、演算器１
６，２４，３４またメモリ１７，２２，３３、更に楕円
加算回路１８，２３，３２、制御部３６，３７，３８は
それぞれ共用される。暗号化装置専用の場合は図２の構
成のみでよく、復号化装置専用の場合は鍵生成手段１９
と復号化手段３２で構成される。
プログラムの読出し、解読実行により動作させることが
でき、その場合ＣＰＵを主体とする制御部３６，３７，
３８がそれぞれ設けられる。図４にこの発明による暗号
装置の実施例を示す。鍵生成手段１９及び暗号化手段２
５及び復号化手段３５は暗号装置４１を構成している。
ただし、鍵生成手段１９及び暗号化手段２５及び復号化
手段３５でデータ読み込み回路１１，２０、演算器１
６，２４，３４またメモリ１７，２２，３３、更に楕円
加算回路１８，２３，３２、制御部３６，３７，３８は
それぞれ共用される。暗号化装置専用の場合は図２の構
成のみでよく、復号化装置専用の場合は鍵生成手段１９
と復号化手段３２で構成される。
【００１７】次に、この発明による暗号システムの実施
例を図５を参照して説明する。特に、守秘通信の場合に
ついて説明する。利用者Ｕ１（送信者）の暗号装置５１
と利用者Ｕ２（受信者）の暗号装置５２とが通信線５３
で接続され、暗号装置５１，５２とそれぞれセンタ装置
５４とが通信線５５，５６をそれぞれ通して接続されて
いる。暗号装置５１，５２の構成はそれぞれ、図４で示
した暗号装置４１及びデータ読み込み回路１１及びデー
タ送信回路２６及びデータ受信回路３１及び送受信器５
７により構成されている。利用者Ｕ１の暗号装置５１の
鍵生成手段１９で生成された公開鍵ｎ1 及びａ1 及びＧ
1 及びＰ1 は送受信器５７より通信線５５を通じてセン
タ装置５４内の鍵ファイル５８に利用者Ｕ１の鍵として
登録される。同様に利用者Ｕ２の暗号装置５２の鍵生成
手段１９で生成された公開鍵ｎ2及びａ2 及びＧ2 及び
Ｐ2 は送受信器５７より通信線５６を通じてセンタ装置
５４内の鍵ファイル５８に利用者Ｕ２の鍵として登録さ
れる。
例を図５を参照して説明する。特に、守秘通信の場合に
ついて説明する。利用者Ｕ１（送信者）の暗号装置５１
と利用者Ｕ２（受信者）の暗号装置５２とが通信線５３
で接続され、暗号装置５１，５２とそれぞれセンタ装置
５４とが通信線５５，５６をそれぞれ通して接続されて
いる。暗号装置５１，５２の構成はそれぞれ、図４で示
した暗号装置４１及びデータ読み込み回路１１及びデー
タ送信回路２６及びデータ受信回路３１及び送受信器５
７により構成されている。利用者Ｕ１の暗号装置５１の
鍵生成手段１９で生成された公開鍵ｎ1 及びａ1 及びＧ
1 及びＰ1 は送受信器５７より通信線５５を通じてセン
タ装置５４内の鍵ファイル５８に利用者Ｕ１の鍵として
登録される。同様に利用者Ｕ２の暗号装置５２の鍵生成
手段１９で生成された公開鍵ｎ2及びａ2 及びＧ2 及び
Ｐ2 は送受信器５７より通信線５６を通じてセンタ装置
５４内の鍵ファイル５８に利用者Ｕ２の鍵として登録さ
れる。
【００１８】送信者Ｕ１が受信者Ｕ２へ通信文を暗号化
して送信する場合は、送信者Ｕ１は通信線５５を通じ
て、センタ装置５４の鍵ファイル５８から、受信者Ｕ２
の公開鍵ｎ2 及びａ2 及びＧ2 及びＰ2 を受けとり、送
信者Ｕ１の暗号装置５１のメモリ２２へ記憶させる。送
信者Ｕ２は送りたい平文ｍから暗号化手段２５により、
送信すべき暗号文（Ｃ1 ，ｃ）を前述と同様に暗号装置
５１で生成する。楕円曲線上の点と整数値の対から構成
される暗号文（Ｃ１，ｃ）をデータ送信回路２６を通じ
て、通信線５３へ送出する。
して送信する場合は、送信者Ｕ１は通信線５５を通じ
て、センタ装置５４の鍵ファイル５８から、受信者Ｕ２
の公開鍵ｎ2 及びａ2 及びＧ2 及びＰ2 を受けとり、送
信者Ｕ１の暗号装置５１のメモリ２２へ記憶させる。送
信者Ｕ２は送りたい平文ｍから暗号化手段２５により、
送信すべき暗号文（Ｃ1 ，ｃ）を前述と同様に暗号装置
５１で生成する。楕円曲線上の点と整数値の対から構成
される暗号文（Ｃ１，ｃ）をデータ送信回路２６を通じ
て、通信線５３へ送出する。
【００１９】受信者Ｕ２の暗号装置５２では、通信線５
３からデータ受信回路３１に受信された暗号文と受信者
Ｕ２のメモリ３３よりの自己の秘密鍵ｓ2 とから、受信
者Ｕ２の復号化手段３５により平文ｍが復号される。利
用者Ｕ２から利用者Ｕ１への暗号通信も同様に行なわれ
る。この場合鍵は、公開鍵ｎ1 及びａ1 及びＧ1 及びＰ
1 ，秘密鍵ｓ1 が使われる。別の利用者Ｕ３から別の利
用者Ｕ４への暗号通信も同様に行なわれる。
３からデータ受信回路３１に受信された暗号文と受信者
Ｕ２のメモリ３３よりの自己の秘密鍵ｓ2 とから、受信
者Ｕ２の復号化手段３５により平文ｍが復号される。利
用者Ｕ２から利用者Ｕ１への暗号通信も同様に行なわれ
る。この場合鍵は、公開鍵ｎ1 及びａ1 及びＧ1 及びＰ
1 ，秘密鍵ｓ1 が使われる。別の利用者Ｕ３から別の利
用者Ｕ４への暗号通信も同様に行なわれる。
【００２０】
【発明の効果】以上述べたこの発明は、次の長所を持っ
ている。 （１）ＲＳＡ暗号及び代数曲線型ＥｌＧａｍａｌ暗号よ
りも高い安全性を持つ。 従来のＲＳＡ暗号は、大きな数の素因数分解が困難なこ
とに安全性の根拠を置いている。従来の代数曲線型Ｅｌ
Ｇａｍａｌ暗号は、大きな素数を法とした対応する代数
曲線上の離散対数問題が困難なことに安全性の根拠を置
いている。しかし、この発明の暗号は、合成数ｎを法と
する演算により、大きな数の素因数分解が困難なこと及
び大きな素数を法とした代数曲線上の離散対数問題が困
難なことの両方に安全性の根拠を置いている。そのた
め、従来の２つの暗号と比べて、解読は困難である。
ている。 （１）ＲＳＡ暗号及び代数曲線型ＥｌＧａｍａｌ暗号よ
りも高い安全性を持つ。 従来のＲＳＡ暗号は、大きな数の素因数分解が困難なこ
とに安全性の根拠を置いている。従来の代数曲線型Ｅｌ
Ｇａｍａｌ暗号は、大きな素数を法とした対応する代数
曲線上の離散対数問題が困難なことに安全性の根拠を置
いている。しかし、この発明の暗号は、合成数ｎを法と
する演算により、大きな数の素因数分解が困難なこと及
び大きな素数を法とした代数曲線上の離散対数問題が困
難なことの両方に安全性の根拠を置いている。そのた
め、従来の２つの暗号と比べて、解読は困難である。
【図１】この発明による暗号装置における鍵生成手段の
実施例の機能的構成を示すブロック図。
実施例の機能的構成を示すブロック図。
【図２】この発明による暗号装置における暗号化手段の
実施例の機能的構成を示すブロック図。
実施例の機能的構成を示すブロック図。
【図３】この発明による暗号装置における復号化手段の
実施例の機能的構成を示すブロック図。
実施例の機能的構成を示すブロック図。
【図４】この発明による暗号装置の実施例の機能的構成
を示すブロック図。
を示すブロック図。
【図５】この発明による暗号システムの実施例の機能的
構成を示すブロック図。
構成を示すブロック図。
Claims (12)
- 【請求項１】 複数の素数の積であるｎ2 と、代数曲線
のパラメータと、上記代数曲線上の因子Ｇ2 （３次曲線
や楕円曲線の場合は点Ｇ、以下同様）と、その因子Ｇ2
及び正整数の秘密鍵ｓ2 倍することを上記第２代数曲線
上でｎ2 を法として行って得られた因子Ｐ2 とを公開鍵
として記憶する記憶手段と、 ランダムに整数ｒを生成する手段と、 上記因子Ｇ2 およびＰ2 をそれぞれ上記整数ｒ倍するこ
とを、上記第２代数曲線上でｎ2 を法として演算して因
子Ｃ１1 およびＣ２1 を求める手段と、 平文ｍ1 と上記因子Ｃ２1 との積を、ｎ2 を法として演
算して結果ｃ1 を得る手段と、 上記Ｃ１1 とｃ1 を暗号出力として出力する手段と、 上記各手段に対する順次制御、上記記憶手段に対する読
出し、書込みなどを行う制御手段とを具備する暗号化装
置。 - 【請求項２】 上記代数曲線は楕円曲線であって、 上記素数は２又は３でない値であり、 上記パラメータは４×ａ3 ＋２７×ｂ2 がｎと互いに素
であるという条件を満すａ，ｂであり、そのａが上記記
憶手段に記憶され、 上記ｍとＣ２1 の乗算は、Ｃ２1 の座標（ｃ2X，ｃ2Y）
のｘ座標ｃ2Xとの乗算であることを特徴とする請求項１
記載の暗号化装置。 - 【請求項３】 複数の素数を生成する手段と、複数の素
数の積をｎ1 を求める手段と、第１代数曲線上の因子Ｇ
1 をランダムに生成する手段と、ランダムな正の整数を
秘密鍵ｓ1 として生成する手段と、因子Ｇ1 を秘密鍵ｓ
1 倍とすることを、上記第１代数曲線上でｎ1 を法とし
て演算して因子Ｐ1 を得る手段とを有する鍵生成手段を
備え、 上記記憶手段には、複数の素数の積であるｎ1 、第１代
数曲線のパラメータ、 正整数の秘密鍵ｓ1 も記憶され、 上記第１代数曲線上の因子Ｃ１2 と、整数値ｃとを暗号
入力として受信する手段と、上記Ｃ１2 を上記ｓ1 倍す
ることを上記第１代数曲線上でｎ1 を法として演算して
因子Ｃ２2 を得る手段と、上記受信したｃ2 を上記Ｃ２
2 で、ｎを法とする割算を行って平分ｍ2 を得る手段と
を有する復号化手段を備えることを特徴とする請求項１
又は２記載の暗号化装置。 - 【請求項４】 複数の素数の積であるｎと、代数曲線の
パラメータと、正整数の秘密鍵ｓとを記憶する記憶手段
と、 上記代数曲線上の因子Ｃ１と、整数値ｃとを暗号入力と
して受信する手段と、 上記Ｃ１を上記秘密鍵ｓ倍することを上記代数曲線上で
ｎを法として演算して因子Ｃ２を得る手段と、 上記ｃを上記因子Ｃ2 でｎを法とする割算を行って平文
ｍを得る手段と、 上記各手段に対する順次制御、上記記憶手段に対する読
出し書込みなどを行う制御手段とを具備する復号化装
置。 - 【請求項５】 上記代数曲線は楕円曲線であって、 上記素数は２又は３でない値であり、 上記パラメータは４×ａ3 ＋２７×ｂ2 がｎと互いに素
であるという条件を満すａ，ｂであり、そのａが上記記
憶手段に記憶され、 上記ｃのＣ2 による除算は、Ｃ2 の座標（ｃ2X，ｃ2Y）
のｘ座標ｃ2Xで割算することであることを特徴とする請
求項４記載の復号化装置。 - 【請求項６】 複数の素数を生成する手段と、 上記複数の素数の積を上記ｎとして求める手段と、 上記代数曲線上の因子Ｇをランダムに生成する手段と、 上記秘密鍵ｓをランダムに生成する手段と、 上記因子Ｇを上記秘密鍵ｓ倍することを、上記代数曲線
上でｎを法として演算して因子Ｐを得る手段と、 よりなる鍵生成手段を備えることを特徴とする請求項４
又は５記載の復号化装置。 - 【請求項７】 請求項３記載の暗号化装置で構成された
第１，第２暗号装置が通信回線で接続され、 上記第１暗号装置は上記第２暗号装置の鍵生成手段によ
り生成された公開鍵を取得する手段と、 上記第１暗号装置は上記取得した公開鍵を用いて暗号化
装置により平文ｍを暗号化して暗号Ｃ1 ，ｃを上記通信
回線で上記第２暗号装置へ送信する手段と、 上記第２暗号装置は上記送信された暗号Ｃ1 ，ｃを受信
して、復号化手段で、上記鍵生成手段で生成された秘密
鍵を用いて復号化して平文ｍを得る手段を具備すること
を特徴とする暗号システム。 - 【請求項８】 入力された平文ｍを、コンピュータによ
りプログラムを読出し、解読実行することにより暗号化
して出力する暗号化装置に用いられ、上記プログラムを
記録した記録媒体であって、 ランダムに整数ｒを生成する処理と、 代数曲線上の因子である公開鍵ＧおよびＰ、複数の素数
の積である公開鍵ｎと上記代数曲線を規定するパラメー
タとを記憶手段から読み出す処理と、 上記読み出された公開鍵ＧおよびＰをそれぞれ整数ｒ倍
することを、上記代数曲線上で、ｎを法として演算して
因子Ｃ１およびＣ２を求める処理と、 上記因子Ｃ１を一時蓄える処理と、 上記平文ｍと上記因子Ｃ２との積を、ｎを法として演算
して結果ｃを得る処理と、 上記Ｃ1 とｃを暗号出力として出力する処理とを実行さ
せる上記プログラムを記録した記録媒体。 - 【請求項９】 上記代数曲線は楕円曲線であって、 上記素数は２又は３でない値であり、 上記パラメータ４×ａ3 ＋２７×ｂ2 がｎと互いに素で
あるという条件を満すａ，ｂであり、 上記ｍとＣ2 の乗算は、Ｃ2 の座標（ｃ2X，ｃ2Y）のｘ
座標ｃ2Xとの乗算であることを特徴とする請求項８記載
の記録媒体。 - 【請求項１０】 代数曲線上の因子Ｃ１と、整数ｃとを
暗号入力して入力され、コンピュータによりプログラム
を読出し、解読実行することにより復号化して平文ｍを
得る復号化装置に用いられ、上記プログラムを記録した
記録媒体であって、 上記暗号Ｃ１，ｃを受信する処理と、 その受信されたＣ１とｃを記憶手段に一時格納する処理
と、記憶手段より正の整数の秘密鍵ｓと上記Ｃ1 と、複
数の素数の積である公開鍵ｎと、上記代数曲線を規定す
るパラメータとを読出す処理と、上記読出されたＣ１を
ｓ倍することを上記代数曲線上で、ｎを法として演算し
て因子Ｃ２を得る処理と、 上記受信されたｃを読出す処理と、 上記読出されたｃを上記因子Ｃ２でｎを法とする割算を
行って平文ｍを得る処理と、 を実行させる上記プログラムを記録した記録媒体。 - 【請求項１１】 上記代数曲線は楕円曲線であって、 上記素数は２又は３でない値であり、 上記パラメータは４×ａ3 ＋２７×ｂ2 がｎと互いに素
であるという条件を満すａ，ｂであり、 上記ｃのＣ2 による除算は、Ｃ2 の座標（ｃ2X，ｃ2Y）
のｘ座標ｃ2Xで割算することであることを特徴とする請
求項１１記載の記録媒体。 - 【請求項１２】 複数の素数を生成する処理と、 上記複数の素数の積を上記ｎとして求める処理と、 上記代数曲線上の因子Ｇをランダムに生成する処理と、 上記秘密鍵ｓをランダムに生成する処理と、 上記因子Ｇを上記秘密鍵ｓ倍とすることを、上記代数曲
線上でｎを法として演算して因子Ｐを得る処理と、 を実行させることを上記プログラムが含むことを特徴と
する請求項１２記載の記録媒体。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10065192A JPH11258986A (ja) | 1998-03-16 | 1998-03-16 | 暗号化装置、復号化装置、暗号システムおよびそのプログラム記録媒体 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10065192A JPH11258986A (ja) | 1998-03-16 | 1998-03-16 | 暗号化装置、復号化装置、暗号システムおよびそのプログラム記録媒体 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11258986A true JPH11258986A (ja) | 1999-09-24 |
Family
ID=13279821
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10065192A Pending JPH11258986A (ja) | 1998-03-16 | 1998-03-16 | 暗号化装置、復号化装置、暗号システムおよびそのプログラム記録媒体 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH11258986A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20120140921A1 (en) * | 2010-12-01 | 2012-06-07 | King Fahd University Of Petroleum And Minerals | Rsa-analogous xz-elliptic curve cryptography system and method |
| CN117811737A (zh) * | 2023-12-29 | 2024-04-02 | 北京海泰方圆科技股份有限公司 | 一种数据处理方法、装置及电子设备 |
-
1998
- 1998-03-16 JP JP10065192A patent/JPH11258986A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20120140921A1 (en) * | 2010-12-01 | 2012-06-07 | King Fahd University Of Petroleum And Minerals | Rsa-analogous xz-elliptic curve cryptography system and method |
| CN117811737A (zh) * | 2023-12-29 | 2024-04-02 | 北京海泰方圆科技股份有限公司 | 一种数据处理方法、装置及电子设备 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN1326351C (zh) | 有限域离散对数密码系统的割圆多项式结构 | |
| US8429408B2 (en) | Masking the output of random number generators in key generation protocols | |
| Kapoor et al. | Elliptic curve cryptography | |
| CA2235359C (en) | Implicit certificate scheme with ca chaining | |
| US9571274B2 (en) | Key agreement protocol | |
| JP4137385B2 (ja) | 公開鍵および秘密鍵による暗号化方法 | |
| EP0936776A2 (en) | A network system using a threshold secret sharing method | |
| US8510789B2 (en) | Data output method, system and apparatus | |
| CN114257402B (zh) | 加密算法确定方法、装置、计算机设备和存储介质 | |
| CN100388663C (zh) | 用于检测一个键对和用于产生rsa键的方法和装置 | |
| JPH11317734A (ja) | デ―タの暗号化復号化方法および、それを用いたネットワ―クシステム | |
| US20160352689A1 (en) | Key agreement protocol | |
| JP3402441B2 (ja) | 公開鍵暗号化装置、公開鍵暗号復号装置及び復号プログラム記録媒体 | |
| JP6294882B2 (ja) | 鍵保管装置、鍵保管方法、及びそのプログラム | |
| CA2742530C (en) | Masking the output of random number generators in key generation protocols | |
| JP4563037B2 (ja) | 暗号化装置および復号化装置、並びにこれらを備えた暗号システム、暗号化方法および復号化方法 | |
| WO2016187690A1 (en) | Key agreement protocol | |
| JPH11258986A (ja) | 暗号化装置、復号化装置、暗号システムおよびそのプログラム記録媒体 | |
| JP3706398B2 (ja) | 楕円曲線による署名、認証及び秘密通信方式 | |
| JP2624634B2 (ja) | 暗号装置および復号化装置および暗号・復号化装置および暗号システム | |
| US20050123131A1 (en) | Cryptographic system comprising an encryption and decryption system and a key escrow system, and the associated equipment and devices | |
| JP4230162B2 (ja) | 公開鍵暗号通信方法 | |
| JPH1155244A (ja) | 鍵回復方法および装置 | |
| JPH08102734A (ja) | 公開鍵暗号方法及び公開鍵暗号システム | |
| JP2004139125A (ja) | 楕円曲線による署名、認証及び秘密通信方式 |