FC2ブログ

鍵交換-まとめ

整数a,b,nに対して、a^bをnで割った余りrを求める計算をべき乗計算という。

→冪数bの和や積への分解や、2進数表記を用いて、できるだけ演算回数や計算量を少なくする努力をする。

 

有限な巡回群Gにおいて、g^x=hなる整数xを求める問題を離散対数問題という。

→これを効率よく溶けるアルゴリズムは存在しないことから、DH暗号への利用ができる。

 

位数が2または3のべき乗でない有限体上で、

y*y=x*x*x+a*x+b

で表される曲線を楕円曲線という

 

楕円曲線の2点の点配置によって定義された2点間の加算演算のことを楕円加算という。特に、点集合は楕円加算により群になる。スカラー倍も定義可能である。

 

与えられた楕円曲線においてxQ=Pとなる整数xを求める問題のことを楕円曲線上の離散対数問題という。小さいサイズの鍵でも通常の離散対数問題よりもとくのが困難と言われている。

 

楕円曲線上の離散対数問題の困難さに基づいた共通鍵の交換方法のことを楕円曲線上のDG鍵交換という

スポンサーサイト



鍵交換-2

楕円曲線

 

体F上で定義された以下の式で表される曲線を楕円曲線という。

 

y*y*y+a1*x*y+a2*y=x*x*x+a3*x*x+a4*x+a5

 

特に有限体Fqにおいて位数qが2または3のべき乗でない場合については、上記の式は次のより単純な式で表現できることが知られている。

 

y*y =x*x*x + a*x + b

 

ECexamples01

簡単のために素体Zp(p≠2,3)上の楕円曲線

⇔2*2*a*a*a + 3*3*3*b*b ≠0(mod p)合同の否定の記号がなかったorz

E:y*y = x*x*x + a*x +b, a,b∈Zp

 

Zp上のすべての2次元ベクトルの集合

Zp*Zp = {(x,y):x,y∈Zp}

のなかで

y*y = x*x*x + a*x + b(mod p)

を満たすベクトルの集合に無限遠点を加えた集合を楕円曲線Eの点集合という。

 

ハッセの定理

 

楕円曲線の K 上の点の個数を N とすると、

6c3c5fb47d0dcb51ade2adb47114075c

となることが知られている。

 

楕円曲線E上の2点P,Qに関して

 

1.PQがy軸に平行でないとき

直線PQと楕円曲線とのもうひとつの好転R=(x,y)とX軸に対して対称な点R’=(x,y)を用いてP+Q=R’とする。

2.直線PQがy軸に平行なとき(x1=x2)

無限遠点Oを用いてP+Q=Oとする。

3.PとQが同一点の時

Pを通る接戦と楕円曲線のもうひとつの好転Rとx軸に関して対象な点R’を用いてP+P=R'とする。

4.どちらかが無限遠点である時

P+O=Pまたは、O+Q=Qとする。このように定義された加算演算を用いるとE(Zp)は可換群となる。

特にこの時の加法を楕円加算という。

 

この辺の説明は楕円曲線を用いた暗号が詳しい。

 

 

楕円曲線上の鍵交換

 

楕円曲線上の離散対数問題

楕円曲線上のDH鍵交換

 

公開情報:素数p、楕円曲線E:y*y=x*x*x+a*x+b,点P∈E(Zp)

Ka:Aが定めた乱数、Aが秘密情報として保持(秘密鍵)

Kb:Bが定めた乱数、Bが秘密情報として保持(秘密鍵)

KaP=Qa:Aが送信する情報(公開鍵)

KbP=Qb:Bが送信する情報(公開鍵)

鍵交換-1

べき乗演算

任意の整数abおよび1より大きい自然数nに対して、a^bをnで割った余りを求めることを、nを法にしたべき乗演算という。

この時

a^b≡r(mod n)

が成立する。

 

b=b1+b2+b3------bmと分解されるとき

a^b1≡r1(mod n)

a^b2≡r2(mod n)

a^b3≡r3(mod n)

a^b4≡r4(mod n)

・・・・

a^bm≡rm(mod n)

であったりしたら、

