# Tag Info

22

RSA was there first. That's actually enough for explaining its preeminence. RSA was first published in 1978 and the PKCS#1 standard (which explains exactly how RSA should be used, with unambiguous specification of which byte goes where) has been publicly and freely available since 1993. The idea of using elliptic curves for cryptography came to be in 1985, ...

20

The public key blob doesn't consist of just the numbers that make up the public key: it begins with a header that says “this is an SSH public key”. The repeated prefix encodes this header. RFC 4254 specifies the encoding of public key in SSH key format. The "ssh-rsa" key format has the following specific encoding: string "ssh-rsa" mpint e ...

18

The solution to this problem is to use hybrid encryption. Namely, this involves using RSA to asymmetrically encrypt a symmetric key. Randomly generate a symmetric encryption (say AES) key and encrypt the plaintext message with it. Then, encrypt the symmetric key with RSA. Transmit both the symmetrically encrypted text as well as the asymmetrically encrypted ...

18

You don't use a pre-generated list of primes. That would make it easy to crack as you note. The algorithm you want to use would be something like this (see note 4.51 in HAC, see also an answer on crypto.SE): Generate a random $512$ bit odd number, say $p$ Test to see if $p$ is prime; if it is, return $p$; this is expected to occur after testing about ...

17

By definition you cannot encrypt values greater than the modulus in RSA, because the plaintext is immediately reduced modulo $n$ which loses information. This is because textbook RSA works in the $\mathbb{Z}/n\mathbb{Z}$ congruence ring, so from RSA's point of view, as long as two values have the same remainder modulo $n$, they are effectively equivalent. So ...

15

No, because it doesn't work that way. Careful how you use 'cracked'. The theory is that you can bust open a particular encrypted message faster using a quantum computer. But the way you worded this question implies that a little time on one quantum computer will make the encryption scheme invalid everywhere. Quantum computers aren't believed to be able to ...

15

First I must state that a secure RSA encryption must use an appropriate padding, which includes some randomness. See PKCS#1 for details. That being said, $d$ is the "private exponent" and knowledge of $d$ and $n$ is sufficient to decrypt messages. $n$ is public (by construction) so $d$ must be kept private at all costs. If it is very small then an attacker ...

14

The standard way to generate big prime numbers is to take a preselected random number of the desired length, apply a Fermat test (best with the base $2$ as it can be optimized for speed) and then to apply a certain number of Miller-Rabin tests (depending on the length and the allowed error rate like $2^{-100}$) to get a number which is very probably a prime ...

14

No, it is not at all feasible to build an index of prime factors to break RSA. Even if we consider 384-bit RSA, which was in use but breakable two decades ago, the index would need to include a sizable portion of the 160 to 192-bit primes, so that the smallest factor of the modulus has a chance to be in the index. Per the Prime number theorem there are in ...

14

From the definition of the totient function, we have the relation: $$\varphi{(n)} = (p - 1)(q - 1) = pq - p - q + 1 = (n + 1) - (p + q)$$ It then easily follows that: $$(n + 1) - \varphi{(n)} = p + q$$ $$(n + 1) - \varphi{(n)} - p = q$$ And you know from the definition of RSA that: $$n = pq$$ Substituting one into the other, you can derive: n = p ...

13

Theoretically you can do encryption of long messages with RSA, in the same way that you can encrypt a long message with a block cipher. This requires an appropriate chaining mode, e.g. CBC: each plaintext "block" is first XORed with (part of) the encrypted previous block. With RSA and proper padding, there is a per-block size overhead. Namely, with the ...

12

