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
3answers
1k views

How can I avoid calculating with huge numbers when implementing the RSA algorithm

There is 26-letter English alphabet. There is the plain text: TRYAGAINLATER. I need to encrypt it by RSA algorithm with the public key 53. What is the ciphertext? ...
3
votes
1answer
384 views

When would I need DSA as opposed to RSA for digital signature?

The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key. This multiple encryption is a pretty expensive process since public key encryption is so ...
3
votes
2answers
285 views

Is there any reason to use RSA or DSA when we have ECC?

I am having trouble coming up with a use case for RSA or DSA. It appears that ECC is better in every way. Is this true? I am looking for cases where RSA/DSA is superior to ECC, not where it is used ...
3
votes
2answers
394 views

Key space vs Cardinality of 1024-bit RSA

I have been trying to figure out the encryption key space, and cardinality of 1024-bit RSA. From my understanding, the key generated from 1024-bit will be primes greater than $2^{1023}$ but less than $...
3
votes
2answers
385 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
4answers
1k views

RSA with composite numbers

It has been said that RSA uses a modulus product of two prime numbers for security reasons. But does RSA even work correctly if we allow composite integers instead? I think that the answer is "NO". ...
3
votes
2answers
255 views

Are there any papers explaining how to port textbook RSA to realworld RSA?

Are there any papers, books, or link where it explains how the plain vanilla "textbook RSA" is actually implemented in practice with all the padding and stuff? Basically, I would like to know the ...
3
votes
2answers
716 views

Does RSA padding have to be unpredictable if the payload is?

I'm trying to understand the precise requirements on padding when using RSA for encryption. Suppose Alice uses RSA to encrypt a payload $M$ that cannot be guessed (say, a random nonce): Alice send $\...
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
1answer
839 views

Theoretical attack on RSA

The high security of RSA is granted, because it is very hard to factorize $$ N = p * q $$ Nevertheless, there is actually no need of factorizing $N$, in order to generate the $Private$ $Key$, but the ...
3
votes
2answers
603 views

RSA performance

I was wondering what is the performance bottleneck in RSA algorithm? Is it the size of message, calculating the modular inverse, exponentiation? Say I have a fixed value of n to encrypt and decrypt ...
3
votes
4answers
3k views

Why is RSA encryption significantly faster than decryption?

I am designing an implementation of RSA . I recorded computation times in Java by using System.currentTimeMillis(). It returned an encryption time of 0.05 ms and ...
3
votes
3answers
234 views

Can the encryption exponent e be greater than ϕ(N)?

So I was just wondering in RSA, can the encryption exponent e be greater than ϕ(N)?? For an examples sake, lets just say N = 707, so p = 101 & q = 7. So, we have ϕ(707) = 600. Can I have e = 707?...
3
votes
2answers
308 views

RSA: Recover e given factorization of N and plaintext/ciphertext pair

Is there a way to recover the public exponent e (assume in this case it is in fact not public) used in an encryption if I know the following: Factorization of <...
3
votes
2answers
513 views

Is it safe to reuse a symmetric key when using asymmetric encryption?

I've written a C# Library that I hope will be used for security purposes in a commercial application. The application will communicate through the internet and not on an internal network. I am using ...
3
votes
2answers
417 views

Avoiding overflow when encrypting with RSA

When encrypting with RSA one calculates $ m^e \pmod n $ by doing the following: m^e % n Where $m$ is what we encrypt. Often $e$ is a very big number to make it ...
3
votes
1answer
798 views

What's the main difference between Pohlig-Hellman and RSA?

Both Pohlig-Hellman and RSA perform encryption and decryption by exponentiation modulo some integer ($p$ prime for PH, $n$ composite for RSA). They both use a key $e$ as the exponent to encrypt a ...
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
279 views

Isn't the deterministic property of (EC)DSA a security problem?

From what I read in Wikipedia's article "Elliptic Curve DSA ~ Security", the "deterministic" generation of $k$ can help prevent certain type of attacks (such as the one happened to Sony). However, ...
3
votes
1answer
746 views

Textbook-RSA meet-in-the-middle attack against other RSA based schemes?

A “meet-in-the-middle” (not “man-in-the-middle”!) attack on textbook-RSA was presented to me. The only requirements for it was that the attacker gets the output of RSA and the public key, and that the ...
3
votes
4answers
949 views

RSA by hand - did I do something wrong? (c = m on encryption)

to understand RSA better I am doing a little calculation by hand, this is what I got: Choosing: $p = 3$ $q = 5$ $n = 15$ $\phi(pq) = 2 \cdot 4 = 8$ $e > \phi(n) => e = 13$ $e \cdot d = 1 \...
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 ...
3
votes
2answers
281 views

Finding Private key in RSA with public key, cipher text and plain text

Is there a known 'non-brute force' method of determining a private key in an RSA system when all other parameters are know? I found the values of a ciphertext ($C$), its corresponding plaintext ($P$) ...
3
votes
1answer
131 views

How do I attack an RSA setup where e is even?

