# Tag Info

42

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

34

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

26

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

26

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

23

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

21

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

17

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 $\... 17 Textbook / Plain RSA should not be used to encrypt messages directly. This is because the ciphertext is deterministic based on the message. Given an eavesdropped ciphertext$c_i$. An effective attack against your scheme would be: Obtain ciphertexts$c_0, ..., c_{26}$by encrypting integers 0-26 using the public modulus$n$and exponent$e$. For$j$in [0,26]... 15 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 ... 14$\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 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 ... 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 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-1de \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, ... 11 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? 11 Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python; def fast_power(base, power): result = 1 while power > 0: # If power is odd if power % 2 == 1: result = (result * base) % MOD # Divide the power by 2 power = ... 10 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 ... 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

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. I have no idea why Bernstein is being so abstruse. No cryptographer who would possibly be reading his paper would need a refresher on something as ubiquitous in that ...

9

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

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

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 $\... 8 A useful way to understand the extended Euclidean algorithm is in terms of linear algebra. (This is somewhat redundant to fgrieu's answer, but I decided to post this anyway, since I started writing this before fgrieu expanded their answer. Hopefully the slightly different perspective may still be useful.) Let's say we're trying to find the inverse of$e$... 8 If you want to reduce integers modulo that specific prime (and I assume you have checked whether$p = 2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$is prime or not), I would suggest you don't use the Solinas algorithms, but instead a different one geared towards modulii of the form$2^n - c$for small$c$. The identity underlying this operation is actually fairly ... 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