# BACKGROUND
## Background Reading
- Flag là tên của tính chất giao hoán.
- Flag: `crypto{abelian}`
# STARTER
## Point Negation
- Chall cho ta: $E: Y^2 = X^3 + 497 X + 1768, p: 9739.$
- Yêu cầu tính tọa độ $Q(x, y)$ với $P + Q = 0$ và $P(8045, 6936).$
- $Q = -P.$

sage: E = EllipticCurve(GF(9739),[497,1768])
sage: P = E(8045,6936)
sage: -P
(8045 : 2803 : 1)

- Flag: `crypto{8045,2803}`
## Point Addition
- Chall cho ta cách tính $P+Q$.
>Algorithm for the addition of two points: P + Q
(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).
- Yêu cầu ta tính $S= P+P+Q+R$, với $E: Y2 = X3 + 497 X + 1768, p: 9739$, $P = (493, 5564), Q = (1539, 4742), R = (4403,5202)$.

sage: E = EllipticCurve(GF(9739),[497,1768])
sage: P = E(493, 5564)
sage: Q = E(1539, 4742)
sage: R = E(4403,5202)
sage: P+ P+ Q+ R
(4215 : 2162 : 1)

- Flag: `crypto{4215,2162}`

## Scalar Multiplication
- Chall yêu cầu ta tính $Q(x,y)= 7863 P$, với $E: Y2 = X3 + 497 X + 1768, p: 9739$; $P= (2339, 2213)$.
- Với thông tin được cung cấp từ chall là:
>Double and Add algorithm for the scalar multiplication of point P by n.
>Input: P in E(Fp) and an integer n > 0
>1. Set Q = P and R = O.
>2. Loop while n > 0.
>3. If n ≡ 1 mod 2, set R = R + Q.
>4. Set Q = 2 Q and n = ⌊n/2⌋.
>5. If n > 0, continue with loop at Step 2.
>6. Return the point R, which equals nP.

sage: E = EllipticCurve(GF(9739),[497,1768])
sage: P = E(2339, 2213)
sage: 7863*P
(9467 : 2742 : 1)

- Flag: `crypto{9467,2742}`

## Curves and Logs
- Chall yêu cầu ta tính x của $S(x, y)$ sau khi băm SHA1 với: $Q_A = n_AG$; $Q_B = n_BG$; shared secret : $S = n_A*Q_B = n_B * Q_A$.

sage: E = EllipticCurve(GF(9739),[497,1768])
sage: QA = E(815,3190)
sage: nB = 1829
sage: S = QA*nB
sage: S
(7929 : 707 : 1)

- SHA1 x= 7929 ta thu được flag.
- Flag: `crypto{80e5212754a824d3a4aed185ace4f9cac0f908bf}`

## Efficient Exchange
- Chall cho ta $q_x = 4726$ và $n_B = 6534$ và file [decrypt.py](https://cryptohack.org/static/challenges/decrypt_08c0fede9185868aba4a6ae21aca0148.py) để decrypt ra flag.
- Thay x vào $Y^2 = X^3 + 497 X + 1768$ để tìm $Y^2$
- Với $Y^2$ ta tính $Y$ dựa vào $p \equiv 3\ mod(4)$ và Symbol Legend.

- Flag: `crypto{3ff1c1ent_k3y_3xch4ng3}`.

# PARAMETER CHOICE
## Smooth Criminal
- Sử dụng hàm `discrete_log` để lấy giá trị n khi biết được $G$ và $Q_A$ do p nhỏ.

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):
    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)
    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16)
    else:
        return plaintext