As a challenge, we were shown an RSA setup where we have a big $n$ (617 decimal digits), $e=4$, and asked to recover three messages. (However, the messages are padded to the same length as the key ...
3
votes
2answers
251 views

Perfect Forward Secrecy in TLS

I read that TLS does PFS using Diffie Hellman. However, DH can be used even without certificates - so how is DHE-RSA better than plain DHE? Is DHE a insecure algorithm, that DHE-RSA is needed?
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
1k views

Openssl & RSA : how many public exponents are possible?

I would like to know if it is possible to set the public exponent we want with "OpenSSL RSA" or if it is really limited to 2 possible exponents: 3 65537 If yes, why ?
3
votes
2answers
930 views

If we can find prime numbers larger than 17 milion digits, why can't we find all 1024bit primes? [duplicate]

"Largest Known Prime Number Discovered; Has 17,425,170 Digits" http://www.sciencedaily.com/releases/2013/02/130213225424.htm If we can find prime numbers larger than 17 milion digits, why can't we ...
3
votes
3answers
1k views

If RSA is limited to 117-200 bytes or so, is that a very limited use case?

Am I missing something, or is RSA very very limiting when it comes to ecrypting data when it comes to the actual message size? I have read that you can only encrypt a message of around 117 to 200 ...
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
1k views

How to decrypt this RSA-like cipher

Suppose we have a RSA-type Modulus $n = pq$ with $p,q$ prime. We also pick a random public exponent $e$ with $\gcd(e,\varphi(n)) = 1$ and compute the private exponent $d$ with $de \equiv 1 \pmod{\...
3
votes
2answers
618 views

How does the cyclic attack on RSA work?

I am trying to get the idea of cyclic attacks againts assymetric RSA encryption. Taken from Handbook of applied cryptography . Let $k$ be a positive integer such that $$c^{(e^{k})} = c\mod n \tag{1}....
3
votes
2answers
172 views

Why do we need Euler's totient function $\varphi(N)$ in RSA?

After we calculated $N = p * q$, we calculate $\varphi(N)$ and use it later to determine $e$ (PR) and $d$ (PU). But why? For decryption and encryption we only use $N$ and don't need $\varphi(N)$. So ...
3
votes
2answers
250 views

Why are recomended RSA key lengths so high? [duplicate]

I was checking for authoritative sources to back up my recommendation of a minimum RSA key length of 1024 and was shocked to find that NIST 800-56Br1 and FIPS 186-4 both recommend at least 2048 bits ...
3
votes
1answer
172 views

RSA private key finding method

Bob uses RSA with $p=83$ and $q=103$. His public key is $e=445$. Alice claims that she can calculate Bob's private key without using the definition $d=e^{−1}\bmod φ(n)$? But how?
3
votes
1answer
173 views

Checking the integrity of RSA public key

Let's say I need to verify a digital signature and the public key is stored in untrusted storage which I need to fetch before I verify the digital signature. However, I can store the cryptographic ...
3
votes
1answer
136 views

Relationship between exponent and modulus in RSA (as RSA properties as listed in X.509)

In one of my assignments, I had the following question (Please read on. Not a homework assignment :) ): X.509 (1998 version) lists properties that RSA keys must satisfy to be secure. One such ...
3
votes
1answer
142 views

RSA with $\lambda(n)$ or $\varphi(n)$

The PKCS #1 v2.0 specifications suggest using $\lambda(n) = \mathrm{lcm}(p-1,q-1)$. What is the benefit of choosing $\lambda(n)$ over $\varphi(n) = (p-1)(q-1)$ in RSA key generation?
3
votes
1answer
90 views

For which RSA moduli, precisely, is $e=d$ for all $e$?

This question shows that there are at least two valid RSA moduli $n$, namely $35$ and $91$, such that for any $e$ coprime to $\lambda(n)$, $$e^2\equiv1\mod\lambda(n)\text.$$ Reading the linked ...
3
votes
2answers
1k views

Chosen plaintext attack on textbook RSA decryption

Let $(n,d)$ be an RSA private key and $(n,e)$ the corresponding public key. Generate a secret random $r$ from $(\mathbb{Z}/n\mathbb{Z})^*$ Compute $C’ = C (r^e) \bmod n$ Submit $C’$ as a chosen ...
3
votes
2answers
4k 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 ...
3
votes
2answers
964 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 ...
3
votes
1answer
357 views

RSA Key generation Public exponent too big

I'm currently writing a paper about RSA (a self-chosen subject). I'm writing about the key-generation in RSA, and I have problem finding the public exponent e. I have chosen p = 61 and q = 53. Then ...
3
votes
1answer
98 views

Do equivalent RSA keys exist?

If $m^{ed} \bmod n = m$ for message $m$, public key $e$ and private key $d$, then adding any integer multiple of $n$ to $m^{ed}$ still equals $m$ modulo $n$. Supposing it exists, how do I find an ...
3
votes
1answer
88 views

RSA Digital Signature vs Elgamal Digital Signature

What are the advantages of RSA signatures against ElGamal signatures? Is there a situation in which it would be better e.g. to use RSA signatures?
3
votes
1answer
78 views

Highest prime factor that is Safe for a particular scheme

My question is how many bits of prime number is secure so that it cannot be factored from very large number? Until today how large prime factor is found in large number? Quantum computing find ...
3
votes
2answers
82 views

Chosen-Message-Attack RSA-Signature

I know that because of the multplicative property of RSA $s =(s_1s_2) \bmod n = (m_1m_2)^d \bmod n$ If Oscar wants to sign now an own message $m$ he chooses another message $m_1$ with $\gcd(m_1,n)=...
3
votes
3answers
117 views

Can an adversary distinguish a private key from a pseudo-random string of the same length?

Apologies if this is a dumb question but allow me to describe the dilemma I have: Suppose that I am protecting a private key on a device using a password & PBKDF2. The obvious attack would be an ...
3
votes
1answer
60 views

Selective and existential unforgability of signature schemes

I understand that one can define EUF-CMA of a signature scheme is terms of a game where the adversary is allowed to query signatures on messages of his choosing, and at the end of the game he must ...
3
votes
1answer
111 views

Should I be concerned about padding oracle attacks if the lifespan of my key is ~1 minute?

I'm using 4096-bit RSA to encrypt a 256-bit AES key generated client-side. The RSA ciphertext is then sent to the server, and the server decrypts the RSA ciphertext to acquire the AES key. ...