# Tag Info

## New answers tagged public-key

0

With regards to the public vs private keys, in RSA, the public key is used to encrypt information, the private key is used to decrypt it. Given only the public key, all you can do is encrypt. So, you can publish that online somewhere (key distribution is a very different problem). Anyone can use it to encrypt a message to you and only you can decrypt it. ...

0

An RSA public key contains the modulus ($n$) and the public exponent ($e$, usually $65537$). It is formatted differently in different implementations, most commonly, it is a dump of the data and its length, encoded with base64. For an example, see http://stackoverflow.com/questions/1193529/how-to-store-retreieve-rsa-public-private-key/13104466#13104466

0

Use the Legendre symbol in your case. Explanation: when $p=2.q+1$, the order of the multiplicative group of $F_p$ is p-1=2q. Then there is no other alternative, when you select a random number, it could be a quadratic Residue with probability $\frac{1}{2}$. The legendre symbol of any number a, is : $a^{\frac{p-1}{2}}=a^{q}=\pm 1$ Then except the number 1, ...

0

Modular inverse can be computed with Extended Euclidian Algorithm, as other answers suggest. I will answer your second question - why an attacker can't get private key? The problem here is that private exponend is modular inverse of public one, but modulo $\phi(n)$, not $n$: $d \equiv e^{-1} \pmod{\phi(n)}$ Attacker does not know $\phi(n) = (p-1)(q-1)$ ...

0

Use Keylength.com There are several metrics that try to estimate for how many years a given keylength may last you. The length calculator at Keylength.com (http://www.keylength.com/en/compare/ ) uses eight such heuristics to give you a general idea which size you should choose. You can go both directions. You can either enter a year and receive a ...

1

To find multiplicative inverse (d) mod φ(n) you may use Extended Eculdian Algoritm "EEA"(or any other algorithm but EEA is usually used to best of my knowledge). The algorithm is explained here http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm this online tool computes the inverse using EEA http://www.cs.princeton.edu/~dsri/modular-inversion.html ...

1

(Realised my mistake as I finished typing the question) Finding the multiplicative inverse is in fact computationally feasible. The prime numbers p and q are not public (although n = pq is). An attacker cannot therefore know φ(n), which is required to derive d from e. The strength of the algorithm rests on the difficulty of factoring n (i.e. of finding p ...

0

As already answered there are mathematical reasons why public-key (aysmmetric) algorithms must have strength less than their key size, often dramatically so: RSA or (non-EC) DSA/DH requires about 3000 bits size for 128 bit strength. For secret-key (symmetric) algorithms we can have strength equal to the key size, or colloquially "use all the bits", and ...

0

The whole point of public key cryptography is that there is a secret key, which, if the system is to be any good, cannot be easily computed from the public key, but is known to the legitimate owner of the public (i.e. the one who generated and published it). And decryption uses the secret key, not the public one. Encryption only uses the public key. But ...

4

While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case. What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd. The special property that $\lambda$ has ...

2

Generally the public exponent is small. then if you know the public and private key, then you can compute $e.d=1+k.\phi(n)$. k is smaller than e and $\phi(n)$ is in the range of n. A direct method allow to make an exhaustive search on the small k which divide ed-1 in such a way that $\frac{e.d-1}{k}$ is an integer. Then $\phi(n)= p.q -(p+q)+1$ allow to find ...

0

Tylo is correct that the keyspace size is not necessarily dictated by the number of bits in the key for an asymmetric algorithm. RSA is a prime example (pun intended). However, the problem is more fundamental: the best-known algorithm for breaking symmetric cryptography is usually brute-force, or at least, something with a negligible speedup over it; for ...

1

Usually we only consider those keys, we can actually use. There is no restriction about the bits in a symmetric key, you can use all of them. For asymmetric encryption schemes, both keys need to fulfill some constraints to actually work. For example: In RSA, $e$ has to be chosen coprime to $\phi(n)$, and you need $ed=1$ mod $\phi(n)$0. What does it mean? ...

0

A symmetric key is basically a random blob, the whole 2^n space is valid and thus has to be searched.

1

For public key encryption, there's an easy solution using a variant of Elgamal. (If you want to do authentication, you can use standard algorithms. If you specifically want signature schemes, say so.) Recall that the security of Elgamal is equivalent to DDH, which is talking about indistinguishability of certain subgroups, namely given a cyclic group $G$, a ...

-1

I am studying the mathematics behind modern cryptography from the excellent text An Introduction to Mathematical Cryptography. Here is their explanation of the same. Suppose Alice is someone who wants to engage in secret communication with multiple people, one of them being Bob. Eve is our regular attacker, always trying to get behind the encryption schemes ...

0

Yes, it is possible. Steve Gibson's SQRL does a similar thing: the user has a master private key, which is hashed together with a domain name to produce a site-specific public/private key pair. (The hash in this case is HMAC-SHA256, with the domain name used as the message.) Your post doesn't mention what kind of services this will be for. If SSH, then you ...

0

Is this possible? Yes. Is there any existing solution which satisfies the above requirements? That depends on what you mean by "existing". Trapdoored key generation can be used for that. x is the chosen key generation algorithm, K$_{\text{priv}}$ and K'$_{\text{priv}}$ are both its trapdoor, and the derivation of K'$_{\text{pub}}$ simply ignores ...

-1

Here is a great video which shows principles for public key cryptography using colors, which makes it easy to understand for everyone: https://www.youtube.com/watch?v=YEBfamv-_do Now what you missed is that it is possible to generate a secret key, and give away something which enables encryption but not decryption. This is the principle of public key ...

1

The answer is: this question is based on a mistaken premise. The private key is usually not generated first. In general, they're generated at the same time. For some schemes, the public key can be derived from the private key, but this doesn't always hold, and that will depend on specific properties of the particular public-key scheme. If it's possible ...

1

What about the beautiful images on this page, Certificate Binary Posters part 1 and part 2? I'd believe they would be useful in this case.

-1

That behavior seems to be due to the workflow of the application you mentioned. In fact the public key is generated first, the private key is derived from the public key. When you get your private key the application already knows the public key. Here is what happens, note the public key existing in step 4: Choose two distinct prime numbers p and q. For ...

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 group $G$ 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 ...

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

0

I am not sure if this is possible in general (for any asymmetric cipher), but this is not prohibited. In theory, private key contains the same information as public key. With unrealistic amount of time, you are able to compute private key from public key. There is one strong requirement: one can't derive the private key from the public key (in a reasonable ...

0

In short, they retrieve the entropy directly from a source on the chip. From Wikipedia: In computing, a hardware random number generator (TRNG, True Random Number Generator) is an apparatus that generates random numbers from a physical process, rather than a computer program. Such devices are often based on microscopic phenomena that generate low-level, ...

1

This is a very interesting question, in the sense that every smart card provider claims the inviolability of its own process. Nowadays, Smart cards can generate their cryptographic keys on the card itself using appropriate hardware. Entropy is generally generated by an embedded random generator. The hardware of the generator is generally certified by ...

0

Something that might bite is that the ASN encoding requires the numbers to be positive. So when a 2048-bit random prime happens to have a '1' as the first bit, it is prefixed with a byte of 0 to make it positive. This means half of your 2048-bit primes are 256 byte and the others are 257 bytes.

1

To conclude the answers here's a note about the simplest way (on linux at least) to view the contents of such keys with openssl: $openssl rsa -in test.key -text Private-Key: (512 bit) modulus: 00:83:8b:7a:98:1d:a9:7a:cc:d3:b3:b8:75:5f:e7: 27:98:12:03:5d:a3:72:30:5e:05:72:b9:99:93:bb: 19:ce:fb:f0:7b:af:84:98:be:46:fa:a1:4a:2f:36: ... 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 ...

0

Actually, the Base64 string doesn't contain just the private key but a specific data structure with additional information. In particular, your data contains a RSAPrivateKey object, which contains several values, including primes p and q. You can see a description of that object here.

7

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

1

A digital signature requires the person/entity doing the signing to be the ONLY one with access to the private key. So by transferring the document AND the key to your server it basically invalidates the whole process as you can now forge the signature of the user. The process works as follows: The private key transforms the original in a unique way. The ...

3

It is logically impossible to transfer a private key. The key will continue to be a signature key, but it will cease to be "private" the minute it is transferred. A signature key that isn't private isn't a private key. If you want the document to be signed by the user (in any semantically coherent sense), this operation has to take place on a device ...

Top 50 recent answers are included