# Cryptography

| Challenge           | Link                       |
| ------------------- | -------------------------- |
| Casino (101 solves) | [Here](#casino-101-solves) |
| Spring (48 solves)  | [Here](#spring-48-solves)  |
| Order (46 solves)   | [Here](#order-46-solves)   |

## Casino (101 solves)

### Description

Care to test your luck?

`nc casino.hsctf.com 1337`

### Solution

So we need money >= 1000000000 to get the flag. Since we can control nonce and hex we can manipulate the plaintext during the decryption process.

<figure><img src="https://329253018-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIYUhWFsdATjBxpgp6f6z%2Fuploads%2FyBGSTqsGp9QiXvSz8iWk%2Fimage.png?alt=media&#x26;token=274e0127-837a-4fac-a61d-fdfc938bfbb7" alt=""><figcaption></figcaption></figure>

To modify the money (plaintext) which is 0.0, we can use scientific notation to get big number with only 3 bytes values. To modify the money (plaintext) which is 0.0, we can use scientific notation to get big number with only 3 bytes value. Here is the detail of process

```python
pt_nonce = Decrypt(nonce) 
tmp1 = pt_nonce[12]^ct_value[12] # pt_nonce[12] ^ ct_value[12] = ord('0')
tmp2 = pt_nonce[11]^ct_value[11] # pt_nonce[11] ^ ct_value[11] = ord('.')
tmp3 = pt_nonce[10]^ct_value[10] # pt_nonce[10] ^ ct_value[10] = ord('0')

# convert the value to our target by converting to null byte and then target
tmp1 ^ ord('0') ^ ord('9') = ord('9') # ord('0') ^ ord('0') = 0 -> 0 ^ ord('9') = ord('9')
tmp2 ^ ord('.') ^ ord('e') = ord('e') # ord('.') ^ ord('.') = 0 -> 0 ^ ord('e') = ord('e')
tmp3 ^ ord('0') ^ ord('1') = ord('1') # ord('0') ^ ord('0') = 0 -> 0 ^ ord('1') = ord('1')
```

```python
from pwn import *

def flag():
	r.recvuntil(b"> ")
	r.sendline(b"1")

def play():
	r.recvuntil(b"> ")
	r.sendline(b"2")
	r.recvuntil(b"> ")
	r.sendline(b"1")

def save():
	r.recvuntil(b"> ")
	r.sendline(b"4")
	r.recvuntil(b": ")
	saved = r.recvline().strip().decode().split(".")
	r.close()
	return saved

def load(nonce, ct):
	data = nonce.hex() + "." + ct.hex()
	r.recvuntil(b"> ")
	r.sendline(b"3")
	r.recvuntil(b"> ")
	r.sendline(data.encode())
	return r.recvline()

def attack(ct):
	ct = list(ct)
	ct[12] ^= ord('0')
	ct[12] ^= ord('9')
	ct[11] ^= ord('.')
	ct[11] ^= ord('e')
	ct[10] ^= ord('0')
	ct[10] ^= ord('1')
	return bytes(ct)

r = remote("casino.hsctf.com", 1337)
data = save()
nonce = bytes.fromhex(data[0])
ct = bytes.fromhex(data[1])

ct = attack(ct)

r = remote("casino.hsctf.com", 1337)
resp = load(nonce, ct)
flag()
r.interactive()
```

<figure><img src="https://329253018-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIYUhWFsdATjBxpgp6f6z%2Fuploads%2Fra3X2x8zlYDaXSnu3F7b%2Fimage.png?alt=media&#x26;token=f53e0b94-9882-4e5d-9267-0c7e2db036a2" alt=""><figcaption></figcaption></figure>

Flag : flag{you're\_ready\_for\_vegas\_now}

## Spring (48 solves)

### Description

One day in April, I found these strange numbers, along with a program.

### Solution

The program encrypt the image using random number generated by Java.util.Random.nextLong . nextLong is pseudorandom generator and for cracking it i used script provided by <https://github.com/Cr4ckC4t/crack-java-prng/blob/main/crack-nextLong.py> . Here is the full implementation for my solver

```python
#!/usr/bin/env python3

# Implement and crack java's util.Random.nextLong()
# Reference: https://developer.classpath.org/doc/java/util/Random-source.html

import sys
from Crypto.Util.number import *
# Colors
class fc:
        cyan = '\033[96m'
        green = '\033[92m'
        orange = '\033[93m'
        red = '\033[91m'
        end = '\033[0m'
        bold = '\033[1m'


# Return the signed representation of a value
# For example:
#	unsigned  1001 =  9
#       signed    1001 = -7
#
#  getSigned(9,4) == 7
#
def getSigned(n,bits):
	if n >= 2**(bits-1):
		return -((n^(2**bits-1))+1)
	else:
		return n

# Returns the value that you need to pass to java.util.Random.setSeed()
# in order to set the seed to `seed`.
def reverseSeed(seed):
        return (seed ^ 0x5DEECE66D)

# This function is unused in this code.
# It implements the java.util.Random.setSeed() function
def setSeed(seed):
	return (seed ^ 0x5DEECE66D) & (2**48-1)

# Implementation of java.util.Random.next(32)
def next32(seed):
	newseed = (seed * 0x5DEECE66D + 0xB) & (2**48-1)
	return newseed, getSigned((newseed >> 16), 32)

# Implementation of java.util.Random.nextLong()
def nextLong(seed):
	seed, a = next32(seed)
	seed, b = next32(seed)
	return  seed, getSigned(((a<<32)+b), 64)

# Contrary to getSigned(), expects 64 bit as input
# Returns the correct bit representation of the value but as positive integer
def signedLongToInt(long):
        x = ''
        if long < 0:
                x = bin((abs(long)^(2**64-1))+1)[2:]
        else:
                x = bin(long)[2:]
        return int(x,2)

# Since one long token consists of two generate 32 bit tokens
# and since the first token consists of the first 32 bit of the
# seed for the second token - we can brute force the remaining 16
# bits to find the seed that was used to create the second token.
# Once we have the seed, we can create every following number.
def crackSeed(long):
	longbin = bin(signedLongToInt(long))[2:]  # get the correct binary representation of a long
	longbin = '0'*(64-len(longbin))+longbin   # pad seed to 64 bit

	lower = longbin[32:]  # take lower 32 bit

	# Usually brute forcing the 16 LSBs of the 48 bit seed should be good enough
	# But in some special cases, we might need to brute force a few more bits

	for bits in range(16,20): # amount of bits to brute force
		print(f'{fc.orange}[>]{fc.end} Brute forcing {fc.orange}{bits}{fc.end} bits...')
		upper = longbin[0:48-bits] 				# the *known* bits of the seed (start at 32)
		for i in range(2**bits): 				# iterate over all unknown bits
			bini = bin(i)[2:]
			bini = '0'*(bits-len(bini))+bini  		# pad unknown bits to correct length
			print(f'\tSeed: {fc.cyan}{upper}{fc.red}{bini}{fc.end}', end='\r')
			genseed = upper+bini				# create the 48 bit seed
			ns, nb = next32(int(genseed,2)) 		# call nextInt() with the seed
			if nb == getSigned(int(lower,2),32):		# compare with the known result (lower)
				print("\n")
				# The found seed is the one being used internally
				print(f"{fc.green}[>] Found the used seed: {int(genseed,2)}{fc.end}")
				# If you want to start a PRNG with this seed manually (e.g. Java REPL)
				# you'll have to use the reversed seed.
				seed = reverseSeed(int(genseed,2))	# reverse the seed
				print(f"{fc.green}[>]{fc.end} The reversed seed is: {fc.green}{seed}{fc.end}")
				return ns				# return the next seed
		print(f'\n\t{fc.red}Couldn\'t find the seed.{fc.end}')
	print()
	sys.exit(1)

token = -504229198866833519
png_sig = bytes.fromhex("89504E470D0A1A0A")
png = png_sig
png_sig = bytes_to_long(png_sig)

f = open("out.txt","r").read()
exec(f"out = {f}")
seed = crackSeed(png_sig^out[0])
ns = seed
for i in range(1,len(out)):
	ns, long = nextLong(ns)
	png += long_to_bytes((out[i]^long)&0xffffffffffffffff).rjust(8,b'\x00')

g = open("flag.png","wb")
g.write(png)
g.close()
```

<figure><img src="https://329253018-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIYUhWFsdATjBxpgp6f6z%2Fuploads%2FRNmH0VrekYU90AzA31H3%2Fflag.png?alt=media&#x26;token=61b2b3c2-4112-49cf-8fb5-037850282345" alt=""><figcaption></figcaption></figure>

Flag : flag{the\_season\_of\_lies}

## Order (46 solves)

### Description

Python's hash function is not cryptographically secure. I thought I was cool and tried writing my own hash function that was somewhat similar. Sadly, I forgot to store my flag and all I have left is this challenge and the fact that it's output is 1. Can you help me recover the flag?

### Solution

From [euler's theorem](https://en.wikipedia.org/wiki/Euler's_theorem) we know that a^phi = 1 mod n. By using this knowledge we can get phi value from modulus then bruteforcing all possibilities through its divisor then reverse the encryption process. Here is solver i used during competition

```python
from Crypto.Util.number import *

# reverse encryption process
# t = k*(phi - 1)
# (flag^-1 * a) mod p = t
# flag^-1  = t * a^-1
# flag = ((flag ^-1)^-1)

sus = 11424424906182351530856980674107667758506424583604060548655709094382747184198
a = 19733537947376700017757804691557528800304268370434291400619888989843205833854285488738413657523737062550107458
p = 48743250780330593211374612602058842282787459461925115700941964201240170956193881047849685630951233309564529903

a_inv = pow(a, -1, p)


phi = euler_phi(p)

for i in divisors(phi):
    if pow(sus, i, p) == 1:
        for t in range(i-1, p, i):
        	tmp = a_inv * t
        	tmp = pow(tmp, -1, p)
        	flag = long_to_bytes(tmp)
        	if b"flag{" in flag:
        		print(flag.decode())
        		break
        break
```

Flag : flag{big\_numbers\_are\_bad\_numbers}