Questions tagged [public-key]
An asymmetric cipher is an encryption scheme using a pair of keys, one to encrypt and a second to decrypt a message. This way the encrypting key need not be kept secret to ensure a private communication. Similarly in public key authentication, the verification key can be public and the signing key private.
319
questions
123
votes
7answers
76k 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 ...
126
votes
6answers
89k views
Should we sign-then-encrypt, or encrypt-then-sign?
Frequently, we want to send messages that are (a) encrypted, so passive attackers can't discover the plaintext of the message, and (b) signed with a private-key digital signature, so active attackers ...
39
votes
5answers
18k 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 ...
51
votes
3answers
41k views
Definition of textbook RSA
What is the definition of textbook or "raw" RSA?
What are some of the properties of textbook RSA?
How does it differ from other schemes based on RSA?
22
votes
2answers
10k views
Is RSA encryption with a private key the same as signature generation?
It is often said that RSA encryption of a cryptographic hash with a private key is the same as signing (signature generation). And that verification consists of decryption using a public key.
Is RSA ...
64
votes
1answer
50k views
Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5?
I've studied that the Bleichenbacher's CCA attack on PKCS#1 v1.5. is a base to many versions of attacks in the area.
I'm trying to understand that attack, but every explanation I saw starts with the ...
68
votes
4answers
37k 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 (encrypted) message.
How can I do this?
56
votes
8answers
58k 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 ...
16
votes
1answer
3k views
After ECDH with Curve25519, is it pointless to use anything stronger than AES-128?
Is the following reasoning correct:
After ECDH with Curve25519, the resulting shared secret will be an EC public key with a bit strength of 128 bits.
This public key would then be hashed (let's say ...
50
votes
3answers
101k views
RSA encryption with private key and decryption with a public key
When using the RSA cryptosystem, does it still work if you instead encrypt with the private key and decrypt with the public key? What about in the case of using RSA for sender authentication?
18
votes
3answers
2k views
Why does key generation take an input $1^k$, and how do I represent it in practice?
In my lecture, the lecturer said:
Let $K$ be the key generation algorithm. Given a security parameter represented in unary, $1^k$, $K(1^k)$ will output a keypair $(pk; sk)$, known as the public ...
73
votes
5answers
34k 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. ...
25
votes
5answers
29k 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?
27
votes
2answers
31k views
Why is asymmetric cryptography bad for huge data?
I've been told that asymmetric cryptography requires that the message to be encrypted be smaller than its key length.
Why is this?
I know about hybrid encryption, which uses symmetric encryption to ...
13
votes
1answer
18k views
how to use common modulus attack?
I am struck with the following problem:
Let Alice, Bob, Chris and Eve communicate over a public network. They encrypt all messages they send using RSA system. Bob and Chris have the RSA modulus $n_B$ ...
67
votes
3answers
46k 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 ...
17
votes
1answer
1k views
Verbatim of early work on public-key cryptography?
In late 1997, the history of public-key cryptography was turned around with the announcement (then extended) that
public-key cryptography was theorized in a 1970 note [1] by James Henry Ellis: The ...
25
votes
2answers
3k views
Why is PuTTYgen-created RSA public exponent(e) not in {3,17,65537}?
As far as I know, RSA public exponent(e) should be one of {3,17,65537}.
However, I found PuTTYgen-created RSA public exponent(e) is 0x25(37) by default,as follows, (PuTTYgen version: 0.66)
I am ...
13
votes
2answers
3k views
Can a computationally unbounded adversary break any public-key encryption scheme?
Assume there is a public-key encryption scheme $(KeyGen, Enc, Dec)$ with perfect correctness (i.e., for all messages M and valid key-pairs (PK,SK), we have $Dec_{SK}(Enc_{PK}(M))=M$).
Will there ...
26
votes
9answers
26k 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 ...
167
votes
4answers
112k 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 ...
45
votes
3answers
29k 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 ...
27
votes
2answers
43k views
How much computing resource is required to brute-force RSA?
It's been over 30 years since Rivest, Shamir and Adleman first publicly described their algorithm for public-key cryptography; and the intelligence community is thought to have known about it for ...
36
votes
4answers
30k 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 ...
82
votes
10answers
17k views
In end-to-end encryption, doesn't the server need to be trusted?
Applications like WhatsApp use end to end encryption. WhatsApp says that only the users share a specific key and no third party can view the messages. But I do not understand how the two users agree ...
22
votes
4answers
11k views
Is sharing the modulus for multiple RSA key pairs secure?
In the public-key system RSA scheme, each user holds beyond a public modulus $m$ a public exponent, $e$, and a private exponent, $d$.
Suppose that Bob's private exponent is learned by other users. ...
62
votes
1answer
6k views
Why does my SSH private key still work after changing some bytes in the file?
I (for a test) just randomly altered a private RSA key by opening it up in Vim and changing a few bytes. It is the private part of an SSH key pair used for logging in on a remote system. Puzzlingly, ...
23
votes
2answers
31k views
How does a chosen plaintext attack on RSA work?
How can one run a chosen plaintext attack on RSA?
If I can send some plaintexts and get the ciphertexts, how can I find a relation between them which helps me to crack another ciphertext?
21
votes
1answer
1k views
Security of RSA for paranoids with padding?
RSA for Paranoids (RSAP) (in CryptoBytes v1n3), also known as Unbalanced RSA, is a variant of RSA proposed in 1995 by Adi Shamir, as a mean to increase the RSA public modulus size while keeping ...
7
votes
1answer
4k views
Is a known plaintext, ciphertext, and public-key a viable attack on RSA?
Assume Alice and Bob are using RSA to create a common session key and Cindy is listening, attempting to obtain the session key.
Alice and Bob each have their public- and private-key pairs ($\left[...
16
votes
1answer
14k views
How does encryption work in elliptic curve cryptography?
So I think I understand a good amount of the theory behind elliptic curve cryptography, however I am slightly unclear on how exactly a message in encrypted and then how is it decrypted.
So my ...
14
votes
2answers
3k views
Is it safe to reuse a ECDSA nonce for two signatures if the public keys are different?
We denote the s value of an ECDSA signature $(r, s)$ on a message $m$ as:
$s=\frac{H(m)+xr}{k}$
Assume two ECDSA signatures sharing the same nonce $(r, s_1) , (r, s_2)$ on two messages $m_1, m_2$, ...
12
votes
2answers
2k views
More than one private key for RSA
In an RSA-encryption scenario, Bob's public key pair $(n, e)$ is $(143, 43)$. An attacker Mallory tries brute-force and comes to $d = 7$ as the private key.
The value of $φ(143) = 120$ is not known to ...
10
votes
1answer
413 views
Could this “symmetric RSA” scheme provide key compromise resistant communications?
This question, and fkraiem's answer to it, made me wonder about the security and practicality of using "symmetric RSA" to provide a partially compromise-resistant secure channel.
Specifically, assume ...
4
votes
2answers
12k views
Why is hybrid encryption more effective than other encryption scheme?
Currently I am learning about Hybrid Encryption but I was not able to find any good study material.
Below is my understanding:
One of the reason why we use ...
1
vote
1answer
1k views
How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$?
Here is some information we got :
We know the value of $n$, with size $1043$.
We know the value of $p$ (size $20$) and $q$ (size $1023$) as the factors.
$e = 65537.$
$\varphi(n)$ = $(q-1)(p-1)$
When I ...
17
votes
2answers
33k views
What makes RSA secure by using prime numbers?
I am just learning about the RSA algorithm. Looking at the first two steps:
Choose two distinct prime numbers $p$ and $q$.
Compute $n = pq$.
I have some probably stupid questions:
Why do $p$ and $...
14
votes
2answers
5k 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 ...
10
votes
3answers
4k views
Is RSA in a ECB-like-mode safe for bulk encryption?
Let's say I would like to communicate with my friend using asymmetric/public-key encryption, e.g. RSA.
(Note: I do realize that in practice this is done through an intermediate symmetric key, but ...
4
votes
1answer
2k views
How to calculate RSA CRT parameters from public key and private exponent
Given the public key (n, e) and private exponent (d), how to calculate CRT parameters (p, q, dP, dQ, and qInv) of this RSA key pair?
2
votes
2answers
2k views
Factors of RSA modulus
In the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any ...
11
votes
3answers
23k views
Using ECDSA keys for encryption
I know that ECDSA is used for signature only, but I wonder if I can use the public/private Elliptic Curve keys for encryption too.
I have ECDSA SSH public keys and I wonder if I can use them to ...
9
votes
5answers
16k 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 ...
1
vote
1answer
521 views
Definition of Short Authentication String
I am studying for my cryptography final and I passed by the following term: short authentication string. Please, can anyone explain it to me, thank you very much.
16
votes
5answers
11k views
Why does the recommended key size between symmetric and asymmetric encryption differ greatly?
In various articles it is mentioned that for secure communications, the recommended key sizes are 128-bit key size for symmetric encryption (which makes it $2^{128}$ possible keys?) and 2048-bit key ...
10
votes
4answers
4k views
Why should the RSA private exponent have the same size as the modulus?
Consider the generation of an RSA key pair with a given modulus size $n$ and a known, small public exponent $e$ (typically $e = 3$ or $e = 65537$). A common method is to generate two random primes ...
asked Jul 18 '12 at 18:14
Gilles 'SO- stop being evil'
14.7k3 gold badges39 silver badges76 bronze badges
7
votes
1answer
2k views
What does the $\|$ operation mean in cryptographic notation?
I am studying elliptic curves problems, which also includes study of related protocols such as ECIES. The problem is that I don't understand the notation $\|$. What does this operation mean?
Some ...
4
votes
1answer
5k views
ECC vs RSA: how to compare key sizes?
I know and I have understood the details of RSA, elliptic curve cryptography, (EC)DH and (EC)DSA.
I keep reading everywhere that (if we don't consider non-deterministic computers) "ECC can achieve ...
4
votes
2answers
483 views
Bruce Schneier, encryption, public keys and digital-signature.
In his book "Applied Cryptography" Bruce Schneier, when talking about public key cryptography, says that:
If the same algorithm is used for both encryption and digital-signature verification there ...
0
votes
1answer
1k views
RSA encryption/decryption process is not working correctly
I'm trying to apply the RSA cryptosystem to encrypt a byte M=72, using predefined modulus n, public key exponent ...
