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:

def getAnnoyingPrime(nbits, e):
	while True:
		p = getPrime(nbits)
		if (p-1) % e**2 == 0:
			return p

nbits = 128
e = 17

p = getAnnoyingPrime(nbits, e)
q = getAnnoyingPrime(nbits, e)

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

Main Part:

class RNG:
    def __init__(self, lfsr, N, nbits):
        self.lfsr = lfsr
        self.N = N
        self.nbits = nbits
        
        if not (pow(2, 27) < N < pow(2, 31)):
            raise ValueError("modulus is too big or small")
        
        K = pow(2, nbits) // N
        self.cutoff = K * N

    def get_random_nbit_integer(self):
        res = 0
        for i in range(self.nbits):
            res += self.lfsr.bit() << i
        return res
    
    def get_random_integer_modulo_N(self):
        count = 1
        while True:
            x = self.get_random_nbit_integer()
            if x < self.cutoff:
                return x % self.N, count
            count += 1
''''''
        if c.startswith("R"):
            x,t = rng.get_random_integer_modulo_N()
            print("creating this random number took {} attempts".format(t))   
''''''

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)

from tqdm import tqdm
tmp = 2**32
small = 2**32
sml_n = 0
for N in tqdm(range(2**27,2**31)):
    s = tmp // N * N 
    if s ==0b11101111111111111111111111111111 :
        small = s 
        sml_n = N
        print(s,N)

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

correlated

Main Part:

taps = [45, 40, 39, 36, 35, 34, 33, 32, 30, 28, 27, 23, 22, 21, 19, 17, 16, 15, 14, 13, 9, 7, 3, 0]# 24
n = 48
m = 20000
prob = 0.80
delta = 1048576

''''''
    noise = [secrets.randbelow(delta) > prob * delta for i in stream]
    stream = [i ^ j for i,j in zip(noise, stream)]
''''''

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)

Main part:

def is_valid(x):
	return type(x) == int and 0 < x < n

def encode(x):
	return x.to_bytes(256, 'big')

def H(g, h):
	return int.from_bytes(shake_128(encode(g) + encode(h)).digest(16), 'big')

def verify(g, h, pi):
	assert is_valid(g)
	assert is_valid(h)
	assert is_valid(pi)
	assert g != 1 and g != n - 1
	m = H(g, h)
	print(m)
	r = pow(2, T, m) # 2 ^ 2 ^ 64  % m
	assert h == pow(pi, m, n) * pow(g, r, n) % n

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.