# Tag Info

67

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

37

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

28

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

17

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

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as: \begin{align} N&=p\cdot q\\ d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\ d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\ ... 14 Anye$such that$\gcd(e, (p-1)(q-1)) = 1$will do. There is no need for it to be in the set$\{3,17,65537\}$; these last numbers are chosen for speed of encryption, mostly (two set bits leads to faster computation of modular exponentation), and these numbers happen to be prime, so the condition is easily checked. One often encounters other$e$, but many ... 13 Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key. The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve): The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good. He ... 12 You can use a seed to start a PRNG. Then you can use that PRNG to generate the two (or more) primes required to generate the key pair. Now if you save that seed you can regenerate the key pair, which means you don't have the store the modulus, CRT components or private exponent. So yes, it is possible to reduce the size, but this approach does have ... 12 The security level of an elliptic curve group is approximately$\log_2{0.886\sqrt{2^n}}$. You can use this to approximate the security level of a$n$-bit key, eg:$\log_2{0.886\sqrt{2^{571}}} = 285.32537860389294$The real computation (at least for curves over a finite field defined by a prime$p$) is$ \log_2{\sqrt{\pi/4}\sqrt{ℓ}} $, where$ℓ$is the ... 11 It is feasible to generate 300 million public key pairs of reasonable strength in 8 hours on a single computer, easily with ECDSA using a single core/thread, and even with DSA using quite a common multi-core computer. RSA would require many standard computers (baring hardware accelerators for modular exponentiation), assuming all the public keys are made ... 11 First of all, yes, the message digest is the hash of the message. Secondly, do not mix things up. You are talking about public key encryption and signature. Let's redefine them to make sure we have everything right. Alice and Bob got pairs of key ($A_{pub}$,$A_{priv}$), ($B_{pub}$,$B_{priv}$). Alice knows$B_{pub}$and Bob knows$A_{pub}$. Alice wants ... 10 Breaking such a scheme is easy. Suppose Alice wants to transmit a message$M$to Bob. First thing, Alice picks an integer$R_a$and sends the cipher text$C_a = M \times R_a$to Bob. Bob then picks another integer$R_b$and transmits$C_b = C_a \times R_b$back to Alice. Alice calculates$D_a = \frac{C_b}{R_a}$and sends$D_a$to Bob. Bob calculates$D_b = ...

8

The use of the AES key many times is not a problem. However, there is a fundamental flaw with your solution. The server has no way of validating that it received the client's authentic public key. In particular, a man-in-the-middle can capture the client's public key, can forward its own public key to the server, and can then decrypt all traffic sent by each ...

8

For RSA, the answer whether it is feasible for a single computer depends on the reason your generating them (and specifically, whether they need to remain secure if you publish a number of them). For example, if you're generating the RSA keys to search for some criteria (e.g. the hash of the public key has a specific pattern), and you'll discard the ones ...

8

You are looking at the ASN.1 encoding of private (and public) keys; the 00 values you see are an artifact of how ASN.1 encodes integers. ASN.1 is a method for describing data structures, and has ways to represents all sorts of data types. It wasn't designed with public keys (or cryptography) in mind; it was intended for more general use, initially ...

8

If your calculator is able to compute $n^2$, you can compute $m^e \bmod n$ using the binary exponential method. In this method, you should first compute the binary form of $e$. Let $\ell$ be the number of bits in $e$, and let $e_i$ denote the $i$-th bit of $e$, so that $e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$. Now, with the algorithm below, you can compute ...

7

I work for Security Innovation, which owns the NTRU patents. All NTRU-related patents are freely usable under GPL 2.0 and 3.0 -- in other words, they should fit in with your license requirement as given above. If you have specific license requirements beyond GPL please let me know and we'll accommodate them if we can. There's an open-source C and Java ...

7

Yes, it is possible to determine with some certainty which public key in some known set was used to produce RSA ciphertexts made with the same key in this set, given enough ciphertexts, and if neither the public moduli nor the random padding are made with intend to hide which public key was used. Assume that the set of $k$ public keys have public moduli ...

7

There is a method known as "Complex Multiplication". However, it is not simple at all, and tends to be overly expensive for most target orders. See this article for some details. There is also the (theoretical) concern that a curve constructed that way may have a special structure though could possibly be leveraged into an attack one day; generally speaking, ...

6

Decoding information within a time frame is of absolute importance. Say X is an terrorist, the information of his attack will be useful today, not years after the attack has happened. And similarly decoding your message is important today, not years later. Also there might be a possibility that when somebody has decoded your key for future use, you might ...

6

First, let me address the assumption that private keys will be found in a few years using a fast computer. Unless there are serious algorithmic improvements in the cryptanalysis of a scheme, this simply is not true. Of course, the length of the key is of importance, and if you need security for the far future then you should be using 4096-bit keys (or even ...

6

What is stopping someone from saving encrypted info, and decoding it later? Nothing. That's exactly why certain three letter institutions build large data centers... Waiting for the first large quantum computer to be built or for new attack techniques that allow to break e.g. RSA for the key sizes used today. Are there any time-sensitive safeguards ...

6

The requirement was introduced in IUT Recommendation X.509 (November 1993), informative appendix D.5.2: It must be ensured that e > log2(n). If not, then the simple operation of taking the integer eth root of a ciphertext block will disclose the plaintext. This advice was removed in the 2000 edition of the standard. It was arguably misguided, and at ...

6

The previous answer has the correct formula for estimating the security level of prime field elliptic curves. However, the table seems to just list the closest Koblitz curve sizes used, as Richie Frame points out. If you computed the actual security strength of the curves in question, you would not end up with exactly the values in the left column. For ...

6

The Integrated Encryption Scheme offers no qualitative advantage (in term of cryptographic service offered) compared to hybrid encryption using RSA. In particular, neither provides Forward Secrecy: if the private key of the recipient leaks, past cyphertexts can be deciphered. All there is to do is apply the decryption algorithm. This contrasts with ...

6

The field of cryptography that you are looking for is called Kleptography. In kleptography, we are dealing with a setting where the device performing your cryptographic tasks is potentially malicious. Now this device tries to leak information to some attacker that allows this attacker to break the used cryptographic scheme. If I am not mistaken that scheme ...

6

First, assuming any padding, the answer given by fgrieu to your related question still holds. You can associate public keys with signatures by looking at which signatures are consistenly (minimally) smaller than the modulus. The second method, as suggested by poncho in the comments of your related question and the comments of this post cleverly uses small ...

6

No, there is no known efficient method to find an RSA private key from public key, ciphertext and plaintext, including when no padding is used and $e=3$. The best known method is factoring the public modulus, which then trivially allows to find a working private key. Factoring is considered brute force, or tantamount to that. The best known factoring method ...

6

Yes, the basic idea of hardcoding a public key is secure. It is sometimes recommended as an alternative to the complexity TLS and PKI bring – otherwise it can be easy to skip a crucial step and end up with little or no security. However, the "encrypt a secret for server" scheme has some weaknesses compared to TLS. The clearest is lack of forward secrecy ...

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