# Tag Info

## Hot answers tagged modular-arithmetic

13

$\phi(n)$ is the order of the multiplicative group of the numbers in $\mathbb{Z}_n$. $\phi$ is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element. So, using $\phi(n)$ ensures that decryption works. Since $ed\equiv 1\bmod{\phi(n)}$, we can say ...

10

Where does the $\phi(n)$ part come from? Well, the actual requirement is that, if $n = pq$ and both $p$ and $q$ are prime, we have: $de \equiv 1 \mod p-1$ $de \equiv 1 \mod q-1$ The first ensures that RSA encryption, followed by RSA decryption, will obtain the original value modulo $p$. The second ensures that RSA encryption, followed by RSA ...

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

8

The extended Euclidean algorithm is essentially the Euclidean algorithm (for GCD's) ran backwards. Your goal is to find $d$ such that $ed \equiv 1 \pmod{\varphi{(n)}}$. Recall the EED calculates $x$ and $y$ such that $ax + by = \gcd{(a, b)}$. Now let $a = e$, $b = \varphi{(n)}$, and thus $\gcd{(e, \varphi{(n)})} = 1$ by definition (they need to be coprime ...

7

When $n$ is prime, solving for $e$-th roots modulo $n$ is easy, since it suffices to compute $d = e^{-1} \pmod {n-1}$ and then $s = m^d \pmod n$. If $n$ is not prime, but is instead a RSA modulus (a composite integer that is the product of two big primes), then the problem becomes apparently hard (in the sense that we don't have a clue how to do it ...

6

The two last equations don't directly give you the value of $C_i$, they are telling you the values of the remainder of Ci when divided by $P$ and $Q$. You then use the Chinese Remainder Theorem with this information to produce the value of $C_i$ (modulo $N$) that you are looking for. See en.wikipedia.org/wiki/Chinese_remainder_theorem (there is an algorithm ...

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}\ ... 6 Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. – xagawa @xagawa Yes, I want that :-) – Dingo13 I list the PRFs based on the number-theoretical assumptions. They are arithmetic or mathematical function.'' You can use the Feistel network to obtain (S)PRPs from PRFs in theory. From the DDH assumption The Naor-Reingold ... 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 ... 5 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 ... 5 Actually, the fundamental mathematical operation is not$$ \begin{align} \mathbb{N} &\to \mathbb{N} \\ m &\mapsto (m^e) \bmod n & \text{(elevate to the power of $$e$$, divide by $$n$$ and take the remainder)} \\ \end{align} $$but$$ \begin{align} \mathbb{Z}/n\mathbb{Z} &\to \mathbb{Z}/n\mathbb{Z} \\ m &\mapsto (m^e) \bmod n & ...

4

$J_A \cdot a^e \: \equiv \: 1 \:\: \pmod{n} \;\;\;\;\; \iff \;\;\;\;\; a^e \: \equiv \;\; $$\operatorname{modinv}$$(J_A,\hspace{-0.02 in}n) \:\: \pmod{n}$ Since that is the RSA problem, the fastest known way to solve it is to factor $n$ which reveals $\lambda$$(n), and then try \;\;\; a \: = \: \operatorname{mod}\left(\hspace{-0.03 ... 4 No, you wouldn't always get that - in fact it's very unlikely behavior (eg the wikipedia worked example). If encrypting with the public and private exponents was always the same you'd be able to decrypt someone else's message c by calculating c^e=c^d=m. It is important to realize that (after running the RSA setup algorithm) there is algebraically no ... 4 These prime numbers are called Solinas primes (because they were described by Jerome Solinas). The article details how they are found and how optimization works for them. As a brief summary, consider a prime:$$p = \sum_{i=0}^{k} b_i 2^{iw} $$where each b_i is either 0, 1 or -1, and w is your "word size" (typically w = 32 or 64 will yield ... 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 ... 4 See section D.2.2 of FIPS 186-3. The modular reduction can be expressed as two additions and two subtractions of values which are assembled by concatenating selected 32-bit words of the 448-bit value which is to be reduced. Note that these additions and subtractions are modular, so you may have to mind some carries. 4 I had a similar problem, and it took me a long time to figure out all the math, as some of the proofs can be rather terse. So, I took it upon myself to write a full explanation of how to factor N, without all the symbols and relying on a bit less prior knowledge. Anyway, such a system is not safe. If you know a valid e and d, you can factor N. ... 4 To clarify a misconception in your question: It is not true that e is chosen large to make RSA more difficult to crack. Often e is chosen from \{3,5,17,257,65537\}. This has computational advances with regard to square and multiply algorithms as mentioned by Gilles. The choice of e has no influence in the security of RSA primitive (as long as ... 4 Firstly, |\mathbb Z_n|=n, whereas |\mathbb Z_n^*|=\varphi(n)<n. So, by the pigeon-hole principal there cannot be a mathematically invertible function f:\mathbb Z_n\to\mathbb Z_n^*. So, lets relax our idea of what 'invertible' means a bit. How about ensuring every element of \mathbb Z_n^* has a preimage? Yep, we can do that. To use a couple of ... 4 This is Cipolla's algorithm, I believe. The integers mod p we call \mathbf{F}_p, and since h^2 -4x is a quadratic nonresidue mod p, the polynomial P(Y) := Y^2-(h^2-4x) \in \mathbf{F}_p[Y] has no roots. We can then mod out the polynomial ring \mathbf{F}_p[Y] to get \mathbf{K} := \mathbf{F}_p[Y]/(Y^2-(h^2-4x)) (which by some algebra we know is ... 3 No, it isn't safe. Knowing the private exponent d (and a corresponding public key) allows factoring the modulus m, and this allows retrieving all other private exponents (given the public ones). Bob should generate a new modulus, this is not that expensive. Also, Bob should revoke his old public key, if it is registered anywhere. 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 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 ith 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 ... 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 ... 3 First note that using MPC we can compute addition, subtraction, multiplication and division (multiplication by the inverse) on shares. It turns out there are also secure protocols out there for doing comparison (see http://viff.dk and their references). So we could simply do something like this: while k >= m: k = k-m m could be public or secret ... 3 In modular calculations such as this, the divisor (in your case 26) must be at least the size of your character code space. Your code space is 46 characters, so that is not going to work. Any output of the modular calculation will be less than the divisor, so you will never get 83 for x mod 26, it is not going to happen. For a 46 character code space, 46 is ... 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 ...

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