> For the complete documentation index, see [llms.txt](https://thr34dr1pp3r.gitbook.io/ctf/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://thr34dr1pp3r.gitbook.io/ctf/corctf-2024/crypto-steps.md).

# Crypto - Steps

## [Full Implementation](https://github.com/kinasant/THR34DR1PP3R/blob/main/2024/corCTF/Steps/sol.ipynb)

## Challenge

```python
from Crypto.Util.number import getPrime
from random import randint
from hashlib import sha512
from secret import FLAG

p = getPrime(1024)
Pair = tuple[int, int]

def apply(x: Pair, y: Pair) -> Pair:
    z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
    z1 = x[0] * y[0] + x[1] * y[1]
    return z0 % p, z1 % p

def calculate(n: int) -> Pair:
    out = 0, 1
    base = 1, 1
    while n > 0:
        if n & 1 == 1: out = apply(out, base)
        n >>= 1
        base = apply(base, base)
    return out

def step(x: Pair, n: int):
    '''Performs n steps to x.'''
    return apply(x, calculate(n))
def main() -> None:
    g = tuple(randint(0, p - 1) for _ in range(2))
    a = randint(0, p)
    b = randint(0, p)

    A = step(g, a)
    B = step(g, b)

    print(p)
    print(g)
    print(A)
    print(B)
    
    shared = step(A, b)
    assert shared == step(B, a)
    pad = sha512(str(shared).encode()).digest()
    print(xor(FLAG, pad))

```

We are given `p,g,A,B` and we need to find the shared secret by `step(A,b)` or `step(B,a)`

`step(A,b)` is the same as `apply(A,calculate(b))`. If we could somehow reverse the output of apply to get the input then we could use it on `step(g,a)` and find the value of `calculate(a)`

In `apply`, given the output values `z0,z1` and the first input values `x0,x1`, we need to find the values of the second input values `y0,y1` .

For this, we employ the use of Groebner basis

```python
R.<x0,x1,y0,y1,z0,z1> =  PolynomialRing(ZZ)
I  = Ideal([x0*y1+x1*y0-x0*y0-z0,x0*y0+x1*y1-z1])
I.groebner_basis()
x0^2*y1 + x0*x1*y1 - x1^2*y1 - x0*z0 - x0*z1 + x1*z1, x0*y0 + x1*y1 - z1, x1*y0 + x0*y1 + x1*y1 - z0 - z1
```

$$
x\_0^2  \* y\_1 + x\_0*x\_1*y\_1 - x\_1^2 *y\_1 - x\_0*z\_0 - x\_0*z\_1 + x\_1 \* z\_1 = 0 \\
y\_1*(x\_0^2  + x\_0*x\_1 - x\_1^2) = x\_0*z\_0  + x\_0*z\_1-x\_1*z\_1 \\
y\_1 =(x\_0^2  + x\_0*x\_1 - x\_1^2) ^{-1} \* ( x\_0*z\_0  + x\_0*z\_1-x\_1*z\_1 ) \pmod p
$$

$$
x\_0*y\_0 + x\_1*y\_1 - z\_1 = 0 \\
y\_0 = (z\_1-x\_1*y\_1)* x\_0^{-1} \pmod p
$$

```python
def ua1(x,z):
    z0,z1 = z
    x0,x1= x
    y1=((x0*z0 + x0*z1-x1*z1)%p)*(pow((x0^2+x0*x1-x1^2),-1,p)) %p
    y0 = ((z1-x1*y1)%p * pow(x0,-1,p)) %p
    return y0,y1
```

Now we have everything that we need, we can now decrypt.

```python
p=140323158913416495607520736187548995477774864895449373468435168606940894555091715325755245563618777520381345121826124291879072024129139794758353829170487152290036863771427918014687523291663877491666410660298255515196964873944928956895167652588843616727666115196647426152811435167407394960435891152283442366721
g=(96065253104055475368515351480749372850658086665031683689391433619786525841252022013348418216780129963411710917302022475212035579772549622047772413277044476931991100469638284113901919733675144788049607999711496364391389612383885735460390196619821411998848060208912802838145365054170790882835846039461477718592, 99241616571709523646659145402511086659276737895777010655080069795289409091105858433710404513588065826008320709508748555232998727290258965620812790826701703542423766306117851146140634247906095481346444357123297761881438234083584836393572339820023598801127329326758926529813665950889866710376403818615042210724)
A=(70755695722452190644681854912493449110123792967984325777144153291795297730471865203878351550134745747839905472832417565386100721034554991782211134122667955909129461935072670637104557733518048519759925441567454988894610693095988261459294358350906447578625319131211019007537053689563772428590632011546870587548, 67209626648557152207459211543890871397518255584981755641031188457446084495247511864090204533159666638951190009379067537952490757956859052998865712873197974689323985952177932343928382624951392835548222455898153557185369330197085287972647654361464363270469055087587755117442462138962625643131163131541853061105)
B=(112356264561144892053527289833892910675229600209578481387952173298070535545532140474473984252645999236867287593260325203405225799985387664655169620807429202440801811880698414710903311724048492305357174522756960623684589130082192061927190750200168319419891243856185874901350055033712921163239281745750477183871, 53362886892304808290625786352337191943295467155122569556336867663859530697649464591551819415844644455424276970213068575695727349121464360678240605137740996864232092508175716627306324344248722088013523622985501843963007084915323781694266339448976475002289825133821073110606693351553820493128680615728977879615)
a1=b'\xbaH\xca[V\xdf\xbb0d2jN"\x9d$e\xec\xe0M\x00\xdb\xf0\x8f\x99f\xc5\n\x8a\xc2h\xa7\xa7'
calculated_a = ua1(g,A)
shared=apply(B,calculated_a)
pad = sha512(str(shared).encode()).digest()
xor(pad,a1)
b"corctf{w4it_i7's_4ll_f1b0n4cci?}\x18\x04\xa1\xbfX>\xc2\xd8+\xc4.R\x04\\(\x17\x1e\xbf\xdeUv\xcb\x1c<\xa41\x18\x86\xdb\xa9<\xbc"
```