ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

楕円曲線入門 番外編

第4話に追記するには少々長く, また第5話として書くような内容でもない気がしたため番外編とした.

前回, 楕円曲線上でのデジタル署名(ECDSA)の解説をした.
ECDSAでは, 署名にある適当な乱数\(k\)を使用するが, この\(k\)が乱数ではなく全て固定値として署名されていた場合どうなるのか, について本稿で解説する.
先に答えを言うと, 秘密鍵が漏洩するので絶対に固定値を利用してはいけない.

2010年に, ECDSAの実装に問題のあったPS3秘密鍵の取得が可能であることが報告されている.
Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access.

Proof

メッセージM1, M2に対するハッシュ値を \(e1, e2\)
それぞれの署名を \((r_{1}, s_{1}),(r_{2}, s_{2})\)
共通の固定値を\(k\)として秘密鍵\(d\)を解読していく.

本稿では, \(r\)は既に導出されているものとし, \(s\)の計算から解説を始める.

\begin{eqnarray} s_{1} &=& k^{-1}(e_{1} + r_{1}d) \newline s_{2} &=& k^{-1}(e_{2} + r_{2}d) \newline \end{eqnarray}

\(k\)は共通の定数なので, 両辺に\(k\)をかけ\(k = \)の形にすると

$$ k = \frac{e_{1} + r_{1}d}{s_{1}} = \frac{e_{2} + r_{2}d}{s_{2}} $$

\(k\)にご退場いただき, 秘密鍵\(d\)について解くように式を変形していく.

\begin{eqnarray} s_{2}(e_{1} + r_{1}d) &=& s_{1}(e_{2} + r_{2}d) \newline s_{2}e_{1} + s_{2}r_{1}d &=& s_{1}e_{2} +s_{1}r_{2}d \newline s_{2}r_{1}d - s_{1}r_{2}d &=& s_{1}e_{2} - s_{2}e_{1} \newline (s_{2}r_{1} - s_{1}r_{2})d &=& s_{1}e_{2} - s_{2}e_{1} \newline \end{eqnarray}

よって $$ d = \frac{s_{1}e_{2} - s_{2}e_{1}}{s_{2}r_{1} - s_{1}r_{2}} $$

署名が2つあれば, 以上の計算で秘密鍵を得ることができる.
署名用の秘密鍵を得るとたとえばどのようなことができるのかについては, 逮捕されたくないのでコメントを控える.

実は, \(k\)が固定値なので\(r_{1} = r_{2}\)である.

検証

6年通ったNITACを卒業しました

2013年に中卒からの入学でNITACに入り, 6年間お世話になりました.

クラスメイトや先輩, 後輩, そして先生方に恵まれ, 高●専プロコンやドイツへの留学など様々な経験をさせてもらいました. ありがとうございました. 

 

卒業式当日, 私は学会参加のため式には出席していませんが, おそらく卒業証書が発行されているでしょう.

 

NITACを卒業した理由

卒業要件である

  • 卒業に必要な履修・修得単位の獲得
  • 学外発表(学会発表)
  • 卒業研究の最終発表

を達成し, 条件を満たしたからです.

 

f:id:ushiromiya3:20190314234036j:plain

 

そんな感じでNITACを卒業しました.

進学先はUECで, 今年の4月からII類のセキュリティ情報学所属となります.

引き続きよろしくお願いします. 

 

希望の研究室に配属されるよう努力しつつ, 自分のしたい勉強をする年にしたいと思います. バイト先も探しているのでよろしくお願いします.

楕円曲線入門 (4)

前回(第3話)までで基本的な楕円曲線の解説を終えた(多分).

本稿では, 楕円曲線を用いた署名アルゴリズムについて解説する.


Elliptic Curve Digital Signature Algorithm

楕円曲線を使ったデジタル署名(DSA)のアルゴリズム.
まずはデジタル署名とは何か, また何のために使われるのかを解説する.


デジタル署名

先にデジタル署名の役割を言うと, 送り主が誰であるかとデータが改ざんされていないことを証明する.

データの送り主について着目し, 次のようなシナリオを考える.
AliceがBobになにか重要なファイル(データ)を送信したとする. この例ではファイルが暗号化されているかどうかは考慮しない.

Bobが受け取ったファイルが, Aliceから送られてきたものなのかを本人に確認すると,

Bob 「これお前が送ったデータやんな?」

Alice 「ちゃうでw(違わない)」

違うと言われてしまった. どうやら違うようだ.

このような否認がインターネット上で自由に行われることは, 到底許されるべきではない. そこでデジタル署名を用いることで, 否認の対策を行うこととした.
これで, Aliceがいくら自分が送ったファイルではないと言い張っても, デジタル署名がAliceのものであると立証してくれているので嘘がつけなくなった. めでたしめでたし.
実際に使われる署名アルゴリズムとしてはRSAなどが有名である.

ECDSA

さて, 話を楕円曲線に戻す.
これより楕円曲線を使ってデジタル署名を行う手順を解説する.

