JPH0756506A - 楕円曲線に基づく暗号の鍵生成装置 - Google Patents

Abstract

(57)【要約】 【目的】 鍵の生成に必要とするｐ＝ｕ² −ｕｖ＋ｖ²
を満たす整数ｕ，ｖを複素整数の演算を行うことなく求
め、加減乗除算の回数を削減し、鍵生成時間を短かくす
る。 【構成】 素数ｐを記憶部２５に記憶し、ｋ² ≡ｐ−３
（ｍｏｄｐ）かつｋ＜ｐ／２をみたす整数ｋを記憶部２
６に記憶し、平方根計算器２７で√ｐを超えない最大の
整数ｗを求めて記憶部２８に記憶する。記憶部２６から
読出した値をｔとし、記憶部２８の値ｗと比較器３１で
比較する。記憶部２５，２６から読出した値をそれぞれ
ｓ，ｔとして剰余計算器２９でｒ＝ｓｍｏｄｔの演算を
行い、そのｔ，ｒをそれぞれ、記憶部２５，２６に記憶
して、これらを読出して剰余計算器２９へ供給すること
をｔ＜ｗとなるまで繰返す。ｔ＜ｗとなった時のｔを用
いて√｛（ｐ−ｔ² ）／３｝＝ｍを計算し、ｕ＝ｔ＋
ｍ，ｖ＝２ｍを求める。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は楕円曲線に基づく暗号
方式に用いられる暗号化鍵及び復号化鍵を生成する装置
に関する。

【０００２】

【従来の技術】まず、楕円曲線に関する記号の説明をす
る。素数ｐと係数ａ，ｂに対し、ｙ²≡ｘ³ ＋ａｘ＋ｂ
（ｍｏｄｐ）を満たす点（ｘ，ｙ）の集合に無限遠点Ｏ
を加えた集合を楕円曲線Ｅ_p （ａ，ｂ）と呼ぶ。Ｅ
_p （ａ，ｂ）は有限群をなし、その位数を＃Ｅ_p （ａ，
ｂ）と書く。楕円曲線Ｅ_p （ａ，ｂ）を暗号に利用する
際、位数＃Ｅ_p （ａ，ｂ）は鍵生成に利用される。

【０００３】楕円曲線に基づく暗号方式を簡単に述べ
る。（詳細は、Ｈ．Ｋｕｗａｋａｄｏａｎｄ Ｋ．Ｋｏ
ｙａｍａ，“Ａｎ ｅｘｔｅｎｓｉｏｎ ｏｆ ｅｌｌ
ｉｐｔｉｃ ｃｕｒｖｅ ｃｒｙｐｔｏｓｙｓｔｅｍｓ
ｏｖｅｒ ａ ｒｉｎｇＺ_n ”，Ｔｅｃｈ．Ｒｅｐ．
ｏｆ ＩＥＩＣＥ，ＩＳＥＣ９３−５，（１９９３) に
示されている。）ｐ≡１（ｍｏｄ３) をみたす素数ｐを
パラメータとしてもつ楕円曲線Ｅ_p （０，ｂ）の位数＃
Ｅ_p （０，ｂ）は、次のように表現できる。

【０００４】 ここで、ｕとｖは ｐ＝ｕ² −ｕｖ＋ｖ² （１) をみたす整数である。ｑ≡１（ｍｏｄ３) をみたし、か
つｐとは異なる素数ｑに対しても、 ｑ＝ｕ′² −ｕ′ｖ′＋ｖ′² となる。ｐ＋１±（２ｕ−ｖ）とｐ＋１±（−ｕ−ｖ）
とｐ＋１±（−ｕ＋２ｖ）とｑ＋１±（２ｕ′−ｖ′）
とｑ＋１±（−ｕ′−ｖ′）とｑ＋１±（−ｕ′＋２
ｖ′）の最小公倍数をｎ₀ とする。このとき暗号化鍵ｅ
は、ｎ₀ と互いに素な整数とし、復号化鍵ｄは、 ｅ・ｄ≡１（ｍｏｄｎ₀ ） をみたす整数である。平文Ｍ＝（ｍ_x ，ｍ_y ）∈Ｅ
_pq（０，ｂ）に対して、楕円曲線Ｅ_pq（０，ｂ）上でＭ
をｅ倍することが暗号化であり、そのｅ倍して得られた
点Ｃ＝（ｃ_x ，ｃ_y ）が暗号文である。暗号文Ｃ＝（ｃ
_x ，ｃ_y ）∈Ｅ_pq（０，ｂ）に対して、楕円曲線Ｅ
_pq（０，ｂ）上でＣをｄ倍することが復号化であり、そ
のｄ倍して得られた点Ｍ＝（ｍ_x ，ｍ_y ）が平文であ
る。

【０００５】暗号化鍵ｅと復号化鍵ｄを計算するために
は、式（１) をみたすｕとｖを求める必要がある。式
（１) をみたすｕとｖを求める従来の計算方式は、“初
等整数論講義”（高木貞治著，共立出版）に記載されて
いる。この従来の計算方法を簡単に説明する。素数ｐと
ｋ² ≡ｐ−３（ｍｏｄｐ）をみたす整数ｋに対して、ｐ
とｋ−１−２ｗの最大公約数を計算すると、ｕ＋ｖｗが
得られる。ここで、ｗ＝（−１＋√（−３) ）／２であ
る。ｐとｋ−１−２ｗの最大公約数を計算するために
は、複素整数の加減乗除算を行なわなければならない。
複素整数α＝ａ₁ ＋ｂ₁ ｗとβ＝ａ₂ ＋ｂ₂ ｗの加算と
乗算を例にあげる。

【０００６】 α＋β＝（ａ₁ ＋ｂ₁ ｗ）＋（ａ₂ ＋ｂ₂ ｗ） ＝（ａ₁ ＋ａ₂ ）＋（ｂ₁ ＋ｂ₂ ）ｗ α・β＝（ａ₁ ＋ｂ₁ ｗ）・（ａ₂ ＋ｂ₂ ｗ） ＝（ａ₁ ａ₂ −ｂ₁ ｂ₂ ）＋（ａ₁ ｂ₂ ＋ａ₂ ｂ₁ −ｂ
₁ ｂ₂ ）ｗ １回の複素整数の加算には２回の整数の加算が必要であ
り、１回の複素整数の乗算には４回の整数の乗算と３回
の整数の加減算が必要であることがわかる。つまり、１
回の複素整数の加算にかかる時間は整数の加算にかかる
時間の２倍であり、１回の複素整数の乗算の時間は整数
の乗算にかかる時間の４倍以上である。したがって、複
素整数の加減乗除算に基づく従来の計算方式を用いて暗
号化鍵と復号化鍵を求めようとすると、多くの計算時間
が必要であった。

【０００７】

【発明が解決しようとする課題】式（１）をみたすｕと
ｖを求める従来の計算方式は、複素整数の演算を行なう
ので、多くの計算時間が必要とされた。しかし、暗号に
おいて暗号化鍵と複号化鍵はできるだけ高速に計算する
必要があるので、式（１) をみたすｕとｖを高速に求め
る計算装置が要望されていた。

【０００８】

【課題を解決するための手段】この発明によれば、ｇ
（ｇ＝ｐ又はｑ）がｓとして第１記憶部に記憶され、ｋ
² ≡ｇ−３（ｍｏｄｇ）かつｋ＜ｇ／２をみたす整数ｋ
がｔとして第２記憶部に記憶され、√ｇを超えない最大
の整数ｗが平方根計算器で計算され、そのｗが第３記憶
部に記憶され、第１記憶部から読出されたｓと第２記憶
部から読出されたｔについて、剰余計算手段でｒ＝ｓｍ
ｏｄｔが計算され、第２記憶部から読出されたｔと第３
記憶部のｗとの大小関係が比較手段で比較され、この比
較結果がｔ＜ｗとなるまで、ｔをｓとして第１記憶部に
記憶し、ｒをｔとして第２記憶部に記憶し、これら記憶
したｓ，ｔを上記剰余計算手段へ供給することが制御手
段により繰返される。ｔ＜ｗとなった時のｔとｇとから
ｍ＝√｛（ｇ−ｔ² ）／３｝が演算され、更にｔ＋ｍ＝
ｕ″、ｖ″＝２ｍ（ここでｕ″＝ｕ又はｕ′、ｖ″＝ｖ
又はｖ′）が計算されて出力される。

【０００９】このようにこの発明では、複素整数の概念
を用いずに、整数の剰余計算の単純な繰り返しによって
式（１) をみたすｕとｖを求め、暗号化鍵と復号化鍵を
計算することを特徴とする。この発明装置で行う、整数
の剰余計算の単純な繰り返しによって式（１) をみたす
ｕとｖを求める手順を示すと次のようになる。なお、：
＝の記号は右辺の値を左辺に代入することを意味する。

