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.

learn more… | top users | synonyms

3
votes
1answer
1k views

Is RSA of a random nonce with no padding safe?

Consider the following protocol: Bob has a private RSA key $B_{priv}$, and Alice knows the public key $B_{pub}$. Alice wants to send confidential messages to Bob (no integrity intended). To send a ...
3
votes
2answers
386 views

Small Prime Difference in RSA

In RSA, the $p$ and $q$ should be randomly generated, and they are the same size. The difference between $p$ and $q$ should not be small. Suppose that $u=|p-q|<20$ and $p \times q =...
3
votes
2answers
1k views

Difficulty of breaking RSA for a given key size

Is it true that breaking a 1024-bit RSA key is as difficult as breaking a 128 bit symmetric key (e.g. AES)? I know that breaking a RSA key is equivalent to factoring the modulus $N$. To factor it, you ...
12
votes
1answer
646 views

RSA with probable primes

I am a bit of a newbie to RSA encryption, so please be patient. I understand that for a 4096 bit RSA, the numbers p and q should be prime. And to have the best security, the p and q should both be ...
8
votes
3answers
1k views

Is RSA padding needed for single recipient, one-time, unique random message?

I want a way to encrypt files using this process: http://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 ...
7
votes
2answers
607 views

State of the art RSA key generation

I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis. Beside the key lenght I know there are some weakness in the choice of prime ...
3
votes
1answer
275 views

RSA enc/decryption with multiple prime modulus using CRT

Every information I found on internet about RSA-CRT encryption/decryption uses only two primes. I'm interested in my project in doing that using multiple (up to 8) primes. The general idea is to ...
3
votes
1answer
5k 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 ...
9
votes
3answers
681 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 ...
7
votes
1answer
209 views

In RSA, rationale for prime $p$ with $p-1$ having prime factor $u$ with $u-1$ having large prime factor?

In the 1978 RSA paper, it is recommended, among other things, to choose primes $p$ such that $(p-1)$ has a large prime factor $u$. This was motivated by Pollard's p-1 algorithm. Further, the authors ...
7
votes
2answers
2k views

How much can we compress RSA public keys?

I am wondering to what degree we can define an RSA variant, with a security argument that it is as safe as regular RSA with a given modulus size $m$ (e.g. $m=2048$), in which the public key has a ...
5
votes
1answer
480 views

In textbook RSA with low public exponent, how big does a random message needs to be?

Assume RSA with a public modulus $N$ of $n$ bits, a small odd public exponent $e$, plaintext $M$ a random non-negative integer less than $2^m$ for some integer parameter $m$, with $M\mapsto C=M^e\bmod ...
10
votes
3answers
691 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, ...
9
votes
2answers
9k 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?
16
votes
4answers
2k views

Is Wiener's attack on RSA extendable to larger keys with low hamming weight?

Using small private exponents with RSA improves performance. However, it has been shown (Wiener, 1990) that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the ...
11
votes
2answers
3k 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?
12
votes
1answer
5k views

Why do all SSH-RSA Keys begin with “AAAAB3NzaC1yc”?

My Friend and I have been generating a few ssh2-rsa keys and noticed that all the public keys began with "AAAAB3NzaC1yc". The similarity extended to "AAAAB3NzaC1yc2EAAAABIwAAAQEA" between two keys I ...
4
votes
1answer
773 views

Are RSA signatures deterministic?

If I sign the word HELLO with the mechanism "NONEwithRSA" with the same private key, do I always will have the same signature? A Java example always return ...
3
votes
1answer
1k views

RSA key pair generation using PRNG with same seed

I see a lot of Q/A where persons are trying to generate a specific key pair using static data such as a password. Now say we use a known PRNG (dangerous assumption), seeded with a the data as a static ...
2
votes
1answer
6k views

What is the meaning of “trapdoor” in cryptography?

I do not really understand the meaning of a "trapdoor" in cryptography, so here are my questions: What is the meaning of trapdoor and how can I convert a word or string using a trapdoor in ...
10
votes
4answers
2k views

Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?

I have just learned about using PGP/GPG for email encryption and one thing has always bugged me: How is it possible that a message encrypted with somebody's public key can be decrypted only with that ...
8
votes
4answers
2k 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?
6
votes
2answers
2k views

RSA blind signatures in practice

Hi I have a problem with moving my blind signature implementation from educational (textbook RSA) to more practical (padded RSA) side. David Chaums paper gives a following figure: $r$ - blinding ...
6
votes
5answers
5k views

How do ciphers change plaintext into numeric digits for computing?

For example, in RSA, we use this for encryption: $ciphertext = (m^e \mod n)$ and for decryption. If our message is "hello world", then what number do we have to ...
6
votes
4answers
1k views

How do institutions like banks do RSA with big primes?

When encrypting with RSA it is often infeasible to decrypt by just doing c^d mod n, because for example when using the primes $(p,q)=(12553,1233)$, which are small ...
5
votes
2answers
1k views

Is RSA key size the size of private key exponent?

I have implemented a key pair generation scheme for RSA algorithm. I have taken the length of private key exponent as RSA key size, but then I've got to know that RSA key size is the size of the ...
5
votes
1answer
4k views

Common modulus attack on RSA when the 2 public exponents differ by a single bit

This is an exam question an i have no idea how to recover the message m. John wants to send an encrypted message to mary who has a pair of RSA keys, However, John does not know Mary's public key and ...
4
votes
2answers
2k views

