Tag Info

Hot answers tagged

68

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


27

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


22

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


21

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


20

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


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

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


19

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


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

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


17

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


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

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

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


16

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


16

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


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

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


15

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


15

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


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


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$ $+1$s and the same number of $-1$s, 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

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


14

ECDSA is a digital signature algorithm ECIES is an Integrated Encryption scheme ECDH is a key secure key exchange algorithm First you should understand the purpose of these algorithms. Digital signature algorithms are used to authenticate a digital content. A valid digital signature gives a recipient reason to believe that the message was created by a ...


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



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