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

12 不確定是否完整,

就是第二個部份的證明不知道要不要寫,

如果需要就要再補上去,

不確定是否有打錯或是筆記操錯的地方有錯請指正,thanks

1. 寫出並證明費碼定理

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

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

2. 寫出並證明尤拉定理

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

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 <= 同乘反元素[X1*X2*X3..XΦ(n)]-1

1 mod n= aΦ(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

1

2

0

0

1

2

1

1

2

3

2

2

3

4

乘法

0

1

2

0

0

0

0

1

0

1

2

2

0

2

4

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

=a^q 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

分類未分類

發表迴響

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