Are there any standards of multi-prime RSA key generation?

FIPS 186-3 specifies a method to generate DSA parameters. Is there anything similar (official standard or widely-accepted recommendation) that shows how to generate the primes for multi-prime RSA?
4
votes
4answers
451 views

Where does the $\varphi(n)$ part of RSA come from?

$e d \equiv 1 \pmod{\varphi(n)}$ Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?
3
votes
2answers
965 views

risk of attacker decrypting RSA ciphertext without public or private key

As I describe in my previous question I am trying to decide if it's worth it for me to use the Offline Private Key Protocol in creating some long term private archives, instead of just going with a ...
1
vote
1answer
6k views

How do I derive the time complexity of encryption and decryption based on modular arithmetic?

I want to calculate the time complexity of two encryption and decryption algorithms. The first one (RSA-like) has the encryption $$ C := M^e \bmod N $$ and decryption $$ M_P := C^d \bmod N. $$ ...
8
votes
1answer
127 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 ...
7
votes
3answers
2k views

Why is the complexity of RSA-1024 80 bit and not 86 bit?

Why is the complexity of RSA-1024 80 bit and not 86.76611925028119 bit? Here is the complexity for the GNFS (pulled from the linked Wikipedia article): $$\exp\left( \left(\sqrt[3]{\frac{64}{...
7
votes
1answer
412 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
2k views

RSA with modulus product of many primes

I would like to ask what happens if we build an RSA system with modulus a product of more than 2 primes, for example let $n=p_{1}p_{2}...p_{L}$. I know only the classical RSA system with $n=pq$ with $...
4
votes
3answers
661 views

P = NP and current cryptographic systems

I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems. My ...
4
votes
3answers
3k views

Is it safer to encrypt twice with RSA?

I wonder if it's safer to encrypt a plain text with RSA twice than it is to encrypt it just once. It should make a big difference if you assume that the two private keys are different, and that the ...
3
votes
1answer
1k views

Why do we need in RSA the modulus to be product of 2 primes?

I think I roughly understand how the RSA alorithm is working. However, I don't understand why we need the $N$, which we use as a modulus, to be $pq$ for some large primes $p, q$. I vaguely know it ...
3
votes
2answers
2k views

What does an RSA signature look like?

I am using OpenSSL libs to generate signatures. Internally, I learn that a signature is a hash of the message with some padding added to it. I am trying to understand the structure of a signature. If ...
3
votes
2answers
370 views

Is there a way to systematically calculate the public exponent $e$ in RSA?

I'm learning RSA in one of my classes and we were given a problem: $p = 5$, $q = 11$ I have done the following steps: $n = 5 \cdot 11 = 55$ $\phi = (5-1)\cdot(11-1) = 40$ I know that to ...
3
votes
0answers
51 views

IND-CCA1 RSA padding?

I've found a way to complete a task which I'd solve with passwords or by sending keys over the wire (otherwise) by using RSA's homomorphic property. I'm restricted to RSA (any padding; for hardware ...
3
votes
2answers
3k views

How to calculate the maximum output size for data encrypted with a RSA Private Key?

I have an an encryption algorithm I am working with that looks like this: prv_key_enc(sha1_hash(data)) Where, the RSA parameters are: RSA/ECB/PKCS1Padding 1024 ...
2
votes
1answer
598 views

using Post-quantum asymmetric ciphers instead of RSA

We can't trust RSA to encrypt our Emails so what is best post-quantum cryptography system as alternative for RSA which provide good security and don't be breakable? because McEliece cryptosystem looks ...
2
votes
2answers
131 views

Present an attack for the combination of OTP and textbook RSA

Let $N=p \times q$ where $p$ and $q$ are two primes. Compute $\Phi (N) = (p-1)(q-1)$. Choose $e$ s.t. $1 < e < \Phi(N)$ and $gcd(e,\Phi(N))=1$. Compute $d = e^{-1}(mod \ \Phi(N))$. Set ...
2
votes
1answer
305 views

RSA signatures without padding?

Suppose I have a message $M$ for which I generate an RSA-2048 digital signature as follows: $H = H(M)$, $H(M)$ being the SHA-256 of the message $M$ $S = H^d \bmod N$ Assume $N = pq$ is properly ...
2
votes
2answers
907 views

Why RSA uses {d,n} as private key instead of {e,n}?

While studying the RSA algorithm I referred to some books and some sites such as RSA (wikipedia) and all of them chose {d,n} as the secret (private) key and release {e,n} as the public key but as d ...
1
vote
1answer
931 views

How to jusify {e,n} is a valid RSA public key?

I have a two set of key {36,77} and {50,117}, How can validate if it is a valid RSA public keys? Is there any simple method?
1
vote
2answers
680 views

RSA problem if i choose two specific small prime numbers?

I know that rsa normally is made to make it with big integers, but i trying to make the algorithm myself (with the help of wikipedia) and I´m making it with small numbers to track the problems easily. ...
21
votes
2answers
20k views

Signatures: RSA compared to ECDSA

I'm signing very small messages using RSA, and the signature and public key are added to every message, which requires a lot of space compared to the actual content. I'm considering switching to ...
16
votes
2answers
16k views

When to use RSA and when ElGamal asymmetric encryption

If i am not wrong in cryptography there are 2 basic cryptographic schemes for public key cryptography. RSA encryption whose security is based on the infeasibility of solving the factoring of big ...