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 ...
- 91.2k
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 ...
- 27.5k
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 ...
- 86.4k
22
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}...
- 137k
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-...
- 15k
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\...
- 137k
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 ...
- 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;
...
- 46.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 ...
- 11.9k
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,290
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,867
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.9k
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.4k
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 ...
- 15k
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 ...
- 45.7k
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 ...
- 137k
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 ...
- 8,072
8
votes
Is there an upper bound to the private exponent in RSA?
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 < \...
- 45.7k
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?...
- 45.7k
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 ...
- 45.7k
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 ...
- 45.7k
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 \...
- 143k
8
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 $...
- 46.5k
8
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. ...
- 137k
7
votes
Is there an upper bound to the private exponent in RSA?
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 $...
- 137k
7
votes
Modular exponentiation on calculator for textbook RSA
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 ...
- 2,323
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 \...
- 24.7k
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 $...
- 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, ...
- 143k
Only top scored, non community-wiki answers of a minimum length are eligible