# Tag Info

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

13

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

11

Summary: Montgomery only aims at modest (if any) speedup compared to classic algorithms; it is popular for other reasons. Karatsuba allows large speedups for very large parameters, but the threshold where it becomes beneficial is often not reached in cryptographic applications. The techniques can be used together. Montgomery arithmetic is used for ...

11

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

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

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

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

9

Can an attacker learn some bits of a using this information? No. In the case of multiplication modulo a prime, we have, for any possible value of $a$, there is a unique value of $b$ that makes $a \cdot b \bmod p$ give any particular value of $c$ in the range $(1, p-1)$. That is, even if we knew all the bits of $c$, no particular value of $a$ are any ...

7

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

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

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

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

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

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 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: An interesting special case is perfect security: an encryption ... 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 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 ... 6 GF(2^8) or \mathbb F_{2^8} can also be viewed as the vector space \mathbb F_2^8 of 8-bit vectors (or bytes) over GF(2) or \mathbb F_2. Suppose \{\beta_0, \beta_1, \cdots, \beta_7\} is a basis of \mathbb F_2^8 over \mathbb F_2, that is, the sum$$a_0\beta_0 \oplus a_1\beta_1 \oplus \cdots \oplus a_7\beta_7, ~ a_i \in \mathbb F_2$$equals ... 6 It does not; the equation holds for any element g. The fact that g is a generator means only that every element of the group can be obtained a key. This is not at all necessary for the protocol. 5 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 ... 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 ... 5 \mathbb{Z}^*_{13} is a group with 12 elements, not 13. A group is defined by a set of elements, and a "law". The law combines two elements and yields a third one within the set. You get a group if the law fulfils some properties (the law is associative, there is a neutral element, each element has an opposite in the group). \mathbb{Z}_{13} is a group ... 5 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 ... 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

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)

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