【００１０】入力ｇ≡１（ｍｏｄ３) をみたす素数ｇと
ｋ² ≡ｇ−３（ｍｏｄｇ）かつｋ＜ｇ／２をみたす整数
ｋを入力とする。 Ｓｔｅｐ１ｓ：＝ｇ，ｔ：＝ｋ，ｗ：＝（√ｇを超えな
い最大の整数）とする。 Ｓｔｅｐ２もしｔ＜ｗならば、ｕ：＝ｔ＋１，ｖ：＝２
とし出力へ行く。

【００１１】Ｓｔｅｐ３ｒ：＝ｓｍｏｄｔとする。 Ｓｔｅｐ４ｓ：＝ｔ，ｔ：＝ｒとする。 Ｓｔｅｐ５もしｔ＞ｗならば、Ｓｔｅｐ３へ行く。 Ｓｔｅｐ６ｍ：＝√｛（ｇ−ｔ² ）／３｝ Ｓｔｅｐ７ｕ：＝ｔ＋ｍ，ｖ：＝２ｍとする。

【００１２】出力ｕとｖを出力する。本発明は、式
（１) をみたすｕとｖを整数の剰余計算の繰り返しによ
り求めているため、複素整数の演算を必要とした従来の
計算方式より加減乗除算の回数が少なくなり、暗号化鍵
と復号化鍵を計算するための時間が短くてすむ。

【００１３】

【実施例】図１にこの発明の鍵生成装置の構成例を示
す。素数ｐと、ｋ_p ² ≡ｐ−３（ｍｏｄｐ）かつｋ_p ＜
ｐ／２をみたす整数ｋ_p と、素数ｑと、ｋ_q ² ≡ｑ−３
（ｍｏｄｑ）かつｋ_q ＜ｑ／２をみたす整数ｋ_q とをパ
ラメータ生成部１１に入力すると、パラメータ生成部１
１は後述するように演算されて整数ｎ₀ を出力する。そ
のｎ₀ は互素数生成器１２に入力され、ｎ₀ と互いに素
な整数の１個ｅが出力される。このｅと前記ｎ₀ とがユ
ークリッド互除法計算器１３に入力され、ｅｄ≡１（ｍ
ｏｄｎ₀ ）をみたす整数ｄがユークリッド互除法を用い
て計算されてｄが出力される。鍵生成装置の出力はｅと
ｄである。

【００１４】パラメータ生成部１１の構成例を図２に示
す。素数ｐと前記整数ｋ_p とが繰り返し剰余計算器１６
に入力され、後述のように演算されて整数ｔ_p が出力さ
れる。そのｔ_p とｐが第１平方根計算器１７に入力され
て、ｍ_p ＝√｛（ｐ−ｔ² ）／３｝が計算され、その結
果ｍ_p とｔ_p とｐとが第１加算器１８に入力されて、 ｕ＝ｔ_p ＋ｍ_p ｖ＝２ｍ_p ｎ_p1 ⁺ ＝ｐ＋１＋（２ｕ−ｖ） ｎ_p1 ^- ＝ｐ＋１−（２ｕ−ｖ） ｎ_p2 ⁺ ＝ｐ＋１＋（−ｕ−ｖ） ｎ_p2 ^- ＝ｐ＋１−（−ｕ−ｖ） ｎ_p3 ⁺ ＝ｐ＋１＋（−ｕ＋２ｖ） ｎ_p3 ^- ＝ｐ＋１−（−ｕ＋２ｖ） が計算され、ｎ_p1 ⁺ ，ｎ_p1 ^- ，ｎ_p2 ⁺ ，ｎ_p2 ^- ，
ｎ_p3 ⁺ ，ｎ_p3 ^- が出力される。同様に素数ｑと前記整数
ｋ_q とが繰り返し剰余計算器１９に入力されて、ｔ_q が
計算され、そのｔ_q とｑが第１平方根計算器２１に入力
されて、ｍ_q が計算され、更にｍ_q とｔ_q とｑとが第１
加算器２２に入力されて、ｎ_q1 ⁺ ，ｎ_q1 ^- ，ｎ_q2 ⁺ ，ｎ
_q2 ^- ，ｎ_q3 ⁺ ，ｎ_q3 ^- が計算されて出力される。最小公
倍数計算器２３はｎ_p1 ⁺ ，ｎ_p1 ^- ，ｎ_p2 ⁺ ，ｎ_p2 ^- ，ｎ
_p3 ⁺ ，ｎ_p3 ^- ，ｎ_q1 ⁺ ，ｎ_q1 ^- ，ｎ_q2 ⁺ ，ｎ_q2 ^- ，ｎ_q3
⁺ ，ｎ_q3 ^- を入力としてこれらの最小公倍数ｎ₀ を求
め、パラメーター生成部１１の出力とする。

