MY-ASSIGNMENTEXPERT™可以为您提供 sydney MATH2088 Cryptography密码学的代写代考和辅导服务！
这是悉尼大学 密码学课程的代写成功案例。
MATH2088课程简介
Cryptography is the branch of mathematics that provides the techniques for confidential exchange of information sent via possibly insecure channels. This unit introduces the tools from elementary number theory that are needed to understand the mathematics underlying the most commonly used modern public key cryptosystems. Topics include the Euclidean Algorithm, Fermat’s Little Theorem, the Chinese Remainder Theorem, Mobius Inversion, the RSA Cryptosystem, the Elgamal Cryptosystem and the Diffie-Hellman Protocol. Issues of computational complexity are also discussed.
Prerequisites
At the completion of this unit, you should be able to:
- LO1. understand and use the basic terminology of number theory and cryptography
- LO2. carry out simple number-theoretic computations either with a calculator or using MAGMA
- LO3. apply standard number-theoretic algorithms
- LO4. understand and use some classical and number-theoretic cryptosystems
- LO5. apply standard methods to attack some classical cryptosystems
- LO6. understand the theory underlying number-theoretic algorithms and cryptosystems, including the general properties of primes, prime factorisation, modular arithmetic, divisors and multiplicative functions, powers and discrete logarithms.
MATH2088 Cryptography HELP（EXAM HELP， ONLINE TUTOR）
Extra Credit (5 points) Diffie-Hellman key exchange (DHKE).
Recall from class that DHKE proceeds as follows.
Step 1. Alice selects a large prime number $p$ and a multiplicative generator $\alpha(\bmod p)$. Both $p$ and $\alpha$ are made public.
Step 2. Alice picks a secret random $x$, with $1 \leq x \leq(p-2)$. She sends $M_A=\alpha^x(\bmod$ $p)$.
Step 3. Bob picks a secret random $y$, with $1 \leq y \leq(p-2)$. She sends $M_B=\alpha^y(\bmod$ $p)$.
Step 4. Using the received messages, Bob and Alice compute the shared session key $K$. Alice calculates $K$ with the knowledge of her secret and Bob’s message, by computing $M_B{ }^x(\bmod p)$. Similarly, Bob computes $M_A{ }^y(\bmod p)$.
Here is man-in-the-middle attack on DHKE different from the one studied in class. This version of the man-in-the-middle attack differs from the one seen in class, as it has the “advantage” that Eve does not have to intercept and retransmit all the messages between Alice and Bob.
Suppose Eve discovers that $p=M q+1$, where $\mathrm{q}$ is an integer and $\mathrm{M}$ is small. Eve intercepts $\alpha^x(\bmod p)$ and $\alpha^y(\bmod p)$ sent by Alice and Bob in steps 2 and 3 respectively. Eve sends Bob $\left(\alpha^x\right)^q(\bmod p)$ as message $M_A$ in step 2 , and sends Alice $\left(\alpha^y\right)^q(\bmod p)$ in step 3. Step 4 proceeds as described, but using the modified values of $M_A$ and $M_B$.
(2 points) Show that the Alice and Bob calculate the same key $K^{\prime}$.
Solution.
Alice computes $K^{\prime}$ as $\left(M_B\right)^x(\bmod p)$. Eve tampers sending $\left(\alpha^y\right)^q(\bmod p)$ as $M_B$. So Alice computes $\left(\left(\alpha^y\right)^q\right)^x(\bmod p)$ as $K^{\prime}$, which is $\alpha^{x y q}(\bmod p)$. Similary, Bob computes $K^{\prime}$ as $\left(M_A\right)^y(\bmod p)$. Eve tampers sending $\left(\alpha^x\right)^q(\bmod p)$ as $M_A$. Similary, Bob computes $K^{\prime}$ as $\left(\left(\alpha^x\right)^q\right)^y(\bmod p)$, which is same $K^{\prime}$ as what Alice computes $\left(\alpha^{x y q}\right.$ $(\bmod p))$
(3 points) Show that there are only M possible values for $K^{\prime}$, so Eve may find $K^{\prime}$ by exhaustive search.
Hint. Recall that the generator $\alpha$ is specially chosen. It generates all elements between 1 and $p$ under the exponentiation operation without repeats. Therefore, $\alpha^{(p-1)}=1(\bmod$ p).
Solution. The exponent of $\alpha$ that results in computation of $K^{\prime}$ is $(x y q)$ – let us term this value as $t$. We know that $(p-1)$ is $M q$. There must exist some $n, r$ such that $x y=$ $n M+r$, where $r=(x y)(\bmod M)$. So, we get :
$$
\begin{aligned}
& K^{\prime}=\alpha^{x y q}(\bmod p) \
& =\alpha^{(n M+r) q}(\bmod p) \
& =\alpha^{(n M q+r q)}(\bmod p) \
& =\left(\alpha^{n M q}\right)\left(\alpha^{r q}\right)(\bmod p) \
& =\left(\left(\alpha^{M q}\right)^n\right)\left(\alpha^{r q}\right)(\bmod p)
\end{aligned}
$$
By Fermat’s Theorem (also restated as hint) $\alpha^{M q}$ is $1(\bmod p)$, $=(1)\left(\alpha^{r q}\right)(\bmod p)$
Since $r$ can only take values between 0 and $(M-1)$, the exponent has to be one of $M$ multiples of $q$. Eve knows $q$ and $M$ is small, so she can exhaustively search for $K^{\prime}$.
In this section we study secret sharing schemes.
Definition of $(n, t)$ threshold secret sharing scheme. A $(n, t)$ threshold secret sharing scheme is one where the secret can be efficiently computed given $t$ of the $n$ shares, but any $(t-1)$ shares reveal no information about the secret.
Shamir polynomial scheme. (4 points) Suppose we using the scheme using polynomials module a prime $p$, as described in class and the lecture notes. This scheme is called Shamir polynomial scheme.
(3 points) You have to setup a $(30,2)$ Shamir scheme, working mod prime $p=101$. Two of the shares are $(1,13)$ and $(3,12)$. Another person received the share $(2, )$, but the part denoted by $$ is unreadable. What is the correct value of $*$ ?
Solution. Let the polynomial be $M+S_1 x(\bmod 101)$. The polynomial has degree 1 because we need 2 shares to be sufficient to reconstruct the secret $M$.
Substituting for the two given shares
$$
\begin{aligned}
& M+1 \times S_1=13(\bmod 101) \
& M+3 \times S_1=12(\bmod 101)
\end{aligned}
$$
Writing it in matrix form,
$$
\left(\begin{array}{ll}
1 & 1 \
1 & 3
\end{array}\right)\left(\begin{array}{l}
M \
S 1
\end{array}\right)=\left(\begin{array}{l}
13 \
12
\end{array}\right)(\bmod 101)
$$
Solving the set of equations, we get,
$$
\left(\begin{array}{l}
M \
S 1
\end{array}\right)=\left(\begin{array}{c}
27 / 2 \
-1 / 2
\end{array}\right)(\bmod 101)
$$
The result is :
$$
\left(\begin{array}{l}
M \
S 1
\end{array}\right)=\left(\begin{array}{c}
27 / 2 \
-1 / 2
\end{array}\right)(\bmod 101)
$$
We are working $(\bmod 101)$, and we need the coefficients $\bmod 101$. Since we know that $1 / 2 \equiv 51(\bmod 101)$, we can replace $1 / 2(\bmod 101)$ with 51 . Therefore,
$M \equiv 27(1 / 2)(\bmod 101) \equiv 27(51)(\bmod 101) \equiv 64(\bmod 101)$.
Similarly,
$$
S_1 \equiv-51(\bmod 101)
$$
Polynomial is thus,
$64-51 x(\bmod 101)$
The third share is simply an evaluation of this polynomial at $x=2$, which is 63 .
Extensibility. (1 points) It is easy to extend Shamir’s polynomial $\bmod p$ scheme, to add new users. Show how could you extend a $(n, t)$ Shamir scheme to a $(n+1, t)$ scheme that includes an extra user, without changing the shares for existing $n$ users.
Solution. Simply evaluate the polynomial at another point $x_{n+1}$, and give $\left(x_{n+1}, f\left(x_{n+1}\right)\right)$ as the new share. No changes to existing shares are needed for this.
MY-ASSIGNMENTEXPERT™可以为您提供 sydney MATH2088 Cryptography密码学的代写代考和辅导服务！
