Cryptographic Reference Problems

FACTORING

Integer factorisation: Given positive $n$, find its prime factorization.

i.e. find the distinct $p_i$ such that $n = p^{e_n}_1\cdots p^{e_n}_n$ for some $e_i \geq 1$

SQRROOT

Given $a$ such that $a \equiv x^2 \mod\ n$ find $x$

RSAP

Do RSA in reverse:

Given a private key $(n, e)$ and a ciphertext $c$ made using that key find the plaintext $m$ such that $m^e\equiv c \mod n$

Comparison

SQRROOT $=_p$ FACTORING

So it is just as hard to solve SQRROOT as it is FACTORING.

RSAP $\leq_p$ FACTORING

So reversing RSA is no harder than FACTORING, but it could be easier. This is an unknown.

DLP

The Discrete Logarithm Problem:

Given a prime $p$, a generator $g$ of $Z^*_p$

DHP

The Diffie-Hellman problem:

Given a prime $p$, a generator $g \in Z^*_p$, and elements $g^a\mod p$ and $g^b\mod p$, find $g^{ab}\mod p$

Comparison

DHP $\leq_p$ DLP

Back to Computer Security