Skip to content

Latest commit

 

History

History
15 lines (10 loc) · 627 Bytes

README.md

File metadata and controls

15 lines (10 loc) · 627 Bytes

Strong Prime

  • Round: 29 (2022/12)
  • Category: Crypto
  • Points: 100
  • Solves: 9

Description

Discrete log can be broken if the prime isn't strong enough, and that's why I use getStrongPrime.

Solution

getStrongPrime doesn't guarantee $p$ to be safe, so it is easy to see $p-1$ have many small prime factors. For each prime factor $q$ we can solve discrete log in that subgroup to get $\text{flag} \equiv x \pmod{q}$ then use CRT to recover the flag. The padding can be handled by guessing the flag length to get another equation to the CRT system.