a^b=a^b1*a^b2・・・・・・・a^bm≡r1*r2*r3・・・rm(mod n)

 

b=b1*b2*********bmと分解されるときは

a^b1≡r1(mod n)

a^b2≡r2(mod n)

a^b3≡r3(mod n)

・・・・

a^bk≡rk(mod n)

であったりしたら、

a^b=((((------((a^b1)^b2)-----))))^bm≡rm(mod n)

ex.

7^1000≡1^(1+1+++++++1)≡1(mod 6)

 

さらに整数bを

b=bm*2^m + bm-1^m-1 +++++++ b1*2^1

=(bm,bm-1,,,,,,,b1,b0),∀bi,∈{0,1}

↑さすがにカッコをつけようと思ったが・・・まあ、自分がわかれば大丈夫だ、問題ない。

と2進数表記した場合について、b1=1であるすべてのiに対して

a^2^i≡r1(mod n)

を予め計算しておけば、これを用いて以下のように計算できる。

a^b=(a^2^n)^bn * (a^2^n-1)bn-1 *********(a2^2^1)^b1*a^b0

≡rn*rn-1*****r1 * a^b0(mod n)

 

ex.

8^103(mod 13)=8^12^8 * 8^7

≡8^7(mod 13) = 8^3^2*8

≡5^2 * 8(mod 13) ≡ 5(mod 13)

 

101^659(mod 1237)

659=(1010010011)と2進数表記できることから

101^2^9≡750(mod 1237)

101^2^7≡750(mod 1237)

101^2^4≡750(mod 1237)

101^2≡750(mod 1237)

が得られる。したがって以下のように計算できる。

101^659=(101^2^9)(101^2^7)(101^2^4)(101^2)101

≡750*991*683*305*101(mod 1237)

≡90(mod 1237)

 

離散対数問題と鍵暗号

Gを位数|G|が有限な巡回群とする。この時、与えられたGの生成元gとh∈Gに対して、g^x=hとなる整数xの事をgをそこにするhの離散対数といい、上記の問題を離散対数問題という。

現在においてはい数が300桁(1024ビット)以上であれば、効率的にとくことは難しいとされている。

有限体Fqの加法単位元0以外の元からなる集合Fq*は乗法にかんしても巡回群となることが知られている。

送信者と受信者が共通の秘密鍵を用いて乗法のやりとりをする場合、予め送信者と受信者が同じ鍵を共有しておく必要がある。

そのために、盗聴の可能性がある危険な通信路において、両者が安全に共通鍵をやり取りする方法について考える。

Ka:Aが定めた整数(乱数)、Aが秘密情報として保持(秘密鍵)

Kb:Bが定めた整数(乱数)、Bが秘密情報として保持(秘密鍵)

g^Ka≡ca(mod p):Aが送信する情報(公開鍵)

g^Kb≡cb(mod p):Bが送信する情報(公開鍵)

この時、次の手順により各々が共通鍵を取得することが出来る。

1) Aは秘密鍵KaとBの公開鍵g^Kbを用いて

cb^Kb≡g^Kb^Ka≡g^KaKb≡Kab(mod p)

2) Bは秘密鍵KbとAの公開鍵g^Kaを用いて

ca^Ka≡g^Ka^Kb≡g^KaKb≡kab(mod p)

を計算する

3)1.2で求めたKabを共通鍵として各々が保持。

 

ここで、例えば盗聴者イブが共通鍵Kabを得るために、Aの公開鍵Caから、秘密鍵Kaを求めようとする場合について考えてみよう。結局このような目的を達成するには。

g^Ka≡ca(mod p)

を満たす整数Kaを求めることになるので、これは情報に関する巡回群Zp*上における離散対数門d内をとくことに他ならないことが分かる。

故にDiffie-Hell,am鍵共有(鍵交換)の安全性は離散対数問題の困難さに基づいていることが分かる。

 

現在のところ、安全性を確保するためには、離散対数問題と対応させて、300桁以上の素数pを用意する必要があるとされている。

Image159

Excelで作ったモデル、p=11wwww

基礎数理

最大公約数+拡張ユークリッド・アルゴリズム

a=b*m+r

r=0⇔(def)b|a

 

