# Tag Info

4

$q$ does not divide $s^e-h(m)$, but $p$ does, so since the gcd must divide both $s^e-h(m)$ and $n$ it's $p$. To be even more explicit, we know that $p$ divides both $s^e-h(m)$ and $n$. The only larger divisor of $n$ that is also divisible by $p$ is $n$ itself, but if $n$ would divide $s^e-h(m)$, then $q$ would also divide $s^e-h(m)$, which we already assumed ...

2

The following potential reasons occur to me why someone might not choose to use the CRT optimization: The implementor worries about induced faults (but not quite enough to implement the obvious protection against it). That is, with the CRT optimization, we process the RSA block both mod p and mod q separately, and then combine them. That means that if ...

2

Using randomization on the RSA key before encryption doesn't work as easy as a simple XOR: the key (or actually, key pair) has some complicated mathematical structure, and the public part of it (the modulus and the public exponent) need to be known by the encrypting party. What might be possible would be to randomly chose the encryption exponent, and ...

1

The main problem here is that signature is malleable. Given signatures on $m_1$ and $m_2$ allows you to construct a valid signature on $m_1m_2$ by multiplying the signatures. Therefore, the answer is no. When you hash you don't have $H(m_1m_2)=H(m_1)H(m_2)$, so hashing destroys this algebraic structure that connects messages and signatures. EDIT: I'm ...

1

RSA CRT (with $N$ the product of two distinct primes $p$ and $q$) implements the $x\to y=x^d\bmod N$ private-key function by computing $y_p=x^d\bmod p$ and $y_q=x^d\bmod q$; then combining $y_p$ and $y_q$ into the desired $y$ by constructing the solution to the equations $y\equiv y_p\pmod p$, $y\equiv y_q\pmod q$, $0\le y<N$, with that last step requiring ...

1

I might be giving out too much information here (so don't read unless you want spoilers). Anyway, as rings the Chinese Remainder Theorem gives $$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z}\times \mathbb{Z}/q\mathbb{Z}$$ The isomorphism takes $(\mathbb{Z}/n\mathbb{Z})^\times$ to $(\mathbb{Z}/p\mathbb{Z})^\times \times ... 1 Hint: try to prove that$a^{phi(n)/g} \equiv 1 \pmod p$for all$a$satisfying$gcd(a, n) = 1$. Metahint:$phi(n)/g = (p-1) \times (q-1)/g$; is$(q-1)/g\$ an integer?

1

It is generally applied as far as I know. One thing that makes it tricky to implement in some situations is that it may be more vulnerable to certain side channel and fault injection attacks than "straight" RSA. Those attacks may expose the prime factors and thus the private key. I cannot see other reasons why it wouldn't be implementable on some platforms, ...

Only top voted, non community-wiki answers of a minimum length are eligible