# Tag Info

9

The question asks how to systematically pick the public exponent $e$ in RSA. I'll stick to public modulus $N$ that is the product of exactly two distinct odd primes $p$ and $q$, but the choice of $e$ is not fundamentally different in multiprime RSA. What's an acceptable public exponent $e$? The public exponent in RSA should be an integer $e>1$ with ...

4

Yes; as long as the product of the two plaintexts $p_1 \cdot p_2 < N$, you'll get their product; it doesn't matter what the ciphertext values actually are. The relevant question is: what happens if the plaintexts overflow; that is, what if $p_1 \cdot p_2 \ge N$? In that case, when you decrypt, you'll get the result $p_1 \cdot p_2 \bmod N$

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 ...

4

Yes, you can, but you would need access to raw or textbook RSA encryption and you would have to implement the PKCS#1 v1.5 or PSS padding primitives yourself. Beware that PKCS#1 v1.5 compatible padding is different for encryption signature generation. If you only have PKCS#1 v1.5 encryption or OAEP encryption available then the encryption routine will ...

4

This describes some attacks against textbook RSA (also known as raw RSA), where the public or private functions $x\to y=x^e\bmod N$ or $y\to x=y^d\bmod N$ are applied directly to the message. Encryption / Decryption Determinism in textbook RSA allows an attacker - given a ciphertext - to search for the corresponding plaintext. Determinism also leads to ...

4

You've mostly pieced it out. This is a DER encoding the the public key, and consists of a sequence of two integers (the first being the modulus, and the second being the exponent). Here is the breakdown of the encoding: 30 The value 30 is used to signify 'sequence'; this is a container that carries a list of DER-encoded objects. 82 01 0a Whenever we ...

3

The only way you could do this if if you could affect the padding schemes appropriately. Mathematically, textbook RSA encryption with the private key is the same as textbook RSA signature generation. Nobody should use textbook RSA, however. In practice, padding schemes are used and they differ between the two operations. So unless you can turn off padding ...

3

Okay, I came up with this, it's not a complete answer and the attack presented is pretty weak without a follow-up algorithm for breaking a somewhat unbalanced modulus but let me know if you spot any flaws or have any ideas to improve it... If $n = pq$ with $p, q$ prime and $\gcd(pq, (p - 1)(q - 1)) = r > 1$ then clearly $r = p$ or $r = q$. Now ...

2

This is called the common modulus attack. Bezout's Identity says that there exists $x$ and $y$ such that $ax + by = gcd(a, b)$. In our case we have $gcd(e_a,e_b) = 1$, so we can find $x$ and $y$ such that $e_{a}x + e_{b}y = 1$ (you can use the extended euclidean algorithm for this). After solving for $x$ and $y$, you compute: $C^xC^y\mod N$ to get $M$. ...

2

It's a consequence of the Chinese Remainder Theorem (look it up, if you don't know it) if you want to be more precise and understand it algebraically. If $n=pq$ and $de \equiv 1\;(\textrm{mod }\phi(n))$, then we also have that $$de \equiv 1\;(\textrm{mod }p-1),\;\;de \equiv 1\;(\textrm{mod }q-1),$$ since $\phi(n)=(p-1)(q-1)$. It follows that for any ...

2

Textbook RSA encryption scheme is not IND-CPA secure as it is a deterministic scheme. Textbook RSA signature scheme is not secure considering Existential Unforgability under Chosen Message Attack. e.g. if attacker $\mathcal{A}$ chooses random x $\in$ {1,2,...,n-1} and computes y = x$^{e}$ mod n, then sets m = y, $\sigma_{m}$ = x then $\sigma_{m}$ is a valid ...

2

In RSA, the modulus is computed as $n=pq$ where $p$ and $q$ are prime. Given two moduli, if they have no primes in common, then the GCD is $1$ and they are relatively prime. If they share a prime factor, then the GCD will reveal that prime factor. Therefore, anyone who knows the two public keys can factorize the moduli and break security.

2

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 ...

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 ...

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 ...

1

@CodesInChaos is right, here is an example of his method on your data : $40 = 2^3 5$ so I pick, say $e=3$, which is for sure coprime with $40$. Actually $e=3$ is a common value in some implementations of RSA (see @fgrieu giant response about that) By chance (or did you teacher foresaw it ?) Extended Euclidian Algo is pretty fast here : $40 = 13 \times 3 ... 1 1) Yes. This is the common modulus attack and has actually been answered many times on this forum. 2) Assuming$r$is prime, yes.$\phi(n)$, (the totient of$n$) can be computed by subtracting 1 from each of$n$'s prime factors and multiplying them together. 1 It is extremely likely to be either RSA with PSS padding or RSA with PKCS#1 v1.5 padding, the latter being the most likely. If you sign two times and the output is twice the same then it is not PSS and PKCS#1 v1.5 would be the prime suspect (that was my brain making fun of me, pun not intended). RSASSA-PSS is different from other RSA-based signature ... 1 The "normal", unmodified RSA (called textbook RSA) is susceptible to some attacks. We need to change it slightly to avoid this problems. The question Definition of Textbook RSA and the Wikipedia lists some possible attacks. In practice a special padding algorithm is used, like the Optimal asymmetric encryption padding (OAEP). The documentation of the ... 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 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, ... 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?

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