Linked Questions

2 votes
3 answers
37k 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 ...
user11621's user avatar
1 vote
2 answers
3k 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 $\...
Toomany Bees's user avatar
7 votes
1 answer
2k 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 ...
user4811's user avatar
  • 579
3 votes
1 answer
844 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$, ...
user51957's user avatar
8 votes
1 answer
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 ...
4nf3rt's user avatar
  • 145
3 votes
1 answer
757 views

Given $φ(n)$ how can we find any combinations for $p, q$ prime numbers

Suppose i already have found that $φ(n) = 240$ for $n = 900$. How can i conclude that my $n = pq$ is of type $2^2\cdot3^2\cdot5^2$? What is $q$ and what is $p$ here? To be more precise with my ...
Mabadai's user avatar
  • 133
0 votes
1 answer
555 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?
Kp23's user avatar
  • 17
-1 votes
1 answer
278 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 ...
atom2ueki's user avatar
  • 157
-1 votes
1 answer
1k 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 ...
Aneesh Relan's user avatar
0 votes
2 answers
541 views

Find the RSA private key only by knowing the public key, the ciphertext and that each letter in the alphabet was encrypted separately

Is there a way to determine the private key (or the phi value) without n factorisation if one knows the ciphertext and the public key and that each letter of the (English) alphabet has been encrypted ...
georggr's user avatar
0 votes
1 answer
641 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 ...
Peter_Pan's user avatar
  • 103
0 votes
0 answers
75 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$ ...
Combiner_85's user avatar