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+1\\ q = 289j+1$

#### # Solution:

We can find that `n`

is not very big. So I try to factor it by `yafu`

.

$p = 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 = 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

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

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

$h = 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`

$pi^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=base^{h_0},g=base^{g_0},pi=base^{p_0}$ , then $base^{h_0} = base^{p_0m+g_0r},r=2^T\mod m$.

Then we only need to find the solution of $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=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 = 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.