Linked Questions

0
votes
1answer
780 views

In what cases will RSA not work? [duplicate]

I know that there are cases when RSA will not work like when the number to feed into the system is greater than the modulus. I was wondering if there were any other cases when RSA won't work I looked ...
0
votes
1answer
484 views

RSA: Fermat-Euler Theorem - coprimality of message and modulus [duplicate]

I understand the implication of the Fermat-Euler theorem and how it applies to RSA and the detailed explanation by user Ninefingers at What is the relation between RSA & Fermat's little ...
2
votes
1answer
233 views

Why can't different messages result in the same ciphertext when encrypted with RSA? [duplicate]

In the encryption step of the RSA encryption to get the cypher text $C$ $C \equiv M^e \pmod n$ I am struggling to understand how we know that there only exists one $M$ that maps to a certain $C$? ...
0
votes
0answers
109 views

RSA Encryption: What happens if n is a factor of the message M? [duplicate]

From what I have learned about RSA encryption, the message M and the modulo n must be coprime because Euler's theorem only holds for coprime numbers? for example, what happens if I choose p = 3, q = ...
1
vote
0answers
105 views

Fermat's little theorem in RSA with CRT [duplicate]

I have a question about the calculation of RSA decryption with the help of the CRT (Chinese Remainder Theorem). If $c$ is the crytogram, $m$ the message, $d$ the private key and $p, q$ the primes. ...
0
votes
0answers
77 views

In RSA, what happens if the plaintext $m$ is not coprime to $n$? [duplicate]

Coming from the Wikipedia page on RSA, I think I understand the following: RSA is based on generating an integer $n$ as the product of two large primes, $p$ and $q$, and encryption/decryption ...
0
votes
0answers
31 views

RSA encryption. Does message have to be coprime to n? [duplicate]

If I understand correctly, for RSA to work we need the message(cleartext) M $\in Z_n$ and gcd(M,n)=1. That is M coprime to n. This is to fulfil the requirement for Eulers theorem. How does RSA make ...
14
votes
3answers
28k views

RSA Proof of Correctness

Can anyone provide an extended (and well explained) proof of correctness of the RSA Algorithm? And why is it needed? I can't say that this or this helped me much, I'd like a more detailed and newbie ...
6
votes
1answer
4k views

Why does gcd(m,N) have to be 1 in RSA?

In the RSA algorithm, if an attacker wants to get $d$, the attacker does this simply by encrypting random messages $m < N$. If the attacker finds a message $m_1$ that the attacker can not encrypt ...
4
votes
4answers
3k views

RSA by hand - did I do something wrong? (c = m on encryption)

to understand RSA better I am doing a little calculation by hand, this is what I got: Choosing: $p = 3\\ q = 5\\ n = 15\\ \varphi(p\cdot q) = 2 \cdot 4 = 8\\ e > \varphi(n) \implies e = 13\\ e \...
10
votes
2answers
1k views

Can RSA be used to encrypt p?

In RSA you choose $n=pq$ where $p$ and $q$ are large primes with similar length. Then you choose $e$ that is coprime with $\phi(n)$ and find $d$ that is modular multiplicative inverse of $e$ modulo $\...
5
votes
2answers
957 views

In RSA $(e,n)$, $(d,p,q)$, why does it work even if plaintext $M$ is not coprime with $n$?

I read this post Does RSA work for any message M?, but I cant prove that $(M^e)^d-M\equiv 0\pmod{p}$ like this:
7
votes
1answer
1k views

Proving RSA is a permutation

I am trying to prove that RSA is a permutation. All I can find is places where it is stated that it is a permutation because the function is bijective. I know that it is, but would like to see a ...
3
votes
2answers
1k views

Why is RSA encryption performed in mod n, but computation of inverse in $\bmod \varphi(n)$

I am studying the principles of RSA and have come across some unintuitive statements. Lets revisit the RSA algorithm: RSA Key Generation Output: public key: $k_{pub} = (n,e)$ and private key: $k_{pr}...
3
votes
2answers
748 views

Does order matter for RSA when used multiple times?

I actually have no idea how RSA works, but I currently (think that I) know Public and private keys are mathematically doing their opposites Therefore, the order in which they are applied doesn't ...

15 30 50 per page