【００１５】図２中の繰り返し剰余計算器１６の構成例
を図３に示す。素数ｐとｋ² ≡ｐ−３（ｍｏｄｐ）かつ
ｋ＜ｐ／２をみたす整数ｋを入力とし、ｐが第１記憶部
２５に記憶され、ｋが第２記憶部２６に記憶され、ｐは
第２平方根計算器２７にも入力され、√ｐを超えない最
大の整数が計算され、その結果が第３記憶部２８に記憶
される。そして、第１記憶部２５から読み出された値を
ｓとし、第２記憶部２６から読み出された値をｔとし
て、剰余計算器２９でｒ＝ｓｍｏｄｔが計算され、ｔと
ｒが出力され、そのｔが第１記憶部２５に記憶され、ｒ
が第２記憶部２６に記憶される。第２記憶部２６から読
み出されたｔは、第３記憶部２８に記憶されている値ｗ
との大小関係が比較器３１で比較され、第２記憶部２６
から読み出された値ｔが第３記憶部２８に記憶されてい
る値ｗより小さくなるまで、第１記憶部２５、第２記憶
部２６の読み出し、そのｓ，ｔについての剰余計算器２
９での計算、その結果についての第１、第２記憶部２
５，２６への記憶が制御部３２で繰り返される。比較器
３１の比較結果がｔ＜ｗとなると第２記憶部２６から読
み出された値ｔが繰り返し剰余計算器１６の出力とされ
る。

【００１６】繰り返し剰余計算器１９も同様に構成され
る。上述の各種演算は電子計算機で行ってもよい。

【００１７】

【発明の効果】複素整数は実部と虚部をもつので、複素
整数の加減乗除算は整数の加減乗除算の数倍の時間がか
かる。したがって、複素整数の加減乗除算に基づく従来
の計算方式を用いると、暗号化鍵と復号化鍵を計算する
ために多くの時間が必要であった。しかしこの発明で
は、式（１) をみたすｕとｖを整数の剰余計算の繰り返
しにより求めているため、複素整数の演算を必要とした
従来の計算方式と比較して、整数の加減乗除算の回数を
大幅に削減できるので、暗号化鍵と復号化鍵を計算する
ための時間が短くてすむ。

【００１８】例えば、ｐを７９とし、ｋ² ≡ｐ−３（ｍ
ｏｄｐ）かつｋ＜ｐ／２をみたすｋを３２とすると、 入力ｐ：＝７９， ｋ：＝３２ Ｓｔｅｐ１ ｓ：＝ｐ＝７９，ｔ：＝ｋ＝３２，ｗ＝８
（√７９を超えない最大の整数） Ｓｔｅｐ２ ｔ＝３２＞ｗ＝８ Ｓｔｅｐ３ ｒ：＝ｓｍｏｄｔ＝７９ｍｏｄ３２＝１５ Ｓｔｅｐ４ ｓ：＝３２，ｔ：＝１５ Ｓｔｅｐ５ ｔ＝１５＞ｗ＝８ Ｓｔｅｐ３ ｒ：＝ｓｍｏｄｔ＝３２ｍｏｄ１５＝２ Ｓｔｅｐ４ ｓ：＝１５，ｔ：＝２ Ｓｔｅｐ５ ｔ＝２＜ｗ＝８ Ｓｔｅｐ６ ｍ：＝√｛（７９−２² ）／３｝＝５ Ｓｔｅｐ７ ｕ：＝ｔ＋ｍ＝２＋５＝７，ｖ：＝２ｍ＝
２×５＝１０ 出力 ｕ＝７，ｖ＝１０ 一方、従来方式を用いて、ｐ＝７９と、ｋ² ≡ｐ−３
（ｍｏｄｐ）をみたすｋ＝３２に対してｐとｋ−１−２
ｗとの最大公約数、つまりｇｅｄ（７９，３２−１−２
ｗ）の計算は、以下のようなＺ［ｗ］上の剰余計算の繰
り返しで実現される。

