38

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


38

I've never heard that RSA becomes less secure when the modulus grows. Obviously the strength doesn't grow as fast as the number of bits, but that only means that it grows sub-exponentially. If it keeps growing (without the growth going near zero) then there is no "trap". Check for instance here where the conclusion is that there is no exponential growth but ...


23

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


23

I don't understand at all what this claim is on the website. The claim that RSA becomes very expensive for large $N$ is true, but to say that the gap between encryption/decryption cost and factoring goes down makes no sense at all! The function describing the running time of the best factoring algorithms is clearly asymptotically larger than $n^3$ (the time ...


22

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


22

I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject ...


18

A boring method is to carefully apply the (partially) extended Euclidean algorithm. But in the question, the modulus is a power of two (specifically $2^6$), and we can use that $$a\,x\equiv1\pmod{2^k}\implies a\,x\,(2-a\,x)\equiv1\pmod{2^{2k}}$$ from which it follows this fact: if the modular inverse of $a$ modulo $2^k$ is (the lower $k$ bits of) $x$, ...


15

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


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

I'll use these common definitions and notations: $a\equiv b\pmod c$ means that $c>0$ and $c$ divides $b-a$ $a\equiv b^{-1}\pmod{c}$ means that $a\cdot b\equiv 1\pmod{c}$ $a=b\bmod c$ means that $a\equiv b\pmod{c}$ and $0\le a<c$ $a=b^{-1}\bmod c$ means that $a\equiv b^{-1}\pmod c$ and $0\le a<c$ $\varphi$ is the Euler totient function (also noted $\...


12

RSA encryption and decryption is built upon Euler's theorem which says that $a^{\phi(n)} \equiv 1 \pmod n$, and since $p$ and $q$ are primes, $\phi(pq) = (p-1)(q-1)$. If we have message $M$, modulus $n$, private exponent $d$ and public exponent $e$, RSA encryption works like this: Encryption: $C = (M^e \bmod n)$ Decryption: $M' = (C^d \bmod n)$, which ...


12

A modular operation is an operation done modulo some modulus. "modular" is an adjective: modular inverse, modular operation, modular reduction, ... "modulo" is indeed the Latin ablative of modulus, and that makes it an adverb: I walk modulo $n$, just like I walk fast. "modulus" is a noun: the number $n$ is the modulus that you would use in some system.


11

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


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

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


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


10

I suppose there is really no requirement to have $a <b$. But then again, if you are using an $a>b$ why not reduce it modulo $b$ and save space?


10

The sum of two words with carries suppressed is just a convoluted way of saying XOR. You don't need to implement any kind of complicated summation operation. Just perform a bitwise-exclusive OR. See also https://en.wikipedia.org/wiki/Exclusive_or#Computer_science


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

The security of $\varphi$ and $\lambda$ should be equivalent since they are mathematically equivalent in the context in which they are used. (That is: the $d´$th power in $(\mathbb Z/pq \mathbb Z)^\times$ is exactly the same operation as the $d$th power.) However, the mathematically right modulus for computing $d$ is $\lambda(pq)$: it is precisely the ...


8

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)


8

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


8

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


8

Let $x\in\mathbb Z/p\mathbb Z$ be the point's first coordinate, and define $z := x^3+ax+b$. We know that there exists a square root $y\in\mathbb Z/p\mathbb Z$ of $z$, i.e. $y^2=z$. Let's assume we have already found such an $y$. Since the order of $(\mathbb Z/p\mathbb Z)^\ast$ is $p-1$, Lagrange's theorem implies $y^p=y\text,$ hence $$\left(z^{(p+1)/4}\right)...


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


8

As the comment you quote notes: On some platforms, including Intel, the [modulo] operation can take a smaller number of cycles if the input is "small". Is that really true, and what does that mean? A bit of Googling led me to the Intel® 64 and IA-32 Architectures Optimization Reference Manual, which in table C-16 lists the throughput of the DIV ...


8

I'm not very good at reading Lisp, so please correct me if I'm wrong, but it looks as if you're naïvely calculating $a^{n-1} \bmod n$ by first raising $a$ to the $n-1$ -th power, and then reducing the result modulo $n$. This is a very inefficient way to implement modular exponentiation since, as you've noticed, the intermediate result $a^{n-1}$ can quickly ...


8

The best way to approach problems like this is to start by assuming that a simple solution exists. That assumption might be wrong, of course, but: since this is a textbook problem, it probably does have a relatively simple solution that you should be able to figure out based on what you've learned, and even if that wasn't the case, you should still at ...


8

Yes, it's broken. Here is the approach I see: $$p = \text{gcd}( n, r^e - r \bmod n)$$ with quite high probability, for random $r$. This happens because $e \equiv 1 \bmod p-1$, and hence $r^e \equiv r \pmod p$ (for any $r$). It is unlikely that $r^e \equiv r \pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.


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