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

10

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

9

Actually, that was proposed here back in 1998 (sorry, an electronic version of the paper does not appear to be on the web) -- the author claimed a modest speedup in the private operations. However, that speed up would appear to be about the same if you just did "multiprime RSA", that is, selected an RSA modulus of the form $pqr$ for three distinct primes ...

9

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$. If there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we ...

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

There's no real difference between $p$ and $q$ in RSA. It looks like OpenSSL just has the agreement "$p$ has to be bigger than $q$" for conveniences. One of the numbers has to be bigger than the other (otherwise they would be the same number, and $p = q$ is very bad in RSA). Just use two examples: $p = 13$ and $q = 11$. $p$ is bigger than $q$, all right. ...

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

7

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

7

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. This is an application of the shared modulus attack explained by Boneh in his analysis of RSA ...

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

The GQ identification scheme is essentially a zero-knowledge proof of a value $x$ such that $x^\mu \equiv J \pmod N$ where $N$ is an RSA modulus and $(\mu,N)$ are system parameters and $J$ is known to the verifier and $x$ only known to the prover. Now your question is not directly concerned with the aforementioned proof where a user shows the possession of ...

6

A possible RSA variant uses: some odd exponent $e>2$ (that can be $e=3$ or $e=2^{16}+1$ as customary in standard RSA); $p$ and $q$ distinct large random primes, with $\gcd(e,p)=\gcd(e,p-1)=\gcd(e,q-1)=1$; $N=p^2\cdot q$; some $d$ computed such that $d\cdot e\equiv 1\pmod{\operatorname{lcm}(p,p-1,q-1)}$; public-key function $x\to x^e\bmod N$; private-key ...

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. The definition of perfect security is: Claude Shannon proved, using information theory considerations, ... 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 & ...

5

Is it the idea to limit the result to a group? Yes. The advantage to doing so is that we have multiplicative inverses (well, for anything relatively prime to $n$) and can therefore decrypt. It also keeps ciphertexts relatively small. Why is there no uncertainty about the result? There would be, except we require require plaintexts to be smaller than the ...

5

Unless otherwise stated, $a$ is any integer representative of an eponymous element of $\mathbb{Z}_p$. \begin{align} a^3\equiv a\pmod p &\Longleftrightarrow a^3-a\equiv0\pmod p\\ &\Longleftrightarrow a\cdot(a^2-1)\equiv0\pmod p\\ &\Longleftrightarrow a\cdot(a-1)\cdot(a+1)\equiv0\pmod p\\ &\Longleftrightarrow\begin{cases} a\equiv0\pmod ... 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

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

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

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)

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

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

4

I believe you are being confused by what $k^{-1}$ means. It doesn't mean "interpret $k$ as a real number, plug it into a calculator, and hit the $1/x$ button". When we use the $k^{-1}$ notation, what we mean to say is that $a = k^{-1}$ is equivalent to saying that $a \times k = 1$. You will say "doesn't that mean doing exactly what a calculator does?". ...

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