February 7, 2022

## WriteUps of DiceCTF2022(part crypto)

Record some of my challenge-solving ideas for DiceCTF2022,if there are any discrepancies ,plz correct me ~ .By the way, my English is weak. First attempts to write wp in English. Hope you don’t feel lame…

## baby_rsa

#### Main Part:

the getAnnoyingPrime :

#### Solution:

We can find that n is not very big. So I try to factor it by yafu.

Due to the generation of primes,we know that phi( (p-1)(q-1) ) is a multiple of e .

then AMM can solve this RSA by knowing the factoring of n.

## rejected

#### Solution:

If try to get random integer (modulo N),we can know how many times the new integers generated in order to make the integer less than RNG.cutoff by oracle. but the N depends on the number we provide.

because in the class RNG

here we can find a method to leak the high bits of new integer.

if we can make the self.cutoff=0b1011111111111111111111111111 ,when count += 1,then the high 2 bits of new 32 bits integer is 1,1.

but 0b101111111111111 does not have an N satisfying this condition.

so we try to find more.

At last , we find N = 366048349(self.cutoff =0b11101111111111111111111111111111)

Then, we can solve lfsr by knowing 64 bits.(ps: It is very special that all 64 bits are 1)

## correlated

#### Solution:

Due to the description of this challenge, I went through 2 or 3 hours of paper, but found nothing about the improvement of fast correlation attacks.

Finally, I just try to randomly select 48 bits out of 20,000 Bits.

Assuming that they are not disturbed by noise, then the decryption can be successful and the key can be obtained.

I think the probability of this method is a bit small but it works.

## pow-pow(after the game)

#### Solution:

Verify is

And the prove given in the chal is….

At first I wanted to try fast power, but it failed in the end.

Then I try to analyze the verify part and got an IDEA: h => 1, try to find g and pi

but also failed.

I think what is particularly wonderful is that liangjs converts the problem into power and turns it into addition.

Let , then .

Then we only need to find the solution of .

It can be found that the prove given in chal is to reduce the influence of m.

and crazyman says let m be a smooth number (I didn’t get any inspiration because I think letting gcd(g_0,m) = m is simply impossible.)

So I didn’t solve the chal until the game was over.

After the Game and reading writeups , I’m amazed at how unlikely it is to find such a number ,but it is!

We can let h0 = 0 , then if g0 is the multiple of m, this chal can be solved easily.

Because it converts to

The trouble next is how to find the g0 satisfying this condition.

We choose g0 to be the product of all primes between [1,2**20],and by left shifting g0 to make g0 a multiple of k.

defund(Question maker) choose the base as 2 (official wp)

## commitment-issues(solved by liangjs)

We can converts the main relationship.

The m is flag,and small.

Then by combining the relationship, and use coppersmith to get the m.