An enjoyable CTF competition！Never Stop Exploiting got the 4th place in the end. We solved all the six crypto challenges and here are the writeups by tl2cents.

## Binned, 126 solves, 45 pts

### Source code

1 | #!/usr/bin/env python3 |

### Solution

The encryption is : where . It seems like a discrete logarithm problem but the solution is far away from that. The order of with modulo is preventing any kind of smooth attack and subgroup attack. The trick is binomial expansion of and the left part is the first three terms in or the first two terms in . Just solve the equation in integer ring!

exp

1 | # sage |

## Chaffymasking, 66 solves, 73 pts

Just reverse the `chaffy_mask`

function and find that the keys are given with a reversible encryption（`xor`

） which might not be intended solution after seeing the flag.

exp

1 | # python |

## Desired curve, 19 solves, 194 pts

### Source code

1 | #!/usr/bin/env sage |

### Solution

We can choose and to control and , parameters of ecc curve and the flag is encrypted by . Maybe there is a way to obtain a pair of such that is smooth (by brute forcing or something tricky). I simply implemented the subgroup attack. Observe that every time there are small factors of , we can transform and into the subgroup with order by multiplying where is smooth with its prime factors from . Then solve the subgroup discrete logarithm: and obtain . Continue until you fully recover the flag with .

exp

1 | # sage |

## Disinvolute, 7 solves, 334 pts

Fascinating! **Safe primes are not safe this time**! I came up with two solutions for this challenge.

Challenge info:

1 | test@tl2cents:~$ nc 65.21.255.31 12431 |

### Solution 1: Safe primes structure (Intended)

We obtain a nested power equation : . The first power of gives : , and the second power of gives where is Euler function. From above equation, we have:

This situation is corresponding to the **RSA cycling** attack if is deliberately selected such that in is small. I’ll introduce two general attacks with information of or leaked.

**cycling attack**: If is small, we can simply encrypt the ciphertext times and get plaintext ：.**recovering from factorization of**: this attack can performs well if the factorization of is given (or can be easily obtained by`factor`

,`factorDB`

) and the number of prime factors is small. The core idea is reversing the Euler function and obtain all the possible prime factors of . The detailed process can be found here: Cycling Writeup of Google CTF 2022, writeups.

The scenario of this challenge is similar to the challenge`Cycling`

of Google CTF 2022 quals, but in this challenge, we’re not given the exact value of and we can’t factorize either. Notice that : “**I have used safe primes to insure that security is MAX**“, we focus on the **expression of in the safe prime case.**

Applying (2) into expression of n and :

Plugging (3) into (4), we obtain an expression of with ：

By (2), we also have and replace in (5):

Hence, if are strong primes, given the exact value of , we can easily recover by (6) and solve the quadratic equation to factor .

In this challenge , and k is small (about ) by analyzing the data samples, so brute-forcing is enough to recover .

remote data

1 | from pwn import * |

Solver

1 | # sage |

### Solution 2: RSA Broadcast Attack (Unintended)

Every time, we connect to server and obtain a new encrypted data sample . At most, we need 65537 data samples to fully recover by RSA Broadcast Attack: collect enough samples until we can calculate the 65537-th root of in integer ring! The connection times : and the time cost is about 6 hours. I guess that’s why the organizers added another server for this challenge halfway through the game.

## Mariana, 59 solves, 80 pts

Math trick! We need to input x such that:

By the Euler theorem：

## Mindseat, 33 solves, 128 pts

Factorize RSA modulo and then compute subgroup discrete logarithm.

### Source code

1 | #!/usr/bin/env python3 |

### Factorize RSA modulo

The primes are generated with backdoor : . In this case, if k is more than half of `p.nbits()`

, we can use the coppersmith method to factorize the RSA modulo . How to extract k? Observe that :

Find the max k of each modulo n and choose the smallest one as the final k parameter. I choose k = 134.

Coppersmith cracker

1 | def small_roots(n,k=134): |

### Discrete Logarithm

The encryption process is :

Notice the the order of contains the prime power factor : because and the the order of doesn’t contain the prime power factor: , we can transform (2) into the following discrete logarithm problem in subgroup with order :

In the previous section, . Now we can fully recover m by computing the discrete logarithm in (3).

exp

1 | ns = PUBKEYS |