Linked Questions

2
votes
3answers
31k views

How can I find the prime numbers used in RSA?

I got this question in a local hacking event, but I couldn't solve it. Problem Statement ---- Continuing their snooping habit, NSA kept bugging Alice's communication. Resorting to the age old ...
1
vote
2answers
629 views

In RSA, why would we ever want to find the values of p and q if we already know phi(n)?

I'm studying RSA for the first time, and I know that $p$ and $q$ must be kept secret because with them we can calculate $\phi(n)$, which then lets us calculate the private key $d$. So $p$, $q$, and $\...
5
votes
1answer
1k views

Is it possible to determine the group order by knowing the “public” and “private” key exponents in an RSA group?

I have an RSA group with modulus $n = p \cdot q$, two safe primes $p=2p'+1$ and $q=2q'+1$ and the "public" and "private" key exponents $d$ and $e$. $\phi(n) = 4p'q'$ is the order of the RSA group. If ...
3
votes
1answer
585 views

Equations modulo phi(n)

Let $n$ be an RSA modulus and assume one has the two following equations \begin{align} y_1 = (x+a_1)^{-1} \pmod{\varphi(n)}\\ y_2 = (x+a_2)^{-1} \pmod{\varphi(n)} \end{align} with known $y_1$, $y_2$, ...
7
votes
1answer
1k views

Deletion in RSA Accumulator

I am studying RSA Dynamic Accumulators and I have a question: why is it simpler to calculate the new accumulator value after a deletion if the secret $\phi(N)$ is known? Is possible to calculate the ...
0
votes
1answer
422 views

In RSA. Why is $\phi(n)$ kept secret and $n$ is public?

I mean, $n$ can also be easily used to find the factors $p$ and $q$ right?
-1
votes
1answer
242 views

How to keep phi(n) secret in RSA?

As we know, RSA cryptosystem have both private key(a,p,q) and public key(b,n), by chinese remainder theorem and fermat's little theorem, we know that the importance of keep p and q secret, and from ...
-1
votes
1answer
988 views

Can I calculate $d$ given only RSA’s $c$, $n$ and $e$?

The question “Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid” assumes the factors are known. This got me wondering if it is possible to ...
0
votes
1answer
136 views

RSA - Calculating $d$ given $\varphi (N)$ and $N$

From this discussion, I know that if I know $\varphi (N)$ and $N$ (where $N=pq$, $p$ and $q$ prime), then I can very easily get $p$ and $q$. Suppose I have the encrypted message $c$. I want to get ...
0
votes
0answers
51 views

How do I retrieve a number which has been multiplied with a random number?

I have a 1024-bit number $n$ obtained by multiplying two 512-bit randomly generated prime numbers $p$ and $q$. Then there's $\phi = (p-1)(q-1)$, which is another 1024-bit number. I do not have $\phi$ ...