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 :

p=289k+1q=289j+1p = 289k+1\\ q = 289j+1

# Solution:

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

p=337117592532677714973555912658569668821q=172036442175296373253148927105725488217p = 337117592532677714973555912658569668821\\ q = 172036442175296373253148927105725488217

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

self.cutoff=232//NNself.cutoff = 2^{32}//N * N

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

pimg264modmhmodnpi^m\cdot g^{2^{64}\mod m}\equiv h\mod n

And the prove given in the chal is....

h=g2264modnh = g^{2^{2^{64}}}\mod n

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

pimmodn=g0(2Tmodm)modnpi^m\mod n = g^{0-(2^T\mod m)}\mod n

but also failed.

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

Let h=baseh0,g=baseg0,pi=basep0h=base^{h_0},g=base^{g_0},pi=base^{p_0} , then baseh0=basep0m+g0r,r=2Tmodmbase^{h_0} = base^{p_0m+g_0r},r=2^T\mod m.

Then we only need to find the solution of h0p0m+g0rmodϕ(n)h_0\equiv p_0m+g_0r\mod \phi(n).

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

0=p0m+g0r=p0m+kmr=>0=p0+kr=>p0=kr0=p_0m+g_0r=p_0m+kmr=>0=p_0+kr=>p_0=-kr

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.

s=mdc1=(s+r)modnc2=r5modns = m^d\\ c1 = (s+r)\mod n\\ c2 = r^5\mod n

The m is flag,and small.

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

请我喝[茶]~( ̄▽ ̄)~*

De3B4to 微信支付

微信支付

De3B4to 支付宝

支付宝