ComSec作业四：Diffie-Hellman

ComSec作业四：Diffie-Hellman

10.1 Alice and Bob use the Diffie-Hellman key exchange technique with a common prime $q=157$ and a primitive root $\alpha =5$.

If Alice has a private key $X_A=15$, find her public key $Y_A$

Y A = α X A m o d    q = 5 15 m o d    157 = 79 YA=αXAmodq=515mod157=79

YA​=αXA​modq=515mod157=79​

If Bob has a private key $X_B=27$, find his public key $Y_B$.

Y A = α X B m o d    q = 5 27 m o d    157 = 65 YA=αXBmodq=527mod157=65

YA​=αXB​modq=527mod157=65​

What is the shared secret key between Alice and Bob?

$$sharedsecretkey=Y_A^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}q=Y_B^{X_A}\mathrm{m}\mathrm{o}\mathrm{d}q=79^{27}\mathrm{m}\mathrm{o}\mathrm{d}q=79^{27}\mathrm{m}\mathrm{o}\mathrm{d}q=65^{15}\mathrm{m}\mathrm{o}\mathrm{d}q=78$$

10.2 Alice and Bob use the Diffie-Hellman key exchange technique with a common prime $q=23$ and a primitive root $\alpha =5$.

If Bob has a public key $Y_B=10$, what is Bob’s private key $X_B$?

由于q比较小，可以枚举n，得到下列的表

查表可知当${\alpha }^n\mathrm{m}\mathrm{o}\mathrm{d}q=10$的时候，$n=3$，所以$X_B=3$

If Alice has a public key $Y_A=8$, what is the shared key $K$ with Bob?

$$K=Y_A^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}q=8^3\mathrm{m}\mathrm{o}\mathrm{d}23=6$$

Show that 5 is a primitive root of 23.

$$\begin{gathered} \varphi (23)=22=11\times 2 \\ 又由于5^{11}\mathrm{m}\mathrm{o}\mathrm{d}=22\ne 1 \\ {5}^2\mathrm{m}\mathrm{o}\mathrm{d}=2\ne 1所以5是23的原根 \end{gathered}$$

ComSec作业五：椭圆曲线

10.12 Consider the elliptic curve $E_7(2,1)$; that is, the curve is defined by $y^2=x^3+2x+1$with a modulus of $p=7$. Determine all of the points in $E_7(2,1)$. Hint: Start by calculating the right-hand side of the equation for all values of $x$.

椭圆曲线$E_7(2,1)$，包含的所有的点为$(0,0),(1,3),(3,3),(5,2)$

10.13 What are the negatives of the following elliptic curve points over $Z_7$? $P=(3,5)$;$Q=(2,5)$;$R=(5,0)$.

$$\begin{gathered} -P=(3,2) \\ -Q=(2,2) \\ -R=(5,0) \end{gathered}$$

10.14 For $E_{11}(1,7)$, consider the point $G=(3,2)$. Compute the multiple of $G$ from $2G$ through $13G$.

2 G = G + G { δ = 3 x ′ 2 + a 2 y ′ m o d    p = 7 x = δ 2 − 2 ∗ x ′ m o d    p = 10 y = δ ∗ ( x ′ − x ) − y ′ m o d    p = 4 } 2 G = ( 8 , 1 ) 3 G = 2 G + G { δ = x 2 − x 1 y 2 − y 1 m o d    p = 5 x = δ 2 − x 1 − x 2 m o d    p = 1 y = δ ∗ ( x G − x ) − y G m o d    p = 8 } 3 G = ( 3 , 7 ) 2G=G+G\left\{δ=3x′2+a2y′modp=7x=δ2−2∗x′modp=10y=δ∗(x′−x)−y′modp=4

\right\}2G=(8,1)\\ 3G=2G+G\left\{δ=x2−x1y2−y1modp=5x=δ2−x1−x2modp=1y=δ∗(xG−x)−yGmodp=8 \right\}3G=(3,7)\\ 2G=G+G⎩⎨⎧​δ=2y′3x′2+a​modp=7x=δ2−2∗x′modp=10y=δ∗(x′−x)−y′modp=4​⎭⎬⎫​2G=(8,1)3G=2G+G⎩⎨⎧​δ=y2−y1x2−x1​modp=5x=δ2−x1​−x2​modp=1y=δ∗(xG​−x)−yG​modp=8​⎭⎬⎫​3G=(3,7)