準備

利用する楕円曲線 \(EC := y^{2} = x^{3} + Ax + B\) を定義.
\(EC\)上の点を\(G\), \(G\)の位数を\(n\)とする. 位数が\(n\)なので, \([n]G = O\)が成り立つ.

ただし, \(n\)は素数である必要がある. \(Modulus\)でなく位数が素数である点に注意.
つまり, \(Modulus\)と\(n\)が両方とも素数である楕円曲線(とベースポイント\(G\))を選択する必要がある.

次にAliceは\([1, .., n-1]\)の中から適当な\(d_{A}\)を選択して, \(Q_{A} := [d_{A}]G\) を計算しておく.

\((Curve, G, n, Q_{A})\)が公開されている情報である.

署名

mをメッセージとする.

\begin{eqnarray} e &:=& SHA256(m) \newline k &:=& randint(1, n-1) \newline (x_{1}, \, y_{1}) &:=& [k]G \newline r &:=& x_{1} \, mod \, n \end{eqnarray} \(r\)は楕円曲線上の計算の時点で\(x_{1} < n\)だが念の為.

$$ s := k^{-1}(e + rd_{A}) \, mod \, n $$

\((r, s)\)が署名となる.

\(e\)の導出にSHA256を使用しているが, 署名/検証で同じハッシュ関数を使用するのであれば他のものを利用しても良い.

検証

受け取ったメッセージを復号したものをmとする.

\begin{eqnarray} e &:=& SHA256(m) \newline w &:=& s^{-1} \, mod \, n \newline u &:=& ew \, mod \, n \newline v &:=& rw \, mod \, n \newline \end{eqnarray}

\((u, v)\), ベースポイント\(G\)とAliceが署名した\(Q_{A}\)を使って $$ (x_{2}, \, y_{2}) := [u]G + [v]Q_{A} $$

\(r \equiv x_{2} \, mod \, n\)であれば署名は有効である.

正当性

以上の手順で正しく検証ができることを確かめる.
先ほどの式を変形していこう.

\begin{eqnarray} [u]G + [v]Q_{A} &=& [u]G + [v][d_{A}]G \newline &=& [u + vd_{A}]G \newline &=& [ew + rwd_{A}]G \newline &=& [w(e + rd_{A})]G \newline &=& [s^{-1}(e + rd_{A})]G \newline &=& [(k^{-1})^{-1}(e + rd_{A})^{-1}(e + rd_{A})]G \newline &=& [k(e + rd_{A})^{-1}(e + rd_{A})]G \newline &=& [k]G \newline &=& (x_{2}, \, y_{2}) \end{eqnarray}

以上より, 署名と検証とで\(e\)が同じならば \(r \equiv x_{1} \equiv x_{2} \, mod \, n \) なので, 正しく署名の検証ができていることが示せた.

以下のコードでは\((e, d)\)を自分で作為的に選んでいるが, 署名については正しく検証できている.

ここではsageMathを使ったコードを載せているが, Golangで実行したものもあるので併せて載せておく. ECDSA by Golang (曲線や演算の定義により, 少し長いのでリンクだけ)

参考文献


To Be Continued..

乱数を使わない場合のECDSA -> 番外編
次->まだ

読書したい

読書っていいですよね. 私は最近ちゃんとした読書ができていませんが, 昔はよく小説を読んでいました. 

 

英語でも日本語でも, 文章を読めば色々な言葉が登場するので語彙力がつきますし, 何かを説明する文章であれば, 書きながら頭の中で整理がついてより理解が深められます. また, 文章を読むことは自分が文章を書くのにも役立ちます. 役立つ, というより読まなければ書けないのではないか, と思っています. 具体的な例を挙げると, 論文を読んだことがない人が論文を書くのは難しいですし, 英語が読めない(単語がわからない)人が英作文をするのも難しいですよね. 

小説を読んで作者の気持ちを読み解く..みたいなことは私も得意ではありませんが, 言葉や言い回しを知るという目的であれば読書は非常に有効な手段だと思います. 

 

読書で多くの言葉を知ることができるように, 文章を書くことでも多くの言葉を知ることができます. 私はよく, 単語が正しい意味で使えているかを, ツイートする前や記事を投稿する前に調べたりします. こうすることで曖昧に記憶していた単語がはっきりした意味で理解でき, 類似する単語も同時に会得できます. 辞書って素晴らしいですね.

 

技術書や専門書ばかりを読むのはエンジニアとしてはいいことですが, たまには他の文学に触れてみるのも楽しいのではないでしょうか. 久しぶりに小説が読みたくなった話でした.

近況

ykm11.hatenablog.com

 

本日, 卒業研究の最終発表が終了しました. 私の研究はおそらく引き継ぎ者がいないので, 後始末をする必要がなくひとまず終わりです(学会発表が2週間後に控えてますが).

次の月曜日に成績確認があり, そこでちゃんと単位修得(履修)できていれば卒業が確実なものとなります. 

 

お疲れ様でした.