# Tính chia hết
Các số tự nhiên là các số 1,2,.... Các số nguyên là các số tự nhiên, số 0 và các số âm -1, -2, -3,... Số nguyên $a$ chia hết cho số nguyên $b$ nếu tồn tại số nguyên c mà $a=bc$ . Khi đó ta viết $b\mid a$ và nói $b$ là ước số của $a$, $a$ là bội số của $b$. Ta viết $b \nmid a$ nếu $b$ không là ước số của $a$.
**Bài tập 1 :** Chứng minh nếu $a$ và $b$ là hai số tự nhiên thì $a!b!\mid (a+b)!$
**Chứng minh**.
Dễ thấy tính chất đúng nếu ít nhất một trong 2 số $a$ và $b$ bằng $1$.
Giả sử với một số $n > 2$ , bài toán đúng với mọi cặp hai số tự nhiên có tổng không lớn hơn $n$. Xét $a+b=n+1$, do bài toán đúng với mọi cặp hai số tự nhiên có tổng bằng $n$ và $a+b-1=n$. Nên $(a-1)!b!\mid (a+b-1)!$ và $a!(b-1)!\mid (a+b-1)!$ mà $(a+b)! = (a+b-1)!(a+b) =(a+b-1)!a + (a+b-1)!b$.
Lại có $(a-1)!b!\mid (a+b-1)!$ nên $a!b!\mid (a+b-1)!a$ và $a!b!\mid (a+b-1)!b$.
Cộng lại ta có ${a!b!\mid (a+b-1)!a + (a+b-1)!b}$ hay ${a!b!\mid (a+b)!}$.Vậy đúng với hai số tự nhiên có tổng bằng $n+1$.Vậy bài toán đúng với mọi $a$ và $b$ .
**Bài tập 2** Chứng minh rằng nếu là tập hợp $S$ gồm các số tự nhiên mà tổng và hiệu của hai phần tử bất kỳ thuộc $S$ cũng là phần tử thuộc $S$ , giả sử $d$ là số tự nhiên nhỏ nhất thuộc $S$ , thì là tập hợp các bội số tự nhiên của $d$ (ở đây các hiệu được lấy theo hai phần tử phân biệt và theo thứ tự số lớn trừ số bé)
**Chứng minh**
Theo giả thiết thì tổng 2 số tự nhiên bất kì thuộc tập $S$ nên tổng các phần tử cũng thuộc $S$ . Trường hợp đặc biệt các tất cả các phần tử đều bằng $d$ thì các số có dạng $kd$ với $k=1,2,...$ cũng thuộc $S$.
Mặt khác giả sử $h$ là một phần tử thuộc $S$ và $h$ không phải bội của $d$ khi đó ta chia $h$ cho $d$ ,ta có $h=qd+r,r<d$. Nếu $q = 0$ thì $h=r$ mà $r<d$ nên $h<d$ mâu thuẫn với giả thiết $d$ là số tự nhiên nhỏ nhất trong tập $S$.Vậy $qd$ là bội của $d$ thuộc $S$. Mặt khác $r = h-qd$ là hiệu của hai số tự nhiên thuộc tập $S$ nên $r$ cũng phải thuộc $S$ mà $r<d$ mâu thuẫn với giả thiết $d$ là số tự nhiên nhỏ nhất thuộc $S$.
Vậy mọi phần tử của $S$ đều là bội số của $d$.
**Các tính chất**
1. Nếu $a\mid b$ và $b\mid c$ thì $a\mid c$
2. Nếu $a\mid b$ và $b\mid a$ thì $a = b$ hoặc $a=-b$
3. Nếu $a\mid b$ và $a\mid c$ thì $a\mid(b+c)$ và $a\mid(b-c)$
# Bội chung nhỏ nhất
**Định lý 1.** Mọi bội số chung của các số tự nhiên ${a_1},{a_2},...,{a_n}$ đều chia hết cho bội số chung nhỏ nhất của các số đó.
**Chứng minh**
Giả sử tồn tại bội chung $M$ của các số tự nhiên ${a_i},i=1,2,...,n$ mà không chia hết cho bội chung nhỏ nhất $L$ của các số đó , ${M=qL+r}$ với $r<L$ , $r=M-qL$. Mà $M,L$ đều là bội của các số tự nhiên $a_i,i=1,2,...n$ nên tồn tại $x_i,y_i$ sao cho $M=x_ia_i$ và $L=y_ia_i$. Do đó $r=(x_i-qy_i)a_i$ suy ra $a_i\mid r$ với mọi $i=1,2,...,n$. Suy ra $r$ là bội chung của $a_i,i=1,2,...,n$ mà $r<L$ vô lí vì $L$ là bội chung nhỏ nhất của $a_i,i=1,2,...,n$.
# Ước chung lớn nhất
**Định lí 2** Nếu $S$ là tập hợp (hữu hạn hay vô hạn) các số nguyên mà trong đó có ít nhất một phần tử khác 0 thì tồn tại ước số chung lớn nhất của các số nguyên thuộc $S$ . Hơn nữa ước số chung lớn nhất này chia hết cho mọi ước số chung khác của các số nguyên thuộc $S$.
# Các số nguyên tố cùng nhau
Hai số $a,b$ được gọi là hai số nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng $1$ ($GCD(a,b)=1$)
**Định lí 3** Khi chia các số nguyên $a$ và $b$ cho ước số chung lớn nhất của chúng thì ta nhận được các số nguyên tố cùng nhau
**Chứng minh**
Giả sử $GCD(a,b)=d$ Đặt ${a_1 = a \div d},{b_1=b\div d}$.Giả sử $a_1$ và $b_1$ không phải là hai số nguyên tố cùng nhau tức $GCD(a_1,b_1) = d_1 > 1$ , lại có ${a_2=a_1\div d_1},{b_2=b_1\div d_1}$. Khi đó $a = dd_1a_2, b = dd_1b_2$. Suy ra $GCD(a,b)=dd_1 > d$ vô lí vì $d_1$ > 1 . Vậy $d_1$ phải bằng $1$ hay $a,b$ là hai số nguyên tố cùng nhau.
**Định lí $3^a$** Khi chia các số nguyên $a_1,a_2,...,a_n$ cho ước số chung lớn nhất của chúng thì ta nhận được các số nguyên có ước chung lớn nhất là 1.
**Bài tập 1** Chứng minh rằng nếu $n$ và $m$ là các số tự nhiên, $m$ lẻ, thì $GCD(2^m-1,2^n+1)=1$.
**Chứng minh**
Giả sử $GCD(2^m-1,2^n+1)=d$ ,khi đó thì $d$ là một số lẻ (vì là ước chung lớn nhất của 2 số lẻ) và $2^m-1=kd$ và $2^n+1=hd$. Suy ra $2^m=kd+1$ và $2^n=hd-1$ suy ra $2^{mn}=(kd+1)^n = \displaystyle \sum_{i=1}^{n}\binom{i}{n}(kd)^i*1^{n-i} = ud+1$ và $2^{nm}=(hd-1)^m = \displaystyle \sum_{i=1}^{m}\binom{i}{m}(hd)^i*(-1)^{m-i} = vd-1$ với $u,v$ là các số tự nhiên .
Suy ra $ud+1 = vd-1$ nên $(v-u)d=2$ suy ra $d\mid 2$ mà $d$ là số lẻ nên $d=1$.
Vậy $GCD(2^m-1,2^n+1)=1$.
**Bài tập 2** Chứng minh rằng với mọi số tự nhiên $n$ ta có $GCD(n!+1,(n+1)!+1) = 1$
**Chứng minh**
Giả sử $d =GCD(n!+1,(n+1)!+1)$ , ta có $d\mid n!+1$ và $d\mid (n+1)!+1$ , lại có $(n!+1)(n+1)=(n+1)!+n+1$, thấy $d\mid (n+1)!+n+1$ suy ra $d\mid n$ vì $d\mid n!+1$ nên ta có $d\mid 1$
# Quan hệ giữa ước số chung lớn nhất và bội số chung nhỏ nhất
**Định lý 4.** Tích của hai số tự nhiên bằng với tích của ước số chung lớn nhất và bội số chung nhỏ nhất của hai số đó.
# Định lý cơ bản của số học
**Định lý 5.** Số tự nhiên là ước số của một tích hai số tự nhiên và nguyên tố cùng nhau với một trong hai số đó sẽ là ước số của số còn lại.
**Hệ quả.** Nếu là các số nguyên thỏa mãn $a\mid c,b\mid c$ và $GCD(a,b)=1$ thì $ab\mid c$
**Định lí 6** Nếu $a,b,c$ là các số nguyên thỏa mãn $GCD(a,b)=GCD(a,c)=1$ thì $GCD(a,bc)=1$
**Chứng minh**
Giả sử $d=GCD(a,bc)$ và $d_1=GCD(b,d)$, ta có $d_1\mid b$ và $d_1\mid d$. Vì $d\mid a,d_1\mid a$ và $GCD(a,b)=1$ nên $d_1=1=GCD(b,d)$ mà $d=GCD(a,bc)$ , $d\mid bc$, theo định lí 5 ta có $d\mid c$. Vì $d\mid a$ và $GCD(a,c)=1$ suy ra $d = 1 =GCD(a,bc)$.
**Định lý $6^a$.** Giả sử $n$ là số tự nhiên $\ge2$ . Nếu $a_i,i=1,2,...,n$ và $a$ là các số nguyên thỏa mãn $GCD(a_i,a)=1$ với mọi $i=1,2,...,,n$ thì $GCD(\displaystyle \prod_{i}^{n}a_i,a) = 1$
**Hệ quả 1** Nếu $GCD(a,b)=1$ và $n$ là số tự nhiên thì $GCD(a^n,b^n)=1$
**Chứng minh** Theo định lí 6 ta có .
**Hệ quả 2** Với mọi số tự nhiên $a,b,n$ mà $a^n\mid b^n$ suy ra $a\mid b$
**Chứng minh**
Đặt $d=GCD(a,b)$ ta có $a = da_1,b=db_1$ với $GCD(a_1,b_1) = 1$ theo hệ quả 1 ta có $GCD(a_{1}^{n},b_{1}^{n})=1$.Vì $a^n|b^n$ nên $(da_1)^n\mid (db_1)^n$, ta có $a_{1}^{n}\mid b_{1}^{n}$ suy ra $a_{1}^{n}\mid GCD(a_{1}^{n},b_{1}^{n})$ hay $a_{1}^{n}\mid 1$ suy ra $a_1=1,a=d$ suy ra $b=ab_1$ .
Vậy $a\mid b$
**Định lý 7.** Nếu một số tự nhiên là lũy thừa bậc $m$ của một số hữu tỷ và $m$ là số tự nhiên thì số đó là lũy thừa bậc $m$ của một số tự nhiên.
**Chứng minh**
Giả sử số tự nhiên $n$ là lũy thừa bậc $m$ của số hữu tỷ $p/q$. Giả sử $p$ và $q$ là các số tự nhiên và $GCD(p,q)=1$. Theo định lí $6^a$ ta có $GCD(p^m,q)=1$. Mặt khác $n=(p/q)^m$ hay $p^m = nq^m$ suy ra $q\mid p^m$ nên $q\mid GCD(p^m,q)=1$. Do đó $q=1$ nên n = $p^m$.**(ĐPCM)**
**Hệ quả** Căn bậc $m$ của số tự nhiên không phải lũy thừa bậc m của một số tự nhiên là số vô tỷ
**Bài tập 1.** Chứng minh rằng nếu $a,b,d$ là các số nguyên thỏa mãn $GCD(a,b)=1$ và $d\mid a+b$ thì $GCD(d,a)=1$ và $GCD(d,b)=1$
**Chứng minh**
Giả sử $c=GCD(d,a)$ thì $c\mid d,c\mid a$. Do đó $d\mid a+b,c\mid a+b$ suy ra $c\mid b$. Do đó $c\mid GCD(a,b)$ hay $GCD(d,a)\mid GCD(a,b)=1$ suy ra $GCD(d,a)=1$. Tương tự chứng minh được $GCD(d,b)=1$
**Định lý 8.** Giả sử $a$ và $b$ là các số tự nhiên nguyên tố cùng nhau mà tích của chúng là lũy thừa bậc $n$ của một số tự nhiên thì các số $a$ và $b$ cũng là các lũy thừa bậc $n$ của các số tự nhiên
**Hệ quả.** Giả sử $k,c,n$ là các số tự nhiên và $a_i,i=1,2,...n$ là dãy các số tự nhiên đôi một nguyên tố cùng nhau và $\displaystyle \prod_{i}^{n}a_i = c^n$ . Khi đó mọi số thuộc dãy $a_i,i=1,2,...n$ là lũy thừa bậc $n$ các số tự nhiên.
# Biểu diễn số hữu tỷ thành liên phân số
Ký hiệu $n_0,n_1$ là các số tự nhiên ,sử dụng thuật toán Euclid cho các số $n_0,n_1$ , ta có thể biểu diễn phân số $n_0/n_1$ theo công thức
với $i=1,2,...,k-1$ ta có $n_{i-1}/n_i$=$q_i+\frac{1}{n_i/n_{i+1}}$ và $\frac{n_{k-1}}{n_k}=q_k$
# Số học module
Với một số nguyên $m\ge 1$ , ta nói 2 số $a,b$ đồng dư với module $m$ nếu hiệu $a-b$ chia hết cho $m$.Ta viết
$a \equiv b \pmod m$ để biểu diễn.
**Tính chất**
**1.** Nếu $a_1 \equiv a_2 \pmod m$ và $b_1 \equiv b_2 \pmod m$ thì $a_1\pm b_1 \equiv a_2\pm b_2 \pmod m$.
**2.** Với $a$ là một số nguyên thì $a\cdot b \equiv 1 \pmod m$ với một vài số $b$ nếu và chỉ nếu $GCD(a,m)=1$.
Hơn nữa nếu $a\cdot b_1 \equiv a\cdot b_2 \equiv 1 \pmod m$ thì $b_1 \equiv b2 \pmod m$. Ta gọi $b$ là nghịch đảo $a$ trong modulo $m$
**Chứng minh**
Ta có $GCD(a,m)=1$, như vậy ta có thể tìm được cặp $(u,v)$ thỏa mãn $ua+vm=1 \Rightarrow ua - 1 = -vm$ chia hết cho $m$ . Từ đó ta có $ua \equiv 1 \pmod m$ ta có thể coi $u=b$ (1).
Với $a\cdot b \equiv 1 \pmod m$ ta có $ab - 1 = vm \Rightarrow ab - vm = 1 \Rightarrow GCD(a,m) = 1$(2)
Từ (1) và (2) ta đã chứng minh được tính chất 2
**Ứng dụng** Trong các bài toán mã hóa cổ điển , ta thường sử dụng số học module để giá trị của chuỗi mã hóa sẽ là một chuỗi mà các kí tự là các kí tự trong bảng kí tự mà ta muốn . Ví dụ nếu ta chỉ muốn chuỗi mã hóa sẽ chỉ bao gồm các kí tự chữ cái thường , ta sẽ mã hóa kí tự bằng một loại mã hóa , sau đó sẽ lấy từng kí tự mã hó đó chia cho 26- số chữ cái in thường.
# Vành số nguyên module
**1.** $\mathbb{Z}/m\mathbb{Z} = \{0,1,2,...,m-1\}$ ta gọi là vành số nguyên theo module $m$ . Ta cộng và nhân các phần tử của $\mathbb{Z}/m\mathbb{Z}$ như cộng và nhân các số nguyên rồi sau đó chia cho $m$ lấy dư để có kết quả trong $\mathbb{Z}/m\mathbb{Z}$
**2.** Tập hợp các phần tử đơn vị trong $\mathbb{Z}/m\mathbb{Z}$ là các phần tử nghịch đảo của một số nguyên $a$ trong module $m$. Kí hiệu
$(\mathbb{Z}/m\mathbb{Z})^* = \{a \in \mathbb{Z}/m\mathbb{Z}: GCD(a,m)= 1 \}$$=a \in \mathbb{Z}/m\mathbb{Z} : \text{ a có một phần tử nghịch đảo trong module m}$.
Ta gọi $(\mathbb{Z}/m\mathbb{Z})^*$ là nhóm các phần tử đơn vị module $m$
**Ví dụ** Nhóm các phần tử đơn vị module $24$ :
$(\mathbb{Z}/24\mathbb{Z})^{*}$ = $\{1,5,7,11,13,17,19,23\}$
# Định lý Thue–Siegel–Roth
Nếu $\alpha$ là một số vô tỉ , thì với mọi $\epsilon>0$ chỉ có hữu hạn các phân số $\frac{p}{q} \in \mathbb{Q}$ sao cho:
> $\lvert \alpha - \frac{p}{q} \rvert < \frac{1}{q^{2+ \epsilon}}$
Khi đó ta gọi $\frac{p}{q}$ là xấp xỉ của $\alpha$
# Số nguyên tố
Với $p$ là một số nguyên tố thì tất cả các phần tử khác $0$ trong $\mathbb{Z}/p\mathbb{Z}$ đều có phần tử nghịch đảo
$(\mathbb{Z}/p\mathbb{Z})^* = \{1,2,3,...,p-1\}$
Nếu $p$ là một số nguyên tố thì tập hợp $\mathbb{Z}/p\mathbb{Z}$ của các số nguyên trong module $p$ với các quy tắc cộng , trừ , nhân , chia được gọi là một trường.
Trường là tên gọi chung cho các vành giao hoán mà trong đó các phần tử khác $0$ đều có phần tử nghịch đảo
Trường $\mathbb{Z}/p\mathbb{Z}$ hữu hạn các phần tử , được gọi là trường hữu hạn , kí hiệu $\mathbb{F_p}$. Ta cũng có kí hiệu $\mathbb{F_{p}^{*}}$ để thay thế cho kí hiệu $(\mathbb{Z}/p\mathbb{Z})^*$
# Hàm phi Euler
Với $n$ là số nguyên dương , hàm phi Euler là số lượng các số nguyên tố cùng nhau với $n$ trong đoạn từ $1$ đến $n$.Kí hiệu $\varphi(n)$.
**Tính chất**
* Với $p$ là một số nguyên tố thì $\varphi(p) = p-1, \varphi(p^k) = p^k - p^{k-1}$
* $\varphi(ab) = \varphi(a) \varphi(b)$
**Công thức tính**: Với $n$ là số nguyên dương , $p_i$ là các số nguyên tố , $k_i$ là các số nguyên dương, ta phân tích n thành tích các số nguyên tố $n = p_1^{k_1}...p_i^{k_i}$ . Khi đó $\varphi(n) = \varphi(p_1^{k_1}...p_i^{k_i}) = \varphi(p_1^{k_1})\varphi(p_2^{k_2})...\varphi(p_i^{k_i})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})...(p_i^{k_i}-p_i^{k_i-1})$
# Định lý Fermat nhỏ
Với $p$ là một số nguyên tố và một số nguyên $a$ bất kì , ta có :
$a^{p-1} \equiv
\begin{cases}
1 \pmod{p} & \text{if } p \nmid a, \\
0 \pmod{p} & \text{if } p \mid a.
\end{cases}$
**Định lí 1** Với $p$ là một số nguyên tố và $a$ là một số nguyên không chia hết cho $p$ . Giả sử rằng $a^n \equiv 1\pmod p$ thì $n$ chia hết cho bật của $a$ trong module $p$ . Cụ thể hơn thì $p-1$ chia hết cho bậc của $a$.
**Chứng minh**
Với $k$ là bậc của số nguyên $a$ trong module $p$ , ta định nghĩa $a^k \equiv 1 \pmod p$ và $k$ là số mũ nguyên dương nhỏ nhất thỏa mãn . Lại có $a^n \equiv 1 \pmod p$ , ta chia $n$ cho $k$ , có: $n = kq + r$ với $0 \le r <k$. Khi đó ta có $1 \equiv a^n \equiv a^{kq+r} \equiv (a^{q})^k \cdot a^r \equiv a^r \pmod p$ mà $0 \le r <k$ và $k$ là số nguyên dương nhỏ nhất thỏa mãn $a^k \equiv 1 \pmod p$. Suy ra $r = 0$. Như vậy $n=kq$ , $k \mid n$. Mà theo định lý Fermat nhỏ , ta có $a^{p-1} \equiv 1 \pmod p$ nên $k \mid p-1$
**Ví dụ** Ta xét $p=7$ , các phần tử $a\in \{1,2,3,4,5,6\}$
Với $a=2$ ta có $2^3=8 \equiv 1 \pmod 7 \Rightarrow \text{ord}_7(2)=3$ và $3 \mid 6 = p-1$.
# Ứng dụng trong thuật toán mã hóa RSA
RSA là một thuật toán mã hóa công khai.
Tạo khóa bằng cách
1. sử dụng 2 số nguyên tố lớn là $p,q$ với $p\ne q$
2. Tính $n=pq$
3. Tính $\varphi(n) = (p-1)(q-1)$
4. Chọn một số nguyên $e$ sao cho $1 < e < \varphi(n),GCD(e,\varphi(n))=1$
5. Tính $de \equiv 1 \pmod {\varphi(n)}$. $d$ là nghịch đảo của $e$ trong module $\varphi(n)$.
**Mã hóa**
Bản rõ thông điệp $m$ sẽ được mã hóa theo công thức
> $c = m^e \text{ mod } n$
$c$ được gọi là bản mã .
**Giải mã**
Từ việc mã hóa , ta có $c = m^e \text{ mod } n$ , lũy thừa $d$ lần ta có $c^d = m^{ed} \text{ mod } n$.
Mà $ed \equiv 1 \pmod {\varphi(n)} \Rightarrow \exists k \text{ sao cho } ed = 1 + k\varphi(n)$
Ta có $m^{ed} = m^{1+k\varphi(n)}=m^{1+k(p-1)(q-1)}=m \cdot m^{k(p-1)(q-1)} = m\cdot (m^{p-1})^{k(q-1)}$.
Xét theo modulo $p$ ta có $m^{ed} \equiv m\cdot (m^{p-1})^{k(q-1)} \equiv m\cdot 1^{k(q-1)} \equiv m\pmod p$.
Tương tự ta có $m^{ed} \equiv m \pmod q$. Mà $p,q$ là hai số nguyên tố cùng nhau . Theo định lí số dư Trung Hoa , ta có
$m^{ed} \equiv m \pmod n$. Như vậy nếu ta có được $d$ , ta có thể giải mã theo công thức $m=c^d \pmod m$.
# Căn nguyên thủy
**Định nghĩa** Với $p$ là một số nguyên tố . Thì tồn tại một phần tử $g \in \mathbb{F_{p}^{*}}$ mà mọi lũy thừa của nó tạo thành các phần tử trong $\mathbb{F_{p}^{*}}$.
> $\mathbb{F_{p}^{*}} = \{1,g^1,g^2,...g^{p-2}\}$
Các phần tử mà thỏa mãn tính chất này thì được gọi là căn nguyên thủy của $\mathbb{F_{p}^{*}}$ hay phần tử sinh của $\mathbb{F_{p}^{*}}$ có bậc là $p-1$.
**Ví dụ** Trường $\mathbb{F_{11}}$ có 2 là căn nguyên thủy bởi $2^0=1,2^1=2,2^2=4,2^3=8,2^4=5,2^5=10,2^6=9,2^7=7,2^8=3,2^9=6$
Nếu $p$ lớn thì trường hữu hạn $\mathbb{F_{p}}$ có khá nhiều căn nguyên thủy . Công thức tính số căn nguyên thủy của $\mathbb{F_{p}}$ là $\varphi(p-1)$
# Thuật toán euclid
Với $a,b$ là các số nguyên dương với $a \ge b$. Thuật toán tính $GCD(a,b)$ trong các bước hữu hạn
1. Đặt $r_0=a$ và $r_1=b$
2. Khởi tạo $i=1$
3. Chia $r_{i-1}$ cho $r_i$ để lấy thương $q_i$ và dư $r_{i+1}$
$r_{i-1} = r_{i}q_{i}+r_{i+1}$ với $0\le r_{i+1}<r_i$
4. Nếu phần dư $r_{i+1}=0$ thì $r_i=GCD(a,b)$ thuật toán dừng lại.
5. Ngược lại thì nếu $r_{i+1}>0$ , $i=i+1$ và quay trở lại bước 3
**CODE:**
```python
def GCD(a,b):
if b==0:
return a
return GCD(b,a%b)
```
# Thuật toán euclid mở rộng
Cho 2 số $a,b$ là 2 số nguyên dương. Thì đẳng thức $au+bv=GCD(a,b)$ luôn có một cặp số nguyên $(u,v)$ thỏa mãn.
Nếu $(u_0,v_0)$ là một cặp thỏa mãn thì các cặp còn lại sẽ có dạng
$u=u_0+\frac{bk}{GCD(a,b)}$ và $v=v_0-\frac{bk}{GCD(a,b)}$
**Định nghĩa.** Giả sử $a$ và $b$ là các số nguyên.Ta nói rằng $a$ và $b$ là nguyên tố cùng nhau nếu $GCD(a,b)=1$
Với tất cả phương trình $Au+Bv=GCD(A,B)$. Trong trường hợp 2 số nguyên tố cùng nhau , ta có thể chia 2 vế cho $GCD(A,B)$.
> $\frac{A}{GCD(A,B)}u+\frac{B}{GCD(A,B)}v=1$
với $a = \frac{A}{GCD(A,B)}, b=\frac{B}{GCD(A,B)}$
```python=
def extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
else:
g, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return (g, x, y)
```
**Ứng dụng trong mật mã học**
**1. Challenge 1**
```python
from Crypto.Util.number import *
from math import gcd
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e1 = 65537
e2 = 65541
flag = bytes_to_long(open("flag.txt", "rb").read())
print("n =",n)
print("e1 =", e1)
print("ct1 =",pow(flag,e1,n))
print("e2 =", e2)
print("ct2 =",pow(flag,e2,n))
```
Ở bài này , chúng ta có thể thấy $GCD(e_1,e_2)=1$ và $c_1=flag^{e_{1}}\%n$ (1) và $c_2=flag^{e_{2}}\%n$ (2).
Vì $GCD(e_1,e_2)=1$ nên ta có thể tìm được một cặp số $(u,v)$ thỏa mãn $e_1u+e_2v=1$. Như vậy khi tìm được cặp số $(u,v)$ thỏa mãn ta có thể lũy thừa 2 vế của (1) với $u$ lần và (2) với $v$ lần ta có $c_{1}^{u}=flag^{e_{1}u}\%n$ và $c_{2}^v=flag^{e_{2}v}\%n$. Từ đây khi nhân cả 2 đẳng thức cho nhau , ta có
${c_{1}^{u}}\cdot c_{2}^v =(flag^{e_{1}u} \cdot flag^{e_{2}v})\%n$ $= flag^{e_{1}u +e_2v}\%n = flag^1\%n = flag\%n$.
Vậy từ đây ta có thể suy ra được $flag =({c_{1}^{u}}\cdot c_{2}^v)\%n$
**Solve**
```python=
from Crypto.Util.number import *
def extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
else:
g, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return (g, x, y)
n = 15901254888844811128179580871245406367429458470377184674346144751647374670572937768656662957181512676359418078437011136469224896319966386627429206795068925897174248433855017421313735430678168492234734394880647475648543609402371350918389677358888213271400537134395832504542372530206725503786073409188730402071770292410309575838578560769345145559847445412095633449125407739637164904665737253942695011113881455582555714641495649700106905760395890793940455457773086996884372149400456988433069484775450712870324541468746668190911973339621513763606476441759444049821345124475226171788841826196367674824619262818229167280107
e1 = 65537
ct1 = 6134713060373435948556474755855318784386720533953884009246240230205407388931085061564081789370911428824500127094059273266356818554934711862668962397011233481783841108721632742213583285732759368587704811645978337309631245786774989959480411962700732626871529276001383894787587890246419493222154158464064454367987270237741841658379743685415736043545535123996868337417705604454771996894293403948475999489203865577952909377970056528295843799981597066017034794709047626102191735563773119979967162811502028349624454414951508274122376784208439303447130332220269755596599585303081456170876589844251202787958224612648075708562
e2 = 65541
ct2 = 12289174959608687614094152331093686256316096581108792383625768772032690081683139088648586590620176510267962855115162928652900907905574080504437818319541316724690074755982084736680317758812405111214623901140007349554490399561006332911290313432255914648059000856948663708488993033097035326726610432584609807471282725520290806726859367916119927128609556138041397810164173198429419124294772498511334575878710441004571373454998992258607853538605225636106010766617069707286680319864945149772991558425391072666852710438410307946265874104771063270484981200520545808138897444402746976571938734768901920974191380418701890161795
g,u,v = extended_gcd(e1,e2)
flag = (pow(ct1,u,n)*pow(ct2,v,n))%n
print(long_to_bytes(flag))
```
**Challenge 2**
```python=
from Crypto.Util.number import *
from math import gcd
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x69420
while gcd(e,n) != 1:
p = getPrime(1024)
q = getPrime(1024)
n = p * q
flag = bytes_to_long(open("flag.txt", "rb").read())
print("n =",n)
print("e =", e)
print("ct =",(flag * e) % n)
```
Ở bài này ta nhận thấy $ct=(flag\cdot e)\%n$, mà $GCD(e,n)=1$ áp dụng euclid mở rộng , ta có $eu + vn=1$
module 2 vế ta sẽ có $(eu\%n + vn\%n)\%n = 1 \Rightarrow (eu\%n + 0)\%n = 1 \Rightarrow eu \equiv 1 \pmod n$. Như vậy nếu ta tìm được $u$ theo euclid mở rộng , ta có thể nhân $u$ vào 2 vế của $ct=(flag\cdot e)\%n$ , ta có
$ct\cdot u \equiv flag \cdot eu \pmod n \Rightarrow ct\cdot u \equiv flag\pmod n$
**Solve**
```python=
from Crypto.Util.number import *
def extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
else:
g, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return (g, x, y)
n = 15669685757275858271517486459741480949709829038672662592840711136077116992626270806370795316225969166761702778585882394226268581092084017094212107735253129408007892578162493318794748779312080567040352251128742092616601814151832616233426031951866834971036929269763591471466508084263954716112245398580695780233217763237765517798263718999955474636710222812619263870485272604471325662716828788546656464120667450838146389227081697053328590063163530544619158945636788013215358038098687550448601179070843308918208395203277478325191452325882149150080779747786647705937785580384235707024256106519539741319696717019352766536277
e = 431136
ct = 4650422119778864766567823687240641012511579368001018447853162768781210528
u,v = extended_gcd(n,e)[1],extended_gcd(n,e)[2]
print(long_to_bytes((ct*v)%n))
```
**Wiener's Attack**
Wiener's Attack có thể được sử dụng để giải mã RSA trong trường hợp khóa bí mật $d$ quá nhỏ so với $n$
> Nếu $d<\frac{1}{3}n^{\frac{1}{4}}$
Ta có $ed \equiv 1\pmod {\varphi(n)}$, nên $\exists k$ sao cho $ed = 1+k\varphi(n)\Rightarrow \frac{e}{\varphi(n)} - \frac{k}{d} = \frac{1}{d\varphi(n)}$.
Ta có thể có $\varphi(n)$ là $n$ khi $n$ rất lớn.Khi đó theo định lí Thue–Siegel–Roth ta có
$\lvert \frac{e}{n} - \frac{k}{d} \rvert < \frac{1}{2d^2}$
**Các bước :**
1. Tính các liên phân số của $\frac{e}{n}$
2. Sinh tất cả các convergents $\frac{k}{d}$
3. Kiểm tra với từng $(k,d)$
* $ed \equiv 1 \pmod k$
* Thử khôi phục lại $\varphi(n)=\frac{ed-1}{k}$
* Giải phương trình $x^2-sx+n=0$ với $s = n-\varphi(n)+1$
* Nếu phương trình có nghiệm nguyên thì thỏa mãn.
**Challenge 3**
```python=
from Crypto.Util.number import getPrime, bytes_to_long, inverse
from random import randint
def generate_rsa_instance(bits=512, flag_text=b"flag{example_for_wiener}"):
while True:
p = getPrime(bits)
q = getPrime(bits)
n = p * q
phi = (p - 1) * (q - 1)
d_bound = int(pow(n, 0.25))
d = randint(2, d_bound - 1)
try:
e = inverse(d, phi)
break
except ValueError:
continue
m = bytes_to_long(flag_text)
c = pow(m, e, n)
return {
"p": p,
"q": q,
"n": n,
"d": d,
"e": e,
"m": m,
"c": c,
}
rsa = generate_rsa_instance()
print("n = ", rsa["n"])
print("e = ", rsa["e"])
print("c = ", rsa["c"])
```
**Solve**
```python=
from Crypto.Util.number import getPrime, bytes_to_long, inverse, long_to_bytes
from math import isqrt
n = 67161573951394194182014576129565831264213407812255355470229739989074486896781005054839698896720107580234685838690770939078788263082237572296922229976901913209209880122443221273880228237334136382339369335346236259363095101606455386620149764869062908403103114875198315149312525085438061585317117653631658293089
e = 63522351854952592792782007891439022262764768403437331259740753727322476302634168585972657330490870662357045008617613293490245253933040323690674314146265353984154418319171400099558251289278367361847136731781819400072357162943040846504944305121755394225257470667214063054186234339222352840810439194952657846035
c = 64946478295235882695093474476145417480041458953174193210485977768887045615287612729083185846380652729041839558568792552649654186142152277547058032369537539138551688900929674050112856772684816220530019860371665350689333439486741950958580008524899108092623755243947900373632965924931793429078260125511283792177
def continued_fraction(n, d):
if d == 0:
return []
q = n // d
r = n - q * d
return [q] + continued_fraction(d, r)
def convergents(n, d):
hh, kk, h, k = 0, 1, 1, 0
for x in continued_fraction(n, d):
hh, kk, h, k = h, k, h * x + hh, k * x + kk
yield h, k
def find_p_q(e, n):
p, q = 0, 0
for k, d in convergents(e, n):
if k != 0:
phi_n = (e * d - 1) // k
a, b, c = 1, n - phi_n + 1, n
delta = pow(b, 2) - 4 * a * c
if delta >= 0:
s1 = (-b + isqrt(delta)) // 2 * a
s2 = (-b - isqrt(delta)) // 2 * a
if n == s1 * s2:
return abs(s1), abs(s2)
return -1, -1
p,q = find_p_q(e,n)
print("p =", p)
print("q =", q)
phi_n = (p - 1) * (q - 1)
d = pow(e, -1, phi_n)
m = pow(c, d, n)
print("m =", long_to_bytes(m))
```
Sign in with Wallet
Connect another wallet