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 ...
user avatar
  • 85.9k
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 ...
user avatar
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 ...
user avatar
21 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}...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
  • 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, ...
user avatar
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; ...
user avatar
  • 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?
user avatar
  • 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)^\...
user avatar
  • 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 ...
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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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?...
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 ...
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 ...
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 \...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
  • 133k
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 $...
user avatar
  • 125k

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