# Tag Info

45

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

23

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

21

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

21

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

19

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

18

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

17

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

17

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

16

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

15

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

15

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

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

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

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

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

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

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

11

Textbook RSA: Choose two large primes $p$ and $q$. Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\phi(n))=1$ (where $\phi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\mod\phi(n)$. $(e, n)$ is the public key, $(d, n)$ the private one. To encrypt a message $m$, compute $c\equiv m^e\mod n$. To decrypt a ciphertext $c$, compute $m \equiv ... 11 Firstly, a number theory textbook might well help here. I own An Introduction to the theory of numbers which will give you a grounding in this and many other number theory topics which crop up in crypto. It's not my favourite book notation-wise, but in terms of topics covered it is very thorough. Now, on to what you need help with. There exists a theorem ... 11 You might want to look at NIST SP800-57, section 5.2. As of 2011, new RSA keys generated by unclassified applications used by the U.S. Federal Government, should have a moduli of at least bit size 2048, equivalent to 112 bits of security. If you are not asking on behalf of the U.S. Federal Government, or a supplier of unclassified software applications to ... 11 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 ... 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 ... 11 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 ... 11 I thought about this and done a bit of research and the answer is no. The problem is the gap between the difficulty of factorisation versus prime generation isn't really large enough at the scale of primes/moduli we can work with. By 1588 the largest prime discovered was 524287 and that was due to Pietro Cataldi. This was a prime generated by a single ... 10 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 ... 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 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

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

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