Tag Info

Hot answers tagged

7

If $p$ and $q$ are 1024-bit primes, then by definition of the bit size of an integer (at least, a prime in a cryptographic context with glimpses of RSA), $2^{1023}\le p<2^{1024}$ and $2^{1023}\le q<2^{1024}$. Thus their product $n=pq$ verifies $2^{2046}\le n<2^{2048}$, and $n$ is a 2047-bit or 2048-bit integer. We show by exhibition that both cases ...


5

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


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

Any integer $n$ can be represented in binary form in $\left \lfloor{log_2{n}}\right \rfloor + 1$ bits. Now coming to your problem where $n = pq$. Number of bits to represent $n$ is $\left \lfloor{log_2{n}}\right \rfloor + 1 = \left \lfloor{log_2{pq}}\right \rfloor + 1 = \left \lfloor{log_2{p}+log_2{q}}\right \rfloor + 1$. By the properties of the floor ...


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

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.


1

No, the total number of bits after multiplication will be 2*1024. In binary form take for eg. 3 (2 bits = 11) * 3 (2 bits = 11) = 9 (4 bits = 1001 in binary)



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