Questions tagged [rsa]
An asymmetric (e.g. public-key) cryptosystem, based on modular exponentiation with big exponents and modulus. RSA can be used both for signature and encryption with proper paddings.
2,786
questions
15
votes
3
answers
7k
views
Can or can not D-Wave's quantum computers use Shor's and Grover's Algorithm to find encryption keys? Why?
I read that a company called D-Wave Systems has and is manufacturing quantum computers of 128 qubits.
Can they or can they not use Shor's and Grover's algorithms for finding RSA-keys? If they can't ...
15
votes
3
answers
41k
views
Is there a specification for the "BEGIN RSA PRIVATE KEY" format?
Until now I didn't find a specification (RFC or similar) for the file format that uses the BEGIN RSA PRIVATE KEY prefix and END RSA PRIVATE KEY suffix. Where is it defined? Is there an official name ...
15
votes
1
answer
30k
views
RSA cracking: The same message is sent to two different people problem
Suppose we have two people: Smith and Jones.
Smith public key is e=9, n=179 and Jones public key is e=13, n=179.
Bob sends to ...
15
votes
3
answers
1k
views
Can we ensure the security of a crypto-algorithm and -implementaton against acoustic cryptanalysis?
Like people always say: “Attacks only get worse…” — which is why I'm asking early.
I have been reading the paper “RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis” published December 18, ...
15
votes
2
answers
8k
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 ...
15
votes
4
answers
2k
views
Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC)?
Related to "Is it possible to derive the encryption method from encrypted text?".
Given ciphertexts generated by any of the major asymmetric ciphers (RSA, ElGamal, ECC, etc..) can these ciphertexts ...
15
votes
2
answers
3k
views
Given enough RSA signature values, is it possible to determine the public key value?
Given enough RSA signature values, is it possible to determine which public key is required to verify the values?
Could there be enough information to establish which key is required? Is there ...
15
votes
1
answer
25k
views
Should I be using PKCS1 v1.5 or PSS for RSA signatures?
I am implementing an application where a user needs to sign some data that they have created, store it in an untrusted place, then later retrieve that data and verify it is still authentic before ...
15
votes
2
answers
2k
views
Attacking RSA signature verification that ignores padding
I am looking at a RSA signature verification that is quite obviously flawed and am wondering if there's a way to exploit that flaw in practice.
Signature is generated using RSA with PKCS 1.5 padding, ...
14
votes
1
answer
6k
views
How to find the encoding of an RSA public key?
What practical methods is there to reconstruct an RSA public key in unknown format?
As an illustration, in a database I find this (which doesn't look like ASN to me):
...
14
votes
2
answers
44k
views
AES vs RSA - Which is stronger given two scenarios?
Let's say we have some plaintext.
Let's say that we encrypt this plaintext with a random 32 byte key using AES-256.
Let's say that we also encrypt this plaintext with an RSA 2048 public key.
If only ...
14
votes
3
answers
29k
views
Deciphering the RSA encrypted message from three different public keys
I have three different 1024-bit public keys with common exponent $e$ but different moduli. A message $m$ is encrypted (without padding) using the three keys, which results in three different encrypted ...
14
votes
3
answers
3k
views
Is it reasonable to assure that p-1 and q-1 aren't smooth?
I came across the requirement that, in RSA, $p-1$ and $q-1$ shouldn't be smooth, shouldn't consist of lots of small factors. Therefore my question:
How complicated is it to check whether $p-1$ is ...
14
votes
1
answer
16k
views
RSA-PSS salt size
One of the inputs of RSA-PSS signing and verification is the salt size. According to PKCS#1, you must know the salt size before the verification is carried out. However, this makes interoperability ...
14
votes
2
answers
11k
views
What's the difference between rsa_pss_pss_* and rsa_pss_rsae_* schemes?
I'm trying to understand the difference between rsa_pss_pss_ and rsa_pss_rsae_.
The picture shows the extension of TLS1.3's ...
14
votes
2
answers
6k
views
Leading 00 in RSA public/private key file
I found these following values ALWAYS have the leading 00 in public/private key,
public key: modulus
private key: modulus, p,q, d mod (p-1), d mod (q-1), coefficient
e.g., modulus
...
14
votes
2
answers
16k
views
Why has the RSA factoring challenge been withdrawn?
Wikipedia states that RSA challenge has been withdrawn.
Does it mean that an efficient factoring algorithm is "just around the corner"?
or are there some other reasons?
If the challenge was still ...
14
votes
3
answers
10k
views
Creating a license system based on asymmetric encryption (RSA or ECDSA)
I’ve spent a couple of days researching the topic of creating a license system for my desktop software. While I fully understand that there’s no perfect copy protection, this approach seems to have ...
14
votes
1
answer
5k
views
Bleichenbacher 1998 "Million message attack" on RSA
I have been reading Bleichenbacher's 1998 paper on a forged message attack on RSA. The paper assumes access to an Oracle that takes a ciphertext $c$ and will check the decrypted text for valid PKCS #1 ...
13
votes
3
answers
20k
views
Is RSA-OAEP deprecated?
I need asymmetric pub/private keypair encryption in JavaScript. Web browsers support RSA-OAEP, which works exactly as I need. But there is a table which lists supported algorithms for web crypto at ...
13
votes
2
answers
3k
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 ...
13
votes
2
answers
2k
views
RSA encryption using multiplication
Generally in RSA we encrypt as $m^e \pmod n$. Will RSA work if we replace the power by normal multiplication? $E = (m \times e) \mod n$ and decryption as $c \times d \mod n$. What will be $d$ ...
13
votes
2
answers
4k
views
Why RSA can't handle numbers above 76?
I'm going to encrypt the characters Zhu, and decrypt them using RSA. I'm using the public key $\{e, n\}$ and private key $\{d, n\}$. The values of $e$, $d$ and $p$ ...
13
votes
2
answers
915
views
What motivated the creation of RSA and ECDH?
Recently I've been learning about cryptography and so far I am loving it. However, there are some things I do not comprehend.
As far as I know, RSA was published in 1979 while New Directions on ...
13
votes
2
answers
20k
views
At what stage is DHE and RSA used during the SSL/TLS handshake?
At what stage of the SSL/TLS handshake is the DHE and RSA used and what is the purpose of using a pre-master secret when you could just use RSA to exchange the symmetric key (i.e. AES) for further ...
13
votes
2
answers
4k
views
Should RSA primes $p$ and $q$ differ in length by "a few digits"?
When generating RSA keys in the original RSA paper it is stated:
to gain additional protection against sophisticated factoring algorithms, p and q should differ in length by a few digits
Why is ...
13
votes
4
answers
10k
views
Is it possible to get an RSA encryption key by comparing the unencrypted and encrypted file?
Exactly what the title says. If I have a RSA encrypted file, and the exact same file but decrypted, can I tell the key that was used from that information?
13
votes
3
answers
15k
views
Recommended key size for DKIM
What is the recommended key length for DKIM? I'm currently thinking about a 1024-bit key vs. a 2048-bit one.
From the crypto point of view for RSA, 2048 or 4096 bits is clearly recommended--no ...
13
votes
3
answers
13k
views
Anatomy of an RSA private key
I'm learning about OpenSSL and public key infrastructure and am curious about the structure of an RSA key and how it's related to its corresponding public key.
I can generate a private RSA key with ...
13
votes
0
answers
298
views
RSA key such that pi deciphers to your name per RSA-OAEP
Can you efficiently construct an RSA public/private key pair with $8k$-bit public modulus such that $C=\left\lfloor\pi\,2^{8k-2}\right\rfloor$ deciphers per RSA-OAEP to your name as a bytestring in ...
13
votes
0
answers
842
views
RSA factorization with special primes
Suppose that primes for RSA modulus are generated using formula:
$P_i(x,y) = \operatorname{next\_prime}(x^{z_i}+y^{z_i}) = x^{z_i}+y^{z_i}+d_i$
where $x,y$ are unknown random numbers with size 128 ...
12
votes
8
answers
13k
views
Cracking RSA (or other algorithms) manually by a savant
RSA cryptography strength comes from the hardness (or so we believe) of factoring big numbers. For key lengths over 2048 bits, it is infeasible for current or near-future computers to factor those ...
12
votes
3
answers
4k
views
Is RSA padding needed for single recipient, one-time, unique random message?
I want a way to encrypt files using this process: https://crypto.stackexchange.com/a/15 . That is: generate a random password, use that to AES-encrypt a file, and use an RSA public key to encrypt the ...
12
votes
4
answers
7k
views
RSA private key integrity check
I am working on a device whose OS provides an RSA Private primitive, where the inputs are the message, and the usual components of a private key. Unfortunately it is bugged so that in some cases of ...
12
votes
1
answer
1k
views
If RSA is only used to encrypt symmetric keys which are random, what's wrong with textbook RSA?
As far as I know, IND-CPA is used to protect against frequency analysis. But if RSA is only used to encrypt symmetric keys, what's wrong with using only textbook RSA because random keys are very ...
12
votes
4
answers
11k
views
How are random numbers for RSA generated? [duplicate]
The RSA public key encryption requires two very large prime numbers as part of its encryption process that serve as secrets. These are typically generated with cryptographically secure random number ...
12
votes
2
answers
3k
views
uniqueness of the RSA public modulus
What is the probability that two separate RSA public moduli are the same? For example, consider a 2048-bit modulus. The number seems to be huge, but the choice for prime factors p and q is much more ...
12
votes
1
answer
32k
views
How much stronger is RSA-2048 compared to RSA-1024?
How much stronger is RSA-2048 compared to RSA-1024? It is hard to imagine very big numbers. So what would be your way to explain the difference to someone who doesn't know much about cryptography?
12
votes
3
answers
11k
views
What are some disadvantages of homomorphic encryption schemes?
I'm doing some self-teaching / research for my own benefit in homomorphic cryptography.
I've studied both additive and multiplicative schemes (Paillier and RSA respectively), but all I can seem to ...
12
votes
2
answers
3k
views
Validating an RSA public key
What kind of tests can be performed on a public key to check if it is likely a valid key? The tests should be relatively fast - i.e. not computationally intensive - and not include modular ...
12
votes
3
answers
6k
views
How to perform authentication without central server in P2P?
How can one be sure that the man who you're talking with is the one who you think he is? i.e. How can one perform authentication in P2P network without a central trust server or Certificate Authority?
...
12
votes
2
answers
5k
views
Is it possible to recover an RSA modulus from its signatures?
Let's say that you have some small number of RSA signatures of known data: you know some pairs $(m_k, c_k)$ such that ${c_k}^e \equiv m_k \pmod n$. If you know $e$, because probably it's one of $\{3, ...
12
votes
4
answers
5k
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 ...
12
votes
3
answers
20k
views
Why can’t DSA be used for encryption?
This question at StackOverflow mentions that DSA cannot be used for encryption. But both RSA and DSA can be used to generate public and private keys, right? Then why can't I use the DSA public key to ...
12
votes
2
answers
4k
views
Safe primes in RSA
It's my understanding that there's no longer a requisite of safe primes for $q$ and $p$ when choosing a RSA modulus. How is it that this does not change the hardness of factoring $N$?
12
votes
1
answer
5k
views
Algorithm to factorize $N$ given $N$, $e$, $d$
I have an RSA public key (public modulus $N$ and public exponent $e$), and the private exponent $d$ of matching private key.
How can I compute $p$ and $q$, the primes factor of $N$ ?
12
votes
1
answer
7k
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:
...
12
votes
3
answers
444
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 ...
12
votes
1
answer
4k
views
What signature schemes allow recovering the public key from a signature?
It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone.
This seems like an interesting property; as far as I know, RSA doesn't share ...
12
votes
2
answers
11k
views
What are advantages of using a HMAC over RSA with SHA-1 hashes?
I am currently studying for an exam and this was a previous question:
Give one advantage of using HMACs over using RSA to sign SHA-1 hashes.
My thoughts are that it has something to do with the ...