# TSJ CTF 2022 WriteUps

This time I created several challenges for TSJ CTF 2022, and I published my challenges and writeups in maple3142/My-CTF-Challenges. Due to GitHub's poor support of mathjax rendering in markdown, I decided to create this one for readers of Crypto writeups.

For other categories, please read it here

## Futago

- Category: Crypto, CSC (Cursed Shaman Challenges, guessy challenges in TSJ CTF)
- Score: 56/100 (CSC)
- Solves: 14/428

### Description

Who need source for RSA challenges?

### Overview

See the README of this challenge.

### Solution

#### Stage 1

Guess that two public keys shares a prime, so you can factor it with gcd.

#### Stage 2

Found out that

#### Stage 3

You got two seemingly normal 2048 bits RSA public key

If you write them like this:

Then substracting them:

Suppose

Then you can multiply them together:

It is easy to see

1 | from Crypto.PublicKey import RSA |

## RNG++

- Category: Crypto
- Score: 213/500
- Solves: 21/428

This is actually a broken version of

`RNG+++`

.

### Description

I encrypted the flag and messages by xoring them with a random number generator.

### Overview

You got a simple LCG with `randmsg`

are encrypted by the same
way.

### Solution

The first thing to notice is `randmsg`

generated messages
are all decimal digits, and they are `0x30`

to
`0x39`

in ASCII. It is obvious that their binary
representation are all `0011????`

, so we can get serveral non
continuous bits of states

The most simple unintended solution is to use `z3`

. You
just let the state be

Another more mathematical unintended solution by @Kuruwa: Since

The intended solution will be in the writeup of
`RNG+++`

.

## babyRSA

- Category: Crypto
- Score: 276/500
- Solves: 13/428

### Description

### Overview

We have

### Solution

By substituting the coorinates of

Define another polynomial

For more details: Extensions of Coppersmith algorithm

Once you got

1 | from Crypto.Util.number import * |

Another way to factor it by @Kuruwa:

Since

Since

## Top Secret

- Category: Crypro
- Score: 325/500
- Solves: 9/428

### Description

In year 2087, the TSJ corporation invented a new patented stream cipher to protect their communication. One day, another member stole an important file from the CEO's computer, but it turns out to be encrypted. Fortunately, the script used to encrypt the file were stolen too. You, as a member of Nantou Resistance, accept the challenge to decrypt it.

### Overview

This is a weird stream cipher that has an internal state
`s`

, and it will update its state using the
`forward`

/`fast_forward`

function:

1 | def forward(s: int, n: int, k: int) -> int: |

The `k`

is a known constant, and the `n`

is the
key of the cipher. The initialize state of the cipher is fixed too. The
objective is to decrypt a PNG encrypted by it.

### Solution

First, it is necessary to understand the meaning of
`s = (s >> 1) ^ ((s & 1) * k)`

. If you ever tried
to read the implementation of AES, you may find that it is pretty
similar to the `xtime`

operation. (An
example in C)

`xtime`

operation means multiplying an

In this challenge, the order of bits are swapped, so the bit shifting
direction are different. And the constant `k`

obvious
represents a 128 degree polynomial...?

Actually, `key = randbelow(2 ** 128)`

is meant to confuse
people. If you try to construct the polynomial by
`f'{k:0128b}1'`

you will see it is not a prime polynomial,
because its leftmost bit is `0`

. The correct degree is 127,
so you can construct the field in Sage and implements
`fast_forward`

like this:

1 | from sage.all import GF, var |

The next step is to observe that the first 16 bytes of PNG is known, not just 8 bytes, because of the IHDR chunk. Xor the first chunk of ciphertext and the first 16 bytes of PNG gives second state of the cipher. This can be written as:

So this is a discrete log problem in

The intended way is to use Fast Evaluation of Logarithms in Fields of Characteristic Two, which can solve discrete log in this size easily, and it is implemented in pari too.

In Sage, you can just use `pari.fflog(e, g)`

to find
`x`

such that `g^x == e`

. In newer version of Sage
(9.5 or above), `e.log(g)`

works too.

1 | from sage.all import var, GF, pari |

By the way, @Utaha
tells me that it is not necessary to compute the discrete log to solve
this challenge. Because the key stream is just

## Cipher Switching Service

- Category: Crypto
- Score: 416/500
- Solves: 4/428

### Description

You can freely swap the encrypted flag between two cryptosystem, but you still don't know what is the flag.

### Overview

The server prints one 1024 bits RSA public key and one 1024 bits ElGamal public key on connection, and gives an RSA encrypted randomly padded flag (padded length is 96 bytes). The length of the flag is 20.

Server supports two operations, allowing you to decrypt a RSA ciphertext and encrypt it using ElGamal, and vice versa.

### Solution

Note: There is a much more simpler unintended solution idea from @Mystiz, scroll to the bottom to see

Using the homomorphic property of RSA, we can get any ciphertext of

I use

When it decrypts

Suppose

Since the oracle is not really robust, might need to use some heuristic to make it more stable.

1 | from pwn import * |

An unintended solution by @Mystiz is to find a *slightly* above

## Signature

- Category: Crypto
- Score: 469/500
- Solves: 2/428

### Description

Another boring crypto challenge about signatures.

### Overview

This challenge signs 6 signatures using ECDSA on Secp256k1. The nonce

### Solution

This challenge is based on jonasnick/ecdsaPredictableNonce.

Need to use two basic facts:

- For two n bits integer
, , where and is their n-th bit.

So

In Secp256k1,

But it forgot an important fact:

Details are in the solution script

After recovering `Congrats! This is your flag:`

in the plaintext, we can take
the first block and xor it with the first block of ciphertext, they
decrypt it with the key. This is how AES-CTR works.

1 | from fastecdsa.curve import secp256k1 as CURVE |

## RNG+++

- Category: Crypto
- Score: 469/500
- Solves: 2/428

This upgraded version of

`RNG++`

, so you might want to read it before reading this.

### Description

I encrypted the flag and messages by xoring them with a random number generator again. But it should be harder to break this time.

### Overview

Basically same as `RNG++`

, but

### Solution

Since we only know some bits in each state

1 | 0011????0011????0011????0011????0011????... |

It is easy to see **small**, so it isn't
too hard to think about lattice.

Using coefficient matrix of those polynomials (

1 | from Crypto.Util.number import * |