Linked Questions
13 questions linked to/from Is knowing the private key of RSA equivalent to the factorization of $N$?
1
vote
1
answer
13k
views
RSA, finding p,q [duplicate]
If the public key $(e,n)$ and the private key $(d,n)$ are known, what is the easiest way to find the primes $p$ and $q$?
When $n$ and $\phi(n)$ are given this is easy to solve. But I can't manage it ...
- 19
0
votes
0
answers
36
views
How to factor $n = p.q$, where $p,q$ are primes, knowing a multiple of $\mathrm{lcm}(p-1, q-1)$? [duplicate]
I was reading this post https://senderek.com/SDLH/ about Shamir's hash function, which is defined as follows:
Let $p,q$ be positive prime integers and let $n=p\times q$. Let $\ell = \mathrm{lcm}(p-1, ...
- 509
7
votes
2
answers
35k
views
Finding Private key in RSA with public key, cipher text and plain text
Is there a known 'non-brute force' method of determining a private key in an RSA system when all other parameters are know?
I found the values of a ciphertext ($C$), its corresponding plaintext ($P$) ...
- 73
12
votes
1
answer
6k
views
Algorithm to factorize $N$ given $N$, $e$, $d$
I have an RSA public key (public modulus $N$ and public exponent $e$), and the private exponent $d$ of matching private key.
How can I compute $p$ and $q$, the primes factor of $N$ ?
- 123
3
votes
1
answer
1k
views
Theoretical attack on RSA
The high security of RSA is granted, because it is very hard to factorize
$$
N = p * q
$$
Nevertheless, there is actually no need of factorizing $N$, in order to generate the $Private$ $Key$, but the ...
- 97
3
votes
1
answer
2k
views
RSA private key d knowing e,n
I need to find RSA private key $(d, N)$ knowing $(e, N)$. It's "own" RSA implementation. As i know
$p$ is random 70 bit number, then $q$ is $p-2^{10} < q < p+2^{10}$
$d$ is max 16 bit long with ...
- 195
-1
votes
1
answer
842
views
Cracking RSA message with shared modulo but different e while knowing one of the private keys
How can one crack a message c_2 encoded by e_2 if one knows e_1, e_2, d_1, and both codes share common modulo n, without using factorization?
Considering textbook RSA
- 113
0
votes
2
answers
485
views
RSA algorithm private key extraction
Decrypting messages can be done by using the following formula:
$$M = C^d \mod n$$
Where $M$ is the decrypted message, $C$ is the encrypted message and $d$ is the private key
Theoretically speaking,...
- 109
0
votes
2
answers
635
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 ...
- 1
1
vote
1
answer
1k
views
Factoring $n$ in RSA knowing $e$ and $d$
I know that if $(n,e)$ is the public key in RSA and we also know $d$ the private key, then there is a probabilistic algorithm to factor $n$.
I'm reading the proof from Fact 1 on here.
I understand ...
- 135
0
votes
0
answers
698
views
RSA: Multiple Private keys for single public key and N [duplicate]
I'm working on a problem that gives me two private keys $d_1,d_2$ that work with the same $(N,e)$ pair. The problem gives me the two private keys and $N$. Is it possible to find $p$ and $q$? Or how ...
user59119
3
votes
2
answers
183
views
Does Coron and May's paper for deterministically reducing finding 𝑑 to factoring 𝑛 work with $\lambda(n)$?
Samuel Neves in his reply mentioned a method by Coron and May's 2004 paper for deterministically reduce finding 𝑑 to factoring 𝑛.
As you all know, we are using $\lambda(n)$ everywhere now for RSA. ...
- 159
1
vote
1
answer
276
views
Same message space for different public exponents
What is the weakness, if there is any, of using the same message space for different public exponents (assuming e changes everytime)?
Imagine I have a message space [0,n] where n is a 1024 bit number ...
- 431