# Tag Info

18

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

15

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

13

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

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

12

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

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

10

Breaking such a scheme is easy. Suppose Alice wants to transmit a message $M$ to Bob. First thing, Alice picks an integer $R_a$ and sends the cipher text $C_a = M \times R_a$ to Bob. Bob then picks another integer $R_b$ and transmits $C_b = C_a \times R_b$ back to Alice. Alice calculates $D_a = \frac{C_b}{R_a}$ and sends $D_a$ to Bob. Bob calculates $D_b = ... 9 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 ... 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 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$p$... 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 more ... 9 If your calculator is able to compute$n^2$, you can compute$m^e \bmod n$using the binary exponential method. In this method, you should first compute the binary form of$e$. Let$\ell$be the number of bits in$e$, and let$e_i$denote the$i$-th bit of$e$, so that$e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$. Now, with the algorithm below, you can compute ... 8 Very easy, you just use the Extended Euclidean Algorithm to compute$a^{-1} \pmod p$. Then you have$b \equiv ca^{-1} \pmod p$. Note that, because the EEA has polynomial complexity, this remains easy even if$p$is very large (e.g., tens of thousands of bits). 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. ... 7 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. 7 Mathematically speaking, there is no upper bound on the private exponent in RSA: assuming$d$is a valid private exponent, then the valid exponents are the set of$d'=d+k\cdot\lambda(p\cdot q)$with$k\in\mathbb Z$, where$\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$since$p$and$q$are distinct primes; this set is unbounded. If you compute$d$as an ... 7 If$d$is a valid RSA decryption exponent, then so is$d \pm k \lambda(pq)$for any integer$k$. As a corollary, we may always choose the decryption exponent to lie in the range$0 < d < \lambda(pq)$. In fact, there's generally no reason to choose the decryption outside that range: a larger exponent would just make decryption slower, while using a ... 7 Claim: If$A$and$Bare coprime, the map \begin{align*} \{0,\dots,B-1\}\ &\to\ \{0,\dots,B-1\} ,\\ x \ &\mapsto\ A\cdot x\bmod B \end{align*} is a well-defined bijection. It is clear directly from the definition of\bmod$that$A\cdot x\bmod B$is indeed between$0$and$B-1$. Surjectivity follows, e.g., from Bézout's lemma. Any surjection ... 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$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 ... 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}\ \pmod{35}... 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 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 the ... 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 When choosing the public exponent e, if the value chosen is the first coprime after \phi(n)/2 then the resulting public and private exponents are equal. Well, yeah, that'll always be true. Why does this happen? We have e=d whenever we have both of the following true:$$e^2 \equiv 1 \pmod{p-1}e^2 \equiv 1 \pmod{q-1}$$Now, if$e = (...

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