p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p),[a,b])
Q_A = E(280810182131414898730378982766101210916, 291506490768054478159835604632710368904)
Q_B = E(272640099140026426377756188075937988094, 51062462309521034358726608268084433317)
G = E(179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
n = G.discrete_log(Q_A)
print(n)
print("SECRET:", n*Q_B)
x = 171172176587165701252669133307091694084
data = {'iv': '07e2628b590095a5e332d397b8a59aa7', 'encrypted_flag': '8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af'}
iv = data["iv"]
encrypted_flag = data['encrypted_flag']
print(decrypt_flag(x, iv,encrypted_flag))

## Exceptional Curves

- Với E.order đã là số nguyên tố và chall thuộc dạng tấn công [Smart Attack](https://wstein.org/edu/2010/414/projects/novotney.pdf)

from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os

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')
def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break
    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp
    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()
    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)
p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece
E = EllipticCurve(GF(p), [a, b])
G = E(3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005,4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850)
b_x = 0x7f0489e4efe6905f039476db54f9b6eac654c780342169155344abc5ac90167adc6b8dabacec643cbe420abffe9760cbc3e8a2b508d24779461c19b20e242a38
b_y = 0xdd04134e747354e5b9618d8cb3f60e03a74a709d4956641b234daa8a65d43df34e18d00a59c070801178d198e8905ef670118c15b0906d3a00a662d3a2736bf
B = E(b_x, b_y)
A = E(4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865, 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757)
n_A = SmartAttack(G, A, p)
x = (ZZ(n_A)*B)[0]
data = {'iv': '719700b2470525781cc844db1febd994', 'encrypted_flag': '335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0'}
iv = data["iv"]
encrypted_flag = data['encrypted_flag']
print(decrypt_flag(x, iv,encrypted_flag))

## Micro Transmissions
- Same as chall `Smooth Criminal`

from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os

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')

p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
E = EllipticCurve(GF(p), [1,4]) 
G = E(43190960452218023575787899214023014938926631792651638044680168600989609069200, 20971936269255296908588589778128791635639992476076894152303569022736123671173)
A = E.lift_x(87360200456784002948566700858113190957688355783112995047798140117594305287669)
B = E.lift_x(6082896373499126624029343293750138460137531774473450341235217699497602895121)
order = G.order()
print(factor(order))

max_value_n = 18446744073709551615

results = []
factors = []
mul = 1
for prime, exponent in factor(order):
    e = (order//(prime**exponent))
    G_new = G*e
    A_new = A*e
    dlog = G_new.discrete_log(A_new)
    print(prime, dlog)
    results.append(dlog)
    factors.append(prime**exponent)
    mul *= prime
    if mul > max_value_n:
        break

n_A = crt(results,factors)
print("Found:",n_A)

x = (ZZ(n_A)*B)[0]
data = {'iv': 'ceb34a8c174d77136455971f08641cc5', 'encrypted_flag': 'b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453'}
iv = data["iv"]
encrypted_flag = data['encrypted_flag']
print(decrypt_flag(x, iv,encrypted_flag))

## Elliptic Nodes

from Crypto.Util.number import long_to_bytes
from collections import namedtuple
from sage.all import *

Point = namedtuple("Point", "x y")
p = 4368590184733545720227961182704359358435747188309319510520316493183539079703
Gx = 8742397231329873984594235438374590234800923467289367269837473862487362482
Gy = 225987949353410341392975247044711665782695329311463646299187580326445253608
Qx = 2582928974243465355371953056699793745022552378548418288211138499777818633265
Qy = 2421683573446497972507172385881793260176370025964652384676141384239699096612
res1 = (Gy ** 2 - Gx ** 3) % p 
res2 = (Qy ** 2 - Qx ** 3) % p 
a = ((res1 - res2) * pow((Gx - Qx), -1, p)) % p 
b = (res1 - a * Gx) % p 
print(f"{a = }")
print(f"{b = }")
R = PolynomialRing(GF(p), 'x')
x = R.gen()
f = x^3 + a * x + b
shift = f.roots()
print(shift)
shift = 1557923326969252180825193218688702224840389936248863823173183835359957757721 
f2 = f.subs(x=x+shift)
print('Shifted curve:', f2.factor())
t = GF(p)(305179796174210822247618473361747316085422620437271958999235012896334193460).square_root()
print(t)
_Qx, _Qy = (Qx - shift, Qy)
_Gx, _Gy = (Gx - shift, Gy)
v = (_Qy + t*_Qx)/(_Qy - t*_Qx) % p
u = (_Gy + t*_Gx)/(_Gy - t*_Gx) % p
print(f"{v = }, {u = }")
d = discrete_log(v, u)
long_to_bytes(d)

# SIGNATURES
## Digestive

import requests
url = "https://web.cryptohack.org/digestive/"
def sign(username):
    return requests.get(url + "/sign/" + username).json()
def verify(msg, signature):
    return requests.get(url + "/verify/" + msg + "/" + signature).text
username = "a" * 1000
payload = '{"admin": false, "username": "' + username + '", "admin":true}'

out = sign(username)
flag = verify(payload, out["signature"])
print(flag)

## Curveball