Suggestions for cool/fascinating math problems that are hard to solve, but if done correctly can be performed very efficient? Wanna build some puzzles and need some ideas :)

You could have a problem based on Diffie-Hellman key exchange, or RSA.
You know, if you use small values then figuring out the discrete logarithm problem or factorization or something like that would be an interesting challenge for a human.

You can also construct RSA keys in a poor way. For example, if two public keys have one common factor it's possible to recover both private keys.

Because (very trivial example)
If you have two public keys
n1 = (3*5)
n2 = (3*7)
Then gcd(n1,n2) = 3

And then you can just factor out the remaining primes by just

n1/3
n2/3

Any other ideas? Maybe with polynomials, curves, algebra or something else :D?