# Tag Info

133

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

123

In the first decade of the 21st 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 ...

98

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

85

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

85

It (or rather, the software running on it) will use arbitrary-precision ("bignum") arithmetic. The way this works is basically the same way in which you (probably) learned to do arithmetic on paper at school. The arithmetic taught to us humans at school is base-10 arithmetic — that is, we represent numbers as strings made up of ten different digits, ...

82

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

71

First things first, I would not have described BearSSL as being "bignum-free". However, it is true that it does not have a generic implementation of big integers; what it contains is a generic implementation (actually several) of big modular integers. And it matters. About low-level multiplications Software libraries run on some hardware and cannot use ...

62

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(p)... 60 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 ... 56 First, you do not break RSA through brute force. RSA is an asymmetric encryption algorithm, with a public/private key pair. The public key has a strong internal structure, and unravelling it yields access to the private key (basically, the main component of the public key is the modulus, which is a big composite integer, and the private key is equivalent to ... 55 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 ... 52 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 ... 52 Asymmetric encryption is vastly inferior to symmetric encryption. That is, in all respects, except one -- being asymmetric. When that property is needed, there's no way around it, obviously. Asymmetric encryption is much slower. It is much more susceptible to showing recognizable patterns of some kind given non-random input. You need much larger key sizes ... 49 Diffie-Hellman Key Exchange Problem: We have a symmetric encryption scheme and want to communicate. We don't want anybody else to have the key, so we can't say it out loud (or over a wire). Solution/Mechanics: We each pick a number, usually large, and keep it a secret, even from each other. I'll pick$x$, and you'll pick$y$. We agree on two more numbers,... 45 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 \... 40 I'm considering switching to ECDSA, would this require less space with the same level of encryption? The answer to that question is yes, both ECDSA signatures and public keys are much smaller than RSA signatures and public keys of similar security levels. If you compare a 192-bit ECDSA curve compared to a 1k RSA key (which are roughly the same security ... 39 I've never heard that RSA becomes less secure when the modulus grows. Obviously the strength doesn't grow as fast as the number of bits, but that only means that it grows sub-exponentially. If it keeps growing (without the growth going near zero) then there is no "trap". Check for instance here where the conclusion is that there is no exponential growth but ... 38 Those appear to be based on the complexity of the General Number Field Sieve, one of the fastest (if not the fastest) classical factoring algorithms. I confirmed this in Mathematica. Here is the complexity for the GNFS (source):$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$where$n$is a ... 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 ... 38 It just means that BearSSL was implemented without using any third-party bignum libraries. According to the BearSSL website: BearSSL's current implementation are less than optimal with regards to performance; they are in pure C, with only 32-bit multiplications. Better implementations shall be added in subsequent versions. Avoiding the use of external ... 37 The extended Euclidean algorithm is essentially the Euclidean algorithm (for GCD's) ran backwards. Your goal is to find$d$such that$ed \equiv 1 \pmod{\varphi{(n)}}$. Recall the EED calculates$x$and$y$such that$ax + by = \gcd{(a, b)}$. Now let$a = e$,$b = \varphi{(n)}$, and thus$\gcd{(e, \varphi{(n)})} = 1$by definition (they need to be coprime ... 37 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, and ... 36 Yes, (textbook) RSA works for any message$M \in \{0\dots n-1\}$, in the sense that the decryption procedure recovers the original message; that is$\left((M^e\bmod n)^d\bmod n\right)=M$. For this to hold, we need to assume$p\ne q$, a requirement not formally stated in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and ... 36 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 ... 35 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 ... 33 Copy / paste that key into http://phpseclib.sourceforge.net/x509/asn1parse.php and you'll see that there are several different integers in there.$p$is there,$q$is there as is the exponent and several other integers to speed things up by taking advantage of the Chinese Remainder Theorem. The key is encoded using DER and derives semantic meaning via ASN.1.... 33 The answer is "not safe". But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice. Google found one collision based on some existing, publicly known collision attacks on SHA-1. Sees the introduction of Google's paper for a complete list of prior work. First, let me briefly explain how RSA-SHA1 ... 32 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 ...

32

This question has many problems in the way it was asked, and clearly did not come after doing some investigation. However, since this seems to be a misconception that is spreading widely, I will relate to it. It is not true that the "crypto community" (whoever that is) believes that the NSA can break RSA. In fact, if Snowden taught us anything, it is that ...

30

The difference is subtle. DH is used to generate a shared secret in public for later symmetric ("private-key") encryption: Diffie-Hellman: Creates a shared secret between two (or more) parties, for symmetric cryptography Key identity: (gens1)s2 = (gens2)s1 = shared secret   (mod prime) Where: gen is an integer whose powers ...

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