Hot answers tagged

83

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


70

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


70

An ASN.1-encoded SSH private key contains the following integers in order: The public modulus $n$ and exponent $e$; The private exponent $d$; The prime factors $p$ and $q$ of $n$; The "reduced" private exponents $d_p=d\bmod(p-1)$ and $d_q=d\bmod(q-1)$; The "CRT coefficient" $q_{\text{inv}}=q^{-1}\bmod p$. The observation that the value of $d$ in such a ...


41

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


39

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 $Log(...


38

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


38

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


34

The answer is in the source, file sshrsag.c, line 9: #define RSA_EXPONENT 37 /* we like this prime */ This value $e=37$ matches the conditions for a reasonable fixed RSA public exponent: $e$ is odd, $e$ is at least $3$, $e$ is reasonably small. The later condition is good for speed of operations involving the public key (encryption, ...


30

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


29

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


29

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


28

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


27

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


27

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


24

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


24

Is this number specified anywhere? It was formally specified in this RFC as the 1536 bit MODP group (although its use predates that RFC). However, from what I've seen, the 2048 bit MODP group from that same document is actually more popular. Why was this particular number picked? Well, it's a safe prime; in addition, the leading 64 bits and the ...


23

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


23

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


23

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


23

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


22

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


22

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


19

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


19

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


18

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


18

Post-quantum security: As you note, quantum attacks are not known to break lattice-based cryptosystems. But some other proposals like McEliece, as well as most symmetric primitives are not known to be poly-time breakable on a quantum computer. Security from worst case assumptions: In security proofs for cryptosystems we typically assume that some problem ...


18

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


17

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


17

Asymmetric encryption and signing are entirely distinct concepts. The security and construction requirements are completely different. (Encryption for instance, needs to be an injection, whereas signature verification needs to be a surjection towards the verified message space. As a further hint of how they are intrinsically different, note that it lasted ...


17

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



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