43 votes
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 ...
Maarten Bodewes's user avatar
  • 92.6k
26 votes

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 ...
Yehuda Lindell's user avatar
23 votes

How to determine the multiplicative inverse modulo 64 (or other power of two)?

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}...
fgrieu's user avatar
  • 141k
23 votes
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 ...
Thomas Pornin's user avatar
20 votes
Accepted

Must RSA exponent and modulus be odd

If the modulus is even, that means one of its factors is 2. The modulus is supposed to be the product of two large prime numbers. While it's possible to use more than two prime factors (called multi-...
forest's user avatar
  • 15.3k
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 ...
Wilson's user avatar
  • 929
13 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; ...
kelalaka's user avatar
  • 48.5k
13 votes

Must RSA exponent and modulus be odd

In the context of RSA, the modulus should be a product of two large primes, and all primes $>2$ are odd — so it's not a restriction in this situation. The reason the implementation only works with ...
yyyyyyy's user avatar
  • 12.1k
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, ...
Ruben De Smet's user avatar
12 votes
Accepted

Intentionally craft a 180 to 255 bits Integer that bypass this miller‑rabin test with having a known factor

If your Miller-Rabin tests are being computed for random bases, then there is very little chance as at least seventy-five per cent of possible bases will fail for any given modulus. If the bases of ...
Daniel S's user avatar
  • 23.9k
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?
Guut Boy's user avatar
  • 2,877
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 ...
Henrick Hellström's user avatar
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 ...
forest's user avatar
  • 15.3k
9 votes
Accepted

Discrete Logarithm: What does it mean to find the discrete logarithm of $a$ to base $g$ modulo $p$?

Discrete Log for arbitrary Groups: Discrete Log can be defined in arbitrary groups and some groups can have an easy solution (powers of 10) and some can have a hard solution. Let $G$ be any group and $...
kelalaka's user avatar
  • 48.5k
9 votes
Accepted

Concrete example of Montgomery Multiplication

In this answer we study modular multiplications using Montgomery arithmetic, illustrated with the example $7510\cdot 8431\cdot 2143\bmod9137$, working in base $\beta=10$ because the question does. ...
fgrieu's user avatar
  • 141k
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 ...
Ilmari Karonen's user avatar
8 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 ...
fgrieu's user avatar
  • 141k
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?...
Ilmari Karonen's user avatar
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 ...
Ilmari Karonen's user avatar
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 ...
Ilmari Karonen's user avatar
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 \...
poncho's user avatar
  • 147k
7 votes
Accepted

Factoring large $N$ given oracle to find square roots modulo $N$

What I have come up with till now is, first call algorithm $S$ on some number to find a square root $a$. Call it repeatedly until I get $b$ which is not of the form $a\equiv\pm b\pmod N$. Repeat this ...
yyyyyyy's user avatar
  • 12.1k
7 votes

Do equivalent RSA keys exist?

The formula at the heart of RSA is: $$x^{\lambda(n)} = 1 \pmod n$$ where $\lambda$ is the Carmichael function. In the case of two-prime RSA it's $\operatorname{lcm} (p - 1, q-1)$. $$m^{k \cdot \...
CodesInChaos's user avatar
  • 24.9k
7 votes

How do you make Fermat's primality test go fast?

You don't need to explicitly calculate $a^{m-1}$. Observe that $a^{2k} =(a^k)^2$ and that $a^{2k+1} = a \cdot (a^k)^2$. This suggests a simple recursive function $\phi(k)$ to determine $a^k$ modulo $...
quicksort's user avatar
  • 171
7 votes
Accepted

Why does AES use a Binary Field?

Well, there would be two possible ways to use modular arithmetic: You could do the arithmetic modulo $2^n$. However, that has some nasty properties (not all elements have multiplicative inverses, ...
poncho's user avatar
  • 147k
7 votes
Accepted

Paillier paper: Number Theoretic Lemma doesn't seem to work

Short answer: This appears to be an error in the paper, but it's not a problem in practice. The proof of Lemma 3 uses the following implication: Since $\gcd(\lambda,n)=1$, $x_2-x_1$ is necessarily ...
yyyyyyy's user avatar
  • 12.1k
7 votes
Accepted

Discrete logarithm weak group

Is there any better algorithm ? Actually, your second algorithm (select a small set of primes $\{ 2, q_1, q_2, ..., q_n \}$ and check if $\ 2q_1 q_2 ... q_n + 1$ is prime) is quite efficient. You ...
poncho's user avatar
  • 147k
7 votes

Is encrypting every number separately using RSA secure?

With appropriate padding (such as OAEP), using RSA to encrypt individual bytes or characters or even bits is indeed secure*. Of course it's also incredibly wasteful, as you're turning every 8 bits of ...
Ilmari Karonen's user avatar
6 votes

Constant time multiplicative inverse within a word

This answers the original question in the particular case of $p=2^{64}$. It quickly computes the modular inverse of any odd 64-bit integer, hopefully on any compilers with 64-bit support conforming to ...
fgrieu's user avatar
  • 141k
6 votes

Constant time multiplicative inverse within a word

You can compute $f(x) = x^{\phi(p)-1} \bmod p$ in constant time, using $O(\log p)$ constant time modular multiplies. If $p$ is prime, this reduces to $f(x) = x^{p-2} \bmod p$ BTW: calling it 'Knuth'...
poncho's user avatar
  • 147k

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