# **TASK2**
# **RSA ATTACK**
## Khái niệm
RSA là một thuật toán mã hóa khóa công khai được sử dụng rộng rãi để truyền dữ liệu an toàn. Nó là một trong những hệ thống mật mã khóa công khai thực tế đầu tiên và được sử dụng rộng rãi để truyền dữ liệu an toàn. Thuật toán lần đầu tiên được mô tả bởi Ron Rivest, Adi Shamir và Leonard Adleman vào năm 1977.
Tính bảo mật của RSA dựa trên các tính chất toán học của các số nguyên tố lớn và khó khăn trong việc phân tích tích của hai số nguyên tố lớn. Trong RSA, các khóa được sử dụng để mã hóa và giải mã là một cặp số nguyên tố lớn, một là khóa công khai và một là khóa riêng. Khóa công khai có thể được chia sẻ tự do, trong khi khóa riêng phải được giữ bí mật.
Dữ liệu được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa riêng tương ứng, khiến RSA trở thành một công cụ quan trọng để liên lạc an toàn qua internet và các mạng khác. RSA được sử dụng rộng rãi cho chữ ký số, bảo vệ phần mềm và giao dịch trực tuyến an toàn.
### Tạo khóa
- Chọn 2 số nguyên tố lớn $p, q$ với $p ≠ q$
- Tính $n = pq$
- Tính giá trị hàm số $φ(n)$ = $(p-1)(q-1)$
- Chọn 1 số $e$ sao cho $1 < e < φ(n)$ và $gcd(e,φ(n)) = 1$
- Tính $d = $e^{-1}$ ($mod φ(n)$), số $d$ thỏa mãn $ed ≡ 1$ (mod $φ(n)$)
#### Public Key gồm:
- $n$ - module
- $e$- số mũ công khai (số mũ mã hóa)
#### Private Key gồm:
- $p,q$ là hai số nguyên tố ban đầu
- $d$ - số mũ bí mật (số mũ giải mã)
### Mã hóa
Khi Bob muốn gửi một tin nhắn M cho Alice, Bob chuyển M thành một số m < n theo 1 cách thỏa thuận trước. Bob sẽ tính ra bản mã c từ bản rõ m theo công thức:
$c$ = $m^e$ mod $n$
### Giãi mã
Để giải mã, Alice dùng khóa bí mật của mình để tính ngược lại: $m$ = $c^d$ mod $n$
Quá trình giải mã hoạt động vì ta có:
$c^d$ ≡ $(m^e)^d$ ≡ $m^{ed}$ mod $n$ = $m^1$ mod $n$ = $m$ mod $n$
Độ an toàn của hệ thống RSA dựa trên 2 vấn đề của toán học: bài toán phân tích ra thừa số nguyên tố các số nguyên lớn và bài toán RSA. Nếu 2 bài toán trên là khó (không tìm được thuật toán hiệu quả để giải chúng) thì không thể thực hiện được việc phá mã toàn bộ đối với RSA. Phá mã một phần phải được ngăn chặn bằng các phương pháp chuyển đổi bản rõ an toàn.
Dưới đây là một số cách tấn công RSA
## 1.Factoring N
Bước đầu tiên cần quan tâm khi tấn công RSA đó là phân tích N thành thừa số nguyên tố để tìm được p,q .Sau khi tìm được p,q việc giải mã trở nên dễ dàng.Ta có thể thử factoring n bằng một số tool online như [factordb](http://www.factordb.com/),[alpertron](https://www.alpertron.com.ar/ECM.HTM) . Với trường hợp N quá lớn hoặc không phân tích được, ta nên tấn công theo hướng khác
## 2.Elementary Attack
### Common modulus
#### External Attack
Để tránh tạo một modulus N = pq khác nhau cho mỗi người dùng ,nên mọi người sẽ có chung modulus N.Mỗi người dùng *i* sẽ có một cặp khóa *($e_i$,$d_i$)*
Giả sử bạn có 2 cipher $C_A$,$C_B$ và 2 cặp Pulic Key (N,$e_A$),(N,$e_B$)
Thông thường gcd($e_A$,$e_B$) phải bằng 1.
Ta cần tìm cặp số u,v sao cho $e_A$*u + $e_B$*v = 1.
Tìm u,v theo thuật toán Euclid mở rộng.
$C_A$ = $M^{e_A}$ và $C_B$ = $M^{e_B}$
$C^u_A$ = $M^{e^u_A}$ = $M^{e_A*u}$ và $C^v_B$ = $M^{e^v_B}$ = $M^{e_B*v}$
=>$C^u_A$ * $C^v_B$ = $M^{e^u_A}$ * $M^{e^v_B}$ = $M^{e_A*u+e_B*v}$ = M^1^ = M
#### Internal Attack
Trường hợp khác ,bạn sở hữu một cặp (e,d)
$ed$ ≡ $1 (mod φ(n))$
$(ed-1) = k φ(n)$
=> Tồn tại 1 giá trị k sao cho: $φ(n) = (ed -1)/k$ là số nguyên
Khi có được φ(n) và số mũ e công khai của mục tiêu ,ta có thể tính được khóa bí mật của mục tiêu : $d_{victim}$ ≡ $e^{-1}_{victim}$ $(mod φ(n))$
Từ đó giải mã message.
### Blinding
Marvin muốn Bob kí vào một `message` $M$,nhưng Bob từ chối,
Marvin cố gắng lựa chọn một giá trị ngẫu nhiên *r* tương đối nguyên tố với N(nghĩa là $gcd(N,r) = 1$)
Tạo ra $M' ≡ M*r^e mod N$ sau đó hỏi Bob kí
Marvin thu được bản blinded signature $S'$ ≡ $M'^d$ mod $N$
Bây giờ Marvin chỉ cần tính được S bản kí của M gốc
=>$S$ = $S'/r$ mod $N$
Vì $S^e$ = $S'^e/r^e$ = $M'^{ed}/r^e$ ≡ $M'/r^e$ = $M mod N$
## 3.Low private exponent (small d)
### Wiener Attack
Điều kiện cần:
- $d$ < $1/3n^{1/4}$
- $q < p < 2q$
- $e' < n^{3/2} (e' = e$ mod $n$) Public Key không quá lớn
Nếu thỏa mãn các điều kiện trên (nhận biết thông qua việc đề cho e rất lớn), ta có thể dễ dàng tìm được d và phá vỡ toàn bộ hệ thống mã hóa.
Chứng minh:
Phép chứng minh sử dụng tính chất của liên phân số. Vì $ed ≡ 1 (mod φ(n))$ nên tồn tại một số nguyên k sao cho $ed - kφ(n) = 1$. Vì vậy:
Do đó $k/p ≈ e/φ(n)$ mà $φ(n) ≈ n$ Thay $φ(n)$ bằng $n$ ta thu được:
Bây giờ $k*φ(n)$ = $ed-1$ vì $e < φ(n)$ ta thấy $k < d < 1/3n^{1/4}$ .Từ đó ta thu được:
Từ đó, áp dụng định lý về dãy hội tụ liên phân số, ta tìm trong dãy hội tụ của khai triển liên phân số e/n sẽ tìm được k/d. Bằng cách thử từng cặp k/d này, ta tính $φ(n) = (ed - 1)/k$. Lúc này ta có:
$p+q = n-φ(n)+1$ và $pq = n$
Dùng định lý Vi-et đảo tính được $p, q$. Xác nhận lại $pq = n$ để tìm ra cặp $k/d$ đúng. Tìm được $p, q$ sẽ tính được $d$
Để tránh bị tấn công bởi phương pháp Wiener Attack, ta có thể dùng e nhỏ, nhưng lúc này bù lại d sẽ lớn và tốc độ giải mã là khá chậm. Nếu n là một số dài 1024 bit thì d phải dài ít nhất 256 bit.
M. Wiener đưa ra 2 giải pháp hiệu quả để phòng tránh hình thức tấn công trên mà vẫn giữ được tốc độ tính toán:
1.Sử dụng định lý số dư Trung Hoa (Chinese Remainder Theorem – CRT).
Giả sử ta chọn d sao cho $d_p$ = $d$ mod $(p-1)$ và $d_q$ = $d$ mod $(q-1)$ đều là số nhỏ (khoảng 128 bit) nhưng $d$ vẫn là số lớn. Quá trình giải mã vẫn có thể thực hiện nhanh chóng theo cách sau: Đầu tiên tính $m_p$ = $C^{d_p}$ (mod $p$) và $m_q$ = $C^{d_q}$ (mod $q$). Dùng định lý CRT để tìm số $m$ thỏa mãn $m$ = $m_p$ (mod $p$) và $m$ = $m_q$ (mod $q$). Kết quả $m$ tính được sẽ thỏa mãn tính chất $m = c^d$ (mod $n$) như yêu cầu. Vì $d$ lớn nên Wiener Attack không hiệu quả nữa.
2.Thay $e$ bằng $e'$ với $e' = e + kφ(n)$ với $k$ là một số nguyên đủ lớn sao cho $e'$ > n3/2, lúc này Wiener Attack sẽ không áp dụng được bất kể d nhỏ thế nào
## 4. Low Public Exponent
### Hastad's Broadcast Attack
Để cuộc tấn công này thành công, bạn sẽ cần nắm bắt ít nhất $e$ các bản mã tương ứng với cùng một bản rõ $m$.
Giả sử $e$ = 3 và do đó $M = m ^ 3$. Bạn sẽ phải giải hệ phương trình này:
$c_1$ = $M^3$ mod $n_1$
$c_2$ = $M^3$ mod $n_2$
$c_3$ = $M^3$ mod $n_3$
Chúng ta có thể dùng định lí [Chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Theorem_statement) để giải phương trình này
Nếu $gcd(N_i,N_j) = 1(i ≠ j )$
Trước tiên cần tính $N_i$ = $N/n_i$
Vì $gcd(N_i,n_i) = 1$ ta có thể tìm được $u_i*N_i$ + $v_i*n_i$ = $1$.Trong đó $u_i$ là nghịch đảo của $N_i$ modulo $n_i$ hay $N_i*u_i$ ≅ 1 mod $n_i$
Vì $m < n_i$ nên $m^3 < N$.Ta có thể tính $m$ bằng căn bậc 3 của $N$
## 5.Implementation Attack
### Fermat Attack
Trong thực tế $p$ và $q$ phải có cùng độ dài bit để tạo khóa RSA mạnh mẽ nhưng việc chọn số nguyên tố quá gần cũng có thể làm hỏng hoàn toàn bảo mật.
Điều kiện : $p-q$<$n^{1/4}$
Thuật toán Fermat:
với
Bây giờ $n$ được tính bằng
$n$ = $(x+y)(x-y)$
Giải thuật Fermat để tìm $p,q$:
1. $a$ = $\sqrt n$
2. $b$ = $a*a -n$
3. while b is not perfect square:a.
a.increment $a$
b. $b = a*a -n$
4. return $a - \sqrt b$
### Timing Attack
Đây là kiểu tấn công dựa trên thuật toán nhân bình phương có lặp
$C$ = $M^d$ mod $N$
Chuyển d về dạng nhị phân (ví dụ 20 = 10100)
d = $d_0,d_1...d_n$
d = $\sum^n_{i=0}2^id_i$
C = $\prod^n_{i=0}M^{{2^i}*d_i}$
Thuật toán nhân bình phương có lặp:
Set $z = M,C =1$ For $i = 0,...,n$:
(1) Nếu $d_i$ = $1$ thì $C = C*z$ mod $N$
(2) $z$ = $z^2$ mod $N$
Cuối cùng $C$ sẽ bằng $M^d$ mod $N$
Vì $d$ là số lẻ nên $d_0$ luôn bằng $1$ Ở lần lặp tiếp theo nếu $d_1$ = $1$ thì sẽ thực hiện phép tính $C = C*z$ mod $N$.Nếu không thì sẽ không thực hiện ,vì có sự khác biệt về thời gian thực hiện phép tính nên dựa vào đó ta có thể xác định được $d_1$ bằng $0$ hay $1$
Tiếp tục như vậy để khôi phục $d_2,d_3,..,d_n$.Lưu ý khi một số mũ $e$ nhỏ được sử dụng ,cuộc tấn công khóa timing attack chỉ cần dùng cho đến khi một phần tư số bit của $d$ được phát hiện.
Dưới đây là một đoạn code bằng python
```python
import time
from Crypto.Util.number import long_to_bytes
def repeated_squaring(c, d, n):
x = 1
while d:
d >>= 1
if d&1:
x = (x*c)%n
x = (c*c)%n
return x
def RSA_decrypt(ciphertext, d, n):
start = time.time()
plaintext = repeated_squaring(ciphertext, d, n)
end = time.time()
return end - start
def Kocher_Timing_Attack(ciphertext, n):
lower_bound = 0
upper_bound = n - 1
while True:
d = (lower_bound + upper_bound) // 2
time_elapsed = RSA_decrypt(ciphertext, d, n)
if time_elapsed > 0.1:
upper_bound = d - 1
elif time_elapsed < 0.1:
lower_bound = d + 1
else:
return d
n = 996905207436360486995498787817606430974884117659908727125853
e = 65537
ciphertext = 375444934674551374382922129125976726571564022585495344128269
# The private key is not known, but we can extract it using the Kocher Timing Attack
private_key = Kocher_Timing_Attack(ciphertext, n)
print("The private key is:", private_key)
# Verify that the private key is correct by decrypting the ciphertext
plaintext = repeated_squaring(ciphertext, private_key, n)
print("The plaintext is:", plaintext)
print(long_to_bytes(plaintext))
```
Kocher Timing Attack có thể mất nhiều thời gian để chạy, đặc biệt đối với các giá trị lớn hơn của n. Điều này là do cuộc tấn công dựa vào việc đo thời gian thực hiện giải mã RSA và thời gian thực hiện có thể rất nhỏ, khiến cuộc tấn công chậm và không đáng tin cậy. Ngoài ra, độ chính xác của kết quả bị ảnh hưởng bởi các yếu tố khác, chẳng hạn như hệ điều hành và phần cứng đang được sử dụng, khiến cuộc tấn công trở nên không đáng tin cậy hơn.
Trong các ứng dụng trong thế giới thực, không nên sử dụng Kocher Timing Attack, vì nó có thể rất chậm và không đáng tin cậy, đồng thời có nhiều cách an toàn và hiệu quả hơn để thực hiện mã hóa và giải mã RSA. Thay vào đó, bạn nên sử dụng các thư viện RSA đã được thiết kế có tính đến khả năng chống tấn công kênh phụ, chẳng hạn như OpenSSL hoặc PyCrypto.
### Random Fault
Trong RSA việc giải mã và kí dùng chinese remainder theorem(CRT) để tăng tốc độ tính $M^d$ mod $N$.Thay vì mod cho $N$ ta sẽ mod cho $p,q$
$s_p$ = $m^d$ mod $p$
$s_q$ = $m^d$ mod $q$
CRT được dùng để kết hợp 2 chữ kí $s_p$ và $s_q$ thành kí kí cuối $s$
Khi không có lỗi trong quá trình tính toán các chữ ký một phần $s_p$ và $s_q$, chúng ta có thể thực hiện các quan sát sau khi xác minh chữ ký $s$ cuối cùng :
Chữ ký $s^e$ đã xác minh phù hợp với $m$ modulo $p$ hoặc $q$. Điều này có nghĩa $s^e - m$ là đó là bội số của $p$ và cũng là bội số của $q$. Điều này làm cho nó trở thành bội số của $n = pq$ và do đó, $GCD(S^E - m, n) = n$
Trường hợp có lỗi xảy ra:
Chữ ký $s^e$ đã xác minh phù hợp với m modulo $q$ nhưng không phải là $p$. Điều này có nghĩa $s^e - m$ là đó là bội số của $q$ nhưng không phải là bội số của $p$. Vậy $GCD(S^E - m, n) = q$
Điều này vẫn đúng nếu lỗi xảy ra trong quá trình tính toán $s_q$
Cuộc tấn công này chỉ có thể hoạt động nếu kẻ tấn công biết văn bản $m$ thuần túy . Điều này cũng có nghĩa là không có khoảng đệm ngẫu nhiên nào được áp dụng cho tin nhắn trước khi ký.
### Bleichenbacher's Attack on PKCS 1
Giả sử `module` $N$ là một số $n$-bits,`message` $M$ là một số $m$-bits với $m < n$ trước khi mã hóa đệm vào $M$ thêm $n-m$ bits ngẫu nhiên.Sau khi đệm ,`message` có dạng như bên dưới:
| 02 | Random | 00 | M |
|:---:|:------:|:---:|:---:|
kết quả là `message` dài $n$ bits và được mã hóa bởi RSA.Khối ban đầu chứa `"02"` và dài 16 bits để thể hiện rằng `message` đã được đệm.
Khi máy của Bob nhận được `message` PKCS1,một ứng dụng sẽ giải mã nó,kiểm tra khối ban đầu và loại bỏ phần đệm ngẫu nhiên.Mốt số ứng dụng kiểm tra nếu không có `"02"` ở khối ban đầu sẽ báo lỗi.Sử dụng thông báo lỗi kẻ tấn công Marvin có thể giải mã các bản mã mà anh ta lựa chọn.
Giả sử anh ta chặn được một bản mã $C$ gửi cho Bob và muốn giải mã nó .Để thực hiện cuộc tấn công,Marvin chọn một số $r$ ngẫu nhiên ($r \epsilon Z^*_N$) và tính $C'$ = $C*r$ mod $N$ sau đó gửi $C'$ cho máy của Bob.Máy của Bob nhận $C'$ và giải mã.Nó sẽ phản hồi 1 thông báo lỗi hoặc không phản hồi(Nếu tình cờ C' được định dạng đúng).Do đó Marvin biết được 16 bit quan trọng nhất có `"02"` hay không với "$r$" bất kì mà anh ta chọn.Như vậy là đủ để giải mã $C$
# Kết luận
Hệ mật RSA là một trong những hệ mật công khai phổ biến nhất hiện nay, được sử dụng rộng rãi trong các ứng dụng bảo mật. Tuy nhiên, khi mã hóa hoặc giải mã các thông điệp lớn, RSA có thể gặp phải vấn đề về tốc độ tính toán. Dưới đây là một số phương pháp mã hóa được sử dụng để giữ cho tốc độ tính toán ở mức độ cao mà vẫn đảm bảo tính an toàn của hệ mật RSA:
- RSA với phương pháp tối ưu hóa các phép tính modulo: Phương pháp này sử dụng các thuật toán tối ưu hóa để tính toán các phép tính modulo. Ví dụ, thuật toán Montgomery có thể giảm đáng kể thời gian tính toán modulo.
- RSA với phương pháp chia nhỏ dữ liệu (RSA-CRT): RSA-CRT là một phương pháp mã hóa trong đó các phép tính modulo được chia nhỏ thành các phép tính modulo nhỏ hơn, sau đó được thực hiện độc lập và kết hợp với nhau để đạt được kết quả cuối cùng. Phương pháp này giúp tăng tốc độ tính toán khi mã hóa hoặc giải mã các thông điệp lớn.
- RSA với phương pháp sử dụng bảng mũ: Phương pháp này sử dụng bảng mũ để tính toán các giá trị của các số mũ lớn. Khi một số mũ được tính toán, giá trị đó được lưu trữ trong bảng mũ, điều này giúp giảm thời gian tính toán trong các lần tính toán sau.
- RSA với phương pháp sử dụng đa luồng (multithreading): Phương pháp này sử dụng nhiều luồng để thực hiện các phép tính RSA đồng thời, tăng tốc độ tính toán.
Tuy nhiên, khi sử dụng bất kỳ phương pháp tối ưu hóa nào, cần phải đảm bảo tính an toàn của hệ mật RSA. Một số lỗ hổng an ninh có thể xảy ra nếu các phương pháp tối ưu hóa được sử dụng không đúng cách hoặc không được áp dụng đầy đủ các biện pháp bảo mật. Do đó, nếu không có kinh nghiệm về bảo mật, nên sử dụng các thư viện RSA
# **CryptoHack - RSA writeups**
## **STARTER**
### **RSA Starter 1**
$101^{17}$ mod $22663$ = $19906$
### **RSA Starter 2**
```python
print(pow(12, 0x10001, 17*23))
```
Kết quả là `301`
### **RSA Starter 3**
```
RSA relies on the difficulty of the factorisation of the modulus N. If the primes can be found then we can calculate the Euler totient of N and thus decrypt the ciphertext.
Given N = p*q and two primes:
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
What is the totient of N?
```
```python
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
phi = ( p - 1) * ( q - 1 )
print(phi)
```
$\phi n$ = `882564595536224140639625987657529300394956519977044270821168`
### **RSA Starter 4**
```
The private key d is used to decrypt ciphertexts created with the corresponding public key (it's also used to "sign" a message but we'll get to that later).
The private key is the secret piece of information or "trapdoor" which allows us to quickly invert the encryption function. If RSA is implemented well, if you do not have the private key the fastest way to decrypt the ciphertext is to first factorise the modulus.
In RSA the private key is the modular multiplicative inverse of the exponent e modulo the totient of N.
Given the two primes:
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
and the exponent:
e = 65537
What is the private key d?
```
```python
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
print(d)
```
$d$ = `121832886702415731577073962957377780195510499965398469843281`
### **RSA Starter 5**
```
N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
Use the private key that you found for these parameters in the previous challenge to decrypt this ciphertext:
c = 77578995801157823671636298847186723593814843845525223303932
```
```python
d = 121832886702415731577073962957377780195510499965398469843281
N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932
print(pow(c,d,N))
```
Kết quả `13371337`
### **RSA Starter 6**
Sign the flag crypto{Immut4ble_m3ssag1ng} using your private key and the SHA256 hash function.
[private.key](https://cryptohack.org/static/challenges/private_0a1880d1fffce9403686130a1f932b10.key)
```
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
```
```python
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
# hm = int('259f7a318fa46d43acd6a32ce41c63e91e16d40fc7a8f3dea39dc5df59d1ef31', 16) # from the above Linux utils
hash = SHA256.new(data=b'crypto{Immut4ble_m3ssag1ng}')
S = pow(bytes_to_long(hash.digest()), d, N)
print(hex(S)[2:])
```
## **PRIMES PART 1**
### Factoring
Bài yêu cầu factor số `510143758735509025530880200653196460532653147 ` flag là số nhỏ hơn
Mình dùng [factor](http://www.factordb.com/)
Kết quả là `19704762736204164635843`
### Inferius Prime
Bài cho 2 file [infrius.py](https://cryptohack.org/static/challenges/inferius_e85eea9b19cd68aa71ce850918302bad.py) và [output.txt](https://cryptohack.org/static/challenges/output_4b843d94b6196df152219c3165b9347f.txt)
```python
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD
e = 3
# n will be 8 * (100 + 100) = 1600 bits strong which is pretty good
while True:
p = getPrime(100)
q = getPrime(100)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
if d != -1 and GCD(e, phi) == 1:
break
n = p * q
flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag
```
```python=
n = 742449129124467073921545687640895127535705902454369756401331
e = 3
ct = 39207274348578481322317340648475596807303160111338236677373
```
Khi factor n thử thì ra p,q luôn
```python
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
p, q = 752708788837165590355094155871, 986369682585281993933185289261
n, phi = p * q, (p - 1) * (q - 1)
e = 3
d = inverse(e, phi)
ct = 39207274348578481322317340648475596807303160111338236677373 # from output.txt
print(long_to_bytes(pow(ct, d, n)))
```
Flag `crypto{N33d_b1g_pR1m35}`
### Monoprime
Bài cho file output.txt
```python
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
```
Bài này mình factor thử $n$ thì không được n chính là nguyên tố và $\phi n$ = $n-1$
```python
from Crypto.Util.number import long_to_bytes, inverse
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
d = inverse(e, n-1)
m = pow(ct, d, n)
print(long_to_bytes(m))
```
Flag `crypto{0n3_pr1m3_41n7_pr1m3_l0l}`
### Square Eyes
Bài cho file output.txt
```python
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
```
Sau khi factor n thử thì mình thấy $n$ có dạng $n = p^2$
Khi ấy $\phi n$ = $p*(p-1)$
```python
from Crypto.Util.number import *
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
p = 23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107
phi = p*(p-1)
d = inverse(e,phi)
m = pow(ct,d,n)
print(long_to_bytes(m))
```
Flag `crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}`
### Manyprime
Bài cho file output.txt
```python
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
```
Khi factor n thu được 1 dãy số nnguyên tố
```python
from Crypto.Util.number import inverse, long_to_bytes
N = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ciphertext = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
factor_set = (9282105380008121879, 9303850685953812323, 9389357739583927789, 10336650220878499841, 10638241655447339831, 11282698189561966721, 11328768673634243077, 11403460639036243901, 11473665579512371723, 11492065299277279799, 11530534813954192171, 11665347949879312361, 12132158321859677597, 12834461276877415051, 12955403765595949597, 12973972336777979701, 13099895578757581201, 13572286589428162097, 14100640260554622013, 14178869592193599187, 14278240802299816541, 14523070016044624039, 14963354250199553339, 15364597561881860737, 15669758663523555763, 15824122791679574573, 15998365463074268941, 16656402470578844539, 16898740504023346457, 17138336856793050757, 17174065872156629921, 17281246625998849649)
phi = 1
for prime in factor_set:
phi *= (prime - 1)
d = inverse(e, phi)
plaintext = pow(ciphertext, d, N)
print(long_to_bytes(plaintext))
```
Flag `crypto{700_m4ny_5m4ll_f4c70r5}`
## PUBLIC EXPONENT
### Salty
Bài cho 2 file salty.ppy và output.txt
```python
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
e = 1
d = -1
while d == -1:
p = getPrime(512)
q = getPrime(512)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
n = p * q
flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag
```
```python
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
```
Nhìn soure code ta thấy $e = 1$ mà $c < n$ suy ra $m = c$
```python=
from Crypto.Util.number import *
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
m = ct % n
print(long_to_bytes(m))
```
Flag `crypto{saltstack_fell_for_this!}`
### Modulus Inutilis
Bài cho 2 file modulus_inutilis.py và output.txt
```python
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
e = 3
d = -1
while d == -1:
p = getPrime(1024)
q = getPrime(1024)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
n = p * q
flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag
```
```python
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
```
Bài này vì e = 3 và c < n nên phép module không ảnh hưởng đến m hay $m^3$ < n tính m bằng căn 3 của c
```python
from gmpy2 import iroot
from Crypto.Util.number import *
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
c = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
print(long_to_bytes(iroot(c,3)[0]))
```
Flag `crypto{N33d_m04R_p4dd1ng}`
### Everything is Big
Bài cho 2 file soure.py và output.txt
```python
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, bytes_to_long
FLAG = b"crypto{?????????????????????????}"
m = bytes_to_long(FLAG)
def get_huge_RSA():
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
while True:
d = getPrime(256)
e = pow(d,-1,phi)
if e.bit_length() == N.bit_length():
break
return N,e
N, e = get_huge_RSA()
c = pow(m, e, N)
print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')
```
```python
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
```
Bài này sau khỉ thử chuyển e sang số nguyên mình thấy e khá lớn nên mình thử owiener attack
```python
import owiener
from Crypto.Util.number import long_to_bytes
N = int('0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d',16)
e = int('0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3',16)
c = int('0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474',16)
d = owiener.attack(e,N)
m = pow(c,d,N)
print(long_to_bytes(m))
```
Flag `crypto{s0m3th1ng5_c4n_b3_t00_b1g}`
### Crossed Wires
Bài cho 2 file soure.py và output.txt
```python
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime
FLAG = b"crypto{????????????????????????????????????????????????}"
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)
my_key = (N, d)
friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]
cipher = bytes_to_long(FLAG)
for key in friend_keys:
cipher = pow(cipher, key[1], key[0])
print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")
```
```python
My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
```
Đọc ssoure code mình sẽ thấy được cipher = pow(cipher,key[1],key[0]) , có nghĩa là cipher sẽ mũ e mod n lần lượt trong từng cặp $(e_i,n)$ của friend_key.
Sau khi factor mình tìm được p,q từ đó tính được $\phi n$
Vậy để decrypt thì từ phi (n) sẽ tìm được d của từng cặp và $m = pow(c,d_n,n)$
với $d_n =d1 *d2 * …d_i$
```python=
from Crypto.Util.number import long_to_bytes, inverse
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
e0 = 65537
e1, e2, e3, e4, e5 = 106979, 108533, 69557, 97117, 103231
p = 161469718942256895682124261315253003309512855995894840701317251772156087404025170146631429756064534716206164807382734456438092732743677793224010769460318383691408352089793973150914149255603969984103815563896440419666191368964699279209687091969164697704779792586727943470780308857107052647197945528236341228473
q = 134460556242811604004061671529264401215233974442536870999694816691450423689575549530215841622090861571494882591368883283016107051686642467260643894947947473532769025695530343815260424314855023688439603651834585971233941772580950216838838690315383700689885536546289584980534945897919914730948196240662991266027
ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
phi = (p-1)*(q-1)
d1 = inverse(e1, phi)
d2 = inverse(e2, phi)
d3 = inverse(e3, phi)
d4 = inverse(e4, phi)
d5 = inverse(e5, phi)
d_n = d1*d2*d3*d4*d5
m = long_to_bytes(pow(ct, d_n, n))
print(m)
```
Flag `crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}`
### Everything is Still Big
Soure code bài cho
```python
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, bytes_to_long, inverse
from random import getrandbits
from math import gcd
FLAG = b"crypto{?????????????????????????????????????}"
m = bytes_to_long(FLAG)
def get_huge_RSA():
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
while True:
d = getrandbits(512)
if (3*d)**4 > N and gcd(d,phi) == 1:
e = inverse(d, phi)
break
return N,e
N, e = get_huge_RSA()
c = pow(m, e, N)
print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')
```
```python
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
```
Sau khi unhex và factor thử n mình tìm luôn được p,q và tìm được flag nhưng code ở dưới dùng owiener attack cũng được luôn :))
```python
import owiener
from Crypto.Util.number import long_to_bytes
N = int('0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b',16)
e = int('0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f',16)
c = int('0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5',16)
d = owiener.attack(e,N)
m = pow(c,d,N)
print(long_to_bytes(m))
```
Flag: `crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}`
### Endless Emails
Bài cho soure code johan.py
```python
#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, getPrime
from secret import messages
def RSA_encrypt(message):
m = bytes_to_long(message)
p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 3
c = pow(m, e, N)
return N, e, c
for m in messages:
N, e, c = RSA_encrypt(m)
print(f"n = {N}")
print(f"e = {e}")
print(f"c = {c}")
```
output.txt
Đọc code bài cho và thấy e = 3 và chó nhiều cặp ($e_i,n_i)$
nên mình dùng Hastad Broadcast Attack kết hợp định lí [số dư Trung Hoa](https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
để solve
```python
from itertools import combinations
from Crypto.Util.number import *
from gmpy2 import iroot
def crt(remainders, mod):
assert len(remainders)== len(mod)
N = 1
for i in mod:
N*=i
Ni = []
for i in range(len(mod)):
Ni.append(N//mod[i])
Y=[]
for i in range(len(mod)):
Y.append(pow(Ni[i],-1,mod[i]))
res = 0
for i in range(len(mod)):
res+=remainders[i]*Ni[i]*Y[i]
return res%N
n0 = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
e = 3
c0 = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
n1 = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
e = 3
c1 = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172
n2 = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
e = 3
c2 = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153
n3 = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
e = 3
c3 = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577
n4 = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
e = 3
c4 = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805
n5 = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
e = 3
c5 = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749
n6 = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
e = 3
c6 = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144
n=[n0,n1,n2,n3,n4,n5,n6]
c=[c0,c1,c2,c3,c4,c5,c6]
for i,j,k in combinations(range(len(n)),3):
mod=[n[i],n[j],n[k]]
remains =[c[i],c[j],c[k]]
m =iroot(crt(remains,mod),3)
flag=long_to_bytes(m[0])
if b'crypto{' in flag:
print(flag)
```
Flag: `crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}`
## PRIMES PART 2
### Infinite Descent
Bài cho soure code descent.py
```python
#!/usr/bin/env python3
import random
from Crypto.Util.number import bytes_to_long, isPrime
FLAG = b"crypto{???????????????????}"
def getPrimes(bitsize):
r = random.getrandbits(bitsize)
p, q = r, r
while not isPrime(p):
p += random.getrandbits(bitsize//4)
while not isPrime(q):
q += random.getrandbits(bitsize//8)
return p, q
m = bytes_to_long(FLAG)
p, q = getPrimes(2048)
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
```python
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
```
Mặc dù n khá lớn nhưng khi đem đi factor mình vẫn tìm đc p,q dễ dàng có được flag
```python
from Crypto.Util.number import *
from gmpy2 import *
p = 19579267410474709598749314750954211170621862561006233612440352022286786882372619130071639824109783540564512429081674132336811972404563957025465034025781206466631730784516337210291334356396471732168742739790464109881039219452504456611589154349427303832789968502204300316585544080003423669120186095188478480761108168299370326928127888786819392372477069515318179751702985809024210164243409544692708684215042226932081052831028570060308963093217622183111643335692361019897449265402290540025790581589980867847884281862216603571536255382298035337865885153328169634178323279004749915197270120323340416965014136429743252761521
q = 19579267410474709598749314750954211170621862561006233612440352022286786882372619130071639824109783540564512429081674132336811972404563957025465034025781206466631730784516337210291334356396471732168742739790464109881039219452504456611589154349427303832789968502204300316585544080003423669120186095188478480761108168299370326928127888786819392372477069515318179751702985809024210164243409544692708684215042226932081052831028570060308963093217622183111643335692362635203582868526178838018946986792656819885261069890315500550802303622551029821058459163702751893798676443415681144429096989664473705850619792495553724950931
n =383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
```
Flag: `crypto{f3rm47_w45_4_g3n1u5}`
### Marin's Secrets
Bài cho soure code marin.py
```python
#!/usr/bin/env python3
import random
from Crypto.Util.number import bytes_to_long, inverse
from secret import secrets, flag
def get_prime(secret):
prime = 1
for _ in range(secret):
prime = prime << 1
return prime - 1
secrets = random.shuffle(secrets)
m = bytes_to_long(flag)
p = get_prime(secrets[0])
q = get_prime(secrets[1])
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
```python
n: 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e: 65537
c: 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
```
Đọc tiêu đề thì mình sẽ nghĩ đến Mersene Attack. [Marin Mersenne](https://en.wikipedia.org/wiki/Marin_Mersenne) là một nhà toán học người pháp nổi tiếng ở thế kỷ 17 được biết đến với việc nghiên cứu các [số nguyên tố Mersenne](https://vi.wikipedia.org/wiki/S%E1%BB%91_nguy%C3%AAn_t%E1%BB%91_Mersenne) với dạng $2^n -1$ .Và hiện nay có khoảng [50 số nguyên tố Mersenne được biết đến.](https://vi.wikipedia.org/wiki/Danh_s%C3%A1ch_s%E1%BB%91_nguy%C3%AAn_t%E1%BB%91_Mersenne_v%C3%A0_s%E1%BB%91_ho%C3%A0n_h%E1%BA%A3o)
Dựa vào list 50 số nguyên tố Mersenne thì ta sẽ tìm được p,q. Có được p,q thì ta sẽ tìm ra được flag
```python
from Crypto.Util.number import *
from gmpy2 import *
n= 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e=65537
c= 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
prime_list = [2,3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933]
for prime in prime_list:
p = 2**prime - 1
if n % p == 0:
q = n // p
print("p = ",p)
print("q = ",q)
break
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
print(flag)
```
Flag: `crypto{Th3se_Pr1m3s_4r3_t00_r4r3}`
### Fast Primes
Bài cho soure code fast_prime.py
```python
#!/usr/bin/env python3
import math
import random
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, inverse
from gmpy2 import is_prime
FLAG = b"crypto{????????????}"
primes = []
def sieve(maximum=10000):
# In general Sieve of Sundaram, produces primes smaller
# than (2*x + 2) for a number given number x. Since
# we want primes smaller than maximum, we reduce maximum to half
# This array is used to separate numbers of the form
# i+j+2ij from others where 1 <= i <= j
marked = [False]*(int(maximum/2)+1)
# Main logic of Sundaram. Mark all numbers which
# do not generate prime number by doing 2*i+1
for i in range(1, int((math.sqrt(maximum)-1)/2)+1):
for j in range(((i*(i+1)) << 1), (int(maximum/2)+1), (2*i+1)):
marked[j] = True
# Since 2 is a prime number
primes.append(2)
# Print other primes. Remaining primes are of the
# form 2*i + 1 such that marked[i] is false.
for i in range(1, int(maximum/2)):
if (marked[i] == False):
primes.append(2*i + 1)
def get_primorial(n):
result = 1
for i in range(n):
result = result * primes[i]
return result
def get_fast_prime():
M = get_primorial(40)
while True:
k = random.randint(2**28, 2**29-1)
a = random.randint(2**20, 2**62-1)
p = k * M + pow(e, a, M)
if is_prime(p):
return p
sieve()
e = 0x10001
m = bytes_to_long(FLAG)
p = get_fast_prime()
q = get_fast_prime()
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(FLAG)
assert cipher.decrypt(ciphertext) == FLAG
exported = key.publickey().export_key()
with open("key.pem", 'wb') as f:
f.write(exported)
with open('ciphertext.txt', 'w') as f:
f.write(ciphertext.hex())
```
key.pem
```pem=
-----BEGIN PUBLIC KEY-----
MFswDQYJKoZIhvcNAQEBBQADSgAwRwJATKIe3jfj1qY7zuX5Eg0JifAUOq6RUwLz
Ruiru4QKcvtW0Uh1KMp1GVt4MmKDiQksTok/pKbJsBFCZugFsS3AjQIDAQAB
-----END PUBLIC KEY-----
```
ciphertext.txt
```hex=
249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28
```
Đọc soure code mình thấy bài dùng thuật toán sàng số nguyên tố sieve sau đó mã hóa `flag` bằng RSA kết hợp với OAEP padding .Sau khi đọc file pem mình có được n,e và đem n đi facor thì tìm được p,q
```python=
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import long_to_bytes
from Crypto.Util import number
key = RSA.importKey(open("key.pem", "rb").read())
print("n= ",key.n)
print("e= ",key.e)
e= 65537
n = 4013610727845242593703438523892210066915884608065890652809524328518978287424865087812690502446831525755541263621651398962044653615723751218715649008058509
p = 51894141255108267693828471848483688186015845988173648228318286999011443419469
q = 77342270837753916396402614215980760127245056504361515489809293852222206596161
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
hexc = 0x249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28
c = long_to_bytes(hexc)
m = cipher.decrypt(c)
print(m)
```
Flag: `crypto{p00R_3570n14}`
### Ron was Wrong, Whit is Right
Bài cho soure code excerpt.py
```python
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
msg = "???"
with open('21.pem') as f:
key = RSA.importKey(f.read())
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(msg)
with open('21.ciphertext', 'w') as f:
f.write(ciphertext.hex())
```
Vì đọc code thấy key và cipher được lưu ở file 21.pem và 21.ciphertext tương tự bài trước mình đọc file có được n,e đem n đi factor và tìm đc p,q
```python
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
key = RSA.importKey(open("21.pem", "rb").read())
e = key.e
n = key.n
p = 919031168254299342928662994540730760042229248845820491699169870943314884504551963184014786520812939038906152950817942941469675496074887272906954399256046690838233813273902630076899906873722574023918253104149453601408405078374008695616160025877687382663027910687942091698042309812910101246025081363544171351624307177908410700904833438480012985928358897861427063761678614898919524867442676631453135379994570031284289815099294504127712924001149921480778993635917803466637717023744788311275545126346774536416864472035644211758788016642401235014385037912224180351022196262011724157012443048941426178651665266181311662824205620324073087330858064769424755443807165558567191049013947419763315902476674266627953223373671797370373786249718677582213173537848582863398367624397247597103174897140005790273296171101569756006898658668311846034013183862374297777882433967015111727139360441681664840944403450472574336901043555319067050153928231938431298082827397506406624964952344826628463723499263165279281720105570577138817805451223334196017505528543229067732013216932022575286870744622250293712218581458417969597311485156075637589299870500738770767213366940656708757081771498126771190548298648709527029056697749965377697006723247968508680596118923
q = 991430390905926023965735525726256769345153760248048478891327804533279477721590201738061124861790305326884541900044434890157058142414306020739922709698601329762087825767461256626800629782378634339618941488765491437487541851308806651586976069659042714378353883168031522106709494592827914376213512564492771821921367377484213072867988877925314809325159382342584541006645302760204539354879391605736604946702073863673524002591877977949645618863730441482821840664748508050205004505250025193611888170440612737112479006348533153568103452396596042639466753099280111709882461562564978070397786887446291916733276692400981917025361391646188802038772976331121474570242334921390569285834250256522656433623912544555266998750630136756355560927237594975904642791712318215315246754105993145827690531584325461597482035600919501967088106457091199733024323755210212616553447076697617349235377466327471959683763796707566328536834402308887105044128592177681553611608618850780128709949316259039664054913946726480968288231015999572777436469163437066403964134928735809253108394078092917006632332098357725950865697047565284013456253933234017983509582245874130968218422573483012858388392588302838940565560162598810462310034964473576147200222580784694005333482381
c = 0xc62d91677825632cb8ac9d2fbee7490fca70b3f067bd8d811fa446a21001de7943cacafc429b2513d3f20c3224d212ca2937a4a4ea10792a1c498b791e978e4b050b525576bc68421e40d9f420c0b8a07778daf69edf2095bf48222896bb2d6581288ce7a2e7aec15a88a440ff1a1e48beb56f68b4f860d1f64a6ec8cafed90846b7d893bc482df69c8478d5a0d6fc2d043cdd97178740a9eb59d2576b5136200c8ea77e648c88e6c5104ca5d0c6add2fc2c8569ce909f8461e7fa3d901fe67eaeff656399d4751fedba9973e246427e0c7a217f5bdc3edcb5033f17b5ef53419e340355a809eb46f48f538e880abd6f72212b02d3dbf2c4f633a503e648d1a835c4574b23e329e1c51078ea7cbb7533e771899498d4a5760bc0799b7e046f268f098fe0b57de47cd70ccf01ad3c9daec5027f306141bfe7a6c0bd29ee6caf94c7433c25e34ee974005e2360337cb6b3cec5eaf5d31d19f01435f4cdcaa455a18e78dee078395b8ad14b9c3a0d817dc1e3109c7b8af35ab3a5950bf47d5e621f9373ef421540052aac307ecea91f9c29c14bfd81b41d4c5a9b34a8ec2fa1ae06c3d881f39286c3d8dbb1849602fecc27bb135f7dd443e2598d247d1182d350b04be1ac0a734cb0e852a36902d88066ac375a35e279b126e413a97aaa35a0ba933f7b8d574c298332ce428c181464b240709a414af1b77103441b6ccfd0790eccea5926844054903c83f4cb415d600a6b7bc771c9e7a86394a2b427ebe8edec08b8095f561827716898e11caf6f0fe562af8a69f7b6469f0e86bdcc32f429f10821c763b34307efc5b2ae7fd524a07e5d0b762c096f025a3f240fb7bd3554582dcce32c175867d93970b0422e17870ec58f2a305545a3d284b3abb2d21a45ad8fd5faed0dc66312a5aa2f994606a51cd6682acd48ea3fb883f0611e1e5c2fb4047b5c80815ba5d3bcfefaf121bfde4d5c91ee27bb899ef0d29fa5c6dc4223ac2bfcff0217d08579a13e9b02dc97aa2622df62eeaaa38bb3bd087cdd209f03e8926a951e90eaa0f678a252a067ac66402a4c85865931689ed3b33f9f6de0c499f140ef508dfba6007a607a271dcbec18a61f7488bba34d143f93bc259310ffbf23f3391734d8d8811a4be8abf6382e55c2ccbfd80b1559d907fd8d46e0431cdbcd8fdb06d57973437f7b8ff5efc5a53c80d552e8fe622971f7376eeea35f4df9b32ada93e531a52b63ba13f6b7bf61ab337d6d93feb0e8c8a309dfa7e5f50e8cf9655b73ae64822b50db5312f35f4718b0668305065ea283ddf8f0a4e8f486ee9d119ebc584be1837b3d959a25ace208ffac2fb703390a72d3027b64fdd1955b513c0403f09232efa1794a277e0be3f4f9f3a6fd23c6e52101e723cef5db7a2a18a107cd522379adb40c5ed36b26cdf53a1000d7d576f1157b42aac3d3ee011275
d = pow(e, -1, (p-1)*(q-1))
key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
print(cipher.decrypt(bytes.fromhex(hex(c)[2:])).decode())
```
Flag: `crypto{3ucl1d_w0uld_b3_pr0ud}`
### RSA Backdoor Viability
complex_primes.py
```python
n = 709872443186761582125747585668724501268558458558798673014673483766300964836479167241315660053878650421761726639872089885502004902487471946410918420927682586362111137364814638033425428214041019139158018673749256694555341525164012369589067354955298579131735466795918522816127398340465761406719060284098094643289390016311668316687808837563589124091867773655044913003668590954899705366787080923717270827184222673706856184434629431186284270269532605221507485774898673802583974291853116198037970076073697225047098901414637433392658500670740996008799860530032515716031449787089371403485205810795880416920642186451022374989891611943906891139047764042051071647203057520104267427832746020858026150611650447823314079076243582616371718150121483335889885277291312834083234087660399534665835291621232056473843224515909023120834377664505788329527517932160909013410933312572810208043849529655209420055180680775718614088521014772491776654380478948591063486615023605584483338460667397264724871221133652955371027085804223956104532604113969119716485142424996255737376464834315527822566017923598626634438066724763559943441023574575168924010274261376863202598353430010875182947485101076308406061724505065886990350185188453776162319552566614214624361251463
e = 65537
c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388
```
Đầu tiên mình lại factor n và vẫn tìm được p,q dễ dàng có flag
```python
from Crypto.Util.number import *
n = 709872443186761582125747585668724501268558458558798673014673483766300964836479167241315660053878650421761726639872089885502004902487471946410918420927682586362111137364814638033425428214041019139158018673749256694555341525164012369589067354955298579131735466795918522816127398340465761406719060284098094643289390016311668316687808837563589124091867773655044913003668590954899705366787080923717270827184222673706856184434629431186284270269532605221507485774898673802583974291853116198037970076073697225047098901414637433392658500670740996008799860530032515716031449787089371403485205810795880416920642186451022374989891611943906891139047764042051071647203057520104267427832746020858026150611650447823314079076243582616371718150121483335889885277291312834083234087660399534665835291621232056473843224515909023120834377664505788329527517932160909013410933312572810208043849529655209420055180680775718614088521014772491776654380478948591063486615023605584483338460667397264724871221133652955371027085804223956104532604113969119716485142424996255737376464834315527822566017923598626634438066724763559943441023574575168924010274261376863202598353430010875182947485101076308406061724505065886990350185188453776162319552566614214624361251463
e = 65537
c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388
q = 20365029276121374486239093637518056591173153560816088704974934225137631026021006278728172263067093375127799517021642683026453941892085549596415559632837140072587743305574479218628388191587060262263170430315761890303990233871576860551166162110565575088243122411840875491614571931769789173216896527668318434571140231043841883246745997474500176671926153616168779152400306313362477888262997093036136582318881633235376026276416829652885223234411339116362732590314731391770942433625992710475394021675572575027445852371400736509772725581130537614203735350104770971283827769016324589620678432160581245381480093375303381611323
p = 34857423162121791604235470898471761566115159084585269586007822559458774716277164882510358869476293939176287610274899509786736824461740603618598549945273029479825290459062370424657446151623905653632181678065975472968242822859926902463043730644958467921837687772906975274812905594211460094944271575698004920372905721798856429806040099698831471709774099003441111568843449452407542799327467944685630258748028875103444760152587493543799185646692684032460858150960790495575921455423185709811342689185127936111993248778962219413451258545863084403721135633428491046474540472029592613134125767864006495572504245538373207974181
phi = (q-1) * (p-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
#crypto{I_want_to_Break_Square-free_4p-1}
```
Google Drive
Gist
Clipboard
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
