# MISC
## GUESSMYTOKEN
### Description


As you see, the challenge gives us 8 bytes at random, and our work is to guess them. If we send the correct one, we can get the flag. However, we only have 10 seconds to guess once.
- ↑: need to increase(bytes at this index is smaller than target).
- ↓: need to decrease(bytes at this index is higher than target).
- X: need to remain (bytes at this index is correct).
### Script:

Write the binary search algorithm to solve the challenge.

from pwn import *

#context.log_level ='debug'

def binary_change(payload, res, old_payload):
    ans = ""
    for i in range(16):
        if (res[i] == "↓"):
            #payload[i] = payload[i]  - |payload[i] - old_payload[i]| / 2
            ans += str( hex( int( int(payload[i], 16) - abs((int(payload[i], 16) - int(old_payload[i], 16)) / 2) ) ) [2:] )   
        elif (res[i] == "↑"):
            #payload[i] = payload[i]  + |payload[i] - old_payload[i]| / 2
            ans += str( hex( int( int(payload[i], 16) + abs((int(payload[i], 16) - int(old_payload[i], 16)) / 2) ) ) [2:] )
        else:
            ans += payload[i]
    return ans
        
r = remote('guess-my-token.rumble.host', 6903)

payload = "8888888888888888"     
for i in range(5):
    r.recvuntil(b'Your guess: ')
        
    r.sendline(payload.encode())
    try:
        r.recvuntil(b'My control: ')
    except EOFError:
        r.close()
        break
    res_guest = r.recvline().rstrip().decode()
        
    if i == 0:
        log.info("0000000000000000" + ".....Old payload")
        log.info(payload + ".....Payload")
        log.info(res_guest)
        old_payload1 = payload
        payload = binary_change(payload, res_guest, "0000000000000000")
            
            
    else:
        log.info(old_payload1 + ".....Old payload")
        log.info(payload + ".....Payload")
        log.info(res_guest)
        old_payload2 = payload
        payload = binary_change(payload, res_guest, old_payload1)
        old_payload1 = old_payload2
        
r.interactive()


# Crypto
## Bigger is better
### Source code

import os
import gmpy2
import Crypto.Util.number as number
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

def gen_params():
    e = gmpy2.mpz(number.getPrime(520))
    while True:
        while True:
            p = gmpy2.mpz(number.getPrime(512))
            q = (p * gmpy2.invert(p - 1, e)) % e
            if q.is_prime():
                break

        n = p * q
        phi = (p-1)*(q-1)

        if gmpy2.gcd(e, phi) == 1 and e < phi:
            d = (1 + (e - 1) * phi) // e
            return (int(n), int(e), int(d))
        
flag = os.environ["FLAG"]
key = RSA.construct(gen_params())

cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(flag.encode())

print("Flag:", ciphertext.hex())
print("n:", key.n)
print("e:", key.e)

In RSA p and q must be generate at random, but in this situation as we can see there is a relationship between p, q and e.

So what it really means?

Take a look at this code

` q = (p * gmpy2.invert(p - 1, e)) % e `
it means

<=> q = p * (p-1)^-1 mod e
<=> q*(p-1) = p mod e
<=> q*p = p+q mod e
So N (which is q*p) will equals to (p+q)%e or we can say N%e = p+q.

After having the sum of p and q we can calculate p and q by solving equation.

Ok but what equations.

So the things is when we have sum and product of p,q we will have this equation.


But I can't do this equation ( I called it (*)) so I tried to create another one by hand. Here it is

We have:
<=> p + q = n mod e
<=> p + q = (p * q) mod e
<=> n/q + q = (p * q)mod e
<=> n + q^2 = (p*q)*q mod e
<=> q^2 - (p*q)*q + n = 0 (1)

Equation (1) have the format a*x^2 +b*x + c = 0
a = 1, b = -(p*q), c = p*q

We have delta = b^2 - 4*a*c
=> x1 = [-b+sqrt(delta)]/2
<=> x1(aka q) = [(p*q)+sqrt(b^2 - 4*a*c)]/2
=> x2 = n/2

Done! But there is one more thing I still don't know if there is any relation between (1) and (*). Nevermind, here is the script:

import gmpy2
from Crypto.Util.number import inverse, long_to_bytes
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
Flag = "01b61a99ec3144e1eb15dd819185c340c7b17b38d069f5189807681d3c7a26afe1088f6b270c9cf26915d857e83de910971054fb92926adb0226325317510ddc5129a21beb6241001e638f6981cbcb3cd5a0be8168ae21d149d83fd3e9b5f9115e28ab2320a201a522d25f4e14552434835af1bb22d3f710341ed22722011c0372"
n = 597335689226045056913166505037840157078954264999700629833258496762227084400401604912493527516646939874075386574739856551056864389324619848840266776702144772354597990152158599522528018659755118263808518976172810917606196554528503935276695298154816588160752930883134894518555210481664717173645960866565960880557
e = 2634065751614482329107725637023560471652100411843894146340117230337954286149474325215157995353348215193206597222786188634557304190252766656287157923889937903
p_plus_q = n % e
pq = n
ct = bytes.fromhex(Flag)
p = int((p_plus_q + gmpy2.isqrt(p_plus_q * p_plus_q - 4 * pq)) // 2)
q = int(pq // p)
phi = (p - 1) * (q - 1) #chinese remainder theorem
d = inverse(e,phi) # e^-1 mod phi
private_key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(private_key)
flag = cipher.decrypt(ct)
print(flag.decode())

Here is the flag