Tag Info

Accepted

Why is it not possible to increase the size of RSA keys indefinitely?

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 ...
• 85.9k

Why is it not possible to increase the size of RSA keys indefinitely?

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

How to avoid side channel attacks when handling large numbers?

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 ...
• 84.8k
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}... • 125k 17 votes Accepted lcm versus phi in RSA 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\... • 125k 17 votes Accepted Is encrypting every number separately using RSA secure? 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 ... • 318 12 votes Accepted How is information disclosed by modular multiplication? 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 \... • 133k 12 votes Accepted How to use "mod" related words in technical paper？ 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, ... • 2,153 12 votes Accepted Efficient function/algorithm/method to do modular exponentiation Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python; ... • 43.5k 11 votes Accepted Does the prime modulus have to be bigger that the generator? 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? • 2,857 10 votes lcm versus phi in RSA 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)^\... • 11.2k 10 votes Accepted Public key crypto without modular arithmetic? 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 ... • 10.2k 10 votes Accepted Salsa20 Implementation: Sum of 2 Words with Carries Suppressed 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 ... • 13.5k 9 votes Accepted RSA with modulus n=p²q 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, ... • 133k 9 votes Accepted Exactly two of the four roots must be greater than N/2 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 ... • 7,338 9 votes Point decompression on an elliptic curve 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 ... • 11.2k 9 votes Random Galois fields 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 ... • 2,626 8 votes Calculating RSA private exponent when given public exponent and the modulus factors using extended Euclid 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 ... • 44.5k 8 votes How hard to solve the given mod problem 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 ... • 7,914 8 votes Accepted Adding a number congruent to 0 to ensure that the mod operation takes a constant number of instruction cycles 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?... • 44.5k 8 votes How do you make Fermat's primality test go fast? 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 ... • 44.5k 8 votes How can I determine if a hash function is secure? 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 ... • 44.5k 8 votes Accepted RSA given d and d = p 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 \... • 133k 7 votes Calculating RSA private exponent when given public exponent and the modulus factors using extended Euclid The method in the other answer is didactic, but requires backtracking earlier calculations, and thus having kept these or use of recursion, which is undesirable in constrained environments as often ... • 125k 7 votes Accepted In RSA, why does$p$have to be bigger than$q$where$n=p \times q$? 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 ... • 3,820 7 votes Accepted Addition / Multiplication modulo 13$\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 ... • 84.8k 7 votes Accepted What are the computational benefits of primes close to the power of 2? After a multiplication you have a number with$2 \cdot 255$bits. Since$2^{255} = 19 \pmod q$, you can take the upper half, multiply it by 19 and add it to the lower half. This gives you an ... • 24.1k 7 votes Accepted How to calculate RSA CRT parameters from public key and private exponent The first (and hardest) step is to factor$n$; the easiest way to do this (given$e$and$d$) is with this randomized procedure: Select a random value$z$from the range$(2, n-2)$Compute the value$...
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 \$...