Nowadays various changes are taking place in the society by the spread of the Internet, and we will vote by the Internet using the encryption in the elections. Even if the key of the Elliptic Curve Cryptosystem is shorter than the key of the RSA cryptosystem, the Elliptic Curve Cryptosystem is secure. This paper shows the method of Internet vote with the Elliptic Curve Cryptosystem. Furthermore, the simulation of an Internet vote with the Elliptic Curve Cryptosystem is shown using Excel and VBA.
1．はじめに
現在、インターネットの普及で、社会に様々な変化が起こっているが、選挙における投票もイ ンターネットを利用して、パソコンや携帯電話、スマートフォンなどからの投票が可能になれば、 若者をはじめとして、投票率がアップするだけでなく、政治への関心も高まる可能性が高いと思 われる。インターネット等のネットワークの利用では、暗号を使って、投票の秘密を厳守する必 要がある。「二重鍵インターネット投票」［1］ では、RSA 暗号を用いて、候補者名を乱数で変換し た後、公開鍵で暗号化し、それに投票者名を入れて、秘密鍵で署名する方法について述べた。こ の公開鍵暗号方式には、RSA 暗号だけでなく、最近、楕円曲線暗号も使用されるようになって きた。この論文では、インターネットを使用した投票で、RSA 暗号よりもキーが短くとも同程 度の安全性のある楕円曲線暗号を利用する方法について述べる。そして、実際に楕円曲線暗号を 用い、Excel と VBA を使用して投票をシミュレーションした結果についても解説する。楕円曲線暗号利用のインターネット投票
An Internet Vote Using the Elliptic Curve Cryptosystem
高林 茂樹
TAKABAYASHI Shigeki
2．楕円曲線暗号の利用
楕円曲線暗号は、1985年に Koblitz 氏と Miller 氏がほぼ同時に独立に考案した楕円曲線を利 用する暗号方式である。
2.1 楕円曲線の方程式
要素同士で加算・減算・乗算・除算（ただし0による除算は除く）を計算することができる集 合を体（field）と言い、Fpのように、要素の個数が p 個である体を素体（prime field）と呼ぶ。
素体 Fp上の楕円曲線の方程式は次のようになる。 !'+##*$"$*"%$!%%"( '!'!#%$$"#&%#&!# ) 楕円曲線 E 上の点の中で、座標が Fp要素となる点を Fpの有理点という。 この有理点の数（群位数）を &とすると Hasse−Weil の定理で '""!#'* $&$'"""##* である。 2.2 有理点の加法 素体 Fp上の楕円曲線!'+##*$"$*"%上の2点 P と Q の和を R とすると、 R＝P＋Q は以下のようになる。ただし O は無限遠点とする。 P＝O のときは、R＝Q Q＝O のときは、R＝P それ以外のときは、P＝（xp, yp），Q＝（xq, yq）とすると、 yp＝−yqのときは、R=O とする。 このとき P は Q の逆元となり、Q＝−P となっている。 yp≠−yqのときは、R＝（xr, yr）とする。ここで xrと yrは *)#"#!*'!*( +)#"*('!*))!+' となる。 ここでλ は、 xp≠xqのときは、+ '!+( *'!*( ―３２―
xp＝xqのときは、 "#"!!! !$" である。［2］ 2.3 暗号化と復号化 楕円曲線の有理点 S とスカラー（整数）d から有理点 T＝d×S を計算することは容易である。 しかし、S と T から T＝d×S を満たすスカラー d を見つけることは計算に時間がかかり困難で ある。このことを利用した暗号化と復号化には、楕円曲線暗号による公開鍵暗号方式である楕円 エルガマル（ECElGamal）暗号を使用する。［2］ !送信者と受信者は、素体 Fp上の楕円曲線 E と曲線上の点 P を共有する。 "受信者は、乱数 r1を生成し、スカラー倍点 e＝r1×P を計算する。そして r1を秘密鍵 d とし て保管し、e を公開鍵として公開する。 #送信者は、乱数 r2を生成し、スカラー倍点 R＝r2×P を計算する。 $送信者は、公開鍵 e を入手し、スカラー倍点 K＝r2×e を計算する。 %楕円曲線上の点として表された平文 M に対し、C＝M＋K を計算する。 &暗号文として、点の組（R, C）を送信する。 '暗号文として、点の組（R, C）を受信する。 (点 R と秘密鍵 d から、スカラー倍点 K＝d×R を計算して K を復元する。 )M＝C−K を計算し、平文 M を復元する。 2.4 投票における楕円曲線暗号 楕円曲線暗号による投票では、選んだ候補者を公開鍵1で暗号化し、さらに投票者の情報と暗 号化された候補者をさらに公開鍵2で暗号化して送信つまり投票する。投票者の情報は二重投票 でないかチェックすることに使用する。選挙管理組織（選挙管理委員会またはインターネット選 挙を管理する組織）で受信した暗号化された情報は、公開鍵2と対になった秘密鍵2で復号化さ れ、有権者の名簿と照合する。選挙の投票が締め切られ、開票時刻になったら、暗号化された候 補者は、投票者情報と完全に分離した状態で、公開鍵1と対になった秘密鍵1で復号化する。 !選んだ候補者の暗号化 （a）投票者と選挙管理組織は、素体 Fp上の楕円曲線 E1と曲線上の点 P1を共有する。 ―３３―
（b）選挙管理組織は、乱数 r11を生成し、スカラー倍点 e1＝r11×P1を計算する。そして r11を秘 密鍵 d1として保管し、e1を公開鍵として公開する。 （c）投票者は、乱数 r12を生成し、スカラー倍点 R1＝r12×P1を計算する。 （d）投票者は、公開鍵 e1を入手し、スカラー倍点 K1＝r12×e1を計算する。 （e）楕円曲線上の点として表された候補者 M1に対し、C1＝M1＋K1を計算する。 !投票者情報の暗号化 （a）投票者と選挙管理組織は、素体 Fp上の楕円曲線 E2と曲線上の点 P2を共有する。 （b）選挙管理組織は、乱数 r21を生成し、スカラー倍点 e2＝r21×P2を計算する。そして r21を秘 密鍵 d2として保管し、e2を公開鍵として公開する。 （c）投票者は、乱数 r22を生成し、スカラー倍点 R2＝r22×P2を計算する。 （d）投票者は、公開鍵 e2を入手し、スカラー倍点 K2＝r22×e2を計算する。 （e）楕円曲線上の点として表された投票者情報 M2および暗号化された候補者 C1と R1に対し、 C2＝M2＋K2、R21＝R1＋K2、C21＝C1＋K2を計算する。 （f）暗号文として、点の組（R2, C2, R21, C21）を選挙管理組織に送信する。 "投票者情報の復号化 （a）点 R2と秘密鍵 d2から、スカラー倍点 K’2＝d2×R2を計算して K2を復元する。 （b）M’2＝C2−K’2を計算し、投票者情報 M2を復元する。 R’1＝R21−K’2および C’1＝C21−K’2を計算し、R1と C1も復元する。 #選んだ候補者の復号化 （a）投票者情報 M’2と暗号化された候補者 C’1を完全に分離する。 （b）点 R’1と秘密鍵 d1から、スカラー倍点 K’1＝d1×R’1を計算して K’1を復元する。 （c）M’1＝C’1−K’1を計算し、選んだ候補者 M1を復元する。
3．楕円曲線暗号による投票のシミュレーション
3.1 有理点の計算 ―３４―素体 Fp上の楕円曲線の方程式
!((##'$"#'"$#!$%"( &!'!#%#$"#&$#&!# )
を満たして、下記の式から有理点の数（群位数） %が300程度となる素数 &を使用した。 &""!#&* $%$&"""#&*
ここでの例では &=317すると、 282.4$%$ 353.6
#!$%"$"&，判別式'!#%#$"#&$#&!#
を満たし、有理点の数（群位数）が素数となる式を求める。 #=17，$=99のとき、有理点の数（群位数） %=349となり、これは素数である。 したがって、下記の式を、このシミュレーションで有理点の計算に使用する。 (##'$""&'"'' "( )$"& 有理点の計算プログラムを以下に示す。a, b, p は、ワークシート上で指定している。 Sub yuuriten() Dim M(30000), N(30000) As Long Dim ia, ib, ih, ih1, i, j, ip, ir, iw As Long Dim wk As Worksheet Set wk = ActiveSheet Range(”P2:R30000”).Select Selection.ClearContents ia = wk.Cells(5, 3).Value ib = wk.Cells(6, 3).Value ih = wk.Cells(7, 3).Value ih1 = ih − 1 For i = 0 To ih1 M(i) = (i * i) Mod ih iw = (M(i) * i) Mod ih
N(i) = (iw + ((ia * i) Mod ih) + ib) Mod ih Next i
Application.ScreenUpdating = False ip = 1
For i = 0 To ih1
For j = 0 To ih1
If N(i) <> M(j) Then GoTo Label1 ip = ip + 1 wk.Cells(ip, 16).Value = ip − 1 wk.Cells(ip, 17).Value = i wk.Cells(ip, 18).Value = j Label1: Next j Next i wk.Cells(11, 3).Value = ip Application.ScreenUpdating = True End Sub """!#!!$!!%%の F 317での有理点の計算結果を表−1に示す。P は有理点の番号、x と y は、 有理点の x 座標と y 座標である。 ―３６―
3.2 公開鍵と秘密鍵の生成 !第1鍵（候補者の暗号化用） （a）投票者と選挙管理組織は、素体 Fp上の楕円曲線 E1と曲線上の点 P1を共有する。 （b）選挙管理組織は、乱数 r11を生成し、スカラー倍点 e1＝r11×P1を計算する。そして r11を第 1秘密鍵 d1として保管し、e1を第1公開鍵として公開する。 シミュレーションの例では、以下のようになっている。 表−1 有理点の計算結果 ―３７―
図−1 投票用の画面 "第2鍵（投票者情報の暗号化用） （a）投票者と選挙管理組織は、素体 Fp上の楕円曲線 E2と曲線上の点 P2を共有する。 （b）選挙管理組織は、乱数 r21を生成し、スカラー倍点 e2＝r21×P2を計算する。そして r21を第 2秘密鍵 d2として保管し、e2を第2公開鍵として公開する。 シミュレーションの例では、以下のようになっている。 3.3 選んだ候補者と投票者情報の入力 !投票の画面 （a）投票する人は、候補者名リストの中から1名を選択する。 （b）投票者の情報として有権者コードと生年月日を入れる。 "選んだ候補者の暗号化 （a）候補者名をコード化する。なお、このシミュレーションでは、有理点の数が349なので、 この数より大きいコードは、分割している。 （b）乱数 r12を生成し、スカラー倍点 R1＝r12×P1を計算する。 （c）第1公開鍵 e1を入手し、スカラー倍点 K1＝r12×e1を計算する。 ―３８―
（d）楕円曲線上の点として表された候補者 M1に対し、C1＝M1＋K1を計算する。 シミュレーションの例では、以下のようになっている。 !投票者情報の暗号化 （a）投票者情報をコード化する。 （b）乱数 r22を生成し、スカラー倍点 R2＝r22×P2を計算する。 （c）第2公開鍵 e2を入手し、スカラー倍点 K2＝r22×e2を計算する。 （d）楕円曲線上の点として表された投票者情報 M2および暗号化された候補者 C1と R1に対し、 C2＝M2＋K2、R21＝R1＋K2、C21＝C1＋K2を計算する。 シミュレーションの例では、以下のようになっている。 有理点の加法で使用した関数プログラムを次に示す。引数は2つの有理点の位置とする。
Function tasi (a, b As Long) As Long
Dim ia, ib, ih, i, j, ip, ir, iw, ix, iy, xa, xb, ya, yb, xc, yc, lam As Long Dim wk As Worksheet Set wk = ActiveSheet ia = wk.Cells(5, 3).Value ib = wk.Cells(6, 3).Value ih = wk.Cells(7, 3).Value xa = wk.Cells(a + 1, 17).Value ya = wk.Cells(a + 1, 18).Value xb = wk.Cells(b + 1, 17).Value yb = wk.Cells(b + 1, 18).Value ir = wk.Cells(11, 3).Value ―３９―
If a = 0 Or b = 0 Then tasi = a + b
GoTo Label4 End If
If (xa = xb) And (ya = (ih − yb) Or ((ya + yb) = 0)) Then tasi = 0
GoTo Label4 End If
If xa = xb Then GoTo Label1 ix = ya − yb
If ix < 0 Then ix = ix + ih iy = xa − xb
If iy < 0 Then iy = iy + ih lam = wari(ix, iy)
GoTo Label2 Label1:
ix = (3 * xa * xa + ia) Mod ih iy = (2 * ya) Mod ih
lam = wari(ix, iy) Label2: xc = lam * lam − xa − xb xc = xc + 2 * ih xc = xc Mod ih yc = xa − xc If yc < 0 Then yc = yc + ih yc = lam * yc − ya If yc < 0 Then yc = yc + ih yc = yc Mod ih For i = 1 To ir
If wk.Cells(i, 17).Value = xc And wk.Cells(i, 18).Value = yc Then GoTo Label3 Next i tasi = 99 GoTo Label4 Label3: tasi = i − 1 Label4: ―４０―
図−2 投票者情報の 確認画面と開票の画面 End Function $暗号化されたデータの送信 暗号化されたデータである点の組（R2, C2, R21, C21）を選挙管理組織に送信する。 シミュレーションの例では、送信データは、以下のようになっている。 3.4 投票の確認および開票 !投票者の確認画面 暗号化された投票者情報のみを復号化したあと、投票者情報は、選挙管理組織のあるデータを 照合し、投票の確認をする。必要に応じて画面でもチェック可能にする。 "開票の画面 投票者情報と、まだ暗号化されている選ばれた候補者名を完全に切り離したあと、この候補者 名を復号化する。そして票の集計をする。必要に応じて、コード化されていた候補者名を文字化 し、画面でもチェック可能にする。 #投票者情報の復号化 （a）点 R2と第2秘密鍵 d2から、スカラー倍点 ―４１―
K’2＝d2×R2（＝d2×r22×P2＝r22×e2＝K2） を計算して K2を復元する。 （b）M’2＝C2−K’2を計算し、投票者情報 M2を復元する。 R’1＝R21−K’2および C’1＝C21−K’2を計算し、R1と C1も復元する。 シミュレーションの例では、以下のようになっている。 !選んだ候補者の復号化 （a）投票者情報 M’2と暗号化された候補者 C’1を完全に分離する。 （b）点 R’1と第1秘密鍵 d1から、スカラー倍点 K’1＝d1×R’1（＝d1×r12×P1＝r12×e1＝K1） を計算して K1を復元する。 （c）M’1＝C’1−K’1を計算し、選んだ候補者 M1を復元する。 シミュレーションの例では、以下のようになっており、M1が復元されている。
4．おわりに
現在、公開鍵暗号として RSA は広く普及しているが、コンピュータの性能向上等による解読 リスクの高まりに伴い、キーサイズを長くする等の対策が求められている。このため RSA に代 わる公開鍵暗号として楕円曲線暗号が注目されている。RSA では、秘密鍵を生成する際、利用 者ごとに異なる2個の素数を使用している。片方の素数が重複しても、2個の素数の積から作ら れる公開鍵は異なるものとなるため、重複していることに気づきにくく、これを選挙管理組織の システム管理者が検証によって見つけようとしても難しい。これに対し、楕円曲線暗号では、秘 密鍵を生成する際、利用者ごとに異なる乱数の発生等により1個の自然数を無作為に選択するだ けであり、鍵生成の仕組みが RSA と異なることからこのような問題は起こりにくい。つまり楕 ―４２―円曲線暗号では、公開鍵を発行する時点で、選挙管理組織のシステム管理者が既存の公開鍵との 重複を検証することは容易である。したがって、楕円曲線暗号ではこの問題での安全性への影響 は RSA と比較して相対的に低いと考えられており、運用時における選挙管理組織の管理者の負 担を軽減できる暗号方式と考えられる。［3］ インターネット等のネットワークを利用した国政レベルの選挙を実施している国には、現在、 バルト3国の1つであるエストニアがあるが、これ以外ではほとんど例がない。［4］ 「二重鍵利用の インターネット投票」［1］ でも述べたように、国政選挙等において、インターネットを使用した投 票が普及しないのは、技術的な問題だけでなく関連する制度の整備状況にもあり、見直しが必要 である。楕円曲線暗号は、今後さらに普及していくと考えられるが、RSA 暗号よりもキーサイ ズが短くとも安全といわれ、運用する選挙管理組織にとっても負担の軽い楕円曲線暗号を使用し て、まず不在者投票からでもインターネット投票を可能にする制度を早急に検討し、実施すべき である。これによりパソコン、携帯電話、スマートフォンからの投票が、選挙期間中であれば、 場所や時間の制限なく可能となり、投票率のアップも期待される。さらに今後は、投票時に候補 者を選ぶための参考となる情報、たとえば選挙公報や候補者に対するアンケート結果のような情 報をデータベース化し、有権者にとって利用しやすくすることも必要である。 参考文献 ［1］高林茂樹「二重鍵利用のインターネット投票」埼玉女子短期大学紀要第29号 2014 ［2］伊豆哲也「楕円曲線暗号入門」researchmap 2013 ［3］清藤武暢／四方順司「公開鍵暗号を巡る新しい動き：RSA から楕円曲線暗号へ」金融研究 2013
［4］NTT DATA DIGITAL GOVERNMENT & FINANCIAL TOPICS 編集局「エストニアの 電子選挙」2013
http://e−public.nttdata.co.jp/topics_detail2/contents_type=9&id=923