Both RSA and Diffie-Hellman work with modular exponentiation. But they work in a different way: In RSA, there are two exponentiations which invert each other, i.e. we have $e$ and $d$ such that $(x^e)^d \equiv x$ for all $x$. E.g. if $\square^e$ is the encryption, $\square^d$ is the corresponding decryption. To create this pair of $e$ and $d$ (or derive one ...

12

The users will be able to read each other's messages (even though they can have different private keys, say $d_1$ and $d_2$). This is because knowledge of $d_i$ is sufficient to factor $N$, thus allowing that party to compute the other party's private key. This was detailed by Boneh in his analysis of RSA attacks.

11

To walk you through RSA from start to end, here's how it works. Choose two large distinct primes $p$, $q$. Calculate $n=pq$. Calculate $\phi(pq)$. This happens to be $(p-1)(q-1)$. Choose $e$ such that $gcd(e, \phi(pq)) = 1$ and $1 < e < \phi(pq)$. Compute $d$ such that $de = 1 \mod \phi(pq)$. Do some crypto; $c = t^e \mod n$ and $t = c^d \mod n$. ...

11

Yes, RSA 'works' for any message $M \in [0..n-1]$, in the sense that the decryption procedure recovers the original message; or in other words $((M^e\mod n)^d\mod n)=M$. An easy proof is to consider $Z=(M^e)^d -M$; show $Z\equiv 0\pmod{p}$ and $Z\equiv 0\pmod{q}$; from which it follows that $Z\equiv 0\pmod{n}$. Note: in general, $M^e\equiv M\pmod{n}$ does ...

11

Two properties of RSA are important here: If you know $p$ and $q$, you can reverse RSA encryption for arbitrary $e$ If you know $e$, $d$ and $n$ you can efficiently factor $n$, and obtain $p$ and $q$. This means if you know one private key for a given $n$, you know all of them. Thus different persons should not share a modulus. Such a scheme can be ...

10

RSA has not been cracked. No one has demonstrated practically viable computing that's anywhere in the realm of breaking RSA. There is no reason to change any of your practices. The first thing to understand is that D-Wave has a long history of repeatedly making bogus claims to the popular press. Experts in quantum computing have been criticizing and ...

10

Computational cost of RSA with keys of length $n$ bits is roughly $O(n^2)$ for public key operations (encryption, signature verification), and $O(n^3)$ for private key operations (decryption, signature generation). So RSA with a million-bit key will be roughly one billion times slower than RSA with 1024-bit keys (for the private key operations); the latter ...

10

Yes, there is a practical attack. Leaking those (or even just one of those) allows us to factor the modulus quite efficiently. Suppose the attacker knows the values $n$, $e$ (the public exponent) and the value of $d \bmod (p-1)$ (which we will call $dp$). Then, the attacker selects a value $m$, and then computes: $gcd( n, m ^ {e \cdot dp-1} - 1 \bmod n)$ ...

10

I recommend that you stick with the standard padding methods, even in your scenario. Here's one reason, if your 'random password' consists only of the AES key, and you use the raw RSA operation on it (that is, zero pad it to the size of the RSA modulus, and then compute $M^e \bmod N$), then yes, there does exist weaknesses; there's a meet-in-the-middle ...

9

If there is a vulnerability in encrypting a RSA private key with the corresponding public key, when the private key is password-protected, then it mechanically implies a vulnerability in the password-based protection scheme: if an attacker gets a copy of the password-encrypted key (without the password), he can encrypt it with the public key himself; so an ...

9

In any public key system, you don't encrypt with private key. You encrypt with public key, or sign with private key. If your goal is signing (resp. encrypting) one small value with the RSA private (resp. public) key, keeping the signature small: forget about it, that's not directly possible. Under RSA, a cryptogram is always of size at least comparable to ...

9

This is mostly a supplement to @ThomasPornin's answer, not a complete answer on its own (but too long to fit in a comment). ECC uses a finite field, so even though elliptical curves themselves are relatively new, most of the math involved in taking a discrete logarithm over the field is much older. In fact, most of the algorithms used are relatively minor ...

9

A signature algorithm operates over a sequence of bits -- any sequence of bits. The meaning you may want to attach to these bits is totally none of the business of the signature algorithm. It is supposed to be handled at some other level. Basically you want to attach some meta-data to the signed object, and have that meta-data signed as well. The usual ...

9

Wiener's result has been improved several times, and it is hard to tell how big the private exponent must be to be safe from further progress. Also, the proposed technique, assuming $d>n^{1/3}$, requires a minimum of ${1\over3}\cdot log_2(n)$ modular multiplications for the sparsest $d$ conceivable (a power of two), compared to say ${7\over6} \cdot ... 9 For realistic key sizes and good random number generators collisions of RSA keys never happen. For example assume a 1024 bit RSA key. The primes from which it comes are about 512 bit. If we assume every 500ths 512 bit number is a prime, and we assume the most significant bit of the 512 bit number is set, we still get about$2^{500}$or$10^{150}$different ... 9 The main difference is that Pohlig-Hellman is a symmetric cypher, while RSA is a public key system. This is because, with Pohlig-Hellman, anyone who knows the encryption key$e$can compute the inverse operation (because the 'decryption' key$e^{-1} \bmod p-1$is easy to compute), while the RSA, someone who knows the encryption key$e\$ (but not the ...

8

There are several kinds of asymmetric cryptographic algorithms. All use some sort of mathematical structure, but not the same, and not all involve prime integers. RSA is the most well-known asymmetric algorithm, which includes several variants (e.g. for asymmetric encryption or for digital signature). In a RSA public key, there is a big integer called the ...

8

After contacting D-Wave and asking them the implications of their quantum computer against RSA, they responded that they had not cracked RSA for the following reasons: Short answers: Q. Is RSA effectively cracked by your quantum computer A. No. Q. Should our customers be concerned that companies with quantum computers are intercepting our encrypted ...

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