【００１９】 入力α：＝ｐ＝７９，β：＝３２−１−２ｗ Ｓｔｅｐ１α：＝７９，β：＝３１−２ｗ Ｓｔｅｐ２γ：＝αｍｏｄβ＝７９ｍｏｄ（３１−２
ｗ）＝−１４＋６ｗ Ｓｔｅｐ３α：＝３１−２ｗ，β：＝−１４＋６ｗ Ｓｔｅｐ４β≠０ Ｓｔｅｐ２γ：＝αmod β＝３１−２ｗmod(−１４＋６
ｗ）＝−３−１０ｗ Ｓｔｅｐ３α：＝−１４＋６ｗ，β：＝−３−１０ｗ Ｓｔｅｐ４β≠０ Ｓｔｅｐ２γ：＝αmod β＝１４＋６ｗｍｏｄ（−３−
１０ｗ）＝０ Ｓｔｅｐ３α：＝−３−１０ｗ，β：＝０ｗ Ｓｔｅｐ４β＝０ 出力α＝−３−１０ｗ つまりｕ＝−３，ｖ＝−１０を出力する。

【００２０】ここで式（１) をみたすｕとｖは６通りの
解が存在するため、前記この発明により求めたｕ＝７，
ｖ＝１０と異なったものとなった。この例によればこの
発明では整数の剰余演算は２回で済んだが、従来方法で
は複素整数の剰余演算を３回必要とし、複素整数の剰余
演算は整数の剰余演算よりも計算に時間がかかるため、
この発明によれば従来よりも短い計算時間で鍵を生成す
ることができる。

【図面の簡単な説明】

【図１】この発明による鍵生成装置の構成例を示すブロ
ック図。

【図２】図１中のパラメータ生成器１１の構成例を示す
ブロック図。

【図３】この発明の要部である図２中の繰り返し剰余計
算器１６の構成例を示すブロック図。

Claims (1)

【特許請求の範囲】
1. 【請求項１】 ｐ≡１（ｍｏｄ３) をみたす素数ｐに対
   しｐ＝ｕ² −ｕｖ＋ｖ² をみたす整数ｕ，ｖを求め、こ
   れらとｐとからｐをパラメータとしてもつ楕円曲線Ｅ_p
   （０，ｂ）の位数を求め、またｑ≡１（ｍｏｄ３) をみ
   たし、かつｐと異なる素数ｑに対しｑ＝ｕ′² −ｕ′
   ｖ′＋ｖ′² をみたす整数ｕ′，ｖ′を求め、これらと
   ｑとからｑをパラメータとしてもつ楕円曲線Ｅ_q （０，
   ｂ）の位数を求め、上記両位数から、楕円曲線に基づく
   暗号の鍵を生成する装置において、 ｇ（ｇは上記ｐ又はｑ）をｓとして記憶する第１記憶部
   と、 ｋ² ≡ｇ−３（ｍｏｄｇ）かつｋ＜ｇ／２をみたす整数
   ｋをｔとして記憶する第２記憶部と、 √ｇを超えない最大の整数ｗを計算する平方根計算器
   と、 上記整数ｗを記憶する第３記憶部と、 上記第１記憶部から読出されたｓと、上記第２記憶部か
   ら読出されたｔについてｒ＝ｓｍｏｄｔを計算する剰余
   計算手段と、 上記第２記憶部から読出されたｔと上記第３記憶部のｗ
   との大小関係を比較する比較手段と、 その比較結果がｔ＜ｗとなるまで、上記ｔをｓとして上
   記第１記憶部に記憶し、上記ｒをｔとして上記第２記憶
   部に記憶し、これら記憶したｓ，ｔを上記剰余計算手段
   へ供給することを繰返す手段と、 上記ｔ＜ｗとなった時の上記ｔとｇとからｍ＝√｛（ｇ
   −ｔ² ）／３｝を演算する手段と、 ｔ＋ｍ＝ｕ″、ｖ″＝２ｍ（ｕ″はｕ又はｕ′、ｖ″は
   ｖ又はｖ′）を計算して出力する手段と、 を具備することを特徴とする楕円曲線に基づく暗号の鍵
   生成装置。