Public key cryptography describes all cryptographic algorithms which have a pair of keys, one key that performs encryption and one key that performs decryption. One of these keys is made available publicly, allowing anyone to send messages that only the holder of the private key can read. You should ...
37
votes
3answers
18k views
Why is elliptic curve cryptography not widely used, compared to RSA?
I recently ran across elliptic curve crypto-systems:
An Introduction to the Theory of Elliptic Curves (Brown University)
Elliptic Curve Cryptography (Wikipedia)
Performance analysis of identity ...
21
votes
3answers
3k views
How can I use asymmetric encryption, such as RSA, to encrypt an arbitrary length of plaintext?
RSA is not designed to be used on long blocks of plaintext like a block cipher, but I need to use it to send a large message.
How can I do this?
18
votes
2answers
863 views
How are primes generated for RSA?
As I understand it, the RSA algorithm is based on finding two large primes (p and q) and multiplying them. The security aspect is based on the fact that it's difficult to factor it back into p and q. ...
16
votes
3answers
1k views
How big an RSA key is considered secure today?
I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the ...
15
votes
5answers
5k views
How does asymmetric encryption work?
I've always been interested in encryption but I have never found a good explanation (beginners explanation) of how encryption with public key and decryption with private key works.
How does it ...
15
votes
7answers
1k views
How can SSL secure a two-way communication with only one key-pair?
As I understand it, SSL involved the use of a public-private key pair. How does this enable two-way communication?
Suppose I have some server with which I wish to communicate securely. I connect to ...
13
votes
4answers
4k views
Basic explanation of Elliptic Curve Cryptography?
I have been studying Elliptic Curve Cryptography as part of a course based on the book Cryptography and Network Security. The text for provides an excellent theoretical definition of the algorithm but ...
11
votes
3answers
3k views
Why is public-key encryption so much less efficient than secret-key encryption?
I'm currently reading Cryptography Engineering. After giving a high level explanation of the difference between secret-key encryption and public-key encryption, the book says:
So why do we bother ...
10
votes
8answers
897 views
RSA with small exponents?
Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse ...
9
votes
3answers
419 views
Does NTRU decrypt correctly now?
The NTRU public-key cryptosystem has a lot of interesting properties (being resistant to quantum computer attacks, being standardized by several important bodies), but it also has a pretty unique ...
9
votes
5answers
2k views
Types of Cryptography for a 4-8 bit microcontroller
This is more of a research question.
I was wondering what types of crypto algorithms would work best on a small 4-8 bit micro controller. I recently read a paper called Security Considerations for ...
9
votes
2answers
304 views
How should one implement a delegated shared trust protocol?
Consider the following (probably naive) scenario.
Alice, who is very limited in her knowledge of security in general (clueless about securing a private key for example), wishes to delegate certain ...
8
votes
2answers
817 views
Can two different pairs of RSA key have the same modulus?
Can $n=pq$ be part of two different pairs of RSA keys?
If such keys exist, say $(e_1,n)$ and $(e_2,n)$, how are they related?
What will be the security concerns for the two users?
8
votes
4answers
662 views
Does RSA work for any message M?
I decided to read the original RSA paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystem because of a question I had about RSA (which is not the question I'm about to ask, but ...
8
votes
3answers
241 views
Is it possible to create an asymmetric cryptosystem where the private keys are not easily verifiable as such?
Plaintext that consists of an RSA key is easily recognizable as such, because it satisfies certain mathematical properties, in particular (See the answer for Why can an encrypted private key be brute ...
8
votes
2answers
565 views
Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC) ?
Related to this question.
Given ciphertexts generated by any of the major asymmetric ciphers (RSA, ElGamal, ECC, etc..) can these ciphertexts be distinguished from random noise? Justify why, why ...
7
votes
3answers
376 views
Asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm
In the computer security class (in which cryptography is a big chapter) that I took, I remembered the professor said about current asymmetric cryptography algorithms are based on integer factorization ...
7
votes
2answers
660 views
Are there practical upper limits of RSA key lengths?
Suppose one wanted to use RSA encryption for the sole purpose of sending key bits for use in symmetric crypto systems, a dedicated key exchange system so to speak.
And say you didn't think that the ...
7
votes
3answers
300 views
Is key size the only barrier to the adoption of the McEliece cryptosystem, or is it considered broken/potentially vulnerable?
A recent paper showed that the McEliece cryptosystem is not, unlike RSA and other cryptosystems, weakened as drastically by quantum computing because strong Fourier sampling cannot solve the hidden ...
7
votes
1answer
202 views
Alice trusts Bob only when Bob trusts Alice
some story first: Alice and Bob both have public/private key pairs. Now Bob wants Alice to sign his public key id. Alice agrees but only when Bob signs the public key id of her.
Is this something ...
6
votes
5answers
2k views
Why do we need asymmetric algorithms for key exchange?
In SSL protocols, both symmetric and asymmetric algorithms are used. Why is it so? The symmetric algorithms are more secure and easier to implement. Why are asymmetric algorithms usually preferred in ...
6
votes
2answers
1k views
Definition of Textbook RSA
What is the definition of Textbook RSA?
What are some of the properties of textbook RSA?
How does it differ from other RSAs?
6
votes
1answer
588 views
Generating Random Primes
Although this has been extensively discussed around here, I'm curious whether my approach makes sense, or I should just stick to "the standard version".
I'm implementing some homomorphic encryption ...
6
votes
1answer
301 views
Exposing RSA private-key data… bad?
We know that exposing $p$, or $q$ or $\phi(n)$ results in trivial attacks on RSA since they allow us to factor $n$ and to compute the private exponent $d$.
In OpenSSL (and most RSA implementations) ...
6
votes
1answer
282 views
Compressing EC private keys
For reasonable security, EC private keys are typically 256-bits. Shorter EC private keys are not sufficiently secure. However, shorter symmetric keys (128-bits, for example) are comparably secure.
I ...
6
votes
2answers
1k views
Impacts of not using RSA exponent of 65537
This RFC says the RSA Exponent should be 65537. Why is that number recommended and what are the theoretical and practical impacts & risks of making that number higher or lower?
What are the ...
6
votes
1answer
666 views
Why does the PKCS1 RSA private key structure contain more than just exponent and modulus?
The ASN.1 spec for the PKCS1 RSA private key format is as follows:
...
6
votes
2answers
308 views
For public-key encryption, why does COA resistance imply CPA resistance?
My professor told me:
If a public-key crypto-system is secure against ciphertext-only attacks,
then it is also secure against a chosen-plaintext attack.
Why is this true? Is there a proof that ...
6
votes
1answer
1k views
How do other, non-RSA algorithms, compare to the PKCS #1 standard?
Arguably the PKCS suite of standards have a profit-oriented bias as they are promoted by RSA and promote their algorithms over others in the form of RFCs and other means.
I'm considering the ...
6
votes
3answers
162 views
Number of intersections of two sets
Suppose both I and my friend have a set of integer numbers. We want to know the number of common elements in our two sets but without knowing elements of the sets of each other. So I don't want my ...
6
votes
3answers
370 views
Security equivalence proofs for breaking RSA
It is my understanding that while a practical solution to the factoring problem will definitely break RSA, it has never been proven that the security of RSA is equivalent to factoring.
In otherwords, ...
6
votes
2answers
2k views
What's the fundamental difference between Diffie-Hellman and RSA?
What is the difference in the purpose of DH and RSA? Aren't they both public-key encryption?
5
votes
5answers
461 views
Applications of Group Ciphers
I've been reading a paper [1], and I've ran across something called a "Group Cipher", which is similar to homomorphic encryption, with an important difference.
In homomorphic encryption we have an ...
5
votes
3answers
286 views
RSA primes vs. largest known primes
In the context of a new largest (mersenne) prime number being found this week -
The largest known prime number is now 2^57,885,161 − 1, and it took 5 years to find ...
5
votes
3answers
639 views
Is it possible to validate a Public Key in RSA?
If I have a 1024-bit number, and someone is telling me that it is in fact a valid RSA public key, is there any way I can quickly validate that it is indeed so (without cracking RSA)?
(I suppose I am ...
5
votes
2answers
2k views
In RSA, do I calculate d from e or e from d?
In the original paper introducing RSA, it is implied that one should first choose $d$ and then calulate $e$ from $p$, $q$, and $d$. However, I have found in other places (such as the wikipedia article ...
5
votes
1answer
156 views
What are the benefits of lattice based cryptography?
Previously we visited the benefits of elliptic curves for cryptography. Lattice based cryptography is starting to become quite popular in academia. The primary benefit of lattice based crypto is the ...
5
votes
1answer
276 views
How should I check the received ephemeral Diffie-Hellman public keys?
In my application I'm doing a DH key exchange, where both sides generate their
own ephemeral key. No static keys are used. I am trying to make my
application resistant against an active attack and ...
5
votes
2answers
565 views
Cycle attack on RSA
I originally posted this question in the mathematics section, you can see it here.
Let $p$ and $q$ be large primes, $n=pq$ and $e : 0<e<\phi(n), \space gcd(e, \phi(n))=1$ the public encyption ...
5
votes
2answers
865 views
Why can't Diffie-Hellman be used for signing?
I understand that signing is often a case of hashing data and then encrypting the hash with the private key. What properties keep Diffie-Hellman from being useful for this?
5
votes
1answer
116 views
Proof that padded RSA is CPA-secure
I'm referring to page 383 of J. Katz and Y. Lindell's Introduction to Modern Cryptography. The book presents a padded RSA:
${\bf Key Generation:}$ same as Textbook RSA (given security parameter ...
5
votes
1answer
290 views
GPG/PGP Verification of Revocation
How does one verify a key revocation?
After revoking a key and sending the revocation to MIT's keyserver, I noticed that the key is listed as such:
...
4
votes
4answers
419 views
Why is it important that phi(n) is kept a secret, in RSA?
Why is it important that $\phi(n)$ is kept a secret, in RSA?
4
votes
4answers
2k views
How can one securely generate an asymmetric key pair from a short passphrase?
Background info:
I am planning on making a filehost with which one can encrypt and upload files. To protect the data against any form of hacking, I'd like not to know the encryption key ($K$) used for ...
4
votes
3answers
487 views
What is Identity-Based Encryption (IBE) and why is it “better”?
Most CS/Math undergrads run into the well-known RSA cryptosystem at some point. But about 10 years ago Boneh and Franklin introduced a practical Identity-Based Encryption system (IBE) that has ...
4
votes
3answers
201 views
What other one-way functions are used in cryptosystems?
For RSA and El Gamal (and most other public key cryptosystems), one of the key ideas is that factoring and finding discrete logarithms are hard. There are other systems that rely on certain properties ...
4
votes
2answers
183 views
Signature schemes for underpowered devices (8bit microcontroller)
I am currently researching into a small scale home automation system, aiming for cost. The system architecture is basically one master and several slaves which are connected in parallel.
Recently ...
4
votes
1answer
153 views
In RSA encryption, does the value of e need to be random?
I am a novice programmer and am just finishing up an RSA encryption program that I am writing for practice. Currently I have the program generate a relatively small random value for the public key e. ...
4
votes
3answers
212 views
Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?
If Alice encrypts two messages $a$ and $b$, such that $x=E(a)$, $y=E(b)$. Can Alice prove (without revealing $a$, $b$ or the private key) that $a = b$?
Obviously the proof must not be too long and it ...
4
votes
1answer
106 views
Do public/private pairs work both ways?
Public/private key algorithms such as RSA encrypt a message with a private key but only decrypted with another (mathematically related) key.
Can the public key decrypt the messages encrypted with ...
