# Tag Info

63

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

47

In the first decade of the 21th century, and counting, on a given $\text{year}$, no RSA key bigger than $(\text{year} - 2000) \cdot 32 + 512$ bits has been openly factored other than by exploitation of a flaw of the key generator (a pitfall observed in poorly implemented devices including Smart Cards). This linear estimate of academic factoring progress ...

28

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

26

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

24

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

23

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

21

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

20

Collisions of RSA keys should never happen for realistic key sizes and good random number generators. Assume a 1024 bit RSA key; the primes from which it has been derived 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}$ ...

20

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

19

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

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

18

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

17

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

17

Yes, RSA works for any message $M \in \{0\dots n-1\}$, in the sense that the decryption procedure recovers the original message. In other words, $((M^e\bmod n)^d\bmod n)=M$. That is assuming $p\ne q$. That requirement is unstated in A Method for Obtaining Digital Signatures and Public-Key Cryptosystem, but true with overwhelming odds given the method ...

17

FIPS 186-3 tells you how they expect you to generate primes for cryptographic applications. It is essentially Miller-Rabin but it also specify what to do when you need extra properties from your primes.

17

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

16

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

15

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

15

Let's assume for an instant that you could build a large table of all primes. Then... what ? How would you use it ? What would you look up ? If you "just" scan the table and try to divide the number to factor by each prime, then this is known as trial division; there is no need to store the primes (they can be regenerated on-the-fly; that's the division ...

15

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 ... 14 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 ... 14 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 ... 14 Using$e\ne65537$would reduce compatibility with existing hardware or software, and break conformance to some standards or prescriptions of security authorities. Any higher$e$would make the public RSA operation (used for encryption, or signature verification) slower. Some lower$e$, in particular$e=3$, would make that operation appreciably faster (up to ... 14 Why is it common practice to create a hash of the message and sign that instead of signing the message directly? Well, the RSA operation can't handle messages longer than the modulus size. That means that if you have a 2048 bit RSA key, you would be unable to directly sign any messages longer than 256 bytes long (and even that would have problems, ... 13 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. 13 A second reason that a hash is usually present in RSA signature schemes (apart from being able to sign long messages) is to prevent existential forgery attacks. These look like this: Assume we have the public key$n$,$e$. Choose some random garbage$s$(smaller than$n$), and calculate$m = s^e \mod n$(i.e. "RSA encryption"). If you used "text book RSA ... 13 Mathematically it work just fine. "Encrypt" with the private key, "decrypt" with the public key. Typically, however, we say sign with the private key and verify with the public key. As stated in the comments, it isn't just a straight forward signing of the message$m$. Typically a hash function and padding is involved. Also, often one has a separate key ... 13$\phi(n)$is the order of the multiplicative group of the numbers in$\mathbb{Z}_n$.$\phi$is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element. So, using$\phi(n)$ensures that decryption works. Since$ed\equiv 1\bmod{\phi(n)}$, we can say ... 12 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 ...

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