---
tags : ntu,Cryptography
---
密碼學 Cryptography)
Homework #1 (Due date: 10/03/2019)
=====
r08921a09 郭羿昇
### Question 1.
**f :** Generally speaking, the sentece "the best known algorithm takes at least exponential-time" means that the best algorithm has exponential time complexity **on the worst case**.
So, we may have a lot of y, and for these y, Computing $f^{-1}(y)$ is polynomial time computable.
Therefore, we can't use f as a one-way function.
**g :** Yes. In Practice, security requires hardness on most cases or at least average-case hardness. In fact no real one-way funciton has been found so far.
### Question 2.
(a) Suppose a = 4 and b =6
$E([a, b], 0)=4\times0+6=6\ mod\ 26$
$E([a, b], 13)=(4\times13+6)\ mod\ 26=6\ mod\ 26$

(b) based on part (a):
$𝐸([𝑎,𝑏],0)=𝐸([𝑎,𝑏],13)=6$
both plaintexts, 0 and 13 maps into ciphertext,6, so decryption is impossible.

\(c\) Which values of a and b are allowed for a one-to-one affine cipher?
abitrary $b$ and $\{a \in Z \ |\ gcd(a,26)=1\}$

### Question 3.
we can view this encryption as vigenere with key length=26*t and do the same things in the slides to break vigenere cipher
### Question 4.
substitution: 25 letters (maybe A-Y)
Caesar:1 letter
Vigenere: same letters with length same as key length

### Question 5.
* A : only 2. Because 𝜙(𝑛) is even for all 𝑛≥3.

* B :
proof:
$Lemma1: 𝜙(𝑛)=𝑛∏𝑝|𝑛(1−1/𝑝)$
$Lemma2: 𝜙(𝑚𝑛)=𝜙(𝑚)𝜙(𝑛)\frac{𝑑}{𝜙(𝑑)}, where\ 𝑑=(𝑚,𝑛). (Deduced from Lemma 1)$
Since $𝑎|𝑏$ we have $𝑏=𝑎𝑐$ where $1≤𝑐≤𝑏$. If $𝑐=𝑏$ then $𝑎=1$ and $𝜙(𝑎)|𝜙(𝑏)$ is trivially satisfied. Therefore, assume $𝑐<𝑏$. From Lemma2 we have $𝜙(𝑏)=𝜙(𝑎𝑐)=𝜙(𝑎)𝜙(𝑐)\frac{𝑑}{𝜙(𝑑)}=𝑑𝜙(𝑎)\frac{𝜙(𝑐)}{𝜙(𝑑)}(\#)$

### Question 6.
by Euler’s Theorem:
$a^{\phi(n)-1}a= 1\ (mod\ n)$ Then
$a^{-1}=a^{\phi(n)-1}mod\ n$
### Question 7.
$5^{1213}\ mod\ 13 =(5^{4})^{303}\times5 \ mod\ 13=1^{303}\times5 \ mod\ 13$
$=5\ mod\ 13$
### Question 8.
1. G is not cyclic because there isn't a g $\in$ $Z_{21}^*$ such that order(g) = 21
2. H={1, 2, 4, 8, 11, 16} with order 6
3. 2 is the generator of H

### Question 9.
Choose $𝑥∈ℤ_N^*$ at random.
Pass its square $𝑥^2$ to 𝑆; call the result 𝑦.
If $𝑥≡±𝑦(mod𝑁)$, we were unlucky: Start over with a new 𝑥.
At this point, we know from
$𝑥^2≡𝑦^2(mod𝑁)$
that
$𝑥^2−𝑦^2=(𝑥+𝑦)(𝑥−𝑦)$
is a non-zero multiple of 𝑁 while neither $𝑥+𝑦$ nor $𝑥−𝑦$ alone is, hence we can recover a factor of 𝑁 by computing
$gcd(𝑥+𝑦,𝑁)$.

### Question 10.
$(=>)$ g is a generator of Fp
by Fermat's little theorem
$g^{p-1}$ = $1$ $(mod\ p)$
by definition of generator
$g^1,g^2,...,g^{p-1}\neq1$
So $g^q$ ≠ 1 (mod p) for all divisors q of p – 1

$(<=)$ $g^{p-1}$ = 1 (mod p) and $g^q$ ≠ 1 (mod p) for all divisors q of p–1.
assume g is not a generator:
Then there exist a smallest k $\in$ (0,p-1) such that $g^k=1$
case g $\nmid$ p-1:
$p-1=qk+r\ for\ 0<q<k$ and $g^{p-1}=(g^k)^qg^r=1
\\\because g^k=1 \therefore g^r=1(mod p)$

$(\Rightarrow\Leftarrow)$

case g $\mid$ p-1:
$g^k=1\ mod\ p$ $(
\Rightarrow\Leftarrow)$