Linked Questions

0 votes
1 answer
957 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 ...
Kai Arakawa's user avatar
0 votes
1 answer
538 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 ...
Lordbalmon's user avatar
2 votes
1 answer
361 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$? ...
yanhua's user avatar
  • 21
0 votes
0 answers
145 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 ...
Anakhand's user avatar
  • 101
0 votes
0 answers
111 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 = ...
user25935's user avatar
1 vote
0 answers
108 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. ...
leet's user avatar
  • 11
0 votes
0 answers
51 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 ...
ghetto_department 's user avatar
0 votes
0 answers
42 views

RSA - is the message a member of the multiplicative group of integers modulo n? [duplicate]

As I understand it, RSA works as follows: Pick two large primes $p$ and $q$ Compute $n = p \cdot q$ The associated group $\mathbb{Z}^*_n$ consists of all integers in the range $[1, n - 1]$ that are ...
cmplx96's user avatar
  • 113
0 votes
0 answers
33 views

RSA derivation of ed=1 mod(ϕ(n)) [duplicate]

I know that $m =m^{ed} \bmod n$, and there is Euler's $a^{\varphi(n)} = 1 \bmod n$, but how do we derive that $ed=1 \bmod(\varphi(n))$ holds for all m. Where does that equality come from? Couldn't ...
steatoda's user avatar
0 votes
0 answers
22 views

RSA Digital Signatures Verification [duplicate]

I am trying to learn about RSA digital signatures, and have a question about the verification process. My understanding of the set-up is the following: The signer chooses two secret primes $p$ and $q$,...
Koda's user avatar
  • 101
16 votes
2 answers
35k 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 ...
Matteo's user avatar
  • 1,161
6 votes
1 answer
5k 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 ...
user57752's user avatar
4 votes
4 answers
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 \...
Stefan's user avatar
  • 255
12 votes
2 answers
2k 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 $\...
desowin's user avatar
  • 163
5 votes
2 answers
1k 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:
vũ Hiếu's user avatar

15 30 50 per page