New answers tagged

0

Well, as the author of the answer you cited, I can't much improve on tylo's answer. However, perhaps a couple of examples will be an useful supplement. First, note that for $a,b \in \mathbb{Z}_4$: $$a \oplus b \equiv a + b + 2ab \pmod 4$$ Where the $\oplus$ on the left side means XOR and on the right side are addition and multiplication modulo 4. In ...


2

Sicne your question is refering to an answer on this site, I will not quote the entire answer here. But the crucial point is there in the last paragraph: If none of that made any sense to you, that's OK. You just need to read up about Abstract Algebra, and Fields, Rings and Groups. It's a fascinating and beautiful area of mathematics, and much of ...


3

Since $e$ and $(p-1)(q-1)$ are relatively prime, the extended Euclidean algorithm gives you integers $u$ and $v$ such that $$ eu + (p-1)(q-1)v = 1, $$ from which it is easy to deduce an integer $d$ such that $ed \equiv 1 \pmod{(p-1)(q-1)}$.


0

You appear to be confused about a couple of different things, at least if I have correctly interpreted your confusion. First, the relation you should be using is congruence, not equality. The encryption congruence (not equation) is thus more precisely: $$c \equiv m^e \pmod n$$ Note that this uses the triple congruence sign rather than the equals sign. ...


1

RSA is based on the Carmichael function $\lambda$ (or if you prefer Euler's totient function $\varphi$): $$x^{\lambda(n)} \equiv 1 \pmod n$$ for every integer x that is coprime to n. From this you trivially get: $$x^{k\lambda(n)} \equiv (x^{\lambda(n)})^k \equiv 1^k \equiv 1 \pmod n$$ and multiplying both sides with x: $$x^{k\lambda(n)+1} \equiv x \...


0

You forget that there are relationships between $n$, $d$ and $e$. If you forget those then you basically forget to include the entire RSA problem.


5

The formula at the heart of RSA is: $$x^{\lambda(n)} = 1 \pmod n$$ where $\lambda$ is the Carmichael function. In the case of two-prime RSA it's $\operatorname{lcm} (p - 1, q-1)$. $$m^{k \cdot \lambda(n)+1} = m \pmod n$$ We choose $d$ such that $e\cdot d = 1 \pmod {\lambda(n)}$. If $\operatorname{GCD}(e,\lambda(n)) = 1$ then there is exactly one solution ...



Top 50 recent answers are included