# Tag Info

8

It doesn't become vulnerable; instead, it becomes impossible to decrypt uniquely. Let us take the example you give: $N=65$ and $e=3$. Then, if we encrypt the plaintext $2$, we get $2^3 \bmod 65 = 8$. However, if we encrypt the plaintext $57$, we get $57^3 \bmod 65 = 8$ Hence, if we get the ciphertext $8$, we have no way of determining whether that ...

6

Usually, RSA operations with the public exponent are fast, precisely because the public exponent is short. Hardware accelerators are meant to speed up operations with the private key, which are in much bigger need of it. In particular, hardware accelerators do not need to be "full width" because private key operations use the private key, which contains the ...

6

As mikeazo notes in the comments, RSA operates on the ring $\mathbb Z / n\mathbb Z$ of integers modulo $n$, for a given modulus $n = pq$. In this ring, $$E(m) \cdot t^e \equiv m^e \cdot t^e \equiv (mt)^e \equiv E(mt)\ \pmod n.$$ In particular, for $n = 35$, $e = 23$, $$17^{23} \cdot 2^{23} \equiv 33 \cdot 18 \equiv 594 \equiv 34 \equiv 34^{23}\ ... 5 The modulo operator keeps the result of the addition of M and K within the set Z. For example, if m is 10, M is 6 and K is 5, M + K would be 11 which is no longer in the set Z. Taking 11 mod 10 results in 1 which is in the set Z. As a help towards answering the question whether scheme M + K mod m is perfectly secure, when m is 26 ... 4 Because the time that the Extended Euclidean algorithm depends on the inputs (and, in particular, is a complex function of the two, depending on the ratio expressed as a continguous fraction), there may be some leakage there. It occurs to me, however, that there is a very simple countermeasure; assuming that the secret modulus you are inverting is p, and ... 4 One obvious way is to precompute values a^{k_1} \bmod N, a^{k_2} \bmod N, ...,a^{k_i} \bmod N, and (depending on the value of x) multiply together the appropriate elements. To take a simple example, if we precompute a^1 \bmod N, a^2 \bmod N, a^4 \bmod N, ... a^{2^k} \bmod N, and (based on the value of x in binary, multiply the appropriate ... 3 At the encryption step, you wrote: Public Key: n = 667 k = 3 Input: p = 13 Encrypted Integer: E = (p ^ k) % n And then mistakenly calculated: (13 ^ 7) % 667 = 492 ______^_____________ If you calculate it right using k = 3, you will get E = 196 which correctly decrypts to 13. (as expected) 3 How can I calculate or estimate the difficulty of attacking d when only the public key is known? (no optimizations) Generate a few hundred pairs (n,\varphi(n)) for whatever key size you are interested in, then compute the average distance between the pairs. That would give you a guess as to how many values on average you will need to get ... 3 I just want to add some additional information to the answer of Ilmari. As Ilmari has already described in his answer, when using RSA you work in the ring of integers {\mathbb Z}/{\mathbb Z}_n, which is also called a residue class ring. This means that it consists of the set of residue classes [i], where the i'th class is defined as the set \{a ... 2 In brief: If you know (a,N), you can speed the computation up by precomputing some of the powers of a. Let x=x_n\dots x_1x_0=\sum_{i=0}^n x_i 2^i be the binary expansion of x, and let a_j=a^{2^j}\pmod N. Very naively:$$ a^x \pmod N = \overbrace{a*(a*(a*\dots*(a))\dots))}^{\text{x terms}} $$This requires \theta(x) multiplications. ... 2 You'll probably know this relation, which should be obvious if you think about it:$$(a \bmod n) + (b \bmod n) \equiv a + b \mod n This means that when using addition you do not have to reduce the operands, only the final result. However, if the final result is an operand again it needs not be reduce. This means that long chains of modular additions can ...

2

I am not aware of any method that would let one make good use of a black box or API computing $f(a,e,n)=a^e\bmod n$ for $n$ of up to $2112$ bits, to efficiently compute $f(a,e,n)=a^e\bmod n$ with $n$ above that bound (like $4096$ bits), unless that bigger $n$ has known factorization into terms of at most $2112$ bits (in which case the usual CRT technique ...

2

Mike gave you the answer for the specific question you asked. I'll try to give you an answer to the question you should have asked: For Diffie-Hellman, what criteria should I use to select a secure $p$ and $g$? This question is important, because not every large cyclic group is actually secure. It turns out that, for the group $\mathbb{Z}_p^*$, the ...

2

Numbers get represent as in base 256, i.e. $h = \sum_{i=0}^{17} h_i \cdot 256^i$. Since ints are used which are significantly larger than bytes you don't need to propagate carries immediately. If you forget about modular reduction, then the $i$th digit of the result is computed as $\sum_{j=0}^i h_j\cdot r_{i-j}$. Apart from the lack of carry this is pretty ...

1

From your comment, I replace $p$ with a composite $n$. The answer is no. The problem is determining whether $f(x,y) = a x^2 + b y^2 \bmod{n}$ is one-way or not. We want to find $(x',y')$ such that $f(x',y') = z$, given $a, b, n$ and $z = a x^2 + b y^2 \bmod{n}$. Let us consdier $f'(x,y) = x^2 + h y^2 \bmod{n}$, where $h = b a^{-1} \bmod{n}$. The problem is ...

1

I'm assuming you meant "how to efficiently find generator $g$ in a cyclic group?" Small groups For small values $p$, bruteforce is efficient. Large groups with known factorization of group order The order of the group $\mathbb{Z}_p^*$ is $p-1$. The order of every element divides the order of the group, so the factorization of $p-1$ reveals the possible ...

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