最大公約数gcd(a,b) or (a,b)

(a,b) == 1 ⇔ 互いに素

 

ユークリッド互除法

ユークリッド互除法-wiki

アルゴリズム

入力を m, n (mn) とする。

  1. n = 0 なら、 m を出力してアルゴリズムを終了する。
  2. nm を割り切るなら、 n を出力してアルゴリズムを終了する。
  3. mn で割った余りを新たに n とし、更に 元のnを新たにm とし 3. に戻る。

上記の手順は「n, m に対して剰余の演算を行うことができる」という仮定だけに依っているので、整数環だけではなく任意のユークリッド整域においても同様にして最大公約因子を求めることができる。

(問題) 1071 と 1029 の最大公約数を求める。

  • 1071 を 1029 で割った余りは 42
  • 1029 を 42 で割った余りは 21
  • 42 を 21 で割った余りは 0

よって、最大公約数は21である。

 

てな説明よりも、実際に組んでみるヨロシ。

function euclidean([int]$m, [int]$n){
    if($m -lt $n){
        $a = $m
        $m = $n
        $n = $a
    }
    while($b -! 0){
        if($m%$n -eq 0){
            return $n
        }
        $a = $n
        $n = $m%$n
        $m = $a
    }
}


eucli.ps1

Image155

 

今回はPowerShellで書いてみました。

ちなみに、はじめてPowerShellでスクリプトを走らせるときにはすこおし設定が必要です。

PowerShellスクリプトの実行セキュリティ・ポリシーを変更する

Image153

やたら横になげえダイアログウインドウで肺を洗濯するとでmatu。

 

定理

2つの整数abに対してd=(a,b)→∃x,y|d=ax+by

このようなxyは一意には決まらん。

なんか経過は良く解らんが・・・

(a,b)を求めるのと同時に与式を満たすx,yも求まるんだと、

これを拡張ユークリッド・アルゴリズムという

と、よくわからんかったが、ここが分かりやすい。

拡張ユークリッド互除法

>拡張ユークリッドの互除法は,不定方程式の解を与えます。例として,不定方程式

>1004*x+1001*y=1

>を解きましょう。 ここで不定方程式とは上の等式を解として整数 (x,y) を考えるものです。またこれを解くとは上の等式を満たす>整数(x, y) のすべての組を求めるものです。

---------------------------------

>拡張ユークリッドの互除法は,整数の合同における逆元を計算します。例として,合同式

>12357 * x ≡ 102 mod 100102

>を解いてみましょう。この合同式を解くとは,x を 12357 倍して,100102 で割ったときの余りが 102 となる整数 x をすべて>求めることです。

 

合同式とフェルマーの小定理

合同⇔def 整数a,bに対してa-bが1よりも大きい自然数nで割り切れるとき、abはnを法として合同であるという

a≡b(mod n)

ex.79≡25(mod 3) ・・・ 79 ? 25 = 54 = 3*18

 

nを1より大きい自然数としたとき、1からn-1までの自然数の中でnと互いに素である数の個数をΦ(n)と表す:オイラー関数

ex.Φ(12)・・・5,7,9,11・・・=4

 

オイラーの定理

素数pに対して

n=p1^e1 * p2^e2 *・・・・* pk^ekとするちょきグーパー

Φ(n) = n(1-1/p1)(1-1/p2)・・・・(1-pk)

=p1^(e1-1) * p2^(e2-1)・・・・ * pk^(ek-1)*(p1-1)(p2-1)・・・(pk-1)

ex.60=2^2 * 3 * 5

Φ(60) = 2^(2-1) * 3^(1-1) * 5^(1-1) * (2-1)(3-1)(5-1)

=2^1*1*1 * 1*2*4 = 16

 

定理

1より大きい自然数nに対して、整数aとnが互いに素であるなら

a^Φ(n) ≡ 1(mod n)

 

こいつを利用すると・・・

7^Φ(60) = 7^16 ≡ 1(mod 60)

 

フェルマーの小定理

特にnが素数の場合・・・aで割れない整数aに対して、以下の合同式が成立

a^(n-1) ≡ 1(mod n)

 

これが暗号となんの関係がとの説明は以下が詳しい

