# Tag Info

4

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

0

If you know the prime factors (p,q) of the modulus, then it would be easy to find the private exponent. You'll proceed as follow: Compute the Euler totient $\phi(n)=\operatorname{lcm}(p-1,q-1)=\frac{(p-1)\times(q-1)}{\operatorname{gcd}(p-1,q-1)}$ Choose a number e such that $\operatorname{gcd}(e,\phi(n))=1$, Apply the Extented Euclid Algorith to compute ...

0

RSA operates over a multiplicative group $(\mathbb{Z}/n\mathbb{Z})^*$, not over a field. You can say that it's a ring, but since addition is not used in RSA it's redundant.

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

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

-2

Turns out I was right. X/ln(x) where X would be 2^n as n being the bits.

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

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

0

In RSA, exponents are small, so the encryption/decryption can be done quickly. Here, exponent is of the form $2^t$, where $t$ is very large. For example, consider RSA 2048 - exponents have at most 2048 bits. If you set $t=2048=2^{11}$, then to solve this puzzle one will need to do only 2048 squarings, roughly the same as you need to do a decryption in RSA. ...

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

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

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.

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

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

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)

0

This is no valid standard RSA problem. My own recovery algorithm to get $p,q$ from $n,e_a,d_a$ failed. The reason: It assumes the standard RSA setting, but most factorization algorithms will reveal that $$n=821 \times 528403 \times 107351609 \times 78385044401 \times 7363074684896267$$ Most probably your given $n$ contains a typo. BTW: Your ...

Top 50 recent answers are included