# Tag Info

1

The fastest way to solve your problem instance is as outlined in the above comments. First choose yourself a random message $m$ with $1<m<n-1$. Now compute $c\equiv m^d \pmod n$. Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$ $m \equiv c^{17} \pmod n$ $m \equiv ... 10 The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). We can ... 4 You are essentially asserting that if$k \equiv 1 \pmod N$, then$a^k \equiv a \pmod N$. This is false in general. The correct assertion is the following:$a^k \equiv a^\ell \pmod N$if$k\equiv \ell \pmod{\phi(N)}$. In more general group-theoretic terms, if$a$is an element of order$n$in a group$G$, then$a^k = a^\ell$if and only if$k \equiv \ell ...

0

Mathematically, yes, it will work. Practically, you will require an extremely very long time and an incredible amount of energy, considering the sizes of the primes involved in RSA (usually around 1024-bit prime numbers). It is about billion and billions of years and billions and billions times the energy of the whole universe (RSA: How effective is this ...

2

If you know a multiple of $p$ and $k$ is smaller than $\sqrt(p)$ than you can use a different approach than the one by poncho. Note: knowing a multiple of $p$ is the typical case of RSA where you know the modulus $N$ made by $p\times q$, so if your question refers to RSA you are left only with the constrain on the size of $k$. The method you can use is an ...

4

If $p$ is prime, then $\phi(p) = p-1$; so the question is "given $k(p-1)$, can someone get a good guess of what $p$ might be?" It is unlikely that the attacker would be able to limit it to one particular value of $p$ (as there are likely to be multiple values of $p$ that are plausible), however the attacker might be able to construct a short list of ...

Top 50 recent answers are included