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.

Filter by
Sorted by
Tagged with
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 ...
user128226's user avatar
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 ...
Gustave's user avatar
  • 260
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 ...
Tomas's user avatar
  • 153
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, ...
e-sushi's user avatar
  • 17.9k
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 ...
Emilio Ferrucci's user avatar
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 ...
Ethan Heilman's user avatar
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 ...
Maarten Bodewes - mod election's user avatar
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 ...
izzle's user avatar
  • 591
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, ...
Andrey's user avatar
  • 847
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): ...
Frederick The Fool's user avatar
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 ...
user48579's user avatar
  • 149
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 ...
user3719749's user avatar
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 ...
Stefano Palazzo's user avatar
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 ...
Conrado's user avatar
  • 6,414
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 ...
Nail Jay's user avatar
  • 317
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 ...
Matt Elson's user avatar
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 ...
Jus12's user avatar
  • 1,659
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 ...
CodeX's user avatar
  • 263
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 ...
Pankrates's user avatar
  • 593
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 ...
Tomas M's user avatar
  • 239
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 ...
user86295's user avatar
  • 131
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$ ...
Vinny's user avatar
  • 241
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$ ...
mko's user avatar
  • 261
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 ...
a-lawliet's user avatar
  • 151
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 ...
Ali Gajani's user avatar
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 ...
user avatar
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?
aaro4130's user avatar
  • 141
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 ...
Lut's user avatar
  • 131
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 ...
mbigras's user avatar
  • 241
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 ...
fgrieu - mod election time's user avatar
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 ...
Kamil Pliszka's user avatar
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 ...
derjack's user avatar
  • 181
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 ...
jrgray's user avatar
  • 123
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 ...
M.M's user avatar
  • 223
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 ...
wlad's user avatar
  • 1,239
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 ...
Billy ONeal's user avatar
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 ...
Naka Wai's user avatar
  • 163
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?
user27296's user avatar
  • 121
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 ...
John Smith's user avatar
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 ...
Maarten Bodewes - mod election's user avatar
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? ...
Abzac's user avatar
  • 263
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, ...
Myria's user avatar
  • 2,575
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 ...
Gilles 'SO- stop being evil''s user avatar
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 ...
Lunar Mushrooms's user avatar
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$?
boran's user avatar
  • 131
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$ ?
user61922's user avatar
  • 123
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: ...
user avatar
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 ...
Ben Page's user avatar
  • 223
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 ...
lxgr's user avatar
  • 1,788
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 ...
Shane's user avatar
  • 223

1 2
3
4 5
56