# **TASK4**
# **Group (Abstract Algebra)**
## Định nghĩa
Trong toán học, một nhóm (group) là một tập hợp các phần tử được trang bị một phép toán hai ngôi kết hợp hai phần tử bất kỳ của tập hợp thành một phần tử thứ ba thỏa mãn bốn điều kiện gọi là tiên đề nhóm, lần lượt là tính đóng, tính kết hợp, sự tồn tại của phần tử đơn vị và tính khả nghịch. Một trong những ví dụ quen thuộc nhất về nhóm đó là tập hợp các số nguyên cùng với phép cộng; khi thực hiện cộng hai số nguyên bất kỳ luôn thu được một số nguyên khác. Hình thức trình bày trừu tượng dựa trên tiên đề nhóm, tách biệt nó khỏi bản chất cụ thể của bất kỳ nhóm đặc biệt nào và phép toán trên nhóm, cho phép nhóm bao trùm lên nhiều thực thể với nguồn gốc toán học rất khác nhau trong đại số trừu tượng và rộng hơn, và có thể giải quyết một cách linh hoạt, trong khi vẫn giữ lại khía cạnh cấu trúc căn bản của những thực thể ấy. Sự có mặt khắp nơi của nhóm trong nhiều lĩnh vực bên trong và ngoài toán học khiến chúng trở thành nguyên lý tổ chức trung tâm của toán học đương đại.
## Tính chất
Trong đại số trừu tượng, một nhóm (group) là một tập hợp các phần tử kèm theo một phép toán nhất định trên tập hợp đó, thỏa mãn các tính chất sau:
- Tính đóng: Cho hai phần tử a và b bất kỳ trong nhóm G, thì a * b cũng phải thuộc G.
- Tính kết hợp: Với mọi $a, b, c$ trong nhóm G, ta có $(a * b) * c = a * (b * c)$, trong đó $*$ là phép toán trên nhóm.
- Tồn tại phần tử đơn vị: Tồn tại một phần tử $e$ trong nhóm G sao cho với mọi $a$ trong nhóm G, ta có $a * e = e * a = a$.
- Tồn tại phần tử nghịch đảo: Với mọi a trong nhóm G, tồn tại một phần tử $a^{-1}$ trong nhóm G sao cho $a * a^{-1} = a^{-1} * a = e$.
- Tính giao hoán (tùy chọn): Nếu phép toán * trên nhóm G là phép giao hoán ($a * b = b * a$ với mọi $a, b$ trong G), thì nhóm G được gọi là nhóm Abel (hay nhóm commutative).
Như vậy, một nhóm bao gồm một tập hợp các phần tử và một phép toán trên tập hợp đó, thỏa mãn các tính chất kết hợp, phần tử đơn vị và phần tử nghịch đảo. Các nhóm rất quan trọng trong đại số trừu tượng và được sử dụng rộng rãi trong nhiều lĩnh vực của toán học và khoa học khác.
## Order của một nhóm
Order (Bậc) của một nhóm (Group) là số lượng phần tử trong nhóm đó. Bậc của một nhóm thường được ký hiệu bằng cấp của nhóm và thường được ký hiệu là |G|.
Ví dụ, nhóm $Z_n$ là nhóm tất cả các phần tử nguyên tố cùng với phép toán cộng theo modulo $n$. Bậc của nhóm $Z_n$ là $n$, vì nó có $n$ phần tử.
Như vậy, việc tính bậc của một nhóm là rất quan trọng trong đại số trừu tượng và có thể được sử dụng để xác định tính chất của các nhóm và giải các bài toán liên quan đến nhóm.
Order (bậc) của một nhóm (Group) còn có một số tính chất quan trọng như sau:
1. Định lý Lagrange: Nếu H là một nhóm con của G, thì bậc của H phải chia hết cho bậc của G. Cụ thể hơn, nếu |G| = m và |H| = n, thì n phải chia hết cho m.
2. Theo định lý Euler, nếu a và n là hai số nguyên tố cùng nhau, thì bậc của nhóm $Z_n^*$ là $\phi(n)$, trong đó $\phi(n)$ là hàm số Euler, biểu thị số lượng số nguyên tố nhỏ hơn n. Nói cách khác, |$Z_n^*$| = $\phi(n)$.
3. Những nhóm có bậc là số nguyên tố chỉ có hai nhóm con là {e} và chính nó. Những nhóm này được gọi là nhóm nguyên tố hoặc nhóm Abel nguyên tố.
4. Nếu bậc của một nhóm là số nguyên tố, thì nhóm đó phải là nhóm Abel.
5. Nhóm có bậc là một số chính phương không nhất thiết là nhóm Abel. Ví dụ, nhóm đơn vị bình phương (nhóm các phần tử trong đó có bậc là bốn) không phải là nhóm Abel.
Những tính chất này giúp cho việc nghiên cứu và xác định tính chất của các nhóm trong đại số trừu tượng trở nên dễ dàng hơn.
# CryptoHack DIFFIE - HELLMAN
## STARTER
### Diffie-Hellman Starter 1
Challenge cho p = 991 , g = 209
Yêu cầu tìm d là nghịch đảo của g mod p ( `g*d mod 991 = 1`)
Đáp án là `569`
### Diffie-Hellman Starter 2
Challenge yêu cầu tìm phần tử sinh $g$ nhỏ nhất trên trường $F_p$ với p = 28151
Brute-force bằng python
```python
def is_generator(k, p):
for n in range(2, p):
if pow(k, n, p) == k:
return False
return True
p = 28151
for k in range(p):
if is_generator(k, p):
print(k)
```
Hoặc có thể dùng sage
Đáp án là g = `7`
### Diffie-Hellman Starter 3
```
g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
Calculate the value of g^a mod p for
a: 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
```
Challenge yêu cầu tính $g^a$ mod $p$
```python
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
a = 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
g = 2
print(pow(g,a,p))
```
Kết quả là `1806857697840726523322586721820911358489420128129248078673933653533930681676181753849411715714173604352323556558783759252661061186320274214883104886050164368129191719707402291577330485499513522368289395359523901406138025022522412429238971591272160519144672389532393673832265070057319485399793101182682177465364396277424717543434017666343807276970864475830391776403957550678362368319776566025118492062196941451265638054400177248572271342548616103967411990437357924`
### Diffie-Hellman Starter 4
```
Now it's time to calculate a shared secret using data received from your friend
Alice. Like before, we will be using the NIST parameters:
g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
You have received the following integer from Alice:
A: 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
You generate your secret integer b and calculate your public one B, which you
send to Alice.
b: 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
B: 518386956790041579928056815914221837599234551655144585133414727838977145777213383018096662516814302583841858901021822273505120728451788412967971809038854090670743265187138208169355155411883063541881209288967735684152473260687799664130956969450297407027926009182761627800181901721840557870828019840218548188487260441829333603432714023447029942863076979487889569452186257333512355724725941390498966546682790608125613166744820307691068563387354936732643569654017172
You and Alice are now able to calculate a shared secret, which would be
infeasible to calculate knowing only {g,p,A,B}.
What is your shared secret?
```
Challenge yêu cầu tính `shared secret`
- $A$ = $g^a$ mod $p$
- $B$ = $g^b$ mod $p$
- $key$ = $A^b$ mod $p$ = $B^a$ mod $p$ = $g^{a*b}$ mod $p$
```python
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
b = 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
print(pow(A, b, p))
```
### Diffie-Hellman Starter 5
```
Alice wants to send you her secret flag and asks you to generate a shared secret with her. She also tells you she will be using the NIST standard:
g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
You receive the following integer from Alice:
A: 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
You then generate your secret integer and calculate your public one, which you send to Alice.
b: 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
B: 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581
Individually you each use the shared secret to derive an AES private key. This allows you to encrypt large amounts of data over your channel without needing to exchange keys again.
Alice sends you the following IV and ciphertext:
{'iv': '737561146ff8194f45290f5766ed6aba', 'encrypted_flag': '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'}
Decrypt this to obtain your flag!
```
source.py
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
import os
from secret import shared_secret
FLAG = b'crypto{????????????????????????????}'
def encrypt_flag(shared_secret: int):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Encrypt flag
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pad(FLAG, 16))
# Prepare data to send
data = {}
data['iv'] = iv.hex()
data['encrypted_flag'] = ciphertext.hex()
return data
print(encrypt_flag(shared_secret))
```
decrypt.py
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
shared_secret = ?
iv = ?
ciphertext = ?
print(decrypt_flag(shared_secret, iv, ciphertext))
```
Challenge cho 2 file python code source.py để mã hóa và decrypt.py để giải mã nhưng source code file decrypt.py còn thiếu giá trị của `share_secret`,`iv` và `ciphertext`
Với `iv` và `cipher` bài cho kết hợp với `share_secret` tính theo cách của challenge trước ta có thể tìm được flag
```python
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from hashlib import sha1
def decrypt_flag(shared_secret, iv, ciphertext):
key = sha1(str(shared_secret).encode()).digest()[:16]
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
plaintext = AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext)
return unpad(plaintext, 16).decode()
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
shared_secret = pow(A, b, p)
iv = "737561146ff8194f45290f5766ed6aba"
ciphertext = "39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
Flag: `crypto{sh4r1ng_s3cret5_w1th_fr13nd5}`
## MAN IN THE MIDDLE
### Parameter Injection
```
You're in a position to not only intercept Alice and Bob's DH key exchange, but also rewrite their messages. Think about how you can play with the DH equation that they calculate, and therefore sidestep the need to crack any discrete logarithm problem.
Use the script from "Diffie-Hellman Starter 5" to decrypt the flag once you've recovered the shared secret.
Connect at nc socket.cryptohack.org 13371
```
Đầu tiên,gửi cho Bob một bộ g,p,A bất kì không quan tâm phản hồi của Bob.Tiếp theo gửi B = "0x01" khi này share_secret = B^a mod p .Vì B = 1 nên share_secret cũng sẽ bằng 1 với mọi a.Sau khi có được share_secret ,iv,ciphertext ta có thể tìm được flag
```python
from Crypto.Util.Padding import unpad
from json import loads, dumps
from Crypto.Cipher import AES
from hashlib import sha1
from pwn import remote
def decrypt_flag(shared_secret, iv, ciphertext):
key = sha1(str(shared_secret).encode()).digest()[:16]
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
plaintext = AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext)
return plaintext.decode()
io = remote("socket.cryptohack.org", 13371)
io.readline()
io.sendline(dumps({"p":"0x123", "g":"0x123", "A":"0x123"}).encode())
io.readline()
io.sendline(dumps({"B":"0x01"}).encode())
io.readuntil(b"from Alice: ")
recv = loads(io.readline())
iv, ciphertext = recv["iv"], recv["encrypted_flag"]
shared_secret = 1
print(decrypt_flag(shared_secret, iv, ciphertext))
```
Flag: `crypto{n1c3_0n3_m4ll0ry!!!!!!!!}`
### Export-grade
```
Alice and Bob are using legacy codebases and need to negotiate parameters they both support. You've man-in-the-middled this negotiation step, and can passively observe thereafter. How are you going to ruin their day this time?
Connect at nc socket.cryptohack.org 13379
```
Khi kết nối đến địa chỉ của challenge ta thấy các kiểu hỗ trợ DH1536,DH1024,DH512,DH128,DH64. Ta chọn thử DH64 .System trả về khóa công khai của Alice ,có thể thấy p ở đây tương đối nhỏ
Theo công thức A = g^a^ mod p ,có thể tìm được a khi đã biết g,A,p bằng cách sử dụng thuật toán [Pohlig-Hellman](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm)
```python
from sympy.ntheory.residue_ntheory import discrete_log
from Crypto.Util.Padding import unpad
from json import loads, dumps
from Crypto.Cipher import AES
from hashlib import sha1
from pwn import remote
def decrypt_flag(shared_secret, iv, ciphertext):
key = sha1(str(shared_secret).encode()).digest()[:16]
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
plaintext = AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext)
return plaintext.decode()
io = remote("socket.cryptohack.org", 13379)
io.readline()
io.sendline(dumps({"supported": ["DH64"]}).encode())
io.readline()
io.sendline(dumps({"chosen": "DH64"}).encode())
io.readuntil(b"from Alice: ")
recv = loads(io.readline())
p = int(recv["p"], 16)
g = int(recv["g"], 16)
A = int(recv["A"], 16)
a = discrete_log(p, A, g)
io.readuntil(b"from Bob: ")
recv = loads(io.readline())
B = int(recv["B"], 16)
io.readuntil(b"from Alice: ")
recv = loads(io.readline())
iv = recv["iv"]
ciphertext = recv["encrypted_flag"]
shared_secret = pow(B, a, p)
print(decrypt_flag(shared_secret, iv, ciphertext))
```
Flag: crypto{d0wn6r4d35_4r3_d4n63r0u5}
### Static Client
```
You've just finished eavesdropping on a conversation between Alice and Bob. Now you have a chance to talk to Bob. What are you going to say?
Connect at nc socket.cryptohack.org 13373
```
Khi kết nối đến hệ thống ,hệ thống cho 1 bộ khóa công khai của Alice, tiêu đề challenge cho thấy Alice và Bob đã sử dụng khóa bí mật tĩnh trong quá trình tạo khóa.Khi gửi khóa công Khai của Alice Bob sẽ gửi lại khóa Công khai của anh ta B .Khi chúng ta gửi cho Bob giá trị của khóa công khai của Alice với g = A . Bob sau đó sẽ tính toán và gửi cho chúng ta bí mật được chia sẻ.
Ta có B = g^b^ (mod p) và s = A^b^ (mod p) ;
đặt g = A thì B = A^b^ (mod p) và B = s
Gửi lại cho Bob :`{"p": "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", "g": "0x53adb6626ed68ed83e3b9689e66f3f750be072a139ad656e1b81288eeb4bc62641617dd6355e5c55ae2831725248547ae85c130382b8a36a29def045b9a7c502689481649bc7a6f49beea37d4264378a05839a7461e74952ccb0f86eb5541dc87c4a1aa0b26c81dc1fdc7266a339a329df35e378627eb6fbdc4961e1b376e74bfe31c459df77e07cd6af63f8fd3c86be461fa532e3c1ecbc398bfa783ab11c8473c9354cad5e91a1f7830e8f6323b152993d70d602ba28e251c76bc7a57cfeaf", "A": "0x01"}`
Thu được shared_secret = `0xab76f5e66eb3c21e6b5670e0adbbd257e17b0494a89758f63a242ef8be080fb32984c685569accf111a1d52bc62ea9c3d22a866d653f94bde45e8dd1c5b69c56a8a5687e0de2bac44bfa2b98637a3fca62c0b5b59fe9099170afcc0c6c5c2f42bf44406b63e13f8ef385caa76eeeef76d3499025175361d0868ab5e21be3e5478e03deb380e5fc02b4bb6c88ada521648b091135b3f6329a64e49ca5699ca5b8fd326f10dac377b1a112e1be2e3fb5c1fe7960095d27e65efc6df2d8383b17fd`
với iv = `72abca4ba196bd3562acf269f8578551`
và ciphertext = `c22ca2e6545abcec87fed18ba449944219e9556fae52ae7975567823e20cd451`
Ta có thể tìm được flag
```python
from sympy.ntheory.residue_ntheory import discrete_log
from Crypto.Util.Padding import unpad,pad
import json
import codecs
import hashlib
from Crypto.Cipher import AES
from pwn import remote
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
print(plaintext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
share_secret = 1614388563332122752098703510390923066134536457896374139538253423986871371903043504640865084326776078532097286698839936506357011746373743987728755240984142277415357031755980954699167699770980502561781192539972817602177232642236592991738651825453814512757268184485996400993023063448953845025666763383372150971254078321524118076521462541914412470870836095917351982635822570475022629063039275544222068196147017216270381647770767515316967190073946037040085829611624445
iv = "72abca4ba196bd3562acf269f8578551"
ciphertext = "c22ca2e6545abcec87fed18ba449944219e9556fae52ae7975567823e20cd451"
print(decrypt_flag(share_secret,iv,ciphertext))
```
Flag: `crypto{n07_3ph3m3r4l_3n0u6h}`
## GROUP THEORY
### Additives
```
Alice and Bob decided to do their DHKE in an additive group rather than a multiplicative group. What could go wrong?
Use the script from "Diffie-Hellman Starter 5" to decrypt the flag once you've recovered the shared secret.
Connect at nc socket.cryptohack.org 13380
```
Ở challnge này thay vì dùng DHKE trong nhóm nhân ,ALice và Bob triển khai trong nhóm cộng
Điều đó tương đương
$A = g*a$ mod $p$
$B = g*b$ mod $p$
$s = g*a*b$ mod $p$
Từ đó ta có thể tính được a , a chính là ngịch đảo của A mod p
```python
from Crypto.Util.Padding import unpad
from json import loads, dumps
from Crypto.Cipher import AES
from hashlib import sha1
from pwn import remote
def decrypt_flag(shared_secret, iv, ciphertext):
key = sha1(str(shared_secret).encode()).digest()[:16]
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
plaintext = AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext)
return unpad(plaintext, 16).decode()
io = remote("socket.cryptohack.org", 13380)
io.readuntil(b"from Alice: ")
recv = loads(io.readline())
p = int(recv["p"], 16)
g = int(recv["g"], 16)
A = int(recv["A"], 16)
io.readuntil(b"from Bob: ")
recv = loads(io.readline())
B = int(recv["B"], 16)
io.readuntil(b"from Alice: ")
recv = loads(io.readline())
iv, ciphertext = recv["iv"], recv["encrypted"]
a = A * pow(g, -1, p)
shared_secret = (a * B) % p
print(decrypt_flag(shared_secret, iv, ciphertext))
```
Flag: `crypto{cycl1c_6r0up_und3r_4dd1710n?}`
### Static Client 2
```
Bob got a bit more careful with the way he verifies parameters. He's still insisting on using the p and g values provided by his partner. Wonder if he missed anything?
Connect at nc socket.cryptohack.org 13378
```
Như trong Static client 1, ta có thể sử dụng lại các giá trị của Alice và phát hiện ra rằng Bob đang sử dụng lại khóa 'b' của mình. Thử thách này được giải quyết bằng cách sửa đổi p vì g (dù sao cũng đang được máy chủ xác minh).Thay p bằng một [số smooth](https://en.wikipedia.org/wiki/Smooth_number) với điều kiện:
- smooth_p > p
- smooth_p là số nguyên tố
```python
i = 0
Smooth_p = 1
primes = [2]
while (Smooth_p < p or not is_prime(pSmooth + 1)):
Smooth_p *= primes[i]
primes.append(int(next_prime(primes[-1])))
i += 1
print(Smooth_p)
Smooth_p += 1
return Smooth_p
```
```python
from sympy.ntheory.residue_ntheory import discrete_log
from Crypto.Util.Padding import unpad
from json import loads, dumps
from Crypto.Cipher import AES
from hashlib import sha1
from pwn import remote
def decrypt_flag(shared_secret, iv, ciphertext):
key = sha1(str(shared_secret).encode()).digest()[:16]
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
plaintext = AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext)
return unpad(plaintext, 16).decode()
io = remote("socket.cryptohack.org", 13378)
io.readuntil(b"from Alice: ")
recv = loads(io.readline())
A = int(recv["A"], 16)
g = int(recv["g"], 16)
p = int(recv["p"], 16)
io.readuntil(b"from Alice: ")
recv = loads(io.readline())
iv = recv["iv"]
ciphertext = recv["encrypted"]
smooth_p = 0x72b20ce22e5616f923901a946b02b2ad0417882d9172d88c1940fec763b0cdf02ca5862cfa70e47fb8fd10615bf61187cd564a017355802212a526453e1fb9791014f070d77f8ff4dd54a6d1d58969293734e0b6bc22f3ceea788aa33be35eed4bdc1c8ceb94084399d98e13e69a2b9fa6c5583836a15798ba1a10edd81160a15662cdf587df6b816c570f9b11a466d1b4c328180f614e964f3a5ec61c3f2b759b21687a122f9faefc86fe69a3efd14829639596eb7f2de6eab6b444d06233d34d0651e6fed17db4d0025e58db7cad8824c3e93ed24df588a0a4530be2676e995f870172b9e765ec2886bce140000000000000000000000000000000000000000000000000000000000000000000000000000001
io.sendline(dumps({"g":hex(g),"A": hex(A),"p": hex(smooth_p)}).encode())
io.readuntil(b"Bob says to you: ")
B = int(loads(io.readline())["B"], 16)
b = discrete_log(smooth_p, B, 2)
shared_secret = pow(A, b, p)
print(decrypt_flag(shared_secret, iv, ciphertext))
```
Flag: `crypto{uns4f3_pr1m3_sm4ll_oRd3r}`
## MISC
### Script Kiddie
Challenge cho 2 file
script.py
```python
from Crypto.Cipher import AES
import hashlib
import secrets
def header():
print(""" _____ _ __ __ _
| __ \(_)/ _|/ _(_)
| | | |_| |_| |_ _ ___
| | | | | _| _| |/ _ \
| |__| | | | | | | | __/
|_____/|_|_| |_| |_|\___|
| | | | | | |
| |__| | ___| | |_ __ ___ __ _ _ __
| __ |/ _ \ | | '_ ` _ \ / _` | '_ \
| | | | __/ | | | | | | | (_| | | | |
|_| |_|\___|_|_|_| |_| |_|\__,_|_| |_|
""")
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def pkcs7_unpad(message, block_size=16):
if len(message) == 0:
raise Exception("The input data must contain at least one byte")
if not is_pkcs7_padded(message):
return message
padding_len = message[-1]
return message[:-padding_len]
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
return pkcs7_unpad(plaintext).decode('ascii')
def generate_public_int(g, a, p):
return g ^ a % p
def generate_shared_secret(A, b, p):
return A ^ b % p
def goodbye():
print('Goodbye!')
def main():
header()
print('[-] Collecting data from Alice')
p = int(input('> p: '))
q = (p - 1) // 2
g = int(input('> g: '))
A = int(input('> A: '))
print('[+] All data collected from Alice')
print('[+] Generating public integer for alice')
b = secrets.randbelow(q)
B = generate_public_int(g, b, p)
print(f'[+] Please send the public integer to Alice: {B}')
print('')
input('[+] Press any key to continue')
print('')
print('[+] Generating shared secret')
shared_secret = generate_shared_secret(A, b, p)
query = input('Would you like to decrypt a message? (y/n)\n')
if query == 'y':
iv = input('[-] Please enter iv (hex string)\n')
ciphertext = input('[-] Please enter ciphertext (hex string)\n')
flag = decrypt_flag(shared_secret, iv, ciphertext)
print(f'[+] Flag recovered: {flag}')
goodbye()
else:
goodbye()
if __name__ == '__main__':
main()
```
và output.txt
```typescript
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g: 2
A: 539556019868756019035615487062583764545019803793635712947528463889304486869497162061335997527971977050049337464152478479265992127749780103259420400564906895897077512359628760656227084039215210033374611483959802841868892445902197049235745933150328311259162433075155095844532813412268773066318780724878693701177217733659861396010057464019948199892231790191103752209797118863201066964703008895947360077614198735382678809731252084194135812256359294228383696551949882
B: 652888676809466256406904653886313023288609075262748718135045355786028783611182379919130347165201199876762400523413029908630805888567578414109983228590188758171259420566830374793540891937904402387134765200478072915215871011267065310188328883039327167068295517693269989835771255162641401501080811953709743259493453369152994501213224841052509818015422338794357540968552645357127943400146625902468838113443484208599332251406190345653880206706388377388164982846343351
iv: 'c044059ae57b61821a9090fbdefc63c5'
encrypted_flag: 'f60522a95bde87a9ff00dc2c3d99177019f625f3364188c1058183004506bf96541cf241dad1c0e92535564e537322d7'
```
Đọc source code ta thấy chương trình cho phép người dùng nhập $p,g,A$ sau đó random $b$ sao cho $b < q$ với $q = (p-1)/2$ để tính `shared_secret` theo sau đó là quá trình giải mã. `iv` và `ciphertext` ta đã có vấn đề ở đây là chỉ cần biết được `shared_secret` là sẽ tìm được flag.Phân tích kĩ hơn một chút ta sẽ thấy được điều bất thường :
```python
def generate_public_int(g, a, p):
return g ^ a % p
def generate_shared_secret(A, b, p):
return A ^ b % p
```
Chức năng của 2 hàm này là để trả về $g^a$ mod $p$ và $A^b$ mod $p$ .Biểu thức nên dùng toán tử "**" hoặc hàm **pow()** vì trong python kí tự "^" tương đượng với phép XOR
điều đó có nghĩa là thuật toán bây giờ trở thành:
B = g ^ b mod p
Từ đây ta có thể tính ngược lại b khi biết B và g
b = B ^ g mod p
Sau đó tính được shared_secret
s = A ^ b mod p
```python
from Crypto.Util.Padding import unpad
from json import loads, dumps
from Crypto.Cipher import AES
from hashlib import sha1
from pwn import remote
def decrypt_flag(shared_secret, iv, ciphertext):
key = sha1(str(shared_secret).encode()).digest()[:16]
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
plaintext = AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext)
return unpad(plaintext, 16).decode()
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g = 2
A = 539556019868756019035615487062583764545019803793635712947528463889304486869497162061335997527971977050049337464152478479265992127749780103259420400564906895897077512359628760656227084039215210033374611483959802841868892445902197049235745933150328311259162433075155095844532813412268773066318780724878693701177217733659861396010057464019948199892231790191103752209797118863201066964703008895947360077614198735382678809731252084194135812256359294228383696551949882
B = 652888676809466256406904653886313023288609075262748718135045355786028783611182379919130347165201199876762400523413029908630805888567578414109983228590188758171259420566830374793540891937904402387134765200478072915215871011267065310188328883039327167068295517693269989835771255162641401501080811953709743259493453369152994501213224841052509818015422338794357540968552645357127943400146625902468838113443484208599332251406190345653880206706388377388164982846343351
iv = "c044059ae57b61821a9090fbdefc63c5"
ciphertext = "f60522a95bde87a9ff00dc2c3d99177019f625f3364188c1058183004506bf96541cf241dad1c0e92535564e537322d7"
b = B ^ g
shared_secret = A ^ b
print(decrypt_flag(shared_secret, iv, ciphertext))
```
Flag: `crypto{b3_c4r3ful_w1th_y0ur_n0tati0n}`
### The Matrix
Challenge cho 2 file
the_matrix.sage
```sage!
import random
P = 2
N = 50
E = 31337
FLAG = b'crypto{??????????????????????????}'
def bytes_to_binary(s):
bin_str = ''.join(format(b, '08b') for b in s)
bits = [int(c) for c in bin_str]
return bits
def generate_mat():
while True:
msg = bytes_to_binary(FLAG)
msg += [random.randint(0, 1) for _ in range(N*N - len(msg))]
rows = [msg[i::N] for i in range(N)]
mat = Matrix(GF(2), rows)
if mat.determinant() != 0 and mat.multiplicative_order() > 10^12:
return mat
def load_matrix(fname):
data = open(fname, 'r').read().strip()
rows = [list(map(int, row)) for row in data.splitlines()]
return Matrix(GF(P), rows)
def save_matrix(M, fname):
open(fname, 'w').write('\n'.join(''.join(str(x) for x in row) for row in M))
mat = generate_mat()
ciphertext = mat^E
save_matrix(ciphertext, 'flag.enc')
```
và flag.enc
```
00000001111101100001101010010001001011000110001001
10111010010100110001011011111110011000001001000001
01011101000110110101010100100100111110110110011111
11101100011011010001111011011000100010110001001010
11111111101001010101001011111101010010011010101001
10010011101000000010000110100101111011110011101110
00011100010011010110000000001011000111010101001011
01001111000110100111110011000101011110010111111110
01111001110011000100000110010101011111010000000011
11001101010111111011110110101010001101001001111101
01100111000100010101000001011011001101001110101000
00010001001011101111100010101101011000101100010111
01101100101101011101101000110001011111111010000100
00001110111111000111111100011110000101100100000011
10001001111111011000111011111010110111111111000110
01111101100011110110111000011110000100111001110100
11111100110101111001111000110100011010111011110001
00100011011100101010111011111100000010000101111111
01111001110100011111011100100011011010010011111000
01011011101011111111101011011011000111110011111010
00010100110111110011111100111101100000001101110111
10011011011101110101100110110000011101000010101011
01111000001111011011111000100010010010010111101001
00100000010001110000001101111100011111110011011000
10010101101011011111101111101000111010010011111001
10011011000111000001010111011000000000100111100011
11001001010001111111000011011011101001101010001000
00100100000101110010001001011001111011001110100001
00000101000101100111010111101010001101111110011001
00101000011010100110100111111110000101011001011110
11011001001111111010000001100111011101101100110110
00111000011011011111111011110001001101001101101100
11110010101001100110000110110000100000101010101011
00101001000011001110110111100010010011100101001000
11000100010010111110110010100110110110101000110110
01101011000111001111011110000110001011111000011100
11010011001111111110100101100011000000000011110001
10000011000101100011000110111111011010110111101000
11000011000100010001001011010011010000001101100011
11011001111001010100010101001100001010101100010010
10110101010111111010110001111111100100110001001100
11101001100110001001001100000011100101001010011010
10000011100110001101010110010010100001010011011101
10001110111111100110011000010000011011011111011001
00011100011111110101011100111000110010100011000010
00111111010010111100100101100001001011110101111100
10000100101101000011011010100100011111100101101111
00011101110001001010111001111011111110110011011001
11111100110101111100110001011001000001111100110011
00110010110110011001001111110110000011001111010110
```
Đọc source code ta thấy
- hàm bytes_to_binary để chuyển đổi chuỗi bytes sang chuỗi nhị phân
- hàm generate_mat để tạo ma trận
- hàm load_matrix để đọc ma trận từ một file đã cho
- hàm save_matrix để ghi ma trận vào một file
mat.multiplicative_order() là phương thức được sử dụng trong thư viện SageMath để tính toán bậc đơn vị của ma trận trên trường hữu hạn GF(2). Bậc đơn vị của ma trận là số nguyên dương nhỏ nhất m sao cho ma trận mũ m (tức là m lần lấy tích của ma trận với chính nó) trở thành ma trận đơn vị. Nếu ma trận không có bậc đơn vị, phương thức này sẽ trả về giá trị None.
Sử dụng hàm generate_mat để tạo ma trận và mã hóa nó bằng cách sử dụng phép mũ modulo ^ và số mũ E, lưu kết quả vào file flag.enc(là một ma trận 50 hàng 50 cột).
Chúng ta có thể giải mã ma trận bằng cách tính lũy thừa nghịch đảo của E, sau đó lấy các bit của ma trận đầu tiên (34 * 8 / 50 + 1) và giải mã chúng.Việc lấy số lượng bit cụ thể là (34* 8/50) + 1 được tính toán dựa trên số lượng cột của ma trận đầu tiên. Vì ma trận có kích thước là 50 x 50 và mỗi cột của nó biểu diễn 50 bit của thông điệp, nên số lượng cột cần lấy sẽ là 34* 8/50, với (34*8) là số lượng bit của chuỗi hex mã hóa của thông điệp và 50 là số lượng bit được biểu diễn trong mỗi cột của ma trận.
Thêm một cột nữa được lấy ra bởi vì chuỗi hex mã hóa của thông điệp(FLAG) có độ dài là 34 byte (mỗi byte bao gồm 8 bit), và 34 * 8 bit này không thể được chia đều thành các cột 50-bit. Vì vậy, một cột nữa được lấy ra để đảm bảo rằng đủ bit để giải mã thông điệp được trích xuất từ ma trận đầu tiên.
Sage code:
```sage!
M = Matrix(GF(2), [list(map(int, row)) for row in open("flag.enc").read().splitlines()])
M ^= pow(31337, -1, M.multiplicative_order())
bin_flag = ''.join([str(bit) for col in M.columns()[:(34*8//50)+1] for bit in col])
print(bytes.fromhex(hex(int(bin_flag[:34*8],2))[2:]).decode())
```
Python code:
```python
from Crypto.Util.number import long_to_bytes
P = 2
N = 50
E = 31337
FLAG = b'crypto{??????????????????????????}'
def bin_to_bytes(s):
all_bytes = [s[i:i+8] for i in range(0, len(s), 8)]
return b''.join(long_to_bytes(int(byte, 2)) for byte in all_bytes)
def find_GL_order():
order = 1
k = 0
for k in range(N):
order *= (P**N - P**k)
assert order == GL(N, GF(P)).order()
return order
C = load_matrix('flag.enc')
GLorder = find_GL_order()
D = pow(E, -1, GLorder)
M = C^D
cols = M.columns()[:(len(FLAG)*8//50)+1]
bin_flag = ''.join([str(bit) for col in cols for bit in col])
print(bin_to_bytes(bin_flag))
```
Flag: `crypto{there_is_no_spoon_66eff188}`
Sign in with Wallet
Connect another wallet