# Tag Info

34

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

24

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

17

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

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)\\ ... 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 ... 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 ... 10 In general, the public and private keys are computed together. For some schemes, the public key is computed from the private key. ElGamal is an example. (The system parameters include a suitable cyclic groupG$with a generator$g$. Choose a random exponent$a$. Compute$y=g^a$. The public key is$y$, the private key is$a$.) For other schemes, this is ... 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 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. ... 8 Definitions In RSA, an encryption key is a pair of integers$(N,e)$with$N$the product of$m\ge2$distinct odds secret primes$r_i$(with$0<i\le m$), and$e$is such that$\gcd(e,\lambda(N))=1$where$\lambda(N)=\operatorname{lcm}(r_1-1,\dots,r_m-1)$is the Charmichael function. It follows that$e$is odd. Typically, other conditions are added, like ... 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 ... 7 You are looking for Proxy Re-Encryption. From a high-level viewpoint, a proxy re-encryption scheme is an asymmetric encryption scheme that permits a proxy to transform ciphertexts under Alice's public key into ciphertexts decryptable by Bob's secret key. In order to do this, the delegator$A$gives a special re-encryption key$rk_{A \rightarrow B}$to the ... 7 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 In the basic fixed window method of performing point multiplication, we compute the value$nP$(where$n$is the integer we're multiplying by, and$P$is the basis point) by finding the base$b$representation$n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$(where$0 \le d_i < b$), and then computing first$1P, 2P, ..., (b-1)P$and then$nP = ...

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

Any $e$ 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 condiiton is easily checked. One often encounters other $e$, but many ...

5

Although I can't see any immediate weaknesses, I also don't see how it adds significant value over DSA (while being significantly slower). It claims to be based on two hard problems, discrete log and factoring. However, it doesn't give any particular proof that if you could forge signatures, you can solve both problems. It also doesn't look particularly ...

5

Provably secure cryptographic hash functions are often built using the same sort of operations as what are used in asymmetric crypto. The major problem with these constructions are that they are very inefficient. Also, a lot of these sorts of constructions have finite input domains. Thus, you have to figure out how to extend it to arbitrary length inputs. ...

5

I wondered if there is a "simple" description of the set of numbers n that have this property. Yes, there is; $n$ has a prime factorization $p_1 \cdot p_2 \cdot ... \cdot p_n$ such that all the primes are unique (i.e. $n$ is square-free), and for each prime factor $p_i$, $p_i-1$ must be a divisor of 24. In other words, each prime must be a member of ...

5

It is correct that the given private key does not encode a single integer, and that it includes two primes $p$ and $q$. More precisely, that Base64 data encodes a string of bytes, which is an RSAPrivateKey encoded per ASN.1 DER-TLV (and thus BER-TLV) following PKCS#1v2 Appendix A.1.2 (likely restricted to version 0). It decodes to: 30 ASN.1 tag for ...

5

The reason that one must be derived from the other is that the private and corresponding public key are strongly related: For instance, in RSA, the pair satisfies $ed\equiv 1\mod\varphi(n)$; in Diffie-Hellman, we have $A=g^a$; and so forth. Hence, it is just natural to start with with generating one part and deriving the other to satisfy the cryptosystem's ...

5

Towards the security of the signature scheme, no precaution against timing attack is necessary when verifying an asymmetric signature. That's because there is no secret involved, thus no information leak to fear. However it can happen that the message, or the signature itself, is intended to be secret; a leak by timing dependency (during computation of the ...

5

To generate your pair of keys with elliptic curves first you have to chose your domain parameters (I think this name may comes from the P1363 naming convention, or perhaps it's previous). Those domain parameters will be public. For example for curves over finite fields those parameters are: ${p,a,b,G,n,h}$. The lower level operations will be made in ...

4

Generically, this certainly does not work. For example, with RSA, if you take the domain to be ${\mathbb Z}_N^*$ then it's a permutation so is clearly collision resistant but also completely useless. Then, if you take a larger domain, it's trivial to find a collision. For example, take any $x\in{\mathbb Z}_N^*$ and then take $x'=x + N$. It is clear that an ...

4

So is 2 the private key here ? No, it's referred to as a "shared secret" (because it is shared between Alice and Bob, and is secret to everyone else). If there were 'private' and 'public' keys (which is not the standard terminology with DH), then Alice's private key would be $a=6$, and the public key would be $g^a = 8$. In this case, the 'private key' ...

4

No, this system is not secure. Knowledge of the private key immediately gives enough of the public key that we can immediately encrypt an arbitrary message. The NTRU decryption key includes a polynomial $f$; the encryption key is essentially $f^{-1}g$, where $g$ is a polynomial with coefficients in the set $(0, p, -p)$. Anyone with the private key can ...

4

The method mentioned in the answer by Maarten will allow you to reduce the private key size for any public key algorithm by regenerating the key from a random seed, each time you need it. The drawback is the performance. Each time you need to use the key you need to spend as much CPU time for regenerating the key as you used for generating it the first ...

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