---
# System prepended metadata

title: cryptoHack

---

## 1.	“Symmectric Ciphers”
**Keyed Permutations**
`crypto{bijection}`
**Resisting Bruteforce**
`crypto{biclique}`
**Structure of AES**
Để giải quyết bài toán ta chỉ cần chuyển lần lượt từng phần tử của matrix từ số về dạng kí tự ascii của chúng.
```
def bytes2matrix(text):
    """ Converts a 16-byte array into a 4x4 matrix.  """
    return [list(text[i:i+4]) for i in range(0, len(text), 4)]

def matrix2bytes(matrix):
    """ Converts a 4x4 matrix into a 16-byte array.  """
    text = ''
    for i in range(len(matrix)):
        for j in range(4):
            text += chr(matrix[i][j])
    return text

matrix = [
    [99, 114, 121, 112],
    [116, 111, 123, 105],
    [110, 109, 97, 116],
    [114, 105, 120, 125],
]

print(matrix2bytes(matrix))
```

## 	2. “RSA”
**RSA Starter 1**
Find `pow(101,17,22663)` python
(19906)
**RSA Starter 2**
`C = m^e mod n`

Script
```
e = 65537 
p = 17 
q = 23
n = p*q 
m = 12 #message

print(pow(m,e,n))
```
(301)
**RSA Starter 3**
`(p-1)*(q-1)`
```
p = 857504083339712752489993810777 
q = 1029224947942998075080348647219 
print((p-1)*(q-1))
```
(882564595536224140639625987657529300394956519977044270821168)
## 	3. “Diffe-Helman”
**Diffie-Hellman Starter 1**
```
p = 991  # Prime modulus
g = 209  # Element in the finite field Fp
d = pow(g, -1, p)

print(d)
```
(569)
**Diffie-Hellman Starter 2**
Script
```

p = 28151

def is_primitive_element(g):
    # Set of powers generated by g
    powers = set()

    # Calculate powers of g modulo p
    for i in range(1, p):
        power = pow(g, i, p)
        if power in powers:
            # If a power is repeated, g is not a primitive element
            return False
        powers.add(power)

    # If all elements in Fp are generated by g, it is a primitive element
    return len(powers) == p - 1

# Iterate over elements of Fp
for g in range(1, p):
    if is_primitive_element(g):
        # Found the smallest primitive element
        smallest_primitive_element = g
        break

# Print the smallest primitive element (the flag)
print("Smallest primitive element of Fp:", smallest_primitive_element)
```
(7)
**Diffie-Hellman Starter 3**
```
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
a = 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815


# Calculate g^a mod p to obtain the shared secret
shared_secret = pow(g, a, p)

# Print the shared secret
print(shared_secret)
```
## 	4. “Elliptic Curves”
**Point Addition**
Làm từng bước theo phương pháp đã được nêu ra trong challenge, nhưng thay vì phép chia ta sẽ dùng modular inverse
![](https://hackmd.io/_uploads/BJ1HIon02.png)
```
from Crypto.Util.number import*

a = 497
b = 1768
p = 9739

'''
(a) If P = O, then P + Q = Q.
(b) Otherwise, if Q = O, then P + Q = P.
(c) Otherwise, write P = (x1, y1) and Q = (x2, y2).
(d) If x1 = x2 and y1 = - y2, then P + Q = O.
(e) Otherwise:
  (e1) if P ≠ Q: λ = (y2 - y1) / (x2 - x1)
  (e2) if P = Q: λ = (3x12 + a) / 2y1
(f) x3 = λ2- x1 - x2,     y3 = λ(x1 - x3) - y1
(g) P + Q = (x3, y3)
'''

def add_point(p1, p2):
    if p1 == (0, 0):
        return p2
    if p2 == (0,0):
        return p1
    
    x1, y1 = p1
    x2, y2 = p2

    if x1 == x2 and y1 == -y2:
        return (0, 0)

    lamda = 0
    if p1 == p2:
        lamda = ((3*pow(x1,2,p)+a) * inverse(2*y1, p))
    else:
        lamda = ((y2-y1) * inverse(x2-x1, p))
        
    x3 = (pow(lamda, 2) - x1 - x2) % p
    y3 = (lamda*(x1 - x3) - y1) % p 
    return (x3, y3)

P = (493, 5564)
Q = (1539, 4742)
R = (4403,5202)
#S(x,y) = P + P + Q + R

s = add_point(P,add_point(P, add_point(Q, R)))
print(s)
```

## 	5. “Hash Function”
**Jack's Birthday Hash**
Giá trị hash là chuỗi nhị phân 11 bits nên có tất cả n = 2^11 = 2048 giá trị hash.
p(n) là xác suất để nhóm n secret có ít nhất 1 cái gặp collision với secret của Jack.
Khi đó p(k) là xác suất để không có secret nào trong n cái gặp collision với secret của Jack, *p(k)=(n−1/n)^k.*
Suy ra *p(k)=1−((n−1)/n)^k>0.5*

Script
```
n = 1 << 11
P = 1
for i in range(1, n):
    P = pow((1 - 1/n), i)
    nP = 1 - P
    if nP > 0.5:
        print(i)
        break

```
(1420)
**Jack’s Birthday Confusion**
Tương tự bài trên, n = 2^11.
Gọi p là xác xuất để tồn tại 2 secret có chung giá trị hash trong k secret cho trước, suy ra !p(k)
là xác suất để k secret có giá trị hash đôi một phân biệt, khi đó ![](https://hackmd.io/_uploads/SJOF082C2.png)
Script:
```
from math import factorial
n = 2048
for i in range(n):
	probability = 1 - factorial(n) / (factorial(n - i)*pow(n,i))
	if probability > 0.75:
		print(i)
		break
```
(76)