# Tag Info

70

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

54

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

33

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

32

Surprisingly, very basic algorithms which the children learn at the basic schools are used. For instance: http://www.wikihow.com/Do-Long-Multiplication You can find a similar algorithm for sum, sub and division. Try to ask google for: "division on paper" The "power of" is little tricky. In cryptography you don't really need the "real power of". Instead ...

28

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

27

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

25

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

24

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

23

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

23

There are two reasons by which such "huge" numbers can be computed in reasonable time. The first one is that we do not raise one integer x to some big exponent d. What we do is that we compute x raised to power d modulo an integer n. The modulo means that we are not interested in the final integer xd but only in the remainder of the Euclidian division of xd ...

23

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

22

Textbook RSA: Choose two large primes $p$ and $q$. Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\varphi(n))=1$ (where $\varphi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\bmod{\varphi(n)}$. In other words, $d$ is the modular inverse of $e$, ($d\equiv e^{-1}\bmod{\varphi(n)}$). $(e, n)$ is the public key, $(d, n)$ the private one. To ...

21

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

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

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

20

When encrypting something with RSA, using PKCS#1 v1.5, the data that is to be encrypted is first padded, then the padded value is converted into an integer, and the RSA modular exponentiation (with the public exponent) is applied. Upon decryption, the modular exponentiation (with the private exponent) is applied, and then the padding is removed. The core of ...

19

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.

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

19

Actually, if you're willing to consider a somewhat larger $e$, I found a solution that makes the decryption part real cheap. This solution has $e = 446185741$ and $n = ... 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 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 ... 18 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 ... 18 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 ... 18 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 ... 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

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

17

The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). We can ...

17

This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed. Now, the first important thing to note is ...

16

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

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