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

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

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

Generally speaking, the public key and its corresponding private key are linked together through their internal mathematical structure; such keys are not "just" arbitrary sequences of random bits. The encryption and decryption algorithms exploit that structure. One possible design for a public key encryption system is that of a trapdoor permutation. A ...

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

There are three efficiency issues to discuss here: CPU, network bandwidth, and functionalities. The "moral" reason of public key encryption being slower than private key encryption is that it must realize a qualitatively harder feature: to be able to publish the encryption key without revealing the decryption key. This requires heavier mathematics, compared ...

18

There are some widely used cryptographic algorithms which need a finite, cyclic group (a finite set of element with a composition law which fulfils a few characteristics), e.g. DSA or Diffie-Hellman. The group must have the following characteristics: Group elements must be representable with relatively little memory. The group size must be known and be a ...

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

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

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 ... 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 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 ... 15 The best you can hope for is the following: You derive the password into a "big enough" (e.g. 128 bits) secret key K with a Key Derivation Function like PBKDF2. There are some details to be aware of (see below). You use the secret key K as seed for a Pseudorandom Number Generator. The PRNG is deterministic (same seed implies same output sequence) and ... 15 A Mersenne prime is a prime number that can be written in the form M_p = 2^n-1, and they’re extremely rare finds. Of all the numbers between 0 and 2^{25,964,951}-1 there are 1,622,441 that are prime, but only 42 are Mersenne primes. The second sentence is wrong. What they meant to say is that there are 1,622,441 numbers of the form they mentioned ... 14 The 1^k is a formalism that's only there to make the theoreticians happy. You can safely ignore it. When you actually implement the cryptosystem, you don't try to pass the string 1^k; instead, you pass k, the security parameter (a representation of how much cryptographic strength is desired from the key generation algorithm). I wish I could leave it ... 14 The likelihood of a decryption failure can be made arbitrarily small. IEEE P1363.1 says in appendix A.4.10: For ternary polynomials with d +1s and the same number of -1s, the chance of a decryption failure is given by [B30]:$$\operatorname{Prob}_{(q, d, N)}(\text{Decryption fails}) = P_{(d, N)} \left( \frac{q - 2}{6} \right) where ...

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

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

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

mpz_nextprime states in the documentation and source (file: mpz/nextprime.c) that it simply finds the next prime larger than the provided input. There are various methods of doing so (depending on how efficient it tries to be), but they should all produce the same answer. Looking at the code, mpz_nextprime first tests a number against a large quantity of ...

13

Say you encrypt a message with a key $k$. With symmetric encryption (ie. symmetric ciphers), $k$ must be secret. The sender and recipient must agree (somehow) on $k$. No-one else can be allowed to find out $k$. Anyone else who finds out $k$, can decrypt all the messages encrypted with $k$. For that reason, symmetric ciphers are often called "secret key" ...

13

A lot of answers have said "a mathematical structure" which is absolutely right, but I still see there might be a question: how on earth can one exist? I'll try and fill that gap at a simpler level. So a simple caeser-shift cipher might look like this: $x+7$. In our really simplistic, dangerous example, the "key" here is $7$. If I have some encrypted text, ...

13

Yes, a computationally unbounded attacker can break any public key system. One easy way to see this is to consider the KeyGen algorithm, which takes takes as input a value R (which in normal use is the output of some random number generator), and outputs a public key PK and a private key SK. Now, what a computationally unbounded adversary can do is ...

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

There are two main reasons why asymmetric cryptography is practically never used to directly encrypt significant amount of data: 1) Size of cryptogram: symmetric encryption does not increase the size of the cryptogram (asymptotically), but asymmetric encryption does. If we take the example of RSAES-OAEP in PKCS#1v2 with a 1024-bit key and 160-bit SHA-1 ...

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

12

That's not quite correct. In SSL, two things happen: First, a session key is negotiated using something like the Diffie-Hellman method. That generates a shared session key but never transmits the key between parties. Second, that session key is used in a normal symmetric encryption for the duration of the connection. SSL does use public/private in one ...

12

Actually, for most applications where we want to use asymmetric encryption, we really want something a bit weaker: key agreement (also known as "key exchange"). When RSA or ElGamal is used for that, one party selects a random string, encrypts it with the public key of the other party, and the random string is used as a key for classical symmetric encryption. ...

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