[文件] 電子交易安全 期中考 -2

之前版本有幾個錯誤先修改了,就重寄一份希望不會打擾到大家 ^^;;
檔案中紅字為修改過部分。
第一題:補上第二個式子的證明
第二題:第二個式子筆記沒抄到不知道有哪為好心的人士幫忙補上 ,,
第五題: Z3 的三個表應該是寫錯了,再mod 3 之下 應該不會有大於三的數 (感謝士軒的提醒)

1. 寫出並證明費碼定理

Fermat 定理 ,當 (a,p)=1 (ap互質)

a. ap-1 = 1 mod p

證明:在Zp 之中 ap互質

[1*2*3..*(p-1)]modp={(1*a)(2a)(3a)…[a(p-1)]}modp <-同成a係數只是重排

={a(p-1)*[1*2*3..*(p-1)]}modp <-右邊將a提出成為ap-1次方

因為 ap互質所以存在反元素將兩邊同乘反元素 [1*2*3..*(p-1)]-1 消掉

所以 1modp = a(p-1)modp -> ap-1 = 1 mod p

b. ap = a mod p

證明:假設 (a,p)1 ap的倍數 並可寫成apa mod p

apa mod p

ap –a (a-a) mod p (兩邊同減a)

a(ap-1 –1) 0 mod p (左邊將a提出)

a(ap-1 –1) 0 mod p

p不整除 a p不整除 (ap-1 –1)

與假設不符合所以得證 ap=a mod p

2. 寫出並證明尤拉定理

尤拉定理 ,當 (a,p)=1 (ap互質)

a. aΦ(n)1 mod n

[X1*X2*X3..XΦ(n)]mod n =[(X1modn)(X2modn)(X3modn)…[XΦ(n)]modn] modn

([(X1modn)(X2modn)(X3modn)…[XΦ(n)]modn] modn 同乘a等於係數重排)

= [aX1modn aX2modn aX3modn …. [aXΦ(n)]modn ] modn (右邊係數同乘a)

=aΦ(n) [X1*X2*X3..XΦ(n)]modn (右邊將a提出)

1 mod n= aΦ(n) (左右同乘反元素[X1*X2*X3..XΦ(n)]-1)

得證:aΦ(n)1 mod n

b. (a,n)1 且(a<n) aΦ(n1)a mod n

3. 寫出並證明RSA所用的基本定理

RAS基本定理:m代表一個訊息,n=p*q mΦ(n)+1m mod n

a. (m,n) = 1 根據尤拉定理 aΦ(n) 1 mod n

mΦ(n)+1m mod n(兩邊同乘m後得證 )

b. (m,n)1 所以 b-1 m = C1p b-2 m = C2q

b-1 m = C1 * p , (m , q) = 1 根據尤拉定理可寫為 

mΦ(q) 1 mod q

[mΦ(q)] Φ(p) 1Φ(p)mod q ( 兩邊同乘Φ(p) 次方)

mΦ(n) = 1 mod q (因為 n =p*q1的任何次方還是1 )

mΦ(n) = 1+kq (存在一整數k1modq = 1+kq)

mΦ(n+1) =m + kqm (兩邊同乘m)

mΦ(n+1) = m + kqC1p (m =C1*p代入)

mΦ(n+1) = m + kC1n (其中 n=p*q代入)

mΦ(n+1) = m mod n (m+kC1n等於 m mod n)

b-2 m = C2*q b-1 可證 mΦ(n+1) = m mod n

4. 證明 (a+b) mod n = [(a mod n) + (b mod n)] mod n

假設 (a mod n)= Ra (b mod n) = Rb , a = Ra + j n ; b = Rb + kn

(a+b) mod n = [(Ra+jn )+(Rb+kn) ]mod n

= [Ra+Rb+ (j+k)n ] mod n

=(Ra+Rb) mod n <- 根據假設 (a mod n)= Ra (b mod n) = Rb帶入

= [(a mod n )+ (b mod n )] mod n

5. 何謂一個體, Z3 的三個表

體:除了0之外,有兩個交換環(加法和乘法),加法和乘分具分配律,並有不具有0的真因子,除0之外皆有反元素

加法

0

1

2

0

0

1

2

1

1

2

0

2

2

0

1

乘法

0

1

2

0

0

0

0

1

0

1

2

2

0

2

1

W

-w

w-1

0

0

0

1

2

1

2

1

2

6. Z=kΦ(n)+q az = ? mod n

az =a kΦ(n)+q = [aΦ(n)]k * aq

= {[(aΦ(n))k modn ][aqmodn]}modn (根據尤拉 aΦ(n)1modn )

= {(1modn)(aqmodn)}modn

=aq modn

7. 說明 discrete logarithm problem

離散對數依照方程式: y=gx mod p

給定g x p 可以很快算出 y ,但是只給 y g p 則很難算出 x的值。

8. Euclid algorithm GCD(86,32)

GCD(86,32)

86=2*32+22 GCD(32,22)

32=1*22+10 GCD(22,10)

22=2*10+2 GCD(10,2)

10=2*5+0 GCD(86,32)=2

分類未分類

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *