# Tag Info

## Hot answers tagged public-key

9

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

9

A PGP encrypted message can be hundreds or even thousands of bytes. Encrypting and decrypting large amounts of data using asymmetric algorithms is extremely slow. Encrypting only 32 to 16 bytes (the symmetric key) is much faster. Additionally, if you encrypt the same message twice with an asymmetric algorithm, you will get the exact same ciphertext. Using ...

9

I think you misunderstood a detail of PGP encryption. Only the random symmetric key is encrypted under the recipient's (asymmetric) public key. This way to encrypt stuff is quite common and is called KEM/DEM paradigm: Key Encapsulation Method/Data Encapsulation Method oy Hybrid Encryption. Some refs: en.wikipedia.org/wiki/Hybrid_cryptosystem and ...

7

Yes, obviously if the CA generated your private key, they might keep it and share it with anybody. Yes on both counts. In fact, the normal way to generate a certificate -- whether for a Web server (TLS) or for yourself (S/MIME or TLS client) -- is to create a "Certificate Signing Request" and send it to the CA. The CSR includes your public key, not your ...

7

@pg1989 has not only the right answer, but the only answer if you assume the goal is to have multiple RSA encryption exponents that correspond to the same decryption exponent. $$e_1 * d \equiv 1\ (\mathrm{mod}\ \phi(N))$$ $$e_2 * d \equiv 1\ (\mathrm{mod}\ \phi(N))$$ $$(e_1 - e_2) * d \equiv 0\ (\mathrm{mod}\ \phi(N))$$ But since $d$ is relatively prime ...

7

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

7

There are multiple metrics for work or effort needed: Amount of operations it takes (one operations is, for instance, one invocation of hash function or number of modular multiplication operations) Amount of money it takes Amount of memory it takes Amount of time it takes Strength in bits Amount of operations Usually, if amount of operations is large ...

7

Selecting a small $d$ is known to be insecure. Wiener has shown in 1990 that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the public key $(N,e)$. If you're interested in making the private computational cost cheaper, then I would suggest that RSA is not the best solution; I would recommend you start looking at ...

6

Since this is an historical question, I am going to digress and make some historical corrections. In science, we give credit for important inventions to the people who published. If it turns out that someone else invented it earlier and didn't publish, they don't get credit. Obviously, they should be mentioned in passing or a footnote in the interests of ...

6

If CryptoLocker does its job properly, then no, knowing part of the cleartext will not help you recover the rest. If that helped, then the encryption system would be called weak against known-plaintext attacks. From what I read, it seems that the CryptoLocker authors were competent(*), so no such luck. (In particular, the asymmetric encryption with RSA-2048 ...

6

If the KGC gets compromised it will break security, so why should a KGC generate private keys. Certificateless crypto tries to overcome the problem which exists in identity based crypto, i.e., that the KCG generates all the private keys of the users (that is necessary in IBE, see below) and thus knows all the private keys of users (which in turn enables ...

6

A lot of sleepless nights for the CA, their customers, web browser and OS developers, and Slashdot users, that's what. I don't know if a CA has ever had their private keys compromised, but there have been incidents where their systems were broken into and fraudulent certificates were issued. (There's a difference between a private key actually being taken, ...

6

There is no direct inference from $P = NP$ or $P \neq NP$ to security or insecurity of any particular encryption algorithm. As far as practical consequences are concerned, the "$P = NP$" problem is severely overhyped. If $P = NP$ then any problem for which a solution can be verified in polynomial time can also be solved in polynomial time. "Polynomial time" ...

6

The two last equations don't directly give you the value of $C_i$, they are telling you the values of the remainder of Ci when divided by $P$ and $Q$. You then use the Chinese Remainder Theorem with this information to produce the value of $C_i$ (modulo $N$) that you are looking for. See en.wikipedia.org/wiki/Chinese_remainder_theorem (there is an algorithm ...

6

ECDSA is a digial signature algorithm ECIES is an Intergrated Encryption scheme ECDH is a key secure key exchange algorithm. First you should understand what are 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 ...

6

Diffie Hellman Diffie Hellman is a key exchange protocol. It is an interactive protocol with the aim that two parties can compute a common secret which can then be used to derive a secret key used for some symmetric encryption scheme. I take the notation from the link above and this means we have a group $Z_p^*$ for prime $p$ generated by $g$. Party $A$ ...

6

No, signing the hash of the public key cannot introduce a weakness on a secure signature scheme. When we have a signature scheme, we assume that it is secure in an chosen text model, where the attacker has access to the public key, and can ask any text of his choosing to be signed. We can see that any such scheme (such as ECCDSA, or so we believe) cannot ...

6

That's because the public key in DER format (which is a way of expressing X.509 objects as a sequence of bytes) includes more than just the modulus. Specifically, it consists of: This is a collection of the following objects; that takes up 4 bytes The first object is an integer (which happens to be the public modulus); the integer itself is 257 bytes (not ...

6

Rick Demer already wrote the answer in the very first comment, but without explanation: Hybrid encryption. But since you asked for a real practical example to encrypt your word document, this is how: Your file is on your disc, and it is 100,000 byte large. You can then do: First, you start up a random number generator. Preferably you should either have ...

5

I'd go with hash(ProverPublicKey || RandomChallenge || Data) over your idea of hash(RandomChallenge || Data). Your scheme has the problem that the prover might challenge another party to prove that they have the data and forward that prove to the original challenger. Related keywords are proof-of-retrievability, proof-of-ownership or ...

5

Well, yes, everyone (or, at least, everyone who can use the public key) knows the hash function H and G; so we can assume that an adversary knows them as well. You ask: If YES: How does it help the security, if he just can decode the padding and read the message? Well, he can't decode the padding; the ciphertext has been encrypted using RSA, and he ...

5

If you are restricted to Diffie-Helman, RSA, and ElGamal, I believe you cannot do pairing based cryptography which has applications to attributed based encryption and identity based encryption. These applications are not used heavily in practice, but could be in the next decade or two. For more information on speed benefits of ECC, see this question and ...

5

It depends on what you are using RSA for and how deep of an understanding you would like. A sort of general overview of RSA and potential attacks against textbook RSA is presented in the Handbook of Applied Cryptography, specifically chapter 8. (Note that the entire text is free online.) Chapters 11 and 12 also are useful to read, as they focus on specific ...

5

The basic explanation is that you need both keys to make a complete encryption/decryption cycle. Basically the encryption works with modulo arithmetic so that $$c=m^a \mod n$$ and $$m=c^b \mod n$$ where $a$ and $b$ are the public and private key of the algorithm. $m$ is the plain text message and $c$ s the ciphertext. The most important thing about the ...

5

This depends largely on the trustworthiness of Facebook and your assumptions about the model and attacker. If Facebook is corrupted, they will just exchange your information to their address/public key and can still do a man-in-the-middle. An external attacker could modify the profile pages while they are being transmitted to other users or in their ...

5

We need clear goals. The question asks for "plausible deniability" or "deniable encryption", and these terms needs a precise definition in a public-key context (implied by RSA). I assume that in addition to the IND-CPA and IND-CCA1 properties of a cipher, including hybrid (as implied by AES), it is desired that: One without the private key can't ...

5

Actually, it's not true that public key encryption is based on Discrete Log; the ones in common use (DH, ECDH, ECDSA) are (and even RSA can be viewed as "based on Discrete Log", at least from the standpoint of "if you can solve the Discrete Log modulo a composite, you can break RSA"). However, we do have a number of public key systems (NTRU, McEliece) which ...

5

Symmetric encryption is no longer necessary, because all security services can be implemented with public-key cryptography. No. The speed of asymmetric encryption is prohibitive when it comes to encrypting more than a few hundred bits of data. This is why most protocols that implement encryption with asymmetric cryptography are hybrid, using asymmetric ...

5

How do we keep $\phi(n)$ secret? We don't tell people what it is. The problem of finding $\phi(n)$ given $n$ is a hard problem (if $n$ is hard to factor). So, if we give people a number that they can't factor, and we don't give them $\phi(n)$, they can't determine it on their own.

4

When we say "RSA is broken" do we mean that a practical attack is discovered to retrieve the private key from the public, or do we mean that given a ciphertext and no knowledge of either the private or the public key the attacker can decrypt the data? First off, we always assume the attacker has the public key. Someone saying "RSA is broken" could mean ...

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