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

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

15

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

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

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

12

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

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

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

11

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

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

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

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

What you suggest is valid. Here is a way to show it: In a fully implemented signature system (things are similar for asymmetric encryption), there are three modules: a key pair generator, which produces a pseudo-random key pair; a signature generator, which uses the private key to produce a signature over some piece of data; a signature verifier, which ...

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

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

9

GPG's (or OpenPGP's) public-key file encryption uses multiple steps: Generate a random session key encrypt the file using this random session key encrypt the random session key using the public key of the receiver (or using multiple keys in parallel, if the file is meant to be decrypted by multiple receivers). store the encrypted file together with the ...

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

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

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

9

There's an obvious solution using DH: Alice has a private key $a$ and a public key $g^a$; Bob has a private key $b$ and a public key $g^b$. When Bob sends a message, he computes the shared secret value $(g^a)^b$, converts that into a MAC key (possibly using a nonce to prevent key reuse), computes the MAC of the message, and sends the message and the MAC ...

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

What they are calling a "group cipher" is much more commonly referred to as proxy re-encryption. Proxy re-encryption is typically asymmetric but I don't think there is anything prohibiting it being symmetric. It has many applications (see this list) but most of these applications are using the asymmetric variants. I myself cannot point to another application ...

8

ElGamal encryption works like this: We work in a cyclic group $G$ of order $q$ (a prime integer), with $g$ being a generator. Here, we note the operation multiplicatively. For instance, we work with integers modulo $p$ (a big prime such that $q$ divides $p-1$) and $g$ is one of the $q$-th roots of $1$ modulo $p$. Private key is $x$, an integer modulo $q$. ...

8

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

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