べき乗剰余演算とフェルマーの小定理

てかbcて言語は俺のような使い方をする人間には扱い易そうな言語だな。

導入を検討しよう。

 

有限体

ある演算#が定義された集合Gに対して、以下の小売を満たすとき、Gと演算#の組(G,#)を代数系という。

 

def

代数系が以下の3つの小売を満たすとき、(G、#)あるいは単純にGを群という

1.任意の元abc∈Gに対して(a#b)#c=a#(b#c)

2.任意の元a∈Gに対してe#a=a#e=aなる元e∈Gが存在スルー

3.任意の元a∈Gに対してx#a=a#x=eなる元x∈Gが存在する

eを単位元という。xを逆元という

 

群Gに対して、集合Gの元の個数をこの群の位数といい|G|で表す。

こいつが有限なら有限GUN

#が加法+のときは加法GUN、乗法*の時は乗法群

 

任意の元ab∈Gにたいして、交換速が成立するような群を特に可換群、アベール群(オケツ・テロテロ群)という。

ex.

複素数全体C、実数全体R、整数全体Zは通常加算演算+に対して可換群

 

a^m=a*a*-------*a さらにa^-m=a^-1*--------a^-1

とし、a^0=eとする。

また、a^m=eとなる最小の自然数mを元aの位数という。

群の位数と元の位数

↑フォント綺麗、てか全体的にきれいなページですぅ

 ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄V ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄

526F7A656E204D616964656E2028BFE9C0B1C0D029_123e9b5fb10b_2

群(G,#)において、任意の元a∈Gを用いて

G={g^m:m∈Z}

で表されるときGを巡回群といいgをGの生成元という。

巡回群

 

def

2つの演算が定義された集合Rに関して、(R,+,#)が各演算に対して代数系であり、次の4つの公理を満たすとき(R,+,#)あるいは、単にRを環という。

1.(R,+)は可換群

2.任意の元abc∈Rに対して(a#b)#c=a#(b#c)

3.任意の元abc∈Rに対してa#(b#c)=a#b+a#cおよび(b+c)#a=b#a+c#a

4.乗法に関する単位元1が存在する

 

乗法に関して可換

ab∈Rに対してab=baが成立するとき可換環という。

 

[r]={an+r:m∈Z}={b∈Z:b≡r(mod n)}

この集合[r]をnを法にした整数の剰余類という

代表元

Zn={0,1,2-------,n-1}

を各代表元の集合とする。任意の元ab∈Znに対して、a+bをnで割ったあまりをcとし、a*bをnで割った余りをdとしたとき

a+b≡c(mod n)及び a*b≡d(mod n)

特にこの環をnを法とする整数剰余環という。cf剰余表

剰余環と剰余体

 

なんかだるくなってきたのでココマデ

ブリーフィング

秘密の文章の文字列との組を規則にしたがって文字に置き換えるという方法が取られた

└ 古典暗号

cf.踊る人形、HAL

 

1976 Diffie/Hellman等によって公開鍵配送の発案

→暗号界隈の大きな前進

 

DH鍵共有、RSA暗号、エルガマル暗号 ∈ 公開鍵暗号

 

デジタル署名

 

ハッシュ関数、ゼロ知識証明

 

共通鍵暗号

 

暗号を学ぶ上での基礎知識

├ 余剰演算・冪乗演算

├ ユークリッド・アルゴリズム ・・・ 最大公約数

└ 拡張ユークリッド・アルゴリズ ・・・ 逆元

 

Diffie-Hellman鍵交換 - 楕円曲線

RSA暗号 - 素数の選定方法

エルガマル暗号 - 離散対数問題、計算困難性

ハッシュ関数 - SHA-256

共通鍵暗号 - AES

メッセージ認証コード - 擬似ランダム関数、ユニバーサルハッシュ関数

ゼロ知識証明 - 電子投票、電子送金

TLS、S/MIME、WPA

公開鍵暗号基盤:PKI

電子認証基板、電子認証局、電子証明書、電子署名法

第三者適合評価制度、人間工学

プロフィール

Naka210

Author:Naka210
FC2ブログへようこそ!

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR