3 ms·
Very nice asymmetric backdoor! If you happen to know the factorization and the factors are not too large (e.g. two 500-bit factors + some chaff), then you can
by madars 11y ago
Very nice asymmetric backdoor!
If you happen to know the factorization and the factors are not too large (e.g. two 500-bit factors + some chaff), then you can just use Pohlig-Hellman algorithm to solve the DLP modulo each individual factor, combine the results and recover the shared Diffie-Hellman secret.
But without this trapdoor information (and, say, if p was chosen to be a Blum integer), computing the Diffie-Hellman shared secret is as hard as factoring that modulus (see https://crypto.stanford.edu/~dabo/abstracts/DHfact.html https://crypto.stanford.edu/~dabo/abstracts/DHfact.html).