# Tag Info

6

No, RSA encryption and signature is performed in (the multiplicative semigroup of) the factor ring $\mathbb Z/n\mathbb Z$ which is not a field since the non-zero elements $kp+n\mathbb Z$ (for $0<k<q$) and $kq+n\mathbb Z$ (for $0<k<p$) do not have multiplicative inverses. (However, one easily observes that all other non-zero elements are ...

5

I wondered if there is a "simple" description of the set of numbers n that have this property. Yes, there is; $n$ has a prime factorization $p_1 \cdot p_2 \cdot ... \cdot p_n$ such that all the primes are unique (i.e. $n$ is square-free), and for each prime factor $p_i$, $p_i-1$ must be a divisor of 24. In other words, each prime must be a member of ...

4

You are looking for Proxy Re-Encryption. From a high-level viewpoint, a proxy re-encryption scheme is an asymmetric encryption scheme that permits a proxy to transform ciphertexts under Alice's public key into ciphertexts decryptable by Bob's secret key. In order to do this, the delegator $A$ gives a special re-encryption key $rk_{A \rightarrow B}$ to the ...

4

The attacker wants to find $m = c^d$ but doesn't know $d$, but they can find $m'=(c')^d$ for a significant fraction of random $c^\prime$s. Assume that $\mathrm{GCD}(c, n)=1$. The attacker chooses a random $r$ with $\mathrm{GCD}(r, n)=1$ and computes a new ciphertext $c^\prime$: $c^\prime = c \cdot r^e$ This ciphertext is uniformly distributed among all ...

4

The extended Euclidean algorithm ($\operatorname{xgcd}$), when applied to $p$ and $e<p$, uses at most $\lceil\log_\phi(\sqrt5(p+1))\rceil-2\in\mathcal O(\log p)$ divisions in $\mathbb Z$. (This is Knuth's corollary to Lamé's theorem.) Using Fermat's little theorem and square-and-multiply exponentiation on $e$ modulo $p$ takes at most ...

3

There is no specific reason why $e$ is required to be a prime number. It must be relatively prime to $\phi(n)$ (otherwise we can't decrypt uniquely); however that is the only hard requirement. Assuming that 9 is relatively prime to $\phi(n)$, there is no reason why 9 can't be used as a public exponent. However, selecting a prime value for $e$ does have ...

2

So if $M \approx 10^{20}$, and you have $4 * 10^{20}$ operations, why not just bruteforce it? For more efficient solution, consider meet-in-the-middle technique. For all $1 \le a \le 4\sqrt{M} \approx 10^{20}$, make a hash table with values $a^e \mod{N}$. Then for all $1 \le b \le 4\sqrt{M} \approx 10^{20}$ check if $M^e/b^e \mod{N}$ is in the table. ...

2

One real problem is that lack of authentication between the two sides. Here's one possible problem: Alice generates an RSA keypair (we assume Alice is using proper random numbers) Alice sends the public key as plain text to Bob. Eve intercepts this message, and forwards on a message to Bob with her public key Bob generates a 3DES session key: ...

1

I think that this is not possible with a conventionnal public Key (Probably I'm wrong ?). But this question could easilly be solved by IBE as introduced by Dan Boneh in the seminal paper "Identity-Based Encryption from the Weil Pairing. This new system introduced in the early 2000, allows the Delegation of Decryption Keys, but this require the set up a new ...

1

Can Alice obtain the session key due to the multiplicative properties of the modulus function and the basis of which RSA is built on? Essentially, yes. One way of looking why RSA works (that is, why the encryption and decryption are inverses of each other) is because of two mathematical identities: $$(M^a \bmod N)^b \bmod N = M^{a \cdot b} \bmod N$$ ...

1

Well, I think it is quite hard to give a really objective and complete answer to this question. Personally, I think that why you may encounter RSA blind signatures quite often is due to it's simplicity. I am not quite sure if you will see it often in practical implementation though, because there has been a patent (which as far as I remember expired quite ...

1

You need to choose e such that it is co-prime relative to PHY(n). Since you do not want to get involved in factorization of PHY(n), the best way is to choose e randomly, and better let it be a non even prime. Common values are 2^16+1, 3, etc. Most of the primes you choose will have GCD(e,PHY(n))=1.

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