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）
You are designing a multi-user OS. In your OS, users $\log$ into their respective accounts using passwords. It is dangerous to store user passwords in a file on the computer, because someone who obtains the file gets access to all passwords. As a solution, you decide to store the username and corresponding password’s hash value in the file called hpasswd. Assume that you use an idealized, perfectly random hash function $h(x)$, i.e $h$ is selected uniformly at random from all functions mapping ${0,1}^*$ to ${0,1}^k$. As always, $h$ is publicly known.
When a user logs in with password $p$, the OS grants access to the user iff $h(p)$ matches the entry for that user in hpasswd. Assume $k=20$ in your OS.
There are some weaknesses in this mechanism of your OS. A collision in the password hash of 2 users, allow them to $\log$ in as each other.
(5 points) Suppose an attacker (a normal user) wishes to log in as the system administrator (the superuser) by trying random passwords (without repeating a guess he has already tried). What is the minimum number of password guesses that the attacker has to try to have a success probability greater than $0.6 \%$.
Solution. The attacker never retries a guess which he has tried before (and since the hash function is public, in a stronger attack he never uses a guess that hashes to a value that he has previously generated). Probability of success after ‘ $t$ ‘ tries $=1-$ Probability of failure after ‘t’ tries. Let $P\left{F_t\right}$ be the probability of the event that the attacker fails after ‘t’ attempts, and let $P\left{S_t\right}$ be the probability of success in ‘t’ attempts. Then, we know that $P\left{S_t\right}=1-P\left{F_t\right}$
$$
\begin{aligned}
& P\left{F_1\right}=\left(2^k-1\right) / 2^k \
& P\left{F_2\right}=\left(\left(2^k-1\right) /\left(2^k\right)\right) \times\left(\left(2^k-2\right) /\left(2^k-1\right)\right)=\left(2^k-2\right) / 2^k \
& \vdots \
& P\left{F_t\right}=\left(1-t / 2^k\right) \
& P\left{S_t\right}=1-P\left{F_t\right}=t / 2^k
\end{aligned}
$$
$$
\begin{aligned}
& P\left{F_t\right}=\left(1-t / 2^k\right) \
& P\left{S_t\right}=1-P\left{F_t\right}=t / 2^k
\end{aligned}
$$
For $P\left{S_t\right}>0.006$,
$$
t>0.006 * 2^k
$$
Substituting $\mathrm{k}=20$,
$$
t=2^{12.62}=6295.04 \text {. }
$$
The answer is approximately 6295
(5 points) You want to limit is the probability of user password collisions, to below $20 \%$ in your design. That is, the probability of any two users’ password hashes matching should be below $20 \%$. What is the maximum number of users (n) you should allow in your OS?
Solution. . Let the probability of choosing ‘ $n$ ‘ distinct passwords for each of the ‘ $n$ ‘ users are added, be denoted by the variable $A_n$
$$
P\left{A_n\right}=\left(1-1 / 2^k\right) *\left(1-2 / 2^k\right) *\left(1-3 / 2^k\right) \ldots\left(1-(n-1) / 2^k\right) .
$$
In this question, you want to ensure $1-P\left{A_n\right}$ to be lesser than 0.2 .
$$
\begin{aligned}
& 1-P\left{A_n\right}<0.2 \ & P\left{A_n\right}>0.8
\end{aligned}
$$
Using the approximation, $e^x>1+x$, when $|x|<1$, $$ \begin{aligned} & e^{-1 / 2^k} e^{-2 / 2^k} \ldots e^{-(n-1) / 2^k}>0.8 \
& e^{-\sum_{i=1}^{n-1}\left(i / 2^k\right)}>0.8
\end{aligned}
$$
$$
e^{-n(n-1) / 2^{k+1}}>0.8
$$
Taking natural logarithm on both sides,
$$
-n(n-1) /\left(2^{k+1}\right)>-0.223
$$
For $k=20$,
$$
n<685 \text { (approximately). }
$$
What is non-repudiation?
Solution. Non-repudiation is the concept of ensuring that a party in a dispute cannot repudiate, or refute the validity of a statement or contract.
(7 points) Suppose Alice has to sign a contract with Mallory using an RSA signature where, the signature is computed by $s=(h(m))^d \bmod N$ ( $d$ is Alice’s private key). Assume that the hash function is an idealized, perfectly random hash function $h(x)$, i.e $h$ is selected uniformly at random from all functions mapping ${0,1}^*$ to ${0,1}^k$, and $h$ is publicly known. Mallory has managed to find 40 distinct places where he can make a slight change in the contract: adding a space at the end of line, adding a comma, replacing with equivalent words (like replacing “agreed to pay” with “is obliged to pay”), etc. Surely, Alice does not object any such minor change in the contract and is willing to sign a contract with any of these minor changes.
(2 points) How many possible versions of the contract can Mallory generate that Alice would be willing to sign?
Solution. For each slight change, Mallory can choose to use it or not. There are 40 such changes. So, Mallory can generate $2^{40}$ contracts that Alice will be willing to sign.
(3 points ) Mallory creates a fraudulent contract reflecting a substantial increase in amount that Alice owes to Mallory. He computes the hash of the fraudulent contract as $h(f)$ and finds a version of the good contract that hashes to the same value $h(f)$. What is a minimum safe output size for the hash function (i.e $k=$ ?) to make these collisions unlikely? (An approximate answer with appropriate reasoning is acceptable. You need not show any calculations to get ‘ $k$ ‘.)
Solution. Given that Mallory was able to compute $2^{40}$ different versions of the good contract, we compute how likely is it that one of them hashes to the hash value of his fraudulent contract. Let the size of the hash output be ‘ $k$ ‘ bits.
The probability that the first good version hashes to the fraudulent one, is $\left(1 / 2^k\right)$. The probability that the first good version does not hash to the same hash as the fraudulent one is $\left(1-\left(1 / 2^k\right)\right)$. Therefore, the probability that none of the $2^{40}$ good contracts hash to the same value as the hash of the fraudulent case, is $\left(1-1 / 2^k\right)^{2^{40}}$. From this it follows that the probability that atleast one of the $2^{40}$ versions has the same hash as the fraudulent one is $1-\left(1-1 / 2^k\right)^{260}$.
You can choose how unlikely the event of such collisions should be. For $k=40$, this probability becomes $63 \%$. For $k=41$, this becomes nearly $40 \%$. For $k>50$, the probability is less than $0.1 \%$.
MY-ASSIGNMENTEXPERT™可以为您提供 sydney MATH2088 Cryptography密码学的代写代考和辅导服务！