依次类推可以得到下表

ComSec作业六：Hash

11.1What characteristics are needed in a secure hash function?

单向性，抗碰撞性

11.2What is the difference between weak and strong collision resistance?

弱碰撞性：在已知$x$的和$H(x)$的情况下，寻找一个不等于$x$的$x^{\prime }$使得$H(x)=H(x^{\prime })$成立

强碰撞性：任意找两个不相等的$x,x^{\prime }$，使得$H(x)=H(x^{\prime })$

113What is the role of a compression function in a hash function?

将任意长度的报文压缩成为一个较短的定长输出报文的函数

11.4What is the difference between little-endian and big-endian format?

little-endian：小端序，指的是计算机存储一个数的时候，该数的高字节存在高地址处，低字节存在低地址处

例子：比如0x1234，在计算机中存储为[0x34 0x12]（向右为高地址）

big-endian：大端序，指的是计算机存储一个数的时候，该数的高字节存在低地址处，低字节存在高地址处

例子：比如0x1234，在计算机中存储为[0x12 0x34]（向右为高地址）

11.5What basic arithmetical and logical functions are used in SHA?

加法，模，循环移位，AND、OR、NOT和XOR。

11.6Describe the set of criteria used by NIST to evaluate SHA-3 candidates.

首先需要满足Hash的基本性质：单向性和抗碰撞性

其次就是算法实现的逻辑门更少，效率更加的高

之后就是要抗已知的所有攻击方法的攻击

11.7Define the term sponge construction.

海绵结构分为吸水阶段和挤压阶段，和现实生活中的海绵相类似

吸水阶段就是接受输入，根据输入调整隐藏的state，挤压阶段就是更具隐藏的state计算出Hash的结果

吸水阶段：初始化state->与输入的信息XOR->经过压缩函数->与输入的信息XOR->经过压缩函数->…

挤压阶段：经过压缩函数->挤压出输出1->经过压缩函数->挤压出输出2->…

11.8Briefly describe the internal structure of the iteration function $f$.

$f$函数也称为搅拌函数，过程是经过5个阶段$\theta ,\rho ,\pi ,\chi ,\iota$，可以将隐藏的state中的bit打乱。

11.9List and briefly describe the step functions that comprise the iteration function $f$.

step $\theta$

$$a[x][y][z]\leftarrow a[x][y][z]+\sum _{y^{\prime }=0}^{4}a[x-1][y^{\prime }][z]+\sum _{y^{\prime }=0}^{4}a[x+1][y^{\prime }][z-1]$$

step $\rho$

a [ x ] [ y ] [ z ] ← a [ x ] [ y ] [ z − ( t + 1 ) ( t + 2 ) / 2 ] w i t h    t    s a t i s f y i n g    0 ≤ t ≤ 24    a n d ( 0 1 2 3 ) t ( 1 0 ) = ( x y ) i n    G F ( 5 ) 2 × 2 o r    t = − 1    i f    x = y = 0 a[x][y][z]\leftarrow a[x][y][z - (t+1)(t+2)/2]\\ with\space\space t\space\space satisfying \space\space 0\le t\le 24\space\space and \left(0123

\right)^t \left(10\right)=\left(xy\right) in \space\space GF(5)^{2\times2}\\ or \space\space t=-1\space\space if\space\space x=y=0 a[x][y][z]←a[x][y][z−(t+1)(t+2)/2]with  t  satisfying  0≤t≤24  and(02​13​)t(10​)=(xy​)in  GF(5)2×2or  t=−1  if  x=y=0

step $\pi$

a [ x ] [ y ] ← a [ x ′ ] [ y ′ ] , w i t h    ( x y ) = ( 0 1 2 3 ) ( x ′ y ′ ) , a[x][y]\leftarrow a[x'][y'], with\space\space\left(xy

\right)=\left(0123\right)\left(x′y′\right), a[x][y]←a[x′][y′],with  (xy​)=(02​13​)(x′y′​),

step $\chi$

$$a[x]\leftarrow a[x]+(a[x+1]+1)a[x+2]$$

step $\iota$

$$a\leftarrow a+RC[i_r]$$